From 1a9cac97df063af82516ca35bde34fde62d24c56 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: Chapter 6 (#38) * #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 * Update chapter06/README.md Co-authored-by: Yichen Yan * #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 Co-authored-by: Yichen Yan --- chapter06/docs/06-graph3-nonconst.svg | 290 ++++++++++++++++++++++++++++++++++ 1 file changed, 290 insertions(+) create mode 100644 chapter06/docs/06-graph3-nonconst.svg (limited to 'chapter06/docs/06-graph3-nonconst.svg') diff --git a/chapter06/docs/06-graph3-nonconst.svg b/chapter06/docs/06-graph3-nonconst.svg new file mode 100644 index 00000000..dee852e4 --- /dev/null +++ b/chapter06/docs/06-graph3-nonconst.svg @@ -0,0 +1,290 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return25 + +Return + + + +Stop3->Return25 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +If8 + + +If + + + +True + + +False + + + +If8->Start2:p0 + + +0 + + + +If8->Start2:p1 + + +1 + + + +Con_12 + +#2 + + + +If13 + + +If + + + +True + + +False + + + +If13->Start2:p1 + + +1 + + + +If13->If8:p0 + + +0 + + + +Con_17 + +#2 + + + +Con_18 + +#3 + + + +Region19 + +Region + + + +Region19->If13:p0 + + +1 + + + +Region19->If13:p1 + + +2 + + + +Phi_b20 + +φ_b + + + +Phi_b20->Con_17 + + +1 + + + +Phi_b20->Con_18 + + +2 + + + +Phi_b20->Region19 + + +0 + + + +Region21 + +Region + + + +Region21->If8:p1 + + +2 + + + +Region21->Region19 + + +1 + + + +Phi_a22 + +φ_a + + + +Phi_a22->Con_6 + + +2 + + + +Phi_a22->Con_12 + + +1 + + + +Phi_a22->Region21 + + +0 + + + +Phi_b23 + +φ_b + + + +Phi_b23->Con_7 + + +2 + + + +Phi_b23->Phi_b20 + + +1 + + + +Phi_b23->Region21 + + +0 + + + +Add24 + ++ + + + +Add24->Phi_a22 + + +2 + + + +Add24->Phi_b23 + + +1 + + + +Return25->Region21 + + +0 + + + +Return25->Add24 + + +1 + + + -- cgit v1.2.3