| NInterval.java |
1 // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2
3 package jminusminus;
4
5 import java.util.ArrayList;
6 import java.util.TreeMap;
7
8 /**
9 * Represents a lifetime interval, recording the interval of LIR code for which the corresponding
10 * virtual register contains a useful value.
11 */
12 class NInterval implements Comparable<NInterval> {
13 // Control flow graph instance.
14 private NControlFlowGraph cfg;
15
16 /**
17 * The virtual register id corresponding to the index in the array list of NIntervals used by
18 * register allocation
19 */
20 public int vRegId;
21
22 /**
23 * All live ranges for this virtual register
24 */
25 public ArrayList<NRange> ranges;
26
27 /**
28 * All use positions (in LIR) and their types for this virtual register
29 */
30 public TreeMap<Integer, InstructionType> usePositions;
31
32 /**
33 * The NPhyicalRegister assigned to this interval. If an interval ends up needing more than
34 * one physical register it is split.
35 */
36 public NPhysicalRegister pRegister;
37
38 /**
39 * Whether or not to spill.
40 */
41 public boolean spill;
42
43 /**
44 * From offset.
45 */
46 public OffsetFrom offsetFrom;
47
48 /**
49 * Offset.
50 */
51 public int offset;
52
53 /**
54 * Parent of this interval.
55 */
56 public NInterval parent;
57
58 /**
59 * Children of this interval.
60 */
61 public ArrayList<NInterval> children;
62
63 /**
64 * Constructs an NInterval object.
65 *
66 * @param vRegId program counter.
67 * @param cfg the control flow graph.
68 */
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 /**
82 * This second constructor is used in instantiating children of a split interval.
83 *
84 * @param virtualRegID program counter.
85 * @param cfg The control flow graph.
86 * @param childRanges The instruction ranges for this child.
87 * @param parent The parent interval.
88 */
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 /**
102 * Adds a new range to the existing ranges. If the range overlaps then the old start position
103 * will be given the new start range position.
104 *
105 * @param newNRange the NRange to add
106 */
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 /**
121 * Returns the very first position where an intersection with another interval occurs.
122 *
123 * @param otherInterval the interval to compare against for intersection.
124 * @return the position where the intersection begins.
125 */
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 /**
148 * Returns the next use position of this interval after the first range start of the foreign
149 * interval. If there is no such use, then the first use position is returned to preserve
150 * data flow (in case of loops).
151 *
152 * @param currInterval the interval with starting point after which we want to find the next
153 * usage of this one.
154 * @return the next use position.
155 */
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 /**
168 * Returns the first use position in this interval.
169 *
170 * @return the first use position in this interval.
171 */
172 public int firstUsage() {
173 return usePositions.firstKey();
174 }
175
176 /**
177 * Sets the start value of the very first range. Note: There will always be at least one
178 * range before this method is used by the NRegisterAllocator.buildIntervals() method.
179 *
180 * @param newStart the value to which the first range's start will be set.
181 */
182 public void newFirstRangeStart(int newStart) {
183 if (!ranges.isEmpty()) {
184 ranges.get(0).start = newStart;
185 }
186 }
187
188 /**
189 * Registers a use (read or write).
190 *
191 * @param index the site of the use.
192 * @param type the instruction type.
193 */
194 public void addUsePosition(Integer index, InstructionType type) {
195 usePositions.put(index, type);
196 }
197
198 /**
199 * Returns true if this virtual register is alive at a given index, and false otherwise.
200 *
201 * @param atIndex the index at which to see if this register is live.
202 * @return true if this virtual register is alive at a given index, and false otherwise.
203 */
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 /**
214 * Returns the range in this interval in which the LIR instruction with the given id is live,
215 * or null.
216 *
217 * @param id the LIR instruction id.
218 * @return the range in this interval in which the LIR instruction with the given id is live,
219 * or null.
220 */
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 /**
231 * Writes the interval information to STDOUT.
232 *
233 * @param p for pretty printing with indentation.
234 */
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 /**
280 * Returns the start position for the first range.
281 *
282 * @return the start position for the first range.
283 */
284 public int firstNRangeStart() {
285 return ranges.isEmpty() ? -1 : ranges.get(0).start;
286 }
287
288 /**
289 * Returns the stop position for the last range.
290 *
291 * @return the stop position for the last range.
292 */
293 public int lastNRangeStop() {
294 return ranges.isEmpty() ? -1 : ranges.get(ranges.size() - 1).stop;
295 }
296
297 /**
298 * Returns a comparison of this interval with other.
299 *
300 * @param other interval to compare to.
301 * @return a comparison of this interval with other.
302 */
303 public int compareTo(NInterval other) {
304 return this.firstNRangeStart() - other.firstNRangeStart();
305 }
306
307 /**
308 * Returns true if this interval is the same as other, and false otherwise.
309 *
310 * @param other the interval we are comparing with.
311 * @return true if this interval is the same as other, and false otherwise.
312 */
313 public boolean equals(NInterval other) {
314 return (this.vRegId == other.vRegId);
315 }
316
317 /**
318 * Splits the current interval at the given index. Responsible for splitting a range if the
319 * index falls on one, moving remaining ranges over to child, and moving appropriate
320 * usePositions over to the child.
321 *
322 * @param idx the index at which this interval is to be split
323 * @return the child interval which is to be sorted onto unhandled. If there was no child
324 * created in the case of a pruning this interval is returned.
325 */
326 public NInterval splitAt(int idx) {
327 ArrayList<NRange> childsRanges = new ArrayList<NRange>();
328 if (this.isLiveAt(idx)) { // means split falls on a range
329 // Assumptions: if a range is LIVE on an index, then there exist usePositions at or
330 // before the index within this same range.
331 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 // The following two for loops take care of any untouched ranges which start after the
338 // split position and must be moved to the child interval.
339 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); // expand size of cfg.registers to avoid NPE when printing
350
351 // Transfer remaining use positions.
352 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 /**
362 * Returns the parent interval.
363 *
364 * @return the parent interval.
365 */
366 private NInterval getParent() {
367 return parent != null ? parent : this;
368 }
369
370 /**
371 * Returns the child interval at the given instruction index.
372 *
373 * @param idx the instruction index.
374 * @return the child interval at the given instruction index.
375 */
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 /**
386 * Returns the child of this interval which is live or ends before the given basic block's end.
387 *
388 * @param b the basic block.
389 * @return the child of this interval which ends at or nearest (before) this basic block's
390 * end (last lir instruction index).
391 */
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 // Get the child which ends before idx but also ends closest to idx.
403 if (child.lastNRangeStop() < idx && child.lastNRangeStop() > highestEndingAllowed) {
404 tmp = child;
405 highestEndingAllowed = tmp.lastNRangeStop();
406 }
407 }
408 return tmp;
409 }
410
411 /**
412 * Returns the child of this interval which is live or starts after the given basic block's
413 * start.
414 *
415 * @param b the basic block.
416 * @return the child of this interval which starts at or nearest (after) this basic block's
417 * start (fist lir instruction index).
418 */
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(); // block's end
428 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 /**
438 * Returns the basic block in which this interval's start position falls.
439 *
440 * @return the basic block in which this interval's start position falls.
441 */
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; // this will never happen
449 }
450
451 /**
452 * Returns the basic block in which this interval's end position falls.
453 *
454 * @return the basic block in which this interval's end position falls.
455 */
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; // this will never happen
464 }
465
466 /**
467 * Assigns an offset to this interval (if one hasn't been already assigned). Assigns that
468 * same offset to any (newly created) children.
469 */
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 /**
485 * Returns true if this is a child interval, and false otherwise.
486 *
487 * @return true if this is a child interval, and false otherwise.
488 */
489 public boolean isChild() {
490 return parent != null;
491 }
492
493 /**
494 * Returns true if this is a parent interval, and false otherwise.
495 *
496 * @return true if this is a parent interval, and false otherwise.
497 */
498 public boolean isParent() {
499 return !this.children.isEmpty();
500 }
501 }
502
503 /**
504 * The types of stack pointers.
505 */
506 enum OffsetFrom {
507 FP, SP
508 };
509
510 /**
511 * The types of possible uses.
512 */
513 enum InstructionType {
514 read, write
515 };
516
517 /**
518 * Representation of a liveness range for an interval.
519 */
520 class NRange implements Comparable<NRange> {
521 /**
522 * The range's start position.
523 */
524 public int start;
525
526 /**
527 * The range's stop position.
528 */
529 public int stop;
530
531 /**
532 * Constructs a liveness range extending from start to stop (positions in the code).
533 *
534 * @param start start position.
535 * @param stop stop position.
536 */
537 public NRange(int start, int stop) {
538 this.start = start;
539 this.stop = stop;
540 }
541
542 /**
543 * Truncates the current range to newStop and returns the remainder as a new range.
544 *
545 * @param newStart the new start position.
546 * @param newStop the split position.
547 * @return the remainder of this range starting at newStart and ending at its old stop
548 * position.
549 */
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 /**
557 * Returns true if this range overlaps with other, and false otherwise.
558 *
559 * @param other the other range.
560 * @return true if this range overlaps with other, and false otherwise.
561 */
562 public boolean rangeOverlaps(NRange other) {
563 return other.start <= this.stop && this.start <= other.stop;
564 }
565
566 /**
567 * Returns a comparison of this range and other by their start positions.
568 *
569 * @param other the other range.
570 * @return a comparison of this range and other by their start positions.
571 */
572 public int compareTo(NRange other) {
573 return this.start - other.start;
574 }
575
576 /**
577 * Returns a string representation of this range.
578 *
579 * @return a string representation of this range.
580 */
581 public String toString() {
582 return "[" + start + ", " + stop + "]";
583 }
584 }
585