Ch# Chapter 19: Instruction Selection and Portable Compilationlinear-chapter19

Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

1 files changed, 38 insertions, 29 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index d3ee62c3..12dd9243 100644
--- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -10,46 +10,54 @@ public abstract class GlobalCodeMotion {
     // Arrange that the existing isCFG() Nodes form a valid CFG.  The
     // Node.use(0) is always a block tail (either IfNode or head of the
     // following block).  There are no unreachable infinite loops.
-    public static void buildCFG( StartNode start, StopNode stop ) {
-        schedEarly(start);
-        schedLate(stop);
+    public static void buildCFG( CodeGen code ) {
+        Ary<CFGNode> rpo = new Ary<>(CFGNode.class);
+        _rpo_cfg(null, code._start, code.visit(), rpo);
+        // Reverse in-place
+        for( int i=0; i< rpo.size()>>1; i++ ) {
+            int j = rpo.size()-1-i;
+            CFGNode tmp = rpo.get(i);
+            rpo.set(i, rpo.get(j));
+            rpo.set(j, tmp);
+        }
+        // Set global CFG
+        code._cfg = rpo;
+
+        schedEarly(code);
+        code._visit.clear();
+        schedLate (code);
     }
 
+    // Post-Order of CFG
+    private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) {
+        if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) )
+            return;             // Been there, done that
+        if( def instanceof CallNode && cfg instanceof FunNode )
+            return;           // Ignore linked function calls
+        visit.set(cfg._nid);
+        for( Node useuse : cfg._outputs )
+            _rpo_cfg(cfg,useuse,visit,rpo);
+        rpo.add(cfg);
+    }
 
     // ------------------------------------------------------------------------
     // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses
     // (except at loops).  Since defs are visited first - and hoisted as early
     // as possible, when we come to a use we place it just after its deepest
     // input.
-    private static void schedEarly(StartNode start) {
-        ArrayList<CFGNode> rpo = new ArrayList<>();
-        BitSet visit = new BitSet();
-        _rpo_cfg(null, start, visit, rpo);
+    private static void schedEarly(CodeGen code) {
         // Reverse Post-Order on CFG
-        for( int j=rpo.size()-1; j>=0; j-- ) {
-            CFGNode cfg = rpo.get(j);
+        for( CFGNode cfg : code._cfg ) {
             cfg.loopDepth();
             for( Node n : cfg._inputs )
-                _schedEarly(n,visit);
+                _schedEarly(n,code._visit );
             if( cfg instanceof RegionNode )
                 for( Node phi : cfg._outputs )
                     if( phi instanceof PhiNode )
-                        _schedEarly(phi,visit);
+                        _schedEarly(phi,code._visit );
         }
     }
 
-    // Post-Order of CFG
-    private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, ArrayList<CFGNode> rpo) {
-        if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) )
-            return;             // Been there, done that
-        if( def instanceof CallNode && cfg instanceof FunNode )
-            return;           // Ignore linked function calls
-        visit.set(cfg._nid);
-        for( Node useuse : cfg._outputs )
-            _rpo_cfg(cfg,useuse,visit,rpo);
-        rpo.add(cfg);
-    }
-
     private static void _schedEarly(Node n, BitSet visit) {
         if( n==null || visit.get(n._nid) ) return; // Been there, done that
         assert !(n instanceof CFGNode);
@@ -61,24 +69,25 @@ public abstract class GlobalCodeMotion {
         for( Node def : n._inputs )
             if( def!=null && !(def instanceof PhiNode) )
                 _schedEarly(def,visit);
+
         // If not-pinned (e.g. constants, projections, phi) and not-CFG
         if( !n.isPinned() ) {
             // Schedule at deepest input
-            CFGNode early = Parser.START; // Maximally early, lowest idepth
+            CFGNode early = CodeGen.CODE._start; // Maximally early, lowest idepth
             if( n.in(0) instanceof CFGNode cfg ) early = cfg;
             for( int i=1; i<n.nIns(); i++ )
                 if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
                     early = n.in(i).cfg0(); // Latest/deepest input
-            n.setDef(0,early);              // First place this can go
+            n.setDef(0,early);
         }
     }
 
     // ------------------------------------------------------------------------
-    private static void schedLate( StopNode stop) {
-        CFGNode[] late = new CFGNode[Node.UID()];
-        Node[] ns = new Node[Node.UID()];
+    private static void schedLate( CodeGen code ) {
+        CFGNode[] late = new CFGNode[code.UID()];
+        Node[] ns = new Node[code.UID()];
         // Breadth-first scheduling
-        breadth(stop,ns,late);
+        breadth(code._stop,ns,late);
 
         // Copy the best placement choice into the control slot
         for( int i=0; i<late.length; i++ )