From 4d5538c4b9df61d6c2524868bd005030123b3189 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Sat, 8 Mar 2025 15:17:22 -0800
Subject: first cut encoding driver

ASM printer skips jmps to next-blocks
---
 .../com/seaofnodes/simple/codegen/CodeGen.java     |  8 +--
 .../com/seaofnodes/simple/codegen/Encoding.java    | 60 ++++++++++++++++++++++
 .../com/seaofnodes/simple/print/ASMPrinter.java    | 23 ++++++---
 3 files changed, 79 insertions(+), 12 deletions(-)
 create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java

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

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index a1294890..4215233e 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -303,14 +303,14 @@ public class CodeGen {
     // ---------------------------
     // Encoding
     int _tEncode;
+    public Encoding _encoding;
     public CodeGen encode() {
         assert _phase == Phase.RegAlloc;
         _phase = Phase.Encoding;
         long t0 = System.currentTimeMillis();
-
-
-        //_tEncode = (int)(System.currentTimeMillis() - t0);
-        //throw Utils.TODO();
+        _encoding = new Encoding(this);
+        _encoding.encode();
+        _tEncode = (int)(System.currentTimeMillis() - t0);
         return this;
     }
     // Encoded binary, no relocation info
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
new file mode 100644
index 00000000..d7a19e2a
--- /dev/null
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.node.*;
+import java.io.ByteArrayOutputStream;
+
+
+/**
+ *  Instruction encodings
+ *
+ *  This class holds the encoding bits, plus the relocation information needed
+ *  to move the code to a non-zero offset, or write to an external file (ELF).
+ *
+ *  There are also a bunch of generic utilities for managing bits and bytes
+ *  common in all encodings.
+ */
+public class Encoding {
+
+    // Top-level program graph structure
+    final CodeGen _code;
+
+    // Instruction bytes.  The registers are encoded already.  Relocatable data
+    // is in a fixed format depending on the kind of relocation.
+
+    // - RIP-relative offsets into the same chunk are just encoded with their
+    //   check relative offsets; no relocation info is required.
+
+    // - Fixed address targets in the same encoding will be correct for a zero
+    //   base; moving the entire encoding requires adding the new base address.
+
+    // - RIP-relative to external chunks have a zero offset; the matching
+    //   relocation info will be used to patch the correct value.
+
+    final ByteArrayOutputStream _bits;
+
+
+    Encoding( CodeGen code ) {
+        _code = code;
+        _bits = new ByteArrayOutputStream();
+    }
+
+
+    void encode() {
+        // Basic block layout.  Now that RegAlloc is finished, no more spill
+        // code will appear.  We can change our BB layout from RPO to something
+        // that minimizes actual branches, takes advantage of fall-through
+        // edges, and tries to help simple branch predictions: back branches
+        // are predicted taken, forward not-taken.
+
+
+
+
+        // Write bits in order
+        for( CFGNode bb : _code._cfg )
+            for( Node n : bb._outputs )
+                if( n instanceof MachNode mach )
+                    throw Utils.TODO();
+    }
+
+}
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 1a233aa2..72da53bf 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
@@ -3,7 +3,6 @@ package com.seaofnodes.simple.print;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.SB;
 import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeFunPtr;
 import com.seaofnodes.simple.type.TypeMem;
 import com.seaofnodes.simple.type.TypeRPC;
 
@@ -45,7 +44,7 @@ public abstract class ASMPrinter {
     static int doBlock(int iadr, SB sb, CodeGen code, FunNode fun, int cfgidx) {
         CFGNode bb = code._cfg.at(cfgidx);
         if( bb != fun && !(bb instanceof IfNode) && !(bb instanceof CallEndNode) && !(bb instanceof CallNode)  && !(bb instanceof CProjNode && bb.in(0) instanceof CallEndNode ))
-            sb.p(bb instanceof LoopNode ? "LOOP" : "L").p(bb._nid).p(":").nl();
+            sb.p(label(bb)).p(":").nl();
         if( bb instanceof CallNode ) return iadr;
         final boolean postAlloc = code._phase.ordinal() > CodeGen.Phase.RegAlloc.ordinal();
 
@@ -56,7 +55,7 @@ public abstract class ASMPrinter {
                 break;
 
         if( nPhi>0 ) {
-            // Post-alloc phi prints all on one line
+            // Post- RegAlloc phi prints all on one line
             if( postAlloc ) {
                 sb.fix(4," ").p(" ").fix(encWidth,"").p("  ");
                 for( int i=0; i<nPhi; i++ ) {
@@ -67,6 +66,7 @@ public abstract class ASMPrinter {
                 sb.unchar().nl();
 
             } else {
+                // Pre- RegAlloc phi prints one line per
                 for( int j=0; j<nPhi; j++ ) {
                     PhiNode phi = (PhiNode)bb.out(j);
                     if( phi._type instanceof TypeMem || phi._type instanceof TypeRPC ) continue; // Nothing for the hidden ones
@@ -85,20 +85,22 @@ public abstract class ASMPrinter {
 
         // All the non-phis
         for( int i=nPhi; i<bb.nOuts(); i++ )
-            iadr = doInst(iadr, sb,code,fun,bb,bb.out(i),postAlloc );
+            iadr = doInst(iadr, sb,code, cfgidx, bb.out(i),postAlloc );
 
         return iadr;
     }
 
-    static int doInst(int iadr, SB sb, CodeGen code, FunNode fun, CFGNode bb, Node n, boolean postAlloc ) {
+    static int doInst( int iadr, SB sb, CodeGen code, int cfgidx, Node n, boolean postAlloc ) {
         if( n instanceof CProjNode ) return iadr;
         if( n instanceof CalleeSaveNode && postAlloc ) return iadr;
+        if( n instanceof MemMergeNode ) return iadr;
 
         // All blocks ending in a Region will need to either fall into or jump
         // 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 && !(n instanceof FunNode) ) {
-            sb.hex4(iadr++).p(" ").fix(encWidth,"??").p("  ").fix(opWidth,"JMP").p(" ").fix(argWidth,"L"+n._nid).nl();
+        if( n instanceof RegionNode cfg && !(n instanceof FunNode) ) {
+            if( code._cfg.at(cfgidx+1) == n ) return iadr; // Fall-through, no branch
+            sb.hex4(iadr++).p(" ").fix(encWidth,"??").p("  ").fix(opWidth,"JMP").p(" ").fix(argWidth,label(cfg)).nl();
             return iadr;
         }
 
@@ -154,10 +156,15 @@ public abstract class ASMPrinter {
         if( !(n instanceof CFGNode) && n instanceof MultiNode ) {
             for( Node proj : n._outputs ) {
                 assert proj instanceof ProjNode;
-                doInst(iadr,sb,code,fun,bb,proj,postAlloc);
+                doInst(iadr,sb,code, cfgidx, proj,postAlloc);
             }
         }
 
         return iadr;
     }
+
+    private static String label( CFGNode bb ) {
+        return (bb instanceof LoopNode ? "LOOP" : "L")+bb._nid;
+    }
+
 }
-- 
cgit v1.2.3