From a36369843133a170718006600890d12ceb66a553 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Fri, 14 Mar 2025 16:48:07 -0700
Subject: Buncha encoding related fixes.

RA cloning `CmpIxxx` stretches the input live range, new for cloning... and was making broken graph.
Several cloning related bugs in RISC & ARM.
Invariant around RA cloning vs InstSelect is too complex
---
 .../com/seaofnodes/simple/codegen/RegAlloc.java    | 16 +++++-----
 .../seaofnodes/simple/node/cpus/arm/AndARM.java    |  2 ++
 .../seaofnodes/simple/node/cpus/arm/CmpIARM.java   |  9 ++++++
 .../com/seaofnodes/simple/node/cpus/arm/OrARM.java |  3 +-
 .../seaofnodes/simple/node/cpus/arm/XorARM.java    |  1 +
 .../seaofnodes/simple/node/cpus/riscv/AUIPC.java   |  4 ++-
 .../seaofnodes/simple/node/cpus/riscv/ImmRISC.java |  5 ++--
 .../seaofnodes/simple/node/cpus/riscv/IntRISC.java |  3 +-
 .../simple/node/cpus/riscv/SrlIRISC.java           |  2 +-
 .../seaofnodes/simple/node/cpus/riscv/riscv.java   | 18 ++++++++----
 .../simple/node/cpus/x86_64_v2/CmpIX86.java        | 34 ++++++++++++++++++----
 .../simple/node/cpus/x86_64_v2/JmpX86.java         |  3 +-
 .../com/seaofnodes/simple/print/ASMPrinter.java    |  2 +-
 13 files changed, 72 insertions(+), 30 deletions(-)

