From 0dcd3513a633479ce228f24826db4f09e4c0fc8b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 16 Nov 2026 14:25:14 -0800 Subject: Phi fix Fix Phi/Add refactoring peephole to canonicalize regardless of peephole order. Treat class fcns as having `self` be the class pointer --- chapter05/README.md | 15 +++ .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 34 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 37 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 23 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 36 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 36 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 36 +++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 3 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- chapter28a/README.md | 46 +++++++++ .../main/java/com/seaofnodes/simple/Parser.java | 101 ++++++++++---------- .../java/com/seaofnodes/simple/node/CallNode.java | 11 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 93 +++++++++++++++++++ chapter28b/README.md | 9 +- .../main/java/com/seaofnodes/simple/Parser.java | 101 ++++++++++---------- .../java/com/seaofnodes/simple/node/CallNode.java | 11 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 11 ++- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 94 +++++++++++++++++++ chapter29/README.md | 3 + chapter29/docs/29-grammar.md | 9 +- .../java/com/seaofnodes/simple/node/CallNode.java | 11 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 11 ++- .../com/seaofnodes/simple/parser/Expressions.java | 3 + .../com/seaofnodes/simple/parser/Functions.java | 16 +++- .../com/seaofnodes/simple/parser/References.java | 60 +++++------- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 94 +++++++++++++++++++ chapter30/README.md | 3 + chapter30/docs/30-grammar.md | 9 +- .../java/com/seaofnodes/simple/node/CallNode.java | 11 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 11 ++- .../com/seaofnodes/simple/parser/Expressions.java | 3 + .../com/seaofnodes/simple/parser/Functions.java | 16 +++- .../com/seaofnodes/simple/parser/References.java | 60 +++++------- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 94 +++++++++++++++++++ chapter31/Makefile | 4 +- chapter31/README.md | 3 + chapter31/docs/31-grammar.md | 9 +- .../java/com/seaofnodes/simple/node/CallNode.java | 11 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 38 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 11 ++- .../com/seaofnodes/simple/parser/Expressions.java | 3 + .../com/seaofnodes/simple/parser/Functions.java | 14 ++- .../com/seaofnodes/simple/parser/References.java | 55 ++++------- .../java/com/seaofnodes/simple/Chapter05Test.java | 24 +++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 2 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 93 +++++++++++++++++++ chapter32/README.md | 103 +++++++++++++++++++++ chapter32/docs/32-grammar.md | 10 +- .../java/com/seaofnodes/simple/node/CallNode.java | 15 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 39 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 3 +- .../com/seaofnodes/simple/node/SummaryNode.java | 11 ++- .../com/seaofnodes/simple/parser/Expressions.java | 3 + .../com/seaofnodes/simple/parser/Functions.java | 14 ++- .../com/seaofnodes/simple/parser/References.java | 55 ++++------- .../java/com/seaofnodes/simple/Chapter05Test.java | 35 +++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 6 +- .../seaofnodes/simple/GlobalAssignmentTest.java | 71 ++++++++++++++ .../java/com/seaofnodes/simple/ReceiverTest.java | 93 +++++++++++++++++++ .../seaofnodes/simple/SeparateCompilationTest.java | 2 +- skills/chapter25-codex-notes.md | 14 +++ 153 files changed, 3256 insertions(+), 638 deletions(-) create mode 100644 chapter28a/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter28a/src/test/java/com/seaofnodes/simple/ReceiverTest.java create mode 100644 chapter28b/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter28b/src/test/java/com/seaofnodes/simple/ReceiverTest.java create mode 100644 chapter29/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter29/src/test/java/com/seaofnodes/simple/ReceiverTest.java create mode 100644 chapter30/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter30/src/test/java/com/seaofnodes/simple/ReceiverTest.java create mode 100644 chapter31/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter31/src/test/java/com/seaofnodes/simple/ReceiverTest.java create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/ReceiverTest.java diff --git a/chapter05/README.md b/chapter05/README.md index 40886af2..0955f36a 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -413,6 +413,21 @@ return a; +### Factoring after strength reduction + +Peephole order should not hide the same arithmetic from Phi factoring. +`Phi(x+x,y+x)` can become `Phi(x,y)+x`, but an earlier peephole may already have +replaced `x+x` with `x*2`. The Phi matcher therefore views `x*2` as two copies of +`x` while factoring mixed Add/Mul arms. It does not expand the graph into an Add +that would immediately fold back to a multiply. If all arms are multiplies, +ordinary multiply factoring still applies. + +[Chapter05Test](src/test/java/com/seaofnodes/simple/Chapter05Test.java) +checks the factored operands before and after strength reduction and with either +arm order. Later chapters extend this same view to `x<<1` when shifts arrive. +The rule stays local to doubling; arbitrary coefficients would require creating +another multiplication, with a less clear benefit. + [^1]: Click, C. (1995). Combining Analyses, Combining Optimizations, 132. diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index da3917c7..0db72880 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; public class PhiNode extends Node { @@ -40,14 +41,14 @@ public class PhiNode extends Node { // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node op = factoringOp(); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op(op) ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region for( int i=1; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6acb5535..ff7d5cf7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; public class PhiNode extends Node { @@ -41,14 +42,14 @@ public class PhiNode extends Node { // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node op = factoringOp(); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op(op) ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region for( int i=1; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 64cd3dd7..2f94e486 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; public class PhiNode extends Node { @@ -49,14 +50,14 @@ public class PhiNode extends Node { // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node op = factoringOp(); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op(op) ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region for( int i=1; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 14622140..5f8b0251 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; public class PhiNode extends Node { @@ -49,14 +50,14 @@ public class PhiNode extends Node { // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node op = factoringOp(); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op(op) ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region for( int i=1; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java index fe6231fa..1612b860 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; public class PhiNode extends Node { @@ -55,14 +56,14 @@ public class PhiNode extends Node { // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node op = factoringOp(); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op(op) ) { Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region for( int i=1; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 24a72aa4..fafedcef 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -63,7 +64,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -92,15 +94,34 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6995cc2f..952faf68 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -67,7 +68,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -96,8 +98,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6995cc2f..952faf68 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -67,7 +68,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -96,8 +98,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new ProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8dfa04cf..29de3536 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 309cd8b5..2a481c52 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ea5eeb89..815847fe 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8479b4dc..17fe6cef 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 942748e7..836722d8 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 942748e7..836722d8 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; @@ -66,7 +67,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -95,8 +97,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + new Parser(""); + Node ctrl = init(new CProjNode(Parser.START,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 9b5e1c26..012b6498 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -72,7 +72,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -103,8 +104,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x*2 and x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen("return 0;").parse(); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(new Node[]{null,ctrl,ctrl})); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new MulNode(p,init(new ConstantNode(TypeInteger.constant(2))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java index d6ced4e0..8b8f8156 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -40,7 +40,7 @@ else { return x; """); code.parse().iter(); - assertEquals("return Phi(Region,(arg*2),(Mul+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg*2)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6fb315b4..e8a37a4d 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -74,7 +74,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -105,8 +106,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 5672d566..a5620e13 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -40,7 +40,7 @@ else { return x; """); code.parse().iter(); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java index a752977b..e858a21c 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -78,7 +78,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -109,8 +110,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 0a3049e6..be8e125a 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.parse().iter(); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java index e075ea5c..45d5f1ae 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -78,7 +78,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -109,10 +110,28 @@ public class PhiNode extends Node { return null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 0a3049e6..be8e125a 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.parse().iter(); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index b19d1bb5..bba96016 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -380,7 +380,8 @@ public class Chapter21Test { // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, false); + // Phi factoring changes split placement in this chapter's allocator. + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 164, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8aa123f7..7438f417 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -78,7 +78,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -109,10 +110,28 @@ public class PhiNode extends Node { return null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter09Test.java index df590448..85529d63 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.parse().iter().finalizeIR(); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java index af5d900b..424f9d20 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -106,7 +106,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -137,10 +138,28 @@ public class PhiNode extends Node { return null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 3a4415d9..b60e2462 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.parse().iter().finalizeIR(); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter24a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24a/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 953e009e..f63efa24 100644 --- a/chapter24a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24a/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -129,7 +129,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -161,10 +162,28 @@ public class PhiNode extends Node { return null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter24a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter24a/src/test/java/com/seaofnodes/simple/Chapter09Test.java index f24d96eb..bfa4d776 100644 --- a/chapter24a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter24a/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 7f2bb1f4..70bb5877 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -130,7 +130,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -162,10 +163,28 @@ public class PhiNode extends Node { return null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter24b/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter24b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index f24d96eb..bfa4d776 100644 --- a/chapter24b/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter24b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 064852e4..9f800e2f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -107,7 +107,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; if( nIns()==3 ) { Node merge = matchingGuardMerge(r,1); @@ -165,10 +166,28 @@ public class PhiNode extends Node { return tested!=null && ScopeNode.availableAt(n,r,new java.util.BitSet()) ? n : null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p,(byte)1)); + Node sum = init(new AddNode(i,p,(byte)1)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 50410618..6e167d9e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter26/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter26/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 064852e4..9f800e2f 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -107,7 +107,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; if( nIns()==3 ) { Node merge = matchingGuardMerge(r,1); @@ -165,10 +166,28 @@ public class PhiNode extends Node { return tested!=null && ScopeNode.availableAt(n,r,new java.util.BitSet()) ? n : null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p,(byte)1)); + Node sum = init(new AddNode(i,p,(byte)1)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter26/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter26/src/test/java/com/seaofnodes/simple/Chapter09Test.java index f24d96eb..bfa4d776 100644 --- a/chapter26/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter26/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 064852e4..9f800e2f 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -107,7 +107,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; if( nIns()==3 ) { Node merge = matchingGuardMerge(r,1); @@ -165,10 +166,28 @@ public class PhiNode extends Node { return tested!=null && ScopeNode.availableAt(n,r,new java.util.BitSet()) ? n : null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p,(byte)1)); + Node sum = init(new AddNode(i,p,(byte)1)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter27/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter27/src/test/java/com/seaofnodes/simple/Chapter09Test.java index f24d96eb..bfa4d776 100644 --- a/chapter27/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter27/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } diff --git a/chapter28a/README.md b/chapter28a/README.md index 2f127e19..d61d642c 100644 --- a/chapter28a/README.md +++ b/chapter28a/README.md @@ -23,6 +23,52 @@ This chapter adds file and class semantics to the escape analysis we already have. All required Simple source is available in one compilation. +## Globals use the same receiver as fields + +Every function has a source-visible `self`. An instance method receives its +instance; a global function receives its defining file's class singleton. +For example: + +```simple +int f0=7; +int f1=0; +val touch={int n -> f1=n; return f0+f1;}; +``` + +The function body means `self.f1=n; return self.f0+self.f1;`. Once the class is +initialized, `touch(5)` returns 12. Bare reads, assignments, and compound updates +all resolve the field's receiver and use the same field-access path. A bare +assignment must emit a Store, rather than updating only a lexical Scope slot. +Locals and explicit parameters still shadow fields; an explicitly declared +parameter named `self` shadows the implicit receiver. + +The [parser](src/main/java/com/seaofnodes/simple/Parser.java) supplies a receiver +parameter instead of manufacturing a class constant for each global read. +Normal constant folding removes that parameter for class functions. Its function +signature retains `TypePtr.PTR`, the marker for a hidden receiver with no native +argument slot, so ordinary C callers and callbacks retain their ABI. +[CallNode](src/main/java/com/seaofnodes/simple/node/CallNode.java) binds that slot +to the callee's declared class view even when another class forwards the callback +or an instance stores its function pointer. An instance method can also name its +enclosing class's fields through that declaration's receiver. This does not add +closures or bound method values. + +The class view keeps fields discovered so far and remains open until SCCP +installs the completed shape. This matters for forward functions and for globals +declared after a struct. Class declarations still accumulate Scope values until +initializer exit; this chapter also retains its existing Scope-based instance +constructor handling. Active field uses retain their class-initialization checks. +Passing the hidden class receiver does not itself publish the caller's class to +unknown code; actual escaping fields are tracked normally. + +[GlobalAssignmentTest](src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java) +checks assignments, branches, chained updates, RHS effects, local shadowing, +conversions, constructors, and rejected stores. +[ReceiverTest](src/test/java/com/seaofnodes/simple/ReceiverTest.java) checks explicit +class `self`, nested functions, instance/global name collisions, forward fields, +and native argument/callback ABI behavior. Chapter 28b extends this to imported +functions and summaries. + ## Example: Lazy class initialization, or Pay-As-You-Go Suppose an application sometimes needs a `Table` but not often; many runs may diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java b/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java index 3b5a8ce7..fd9d9753 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java @@ -290,8 +290,16 @@ public class Parser { // All args, "as-if" called externally for( int i=0; i