summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
...
* Update fuzzer for chapter 12. (#104)XmiliaH2024-08-182-37/+73
|
* Some updates to Chapter 3 docs based on feedback by Yarden (#100)Dibyendu Majumdar2024-08-161-12/+22
| | | | | * Some updates to Chapter 3 docs based on feedback by Yarden * Apply feedback from Cliff
* Scope docs (#99)Cliff Click2024-08-153-28/+48
| | | | | * More scope docs * readme updates
* #92 Update readmesdibyendumajumdar2024-08-063-56/+9
|
* Fix chapter12 grammarThalia Archibald2024-08-062-130/+1
|
* Update README.mdCliff Click2024-08-061-2/+22
|
* More error cases, error checkingCliff Click2024-08-066-11/+74
| | | | disallow e.g. "struct x { int i; }; x = new x; x.i=3.14;"
* Fix graph draw with field namesCliff Click2024-08-064-7/+27
| | | | Allow co-recursive defs
* Ref types workingCliff Click2024-08-0625-149/+273
| | | | | | | | | GCM uses a breadth-first pass for schedule-late instead of a post-order; the post-order walk depends on StoreNodes being pinned, which is true in C2 but not Simple. Move GCM call out of IterPeeps. Struct field init is "makeInit()" not integer zero. Rename Type._print to print. Store,Load prints include field name.
* chapter 13 from 12, splitting out ref fields in structsdibyendumajumdar2024-08-063-2/+132
|
* Copy chapter12 -> chapter13Thalia Archibald2024-08-0675-0/+10930
|
* Unify type parsingCliff Click2024-08-051-48/+22
|
* Update Ch12 readmeCliff Click2024-08-051-1/+45
|
* Fuzzer nit picksCliff Click2024-08-053-8/+4
|
* auto-widen on assignCliff Click2024-08-052-125/+11
|
* missing null checkCliff Click2024-08-052-2/+121
|
* A series of minor fuzzer bugsCliff Click2024-08-055-27/+28
|
* Better filter on Load cloneCliff Click2024-08-052-6/+20
|
* Float bugsCliff Click2024-08-0520-42/+113
| | | | | | | | Fix bug infinite loop finding. Fix inf loops before printing graph. Missing float unary negate . Generator makes float exprs Fix missing dep in LCA finding
* Clean up floatsCliff Click2024-08-057-53/+48
| | | | Better pattern in the compiler.
* a little FP cleanupCliff Click2024-08-052-7/+6
|
* more fp bugfixesCliff Click2024-08-054-6/+5
|
* minor FP bugsCliff Click2024-08-056-17/+23
| | | | | Fix bug AddF+0, SubF+0 Fix bug flipping EQ sides.
* Add Float supportCliff Click2024-08-0513-47/+463
| | | | Parsing float constants; float +-*/, auto-widening float expressions.
* minimal empty test so "make" doesnt complainCliff Click2024-08-051-0/+11
|
* #92 chapter 12 start from chapter 11dibyendumajumdar2024-08-0569-0/+10400
|
* TODO comments (#94)Cliff Click2024-08-044-4/+12
|
* Update README.md (#93)Cliff Click2024-08-041-2/+16
|
* Fix grammar and forward-port minor changes (#91)Thalia Archibald2024-07-0136-159/+132
| | | | | | | | | | | | | | | * Backport test exception handling to chapter 1 * Add unary ! to chapter 10 and 11 grammars * Lex { } ! as punctuation * Forward-port format whitespace * Forward-port test organization * Forward-port replace build-graphs.sh with Makefile * Add chapter title to chapter 11
* #85 #80 missed details (#90)Dibyendu Majumdar2024-06-301-0/+29
|
* #80 #85 apply bug fixes from chapter10 (#89)Dibyendu Majumdar2024-06-3021-173/+210
| | | | | | | | | | | | | * #80 #85 apply bug fixes from chapter10 * #85 #80 more detail regarding anti-dependency * Remove Util.eq Was enforced interning of strings, not needed here. --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Cliff's GCM implementation for chapter 11 (#88)Dibyendu Majumdar2024-06-3087-3/+13928
|
* Backport tests (#87)Thalia Archibald2024-06-2190-3315/+3892
| | | | | | | | | | | | | | | | | * Fix unexpected number parse errors * Add chapter titles * Split test files by chapter * Backport rename Fuzzer08Test to FuzzerWrap * Replace graph build scripts with Makefile * Backport Chapter05Test.testRegress1 * Backport require space after 'return' * Backport check EOF after return statement
* Format whitespace (#86)Thalia Archibald2024-06-21273-4025/+4018
| | | | | | | | | * Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces
* peep dead CFG diamond (#83)Cliff Click2024-06-012-1/+11
|
* Add a minor peep to settle a CCC discussion (#82)Cliff Click2024-05-292-9/+19
| | | | | * Add a minor peep to settle a CCC discussion * remove junk test
* Bugfix 78 (#81)Cliff Click2024-05-1319-163/+164
| | | | | | | | | | | | | | | | | | | | | | | * Missing idepth for LoopNode * backedge code removing a Parser keep Stop subsuming a node parser yet needs * Missing addDep * LoadNode cloning peep better profit The LoadNode cloning peep cannot clone around a Loop unless its profit on the backedge, otherwise might infinitely clone around backedge. peep: x - (-y) is x+y peep: -(-x) is x * Drop alias from Field Field is intended to be a part of a Type; as such is abstract, immutable, and true for ALL Time and all TypeStructs which have the same field. Drop the alias and struct from Field. Drop field reset. The alias#s are decided in the Parser, and have a lifetime for the compilation unit; the Fields have infinite lifetime. Minor bugfix idepth caching * Remove emacs junk file
* Fix a series of recent bugs (#79)Cliff Click2024-05-079-55/+47
| | | | | Simplify idom usage; removes a difficult to maintain cache, which does add a (rare) big-O slowdown. Suggestions welcome. Cut outs for some peeps on various dead/dying graphs.
* Ch10 Evaluator (#77)XmiliaH2024-05-057-203/+931
| | | | | | | | | | | | | * Update graph evaluator for ch10 * Update tests to use the new evaluator * Fix anti-dep issue * Fix anti-dep issue * Add comments to the scheduler * Use j.u.Stack and rename BuildBlock
* Documentation updates (#76)Dibyendu Majumdar2024-05-0215-327/+913
| | | | | | | | | | | | | | | | | | * More clearly explain why we do not have an AST in the implementation * Improve the description of type lattice. Cross reference to future chapters. * Minor update * Add lattice visual Revise the text describing meet. * minor update * Add a lattice visual to the text * Update the lattice visual. Add description of the new edges in the SoN graph
* Ch10update (#75)Dibyendu Majumdar2024-04-2818-520/+1149
| | | | | | | | | | | | | | | | | | | | | * Store-after-Store peep * Load-after-Store peephole * Fix graph viz mem edge color bug * Scalar replace loop carried dependence * #67 Dead Not node hanging around - if we add a Not in the upcast then add it to the IterPeeps worklist to ensure it gets cleaned up. We don't see the Not node in the parser hence we cannot do a peep on it there. * #67 Update visuals. Add description of Store-Store and Store-Load peeps. Add examples. * #67 Undo the change that wasn't supposed to be committed! * #67 Update description of the Store-Store and Store-Load peepholes --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Ch10 (#74)Dibyendu Majumdar2024-04-2366-10/+10326
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Chapter 10 start * #67 language grammar for chapter 10 * #67 Fix chapter title * #67 Fix typo * #67 assignment to fields * #67 Struct var decl must be initialized * #67 Start to describe memory and aliasing * #67 revision * #67 Start to describe how we construct the graph * #67 Start to describe how we construct the graph * #67 Start to describe how we construct the graph * #67 Parse struct declaration * #67 WIP parse expressions and statements involving struct vars * #67 WIP parse store expressions * #67 WIP parse load expressions * #67 WIP first go at adding aliases and memslices * #67 WIP A store should get bound to the $mem alias replacing previous node * #67 WIP Add MergeMem node * Update script generator to new features (#68) * #67 WIP Drop MergeMem node * #67 WIP Drop MergeMem node * #67 WIP Improve parsing of postfix expressions * #67 WIP Improve parsing of postfix expressions * #67 WIP Update xmeet - these types can only meet another of the same type * #67 WIP Phi's compute should return input type if input is a MemPtr even if region is in progress because parser needs the correct type * #67 WIP If a null meets a non-null ptr then non-null wins; but ideally we want to retain type of null so we do not have this problem * #67 WIP If a null meets a non-null ptr then non-null then the result is type|null * #67 WIP Fix TypeMemPtr.eq() and also intern struct types * #67 WIP Add missing hash and eq implementations Also refactor common code to get field from ptr * #67 Add START as input to New (as proxy for Mem). Other minor adjustments * #67 Phis widen type inside a loop during parse * #67 Fix redeclaration bug * #67 Small refactor * #67 Add an LLVM inspired IR printer based on post by Yasser A * #67 Add instructions to initialize fields of a struct after a new * #67 Make New's ctrl input the current ctrl rather than Start * #67 Refactor to make it cleaner * #67 Fix bug - interned types should be cleared * #67 Fix bug - new node must be kept so that its not prematurely killed * #67 Fix bug - we must do a depp comparison of structs because types get interned and we can't easily clear the interned types across runs, this means we can end up with structs retaining definitions from older runs. * #67 Refactor * #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input * #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input * #67 Tidy up printing and add expected result on tests * #67 Refactor TypeStruct * #67 Refactor TypeStruct When printing IR in new format - show the projection index * #67 Revise the lattice for ptr types to make it more complete * #67 Revise the lattice for mem and struct types. Add initial test * #67 Refactor how we compute phi type * #67 Refactor how we compute phi type * #67 Use the generated graph but an edge is missing in the graph - to be investigated * #67 One more tweek * Partial work on ch10, some tests busted Revamp Types Mem, MemPtr, Struct, FIeld. Add tests to enforce theoretical rules properties., Add parsing "?" to allow nullable types. Enhance GraphViz to show off mem better. Strip trailing WS in many files. * Strip trailing WS * Post-peephole errors Some nicer error reporting for types. Mem Projs following StartNode are indexed by alias, but may have "holes" in the set of projs. * WS cleanup * Simplify TMP dual Add more test type Rename test type so makefile picks it up Failing 1 test * Scopes and Phis track declared type ...not the initial type. * A fuzzer found bug * Some changes on the fuzzer and maybe faster reducer (#69) * WS and printing changes * Kotlin style null checks (partial) Allow `ptr=rand?; if( ptr ) ptr.field` where the if-test upcasts the ptr to not-null. Field assignments are expressions not statements: `if( (ptr.fld=rez) !=null ) .... ` Many WS changes. * missed cleanup * Fuzzer update (#71) * Update script generator * Fix script generator * Reset type cache to prevent alias blowup (#70) * Reset type cache to prevent alias blowup * Remove the default intern Just reset the UNIQUE_ALIAS number. Intern table doesn't care, that's the whole point of the intern table. Passes existing tests, but fuzzer finds some new stuff * Fix a few of the fuzzer bugs More to come * Fix one more fuzzer bug --------- Co-authored-by: Cliff Click <cliffc@acm.org> * Fix script generated generating invalid code * Greatly simplify Cast usage Casts peephole normally. Added needed Phi optimizations to remove excess casts. Fuzzer bug fixes: Need a plain kill unused on worklist. MemOp error handles aTOP/BOT input. * #67 Add description of lattice to the doc Update grammar - add the '?' nullable syntax Rename VOID to PTR * #67 Some renames * #67 some more text re lattice * #67 Fix the alias ID start to 2 * #67 Revise lattice diagram and doc * #67 Start describing the parser changes and Null Pointer analysis * #67 Draw lattice diagram using graphviz * #67 Revisions to text * #67 Improve description of alias classes * #67 Some renames to make code clearer * #67 Describe null pointer analysis * Fix script generated generating invalid code (#72) * updates to readme shorter example names to make a nicer graph * #67 Revise top level README * #67 Revise top level README --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: XmiliaH <xmilia.hermit@gmail.com>
* fix small typo in chapter 5 (#73)David Rubin2024-04-231-2/+2
|
* Chapter 9 (#66)Dibyendu Majumdar2024-03-0362-7/+8067
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * chapter9 * merge fixes to chapter8 * Ch 9 notes * Ch 9 work Add a Iterate phase, after parsing. Add a Worklist with fast dup removal & rand pull. Add a Node.iter() call which returns progress or null. Peephole calls it. Iter() also asserts that Types make monotonic progress. Intern all types, so we can do a cheap/easy "isa" test. * GVN * rename temporarily * Apply Cliff's worklist changes * Apply Cliff's GVN changes * Revert "GVN" This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f. * Revert "Ch 9 work" This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876. * Fix 3-1+2 Was computing as 3-(1+2) == 0, not 4 as expected. Add tests. Unlock in swap12. * Missed some cut-n-paste changes * Break up the test file per-chapter * Fix keep-alive while looping expressions Must "hook" LHS prior to calling peepholes * Ch9 Region optimization Bug fix, GVN hits 2 inProgress Loops Bug fix lifetime tracking when parsing dead code Bug fix debug find call GraphViz post-iterate * Readme overhaul Progress on Ch 9 readme * Fix bugs hashcode Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on. Proj relies on _idx field, Phi needs a !inProgress check. * Constant nodes print "#" before con * Add a farther neighbor check Peeps that check more than the nearest neighbor register a dependency on the Node that failed them. Should that Node later change, the peep root is put back on the worklist and revisited. * Fix addDeps assert Unwind golden test print, print smarter. Unlock edges in subsume * Update README * shuffle adddeps forward one its needed again shortly in another test, so just cover it now * Fix fuzzer bugs Peep x+(-y) to x-y Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong. Deleting an input can recursively delete the self-node. When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger. Missing addDep in Phi Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2" Make Work list deterministic between tests. * Update fuzzer to run iterate (#62) * Update fuzzer to run iterate * Work seed is now reset by reset * A few more fuzzer tests Set _type in iter() even later, better debugging. Handle dead active scopes in visiualizer. Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter. Type.isConstant is true strictly for lattice centerline constants. Clean up TypeInteger. ideaj warning removal * Fix all fuzzer bugs iter() does not call peep(), instead peep() is self-recursive. This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist. Div, Minus, If all monotonic. Catch a bunch of progress issues. Robustify IRPrinter and Iterate and Region ideal * Reducer could run into an infinite loop (#63) * Write up how the Evaluator works (#64) * Write up how the Evaluator works * Some small improvements and a slightly better wrap up. * Series of fuzzer bugs. Fix monotonicity for all data nodes. Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes. Fix general progress bug allow high Types as constants. Fix progress Region 1-input has obvious idom. Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name. Fix invert comment in TypeInteger * All fuzzer tests pass Turn off expensive assert accidentally turned on CSE needs to join types. Add a type join. Missing dep in Phi * More README * Hacking alternative way to fix the type compute * Node is no longer IntSupplier Renamed Work to WorkList Renamed Iterate to IterOptim Renamed Node.iter() to Node.peepholeOpt() WorkList expects elements to be of Node * Add an example of GVN * Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does. * Add a second example of GVN benefits * Fix typo * Add example of worklist opt * Prepare to allow alternative post parse worklist opt * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * The RPO list was incomplete as it only identified the subgraph accessible from the STOP node. * Fix iter count * Add test suggested by Xmilia * Fix bug where after the region is peeped the phis get consistent number of inputs * Fix bug where after the region is peeped the phis get consistent number of inputs * Dump out stats on how many nodes we peepd during the post parse iterative opt. * Make it easy to switch the IterOpt * Use deps based worklist by default * Sharper worklist add * Copy across Cliff's changes * Merge changes to Iterate * Revert failing change * Update readme * Add comments / update docs to explain the patterns where we call addDep(). * As before, unconditionally made dep a dependent of region. * Fix a lot of missing dep issues Rename IterOptim -> IterPeeps Some grammar changes in comments & readme * Bump up fuzzer limits, more testing Missing dep in idom calc in IfNode. Missed idom cache clear on Region edit. * Remove RPO based peeps O(n^2) behavior * Minor updates README * fix compile bug --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
* Cleanup fuzzer and add java docs (#61)XmiliaH2024-02-067-310/+556
|
* Some minor fixes found via fuzzing (#60)Cliff Click2024-01-155-10/+29
|
* Merge Cliff's fixes (#59)Dibyendu Majumdar2024-01-155-2/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #52 Update chapter8 to align with chapter7 * #52 Update chapter8 to align with chapter7 * #52 Fix spacing * #51 get started on break and continue * #51 get started on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * break & continue scopes are made lazily, and merged into as discovered Drop ContBreak. Drop ScopeNode.addScope. Add a simple mergeScopes. Simplify Region.inProgress; drop from child classes, use in Region. Add a ConstantNode.XCONTROL shortcut. * Fix some regressions * Error on dead code after break/continue * A more robust dead-def check * Fix for dead loop-back path * Fix scope shadowing bug with continue/break Turn on LAZY phis by default; fix minor golden test results * Fix a case with both break & continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 fix erroneous push of scope * #51 fix import * #51 update test expected results * #51 Start Chapter8 writeup * #51 Start Chapter8 writeup * #51 _scope needs killing after continue * Add graph evaluator (#56) * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 update code comments / add assertion * #51 revert assertion * #51 evaluate graph to verify test outcome * #51 add code snippets * #51 add examples * Cleanup README Comment for usefullness of true Loops. Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation. Flow long lines. Remove LAZY flag, set as `true`. Fold up true tests. * minor comment * #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop * #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error * #51 Update main README to link to chapter 8 * Remove useless test * Fix regression for dead infinite loop Add shortcut to fancy IRPrettyPrint --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
* Add fuzzer (#58)XmiliaH2024-01-153-0/+578
| | | | | | | | | * Add fuzzer * Add fuzzer --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Sync changes to previous chapters (#57)Dibyendu Majumdar2024-01-1515-74/+53
| | | Also fix broken links in README
* Implement break and continue (#55)Dibyendu Majumdar2024-01-1418-82/+2140
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #52 Update chapter8 to align with chapter7 * #52 Update chapter8 to align with chapter7 * #52 Fix spacing * #51 get started on break and continue * #51 get started on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * break & continue scopes are made lazily, and merged into as discovered Drop ContBreak. Drop ScopeNode.addScope. Add a simple mergeScopes. Simplify Region.inProgress; drop from child classes, use in Region. Add a ConstantNode.XCONTROL shortcut. * Fix some regressions * Error on dead code after break/continue * A more robust dead-def check * Fix for dead loop-back path * Fix scope shadowing bug with continue/break Turn on LAZY phis by default; fix minor golden test results * Fix a case with both break & continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 fix erroneous push of scope * #51 fix import * #51 update test expected results * #51 Start Chapter8 writeup * #51 Start Chapter8 writeup * #51 _scope needs killing after continue * Add graph evaluator (#56) * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 update code comments / add assertion * #51 revert assertion * #51 evaluate graph to verify test outcome * #51 add code snippets * #51 add examples * Cleanup README Comment for usefullness of true Loops. Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation. Flow long lines. Remove LAZY flag, set as `true`. Fold up true tests. * minor comment * #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop * #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error * #51 Update main README to link to chapter 8 * Remove useless test --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-16 20:37:58 +0000