summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
...
* Chapter8 update to sync with latest changes (#53)Dibyendu Majumdar2023-12-2012-88/+148
| | | | | | | * #52 Update chapter8 to align with chapter7 * #52 Update chapter8 to align with chapter7 * #52 Fix spacing
* Backport some of the code refactoring to previous chapters (#50)Dibyendu Majumdar2023-12-0774-905/+1414
| | | | | | | | | | | * #44 Revise docs and comments * #44 Add starting scope to xScopes * #44 back some of the code refactoring port to previous chapters * #44 add_def should not be public * #44 add_def should not be public. Rename method names so that they are camelcase
* Chapter 7 (also 8 but not officially) (#48)Dibyendu Majumdar2023-12-0375-13/+9729
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #44 Start on chapter 7 * #44 Temp hack on printing to not break on cycles. Parse while statement. * #44 Remove unnecessary method * #44 Remove unnecessary phi map * #44 Phi should have existing nodes from both scopes as input * #44 We need to only insert phis once for each name that is looked up. To do so, we need to know when a named is looked up first time inside the loop body. The phi must have its second input added later on after the loop is fully parsed. * #44 Add phi also when update() is called. Only add phi if name was known at loop start * #44 Only create phi in loop body if var binding in head != body. During finish() lookup in body directly. * #44 Update the print output to make it similar to that in Xmilia's fork * #44 Disable peephole for phis & region involved in while loop * Fix broken tests Remove "disablePeephole" set in some tests, and remaining set for other tests, so a bulk test-all fails because disablePeephole is true for all. Reset disablePeephole in Node.reset Switch HashSet for BitSet (touches all). * Restructure Node class Group printing, group node & edge manipulations, group optimizations. Also, fix LoopRegion idom, it does not use Region idom but uses the original * #44 Node printing * #44 Node printing * #44 Fix control edges in loop region Change label of loop region Fix the output count in dump * #44 Revise dump output * #44 When a LoopRegionNode is duplicated, ensure the dupe is also a LoopRegionNode * #44 When a LoopScopeNode is merged, we merge the names set too * #44 When a LoopScopeNode is merged, we merge the names set too * #44 Fix print1() on RegionNode to use label() * #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created * Revert "#44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created" This reverts commit 5f729709855046c5c10904f08385fd1aec9a298a. * #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created * #44 when we create a phi incrementally for a loop region, all scopes that are cloned from the original must get the same phi update * #44 test case * #44 test case * Squashed commit of the following: commit 15666e287e6bbc39b3fcc49939165a1e908d43b2 Author: Cliff Click <cliffc@acm.org> Date: Mon Nov 27 09:45:40 2023 -0800 lazy/eager phis Eager phis by default, but can flip Parser.LAZY to switch to lazy phis. Several tests golden answers change when flipping this flag due to minor node renumbering. Phi combines same_inputs and singleUniqueInput. Fancier basic-block-like printing. Uses isMultiHead & isMultiTail which show up in many Nodes. Remove blanks in triple-quote strings. commit 6ea70182a92b7db4fe5a1fdc2c4491842ef77ee5 Author: Cliff Click <cliffc@acm.org> Date: Sun Nov 26 11:13:22 2023 -0800 Remove dead scopes Add a debug find commit a52c06a47bf1e56866d8b4d043290838f053ad76 Author: Cliff Click <cliffc@acm.org> Date: Sun Nov 26 10:21:48 2023 -0800 No constraints on backedges nicer loopy graphs commit b5ab550098355f0b66bf24b40adf2e5ba4d86e4e Author: Cliff Click <cliffc@acm.org> Date: Sun Nov 26 10:13:22 2023 -0800 Fix regression commit 30a7f5c734c686c02d3ca479914c9427b65cc469 Author: Cliff Click <cliffc@acm.org> Date: Sat Nov 25 21:51:47 2023 -0800 minor cleanup commit ad742b795ce0c93cfc82b2b11740261cfd923d02 Author: Cliff Click <cliffc@acm.org> Date: Sat Nov 25 21:47:05 2023 -0800 Fixes lazy phi Scope now takes a 'loop' option on dupping; the dup'ed Scope is filled with "Lazy Phi" sentinels - markers to indicate a Phi is need if this variable is ever referenced. If its never referenced, at the loop exit the "Lazy Phi" unwinds back to the original value. Lookup and update calls lazily insert concrete Phis over "Lazy Phis" at first touch. Rename _allScopes to _xScopes its "active" not "all" scopes now. Remove try/finally block at end, because a compiler bug throws, then attempts a GraphViz on a broken graph, then throws again, hiding the original bug. Removed 1 extra layer of Scopes. Scope printing now prints in edge order; added a reversemap for printing. More touches to ascii printing. * Remove flag to parseBlock * Bugfix for lazy on empty loop body Remove extra phi name-matching code * Keep head alive until entire end_loop merging is done * Create chapter 8 as a copy of chapter 7 * #44 Chapter 7 is now eager phis only (#46) * #44 Chapter 7 is now eager phis only * MOVE IR Printing to dedicated class to declutter Node. Remove Ary (#49) * #44 Move IR printing to dedicated class to declutter Node, and remove Ary * #44 refactor Node.delUse() to use common del() * #44 Some cleanups * #44 Some cleanups * #44 Some cleanups * #44 Some cleanups * Revert "#44 Some cleanups" This reverts commit 2702c338c8bdaa5ef2128000e26f1a8496baf34a. * #44 Some cleanups * #44 Some cleanups * #44 Some cleanups * #44 Fix typo * #44 Fix markdown formatting * #44 Remove line numbers from code snippets --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Chapter6 Part 2 - Add further peephole based on dominator calc (#42)Dibyendu Majumdar2023-11-1816-56/+367
| | | | | | | | | | | | | | | | | | | | | | * #37 Add a Utils class to hold some useful functions. (#39) Move the name '$ctrl' to the ScopeNode * Fix maven pom Missing an explicit compiler target, so IntelliJ/Maven defaulted to version 5 ??? Remove explict ver 17 from Makefile. * Add immediate dominator peephole * A little more robust & simpler idom search * #40 Revise chapter 6 writeup to include a description of dominators * #40 Revise chapter 6 writeup to include a description of dominators --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Chapter 6 (#38)Dibyendu Majumdar2023-11-11116-527/+5623
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #37 Create chapter 6 skeleton * #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too. We have a _type field that is like an enum. * #37 Revise Type.meet() - this is now final. Subclasses can override xmeet() which is protected but now handles simple types in Type itself. * #37 Basic test for peephole of CFG * #37 Revise compute of if * #37 Revise compute of if * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP fix the chars inserted by IntelliJ * #37 WIP Fix compute type in IfNode * #37 WIP Null check region inputs * #37 WIP Fix where we choose great grand parent instead of grand parent Add new test * #37 WIP More fixes and tests * #37 WIP Some minor adjustments * Cleanup folding dead IF tests Remove isDeadCtrl & just test for the constant. Remove DEAD_CTRL, doesn't properly reset between tests. Move keep/unkeep to Node. PhiNode has a proper compute() call. ProjNode ideal is a lot simpler. Region doesn't ever get a null. Move the mergeScopes Region peep till after all Phis are added. Type TOP and XCONTROL count as constants. TypeTuple gets a toString * #37 WIP Upate README * #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed * #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed * #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes * Region removes dead input paths Remove region-folding in Return, If. Add a Makefile. Reformat triple-quote lines to be emacs-friendly. * StopNode idealize Return type sharpens to include control input. * Remove !=, >=, >; use Not and <, <=, == Fix bug mixing rotating different ops. Generalize Add fold constants; apply to Mul, EQ. Fix Div.copy * Fix bug rotating e.g. < or <= Peep is only valid for associative ops * #37 WIP Doc updates * Work over the Ch6 Readme Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis. When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input. * Update chapter06/README.md Co-authored-by: Yichen Yan <oraluben@outlook.com> * Update chapter06/README.md Co-authored-by: Yichen Yan <oraluben@outlook.com> * #37 Backport type system changes to chapter 2 * #37 Backport type system changes to chapter 3 * #37 Backport type system changes to chapter 4 * #37 Backport type system changes to chapter 5 * #37 Merge chapter 5 updates from main. Remove language grammar module as we describe the grammar incrementally in each chapter. * #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole * #37 Sync some updates to chapter 2 * #37 Sync some updates to chapter 3 * #37 Sync some updates to chapter 4 --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: Yichen Yan <oraluben@outlook.com>
* Link to parseIf. (#36)Dibyendu Majumdar2023-11-051-138/+18
| | | | | | | * Link to parseIf. Reorder the table of nodes. Fix example. * Replace code with links
* Backport changes in Chapter 5 to previous chapters and update Chapter5 ↵Dibyendu Majumdar2023-11-0395-1483/+3772
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | documentation (#34) * Backport changes from chapter 5 to older chapters (#30) * Fix wrong indent * Backport to chapter 4 * Backport to chapter 3 * Backport to chapter 2 * Backport to chapter 1 * Add if statement to comment (#32) * Update visuals for chapters 1,2 & 3. Reenable drawing of edges from constants to Start for these chapters. * Update visuals for chapters 4. Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4. * Add code snippets for if statement parsing and the duplication and merging of ScopeNodes. Explain how scopeNodes are duplicated and merged. * Add constant check to minus node (#31) * Fix closing root block with } (#33) * Backport fix closing root block with } to chapter 4 and 3 (#35) * Show use-def edge from Phi to Region as dotted edge. Add example of Phi peephole. Update visuals. Add more examples. * Fix visuals in chapter 1 and README in chapter 4. * Remove subheading * Adjust spaces --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
* Cleanup PR#28.Cliff Click2023-11-012-15/+14
| | | | Remove parseBlock flag, and just require the missing `}`
* Bail out unclosed block (#25)Yichen Yan2023-11-016-15/+63
| | | | | | | | | * Report unclosed block in parsing * Fix tests * Resolve comments and rebase onto chapter5 * Test `isEOF` after consume whitespaces
* Update JDK to 21 (#26)Yichen Yan2023-11-013-11/+7
| | | | | | | | | | | | | * Backport fix for set_def killing new_def (#21) * Use JDK 21 * Remove duplicate field in pom * Enable GA test for pull requests --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
* Test expecting an excpetion is missing an fail (#29)XmiliaH2023-11-011-0/+1
|
* Update visualdibyendumajumdar2023-11-016-196/+225
|
* Revert "Report unclosed block in parsing (#28)"dibyendumajumdar2023-11-012-13/+1
| | | | This reverts commit e3c412bbbdd6f6eefe2ac889f6d59aeaef71beb1.
* Report unclosed block in parsing (#28)XmiliaH2023-11-012-1/+13
|
* Fix list of keywords and node index of merge (#27)XmiliaH2023-11-013-3/+3
| | | | | | | * Wrong input index used * Then is currently not a keyword * Some phis are now not created and ids shifted
* Try another graphicsCliff Click2023-11-011-13/+35
|
* Bugfix RegionCliff Click2023-11-011-1/+1
| | | | Region edges need to align with Phi edges; missing leading null
* Small doc cleanup (#24)XmiliaH2023-11-011-59/+54
|
* Add copy method to bool nodes (#23)XmiliaH2023-11-012-6/+13
|
* Update visualdibyendumajumdar2023-11-011-0/+200
|
* Update visualdibyendumajumdar2023-11-012-0/+72
|
* Update visualdibyendumajumdar2023-11-013-119/+149
|
* Update the description of Region nodedibyendumajumdar2023-11-016-409/+395
| | | | | Update visuals Update chapter list
* Remove most TODO'sCliff Click2023-11-016-6/+9
| | | | Make an official TODO which can't be hit in the current Chapter, but future binary ops might hit it.
* Some improvements for chapter5 (#22)XmiliaH2023-11-015-13/+22
| | | | | | | | | | | * Return null when the node cannot be copied * Make add_def package private again * Phi node can have more then two data inputs in theory * Use swap12 * Use addUse
* Cleanup doc example graphCliff Click2023-11-011-2/+1
|
* Lots of improvements to graphvizCliff Click2023-11-0114-60/+79
| | | | | | | | Merging common edges. Phis of same Region align. Phis use greek phi, and have a debug name. Scope carries the debug name. Phis are lightly colored. Common math names for math prims. Parse can optionally show the graph after closing the last scope.
* Bug fix last peepholeCliff Click2023-11-013-8/+10
|
* Rethink & cleanup Add peepsCliff Click2023-11-014-30/+135
| | | | More rigorously head for a left-spline sum-of-products format.
* Fix div-by-0, some javadocCliff Click2023-11-0110-27/+36
| | | | | higher level parsers can return null, but their return is ignored anycase. div-by-0 is defined to be 0, backported to ch2,3,4,5
* javadoc about null-ness returns updateCliff Click2023-11-011-2/+29
|
* Fix missing trailing expressionCliff Click2023-11-012-1/+11
|
* Fix broken error reportCliff Click2023-11-012-2/+11
|
* Fix bugs using keywords as idsCliff Click2023-11-013-19/+71
| | | | | | | | Add an exact 'matchx' for keywords. Add a list of keywords. int true=0; return true; // Expected id, found 'true' int else=arg; if(else) else=2; else else=1; return else; // Expected id, found 'else' inta=1; return a; // undefined inta
* Update READMECliff Click2023-11-013-30/+63
| | | | Add true/false
* Parser gather Returns in the StopCliff Click2023-11-019-55/+78
| | | | | | Return returns a tuple of control & result GraphViz works with multi-Scopes and Scopes do not double-print uid. Proj also does not print uid in golden test results, because every time we add a new early node, the final results change node id so fail golden test.
* Fix Scope.dup mixing up edge ordersCliff Click2023-11-014-44/+35
| | | | Fix GraphVix node edge ordering
* Dont make redundant phisCliff Click2023-11-011-1/+2
|
* Greatly simplify Merge logic; move to ScopeNode.Cliff Click2023-11-016-144/+171
| | | | | | | | | Rename CTRL_TOKEN... its not a token. _allScopes becomes a Stack, because... it behaves like a stack. Add a junk Phi peep. More general AddNode peeps Add a bunch of If tests. Rewrite how expected-exception tests work; the workflow on the old technique sucked. New one stops in the right place in the debugger.
* Emacs per-project settingCliff Click2023-11-011-0/+4
|
* Remove id as we already have it in Node.dibyendumajumdar2023-11-011-12/+1
|
* Small cleanupdibyendumajumdar2023-11-011-7/+5
|
* Add descriptions of the new node types in Chapter 5.dibyendumajumdar2023-11-012-2/+35
| | | | Add references to Cliff's thesis.
* Update the main READMEdibyendumajumdar2023-11-011-2/+2
|
* Small updatesdibyendumajumdar2023-11-011-6/+6
|
* Fix typodibyendumajumdar2023-11-011-1/+1
|
* Add writeup of if statement parsingdibyendumajumdar2023-11-016-3/+644
|
* Add writeup of if statement parsingdibyendumajumdar2023-11-011-0/+24
|
* Update visualization to show all the Scope Nodes that are active.dibyendumajumdar2023-11-014-52/+104
| | | | | | Fix test cases broken due to renaming of ProjNode label. Cleanup the way we update $ctrl token Assign an ID to each ScopeNode so that when we visualize we can assign different names
* Some initial Ch 5 cleanupCliff Click2023-11-0114-37/+42
| | | | | | Drop Control interface, not flexible enough. Use isCFG() call, overloaded in child classes. Projections have a more complex test. Missing some printouts in Bool children, If, Region, Phi. IfNode type is a tuple. Region is TypeControl.
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-16 21:37:19 +0000