From 35eae1492c94e353ba8a1a52bfbae9313808b357 Mon Sep 17 00:00:00 2001 From: bd-912 Date: Sat, 20 Apr 2024 18:22:49 -0600 Subject: CFG Class cleanup/reordering --- V2VM.java | 2 +- cfg/CFGNode.java | 73 +++++++++++++++++++ cfg/ControlFlowGraph.java | 125 +++++++++++++++++++++++++++++++++ vaporize/library/CFGNode.java | 95 ------------------------- vaporize/library/CFGSimp.java | 72 ++++++------------- vaporize/library/ControlFlowGraph.java | 97 ------------------------- 6 files changed, 221 insertions(+), 243 deletions(-) create mode 100644 cfg/CFGNode.java create mode 100644 cfg/ControlFlowGraph.java delete mode 100644 vaporize/library/CFGNode.java delete mode 100644 vaporize/library/ControlFlowGraph.java diff --git a/V2VM.java b/V2VM.java index 5d78381..3d181dd 100644 --- a/V2VM.java +++ b/V2VM.java @@ -13,7 +13,7 @@ import java.io.InputStreamReader; import java.io.IOException; import java.io.PrintStream; -import st.*; +import cfg.*; import misc.*; import vaporize.library.*; 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 sources; + private ArrayList dests; + protected Set reaching; + protected Set 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 getSources() { + return Collections.unmodifiableList(this.sources); + } + + public List getDests() { + return Collections.unmodifiableList(this.dests); + } + + public Set getReaching() { + return Collections.unmodifiableSet(this.reaching); + } + + public Set 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 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 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); + } + +} 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 sources; - private ArrayList dests; - private HashSet reaching; - private HashSet 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 getSources() { - return this.sources; - } - - protected ArrayList getDests() { - return this.dests; - } - - protected HashSet getReaching() { - return this.reaching; - } - - protected HashSet 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 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%s (\"%s\":%s)", n.getClass().getSimpleName(), @@ -111,10 +94,8 @@ public class CFGSimp extends VInstr.VisitorPR 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 getNodes() { - return this.nodes; - } - -} -- cgit v1.2.3