forked from mrhappyasthma/MiniJava-Compiler
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLiveness.java
More file actions
190 lines (147 loc) · 5.65 KB
/
Liveness.java
File metadata and controls
190 lines (147 loc) · 5.65 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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package regalloc;
import IR.Quadruple;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Hashtable;
import java.util.List;
import regalloc.graph.Node;
import symboltable.Variable;
public class Liveness {
List<Node> flowGraph;
List<BitSet> liveIn;
List<BitSet> liveOut;
public Liveness(List<Node> fG) {
flowGraph = fG;
liveIn = new ArrayList<BitSet>();
liveOut = new ArrayList<BitSet>();
}
public void calculateLive() {
List<Variable> listVar = getAllVariables();
//if the function is not the first it is not going to start as 0
int offset = flowGraph.get(0).getNum();
List<BitSet> auxListIn = new ArrayList<BitSet>();
List<BitSet> auxListOut = new ArrayList<BitSet>();;
for (int j = 0; j < flowGraph.size(); j++) {
BitSet bitIn = new BitSet(listVar.size());
liveIn.add(j,bitIn);
auxListIn.add(j,bitIn);
BitSet bitOut = new BitSet(listVar.size());
auxListOut.add(j,bitOut);
liveOut.add(j,bitOut);
}
do {
for (int i = 0; i < flowGraph.size(); i++) {
Node n = flowGraph.get(i);
auxListIn.set(i, liveIn.get(i));
auxListOut.set(i, liveOut.get(i));
//or - union , and - intersection, andNot - difference
BitSet bitUse = n.calculateUse(listVar);
BitSet bitDef = n.calculateDef(listVar);
BitSet aux = liveOut.get(i);
aux.andNot(bitDef);
bitUse.or(aux);
liveIn.set(i, bitUse);
//out[n] = union over successors
List<Node> nextNodes = n.nextNode();
//walk the nexts to get the number of the instruction to see it liveIn
BitSet bitNext = new BitSet(listVar.size());
for (int j = 0; j < nextNodes.size(); j++) {
if(!n.getJumpToFunction() && n!=null){
BitSet bitNextAux = liveIn.get((nextNodes.get(j).getNum())-offset);
bitNext.or(bitNextAux);
}
}
liveOut.set(i, bitNext);
}
} while (!allEqual(liveIn, auxListIn, liveOut, auxListOut));
}
// function to keep in a list all variables and temporaries that the program has
public List<Variable> getAllVariables() {
List<Variable> listVar = new ArrayList<Variable>();
for (int i = 0; i < flowGraph.size(); i++) {
Node n = flowGraph.get(i);
Quadruple instr = n.getInstr();
if (instr.getArg1() != null) {
if ((instr.getArg1()) instanceof Variable) {
Variable arg1 = (Variable) instr.getArg1();
if (!arg1.getType().equals("constant")) {
if (!hasVariable(arg1, listVar)) {
listVar.add(arg1);
}
}
}
}
if (instr.getArg2() != null) {
if ((instr.getArg2()) instanceof Variable) {
Variable arg2 = (Variable) instr.getArg2();
if (!arg2.getType().equals("constant")) {
if (!hasVariable(arg2, listVar)) {
listVar.add(arg2);
}
}
}
}
if (instr.getResult() != null) {
if ((instr.getResult()) instanceof Variable) {
Variable result = (Variable) instr.getResult();
if (!hasVariable(result, listVar)) {
listVar.add(result);
}
}
}
}
return listVar;
}
//function helper that returns true if the Variable is already in the list
private boolean hasVariable(Variable var, List<Variable> listVar) {
for (int i = 0; i < listVar.size(); i++) {
if (listVar.contains(var)) {
return true;
}
}
return false;
}
private boolean allEqual(List<BitSet> liveIn, List<BitSet> auxIn, List<BitSet> liveOut, List<BitSet> auxOut) {
if(liveIn.size() != auxIn.size() && liveOut.size() != auxOut.size()){
return false;
}
else{
if(compareListBits(liveIn, auxIn) && compareListBits(liveOut, auxOut)){
return true;
}
}
return false;
}
public List<BitSet> getLiveOut() {
return liveOut;
}
private void printUseDef(List<Variable> listVar) {
for (int i = 0; i < flowGraph.size(); i++) {
Node n = flowGraph.get(i);
System.out.print(i+" Def: "+n.calculateDef(listVar));
System.out.println(" Use "+n.calculateUse(listVar));
}
}
private void printLiveInOut() {
System.out.println("LiveIn:");
for (int i = 0; i < liveIn.size(); i++) {
System.out.print(i+" "+liveIn.get(i)+" ");
}
System.out.println();
System.out.println("LiveOut:");
for (int i = 0; i < liveOut.size(); i++) {
System.out.print(i+" "+liveOut.get(i)+" ");
}
System.out.println();
}
private boolean compareListBits(List<BitSet> list1, List<BitSet> list2) {
for (int i = 0; i < list1.size(); i++) {
for (int j = 0; j < list1.get(i).size(); j++) {
if(list1.get(i).get(j) != list2.get(i).get(j)){
return false;
}
}
}
return true;
}
}