1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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 String getFunction() {
return this.f.ident;
}
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()));
}
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);
}
}
|
