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