diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-16 14:25:14 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-16 14:25:14 -0800 |
| commit | 0dcd3513a633479ce228f24826db4f09e4c0fc8b (patch) | |
| tree | d8fb6d0fb382df5799789e9dc1eb0fae2d381cce /chapter05 | |
| parent | 51a029304d8105b201bdfb81a7692b8a1b16b028 (diff) | |
| download | Simple-0dcd3513a633479ce228f24826db4f09e4c0fc8b.tar.gz Simple-0dcd3513a633479ce228f24826db4f09e4c0fc8b.zip | |
Phi fix
Fix Phi/Add refactoring peephole to canonicalize regardless of peephole order.
Treat class fcns as having `self` be the class pointer
Diffstat (limited to 'chapter05')
| -rw-r--r-- | chapter05/README.md | 15 | ||||
| -rw-r--r-- | chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java | 34 | ||||
| -rw-r--r-- | chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java | 23 |
3 files changed, 65 insertions, 7 deletions
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<nIns(); i++ ) { - lhss[i] = in(i).in(1); - rhss[i] = in(i).in(2); + lhss[i] = factoringInput(op,in(i),1); + rhss[i] = factoringInput(op,in(i),2); } Node phi_lhs = new PhiNode(_label,lhss).peephole(); Node phi_rhs = new PhiNode(_label,rhss).peephole(); @@ -57,9 +58,28 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { - for( int i=2; i<nIns(); i++ ) - if( in(1).getClass() != in(i).getClass() ) + // 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<nIns(); i++ ) + if( in(i) instanceof AddNode ) return in(i); + return op; + } + + private boolean doubled(Node n) { + return n instanceof MulNode && + n.in(2)._type instanceof TypeInteger con && con.isConstant() && con.value()==2; + } + + private static Node factoringInput(Node op, Node n, int j) { + return op instanceof AddNode && !(n instanceof AddNode) ? n.in(1) : n.in(j); + } + + private boolean same_op(Node op) { + for( int i=1; i<nIns(); i++ ) + if( op.getClass()!=in(i).getClass() && !(op instanceof AddNode && doubled(in(i))) ) return false; return true; } diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index d6c91a4a..282215f1 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -222,4 +222,27 @@ return a; } } + private static <N extends Node> 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(); + } + } } |
