Chapter 13: Referenceslinear-chapter13

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

8 files changed, 41 insertions, 22 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java
index fec540f7..fbf0e518 100644
--- a/src/main/java/com/seaofnodes/simple/node/CastNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java
@@ -22,6 +22,9 @@ public class CastNode extends Node {
     public String uniqueName() { return "Cast_" + _nid; }
 
     @Override
+    public boolean isPinned() { return true; }
+
+    @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return in(1)._print0(sb.append(label()), visited);
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index cf1a76b0..016b0b9b 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -32,7 +32,7 @@ public class ConstantNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return _con._print(sb);
+        return _con.print(sb);
     }
 
     @Override public boolean isMultiTail() { return true; }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 244a0919..a033a7cf 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.Field;
 
 import java.util.BitSet;
 
@@ -12,7 +11,6 @@ import java.util.BitSet;
  */
 public class LoadNode extends MemOpNode {
 
-    Type _declaredType;
     /**
      * Load a value from a ptr.field.
      *
@@ -21,15 +19,11 @@ public class LoadNode extends MemOpNode {
      * @param memPtr The ptr to the struct from where we load a field
      */
     public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
-        super(name, alias, null, memSlice, memPtr);
-        _declaredType = glb;
+        super(name, alias, glb, null, memSlice, memPtr);
     }
 
-    @Override
-    public String label() { return "Load"; }
-
-    @Override
-    public String glabel() { return "."+_name; }
+    @Override public String  label() { return     _name; }
+    @Override public String glabel() { return "."+_name; }
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); }
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 551d2aa9..95319c24 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node {
 
     public final String _name;
     public final int _alias;
+    public final Type _declaredType;
 
-    public MemOpNode(String name, int alias, Node... nodes) {
+
+    public MemOpNode(String name, int alias, Type glb, Node... nodes ) {
         super(nodes);
         _name  = name;
         _alias = alias;
+        _declaredType = glb;
     }
 
     public Node mem() { return in(1); }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 52282737..d846fcef 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -137,7 +137,7 @@ public abstract class Node implements OutNode {
 
     public boolean isUnused() { return nOuts() == 0; }
 
-    public CFGNode cfg0() { return (CFGNode)in(0); }
+   public CFGNode cfg0() { return (CFGNode)in(0); }
 
     /**
      * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index ab567bae..0eacc1f4 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.GlobalCodeMotion;
+import com.seaofnodes.simple.GraphVisualizer;
 
 import java.util.BitSet;
 
@@ -67,13 +69,21 @@ public class StopNode extends CFGNode {
         return addDef(node);
     }
 
-    public StopNode iterate(            ) { return IterPeeps.iterate(this,false).typeCheck(); }
-    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ).typeCheck(); }
+    public StopNode iterate(            ) { return IterPeeps.iterate(this).typeCheck().GCM(false); }
+    public StopNode iterate(boolean show) { return IterPeeps.iterate(this).typeCheck().GCM(show ); }
     StopNode typeCheck() {
         String err = walk( Node::err );
         if( err != null ) throw new RuntimeException(err);
         return this;
     }
+    StopNode GCM(boolean show) {
+        // Break infinite loops, forcing a Never-branch to exit
+        GlobalCodeMotion.fixLoops(this);
+        if( show )
+            System.out.println(new GraphVisualizer().generateDotOutput(this,null,null));
+        GlobalCodeMotion.buildCFG(this);
+        return this;
+    }
 
     @Override public Node getBlockStart() { return this; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index db8e2ce6..57e8b3ad 100644
--- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -11,22 +11,23 @@ import java.util.BitSet;
  */
 public class StoreNode extends MemOpNode {
 
+    private final boolean _init; // Initializing writes are allowed to write null
+
     /**
      * @param name The struct field we are assigning to
      * @param memSlice The memory alias node - this is updated after a Store
      * @param memPtr The ptr to the struct where we will store a value
      * @param value Value to be stored
      */
-    public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) {
-        super(name, alias, ctrl, memSlice, memPtr, value);
+    public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) {
+        super(name, alias, glb, ctrl, memSlice, memPtr, value);
+        _init = init;
     }
 
-    @Override
-    public String label() { return "Store"; }
-    @Override
-    public String glabel() { return "."+_name+" ="; }
-    @Override
-    public boolean isMem() { return true; }
+    @Override public String  label() { return "." +_name+"="; }
+    @Override public String glabel() { return "." +_name+"="; }
+    @Override public boolean isMem() { return true; }
+
     public Node val() { return in(3); }
 
     @Override
@@ -67,4 +68,11 @@ public class StoreNode extends MemOpNode {
         return false;
     }
 
+    @Override
+    String err() {
+        String err = super.err();
+        if( err != null ) return err;
+        Type ptr = val()._type;
+        return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index f0c77743..81cc6076 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -37,6 +37,7 @@ public class SubNode extends Node {
 
     @Override
     public Node idealize() {
+
         // x - (-y) is x+y
         if( in(2) instanceof MinusNode minus )
             return new AddNode(in(1),minus.in(1));