Non-function live-interval computation algorithm

1 files changed, 258 insertions, 0 deletions

diff --git a/vaporize/library/LIRVisitor.java b/vaporize/library/LIRVisitor.java
new file mode 100644
index 0000000..6d5c79f
--- /dev/null
+++ b/vaporize/library/LIRVisitor.java
@@ -0,0 +1,258 @@
+package vaporize.library;
+
+import cs132.vapor.ast.*;
+import graphviz.*;
+import cfg.*;
+import misc.*;
+
+import java.io.File;
+import java.util.*;
+
+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<LIRDict> lirs;
+    private CFGNode curr;                       // the current node being processed
+    private String dot_format;                  // a list of edges to be processed by graphviz
+
+    public LIRVisitor(VaporProgram vp, ArrayList<String> vapor) {
+        this.kettle = new Kettle(vapor);
+        this.lirs = new ArrayList<LIRDict>();
+        this.curr = null;
+
+
+        for (VFunction f : vp.functions) {
+            ControlFlowGraph cfg = new ControlFlowGraph(f);
+            this.dot_format = "";
+
+            MinimalLogger.info(String.format("CFGSimp is collecting nodes for %s",
+                                             this.kettle.parseFuncName(f)));
+            for (VCodeLabel s : f.labels) {
+                cfg.addNode(new CFGNode(s));
+            }
+            for (VInstr s : f.body) {
+                cfg.addNode(new CFGNode(s));
+            }
+
+
+            MinimalLogger.info(String.format("CFGSimp is collecting edges for %s",
+                                             this.kettle.parseFuncName(f)));
+
+            // inital setup
+            // first visit may not find edges; cfg.addEdges will handle
+            this.curr = new CFGNode(f.body[0]);
+            // cascades downwards --- cfg.addEdges
+            for (VVarRef.Local l : f.params)
+                cfg.addReaching(this.curr, l.ident.toString());
+            for (VInstr s : f.body)
+                s.accept(cfg, this);
+
+            MinimalLogger.info(String.format("Spitting out reaching/liveness..."));
+            for (CFGNode n : cfg.getNodes())
+                MinimalLogger.info(String.format("%s ::: %s ::: %s",
+                                                 n.toString(),
+                                                 n.getReaching(),
+                                                 n.getLiveness()));
+
+            if (this.use_graphviz)
+                this.createDotGraph(this.kettle.parseFuncName(f));
+
+            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<LIRDict> getLIRs() {
+        return this.lirs;
+    }
+
+    protected void createDotGraph(String file_name) {
+        MinimalLogger.info(String.format("Outputting %s to %s",
+                                         this.dot_format,
+                                         file_name));
+        GraphViz gv = new GraphViz();
+        gv.addln(gv.start_graph());
+        gv.add(this.dot_format);
+        gv.addln(gv.end_graph());
+        String type = "svg";
+        gv.decreaseDpi();
+        gv.decreaseDpi();
+        gv.decreaseDpi();
+        gv.decreaseDpi();
+        File out = new File(file_name+"."+ type);
+        gv.writeGraphToFile( gv.getGraph( gv.getDotSource(), type ), out );
+    }
+
+    public String visit(ControlFlowGraph cfg, VMemRead n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        cfg.addReaching(curr, n.dest.toString());
+        cfg.addLiveness(curr, ((VMemRef.Global) n.source).base.toString());
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VMemWrite n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        cfg.addLiveness(curr, n.source.toString());
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VAssign n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        cfg.addReaching(curr, n.dest.toString());
+        cfg.addLiveness(curr, n.source.toString());
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VBranch n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.dot_format += cfg.addEdge(curr, cfg.getNode(new Integer(this.kettle
+                                                                     .findLabelIndex(n.target.toString()))));
+
+        cfg.addLiveness(curr, n.value.toString());
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VGoto n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.dot_format += cfg.addEdge(curr,
+                                       cfg.getNode(new Integer(this.kettle
+                                                               .findLabelIndex(n.target.toString()))));
+
+        this.curr = cfg.getNextNode(curr);
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VCall n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        if (n.dest != null)
+            cfg.addReaching(curr, n.dest.toString());
+        for (VOperand a : n.args) {
+            cfg.addLiveness(curr, a.toString());
+        }
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VBuiltIn n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        if (n.dest != null)
+            cfg.addReaching(curr, n.dest.toString());
+        for (VOperand a : n.args) {
+            cfg.addLiveness(curr, a.toString());
+        }
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+    public String visit(ControlFlowGraph cfg, VReturn n) throws RuntimeException {
+        MinimalLogger.info(String.format("->%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        ///////////////////////////////////////////////////////////////
+        CFGNode curr = cfg.getNode(n);
+        this.dot_format += cfg.addEdge(this.curr, curr);
+        this.curr = curr;
+
+        if (n.value != null)
+            cfg.addLiveness(curr, n.value.toString());
+        ///////////////////////////////////////////////////////////////
+        MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
+                                         n.getClass().getSimpleName(),
+                                         this.kettle.get(n).trim(),
+                                         n.sourcePos.toString()));
+        return null;
+    }
+
+}