update slides

2 files changed, 94 insertions, 7 deletions

diff --git a/print/src/main/java/com/seaofnodes/print/IRPrinter.java b/print/src/main/java/com/seaofnodes/print/IRPrinter.java
index bfe1cb05..b974ebe1 100644
--- a/print/src/main/java/com/seaofnodes/print/IRPrinter.java
+++ b/print/src/main/java/com/seaofnodes/print/IRPrinter.java
@@ -36,7 +36,7 @@ public final class IRPrinter<N extends BaseNode<N>> {
                     N p=_a.out(unit.start(),i);
                     if( _a.projection(p) ) ps.add(p);
                 }
-                ps.sort(Comparator.comparingInt(_a::index));
+                ps.sort(projectionOrder());
                 for( N p : ps ) sb.append(line(p));
             }
             ArrayList<N> funs=new ArrayList<>(unit.functions());
@@ -107,6 +107,12 @@ public final class IRPrinter<N extends BaseNode<N>> {
                 N head=_a.input0(n);
                 if( head != null ) nodes.put(head,Boolean.TRUE);
             }
+        // Complete projection groups without extending ordinary dependencies.
+        for( N n : new ArrayList<>(nodes.keySet()) )
+            for( int i=0; i<_a.nOuts(n); i++ ) {
+                N p=_a.out(n,i);
+                if( _a.projection(p) && _a.input0(p)==n ) nodes.put(p,Boolean.TRUE);
+            }
         return render(nodes);
     }
 
