Implement liveness tracking in CFG

2 files changed, 25 insertions, 5 deletions

diff --git a/vaporize/library/CFGNode.java b/vaporize/library/CFGNode.java
index aefcd28..b23ca00 100644
--- a/vaporize/library/CFGNode.java
+++ b/vaporize/library/CFGNode.java
@@ -12,7 +12,7 @@ class CFGNode {
     private ArrayList<CFGNode> sources;
     private ArrayList<CFGNode> dests;
     private HashSet<String> reaching;
-    private ArrayList<String> liveness;
+    private HashSet<String> liveness;
     private int line;
 
     protected CFGNode(Node instruction) {
@@ -20,6 +20,7 @@ class CFGNode {
         this.sources = new ArrayList<>();
         this.dests = new ArrayList<>();
         this.reaching = new HashSet<>();
+        this.liveness = new HashSet<>();
         this.line = this.instruction.sourcePos.line;
     }
 
@@ -59,7 +60,7 @@ class CFGNode {
         this.reaching.add(add);
     }
 
-    protected void addLive(String add) {
+    protected void addLiveness(String add) {
         MinimalLogger.info(String.format("Use %s at %s",
                                          add,
                                          this.line));
diff --git a/vaporize/library/CFGSimp.java b/vaporize/library/CFGSimp.java
index 6aaf0d1..76d5acd 100644
--- a/vaporize/library/CFGSimp.java
+++ b/vaporize/library/CFGSimp.java
@@ -57,11 +57,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..."));
+            MinimalLogger.info(String.format("Spitting out reaching/liveness..."));
             for (CFGNode n : cfg.getNodes())
-                MinimalLogger.info(String.format("%d ::: %s",
+                MinimalLogger.info(String.format("%d ::: %s ::: %s",
                                                  n.getLine(),
-                                                 n.getReaching()));
+                                                 n.getReaching(),
+                                                 n.getLiveness()));
 
             if (this.use_graphviz)
                 this.createDotGraph(this.kettle.parseFuncName(f));
@@ -102,6 +103,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         this.curr = curr;
 
         curr.addReaching(n.dest.toString());
+        if (!n.source.toString().matches("-?(0|[1-9]\\d*)"))
+            curr.addLiveness(((VMemRef.Global) n.source).base.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -119,6 +122,10 @@ 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.source.toString().matches("-?(0|[1-9]\\d*)"))
+            curr.addLiveness(n.source.toString());
+
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -138,6 +145,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
         this.curr = curr;
 
         curr.addReaching(n.dest.toString());
+        if (!n.source.toString().matches("-?(0|[1-9]\\d*)"))
+            curr.addLiveness(n.source.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -158,6 +167,7 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
                                                                      .findLabelIndex(n.target.toString()))));
 
         this.curr = curr;
+        curr.addLiveness(n.value.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -199,6 +209,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
 
         if (n.dest != null)
             curr.addReaching(n.dest.toString());
+        for (VOperand a : n.args)
+            if (!a.toString().matches("-?(0|[1-9]\\d*)"))
+                curr.addLiveness(a.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -219,6 +232,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
 
         if (n.dest != null)
             curr.addReaching(n.dest.toString());
+        for (VOperand a : n.args)
+            if (!a.toString().matches("-?(0|[1-9]\\d*)"))
+                curr.addLiveness(a.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),
@@ -236,6 +252,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.value != null)
+            curr.addLiveness(n.value.toString());
         ///////////////////////////////////////////////////////////////
         MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
                                          n.getClass().getSimpleName(),