1   // Copyright 2013 Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
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  /**
12   * A lifetime interval, recording the interval of LIR code for which the
13   * corresponding virtual register contains a useful value.
14   */
15  
16  class NInterval implements Comparable<NInterval> {
17  
18      /** Control flow graph instance. */
19      private NControlFlowGraph cfg;
20  
21      /**
22       * The virtual register id corresponding to the index in the array list of
23       * NIntervals used by register allocation
24       */
25      public int vRegId;
26  
27      /** All live ranges for this virtual register */
28      public ArrayList<NRange> ranges;
29  
30      /**
31       * All use positions (in LIR) and their types for this virtual register
32       */
33      public TreeMap<Integer, InstructionType> usePositions;
34  
35      /**
36       * The NPhyicalRegister assigned to this interval. If an interval ends up
37       * needing more than one physical register it is split.
38       */
39      public NPhysicalRegister pRegister;
40  
41      /** Whether or not to spill. */
42      public boolean spill;
43  
44      /** From offset. */
45      public OffsetFrom offsetFrom;
46  
47      /** Offset. */
48      public int offset;
49  
50      /** Parent of this interval. */
51      public NInterval parent;
52  
53      /** Children of this interval. */
54      public ArrayList<NInterval> children;
55  
56      /**
57       * Construct a NInterval with the given virtual register ID for the given
58       * control flow graph.
59       * 
60       * @param virtualRegID
61       *            program counter.
62       * @param cfg
63       *            The control flow graph.
64       */
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      /**
78       * This second constructor is used in instantiating children of a split
79       * interval.
80       * 
81       * @param virtualRegID
82       *            program counter.
83       * @param cfg
84       *            The control flow graph.
85       * @param childRanges
86       *            The instruction ranges for this child.
87       * @param parent
88       *            The parent interval.
89       */
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     /**
104      * Add a new range to the existing ranges.
105      * 
106      * @param newNRange
107      *            - the NRange to add
108      */
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     /**
124      * Looks for the very first position where an intersection with another
125      * interval occurs.
126      * 
127      * NOTE: A.nextIntersection(B) equals B.nextIntersection(A)
128      * 
129      * @param otherInterval
130      *            the interval to compare against for intersection.
131      * @return the position where the intersection begins.
132      */
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     /**
156      * The next use position of this interval after the first range start of the
157      * foreign interval. If there is no such use, then the first use position is
158      * returned to preserve data flow (in case of loops).
159      * 
160      * @param currInterval
161      *            the interval with starting point after which we want to find
162      *            the next usage of this one.
163      * 
164      * @return the next use position.
165      * 
166      */
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     /**
181      * The first use position in this interval.
182      * 
183      * @return the first use position.
184      */
185 
186     public int firstUsage() {
187         return usePositions.firstKey();
188     }
189 
190     /**
191      * Sets the start value of the very first range. Note: There will always be
192      * at least one range before this method is used by buildIntervals.
193      * 
194      * @param newStart
195      *            the value to which the first range's start will be set.
196      */
197     public void newFirstRangeStart(int newStart) {
198         // Check
199         if (!ranges.isEmpty()) {
200             ranges.get(0).start = newStart;
201         }
202     }
203 
204     /**
205      * Register a use (read or write)>
206      * 
207      * @param index
208      *            the site of the use.
209      * @param type
210      *            the instruction type.
211      */
212 
213     public void addUsePosition(Integer index, InstructionType type) {
214         usePositions.put(index, type);
215     }
216 
217     /**
218      * Check if this vreg is alive at a given index.
219      * 
220      * @param atIndex
221      *            the index at which to see if this register is live.
222      */
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     /**
234      * The range in this interval in which the LIR instruction with the given id
235      * is live, or null. This will never return null if called for an interval
236      * from the active list after it has been set up by the allocate method.
237      * 
238      * @param id
239      *            LIR instruction id.
240      * @return range in which LIR instruction with given id is live, or null.
241      */
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     /**
253      * Write the interval information to STDOUT.
254      * 
255      * @param p
256      *            for pretty printing with indentation.
257      */
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     /**
304      * The start position for the first range.
305      * 
306      * @return the start position.
307      */
308 
309     public int firstRangeStart() {
310         if (ranges.isEmpty())
311             return -1;
312         else
313             return ranges.get(0).start;
314     }
315 
316     /**
317      * The stop position for the last range.
318      * 
319      * @return the stop position.
320      */
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     /**
330      * Compare start positions (for ordering intervals).
331      * 
332      * @param other
333      *            interval to compare to.
334      * 
335      * @return ordering value.
336      */
337 
338     public int compareTo(NInterval other) {
339         return this.firstRangeStart() - other.firstRangeStart();
340     }
341 
342     /**
343      * Two intervals are equal if they have the same virtual register ID.
344      * 
345      * @param other
346      *            the interval we are comparing ourself with.
347      * @return true if the two intervals are the same, false otherwise.
348      */
349 
350     public boolean equals(NInterval other) {
351         return (this.vRegId == other.vRegId);
352     }
353 
354     /**
355      * Split the current interval at the given index. Responsible for splitting
356      * a range if the index falls on one, moving remaining ranges over to child,
357      * and moving appropriate usePositions over to the child.
358      * 
359      * @param idx
360      *            the index at which this interval is to be split
361      * 
362      * @return the child interval which is to be sorted onto unhandled. If there
363      *         was no child created in the case of a pruning this interval is
364      *         returned.
365      */
366 
367     public NInterval splitAt(int idx) {
368 
369         ArrayList<NRange> childsRanges = new ArrayList<NRange>();
370         if (this.isLiveAt(idx)) { // means split falls on a range
371             // Assumptions: if a range is LIVE on an index, then there
372             // exist usePositions at or before the index
373             // within this same range.
374             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         // The following two for loops take care of any untouched ranges
381         // which start after the split position and must be moved to the
382         // child interval.
383         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); // expand size of cfg.registers to
395         // avoid null pointer exception when printing.
396 
397         // transfer remaining use positions
398         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     /**
407      * The parent interval.
408      * 
409      * @return the parent interval.
410      */
411 
412     private NInterval getParent() {
413         if (parent != null)
414             return parent;
415         else
416             return this;
417     }
418 
419     /**
420      * The child interval at a given instruction index.
421      * 
422      * @param idx
423      *            The instruction index.
424      * @return the child interval.
425      */
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     /**
437      * A child of this interval which is live or ends before the given basic
438      * block's end.
439      * 
440      * @param b
441      *            the basic block.
442      * @return the child of this interval which ends at or nearest (before) this
443      *         basic block's end (last lir instruction index).
444      */
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             // get the child which ends before idx but also ends closest to idx
456             if (child.lastNRangeStop() < idx
457                     && child.lastNRangeStop() > highestEndingAllowed) {
458                 tmp = child;
459                 highestEndingAllowed = tmp.lastNRangeStop();
460             }
461         }
462         return tmp;
463     }
464 
465     /**
466      * The child of this interval which is live or starts after the given basic
467      * block's start
468      * 
469      * @param b
470      *            the basic block
471      * @return the child of this interval which starts at or nearest (after)
472      *         this basic block's start (fist lir instruction index).
473      */
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();// block's end
483         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     /**
494      * Returns the basic block in which this interval's start position falls.
495      * 
496      * @return basic block in which this interval's start position falls.
497      */
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; // this will never happen
506     }
507 
508     /**
509      * The basic block in which this interval's end position falls.
510      * 
511      * @return the basic block number.
512      */
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; // this will never happen
522     }
523 
524     /**
525      * Assigns an offset to this interval (if one hasn't been already assigned).
526      * Assigns that same offset to any (newly created) children.
527      */
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     // The following two methods are used for insertion of move instructions
544     // for spills.
545 
546     /**
547      * Is this interval a child interval?
548      * 
549      * @return true or false.
550      */
551 
552     public boolean isChild() {
553         if (this.parent != null) {
554             return true;
555         } else {
556             return false;
557         }
558     }
559 
560     /**
561      * Is this interval a parent interval? (Ie, does it have children?)
562      * 
563      * @return true or false.
564      */
565 
566     public boolean isParent() {
567         return !this.children.isEmpty();
568     }
569 
570 }
571 
572 /** The types of stack pointers. **/
573 enum OffsetFrom {
574     FP, SP
575 };
576 
577 /** The types of possible uses. */
578 enum InstructionType {
579     read, write
580 };
581 
582 /**
583  * A liveness range (for an interval).
584  */
585 
586 class NRange implements Comparable<NRange> {
587 
588     /** The range's start position. */
589     public int start;
590 
591     /** The range's stop position. */
592     public int stop;
593 
594     /**
595      * Construct a liveness range extending from start to stop (positions in the
596      * code).
597      * 
598      * @param start
599      *            start position.
600      * @param stop
601      *            stop position.
602      */
603     public NRange(int start, int stop) {
604         this.start = start;
605         this.stop = stop;
606 
607     }
608 
609     /**
610      * Mutates current range to be only as long as the split point and returns
611      * the remainder as a new range.
612      * 
613      * @param newStart
614      *            the split location
615      * @param oldStop
616      *            the split location
617      * @return the new NRange which begins at the split position and runs to the
618      *         end of this previously whole range.
619      */
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     /**
629      * Does this liveness range overlap with another?
630      * 
631      * @param a
632      *            The other range.
633      * @return true or false.
634      */
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     /**
651      * One liveness range comes before another if its start position comes
652      * before the other's start position.
653      * 
654      * @param other
655      *            the other range.
656      * 
657      * @return comparison.
658      */
659 
660     public int compareTo(NRange other) {
661         return this.start - other.start;
662     }
663 
664     /**
665      * The string representation of the range.
666      * 
667      * @return "[start,stop]"
668      */
669 
670     public String toString() {
671         return "[" + start + ", " + stop + "]";
672     }
673 
674 }
675