@@ -169,16 +175,21 @@ public final class IRPrinter<N extends BaseNode<N>> {
         ArrayList<ArrayList<N>> body=new ArrayList<>();
         for( int i=0; i<post.size(); i++ ) { blocks.put(post.get(i),i); body.add(new ArrayList<>()); }
         if( body.isEmpty() ) body.add(new ArrayList<>());
+        for( N n : ns ) block(n,nodes,blocks);
+        IdentityHashMap<N,Integer> placed=new IdentityHashMap<>();
         for( N n : ns )
-            if( !_a.control(n) ) body.get(block(n,nodes,blocks)).add(n);
+            if( !_a.control(n) ) body.get(place(n,nodes,blocks,placed)).add(n);
         StringBuilder sb=new StringBuilder();
         IdentityHashMap<N,Boolean> emitted=new IdentityHashMap<>();
         for( int i=0; i<body.size(); i++ ) {
             if( i<post.size() ) {
                 N cfg=post.get(i);
-                sb.append('\n');
+                if( !emitted.containsKey(cfg) ) sb.append('\n');
+                for( N n : body.get(i) )
+                    if( !_a.phi(n) && !_a.projection(n) && _a.input0(n)==null ) emit(n,nodes,emitted,sb);
                 emitDefs(cfg,nodes,emitted,sb);
                 emitLine(cfg,emitted,sb);
+                projections(cfg,nodes,emitted,sb);
                 // A Phi's backedge belongs in the body, never ahead of the Phi.
                 for( N n : body.get(i) ) if( _a.phi(n) ) emitLine(n,emitted,sb);
             }
@@ -235,6 +246,35 @@ public final class IRPrinter<N extends BaseNode<N>> {
                           StringBuilder sb) {
         for( int i=0; i<_a.nIns(n); i++ ) emit(_a.in(n,i),nodes,emitted,sb);
     }
+
+    // Floating data follows its uses. A loop Phi consumes its backedge value
+    // at the latch, not at the header of that (possibly enclosing) loop.
+    private int place(N n, IdentityHashMap<N,Boolean> nodes, IdentityHashMap<N,Integer> blocks,
+                      IdentityHashMap<N,Integer> placed) {
+        Integer old=placed.get(n);
+        if( old!=null ) return old;
+        int early=blocks.get(n);
+        placed.put(n,early); // Close data cycles without changing compiler state.
+        if( _a.control(n) || _a.phi(n) || _a.projection(n) || _a.global(n) ||
+            _a.input0(n)!=null ) return early;
+        int late=Integer.MAX_VALUE;
+        for( int i=0; i<_a.nOuts(n); i++ ) {
+            N use=_a.out(n,i);
+            if( use==null || !nodes.containsKey(use) || _a.kind(use)==Kind.PARM ) continue;
+            if( _a.phi(use) && _a.input0(use)!=null && _a.kind(_a.input0(use))==Kind.LOOP ) {
+                N loop=_a.input0(use);
+                for( int j=1; j<_a.nIns(use); j++ )
+                    if( _a.in(use,j)==n && j<_a.nIns(loop) ) {
+                        N pred=_a.in(loop,j);
+                        if( _a.projection(pred) ) pred=_a.input0(pred);
+                        if( pred!=null && blocks.containsKey(pred) ) late=Math.min(late,blocks.get(pred));
+                    }
+            } else late=Math.min(late,place(use,nodes,blocks,placed));
+        }
+        int b=late==Integer.MAX_VALUE ? early : Math.max(early,late);
+        placed.put(n,b);
+        return b;
+    }
     private void emit(N n, IdentityHashMap<N,Boolean> nodes, IdentityHashMap<N,Boolean> emitted,
                       StringBuilder sb) {
         if( n==null || emitted.containsKey(n) || !nodes.containsKey(n) || _a.control(n) || _a.phi(n) ) return;
@@ -256,12 +296,16 @@ public final class IRPrinter<N extends BaseNode<N>> {
         ArrayList<N> ps=new ArrayList<>();
         for( int i=0; i<_a.nOuts(n); i++ ) {
             N p=_a.out(n,i);
-            if( p!=null && nodes.containsKey(p) && _a.kind(p)==Kind.PROJ && _a.input0(p)==n ) ps.add(p);
+            if( _a.projection(p) && nodes.containsKey(p) && _a.input0(p)==n ) ps.add(p);
         }
-        ps.sort(Comparator.comparingInt(_a::index));
+        ps.sort(projectionOrder());
         for( N p : ps ) emitLine(p,emitted,sb);
     }
 
+    private Comparator<N> projectionOrder() {
+        return Comparator.comparingInt(_a::index).thenComparingInt(_a::id);
+    }
+
     /** Scheduling already determines order; inspect it without sorting compiler arrays. */
     public String scheduled(ArrayList<N> blocks) {
         StringBuilder sb=new StringBuilder();
@@ -283,7 +327,7 @@ public final class IRPrinter<N extends BaseNode<N>> {
                         N p=_a.out(use,j);
                         if( p!=null && _a.kind(p)==Kind.PROJ && _a.input0(p)==use ) ps.add(p);
                     }
-                    ps.sort(Comparator.comparingInt(_a::index));
+                    ps.sort(projectionOrder());
                     for( N p : ps ) emitLine(p,emitted,sb);
                 }
             }
diff --git a/print/src/test/java/com/seaofnodes/print/PrinterTest.java b/print/src/test/java/com/seaofnodes/print/PrinterTest.java
index d63cc6cb..1cbe8a11 100644
--- a/print/src/test/java/com/seaofnodes/print/PrinterTest.java
+++ b/print/src/test/java/com/seaofnodes/print/PrinterTest.java
@@ -29,7 +29,7 @@ public class PrinterTest {
     }
 
     public static void main(String[] args) {
-        expression(); loop(); functions(); assembly();
+        expression(); loop(); ordering(); functions(); assembly();
         System.out.println("Shared printer contracts passed");
     }
     static void expression() {
@@ -90,6 +90,49 @@ public class PrinterTest {
     }
     static int row(String text,String name) { return text.indexOf(" "+name+" "); }
 
+    static void ordering() {
+        var adapter=new Adapter() {
+            @Override public int index(N n) { return switch(n.name) {
+                case "Minus" -> -1; case "Zero", "Again" -> 0; case "Two" -> 2;
+                default -> n._nid;
+            }; }
+        };
+        IRPrinter<N> printer=new IRPrinter<>(adapter);
+        N multi=new N(1,"Multi",Kind.MULTI);
+        N two=new N(2,"Two",Kind.PROJ,multi);
+        N minus=new N(3,"Minus",Kind.PROJ,multi);
+        N zero=new N(4,"Zero",Kind.CPROJ,multi);
+        N again=new N(5,"Again",Kind.PROJ,multi);
+        String text=printer.prettyPrint(two,0);
+        int[] ids=text.lines().filter(s -> !s.isBlank()).mapToInt(s -> Integer.parseInt(s.trim().split("\\s+")[0])).toArray();
+        assert Arrays.equals(ids,new int[]{1,3,4,5,2}) : text;
+        assert multi.outs.equals(Arrays.asList(two,minus,zero,again));
+
+        N outer=new N(10,"Outer",Kind.LOOP,null,null);
+        N inner=new N(11,"Inner",Kind.LOOP,null,outer);
+        N op=new N(12,"OPhi",Kind.PHI,outer,null);
+        N ip=new N(13,"IPhi",Kind.PHI,inner,null);
+        N iv=new N(14,"IValue",Kind.DATA,null,ip);
+        N ov=new N(15,"OValue",Kind.DATA,null,ip,op);
+        ip.add(iv); op.add(ov);
+        N branch=new N(16,"Branch",Kind.CTRL,inner,ip);
+        N left=new N(17,"Left",Kind.CPROJ,branch), right=new N(18,"Right",Kind.CPROJ,branch);
+        N join=new N(19,"Join",Kind.REGION,null,left,right);
+        N il=new N(20,"ILatch",Kind.CTRL,join,ip);
+        N ib=new N(21,"IBack",Kind.CPROJ,il), ie=new N(22,"IExit",Kind.CPROJ,il);
+        inner.add(ib);
+        N ol=new N(23,"OLatch",Kind.CTRL,ie,op);
+        N ob=new N(24,"OBack",Kind.CPROJ,ol), oe=new N(25,"OExit",Kind.CPROJ,ol);
+        outer.add(ob);
+        N after=new N(26,"After",Kind.CTRL,oe,op);
+        text=printer.prettyPrint(after,99);
+        N[] order={outer,op,inner,ip,branch,join,il,ov,ol,after};
+        for( int i=1; i<order.length; i++ )
+            assert row(text,order[i-1].name)<row(text,order[i].name) : text;
+        assert row(text,iv.name)<row(text,ov.name) : text;
+        assert text.equals(printer.prettyPrint(after,99));
+    }
+
     static void functions() {
         N start=new N(1,"Start",Kind.START), stop=new N(2,"Stop",Kind.STOP);
         N one=new N(3,"One",Kind.CONSTANT,start);