From d98a5c8cdf7a249f3c227fc00f014d53452af858 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 31 Mar 2025 10:15:36 -0700 Subject: Move insertAfterAndReplace to RA Fix Split printing --- .../com/seaofnodes/simple/codegen/RegAlloc.java | 25 +++++++++++++++++++--- .../main/java/com/seaofnodes/simple/node/Node.java | 22 +------------------ .../java/com/seaofnodes/simple/node/SplitNode.java | 5 ++++- 3 files changed, 27 insertions(+), 25 deletions(-) (limited to 'chapter21/src') diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index f595bf74..1fe5591b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -251,7 +251,7 @@ public class RegAlloc { // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - makeSplit("def/empty1",round,lrg).insertAfterAndReplace((Node)lrg._machDef, this, false/*true*/); + insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); // Split just before use if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); @@ -341,7 +341,7 @@ public class RegAlloc { // TODO: split before all inputs (except the last; at least 1 split here must be extra) if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) { SplitNode split = makeSplit("def/self",round,lrg); - split.insertAfterAndReplace(def,this,false); + insertAfterAndReplace(split,def,false); if( split.nOuts()==0 ) split.kill(); insertBefore(phi,1,"use/self/phi",round,lrg); @@ -398,7 +398,7 @@ public class RegAlloc { // Single user is already a split adjacent !(n.nOuts()==1 && n.out(0) instanceof SplitNode split && sameBlockNoClobber(split) ) ) // Split after def in min loop nest - makeSplit("def/loop",round,lrg).insertAfterAndReplace(n,this,true); + insertAfterAndReplace( makeSplit("def/loop",round,lrg), n,true); } // PhiNodes check all CFG inputs @@ -488,6 +488,24 @@ public class RegAlloc { insertBefore(n,i,kind,round,lrg,true); } + // Replace uses of `def` with `split`, and insert `split` immediately after + // `def` in the basic block. + public void insertAfterAndReplace( Node split, Node def, boolean must ) { + split.insertAfter(def); + if( split.nIns()>1 ) split.setDef(1,def); + for( int j=def.nOuts()-1; j>=0; j-- ) { + Node use = def.out(j); + if( use==split ) continue; // Skip self + // Can we avoid a split of a split? 'this' split is used by + // another split in the same block. + if( !must && use instanceof SplitNode split2 && sameBlockNoClobber(split2) ) + continue; + int idx = use._inputs.find(def); + use.setDefOrdered(idx,split); + if( j < def.nOuts() ) j++; + } + } + private Node makeSplit( Node def, String kind, byte round, LRG lrg ) { Node split = def instanceof MachNode mach && mach.isClone() ? mach.copy() @@ -559,6 +577,7 @@ public class RegAlloc { return true; } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java index 28f70fce..44c9d7cf 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java @@ -10,7 +10,6 @@ import com.seaofnodes.simple.type.TypeInteger; import java.util.*; import java.util.function.Function; import static com.seaofnodes.simple.codegen.CodeGen.CODE; -import com.seaofnodes.simple.codegen.RegAlloc; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -304,7 +303,7 @@ public abstract class Node { } // insert `this` immediately after `def` in the same basic block. - public CFGNode insertAfter( Node def ) { + public void insertAfter( Node def ) { CFGNode cfg = def.cfg0(); int i = cfg._outputs.find(def)+1; if( cfg instanceof CallEndNode ) { @@ -317,25 +316,6 @@ public abstract class Node { while( cfg.out(i) instanceof PhiNode || cfg.out(i) instanceof CalleeSaveNode ) i++; cfg._outputs.insert(this,i); _inputs.set(0,cfg); - return cfg; - } - - // Replace uses of `def` with `this`, and insert `this` immediately after - // `def` in the basic block. - public void insertAfterAndReplace( Node def, RegAlloc r, boolean must ) { - CFGNode cfg = insertAfter(def); - for( int j=def.nOuts()-1; j>=0; j-- ) { - // Can we avoid a split of a split? 'this' split is used by - // another split in the same block. - if( !must && def.out(j) instanceof SplitNode split && r.sameBlockNoClobber(split) ) - continue; - Node use = def._outputs.del(j); - use.unlock(); - int idx = use._inputs.find(def); - use._inputs.set(idx,this); - addUse(use); - } - if( nIns()>1 ) setDef(1,def); } // Insert this in front of use.in(uidx) with this, and insert this diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/SplitNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/SplitNode.java index 22cb9bb9..3a1ed011 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/SplitNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/SplitNode.java @@ -11,7 +11,10 @@ public abstract class SplitNode extends MachConcreteNode { public SplitNode(String kind, byte round, Node[] nodes) { super(nodes); _kind = kind; _round = round; } @Override public String op() { return "mov"; } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - return in(1)._print0(sb.append("mov("),visited).append(")"); + sb.append("mov("); + if( in(1) == null ) sb.append("---"); + else in(1)._print0(sb,visited); + return sb.append(")"); } @Override public Type compute() { return in(0)._type; } @Override public Node idealize() { return null; } -- cgit v1.2.3