summaryrefslogtreecommitdiff
path: root/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java
diff options
context:
space:
mode:
Diffstat (limited to 'chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java')
-rw-r--r--chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java609
1 files changed, 609 insertions, 0 deletions
diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java
new file mode 100644
index 00000000..afe0b141
--- /dev/null
+++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -0,0 +1,609 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Test;
+import com.seaofnodes.simple.node.*;
+import java.util.BitSet;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter10Test {
+ @Test public void testConditionalStoreSharing() {
+ // Sharing the writes on two of three paths must not write on the third.
+ // Return the object so Load forwarding cannot hide the physical Store.
+ String src = """
+ struct S { int x; };
+ !S !a = new S;
+ a.x = 10;
+ if (arg == 1) a.x = 9;
+ else if (arg == 2) a.x = 9;
+ return a;
+ """;
+ var code = new CodeGen(src).driver(CodeGen.Phase.LocalSched);
+ for( int arg : new int[]{0,1,2,3} ) {
+ long expected = (arg==1 || arg==2) ? 9 : 10;
+ assertEquals("S{x="+expected+"}",Eval2.eval(code,arg));
+ }
+ }
+
+ @Test public void testDeadReferenceReturn() {
+ for( String body : new String[] {
+ "return new S; return 0;",
+ "if(1) return new S; else return 0;"
+ } ) {
+ String src = "struct S { int x; }; " + body;
+ var code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck);
+ org.junit.Assert.assertTrue(body,
+ code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr);
+ }
+ }
+
+
+
+ // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15.
+ private static final String NULLABLE_POINT_SOURCE = """
+ struct Point { int x; };
+ !Point?[] !points = new !Point?[2];
+ points[arg] = new Point { x = 42; };
+ Point? p = points[1];
+ """;
+
+ @Test
+ public void testNullGuards() {
+ for( String body : new String[] {
+ "if (p != null) return p.x; return -1;",
+ "if (null != p) return p.x; return -1;",
+ "if (!!!!p) return p.x; return -1;",
+ "if (!!!p) return -1; return p.x;",
+ "int b = !!p; if (b) return p.x + b - 1; return -1;",
+ "if (!(p == null || arg == 0)) return p.x; return -1;"
+ } ) {
+ CodeGen code = new CodeGen(NULLABLE_POINT_SOURCE+body).driver(CodeGen.Phase.TypeCheck);
+ assertEquals(body,"-1",Eval2.eval(code,0));
+ assertEquals(body,"42",Eval2.eval(code,1));
+ }
+ }
+
+ @Test
+ public void testShortCircuitGuardScheduling() {
+ // The call result exists only on the RHS path, not above the merge.
+ CodeGen code = new CodeGen("""
+ val f = { int n -> (n+1)&7; };
+ int x = 0;
+ if (!!(arg && (x=f(arg)))) return x;
+ return -1;
+ """).driver(CodeGen.Phase.TypeCheck);
+ assertEquals("-1",Eval2.eval(code,0));
+ assertEquals("2",Eval2.eval(code,1));
+ assertEquals("-1",Eval2.eval(code,7));
+ code.driver(CodeGen.Phase.LocalSched);
+ }
+
+ @Test
+ public void testNullGuardErrors() {
+ for( String body : new String[] {
+ "return p.x;",
+ "if (p == null) return p.x; return -1;",
+ "if (!!points) return p.x; return -1;",
+ "if (!!p) { int x = p.x; } return p.x;"
+ } ) {
+ try {
+ new CodeGen(NULLABLE_POINT_SOURCE+body).driver(CodeGen.Phase.TypeCheck);
+ fail(body);
+ } catch( RuntimeException e ) {
+ // Known null is rejected during parsing in these chapters.
+ String expected = body.startsWith("if (p == null)")
+ ? "Accessing unknown field 'x' from 'null'" : "Might be null accessing 'x'";
+ assertEquals(body,expected,e.getMessage());
+ }
+ }
+ }
+
+ @Test
+ public void testFuzzer() {
+ CodeGen code = new CodeGen(
+"""
+int a = arg/3;
+int b = arg*5;
+int x = arg*7;
+int y = arg/11;
+int p; int g; int h;
+if( (arg/13)==0 ) {
+ p = x + y;
+ g = x;
+ h = y;
+} else {
+ p = a + b;
+ g = a;
+ h = b;
+}
+int r = g+h;
+return p-r;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 0;", code.print());
+ }
+
+ @Test
+ public void testStruct() {
+ CodeGen code = new CodeGen("""
+struct Bar {
+ int a;
+ int b;
+};
+struct Foo {
+ int x;
+};
+Foo? foo = null;
+!Bar !bar = new Bar;
+bar.a = 1;
+bar.a = 2;
+return bar.a;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 2;", code.print());
+ }
+
+ @Test
+ public void testExample() {
+ CodeGen code = new CodeGen("""
+struct Vector2D { int x; int y; };
+!Vector2D !v = new Vector2D;
+v.x = 1;
+if (arg)
+ v.y = 2;
+else
+ v.y = 3;
+return v;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Vector2D;", code.print());
+ }
+
+ @Test
+ public void testBug() {
+ CodeGen code = new CodeGen("""
+struct s0 {
+ int v0;
+};
+s0? v1=null;
+int v3=v1.zAicm;
+""");
+ try { code.parse(); fail(); }
+ catch( Exception e ) { assertEquals("Accessing unknown field 'zAicm' from 'null'",e.getMessage()); }
+ }
+
+ @Test
+ public void testBug2() {
+ CodeGen code = new CodeGen("""
+struct s0 { int v0; };
+arg=0+new s0.0;
+""");
+ try { code.parse(); fail(); }
+ catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); }
+ }
+
+ @Test
+ public void testLoop() {
+ CodeGen code = new CodeGen("""
+struct Bar { int a; };
+!Bar !bar = new Bar;
+while (arg) {
+ bar.a = bar.a + 2;
+ arg = arg + 1;
+}
+return bar.a;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_a+2));", code.print());
+ }
+
+ @Test
+ public void testIf() {
+ CodeGen code = new CodeGen("""
+struct Bar { int a; };
+!Bar !bar = new Bar;
+if (arg) bar = null;
+bar.a = 1;
+return bar.a;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Type null is not of declared type *Bar",e.getMessage()); }
+ }
+
+ @Test
+ public void testIf2() {
+ CodeGen code = new CodeGen("""
+struct Bar { int a; };
+!Bar? !bar = null;
+if (arg) bar = new Bar;
+bar.a = 1;
+return bar.a;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Might be null accessing 'a'",e.getMessage()); }
+ }
+
+ @Test
+ public void testIf3() {
+ CodeGen code = new CodeGen("""
+struct Bar { int a; };
+!Bar !bar = null;
+if (arg) bar = null;
+bar.a = 1;
+return bar.a;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Type null is not of declared type *Bar", e.getMessage()); }
+ }
+
+ @Test
+ public void testIfOrNull() {
+ CodeGen code = new CodeGen("""
+struct Bar { int a; };
+!Bar? !bar = new Bar;
+if (arg) bar = null;
+if( bar ) bar.a = 1;
+return bar;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,null,Bar);", code.print());
+ }
+
+ @Test
+ public void testIfOrNull2() {
+ CodeGen code = new CodeGen(
+"""
+struct Bar { int a; };
+!Bar? !bar = new Bar;
+if (arg) bar = null;
+int rez = 3;
+if( !bar ) rez=4;
+else bar.a = 1;
+return rez;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,4,3);", code.print());
+ }
+
+ @Test
+ public void testWhileWithNullInside() {
+ CodeGen code = new CodeGen("""
+struct s0 {int v0;};
+!s0? !v0 = new s0;
+int ret = 0;
+while(arg) {
+ ret = v0.v0;
+ v0 = null;
+ arg = arg - 1;
+}
+return ret;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) {
+ assertEquals("Might be null accessing 'v0'", e.getMessage()); }
+ }
+
+ @Test
+ public void testRedeclareStruct() {
+ CodeGen code = new CodeGen("""
+struct s0 {
+ int v0;
+};
+s0? v1=new s0;
+!s0? !v1;
+v1=new s0;
+""");
+ try { code.parse(); fail(); }
+ catch( Exception e ) { assertEquals("Redefining name 'v1'", e.getMessage()); }
+ }
+
+ @Test
+ public void testIter() {
+ // Build and use an iterator
+ CodeGen code = new CodeGen(
+"""
+struct Iter {
+ int x;
+ int len;
+};
+!Iter !i = new Iter;
+i.len = arg;
+int sum=0;
+while( i.x < i.len ) {
+ sum = sum + i.x;
+ i.x = i.x + 1;
+}
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", code.print());
+ }
+
+
+ @Test
+ public void test1() {
+ CodeGen code = new CodeGen("""
+struct s0 {int v0;};
+!s0 !ret = new s0;
+while(arg) {
+ !s0 !v0 = new s0;
+ v0.v0 = arg;
+ arg = arg-1;
+ if (arg==5) ret=v0;
+
+}
+return ret;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print());
+ }
+
+ @Test
+ public void test2() {
+ CodeGen code = new CodeGen("""
+struct s0 {int v0;};
+!s0 !ret = new s0;
+!s0 !v0 = new s0;
+while(arg) {
+ v0.v0 = arg;
+ arg = arg-1;
+ if (arg==5) ret=v0;
+
+}
+return ret;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print());
+ }
+
+
+ @Test
+ public void test3() {
+ CodeGen code = new CodeGen("""
+struct s0 {int v0;};
+!s0 !ret = new s0;
+while(arg < 10) {
+ !s0 !v0 = new s0;
+ if (arg == 5) ret=v0;
+ arg = arg + 1;
+}
+return ret;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print());
+ }
+
+ @Test
+ public void testBug3() {
+ CodeGen code = new CodeGen("""
+struct s0 { int f0; };
+return new s0;
+int v0=null.f0;
+""");
+ try { code.parse(); fail(); }
+ catch( Exception e ) { assertEquals("Syntax error, expected ;: .",e.getMessage()); }
+ }
+
+ @Test
+ public void testBug4() {
+ CodeGen code = new CodeGen("""
+if(0) {
+ while(0) if(arg) continue;
+ int v0=0;
+ while(1) {
+ int v2=-arg;
+ v0=v2;
+ }
+}
+return 0;
+ """);
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 0;", code.print());
+ }
+
+ @Test
+ public void testBug5() {
+ CodeGen code = new CodeGen("""
+struct s0 {
+ int f0;
+};
+if(0) return 0;
+else return new s0;
+if(new s0.f0) return 0;
+ """);
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return s0;", code.print());
+ }
+
+ @Test
+ public void testBug6MissedWorklist() {
+ CodeGen code = new CodeGen("""
+while(0) {}
+int v4=0;
+while(0<arg) {
+ v4=v4+1;
+ while(1) v4=-v4;
+ while(0) arg=-1;
+}
+return 0;
+ """);
+ code.driver(CodeGen.Phase.FinalizeIR);
+ }
+
+ @Test
+ public void testBug7() {
+ CodeGen code = new CodeGen("""
+struct s0 { int f0; };
+s0 v0 = new s0;
+while(v0.f0) {}
+s0 v1 = v0;
+return v1;
+ """);
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return (const)s0;", code.print());
+ }
+
+
+ @Test
+ public void testBug8() {
+ CodeGen code = new CodeGen("""
+int v2=0;
+while(0)
+while(0) {}
+{
+ {
+ {
+ int v36=0;
+ {
+ while(0) {
+ {
+ while(-v2) {
+ {
+ while(v36) {
+ while(v2) return 0;
+ break;
+ } }
+ if(-v2) break;
+ }
+ }
+ }
+ }
+ } }
+}
+return 0;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 0;", code.print());
+ }
+
+ @Test
+ public void testBug9() {
+ CodeGen code = new CodeGen("""
+int v0=arg==0;
+while(v0) continue;
+return 0;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 0;", code.print());
+ }
+
+ @Test public void testReadBeforeStores() {
+ var code = new CodeGen("""
+ struct S { int x; int y; };
+ !S !a = new S; !S !b = new S;
+ a.x = 11; b.x = 22;
+ !S !p = a; if (arg) p = b;
+ int before = p.x;
+ a.y = 55; b.y = 66;
+ a.x = 33; b.x = 44;
+ return before*100 + p.x;
+ """).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ assertEquals("1133",Eval2.eval(code,0));
+ assertEquals("2244",Eval2.eval(code,1));
+ }
+
+ static final String NESTED_MEMORY = """
+ struct S { int x; int y; int z; };
+ !S !s = new S;
+ s.x = 5; s.y = 7; s.z = 11;
+ while (arg > 0) {
+ s.x = s.x + 1;
+ int j = 3;
+ while (j > 0) {
+ j = j - 1;
+ if (j == 1) continue;
+ s.y = s.y + arg;
+ if (arg == 2) break;
+ s.z = s.z + 1;
+ }
+ arg = arg - 1;
+ }
+ return s;
+ """;
+
+ @Test public void testMemoryAcrossNestedLoops() {
+ var code = new CodeGen(NESTED_MEMORY).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ for (int arg=0; arg<7; arg++) {
+ assertEquals("S{x="+(5L+arg)+",y="+(7L+arg*(arg+1)-(arg>=2 ? 2 : 0))+
+ ",z="+(11L+2*arg-(arg>=2 ? 2 : 0))+"}",Eval2.eval(code,arg));
+ }
+ }
+
+ @Test public void testMemoryAtEarlyReturns() {
+ var code = new CodeGen("""
+ struct S { int x; int y; int z; };
+ !S !s = new S;
+ s.x = 3; s.y = 5; s.z = 7;
+ if (arg) { s.x = 11; s.z = 13; return s; }
+ s.y = 17;
+ return s;
+ """).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ for (int arg=0; arg<2; arg++) {
+ assertEquals(arg==0 ? "S{x=3,y=17,z=7}" : "S{x=11,y=5,z=13}",Eval2.eval(code,arg));
+ }
+ }
+
+ @Test public void testKeepLoadsAtMerge() {
+ var code = new CodeGen("""
+ struct S { int x; };
+ !S !a = new S; !S !b = new S;
+ a.x = arg; b.x = arg+1;
+ !S !p = a; !S !q = b;
+ if (arg<0) { p=b; q=a; }
+ int v;
+ if (arg>1) v=p.x; else v=q.x;
+ return v;
+ """).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ // The one-step safety check stops at the memory aggregate.
+ assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+ assertEquals("-1",Eval2.eval(code,-1));
+ assertEquals("1",Eval2.eval(code,0));
+ assertEquals("3",Eval2.eval(code,3));
+ }
+
+ @Test public void testKeepBranchStores() {
+ var code = new CodeGen("""
+ struct S { int x; };
+ !S !s = new S;
+ if (arg) s.x=arg+1; else s.x=arg+2;
+ return s;
+ """).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ // Keep each Store on its own branch.
+ assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet()));
+ assertEquals("S{x=2}",Eval2.eval(code,0));
+ assertEquals("S{x=4}",Eval2.eval(code,3));
+ }
+
+ @Test public void testKeepReadsBeforeWrites() {
+ var code = new CodeGen("""
+ struct S { int x; int y; };
+ !S !a = new S; !S !b = new S;
+ a.x=arg; b.x=arg+1;
+ !S !p=a; !S !q=b;
+ if (arg<0) { p=b; q=a; }
+ int v;
+ if (arg>1) { v=p.x; p.x=41; p.y=5; }
+ else { v=q.x; q.x=42; }
+ return v;
+ """).driver(CodeGen.Phase.FinalizeIR);
+ StopNode stop = code._stop;
+ assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+ assertEquals("-1",Eval2.eval(code,-1));
+ assertEquals("1",Eval2.eval(code,0));
+ assertEquals("3",Eval2.eval(code,3));
+ }
+
+ private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) {
+ if (n==null || seen.get(n._nid)) return 0;
+ seen.set(n._nid);
+ int cnt=kind.isInstance(n) ? 1 : 0;
+ for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen);
+ return cnt;
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-20 12:24:01 +0000