Non-function live-interval computation algorithm

10 files changed, 191 insertions, 52 deletions

diff --git a/V2VM.java b/V2VM.java
index 3d181dd..f34f5fd 100644
--- a/V2VM.java
+++ b/V2VM.java
@@ -31,8 +31,8 @@ public class V2VM {
             VaporProgram prog = parseVapor(System.in, System.out);
 
             MinimalLogger.info(String.format("Generating CFGs..."));
-            CFGSimp cfv = new CFGSimp(prog, strProg);
-            ArrayList<ControlFlowGraph> cfgs = cfv.getCFGs();
+            LIRVisitor lv = new LIRVisitor(prog, strProg);
+            ArrayList<LIRDict> lvs = lv.getLIRs();
             // MinimalLogger.info(String.format("Spilling Everywhere..."));
             // SpillEverywhere spill = new SpillEverywhere(prog, strProg);
 
diff --git a/cfg/CFGNode.java b/cfg/CFGNode.java
index e604753..5ce39b5 100644
--- a/cfg/CFGNode.java
+++ b/cfg/CFGNode.java
@@ -21,7 +21,7 @@ public class CFGNode {
         this.liveness = new HashSet<>();
     }
 
-    public String toString() {
+    @Override public String toString() {
         return String.format("L%d",
                              this.instruction.sourcePos.line);
     }
diff --git a/st/AbstractInstance.java b/st/AbstractInstance.java
index ddf7156..4e4287d 100644
--- a/st/AbstractInstance.java
+++ b/st/AbstractInstance.java
@@ -14,16 +14,16 @@ public abstract class AbstractInstance {
         this.scope = new ArrayList<>();
     }
 
-    public String toString() {
+    @Override public String toString() {
         return this.name;
     }
 
-    public boolean equals(AbstractInstance other) {
+    @Override public boolean equals(AbstractInstance other) {
         return this.name == other.getName() &&
             this.type == this.type;
     }
 
-    public int hashCode() {
+    @Override public int hashCode() {
         return this.name.hashCode();
     }
 
diff --git a/st/SymbolTable.java b/st/SymbolTable.java
index de45a58..e3dd398 100644
--- a/st/SymbolTable.java
+++ b/st/SymbolTable.java
@@ -16,7 +16,7 @@ public class SymbolTable {
         this.active = new HashMap<>();
     }
 
-    public String toString() {
+    @Override public String toString() {
         StringBuilder mapAsString = new StringBuilder("{");
         for (String key : this.symt.keySet()) {
             mapAsString.append(key + ":" + this.symt.get(key).getType() + ", ");
diff --git a/vaporize/library/LIRDict.java b/vaporize/library/LIRDict.java
new file mode 100644
index 0000000..b32647c
--- /dev/null
+++ b/vaporize/library/LIRDict.java
@@ -0,0 +1,49 @@
+package vaporize.library;
+
+import misc.*;
+import cfg.*;
+import java.util.*;
+
+public class LIRDict {
+
+    private TreeSet<LIRVar> intervals;
+
+    public LIRDict(ControlFlowGraph cfg) {
+        this.intervals = new TreeSet<LIRVar>();
+
+        for (CFGNode n : cfg.getNodes()) {
+            int line = n.getInstruction().sourcePos.line;
+
+            for (String var : n.getReaching())
+                if (!this.contains(var))
+                    this.intervals.add(new LIRVar(var, line, line));
+            for (String var : n.getLiveness()) {
+                if (!this.contains(var))
+                    MinimalLogger.severe(String.format("%s was used before defined!",
+                                                       var));
+                this.getInterval(var).trySetLastUse(line);
+            }
+        }
+    }
+
+    public LIRVar getInterval(String s) {
+        LIRVar ret = null;
+        for (LIRVar v : this.intervals) {
+            if (v.equals(s)) {
+                ret = v;
+                break;
+            }
+        }
+
+        return ret;
+    }
+
+    public boolean contains(String s) {
+        return this.getInterval(s) != null;
+    }
+
+    public SortedSet<LIRVar> getIntervals() {
+        return Collections.unmodifiableSortedSet(this.intervals);
+    }
+
+}
diff --git a/vaporize/library/LIRVar.java b/vaporize/library/LIRVar.java
new file mode 100644
index 0000000..4fab8c8
--- /dev/null
+++ b/vaporize/library/LIRVar.java
@@ -0,0 +1,64 @@
+package vaporize.library;
+
+import misc.*;
+
+public class LIRVar implements Comparable<LIRVar> {
+
+    private String alias;
+    private TransientInterval interval;
+
+    private String register;
+
+    public LIRVar(String alias, int fd, int lu) {
+        this.alias = alias;
+        this.interval = new TransientInterval(fd, lu);
+        this.register = null;
+    }
+
+    @Override public String toString() {
+        return String.format("%s: %d -> %d",
+                             this.alias,
+                             this.interval.first_def,
+                             this.interval.last_use);
+    }
+
+    @Override public boolean equals(Object other) {
+        LIRVar o;
+        return (other instanceof LIRVar &&
+                ((o = (LIRVar) other)).alias.equals(this.alias) &&
+                o.interval.equals(this.interval)) ||
+            (other instanceof String &&
+             this.alias.equals((String) other));
+    }
+
+    @Override public int hashCode() {
+        return alias.hashCode();
+    }
+
+    @Override public int compareTo(LIRVar other) {
+        int ret;
+        if (this.interval.first_def > other.interval.first_def)
+            ret = 1;
+        else if (this.interval.first_def < other.interval.first_def)
+            ret = -1;
+        else
+            ret = 0;
+        return ret;
+    }
+
+    protected boolean trySetLastUse(int last_use) {
+        /**
+         * If the passed last_use is greater than
+         * the this.last_use, override this.last_use.
+         */
+        boolean ret = last_use > this.interval.last_use;
+
+        if (ret)
+            this.interval.last_use = last_use;
+        return ret;
+    }
+
+    public void assignRegister(String register) {
+        this.register = register;
+    }
+}
diff --git a/vaporize/library/CFGSimp.java b/vaporize/library/LIRVisitor.java
index 30ddc7d..6d5c79f 100644
--- a/vaporize/library/CFGSimp.java
+++ b/vaporize/library/LIRVisitor.java
@@ -8,18 +8,18 @@ import misc.*;
 import java.io.File;
 import java.util.*;
 
-public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeException> {
+public class LIRVisitor extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeException> {
 
     private boolean use_graphviz = true;        // if true, generates svg files of the edges in each function
 
     private Kettle kettle;
-    private ArrayList<ControlFlowGraph> cfgs;
+    private ArrayList<LIRDict> lirs;
     private CFGNode curr;                       // the current node being processed
     private String dot_format;                  // a list of edges to be processed by graphviz
 
-    public CFGSimp(VaporProgram vp, ArrayList<String> vapor) {
+    public LIRVisitor(VaporProgram vp, ArrayList<String> vapor) {
         this.kettle = new Kettle(vapor);
-        this.cfgs = new ArrayList<ControlFlowGraph>();
+        this.lirs = new ArrayList<LIRDict>();
         this.curr = null;
 
 
@@ -59,12 +59,17 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
             if (this.use_graphviz)
                 this.createDotGraph(this.kettle.parseFuncName(f));
 
-            this.cfgs.add(cfg);
+            MinimalLogger.info(String.format("Gathering intervals for %s",
+                                             this.kettle.parseFuncName(f)));
+            LIRDict lir = new LIRDict(cfg);
+            this.lirs.add(lir);
+            MinimalLogger.info(String.format("Found intervals: %s",
+                                             lir.getIntervals().toString()));
         }
     }
 
-    public ArrayList<ControlFlowGraph> getCFGs() {
-        return this.cfgs;
+    public ArrayList<LIRDict> getLIRs() {
+        return this.lirs;
     }
 
     protected void createDotGraph(String file_name) {
diff --git a/vaporize/library/SpillEverywhere.java b/vaporize/library/SpillEverywhere.java
index d6671bf..993bfa6 100644
--- a/vaporize/library/SpillEverywhere.java
+++ b/vaporize/library/SpillEverywhere.java
@@ -9,96 +9,82 @@ public class SpillEverywhere extends VInstr.VisitorPR<String, String, RuntimeExc
 
     private VaporProgram vp;
     private Kettle kettle;
-    private String vaporm;
-
-    // public CFGSimp(VaporProgram v) {
-
-    //     // nodes
-    //     for (VInstr s : n.body)
-    //         this.cfg.addNode(new CFGNode(s));
-
-    //     // edges
-    //     for (VInstr s : n.body)
-    //         s.accept("", this);
-
-    //     System.out.println(this.cfg.getNodes().toString());
-    // }
 
     public SpillEverywhere(VaporProgram vp, ArrayList<String> vapor) {
         this.vp = vp;
         this.kettle = new Kettle(vapor);
-        this.vaporm = "";
 
-        for (VFunction f : vp.functions) {
+        for (VFunction f : this.vp.functions) {
+            MinimalLogger.severe("Num : " + Arrays.toString(f.vars));
+            this.kettle.replaceFunctionDeclare(f, 0, 0, 3); // use three registers for "spill everywhere"
             for (VInstr s : f.body) {
                 s.accept("", this);
             }
-            this.kettle.replaceFunctionDeclare(f, 0, 0, 0);
         }
         MinimalLogger.info(kettle.dump());
     }
 
+
     public String visit(String p, VMemRead n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VMemWrite n) throws RuntimeException {
-        System.out.println("HEY!");
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VAssign n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VBranch n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VGoto n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VCall n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VBuiltIn n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.op.name,
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
 
     public String visit(String p, VReturn n) throws RuntimeException {
-        MinimalLogger.info(String.format("%s (%s:%s)",
+        MinimalLogger.info(String.format("->%s (%s:%s)",
                                          n.getClass().getSimpleName(),
-                                         this.kettle.get(n),
+                                         this.kettle.get(n).trim(),
                                          n.sourcePos.toString()));
         return null;
     }
diff --git a/vaporize/library/TransientInterval.java b/vaporize/library/TransientInterval.java
new file mode 100644
index 0000000..f72f2bc
--- /dev/null
+++ b/vaporize/library/TransientInterval.java
@@ -0,0 +1,22 @@
+package vaporize.library;
+
+import misc.*;
+
+class TransientInterval {
+
+    protected int first_def;
+    protected int last_use;
+
+    protected TransientInterval(int first_def, int last_use) {
+        this.first_def = first_def;
+        this.last_use = last_use;
+    }
+
+    @Override public boolean equals(Object other) {
+        TransientInterval o;
+        return (other instanceof TransientInterval) &&
+            (((o = (TransientInterval) other)).first_def == this.first_def) &&
+            o.last_use == this.last_use;
+    }
+
+}
diff --git a/vaporize/tests/ex32.vaporm b/vaporize/tests/ex32.vaporm
index 85ecf13..7ef23aa 100644
--- a/vaporize/tests/ex32.vaporm
+++ b/vaporize/tests/ex32.vaporm
@@ -1,6 +1,12 @@
-func Main [in 0, out 0, local 0]
-  $t0 = HeapAllocZ(4)
-  [$t0] = :functable_A
+func Main [in 0, out 0, local 4]
+  local[0] = $s0
+  local[1] = $s1
+  local[2] = $s2
+  $s0 = HeapAllocZ(4)
+  local[3] = $s0
+  $s0 = local[3]
+  [$s0] = :functable_A
+  $local[4] = $s0
   $t1 = [$t0]
   $t2 = [$t1]
   $a0 = $t0
@@ -8,15 +14,22 @@ func Main [in 0, out 0, local 0]
   call $t2
   $t1 = $v0
   PrintIntS($t1)
+  $s0 = local[0]
+  $s1 = local[1]
+  $s2 = local[2]
   ret
 
 const functable_A
    :A_foo
 
-func A_foo [in 0, out 0, local 1]
+func A_foo [in 0, out 0, local 6]
   local[0] = $s0
+  local[1] = $s1
+  local[2] = $s2
   $t0 = $a0
   $s0 = $a1
   $v0 = $s0
   $s0 = local[0]
+  $s1 = local[1]
+  $s2 = local[2]
   ret