Chapter 11: Global Code Motionlinear-chapter11

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

1 files changed, 565 insertions, 0 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
new file mode 100644
index 00000000..fdf56b56
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -0,0 +1,565 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Test;
+
+
+import static org.junit.Assert.assertEquals;
+
+public class Chapter11Test {
+
+    // A placeholder test used to rapidly rotate through fuzzer produced issues
+    @Test
+    public void testFuzzer() {
+        Parser parser = new Parser(
+"""
+while(-----arg) {
+    while(-arg) {
+        while(-----arg*---0) {
+                int N=--false==false<--arg;
+                while(N<-4==N) {
+                    N=N+N;
+                }
+            }
+        {
+            int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0);
+            while(kzEl_r7EYz<---1) {
+                kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24;
+                if(7) continue;
+                kzEl_r7EYz=false;
+                if(-kzEl_r7EYz+arg<-3) continue;
+                else {
+                    while(kzEl_r7EYz) continue;
+                    arg=----3;
+                    kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz);
+                    int v2uF_4ba=9;
+                }
+            }
+        }
+        int pjcp7rv=arg;
+        {
+            int m2ya3=--arg-pjcp7rv;
+            while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) {
+                m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true);
+                while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) {
+                    pjcp7rv=-3+-arg;
+                    break;
+                }
+                while(-3) {
+                    while(67+0-61) m2ya3=m2ya3;
+                    if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23;
+                    else pjcp7rv=----89;
+                    while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1;
+                    while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62;
+                }
+                break;
+            }
+        }
+        {
+            int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg);
+            while(arg<-arg) {
+                arg=arg+--arg;
+                {
+                    while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33);
+                    pjcp7rv=11;
+                    int c=pjcp7rv;
+                    if(--107) break;
+                    else break;
+                }
+            }
+        }
+        pjcp7rv=pjcp7rv;
+        int aR0Wkua=-pjcp7rv==pjcp7rv;
+        {
+            if(-0!=-0) while(-true) break;
+            else {
+                while(aR0Wkua) pjcp7rv=-0/pjcp7rv;
+                pjcp7rv=pjcp7rv;
+            }
+        }
+    }
+    if(-arg) {
+        {
+            int Isdlt0fr91=0!=arg;
+            while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) {
+                Isdlt0fr91=Isdlt0fr91+-1!=true;
+                if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91;
+                int i=---arg<---arg!=--40;
+                {
+                    int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0;
+                    while(jVX43Ln4Dm<--(3-3)) {
+                        jVX43Ln4Dm=jVX43Ln4Dm+-0<25;
+                        i=24<--(jVX43Ln4Dm);
+                    }
+                }
+                i=(arg!=----false>=7);
+                int Te=5>-arg;
+                break;
+            }
+        }
+        arg=arg!=--true/arg;
+        {
+            int UX=arg;
+            while(UX<-3*arg) {
+                UX=UX+arg/-1;
+                arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg;
+                if(---12) while(-UX) break;
+                break;
+            }
+        }
+        continue;
+    }
+    if(arg) arg=--0;
+    else if(1) continue;
+    int DtTlhjYq=19==arg;
+    {
+        arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq);
+        if(---arg) continue;
+        else {
+                int Zsl=40;
+                while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) {
+                    Zsl=Zsl+arg;
+                }
+            }
+        if((arg)) if(-DtTlhjYq) {
+            }
+            else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false;
+        else {
+                int lwbF=arg>=0;
+                while(lwbF<57) {
+                    lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg;
+                    arg=----0+0;
+                    while(49) break;
+                    if(true) DtTlhjYq=-----arg;
+                    DtTlhjYq=0!=-----(0);
+                }
+            }
+        arg=---arg!=DtTlhjYq/--0;
+        DtTlhjYq=-DtTlhjYq/(--arg<arg);
+        if(32) {
+                int q=-DtTlhjYq;
+                while(q<arg*(0*q)/0) {
+                    q=q+DtTlhjYq;
+                    DtTlhjYq=arg;
+                }
+            }
+        else if(--arg) if(15) break;
+                else arg=0==arg<=-55>DtTlhjYq;
+            else {
+            }
+        DtTlhjYq=-0;
+        {
+            while((0)<-arg) DtTlhjYq=-DtTlhjYq;
+        }
+        if(30/--(arg)>=0) DtTlhjYq=-0>=arg;
+        else {
+            int Y2wcIQJ=--DtTlhjYq*---11;
+            if(arg==arg) {
+                Y2wcIQJ=-----Y2wcIQJ;
+                Y2wcIQJ=Y2wcIQJ<7;
+                if(DtTlhjYq) arg=arg;
+                else break;
+                while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3;
+            }
+            continue;
+        }
+        arg=DtTlhjYq;
+        arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq;
+        arg=51+---(-true)!=arg!=----1==-DtTlhjYq;
+        if(11<=arg) if((arg)+79<32+(-arg)) continue;
+            else if(true==DtTlhjYq) break;
+        break;
+    }
+}
+if(arg!=62==arg) {
+    while(---arg) {
+        {
+            int bhmDacPM=arg/arg;
+            while(bhmDacPM<arg) {
+                bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7;
+                arg=-0;
+                arg=bhmDacPM>=-arg+-arg;
+                break;
+            }
+        }
+        int arg=true;
+        arg=arg<=arg;
+        {
+            int KlC=30;
+            while(KlC<-2) {
+                KlC=KlC+-1!=25<=-KlC>KlC>----0;
+                int Ij=arg>=-arg<=---10;
+                {
+                    int LAbgurVa2R=-arg!=Ij;
+                    while(LAbgurVa2R<-true) {
+                        LAbgurVa2R=LAbgurVa2R+Ij;
+                        KlC=-LAbgurVa2R;
+                        Ij=42*(-Ij>true);
+                        while(Ij) arg=KlC;
+                        KlC=-----7>-(--KlC<--7)==-LAbgurVa2R;
+                    }
+                }
+                int a=Ij<=-KlC;
+                if(Ij) {
+                    int r1W=a!=-false;
+                }
+                else {
+                    arg=56>=Ij;
+                    while(54) break;
+                    arg=8>=-(a<--Ij)/a>=-a-KlC;
+                }
+                int Yt_T=KlC;
+                arg=KlC;
+            }
+        }
+        if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg;
+            else if(----arg) continue;
+        if(-arg-arg) {
+            arg=-(-arg)*--(-3)<(-7==-arg----arg);
+            {
+                int arg=arg;
+                while(arg<-0>arg==-arg-(-arg>1+11)) {
+                    arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg;
+                }
+            }
+            arg=-arg+arg;
+            arg=--47+-arg<1>arg*(-arg==-arg--0>3);
+            arg=(----arg)!=arg+--59;
+            arg=--4+arg==-(arg)-arg;
+        }
+        else {
+            while(--true-----true*-25+-18>arg>=-----(-arg)---13) {
+                arg=-0+--true<false;
+                continue;
+            }
+            arg=true<=arg;
+            break;
+        }
+        arg=arg*22<--(0+-arg);
+        {
+            continue;
+        }
+    }
+    arg=1*---((3<=true)==---2);
+    arg=7+-(-1);
+    return arg+--true;
+}
+else {
+    int o3ypEsewxM=-(---arg);
+    int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg;
+    int L=-arg;
+    int B4mHcrf=---vzXB;
+    int oZWGdzZl=-o3ypEsewxM;
+    int K6tQqa1=11;
+    while(0!=--L) {
+            int sdZfTM=vzXB*true+K6tQqa1;
+            while(sdZfTM<false) {
+                sdZfTM=sdZfTM+arg;
+                sdZfTM=oZWGdzZl;
+                K6tQqa1=-K6tQqa1;
+                arg=---K6tQqa1;
+                while((3+-K6tQqa1)<oZWGdzZl) {
+                    if(-----(-1)) sdZfTM=-false;
+                    {}
+                }
+                K6tQqa1=vzXB!=-(B4mHcrf+-7>false);
+                sdZfTM=vzXB;
+            }
+        }
+    L=false;
+    while(31) B4mHcrf=arg;
+    oZWGdzZl=-0<--oZWGdzZl<=--2;
+    if(K6tQqa1>=20<=46) {
+        if(-1+-L) if(oZWGdzZl) {
+                int wmhv=-----0;
+            }
+        int arg=0;
+        o3ypEsewxM=---(oZWGdzZl);
+        return -oZWGdzZl/0;
+    }
+    else if(arg) {
+            int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM;
+            return -K6tQqa1;
+        }
+        else {
+            if(---0) {
+                {}
+                {}
+            }
+            return o3ypEsewxM;
+        }
+}
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString());
+    }
+
+
+    @Test
+    public void testPrimes() {
+        Parser parser = new Parser(
+"""
+if( arg < 2 ) return 0;
+int primeCount = 1;
+int prime = 3;
+while( prime <= arg ) {
+    int isPrime = 1;
+    // Check for even case, so the next loop need only check odds
+    if( (prime/2)*2 == prime )
+        continue;
+    // Check odds up to sqrt of prime
+    int j = 3;
+    while( j*j <= prime ) {
+        if( (prime/j)*j == prime ) {
+            isPrime = 0;
+            break;
+        }
+        j = j + 2;
+    }
+    if( isPrime )
+        primeCount = primeCount + 1;
+    prime = prime + 2;
+}
+return primeCount;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("Stop[ return 0; return Phi(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  1)); // No primes 1 or below
+        assertEquals(1L, Evaluator.evaluate(stop,  2)); // 2
+        assertEquals(2L, Evaluator.evaluate(stop,  3)); // 2, 3
+        assertEquals(2L, Evaluator.evaluate(stop,  4)); // 2, 3
+        assertEquals(3L, Evaluator.evaluate(stop,  5)); // 2, 3, 5
+        assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7
+    }
+
+    @Test
+    public void testAntiDeps1() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v=new S;
+v.f = 2;
+int i=new S.f;
+i=v.f;
+if (arg) v.f=1;
+return i;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return .f;", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps2() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = 0;
+if (arg) {
+    if (arg+1) v = t;
+    i = v.f;
+} else {
+    v.f = 2;
+}
+return i;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region31,.f,0);", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps3() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v0 = new S;
+S? v1;
+if (arg) v1 = new S;
+if (v1) {
+    v0.f = v1.f;
+} else {
+    v0.f = 2;
+}
+return v0;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return new S;", stop.toString());
+    }
+
+
+    @Test
+    public void testAntiDeps4() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = v.f;
+if (arg+1) arg= 0;
+while (arg) v.f = 2;
+return i;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return .f;", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps5() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+while(1) {
+    while(arg+1) { arg=arg-1; }
+    if (arg) break;
+    v.f = 2;
+}
+return v;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return new S;", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps6() {
+        Parser parser = new Parser(
+"""
+struct s { int v; }
+s ptr=new s;
+while( -arg )
+  ptr = new s;
+while(1)
+  arg = arg+ptr.v;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps7() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+int i = v.f;
+while (arg) {
+    v.f = arg;
+    arg = arg-1;
+}
+return i;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return .f;", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps8() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+while(arg) {
+    arg=arg-1;
+    int f = v.f;
+    v.f = 2;
+    if (arg) arg = f;
+    else v.f = 3;
+}
+return arg;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop13,arg,Phi(Region35,.f,0));", stop.toString());
+    }
+
+    @Test
+    public void testAntiDeps9() {
+        Parser parser = new Parser(
+"""
+struct S { int f; }
+S v = new S;
+S t = new S;
+if (arg) {
+    v.f=2;
+    int i=t.f;
+    v.f=i;
+}
+return v;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return new S;", stop.toString());
+    }
+
+    @Test
+    public void testExample2() {
+        Parser parser = new Parser(
+                                   """
+struct S { int f; }
+S v = new S;
+int i = arg;
+while (arg > 0) {
+    int j = i/3;
+    if (arg == 5)
+        v.f = j;
+    arg = arg - 1;
+}
+return v;
+""");
+        StopNode stop = parser.parse().iterate();
+        //assertEquals("return new S;", stop.toString());
+    }
+
+    @Test
+    public void testSplit() {
+        Parser parser = new Parser(
+                                   """
+struct S { int f; }
+S s = new S;
+if( arg==0 ) s.f = 1;
+else if (arg == 1) s.f = 1;
+return s.f;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region35,1,Phi(Region33,1,0));", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop,  0));
+        assertEquals(1L, Evaluator.evaluate(stop,  1));
+        assertEquals(0L, Evaluator.evaluate(stop,  2));
+    }
+
+    @Test
+    public void testScheduleUse() {
+        Parser parser = new Parser(
+"""
+int v0=0;
+while(0>=0) {
+    int v1=0;
+    v1=v0;
+    if(v1*0)
+        v0=-v1;
+}
+return 0;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
+    }
+
+    @Test
+    public void testLoopCarriedDep() {
+        Parser parser = new Parser(
+"""
+int v0=0;
+{
+    int v1=0;
+    while(v1) {
+        v1=1+(v0!=0);
+        v0=v1/0;
+    }
+}
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
+    }
+}