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 +++++++++++++++ 3 files changed, 65 insertions(+), 7 deletions(-) (limited to 'chapter05') 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(); + } + } } -- cgit v1.2.3