Chapter 6: Peepholes for If

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

5 files changed, 314 insertions, 26 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
index 4085ed7e..47cee096 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -14,8 +14,6 @@ public class Chapter02Test {
         Node._disablePeephole = true; // disable peephole so we can observe full graph
         StopNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
-        GraphVisualizer gv = new GraphVisualizer();
-        System.out.println(gv.generateDotOutput(parser));
         Node._disablePeephole = false;
     }
 
@@ -59,8 +57,6 @@ public class Chapter02Test {
         Parser parser = new Parser("return 1+2*3+-5;");
         StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
-        GraphVisualizer gv = new GraphVisualizer();
-        System.out.println(gv.generateDotOutput(parser));
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 407fbe48..33e2e824 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -31,7 +31,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarScopeNoPeephole() {
-        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
         Node._disablePeephole = true;
         StopNode ret = parser.parse();
         Node._disablePeephole = false;
@@ -40,7 +40,7 @@ public class Chapter03Test {
 
     @Test
     public void testVarDist() {
-        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
+        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);");
         StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 55c0b15f..98878ca6 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -10,7 +10,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole() {
-        Parser parser = new Parser("return 1+arg+2; #showGraph;");
+        Parser parser = new Parser("return 1+arg+2;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
@@ -38,7 +38,7 @@ public class Chapter04Test {
 
     @Test
     public void testPeephole3() {
-        Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
+        Parser parser = new Parser("return 1+arg+2+arg+3;");
         StopNode ret = parser.parse();
         assertEquals("return ((arg*2)+6);", ret.print());
     }
@@ -52,7 +52,7 @@ public class Chapter04Test {
 
     @Test
     public void testVarArg() {
-        Parser parser = new Parser("return arg; #showGraph;");
+        Parser parser = new Parser("return arg;");
         StopNode stop = parser.parse();
         ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
@@ -61,49 +61,49 @@ public class Chapter04Test {
 
     @Test
     public void testConstantArg() {
-        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
+        Parser parser = new Parser("return arg;", TypeInteger.constant(2));
         StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testCompEq() {
-        Parser parser = new Parser("return 3==3; #showGraph;");
+        Parser parser = new Parser("return 3==3;");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testCompEq2() {
-        Parser parser = new Parser("return 3==4; #showGraph;");
+        Parser parser = new Parser("return 3==4;");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq() {
-        Parser parser = new Parser("return 3!=3; #showGraph;");
+        Parser parser = new Parser("return 3!=3;");
         StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq2() {
-        Parser parser = new Parser("return 3!=4; #showGraph;");
+        Parser parser = new Parser("return 3!=4;");
         StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testBug1() {
-        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;");
+        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testBug2() {
-        Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;");
+        Parser parser = new Parser("int a=arg+1; a=a; return a;");
         StopNode ret = parser.parse();
         assertEquals("return (arg+1);", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index b5fcbeaf..134a8be2 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -17,11 +17,9 @@ if (arg == 1)
     a = arg+2;
 else {
     a = arg-3;
-    #showGraph;
 }
-#showGraph;
 return a;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
 
@@ -36,7 +34,7 @@ if (arg == 1) {
     c = 4;
 }
 return c;""", TypeInteger.BOT);
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return Phi(Region16,4,3);", ret.toString());
     }
 
@@ -48,7 +46,7 @@ if( arg==1 )
     return 3;
 else
     return 4;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("Stop[ return 3; return 4; ]", stop.toString());
     }
@@ -64,7 +62,7 @@ if( arg==1 )
 else
     b=a+1;
 return a+b;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
     }
 
@@ -79,7 +77,7 @@ if( arg==1 )
 else
     a=b+1;
 return a+b;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString());
     }
 
@@ -98,7 +96,7 @@ else if( arg==3 )
 else
     a=5;
 return a;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
     }
@@ -114,7 +112,7 @@ if( arg )
 if( arg==0 )
     b=2;
 return arg+a+b;
-#showGraph;""", TypeInteger.BOT);
+""", TypeInteger.BOT);
         StopNode stop = parser.parse();
         assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString());
     }
@@ -129,7 +127,7 @@ if( arg==1 )
     a=arg==3;
 }
 return a;""");
-        StopNode ret = parser.parse(true);
+        StopNode ret = parser.parse(false);
         assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
new file mode 100644
index 00000000..44b49d73
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -0,0 +1,294 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+public class Chapter06Test {
+
+    @Test
+    public void testPeepholeReturn() {
+        Parser parser = new Parser(
+"""
+if( true ) return 2;
+return 1;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testPeepholeRotate() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+if (arg)
+    a = 2;
+return (arg < a) < 3;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
+    }
+
+    @Test
+    public void testPeepholeCFG() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( true )
+  a=2;
+else
+  a=3;
+return a;
+""");
+        StopNode stop = parser.parse(false);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testIfIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg!=1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( a==2 )
+    b=42;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region32,42,5);", stop.toString());
+    }
+
+    @Test
+    public void testIfArgIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( 1==1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( arg==2 )
+    b=a;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region28,2,5);", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With2() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(2));
+        StopNode stop = parser.parse();
+        assertEquals("return 5;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.BOT);
+        StopNode stop = parser.parse(false);
+        assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole3() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(3));
+        StopNode stop = parser.parse(false);
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testDemo1NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""");
+        StopNode ret = parser.parse(false);
+        assertEquals("return Phi(Region22,4,1);", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo1True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 4;", ret.toString());
+    }
+
+    @Test
+    public void testDemo1False() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(0));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 1;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""");
+        StopNode ret = parser.parse(false);
+        assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region33,3,1));", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo2True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 6;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2arg2() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(2));
+        StopNode ret = parser.parse(false);
+        assertEquals("return 5;", ret.toString());
+    }
+
+}