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
|
/*
*/
package submit;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
*
*
*
*/
public final class RegisterAllocator {
// True if t is used
private final boolean[] t = new boolean[10];
private final boolean[] s = new boolean[8];
private final Set<String> used = new HashSet<>();
public RegisterAllocator() { clearAll(); }
public String getRegisterOrLoadIntoRegister(MIPSResult result,
StringBuilder code) {
if (result.getRegister() != null) {
return result.getRegister();
}
String reg = result.getAddress();
return this.loadIntoRegister(result, code, reg);
}
public String loadIntoRegister(MIPSResult result, StringBuilder code,
String register) {
return loadIntoRegisterWithOffset(result, code, register, 0);
}
public String loadIntoRegisterWithOffset(MIPSResult result,
StringBuilder code, String register,
int offset) {
code.append(
String.format("lw %s %d(%s)\n", register, offset, result.getAddress()));
return register;
}
public String getT() {
for (int i = 0; i < t.length; ++i) {
if (!t[i]) {
t[i] = true;
String str = "$t" + i;
used.add(str);
return str;
}
}
return null;
}
// public String getS() {
// for (int i = 0; i < s.length; ++i) {
// if (!s[i]) {
// s[i] = true;
// String str = "$s" + i;
// used.add(str);
// return str;
// }
// }
// return null;
// }
// Returns the number of bytes used to save the registers
public int saveRestore(StringBuilder code, int baseOffset, boolean s_or_t,
boolean save) {
boolean[] r = s;
String prefix = "$s";
if (!s_or_t) {
r = t;
prefix = "$t";
}
String instruction = "sw";
if (!save) {
instruction = "lw";
}
int offset = 0;
for (int i = 0; i < r.length; ++i) {
if (r[i]) {
offset -= 4;
String str = prefix + i;
code.append(instruction)
.append(" ")
.append(str)
.append(" ")
.append(offset - baseOffset)
.append("($sp)\n");
}
}
return -offset;
}
// public int saveS(StringBuilder code, int baseOffset) {
// return saveRestore(code, baseOffset, true, true);
// }
public int saveT(StringBuilder code, int baseOffset) {
return saveRestore(code, baseOffset, false, true);
}
// public int restoreS(StringBuilder code, int baseOffset) {
// return saveRestore(code, baseOffset, true, false);
// }
public int restoreT(StringBuilder code, int baseOffset) {
return saveRestore(code, baseOffset, false, false);
}
public List<String> getUsed() { return new ArrayList<>(used); }
/**
* Any time you call this method you should seriously consider adding a
* corresponding clear() call.
*
* @return
*/
public String getAny() {
// String availS = getS();
// if (availS != null) {
// return availS;
// }
String t = getT();
if (t == null) {
throw new RuntimeException("Out of registers");
}
return t;
}
public void clear(String reg) {
if (reg == null)
return;
if (reg.charAt(1) == 's') {
s[Integer.parseInt(reg.substring(2))] = false;
} else if (reg.charAt(1) == 't') {
t[Integer.parseInt(reg.substring(2))] = false;
} else {
throw new RuntimeException("Unexpected register in clear");
}
}
public void clearAll() {
Arrays.fill(t, false);
Arrays.fill(s, false);
}
}
|
