1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.TreeMap;
7
8
12 class NInterval implements Comparable<NInterval> {
13 private NControlFlowGraph cfg;
15
16
20 public int vRegId;
21
22
25 public ArrayList<NRange> ranges;
26
27
30 public TreeMap<Integer, InstructionType> usePositions;
31
32
36 public NPhysicalRegister pRegister;
37
38
41 public boolean spill;
42
43
46 public OffsetFrom offsetFrom;
47
48
51 public int offset;
52
53
56 public NInterval parent;
57
58
61 public ArrayList<NInterval> children;
62
63
69 public NInterval(int vRegId, NControlFlowGraph cfg) {
70 this.vRegId = vRegId;
71 this.cfg = cfg;
72 ranges = new ArrayList<NRange>();
73 usePositions = new TreeMap<Integer, InstructionType>();
74 spill = false;
75 pRegister = null;
76 offset = -1;
77 parent = null;
78 children = new ArrayList<NInterval>();
79 }
80
81
89 public NInterval(int virtualRegID, NControlFlowGraph cfg, ArrayList<NRange> childRanges,
90 NInterval parent) {
91 this.cfg = cfg;
92 this.ranges = childRanges;
93 this.usePositions = new TreeMap<Integer, InstructionType>();
94 this.vRegId = virtualRegID;
95 this.parent = parent;
96 this.children = new ArrayList<NInterval>();
97 spill = false;
98 offset = -1;
99 }
100
101
107 public void addOrExtendNRange(NRange newNRange) {
108 if (!ranges.isEmpty()) {
109 if (newNRange.stop + 5 == ranges.get(0).start ||
110 newNRange.rangeOverlaps(ranges.get(0))) {
111 ranges.get(0).start = newNRange.start;
112 } else {
113 ranges.add(0, newNRange);
114 }
115 } else {
116 ranges.add(newNRange);
117 }
118 }
119
120
126 public int nextIntersection(NInterval otherInterval) {
127 int a = -1, b = -2;
128 for (NRange r : this.ranges) {
129 if (otherInterval.isLiveAt(r.start)) {
130 a = r.start;
131 break;
132 }
133 }
134 for (NRange r : otherInterval.ranges) {
135 if (this.isLiveAt(r.start)) {
136 b = r.start;
137 break;
138 }
139 }
140 if (a >= 0 && b >= 0) {
141 return a <= b ? a : b;
142 } else {
143 return a > b ? a : b;
144 }
145 }
146
147
156 public int nextUsageOverlapping(NInterval currInterval) {
157 int psi = currInterval.firstNRangeStart();
158 if (usePositions.ceilingKey(psi) != null) {
159 return usePositions.ceilingKey(psi);
160 } else if (!usePositions.isEmpty()) {
161 return usePositions.firstKey();
162 } else {
163 return Integer.MAX_VALUE;
164 }
165 }
166
167
172 public int firstUsage() {
173 return usePositions.firstKey();
174 }
175
176
182 public void newFirstRangeStart(int newStart) {
183 if (!ranges.isEmpty()) {
184 ranges.get(0).start = newStart;
185 }
186 }
187
188
194 public void addUsePosition(Integer index, InstructionType type) {
195 usePositions.put(index, type);
196 }
197
198
204 public boolean isLiveAt(int atIndex) {
205 for (NRange r : ranges) {
206 if (atIndex >= r.start && atIndex < r.stop) {
207 return true;
208 }
209 }
210 return false;
211 }
212
213
221 private NRange liveRangeAt(int id) {
222 for (NRange r : ranges) {
223 if (id >= r.start && id <= r.stop) {
224 return r;
225 }
226 }
227 return null;
228 }
229
230
235 public void writeToStdOut(PrettyPrinter p) {
236 if (cfg.registers.get(vRegId) != null) {
237 String s = cfg.registers.get(vRegId).name() + ": ";
238 for (NRange r : ranges) {
239 s += r.toString() + " ";
240 }
241 if (pRegister != null) {
242 s += "-> " + pRegister.name();
243 } else {
244 s += "-> None";
245 }
246 if (spill) {
247 if (offsetFrom == OffsetFrom.FP) {
248 s += " [frame:" + offset + "]";
249 } else {
250 s += " [stack:" + offset + "]";
251 }
252 }
253 p.printf("%s\n", s);
254 for (NInterval child : this.children) {
255 child.writeToStdOut(p);
256 }
257 } else if (this.isChild()) {
258 String s = "\tv" + this.vRegId + ": ";
259 for (NRange r : ranges) {
260 s += r.toString() + " ";
261 }
262 if (pRegister != null) {
263 s += "-> " + pRegister.name();
264 } else {
265 s += "-> None";
266 }
267 if (offsetFrom == OffsetFrom.FP) {
268 s += " [frame:" + offset + "]";
269 } else {
270 s += " [stack:" + offset + "]";
271 }
272 p.printf("%s\n", s);
273 for (NInterval child : this.children) {
274 child.writeToStdOut(p);
275 }
276 }
277 }
278
279
284 public int firstNRangeStart() {
285 return ranges.isEmpty() ? -1 : ranges.get(0).start;
286 }
287
288
293 public int lastNRangeStop() {
294 return ranges.isEmpty() ? -1 : ranges.get(ranges.size() - 1).stop;
295 }
296
297
303 public int compareTo(NInterval other) {
304 return this.firstNRangeStart() - other.firstNRangeStart();
305 }
306
307
313 public boolean equals(NInterval other) {
314 return (this.vRegId == other.vRegId);
315 }
316
317
326 public NInterval splitAt(int idx) {
327 ArrayList<NRange> childsRanges = new ArrayList<NRange>();
328 if (this.isLiveAt(idx)) { NRange liveRange = this.liveRangeAt(idx);
332 int splitTo = idx;
333 splitTo = usePositions.ceilingKey(idx);
334 childsRanges.add((liveRange.splitRange(splitTo, idx - 5)));
335 }
336
337 for (NRange r : ranges) {
340 if (r.start > idx) {
341 childsRanges.add(r);
342 }
343 }
344 for (NRange r : childsRanges) {
345 ranges.remove(r);
346 }
347
348 NInterval child = new NInterval(cfg.maxIntervals++, cfg, childsRanges, getParent());
349 cfg.registers.add(null);
351 while (this.usePositions.ceilingKey(idx) != null) {
353 child.usePositions.put(usePositions.ceilingKey(idx),
354 usePositions.remove(usePositions.ceilingKey(idx)));
355 }
356 getParent().children.add(child);
357
358 return child;
359 }
360
361
366 private NInterval getParent() {
367 return parent != null ? parent : this;
368 }
369
370
376 public NInterval childAt(int idx) {
377 for (NInterval child : children) {
378 if (child.isLiveAt(idx)) {
379 return child;
380 }
381 }
382 return this;
383 }
384
385
392 public NInterval childAtOrEndingBefore(NBasicBlock b) {
393 int idx = b.getLastLIRInstId();
394 for (NInterval child : children) {
395 if (child.isLiveAt(idx)) {
396 return child;
397 }
398 }
399 NInterval tmp = this;
400 int highestEndingAllowed = b.getFirstLIRInstId();
401 for (NInterval child : children) {
402 if (child.lastNRangeStop() < idx && child.lastNRangeStop() > highestEndingAllowed) {
404 tmp = child;
405 highestEndingAllowed = tmp.lastNRangeStop();
406 }
407 }
408 return tmp;
409 }
410
411
419 public NInterval childAtOrStartingAfter(NBasicBlock b) {
420 int idx = b.getFirstLIRInstId();
421 for (NInterval child : children) {
422 if (child.isLiveAt(idx)) {
423 return child;
424 }
425 }
426 NInterval tmp = this;
427 int lowestStartAllowed = b.getLastLIRInstId(); for (NInterval child : children) {
429 if (child.firstNRangeStart() > idx && child.firstNRangeStart() < lowestStartAllowed) {
430 tmp = child;
431 lowestStartAllowed = tmp.firstNRangeStart();
432 }
433 }
434 return tmp;
435 }
436
437
442 public int startsAtBlock() {
443 for (NBasicBlock b : this.cfg.basicBlocks) {
444 if (this.firstNRangeStart() >= b.getFirstLIRInstId()
445 && this.firstNRangeStart() <= b.getLastLIRInstId())
446 return b.id;
447 }
448 return -1; }
450
451
456 public int endsAtBlock() {
457 for (NBasicBlock b : this.cfg.basicBlocks) {
458 if (this.lastNRangeStop() >= b.getFirstLIRInstId()
459 && this.lastNRangeStop() <= b.getLastLIRInstId()) {
460 return b.id;
461 }
462 }
463 return -1; }
465
466
470 public void spill() {
471 this.spill = true;
472 if (this.offset == -1) {
473 this.offset = cfg.offset++;
474 this.offsetFrom = OffsetFrom.SP;
475 }
476 for (NInterval child : children) {
477 if (child.offset == -1) {
478 child.offset = this.offset;
479 child.offsetFrom = this.offsetFrom;
480 }
481 }
482 }
483
484
489 public boolean isChild() {
490 return parent != null;
491 }
492
493
498 public boolean isParent() {
499 return !this.children.isEmpty();
500 }
501 }
502
503
506 enum OffsetFrom {
507 FP, SP
508 };
509
510
513 enum InstructionType {
514 read, write
515 };
516
517
520 class NRange implements Comparable<NRange> {
521
524 public int start;
525
526
529 public int stop;
530
531
537 public NRange(int start, int stop) {
538 this.start = start;
539 this.stop = stop;
540 }
541
542
550 public NRange splitRange(int newStart, int newStop) {
551 NRange newRange = new NRange(newStart, stop);
552 this.stop = newStop;
553 return newRange;
554 }
555
556
562 public boolean rangeOverlaps(NRange other) {
563 return other.start <= this.stop && this.start <= other.stop;
564 }
565
566
572 public int compareTo(NRange other) {
573 return this.start - other.start;
574 }
575
576
581 public String toString() {
582 return "[" + start + ", " + stop + "]";
583 }
584 }
585