Implement partial reachable tracking in CFG

3 files changed, 41 insertions, 7 deletions

diff --git a/vaporize/library/CFGNode.java b/vaporize/library/CFGNode.java
index b79ee6b..9d627a0 100644
--- a/vaporize/library/CFGNode.java
+++ b/vaporize/library/CFGNode.java
@@ -4,18 +4,22 @@ import misc.*;
 import cs132.vapor.ast.*;
 
 import java.util.ArrayList;
+import java.util.HashSet;
 
 class CFGNode {
 
     private Node instruction;
     private ArrayList<CFGNode> sources;
     private ArrayList<CFGNode> dests;
+    private HashSet<String> reaching;
+    private ArrayList<String> liveness;
     private int line;
 
     protected CFGNode(Node instruction) {
         this.instruction = instruction;
         this.sources = new ArrayList<>();
         this.dests = new ArrayList<>();
+        this.reaching = new HashSet<>();
         this.line = this.instruction.sourcePos.line;
     }
 
@@ -23,10 +27,6 @@ class CFGNode {
         return this.instruction.toString();
     }
 
-    public int hashCode() {
-        return this.line;
-    }
-
     /**
      * For if we only have a line
      * number. (VBranch issues)
@@ -52,6 +52,13 @@ class CFGNode {
         this.dests.add(node);
     }
 
+    protected void addReaching(String add) {
+        MinimalLogger.info(String.format("Def %s at %s",
+                                         add,
+                                         this.line));
+        this.reaching.add(add);
+    }
+
     protected Node getInstruction() {
         return this.instruction;
     }
@@ -64,4 +71,13 @@ class CFGNode {
         return this.dests;
     }
 
+    protected HashSet<String> getReaching() {
+        return this.reaching;
+    }
+
+    protected int getLine() {
+        return this.line;
+    }
+
+
 }
diff --git a/vaporize/library/CFGSimp.java b/vaporize/library/CFGSimp.java
index f85c198..4456d39 100644
--- a/vaporize/library/CFGSimp.java
+++ b/vaporize/library/CFGSimp.java
@@ -52,6 +52,12 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
             for (VInstr s : f.body)
                 s.accept(cfg, this);
 
+            MinimalLogger.info(String.format("Spitting out reaching..."));
+            for (CFGNode n : cfg.getNodes())
+                MinimalLogger.info(String.format("%d ::: %s",
+                                                 n.getLine(),
+                                                 n.getReaching()));
+
             if (this.use_graphviz)
                 this.createDotGraph(this.kettle.parseFuncName(f));
 
@@ -89,6 +95,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         CFGNode curr = cfg.getNode(n);
         this.dot_format += cfg.addEdge(this.curr, curr);
         this.curr = curr;
+
+        curr.addReaching(n.dest.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -123,6 +131,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         CFGNode curr = cfg.getNode(n);
         this.dot_format += cfg.addEdge(this.curr, curr);
         this.curr = curr;
+
+        curr.addReaching(n.dest.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -163,8 +173,6 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
                                        cfg.getNode(new Integer(this.kettle
                                                                .findLabelIndex(n.target.toString()))));
 
-        MinimalLogger.info(String.format("curr is now %s",
-                                         this.kettle.get(n).trim()));
         this.curr = cfg.getNextNode(curr);
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
@@ -183,6 +191,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         CFGNode curr = cfg.getNode(n);
         this.dot_format += cfg.addEdge(this.curr, curr);
         this.curr = curr;
+
+        if (n.dest != null)
+            curr.addReaching(n.dest.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -200,6 +211,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         CFGNode curr = cfg.getNode(n);
         this.dot_format += cfg.addEdge(this.curr, curr);
         this.curr = curr;
+
+        if (n.dest != null)
+            curr.addReaching(n.dest.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
diff --git a/vaporize/library/ControlFlowGraph.java b/vaporize/library/ControlFlowGraph.java
index 2a8caef..1e24dd6 100644
--- a/vaporize/library/ControlFlowGraph.java
+++ b/vaporize/library/ControlFlowGraph.java
@@ -44,7 +44,7 @@ public class ControlFlowGraph {
         }
 
         if (ret == null)
-            MinimalLogger.severe(String.format("Could not find a node matching %s",
+            MinimalLogger.severe(String.format("Could not find the next node for %s",
                                                a.toString()));
 
         return ret;
@@ -58,6 +58,8 @@ public class ControlFlowGraph {
     protected String addEdge(CFGNode source, CFGNode dest) {
         /**
          * Iff the CFGNodes are different, construct an edge between them.
+         * All variables reaching the parent also reach the children.
+         *
          * Returns a string capable of being manipulated by graphviz.
          */
         String ret = "";
@@ -70,6 +72,8 @@ public class ControlFlowGraph {
 
             source.addDest(dest);
             dest.addSource(source);
+
+            dest.getReaching().addAll(source.getReaching());
             ret += ";";
         } else {
             MinimalLogger.info(String.format("Skipping duplicate edge for %d",