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
126
127
128
129
130
131
|
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);
for (String var : source.getReaching()) {
dest.reaching.add(var);
}
for (String var : dest.getLiveness()) {
if (!source.getDefinitions().contains(var))
source.liveness.add(var);
}
ret += ";";
} else {
MinimalLogger.info(String.format("Skipping duplicate edge for %s",
source.toString()));
}
return ret;
}
public void addDefinition(CFGNode n, String s) {
n.defs.add(s);
n.reaching.add(s);
n.liveness.add(s);
}
public void addReference(CFGNode n, String s) {
if (this.isKnownVar(s)) {
MinimalLogger.info(String.format("\"%s\" referenced at %s",
s,
n.toString()));
n.reaching.add(s);
n.liveness.add(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);
}
}
|
