summaryrefslogtreecommitdiff
path: root/vaporize
diff options
context:
space:
mode:
Diffstat (limited to 'vaporize')
-rw-r--r--vaporize/library/CFGNode.java95
-rw-r--r--vaporize/library/CFGSimp.java72
-rw-r--r--vaporize/library/ControlFlowGraph.java97
3 files changed, 22 insertions, 242 deletions
diff --git a/vaporize/library/CFGNode.java b/vaporize/library/CFGNode.java
deleted file mode 100644
index b23ca00..0000000
--- a/vaporize/library/CFGNode.java
+++ /dev/null
@@ -1,95 +0,0 @@
-package vaporize.library;
-
-import misc.*;
-import cs132.vapor.ast.*;
-
-import java.util.ArrayList;
-import java.util.HashSet;
-
-class CFGNode {
-
- private Node instruction;
- private ArrayList<CFGNode> sources;
- private ArrayList<CFGNode> dests;
- private HashSet<String> reaching;
- private HashSet<String> liveness;
- private int line;
-
- protected CFGNode(Node instruction) {
- this.instruction = instruction;
- this.sources = new ArrayList<>();
- this.dests = new ArrayList<>();
- this.reaching = new HashSet<>();
- this.liveness = new HashSet<>();
- this.line = this.instruction.sourcePos.line;
- }
-
- public String toString() {
- return this.instruction.toString();
- }
-
- /**
- * For if we only have a line
- * number. (VBranch issues)
- */
- // FIXME
- 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);
- }
-
- protected void addReaching(String add) {
- MinimalLogger.info(String.format("Def %s at %s",
- add,
- this.line));
- this.reaching.add(add);
- }
-
- protected void addLiveness(String add) {
- MinimalLogger.info(String.format("Use %s at %s",
- add,
- this.line));
- this.liveness.add(add);
- }
-
- protected Node getInstruction() {
- return this.instruction;
- }
-
- protected ArrayList<CFGNode> getSources() {
- return this.sources;
- }
-
- protected ArrayList<CFGNode> getDests() {
- return this.dests;
- }
-
- protected HashSet<String> getReaching() {
- return this.reaching;
- }
-
- protected HashSet<String> getLiveness() {
- return this.liveness;
- }
-
- protected int getLine() {
- return this.line;
- }
-
-
-}
diff --git a/vaporize/library/CFGSimp.java b/vaporize/library/CFGSimp.java
index 54ec61c..30ddc7d 100644
--- a/vaporize/library/CFGSimp.java
+++ b/vaporize/library/CFGSimp.java
@@ -2,6 +2,7 @@ package vaporize.library;
import cs132.vapor.ast.*;
import graphviz.*;
+import cfg.*;
import misc.*;
import java.io.File;
@@ -13,7 +14,6 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
private Kettle kettle;
private ArrayList<ControlFlowGraph> cfgs;
- private VFunction func; // the current function being processed
private CFGNode curr; // the current node being processed
private String dot_format; // a list of edges to be processed by graphviz
@@ -24,22 +24,15 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
for (VFunction f : vp.functions) {
- this.func = f;
- ControlFlowGraph cfg = new ControlFlowGraph();
+ ControlFlowGraph cfg = new ControlFlowGraph(f);
this.dot_format = "";
MinimalLogger.info(String.format("CFGSimp is collecting nodes for %s",
- this.kettle.parseFuncName(this.func)));
- for (VCodeLabel s : this.func.labels) {
- MinimalLogger.info(String.format("Label %d \"%s\"",
- s.sourcePos.line,
- this.kettle.get(s).trim()));
+ this.kettle.parseFuncName(f)));
+ for (VCodeLabel s : f.labels) {
cfg.addNode(new CFGNode(s));
}
- for (VInstr s : this.func.body) {
- MinimalLogger.info(String.format(" Body %d \"%s\"",
- s.sourcePos.line,
- this.kettle.get(s).trim()));
+ for (VInstr s : f.body) {
cfg.addNode(new CFGNode(s));
}
@@ -50,22 +43,21 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
// inital setup
// first visit may not find edges; cfg.addEdges will handle
this.curr = new CFGNode(f.body[0]);
- cfg.setStart(curr);
// cascades downwards --- cfg.addEdges
for (VVarRef.Local l : f.params)
- this.curr.addReaching(l.ident.toString());
- for (VInstr s : this.func.body)
+ 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("%d ::: %s ::: %s",
- n.getLine(),
+ MinimalLogger.info(String.format("%s ::: %s ::: %s",
+ n.toString(),
n.getReaching(),
n.getLiveness()));
if (this.use_graphviz)
- this.createDotGraph(this.kettle.parseFuncName(this.func));
+ this.createDotGraph(this.kettle.parseFuncName(f));
this.cfgs.add(cfg);
}
@@ -92,15 +84,6 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
gv.writeGraphToFile( gv.getGraph( gv.getDotSource(), type ), out );
}
- protected boolean isKnownVar(String str) {
- /**
- * Returns true if the variable belongs to the current function.
- * Required when matching liveness in certain instructions.
- */
- return Arrays.asList(this.func.vars).contains(str) ||
- Arrays.asList(this.func.params).contains(str);
- }
-
public String visit(ControlFlowGraph cfg, VMemRead n) throws RuntimeException {
MinimalLogger.info(String.format("->%s (\"%s\":%s)",
n.getClass().getSimpleName(),
@@ -111,10 +94,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.dot_format += cfg.addEdge(this.curr, curr);
this.curr = curr;
- curr.addReaching(n.dest.toString());
- String source = ((VMemRef.Global) n.source).base.toString();
- if (isKnownVar(source))
- curr.addLiveness(source);
+ 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(),
@@ -133,9 +114,7 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.dot_format += cfg.addEdge(this.curr, curr);
this.curr = curr;
- String source = n.source.toString();
- if (isKnownVar(source))
- curr.addLiveness(source);
+ cfg.addLiveness(curr, n.source.toString());
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
n.getClass().getSimpleName(),
@@ -154,10 +133,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.dot_format += cfg.addEdge(this.curr, curr);
this.curr = curr;
- curr.addReaching(n.dest.toString());
- String source = n.source.toString();
- if (isKnownVar(source))
- curr.addLiveness(source);
+ cfg.addReaching(curr, n.dest.toString());
+ cfg.addLiveness(curr, n.source.toString());
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
n.getClass().getSimpleName(),
@@ -177,8 +154,7 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.dot_format += cfg.addEdge(curr, cfg.getNode(new Integer(this.kettle
.findLabelIndex(n.target.toString()))));
- this.curr = curr;
- curr.addLiveness(n.value.toString());
+ cfg.addLiveness(curr, n.value.toString());
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
n.getClass().getSimpleName(),
@@ -219,11 +195,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.curr = curr;
if (n.dest != null)
- curr.addReaching(n.dest.toString());
+ cfg.addReaching(curr, n.dest.toString());
for (VOperand a : n.args) {
- String source = a.toString();
- if (isKnownVar(source))
- curr.addLiveness(source);
+ cfg.addLiveness(curr, a.toString());
}
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
@@ -244,11 +218,9 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.curr = curr;
if (n.dest != null)
- curr.addReaching(n.dest.toString());
+ cfg.addReaching(curr, n.dest.toString());
for (VOperand a : n.args) {
- String source = a.toString();
- if (isKnownVar(source))
- curr.addLiveness(source);
+ cfg.addLiveness(curr, a.toString());
}
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
@@ -268,8 +240,8 @@ public class CFGSimp extends VInstr.VisitorPR<ControlFlowGraph, String, RuntimeE
this.dot_format += cfg.addEdge(this.curr, curr);
this.curr = curr;
- if (n.value != null && isKnownVar(n.value.toString()))
- curr.addLiveness(n.value.toString());
+ if (n.value != null)
+ cfg.addLiveness(curr, n.value.toString());
///////////////////////////////////////////////////////////////
MinimalLogger.info(String.format("<-%s (\"%s\":%s)",
n.getClass().getSimpleName(),
diff --git a/vaporize/library/ControlFlowGraph.java b/vaporize/library/ControlFlowGraph.java
deleted file mode 100644
index 5d589fb..0000000
--- a/vaporize/library/ControlFlowGraph.java
+++ /dev/null
@@ -1,97 +0,0 @@
-package vaporize.library;
-
-import cs132.vapor.ast.*;
-import misc.*;
-
-import java.util.ArrayList;
-
-public class ControlFlowGraph {
-
- private ArrayList<CFGNode> nodes;
- private CFGNode start;
-
- protected ControlFlowGraph() {
- this.nodes = new ArrayList<>();
- this.start = null;
- }
-
- protected 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;
- }
-
- protected 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;
-
- }
-
- protected void addNode(CFGNode node) {
- this.nodes.add(node);
- }
-
- protected 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("%d -> %d",
- source.getInstruction().sourcePos.line,
- dest.getInstruction().sourcePos.line);
- MinimalLogger.info(String.format("Edge %s",
- ret));
-
- source.addDest(dest);
- dest.addSource(source);
-
- ret += ";";
- } else {
- MinimalLogger.info(String.format("Skipping duplicate edge for %d",
- source.getInstruction().sourcePos.line));
- }
-
- MinimalLogger.info(String.format("Spilling variables: %s",
- source.getReaching().toString()));
- dest.getReaching().addAll(source.getReaching());
-
- return ret;
- }
-
- protected void setStart(CFGNode start) {
- this.start = start;
- }
-
- protected ArrayList<CFGNode> getNodes() {
- return this.nodes;
- }
-
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-13 13:02:32 +0000