blob: 100d6c4edc8d468b1c7b8783994c51d584d733c3 (
plain)
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
|
package vaporize;
import java.util.*;
import misc.*;
public class RegisterAlloc {
private LIRDict intervals;
private String[] all_registers;
private Stack<String> free_registers;
private TreeSet<LIRVar> active;
private int spill_start;
public RegisterAlloc(LIRDict intervals, String[] all_registers) {
this.spill_start = 14;
this.intervals = intervals;
this.all_registers = all_registers;
this.free_registers = new Stack<String>();
this.free_registers.addAll(Arrays.asList(this.all_registers));
this.active = new TreeSet<LIRVar>((v1, v2) -> {
int ret;
if (v1.getLastUse() > v2.getLastUse())
ret = 1;
else if (v1.getLastUse() < v2.getLastUse())
ret = -1;
else if (v1.equals(v2))
ret = 0;
else
ret = 1;
return ret;
});
MinimalLogger.info(String.format("Starting allocation with registers %s",
this.free_registers.toString()));
String register;
for (LIRVar interval : this.intervals.getIntervals()) {
this.expireOldIntervals(interval);
if (this.active.size() >= this.all_registers.length)
this.spillAtInterval(interval);
else {
register = this.free_registers.pop();
interval.assignRegister(register);
this.active.add(interval);
MinimalLogger.info(String.format("Assigning register %s to %s.",
register,
interval.toString()));
}
}
}
private void expireOldIntervals(LIRVar interval) {
// MinimalLogger.info(String.format("Active: %s",
// this.active.toString()));
// MinimalLogger.info(String.format("Available: %s",
// this.free_registers.toString()));
Iterator<LIRVar> iterator = this.active.iterator();
while (iterator.hasNext()) {
LIRVar active = iterator.next();
if (active.getLastUse() >= interval.getFirstDef())
return;
MinimalLogger.info(String.format("%s register %s expired!",
active.toString(),
active.getAssignedRegister()));
iterator.remove(); // Remove the element from the original active set
this.free_registers.push(active.getAssignedRegister());
}
}
private void spillAtInterval(LIRVar interval) {
// You can make this spill optimally (the sarkar linearscan algorithm)
MinimalLogger.severe(String.format("Ran out of free registers, had to spill %s!",
interval.toString()));
this.intervals.addSpilledNum();
interval.assignRegister(String.format("local[%d]", this.spill_start++));
}
}
|
