Encode infinite loops for RISC

7 files changed, 105 insertions, 56 deletions

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java
index 295eab0a..bf3bfdb9 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java
@@ -16,7 +16,7 @@ abstract public class Machine {
     // Return a MachNode unconditional branch
     public abstract CFGNode jump();
     // Break an infinite loop
-    public abstract IfNode never( CFGNode ctrl );
+    public abstract NeverNode never( CFGNode ctrl );
     // Instruction select from ideal nodes
     public abstract Node instSelect( Node n );
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index d2b0e36c..6b4026c5 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -2,9 +2,10 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeMem;
 import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.TypeMem;
 import java.util.BitSet;
 import java.util.HashSet;
 
@@ -45,28 +46,32 @@ public class LoopNode extends RegionNode {
             x = x.idom();
         }
         // Found a no-exit loop.  Insert an exit
-        NeverNode iff = new NeverNode(back());
+        NeverNode iff = CodeGen.CODE._mach == null
+            ? new NeverNode(back()) // Ideal never-branch
+            : CodeGen.CODE._mach.never(back()); // Machine never-branch
         for( Node use : _outputs )
             if( use instanceof PhiNode )
                 iff.addDef(use);
         CProjNode t = new CProjNode(iff,0,"True" ).init();
         CProjNode f = new CProjNode(iff,1,"False").init();
         setDef(2,f);
+        iff._ltree = t._ltree = f._ltree = _ltree;
 
         // Now fold control into the exit.  Might have 1 valid exit, or an
         // XCtrl or a bunch of prior NeverNode exits.
         Node top = new ConstantNode(Type.TOP).peephole();
         ReturnNode ret = fun.ret();
         Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr();
-        if( ctrl._type != Type.XCONTROL ) {
+        if( ctrl!=null && ctrl._type != Type.XCONTROL ) {
             // Perfect aligned exit?
             if( !(ctrl instanceof RegionNode r &&
                   mem  instanceof PhiNode pmem && pmem.region()==r &&
                   expr instanceof PhiNode prez && prez.region()==r ) ) {
                 // Nope, insert an aligned exit layer
-                ctrl = new RegionNode(_loc,null,ctrl).init();
-                mem  = new    PhiNode((RegionNode)ctrl,mem ).init();
-                expr = new    PhiNode((RegionNode)ctrl,expr).init();
+                RegionNode r = new RegionNode(_loc,null,ctrl).init();
+                ctrl = r;  r._ltree = _ltree;
+                mem  = new PhiNode(r,mem ).init();
+                expr = new PhiNode(r,expr).init();
             }
             // Append new Never exit
             ctrl.addDef(t  );
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
index f070a526..6b2b03c3 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
@@ -607,7 +607,7 @@ public class arm extends Machine {
     }
 
     // Break an infinite loop
-    @Override public IfNode never(CFGNode ctrl ) {
+    @Override public NeverNode never(CFGNode ctrl ) {
         throw Utils.TODO();
     }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NJmpRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NJmpRISC.java
new file mode 100644
index 00000000..f0d28a3a
--- /dev/null
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NJmpRISC.java
@@ -0,0 +1,50 @@
+package com.seaofnodes.simple.node.cpus.riscv;
+
+import com.seaofnodes.simple.*;
+import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeFunPtr;
+import java.util.BitSet;
+
+public class NJmpRISC extends NeverNode implements MachNode, RIPRelSize {
+    // label is obtained implicitly
+    public NJmpRISC( CFGNode cfg ) { super(cfg); }
+
+    @Override public String op() { return "jmp"; }
+    @Override public String label() { return op(); }
+    @Override public String comment() { return "L"+cproj(1)._nid; }
+    @Override public StringBuilder _print1( StringBuilder sb, BitSet visited ) { return sb.append("jmp "); }
+    @Override public RegMask regmap(int i) {
+        if( i!=3 ) return null;
+        TypeFunPtr tfp = cproj(0).uctrl().fun().sig();
+        return riscv.retMask(tfp,2);
+    }
+    @Override public RegMask outregmap() { return null; }
+
+    @Override public void encoding( Encoding enc ) {
+        // Short form +/-4K:  beq r0,r0,imm12
+        // Long form:  auipc rX,imm20/32; jal r0,[rX+imm12/32]
+        enc.jump(this,cproj(1));
+        enc.add4(riscv.j_type(riscv.OP_JAL, 0, 0));
+    }
+
+    // Delta is from opcode start
+    @Override public byte encSize(int delta) {
+        if( -(1L<<20) <= delta && delta < (1L<<20) ) return 4;
+        // 2 word encoding needs a tmp register, must teach RA
+        throw Utils.TODO();
+    }
+
+    // Delta is from opcode start
+    @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) {
+        if( opLen==4 ) {
+            enc.patch4(opStart,riscv.j_type(riscv.OP_JAL, 0, delta));
+        } else {
+            throw Utils.TODO();
+        }
+    }
+
+    @Override public void asm(CodeGen code, SB sb) {
+        sb.p(label(cproj(1).uctrl()));
+    }
+}
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/UJmpRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/UJmpRISC.java
index 84224a01..9f623b0c 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/UJmpRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/UJmpRISC.java
@@ -8,12 +8,9 @@ import java.util.BitSet;
 
 // unconditional jump
 public class UJmpRISC extends CFGNode implements MachNode, RIPRelSize {
-    //UJmpRISC() { }
     @Override public String op() { return "jmp"; }
     @Override public String label() { return op(); }
-    @Override public StringBuilder _print1( StringBuilder sb, BitSet visited ) {
-        return sb.append("jmp ");
-    }
+    @Override public StringBuilder _print1( StringBuilder sb, BitSet visited ) { return sb.append("jmp "); }
     @Override public RegMask regmap(int i) {return null; }
     @Override public RegMask outregmap() { return null; }
     @Override public Type compute() { throw Utils.TODO(); }
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 9006c614..ae43ab55 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
@@ -338,9 +338,7 @@ public class riscv extends Machine {
     @Override  public SplitNode split(String kind, byte round, LRG lrg) { return new SplitRISC(kind,round);  }
 
     // Break an infinite loop
-    @Override public IfNode never( CFGNode ctrl ) {
-        throw Utils.TODO();
-    }
+    @Override public NeverNode never( CFGNode ctrl ) { return new NJmpRISC(ctrl);}
 
     // True if signed 12-bit immediate
     public static boolean imm12(TypeInteger ti) {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
index d475a260..39048f2d 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
@@ -381,8 +381,7 @@ public class x86_64_v2 extends Machine {
     }
 
     // Break an infinite loop
-    @Override
-    public IfNode never(CFGNode ctrl) {
+    @Override public NeverNode never(CFGNode ctrl) {
         throw Utils.TODO();
     }
 
@@ -390,45 +389,45 @@ public class x86_64_v2 extends Machine {
     @Override
     public Node instSelect(Node n) {
         return switch (n) {
-            case AddFNode addf -> addf(addf);
-            case AddNode add -> add(add);
-            case AndNode and -> and(and);
-            case BoolNode bool -> cmp(bool);
-            case CallEndNode cend -> new CallEndX86(cend);
-            case CallNode call -> call(call);
-            case CastNode cast -> new CastX86(cast);
-            case CProjNode c -> new CProjNode(c);
-            case ConstantNode con -> con(con);
-            case DivFNode divf -> new DivFX86(divf);
-            case DivNode div -> new DivX86(div);
-            case FunNode fun -> new FunX86(fun);
-            case IfNode iff -> jmp(iff);
-            case LoadNode ld -> ld(ld);
-            case MemMergeNode mem -> new MemMergeNode(mem);
-            case MulFNode mulf -> new MulFX86(mulf);
-            case MulNode mul -> mul(mul);
-            case NewNode nnn -> new NewX86(nnn);
-            case NotNode not -> new NotX86(not);
-            case OrNode or -> or(or);
-            case ParmNode parm -> new ParmX86(parm);
-            case PhiNode phi -> new PhiNode(phi);
-            case ProjNode prj -> prj(prj);
-            case ReadOnlyNode read -> new ReadOnlyNode(read);
-            case ReturnNode ret -> new RetX86(ret, ret.fun());
-            case SarNode sar -> sar(sar);
-            case ShlNode shl -> shl(shl);
-            case ShrNode shr -> shr(shr);
-            case StartNode start -> new StartNode(start);
-            case StopNode stop -> new StopNode(stop);
-            case StoreNode st -> st(st);
-            case SubFNode subf -> new SubFX86(subf);
-            case SubNode sub -> sub(sub);
-            case ToFloatNode tfn -> i2f8(tfn);
-            case XorNode xor -> xor(xor);
-
-            case LoopNode loop -> new LoopNode(loop);
-            case RegionNode region -> new RegionNode(region);
-            default -> throw Utils.TODO();
+        case AddFNode addf -> addf(addf);
+        case AddNode add -> add(add);
+        case AndNode and -> and(and);
+        case BoolNode bool -> cmp(bool);
+        case CallEndNode cend -> new CallEndX86(cend);
+        case CallNode call -> call(call);
+        case CastNode cast -> new CastX86(cast);
+        case CProjNode c -> new CProjNode(c);
+        case ConstantNode con -> con(con);
+        case DivFNode divf -> new DivFX86(divf);
+        case DivNode div -> new DivX86(div);
+        case FunNode fun -> new FunX86(fun);
+        case IfNode iff -> jmp(iff);
+        case LoadNode ld -> ld(ld);
+        case MemMergeNode mem -> new MemMergeNode(mem);
+        case MulFNode mulf -> new MulFX86(mulf);
+        case MulNode mul -> mul(mul);
+        case NewNode nnn -> new NewX86(nnn);
+        case NotNode not -> new NotX86(not);
+        case OrNode or -> or(or);
+        case ParmNode parm -> new ParmX86(parm);
+        case PhiNode phi -> new PhiNode(phi);
+        case ProjNode prj -> prj(prj);
+        case ReadOnlyNode read -> new ReadOnlyNode(read);
+        case ReturnNode ret -> new RetX86(ret, ret.fun());
+        case SarNode sar -> sar(sar);
+        case ShlNode shl -> shl(shl);
+        case ShrNode shr -> shr(shr);
+        case StartNode start -> new StartNode(start);
+        case StopNode stop -> new StopNode(stop);
+        case StoreNode st -> st(st);
+        case SubFNode subf -> new SubFX86(subf);
+        case SubNode sub -> sub(sub);
+        case ToFloatNode tfn -> i2f8(tfn);
+        case XorNode xor -> xor(xor);
+
+        case LoopNode loop -> new LoopNode(loop);
+        case RegionNode region -> new RegionNode(region);
+        default -> throw Utils.TODO();
         };
     }