1
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.Collections;
7 import java.util.TreeMap;
8
9 import static jminusminus.NPhysicalRegister.*;
10
11
15
16 class NInterval implements Comparable<NInterval> {
17
18
19 private NControlFlowGraph cfg;
20
21
25 public int vRegId;
26
27
28 public ArrayList<NRange> ranges;
29
30
33 public TreeMap<Integer, InstructionType> usePositions;
34
35
39 public NPhysicalRegister pRegister;
40
41
42 public boolean spill;
43
44
45 public OffsetFrom offsetFrom;
46
47
48 public int offset;
49
50
51 public NInterval parent;
52
53
54 public ArrayList<NInterval> children;
55
56
65
66 public NInterval(int virtualRegID, NControlFlowGraph cfg) {
67 this.cfg = cfg;
68 this.ranges = new ArrayList<NRange>();
69 this.usePositions = new TreeMap<Integer, InstructionType>();
70 this.vRegId = virtualRegID;
71 this.children = new ArrayList<NInterval>();
72 this.parent = null;
73 spill = false;
74 offset = -1;
75 }
76
77
90
91 public NInterval(int virtualRegID, NControlFlowGraph cfg,
92 ArrayList<NRange> childRanges, NInterval parent) {
93 this.cfg = cfg;
94 this.ranges = childRanges;
95 this.usePositions = new TreeMap<Integer, InstructionType>();
96 this.vRegId = virtualRegID;
97 this.parent = parent;
98 this.children = new ArrayList<NInterval>();
99 spill = false;
100 offset = -1;
101 }
102
103
109
110 public void addOrExtendNRange(NRange newNRange) {
111 if (!ranges.isEmpty()) {
112 if (newNRange.stop + 5 == ranges.get(0).start
113 || newNRange.rangeOverlaps(ranges.get(0))) {
114 ranges.get(0).start = newNRange.start;
115 } else {
116 ranges.add(0, newNRange);
117 }
118 } else {
119 ranges.add(newNRange);
120 }
121 }
122
123
133
134 public int nextIntersection(NInterval otherInterval) {
135 int a = -1, b = -2;
136 for (NRange r : this.ranges) {
137 if (otherInterval.isLiveAt(r.start)) {
138 a = r.start;
139 break;
140 }
141 }
142 for (NRange r : otherInterval.ranges) {
143 if (this.isLiveAt(r.start)) {
144 b = r.start;
145 break;
146 }
147 }
148 if (a >= 0 && b >= 0) {
149 return a <= b ? a : b;
150 } else {
151 return a > b ? a : b;
152 }
153 }
154
155
167
168 public int nextUsageOverlapping(NInterval currInterval) {
169 int psi = currInterval.firstRangeStart();
170
171 if (usePositions.ceilingKey(psi) != null) {
172 return usePositions.ceilingKey(psi);
173 } else if (!usePositions.isEmpty()) {
174 return usePositions.firstKey();
175 } else {
176 return Integer.MAX_VALUE;
177 }
178 }
179
180
185
186 public int firstUsage() {
187 return usePositions.firstKey();
188 }
189
190
197 public void newFirstRangeStart(int newStart) {
198 if (!ranges.isEmpty()) {
200 ranges.get(0).start = newStart;
201 }
202 }
203
204
212
213 public void addUsePosition(Integer index, InstructionType type) {
214 usePositions.put(index, type);
215 }
216
217
223
224 public boolean isLiveAt(int atIndex) {
225 for (NRange r : ranges) {
226 if (atIndex >= r.start && atIndex <= r.stop) {
227 return true;
228 }
229 }
230 return false;
231 }
232
233
242
243 private NRange liveRangeAt(int id) {
244 for (NRange r : ranges) {
245 if (id >= r.start && id <= r.stop) {
246 return r;
247 }
248 }
249 return null;
250 }
251
252
258
259 public void writeToStdOut(PrettyPrinter p) {
260 if (cfg.registers.get(vRegId) != null) {
261 String s = cfg.registers.get(vRegId).name() + ": ";
262 for (NRange r : ranges) {
263 s += r.toString() + " ";
264 }
265 if (pRegister != null) {
266 s += "-> " + pRegister.name();
267 } else {
268 s += "-> None";
269 }
270 if (spill) {
271 if (offsetFrom == OffsetFrom.FP) {
272 s += " [frame:" + offset + "]";
273 } else {
274 s += " [stack:" + offset + "]";
275 }
276 }
277 p.printf("%s\n", s);
278 for (NInterval child : this.children) {
279 child.writeToStdOut(p);
280 }
281 } else if (this.isChild()) {
282 String s = "\tv" + this.vRegId + ": ";
283 for (NRange r : ranges) {
284 s += r.toString() + " ";
285 }
286 if (pRegister != null) {
287 s += "-> " + pRegister.name();
288 } else {
289 s += "-> None";
290 }
291 if (offsetFrom == OffsetFrom.FP) {
292 s += " [frame:" + offset + "]";
293 } else {
294 s += " [stack:" + offset + "]";
295 }
296 p.printf("%s\n", s);
297 for (NInterval child : this.children) {
298 child.writeToStdOut(p);
299 }
300 }
301 }
302
303
308
309 public int firstRangeStart() {
310 if (ranges.isEmpty())
311 return -1;
312 else
313 return ranges.get(0).start;
314 }
315
316
321
322 public int lastNRangeStop() {
323 if (ranges.isEmpty())
324 return -1;
325 else
326 return ranges.get(ranges.size() - 1).stop;
327 }
328
329
337
338 public int compareTo(NInterval other) {
339 return this.firstRangeStart() - other.firstRangeStart();
340 }
341
342
349
350 public boolean equals(NInterval other) {
351 return (this.vRegId == other.vRegId);
352 }
353
354
366
367 public NInterval splitAt(int idx) {
368
369 ArrayList<NRange> childsRanges = new ArrayList<NRange>();
370 if (this.isLiveAt(idx)) { NRange liveRange = this.liveRangeAt(idx);
375 int splitTo = idx;
376 splitTo = usePositions.ceilingKey(idx);
377 childsRanges.add((liveRange.splitRange(splitTo, idx - 5)));
378 }
379
380 for (NRange r : ranges) {
384 if (r.start > idx) {
385 childsRanges.add(r);
386 }
387 }
388 for (NRange r : childsRanges) {
389 ranges.remove(r);
390 }
391
392 NInterval child = new NInterval(cfg.maxIntervals++, cfg, childsRanges,
393 this.getParent());
394 cfg.registers.add(null);
397 while (this.usePositions.ceilingKey(idx) != null)
399 child.usePositions
400 .put(this.usePositions.ceilingKey(idx), this.usePositions
401 .remove(this.usePositions.ceilingKey(idx)));
402 this.getParent().children.add(child);
403 return child;
404 }
405
406
411
412 private NInterval getParent() {
413 if (parent != null)
414 return parent;
415 else
416 return this;
417 }
418
419
426
427 public NInterval childAt(int idx) {
428 for (NInterval child : children) {
429 if (child.isLiveAt(idx)) {
430 return child;
431 }
432 }
433 return this;
434 }
435
436
445
446 public NInterval childAtOrEndingBefore(NBasicBlock b) {
447 int idx = b.getLastLIRInstId();
448 for (NInterval child : children) {
449 if (child.isLiveAt(idx))
450 return child;
451 }
452 NInterval tmp = this;
453 int highestEndingAllowed = b.getFirstLIRInstId();
454 for (NInterval child : children) {
455 if (child.lastNRangeStop() < idx
457 && child.lastNRangeStop() > highestEndingAllowed) {
458 tmp = child;
459 highestEndingAllowed = tmp.lastNRangeStop();
460 }
461 }
462 return tmp;
463 }
464
465
474
475 public NInterval childAtOrStartingAfter(NBasicBlock b) {
476 int idx = b.getFirstLIRInstId();
477 for (NInterval child : children) {
478 if (child.isLiveAt(idx))
479 return child;
480 }
481 NInterval tmp = this;
482 int lowestStartAllowed = b.getLastLIRInstId(); for (NInterval child : children) {
484 if (child.firstRangeStart() > idx
485 && child.firstRangeStart() < lowestStartAllowed) {
486 tmp = child;
487 lowestStartAllowed = tmp.firstRangeStart();
488 }
489 }
490 return tmp;
491 }
492
493
498
499 public int startsAtBlock() {
500 for (NBasicBlock b : this.cfg.basicBlocks) {
501 if (this.firstRangeStart() >= b.getFirstLIRInstId()
502 && this.firstRangeStart() <= b.getLastLIRInstId())
503 return b.id;
504 }
505 return -1; }
507
508
513
514 public int endsAtBlock() {
515 for (NBasicBlock b : this.cfg.basicBlocks) {
516 if (this.lastNRangeStop() >= b.getFirstLIRInstId()
517 && this.lastNRangeStop() <= b.getLastLIRInstId()) {
518 return b.id;
519 }
520 }
521 return -1; }
523
524
528
529 public void spill() {
530 this.spill = true;
531 if (this.offset == -1) {
532 this.offset = cfg.offset++;
533 this.offsetFrom = OffsetFrom.SP;
534 }
535 for (NInterval child : children) {
536 if (child.offset == -1) {
537 child.offset = this.offset;
538 child.offsetFrom = this.offsetFrom;
539 }
540 }
541 }
542
543
546
551
552 public boolean isChild() {
553 if (this.parent != null) {
554 return true;
555 } else {
556 return false;
557 }
558 }
559
560
565
566 public boolean isParent() {
567 return !this.children.isEmpty();
568 }
569
570 }
571
572
573 enum OffsetFrom {
574 FP, SP
575 };
576
577
578 enum InstructionType {
579 read, write
580 };
581
582
585
586 class NRange implements Comparable<NRange> {
587
588
589 public int start;
590
591
592 public int stop;
593
594
603 public NRange(int start, int stop) {
604 this.start = start;
605 this.stop = stop;
606
607 }
608
609
620
621 public NRange splitRange(int newStart, int oldStop) {
622 NRange newRange = new NRange(newStart, stop);
623 this.stop = oldStop;
624
625 return newRange;
626 }
627
628
635
636 public boolean rangeOverlaps(NRange a) {
637 if (a.start < this.start) {
638 if (a.stop <= this.start) {
639 return false;
640 } else {
641 return true;
642 }
643 } else if (a.start <= this.stop) {
644 return true;
645 } else {
646 return false;
647 }
648 }
649
650
659
660 public int compareTo(NRange other) {
661 return this.start - other.start;
662 }
663
664
669
670 public String toString() {
671 return "[" + start + ", " + stop + "]";
672 }
673
674 }
675