From 9b3ad43f7aa2ec6d5f61fb9ff3c432101a5fba52 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 17 Sep 2026 19:18:46 -0700 Subject: Major overhaul debug printing --- .../java/com/seaofnodes/simple/IRPrinterTest.java | 189 +++++++++++++++++++++ 1 file changed, 189 insertions(+) create mode 100644 chapter07/src/test/java/com/seaofnodes/simple/IRPrinterTest.java (limited to 'chapter07/src/test/java') diff --git a/chapter07/src/test/java/com/seaofnodes/simple/IRPrinterTest.java b/chapter07/src/test/java/com/seaofnodes/simple/IRPrinterTest.java new file mode 100644 index 00000000..a76f1eba --- /dev/null +++ b/chapter07/src/test/java/com/seaofnodes/simple/IRPrinterTest.java @@ -0,0 +1,189 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class IRPrinterTest { + private static final String SOURCE = """ + int sum=0; + int i=0; + while(i nodes = inputs(stop); + IdentityHashMap> defs = new IdentityHashMap<>(); + IdentityHashMap> uses = new IdentityHashMap<>(); + IdentityHashMap types = new IdentityHashMap<>(); + for( Node n : nodes ) { + defs.put(n,copy(n._inputs)); + uses.put(n,copy(n._outputs)); + types.put(n,n._type); + } + String printed = IRPrinter.prettyPrint(stop,999); + assertEquals(printed,IRPrinter.prettyPrint(stop,999)); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + int loops = 0; + for( Node n : nodes ) { + assertTrue("missing node " + n._nid,ids.contains(n._nid)); + assertEquals(defs.get(n),copy(n._inputs)); + assertEquals(uses.get(n),copy(n._outputs)); + assertSame(types.get(n),n._type); + if( !(n instanceof LoopNode) ) continue; + loops++; + ArrayList phis = new ArrayList<>(); + for( Node use : n._outputs ) + if( use instanceof PhiNode && use._inputs.get(0)==n ) phis.add(use); + phis.sort(Comparator.comparingInt(p -> p._nid)); + int idx = ids.indexOf(n._nid); + for( Node phi : phis ) assertEquals(Integer.valueOf(phi._nid),ids.get(++idx)); + } + assertTrue("nested source loops must remain",loops>=2); + + } + + @Test(timeout=5000) public void testBrokenGraphs() { + Node stop = new Parser(SOURCE).parse(); + // No entry control or backedge yet, and no reverse edge for the Phi. + LoopNode loop = new LoopNode(null); + PhiNode phi = new PhiNode("x",loop,null,null); + loop._outputs.clear(); + List header = ids(IRPrinter.prettyPrint(phi,0)); + assertEquals(Arrays.asList(loop._nid,phi._nid),header); + // An orphan projection's label may itself dereference missing inputs. + ProjNode proj = new ProjNode(null,0,"broken"); + assertTrue(ids(IRPrinter.prettyPrint(proj,0)).contains(proj._nid)); + // A data cycle with no roots must terminate and print both nodes once. + AddNode a = new AddNode(null,null); + AddNode b = new AddNode(a,null); + a._inputs.set(1,b); + a._outputs.add(null); // keep edge + List cycle = ids(IRPrinter.prettyPrint(a,999)); + assertEquals(2,cycle.size()); + assertTrue(cycle.contains(a._nid)); + assertTrue(cycle.contains(b._nid)); + a._inputs.clear(); + assertTrue(ids(IRPrinter.prettyPrint(a,999)).contains(a._nid)); + assertEquals("",IRPrinter.prettyPrint(null,999)); + } + + @Test public void testProjectionOrderAndSpacing() { + new Parser("return 0;").parse(); + IfNode multi = new IfNode(null,null); + ProjNode p2 = new ProjNode(multi,2,"two"); + ProjNode pm = new ProjNode(multi,-1,"minus"); + ProjNode p1 = new ProjNode(multi,1,"one"); + ProjNode p0 = new ProjNode(multi,0,"zero"); + String printed = IRPrinter.prettyPrint(p2,0); + assertEquals(Arrays.asList(multi._nid,pm._nid,p0._nid,p1._nid,p2._nid),ids(printed)); + String[] lines = printed.split("\n"); + int first = line(lines,multi); + assertTrue(first>0 && lines[first-1].isBlank()); + assertEquals(first+1,line(lines,pm)); + assertEquals(first+2,line(lines,p0)); + assertEquals(first+3,line(lines,p1)); + assertEquals(first+4,line(lines,p2)); + } + + @Test public void testNestedLoopRpo() { + new Parser("return 0;").parse(); + LoopNode outer = new LoopNode(null); + LoopNode inner = new LoopNode(outer); + PhiNode op = new PhiNode("outer",outer,null,null); + PhiNode ip = new PhiNode("inner",inner,null,null); + AddNode innerValue = new AddNode(ip,null); + AddNode outerValue = new AddNode(ip,op); + ip._inputs.set(2,innerValue); + op._inputs.set(2,outerValue); + IfNode branch = new IfNode(inner,ip); + ProjNode left = new ProjNode(branch,0,"left"); + ProjNode right = new ProjNode(branch,1,"right"); + RegionNode join = new RegionNode(null,left,right); + IfNode innerLatch = new IfNode(join,ip); + ProjNode innerBack = new ProjNode(innerLatch,0,"innerBack"); + ProjNode innerExit = new ProjNode(innerLatch,1,"innerExit"); + inner._inputs.set(2,innerBack); + IfNode outerLatch = new IfNode(innerExit,op); + ProjNode outerBack = new ProjNode(outerLatch,0,"outerBack"); + ProjNode outerExit = new ProjNode(outerLatch,1,"outerExit"); + outer._inputs.set(2,outerBack); + IfNode after = new IfNode(outerExit,op); + + // Raw input edits deliberately leave incomplete reverse edges. + String printed = IRPrinter.prettyPrint(after,999); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + before(ids,outer,inner); + before(ids,inner,branch); + before(ids,branch,join); + before(ids,join,innerLatch); + before(ids,innerLatch,outerLatch); + before(ids,innerValue,outerValue); + before(ids,innerLatch,outerValue); + before(ids,outerValue,outerLatch); + before(ids,outerLatch,after); + assertEquals(Integer.valueOf(ip._nid),ids.get(ids.indexOf(inner._nid)+1)); + assertEquals(Integer.valueOf(op._nid),ids.get(ids.indexOf(outer._nid)+1)); + String[] lines = printed.split("\n"); + for( Node cfg : new Node[]{outer,inner,branch,join,innerLatch,outerLatch,after} ) { + int idx=line(lines,cfg); + assertTrue("blank before CFG " + cfg._nid,idx>0 && lines[idx-1].isBlank()); + } + assertEquals(line(lines,branch)+1,line(lines,left)); + assertEquals(line(lines,branch)+2,line(lines,right)); + } + + private static void before(List ids, Node a, Node b) { + assertTrue("missing " + a._nid,ids.contains(a._nid)); + assertTrue("missing " + b._nid,ids.contains(b._nid)); + assertTrue(a._nid + " before " + b._nid,ids.indexOf(a._nid) ids(String text) { + ArrayList ids = new ArrayList<>(); + for( String line : text.split("\n") ) { + String s = line.trim(); + if( !s.isEmpty() && Character.isDigit(s.charAt(0)) ) + ids.add(Integer.valueOf(s.split("\\s+",2)[0])); + } + return ids; + } + + private static ArrayList inputs(Node root) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap seen = new IdentityHashMap<>(); + nodes.add(root); + seen.put(root,Boolean.TRUE); + for( int i=0; i copy(Iterable edges) { + ArrayList copy = new ArrayList<>(); + if( edges!=null ) for( Node n : edges ) copy.add(n); + return copy; + } +} -- cgit v1.2.3