CFG Class cleanup/reordering

2 files changed, 198 insertions, 0 deletions

diff --git a/cfg/CFGNode.java b/cfg/CFGNode.java
new file mode 100644
index 0000000..e604753
--- /dev/null
+++ b/cfg/CFGNode.java
@@ -0,0 +1,73 @@
+package cfg;
+
+import misc.*;
+import cs132.vapor.ast.*;
+
+import java.util.*;
+
+public class CFGNode {
+
+    private Node instruction;
+    private ArrayList<CFGNode> sources;
+    private ArrayList<CFGNode> dests;
+    protected Set<String> reaching;
+    protected Set<String> liveness;
+
+    public CFGNode(Node instruction) {
+        this.instruction = instruction;
+        this.sources = new ArrayList<>();
+        this.dests = new ArrayList<>();
+        this.reaching = new HashSet<>();
+        this.liveness = new HashSet<>();
+    }
+
+    public String toString() {
+        return String.format("L%d",
+                             this.instruction.sourcePos.line);
+    }
+
+    /**
+     * For if we only have a line
+     * number. (VBranch issues)
+     */
+    public boolean equals(Object other) {
+        return (other instanceof CFGNode &&
+                (((CFGNode) other).instruction ==
+                 this.instruction)) ||
+            (other instanceof Node &&
+             (((Node) other).sourcePos ==
+              this.instruction.sourcePos)) ||
+            (other instanceof Integer &&
+             (((Integer) other)
+              .equals(this.instruction.sourcePos.line)));
+    }
+
+    protected void addSource(CFGNode node) {
+        this.sources.add(node);
+    }
+
+    protected void addDest(CFGNode node) {
+        this.dests.add(node);
+    }
+
+    public Node getInstruction() {
+        return this.instruction;
+    }
+
+    public List<CFGNode> getSources() {
+        return Collections.unmodifiableList(this.sources);
+    }
+
+    public List<CFGNode> getDests() {
+        return Collections.unmodifiableList(this.dests);
+    }
+
+    public Set<String> getReaching() {
+        return Collections.unmodifiableSet(this.reaching);
+    }
+
+    public Set<String> getLiveness() {
+        return Collections.unmodifiableSet(this.liveness);
+    }
+
+}
diff --git a/cfg/ControlFlowGraph.java b/cfg/ControlFlowGraph.java
new file mode 100644
index 0000000..c8a7f16
--- /dev/null
+++ b/cfg/ControlFlowGraph.java
@@ -0,0 +1,125 @@
+package cfg;
+
+import cs132.vapor.ast.*;
+import misc.*;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+
+public class ControlFlowGraph {
+
+    private VFunction f;                // the function represented by this CFG
+    private ArrayList<CFGNode> nodes;
+
+    public ControlFlowGraph(VFunction f) {
+        this.f = f;
+        this.nodes = new ArrayList<>();
+    }
+
+    public CFGNode getNode(Object a) {
+        CFGNode ret = null;
+        for (CFGNode n : this.nodes) {
+            if (n.equals(a)) {
+                ret = n;
+                break;
+            }
+        }
+
+        if (ret == null) {
+            String str = (a instanceof Node) ? ((Node) a).sourcePos.toString() :
+                a.toString();
+            MinimalLogger.severe(String.format("Could not find a node matching %s",
+                                               str));
+        }
+        return ret;
+    }
+
+    public CFGNode getNextNode(CFGNode a) {
+        CFGNode ret = null;
+        // we return null if the passed node is the last in the list
+        for (int i = 0; i < this.nodes.size()-1; ++i) {
+            if (this.nodes.get(i).equals(a)) {
+                ret = this.nodes.get(i+1);
+                break;
+            }
+        }
+
+        if (ret == null)
+            MinimalLogger.severe(String.format("Could not find the next node for %s",
+                                               a.toString()));
+
+        return ret;
+
+    }
+
+    public void addNode(CFGNode n) {
+        MinimalLogger.info(String.format("Node + %s",
+                                         n.toString()));
+        this.nodes.add(n);
+    }
+
+    public 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 = "";
+        if (!source.equals(dest)) {
+            ret = String.format("%s -> %s",
+                                source.toString(),
+                                dest.toString());
+            MinimalLogger.info(String.format("Edge %s",
+                                             ret));
+
+            source.addDest(dest);
+            dest.addSource(source);
+
+            ret += ";";
+        } else {
+            MinimalLogger.info(String.format("Skipping duplicate edge for %s",
+                                             source.toString()));
+        }
+
+        MinimalLogger.info(String.format("Spilling variables: %s",
+                                         source.getReaching().toString()));
+        dest.reaching.addAll(source.reaching);
+
+        return ret;
+    }
+
+    public void addReaching(CFGNode n, String s) {
+        MinimalLogger.info(String.format("Def \"%s\" at %s",
+                                         s,
+                                         n.toString()));
+        n.reaching.add(s);
+    }
+
+    public void addLiveness(CFGNode n, String s) {
+        if (this.isKnownVar(s)) {
+            MinimalLogger.info(String.format("Use \"%s\" at %s",
+                                             s,
+                                             n.toString()));
+            n.liveness.add(s);
+        } else
+            MinimalLogger.info(String.format("Use \"%s\" not a known variable!",
+                                             s));
+    }
+
+    public ArrayList<CFGNode> getNodes() {
+        return this.nodes;
+    }
+
+    protected boolean isKnownVar(String str) {
+        /**
+         * Returns true if the variable belongs to the current function.
+         * Required when matching liveness in certain instructions.
+         *
+         * Helper for addLivenessi
+         */
+        return Arrays.asList(f.vars).contains(str) ||
+            Arrays.asList(f.params).contains(str);
+    }
+
+}