forked from mrhappyasthma/MiniJava-Compiler
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInterferenceGraph.java
More file actions
136 lines (112 loc) · 4.27 KB
/
InterferenceGraph.java
File metadata and controls
136 lines (112 loc) · 4.27 KB
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
132
133
134
135
package regalloc;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import regalloc.graph.Node;
import regalloc.graph.NodeInt;
import symboltable.Variable;
public class InterferenceGraph {
List<Node> flowGraph;
List<NodeInt> intGraph;
List<BitSet> liveOut;
List<Variable> vars;
int numVert;
public InterferenceGraph(List<Node> fG, List<BitSet> lO, List<Variable> v) {
flowGraph = fG;
liveOut = lO;
vars = v;
intGraph = new ArrayList<NodeInt>();
}
public void buildInterferenceGraph(){
for (int i = 0; i < flowGraph.size(); i++) {
Node n = flowGraph.get(i);
if(n.getMove()){
//later we will need to check if one of the live outs is the arg1
Variable arg1 = (Variable) n.getInstr().getArg1();
BitSet def = n.calculateDef(vars);
Variable v = vars.get(def.nextSetBit(0));
NodeInt nI = hasVar(v);
//doesn't exist
NodeInt node;
if(nI == null){
node = new NodeInt(v);
intGraph.add(node);
}
//already exists
else{
node = nI;
}
BitSet lOut = liveOut.get(i);
for (int j = 0; j < lOut.length(); j++) {
//if the bit is set
if(lOut.get(i)){
//get the var that has the index
v = vars.get(i);
//verify if the variable in the live out is not arg1
if(!arg1.getName().equals(v.getName())){
//verify if this var already is in a NodeInt
nI = hasVar(v);
NodeInt aux;
//if is not in a NodeInt create a new one
if(nI == null){
aux = new NodeInt(v);
intGraph.add(aux);
}
else{
aux = nI;
}
node.addEdge(aux);
aux.addEdge(node);
}
}
}
}
else{
BitSet def = n.calculateDef(vars);
Variable v = vars.get(def.nextSetBit(0));
NodeInt nI = hasVar(v);
//doesn' exist
NodeInt node;
if(nI == null){
node = new NodeInt(v);
intGraph.add(node);
}
//already exists
else{
node = nI;
}
BitSet lOut = liveOut.get(i);
for (int j = 0; j < lOut.length(); j++) {
//if the bit is set
if(lOut.get(i)){
//get the var that has the index
v = vars.get(i);
//verify if this var already is in a NodeInt
nI = hasVar(v);
NodeInt aux;
//if is not in a NodeInt create a new one
if(nI == null){
aux = new NodeInt(v);
intGraph.add(aux);
}
else{
aux = nI;
}
node.addEdge(aux);
aux.addEdge(node);
}
}
}
}
}
//function that check if the variable already exists in a node
public NodeInt hasVar(Variable var){
for (int i = 0; i < intGraph.size(); i++) {
NodeInt n = intGraph.get(i);
if(n.getVar().getName().equals(var.getName())){
return n;
}
}
return null;
}
}