1
3 package jminusminus;
4
5 import java.util.ArrayList;
6
7
10
11 public class NLinearRegisterAllocator extends NRegisterAllocator {
12
15 private ArrayList<NInterval> unhandled;
16 private ArrayList<NInterval> active;
17 private ArrayList<NInterval> inactive;
18
19
23 private ArrayList<ArrayList<NInterval>> regIntervals;
24 private int[] freePos, usePos, blockPos;
25
26
32
33 public NLinearRegisterAllocator(NControlFlowGraph cfg) {
34 super(cfg);
35 unhandled = new ArrayList<NInterval>();
36 active = new ArrayList<NInterval>();
37 inactive = new ArrayList<NInterval>();
38
39 freePos = new int[NPhysicalRegister.MAX_COUNT];
42 usePos = new int[NPhysicalRegister.MAX_COUNT];
43 blockPos = new int[NPhysicalRegister.MAX_COUNT];
44 regIntervals = new ArrayList<ArrayList<NInterval>>();
45 for (int i = 0; i < NPhysicalRegister.MAX_COUNT; i++) {
46 regIntervals.add(new ArrayList<NInterval>());
47 }
48 }
49
50
54
55 public void allocation() {
56 this.buildIntervals();
59 for (int i = 32; i < cfg.intervals.size(); i++) {
61 this.addSortedToUnhandled(cfg.intervals.get(i));
62 }
63
64 for (int i = 0; i < 32; i++) {
68 if (cfg.registers.get(i) != null) {
69 cfg.intervals.get(i).pRegister = (NPhysicalRegister) cfg.registers
70 .get(i);
71 }
72 }
73
74 for (NBasicBlock block : cfg.basicBlocks) {
78 for (NLIRInstruction lir : block.lir) {
79 if (lir instanceof NLIRLoadLocal) {
80 NLIRLoadLocal loadLocal = (NLIRLoadLocal) lir;
81 if (loadLocal.local >= 4) {
82 NInterval interval = cfg.intervals
83 .get(((NVirtualRegister) loadLocal.write)
84 .number());
85 interval.spill = true;
86 interval.offset = loadLocal.local - 3;
87 interval.offsetFrom = OffsetFrom.FP;
88 }
89 }
90 }
91 }
92
93 NInterval currInterval; int psi; ArrayList<NInterval> tmp;
96
97 while (!unhandled.isEmpty()) {
100 currInterval = unhandled.remove(0);
101 psi = currInterval.firstRangeStart();
102 tmp = new ArrayList<NInterval>();
103 for (int i = 0; i < active.size(); i++) {
104 if (active.get(i).lastNRangeStop() < psi) {
105 tmp.add(active.get(i));
106 } else if (!active.get(i).isLiveAt(psi)) {
107 inactive.add(active.get(i));
108 tmp.add(active.get(i));
109 }
110 }
111 for (NInterval nonActive : tmp) {
112 active.remove(nonActive);
113 }
114 tmp = new ArrayList<NInterval>();
115 for (int i = 0; i < inactive.size(); i++) {
116 if (inactive.get(i).lastNRangeStop() < psi) {
117 tmp.add(inactive.get(i));
118 } else if (inactive.get(i).isLiveAt(psi)) {
119 active.add(inactive.get(i));
120 tmp.add(inactive.get(i));
121 }
122 }
123 for (NInterval nonInActive : tmp) {
124 inactive.remove(nonInActive);
125 }
126 if (!this.foundFreeRegFor(currInterval)) { this.allocateBlockedRegFor(currInterval); }
129 active.add(currInterval);
130 }
131 this.resolveDataFlow();
132 }
133
134
141
142 private void addSortedToUnhandled(NInterval newInterval) {
143 if (unhandled.isEmpty()) {
144 unhandled.add(newInterval);
145 } else {
146 int i = 0;
147 while (i < unhandled.size()
148 && unhandled.get(i).firstRangeStart() <= newInterval
149 .firstRangeStart()) {
150 i++;
151 }
152 unhandled.add(i, newInterval);
153 }
154 }
155
156
166
167 private boolean foundFreeRegFor(NInterval currInterval) {
168 this.initFreePositions(); for (NInterval activeInterval : active) {
170 if (activeInterval.pRegister != null)
171 freePos[activeInterval.pRegister.number - NPhysicalRegister.T0] = 0;
172 }
173 for (NInterval inactiveInterval : inactive) {
174 if (inactiveInterval.nextIntersection(currInterval) >= 0)
175 freePos[inactiveInterval.pRegister.number
176 - NPhysicalRegister.T0] = Math.min(
177 freePos[inactiveInterval.pRegister.number
178 - NPhysicalRegister.T0], inactiveInterval
179 .nextIntersection(currInterval));
180 }
181
182 int reg = this.getBestFreeReg();
185 if (freePos[reg] == 0)
186 return false;
187 else if (freePos[reg] > currInterval.lastNRangeStop()) {
188 currInterval.pRegister = NPhysicalRegister.regInfo[reg
189 + NPhysicalRegister.T0];
190 cfg.pRegisters.add(NPhysicalRegister.regInfo[reg
191 + NPhysicalRegister.T0]);
192 regIntervals.get(reg).add(currInterval);
193 return true;
194 } else {
195 this.addSortedToUnhandled(currInterval.splitAt(freePos[reg]));
196 currInterval.spill();
197 currInterval.pRegister = NPhysicalRegister.regInfo[reg
198 + NPhysicalRegister.T0];
199 regIntervals.get(reg).add(currInterval);
200 return true;
201 }
202 }
203
204
208
209 private void initFreePositions() {
210 for (int i = 0; i < NPhysicalRegister.MAX_COUNT; i++) {
211 freePos[i] = Integer.MAX_VALUE;
212 }
213 }
214
215
220
221 private int getBestFreeReg() {
222 int freeRegNumber = 0;
223 for (int i = 0; i < NPhysicalRegister.MAX_COUNT; i++) {
224 if (freePos[i] > freePos[freeRegNumber])
225 freeRegNumber = i;
226 }
227 return freeRegNumber;
228 }
229
230
236
237 private void allocateBlockedRegFor(NInterval currInterval) {
238 this.initUseAndBlockPositions(); for (NInterval activeInterval : active) {
240 usePos[activeInterval.pRegister.number - NPhysicalRegister.T0] = Math
241 .min(usePos[activeInterval.pRegister.number
242 - NPhysicalRegister.T0], activeInterval
243 .nextUsageOverlapping(currInterval));
244 }
245 for (NInterval inactiveInterval : inactive) {
246 if (inactiveInterval.nextIntersection(currInterval) >= 0)
247 usePos[inactiveInterval.pRegister.number - NPhysicalRegister.T0] = Math
248 .min(usePos[inactiveInterval.pRegister.number
249 - NPhysicalRegister.T0], inactiveInterval
250 .nextUsageOverlapping(currInterval));
251 }
252 int reg = this.getBestBlockedReg(); if (usePos[reg] < currInterval.firstUsage()) {
255 this.addSortedToUnhandled(currInterval.splitAt(currInterval
257 .firstUsage() - 5));
258 currInterval.spill();
259 NInterval splitChild = currInterval.splitAt(currInterval
260 .firstRangeStart());
261 this.addSortedToUnhandled(splitChild);
262 currInterval.spill();
263 } else {
264 currInterval.pRegister = NPhysicalRegister.regInfo[reg
266 + NPhysicalRegister.T0];
267 for (NInterval i : regIntervals.get(reg)) {
268 if (currInterval.nextIntersection(i) >= 0) {
269 NInterval splitChild = i.splitAt(currInterval
270 .firstRangeStart());
271 this.addSortedToUnhandled(splitChild);
272 i.spill();
273 }
274 }
275 regIntervals.get(reg).add(currInterval);
276 }
277 }
278
279
283
284 private void initUseAndBlockPositions() {
285 for (int i = 0; i < NPhysicalRegister.MAX_COUNT; i++) {
286 usePos[i] = Integer.MAX_VALUE;
287 blockPos[i] = Integer.MAX_VALUE;
288 }
289 }
290
291
296
297 private int getBestBlockedReg() {
298 int usableRegNumber = 0;
299 for (int i = 0; i < NPhysicalRegister.MAX_COUNT; i++) {
300 if (usePos[i] > usePos[usableRegNumber])
301 usableRegNumber = i;
302 }
303 return usableRegNumber;
304 }
305
306
310
311 private void resolveDataFlow() {
312 for (NInterval i : cfg.intervals) {
316 if (cfg.registers.get(i.vRegId) != null) {
317 if (i.spill) {
318 for (int c = 0; c < i.children.size(); c++) {
319 if (i.endsAtBlock() == i.children.get(c)
320 .startsAtBlock()) {
321 if (c == 0) {
322 addStoreInstruction(i, i.lastNRangeStop());
323 addLoadInstruction(i.children.get(c),
324 i.children.get(c).firstRangeStart());
325 } else {
326 addStoreInstruction(i.children.get(c - 1),
327 i.children.get(c - 1).lastNRangeStop());
328 addLoadInstruction(i.children.get(c),
329 i.children.get(c).firstRangeStart());
330 }
331 }
332 }
333 }
334 }
335 }
336
337 for (NBasicBlock b : cfg.basicBlocks) {
339 for (NBasicBlock s : b.successors) {
340 for (int i = s.liveIn.nextSetBit(0); i >= 0; i = s.liveIn
341 .nextSetBit(i + 1)) {
342 NInterval parent = cfg.intervals.get(i);
343 NInterval from = parent.childAtOrEndingBefore(b);
344 NInterval to = parent.childAtOrStartingAfter(s);
345 if (!from.equals(to)) {
346 addStoreInstruction(from, from.usePositions.floorKey(b
347 .getLastLIRInstId()));
348 to = getSegmentWithNearestUse(to, s.getFirstLIRInstId());
349 if (to.usePositions.ceilingEntry(s.getFirstLIRInstId())
350 .getValue() == InstructionType.read)
351 addLoadInstruction(to, to.usePositions.ceilingKey(s
353 .getFirstLIRInstId()));
354 }
355 }
356 }
357 }
358 }
359
360
373
374 private NInterval getSegmentWithNearestUse(NInterval i, int id) {
375 if (i.usePositions.ceilingEntry(id) != null)
376 return i;
377 else {
378 NInterval parent = i;
379 int idx = 0;
380 if (i.isChild()) {
381 parent = i.parent;
382 idx = parent.children.indexOf(i) + 1;
383 }
384 for (; idx < parent.children.size(); idx++) {
385 if (parent.children.get(idx).usePositions.ceilingEntry(id) != null)
386 return parent.children.get(idx);
387 }
388 return null;
389 }
390 }
391
392
400
401 private void addStoreInstruction(NInterval from, int id) {
402 NBasicBlock b = cfg.blockAt(id);
403 id++;
404 if (b.idIsFree(id)) { b.insertLIRInst(new NLIRStore(b, id, from.offset, from.offsetFrom,
406 from.pRegister));
407 }
408 }
409
410
418
419 private void addLoadInstruction(NInterval to, int id) {
420 NBasicBlock s = cfg.blockAt(id);
421 id--;
422 if (s.idIsFree(id)) { s.insertLIRInst(new NLIRLoad(s, id, to.offset, to.offsetFrom,
424 to.pRegister));
425 }
426 }
427
428 }