(limited to 'chapter21/src/main/java')

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 badec740..68b9cdcc 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -281,6 +281,14 @@ public class RegAlloc {
         // For all conflicts
         for( Node def : conflicts ) {
             assert lrg(def)==lrg; // Might be conflict use-side
+            // Split before each use that extends the live range; i.e. is a
+            // Phi or two-address
+            for( int i=0; i<def._outputs._len; i++ ) {
+                Node use = def.out(i);
+                if( (use instanceof PhiNode phi && !(phi.region() instanceof LoopNode && phi.in(2)==def ) ) ||
+                        (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
+                    insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
+            }
             // Split after the Phi which extends the LRG.  Split also before
             // Phi slot 1 (and not all inputs), because Phis extend the live range.
             // TODO: split before all inputs (except the last; at least 1 split here must be extra)
@@ -294,14 +302,6 @@ public class RegAlloc {
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
                 insertBefore(def,mach.twoAddress(),"use/self/two",round,lrg);
-            // Split before each use that extends the live range; i.e. is a
-            // Phi or two-address
-            for( int i=0; i<def._outputs._len; i++ ) {
-                Node use = def.out(i);
-                if( (use instanceof PhiNode phi && !(phi.region() instanceof LoopNode && phi.in(2)==def ) ) ||
-                        (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
-                    insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
-            }
         }
         return true;
     }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
index 7c9cc3d7..8e95628c 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
@@ -8,6 +8,8 @@ import com.seaofnodes.simple.node.Node;
 
 public class AndARM extends MachConcreteNode implements MachNode {
     AndARM(Node and) { super(and); }
+    @Override public String op() { return "and"; }
+    @Override public String glabel() { return "&"; }
     @Override public RegMask regmap(int i) { return arm.RMASK; }
     @Override public RegMask outregmap() { return arm.RMASK; }
     @Override public void encoding( Encoding enc ) { arm.r_reg(enc,this,138); }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpIARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpIARM.java
index b00ddfbe..be80fb03 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpIARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpIARM.java
@@ -15,9 +15,18 @@ public class CmpIARM extends MachConcreteNode implements MachNode {
         _bop = bool.op();
         _imm = imm;
     }
+    CmpIARM( CmpIARM cmp ) {
+        super((Node)null);
+        addDef(null);
+        addDef(cmp.in(1));
+        _bop = cmp._bop;
+        _imm = cmp._imm;
+    }
     @Override public String op() { return _imm==0 ? "test" : "cmp"; }
     @Override public RegMask regmap(int i) { return arm.RMASK; }
     @Override public RegMask outregmap() { return arm.FLAGS_MASK; }
+    @Override public boolean isClone() { return true; }
+    @Override public Node copy() { return new CmpIARM(this); }
     // Encoding is appended into the byte array; size is returned
     @Override public void encoding( Encoding enc ) { arm.imm_inst(enc,this,964,_imm); }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrARM.java
index 61626855..19631f35 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrARM.java
@@ -7,7 +7,8 @@ import com.seaofnodes.simple.node.*;
 // Not using the ORRS variant.
 public class OrARM extends MachConcreteNode implements MachNode {
     OrARM(Node and) { super(and); }
-    @Override public String op() { return "orr"; }
+    @Override public String op() { return "or"; }
+    @Override public String glabel() { return "|"; }
     @Override public RegMask regmap(int i) { return arm.RMASK; }
     @Override public RegMask outregmap() { return arm.RMASK; }
     @Override public void encoding( Encoding enc ) { arm.r_reg(enc,this,170); }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorARM.java
index ebdfe094..8c4f65f9 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorARM.java
@@ -7,6 +7,7 @@ import com.seaofnodes.simple.node.*;
 public class XorARM extends MachConcreteNode implements MachNode{
     XorARM(Node xor) {super(xor);}
     @Override public String op() { return "xor"; }
+    @Override public String glabel() { return "^"; }
     @Override public RegMask regmap(int i) { return arm.RMASK; }
     @Override public RegMask outregmap() { return arm.RMASK; }
     @Override public void encoding( Encoding enc ) { arm.r_reg(enc,this,202); }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AUIPC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AUIPC.java
index 5bcb6165..ebae13b6 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AUIPC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AUIPC.java
@@ -23,6 +23,8 @@ public class AUIPC extends ConstantNode implements MachNode {
 
     @Override public void asm(CodeGen code, SB sb) {
         String reg = code.reg(this);
-        _con.print(sb.p(reg).p(" = PC+#"));
+        sb.p(reg).p(" = PC+#");
+        if( _con == null ) sb.p("---");
+        else _con.print(sb);
     }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java
index bac9ea6d..825d9449 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java
@@ -8,11 +8,12 @@ import java.util.BitSet;
 
 abstract public class ImmRISC extends MachConcreteNode implements MachNode {
     final int _imm12;
-    ImmRISC( Node add, int imm12 ) {
+    ImmRISC( Node add, int imm12, boolean pop ) {
         super(add);
-        _inputs.pop();
         _imm12 = imm12;
+        if( pop ) _inputs.pop();
     }
+    ImmRISC( Node add, int imm12 ) { this(add,imm12,true); }
     @Override public RegMask regmap(int i) { return riscv.RMASK; }
     @Override public RegMask outregmap() { return riscv.WMASK; }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java
index eb88203c..9d21ae13 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java
@@ -20,8 +20,7 @@ public class IntRISC extends ConstantNode implements MachNode {
         TypeInteger ti = (TypeInteger)_con;
         // Explicit truncation of larger immediates; this will sign-extend on
         // load and this is handled during instruction selection.
-        int body = riscv.i_type(riscv.I_TYPE, dst, 0, riscv.ZERO, (int)(ti.value() & 0xFFF));
-        enc.add4(body);
+        enc.add4(riscv.i_type(riscv.I_TYPE, dst, 0, riscv.ZERO, (int)(ti.value() & 0xFFF)));
     }
     @Override public void asm(CodeGen code, SB sb) {
         String reg = code.reg(this);
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java
index 7a28d598..078a2fca 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java
@@ -4,7 +4,7 @@ import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.Node;
 
 public class SrlIRISC extends ImmRISC {
-    SrlIRISC( Node and, int imm) { super(and,imm); }
+    SrlIRISC( Node and, int imm, boolean pop) { super(and,imm,pop); }
     @Override int opcode() {  return riscv.I_TYPE; }
     @Override int func3() {  return 5; }
     @Override public String glabel() { return ">>>"; }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
index 3367a520..16b09172 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
@@ -368,8 +368,13 @@ public class riscv extends Machine {
     }
 
     private Node and(AndNode and) {
-        if( and.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm12(ti) )
-            return new AndIRISC(and, (int)ti.value());
+        if( and.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) {
+            if( imm12(ti) )
+                return new AndIRISC(and, (int)ti.value());
+            // Could be any size low bit mask
+            if( ti.value() == 0xFFFFFFFFL )
+                return new SrlIRISC(new SllIRISC(and,32),32,false);
+        }
         return new AndRISC(and);
     }
 
@@ -384,7 +389,7 @@ public class riscv extends Machine {
     }
     private Node nnn(NewNode nnn) {
         // TODO: pass in the TFP for alloc
-        return new NewRISC(nnn, new AUIPC((TypeFunPtr)null));
+        return new NewRISC(nnn, new AUIPC(null));
     }
 
     private Node cmp(BoolNode bool) {
@@ -428,8 +433,9 @@ public class riscv extends Machine {
                 // Here, the low 12 bits get sign-extended, which means if
                 // bit11 is set, the value is negative and lowers the LUI
                 // value.  Add a bit 12 to compensate
-                yield new AddIRISC(new LUI(((x>>12)&1)==1 ? TypeInteger.constant(x+0x1000) : ti), (int)(x & 0xFFF));
-            // Need more complex sequence for larger constants
+                yield new AddIRISC(new LUI(((x>>11)&1)==1 ? TypeInteger.constant(x+0x1000) : ti), (int)(x & 0xFFF));
+            // Need more complex sequence for larger constants... or a load
+            // from a constant pool, which does not need an extra register
             throw Utils.TODO();
         }
         case TypeFloat   tf  -> new FltRISC(con);
@@ -471,7 +477,7 @@ public class riscv extends Machine {
 
     private Node srl(ShrNode shr) {
         if( shr.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm12(ti) && imm12(ti))
-            return new SrlIRISC(shr, (int)ti.value());
+            return new SrlIRISC(shr, (int)ti.value(),true);
         return new SrlRISC(shr);
     }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
index 5b992581..0db93118 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
@@ -2,16 +2,38 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2;
 
 import com.seaofnodes.simple.SB;
 import com.seaofnodes.simple.codegen.*;
-import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.*;
 
 // Compare immediate.  Sets flags.
-public class CmpIX86 extends ImmX86 {
-    CmpIX86( Node add, int imm ) { super(add,imm); }
+public class CmpIX86 extends MachConcreteNode implements MachNode {
+    final int _imm;
+    CmpIX86( Node cmp, int imm ) {
+        super(cmp);
+        _inputs.pop();
+        _imm = imm;
+    }
+    CmpIX86( CmpIX86 cmp ) {
+        super((Node)null);
+        addDef(null);
+        addDef(cmp.in(1));
+        _imm = cmp._imm;
+    }
     @Override public String op() { return _imm==0 ? "test" : "cmp"; }
+    @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; }
     @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; }
-    @Override public int twoAddress() { return 0; }
-    @Override int opcode() { return 0x81; }
-    @Override int mod() { return 7; }
+    @Override public boolean isClone() { return true; }
+    @Override public Node copy() { return new CmpIX86(this); }
+    // Encoding is appended into the byte array; size is returned
+    @Override public final void encoding( Encoding enc ) {
+        short dst = enc.reg(this); // Also src1
+        enc.add1(x86_64_v2.rex(0, dst, 0));
+        // opcode; 0x81 or 0x83; 0x69 or 0x6B
+        enc.add1( 0x81 + (x86_64_v2.imm8(_imm) ? 2 : 0) );
+        enc.add1( x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 7, dst) );
+        // immediate(4 bytes) 32 bits or (1 byte)8 bits
+        if( x86_64_v2.imm8(_imm) ) enc.add1(_imm);
+        else                       enc.add4(_imm);
+    }
     @Override public void asm(CodeGen code, SB sb) {
         String dst = code.reg(this);
         if( dst!="flags" )  sb.p(dst).p(" = ");
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
index 2971ae82..1a5a4d0a 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
@@ -39,9 +39,8 @@ public class JmpX86 extends IfNode implements MachNode {
     @Override public void asm(CodeGen code, SB sb) {
         String src = code.reg(in(1));
         if( src!="flags" ) sb.p(src);
-        else sb.p(" ");
         Node prj = cproj(0);
-        sb.p(prj instanceof LoopNode ? "LOOP" : "L").p(prj._nid);
+        sb.p(prj instanceof LoopNode ? " LOOP" : " L").p(prj._nid);
     }
 
     @Override public String comment() { return "L"+cproj(1)._nid; }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
index c97d809d..77d891a2 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
@@ -99,7 +99,7 @@ public abstract class ASMPrinter {
         // to this block.  Until the post-reg-alloc block layout cleanup, we
         // need to assume a jump.  There's no real hardware op here, yet.
         if( n instanceof RegionNode cfg && !(n instanceof FunNode) ) {
-            while( true ) {
+            while( cfgidx < code._cfg._len-1 ) {
                 CFGNode next = code._cfg.at(++cfgidx);
                 if( next == n ) return iadr; // Fall-through, no branch
                 if( next.nOuts()>1 )
-- 
cgit v1.2.3