Non-function live-interval computation algorithm

5 files changed, 167 insertions, 41 deletions

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;
+    }
+
+}