001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.regalloc;
014
015 import java.lang.reflect.Constructor;
016 import java.util.ArrayList;
017 import java.util.Comparator;
018 import java.util.Enumeration;
019 import java.util.HashMap;
020 import java.util.HashSet;
021 import java.util.Iterator;
022 import java.util.Map;
023 import java.util.SortedSet;
024 import java.util.TreeSet;
025
026 import org.jikesrvm.VM;
027 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalRegisterConstants;
028 import org.jikesrvm.ArchitectureSpecificOpt.PhysicalRegisterSet;
029 import org.jikesrvm.ArchitectureSpecificOpt.RegisterRestrictions;
030 import org.jikesrvm.ArchitectureSpecificOpt.StackManager;
031 import org.jikesrvm.compilers.opt.OptOptions;
032 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
033 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
034 import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
035 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
036 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
037 import org.jikesrvm.compilers.opt.ir.BasicBlock;
038 import org.jikesrvm.compilers.opt.ir.ControlFlowGraph;
039 import org.jikesrvm.compilers.opt.ir.GCIRMapElement;
040 import org.jikesrvm.compilers.opt.ir.IR;
041 import org.jikesrvm.compilers.opt.ir.Instruction;
042 import org.jikesrvm.compilers.opt.ir.Operators;
043 import org.jikesrvm.compilers.opt.ir.RegSpillListElement;
044 import org.jikesrvm.compilers.opt.ir.Register;
045 import org.jikesrvm.compilers.opt.ir.operand.AddressConstantOperand;
046 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
047 import org.jikesrvm.compilers.opt.ir.operand.LongConstantOperand;
048 import org.jikesrvm.compilers.opt.ir.operand.Operand;
049 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
050 import org.jikesrvm.compilers.opt.util.GraphEdge;
051 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
052 import org.jikesrvm.osr.OSRConstants;
053 import org.jikesrvm.osr.LocalRegPair;
054 import org.jikesrvm.osr.MethodVariables;
055 import org.jikesrvm.osr.VariableMapElement;
056 import org.vmmagic.unboxed.Word;
057
058 /**
059 * Main driver for linear scan register allocation.
060 */
061 public final class LinearScan extends OptimizationPlanCompositeElement {
062
063 /**
064 * Build this phase as a composite of others.
065 */
066 LinearScan() {
067 super("Linear Scan Composite Phase",
068 new OptimizationPlanElement[]{new OptimizationPlanAtomicElement(new IntervalAnalysis()),
069 new OptimizationPlanAtomicElement(new RegisterRestrictionsPhase()),
070 new OptimizationPlanAtomicElement(new LinearScanPhase()),
071 new OptimizationPlanAtomicElement(new UpdateGCMaps1()),
072 new OptimizationPlanAtomicElement(new SpillCode()),
073 new OptimizationPlanAtomicElement(new UpdateGCMaps2()),
074 new OptimizationPlanAtomicElement(new UpdateOSRMaps()),});
075 }
076
077 /**
078 * Mark FMOVs that end a live range?
079 */
080 private static final boolean MUTATE_FMOV = VM.BuildForIA32;
081
082 /*
083 * debug flags
084 */
085 private static final boolean DEBUG = false;
086 private static final boolean VERBOSE_DEBUG = false;
087 private static final boolean GC_DEBUG = false;
088 private static final boolean DEBUG_COALESCE = false;
089
090 /**
091 * Register allocation is required
092 */
093 @Override
094 public boolean shouldPerform(OptOptions options) {
095 return true;
096 }
097
098 @Override
099 public String getName() {
100 return "Linear Scan Composite Phase";
101 }
102
103 @Override
104 public boolean printingEnabled(OptOptions options, boolean before) {
105 return false;
106 }
107
108 /**
109 * Associates the passed live interval with the passed register, using
110 * the scratchObject field of Register.
111 *
112 * @param reg the register
113 * @param interval the live interval
114 */
115 static void setInterval(Register reg, CompoundInterval interval) {
116 reg.scratchObject = interval;
117 }
118
119 /**
120 * Returns the interval associated with the passed register.
121 * @param reg the register
122 * @return the live interval or {@code null}
123 */
124 static CompoundInterval getInterval(Register reg) {
125 return (CompoundInterval) reg.scratchObject;
126 }
127
128 /**
129 * returns the dfn associated with the passed instruction
130 * @param inst the instruction
131 * @return the associated dfn
132 */
133 static int getDFN(Instruction inst) {
134 return inst.scratch;
135 }
136
137 /**
138 * Associates the passed dfn number with the instruction
139 * @param inst the instruction
140 * @param dfn the dfn number
141 */
142 static void setDFN(Instruction inst, int dfn) {
143 inst.scratch = dfn;
144 }
145
146 /**
147 * Print the DFN numbers associated with each instruction
148 */
149 static void printDfns(IR ir) {
150 System.out.println("DFNS: **** " + ir.getMethod() + "****");
151 for (Instruction inst = ir.firstInstructionInCodeOrder(); inst != null; inst =
152 inst.nextInstructionInCodeOrder()) {
153 System.out.println(getDFN(inst) + " " + inst);
154 }
155 }
156
157 /**
158 * Return the Depth-first-number of the end of the live interval.
159 * Return the dfn for the end of the basic block if the interval is
160 * open-ended.
161 */
162 static int getDfnEnd(LiveIntervalElement live, BasicBlock bb) {
163 Instruction end = live.getEnd();
164 int dfnEnd;
165 if (end != null) {
166 dfnEnd = getDFN(end);
167 } else {
168 dfnEnd = getDFN(bb.lastInstruction());
169 }
170 return dfnEnd;
171 }
172
173 /**
174 * Return the Depth-first-number of the beginning of the live interval.
175 * Return the dfn for the beginning of the basic block if the interval is
176 * open-ended.
177 */
178 static int getDfnBegin(LiveIntervalElement live, BasicBlock bb) {
179 Instruction begin = live.getBegin();
180 int dfnBegin;
181 if (begin != null) {
182 dfnBegin = getDFN(begin);
183 } else {
184 dfnBegin = getDFN(bb.firstInstruction());
185 }
186 return dfnBegin;
187 }
188
189 public static final class LinearScanState {
190 /**
191 * The live interval information, a set of Basic Intervals
192 * sorted by increasing start point
193 */
194 public final ArrayList<BasicInterval> intervals = new ArrayList<BasicInterval>();
195
196 /**
197 * Was any register spilled?
198 */
199 public boolean spilledSomething = false;
200
201 /**
202 * Analysis information used by linear scan.
203 */
204 public ActiveSet active;
205 }
206
207 /**
208 * A phase to compute register restrictions.
209 */
210 static final class RegisterRestrictionsPhase extends CompilerPhase {
211
212 /**
213 * Return this instance of this phase. This phase contains no
214 * per-compilation instance fields.
215 * @param ir not used
216 * @return this
217 */
218 @Override
219 public CompilerPhase newExecution(IR ir) {
220 return this;
221 }
222
223 @Override
224 public boolean shouldPerform(OptOptions options) {
225 return true;
226 }
227
228 @Override
229 public String getName() {
230 return "Register Restrictions";
231 }
232
233 @Override
234 public boolean printingEnabled(OptOptions options, boolean before) {
235 return false;
236 }
237
238 /**
239 * @param ir the IR
240 */
241 @Override
242 public void perform(IR ir) {
243
244 // The registerManager has already been initialized
245 GenericStackManager sm = ir.stackManager;
246
247 // Set up register restrictions
248 sm.computeRestrictions(ir);
249 }
250 }
251
252 public static final class LinearScanPhase extends CompilerPhase
253 implements PhysicalRegisterConstants, Operators {
254
255 /**
256 * An object which manages spill location assignments.
257 */
258 private SpillLocationManager spillManager;
259
260 /**
261 * The governing IR
262 * Also used by ClassWriter
263 */
264 public IR ir;
265
266 /**
267 * Constructor for this compiler phase
268 */
269 private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(LinearScanPhase.class);
270
271 /**
272 * Get a constructor object for this compiler phase
273 * @return compiler phase constructor
274 */
275 @Override
276 public Constructor<CompilerPhase> getClassConstructor() {
277 return constructor;
278 }
279
280 /**
281 * Register allocation is required
282 */
283 @Override
284 public boolean shouldPerform(OptOptions options) {
285 return true;
286 }
287
288 @Override
289 public String getName() {
290 return "Linear Scan";
291 }
292
293 @Override
294 public boolean printingEnabled(OptOptions options, boolean before) {
295 return false;
296 }
297
298 /**
299 * Perform the linear scan register allocation algorithm.<p>
300 *
301 * See TOPLAS 21(5), Sept 1999, p 895-913
302 * @param ir the IR
303 */
304 @Override
305 public void perform(IR ir) {
306
307 this.ir = ir;
308
309 // The registerManager has already been initialized
310 //GenericStackManager sm = ir.stackManager;
311
312 // Get register restrictions
313 // RegisterRestrictions restrict = sm.getRestrictions(); - unused
314
315 // Create the object that manages spill locations
316 spillManager = new SpillLocationManager(ir);
317
318 // Create an (empty) set of active intervals.
319 ActiveSet active = new ActiveSet(ir, spillManager);
320 ir.MIRInfo.linearScanState.active = active;
321
322 // Intervals sorted by increasing start point
323 for (BasicInterval b : ir.MIRInfo.linearScanState.intervals) {
324
325 MappedBasicInterval bi = (MappedBasicInterval) b;
326 CompoundInterval ci = bi.container;
327
328 active.expireOldIntervals(bi);
329
330 // If the interval does not correspond to a physical register
331 // then we process it.
332 if (!ci.getRegister().isPhysical()) {
333 // Update register allocation based on the new interval.
334 active.allocate(bi, ci);
335 } else {
336 // Mark the physical register as currently allocated.
337 ci.getRegister().allocateRegister();
338 }
339 active.add(bi);
340 }
341
342 // update the state.
343 if (active.spilledSomething()) {
344 ir.MIRInfo.linearScanState.spilledSomething = true;
345 }
346 }
347 }
348
349 /**
350 * Implements a basic live interval (no holes), which is a pair
351 * <pre>
352 * begin - the starting point of the interval
353 * end - the ending point of the interval
354 * </pre>
355 *
356 * <p> Begin and end are numbers given to each instruction by a numbering pass.
357 */
358 static class BasicInterval {
359
360 /**
361 * DFN of the beginning instruction of this interval
362 */
363 private final int begin;
364 /**
365 * DFN of the last instruction of this interval
366 */
367 private int end;
368
369 /**
370 * Default constructor.
371 */
372 BasicInterval(int begin, int end) {
373 this.begin = begin;
374 this.end = end;
375 }
376
377 /**
378 * @return the DFN signifying the beginning of this basic interval
379 */
380 final int getBegin() {
381 return begin;
382 }
383
384 /**
385 * @return the DFN signifying the end of this basic interval
386 */
387 final int getEnd() {
388 return end;
389 }
390
391 /**
392 * Extend a live interval to a new endpoint
393 */
394 final void setEnd(int newEnd) {
395 end = newEnd;
396 }
397
398 /**
399 * Does this interval start after dfn?
400 * @param dfn the depth first numbering to compare to
401 */
402 final boolean startsAfter(int dfn) {
403 return begin > dfn;
404 }
405
406 /**
407 * Does this interval start before dfn?
408 * @param dfn the depth first numbering to compare to
409 */
410 final boolean startsBefore(int dfn) {
411 return begin < dfn;
412 }
413
414 /**
415 * Does this interval contain a dfn?
416 * @param dfn the depth first numbering to compare to
417 */
418 final boolean contains(int dfn) {
419 return begin <= dfn && end >= dfn;
420 }
421
422 /**
423 * Does this interval start before another?
424 * @param i the interval to compare with
425 */
426 final boolean startsBefore(BasicInterval i) {
427 return begin < i.begin;
428 }
429
430 /**
431 * Does this interval end after another?
432 * @param i the interval to compare with
433 */
434 final boolean endsAfter(BasicInterval i) {
435 return end > i.end;
436 }
437
438 /**
439 * Does this interval represent the same range as another?
440 * @param i the interval to compare with
441 */
442 final boolean sameRange(BasicInterval i) {
443 return begin == i.begin && end == i.end;
444 }
445
446 /**
447 * Redefine equals
448 */
449 @Override
450 public boolean equals(Object o) {
451 if (!(o instanceof BasicInterval)) return false;
452
453 BasicInterval i = (BasicInterval) o;
454 return sameRange(i);
455 }
456
457 /**
458 * Does this interval end before dfn
459 * @param dfn the depth first numbering to compare to
460 */
461 final boolean endsBefore(int dfn) {
462 return end < dfn;
463 }
464
465 /**
466 * Does this interval end after dfn
467 * @param dfn the depth first numbering to compare to
468 */
469 final boolean endsAfter(int dfn) {
470 return end > dfn;
471 }
472
473 /**
474 * Does this interval intersect with another?
475 */
476 final boolean intersects(BasicInterval i) {
477 int iBegin = i.getBegin();
478 int iEnd = i.getEnd();
479 return !(endsBefore(iBegin + 1) || startsAfter(iEnd - 1));
480 }
481
482 /**
483 * Return a String representation
484 */
485 @Override
486 public String toString() {
487 String s = "[ " + begin + ", " + end + " ] ";
488 return s;
489 }
490 }
491
492 /**
493 * A basic interval contained in a CompoundInterval.
494 */
495 static class MappedBasicInterval extends BasicInterval {
496 final CompoundInterval container;
497
498 MappedBasicInterval(BasicInterval b, CompoundInterval c) {
499 super(b.begin, b.end);
500 this.container = c;
501 }
502
503 MappedBasicInterval(int begin, int end, CompoundInterval c) {
504 super(begin, end);
505 this.container = c;
506 }
507
508 /**
509 * Redefine equals
510 */
511 @Override
512 public boolean equals(Object o) {
513 if (super.equals(o)) {
514 MappedBasicInterval i = (MappedBasicInterval) o;
515 return container == i.container;
516 } else {
517 return false;
518 }
519 }
520
521 @Override
522 public String toString() {
523 return "<" + container.getRegister() + ">:" + super.toString();
524 }
525
526 }
527
528 /**
529 * Implements a live interval with holes; ie; a list of basic live
530 * intervals.
531 */
532 static class CompoundInterval extends IncreasingStartIntervalSet {
533 /** Support for Set serialization */
534 static final long serialVersionUID = 7423553044815762071L;
535 /**
536 * Is this compound interval fully contained in infrequent code?
537 */
538 private boolean _infrequent = true;
539
540 final void setFrequent() { _infrequent = false; }
541
542 final boolean isInfrequent() { return _infrequent; }
543
544 /**
545 * The register this compound interval represents
546 */
547 private final Register reg;
548
549 /**
550 * A spill location assigned for this interval.
551 */
552 private SpillLocationInterval spillInterval;
553
554 SpillLocationInterval getSpillInterval() { return spillInterval; }
555
556 /**
557 * Return the register this interval represents
558 */
559 Register getRegister() {
560 return reg;
561 }
562
563 /**
564 * Create a new compound interval of a single Basic interval
565 */
566 CompoundInterval(int dfnBegin, int dfnEnd, Register register) {
567 BasicInterval newInterval = new MappedBasicInterval(dfnBegin, dfnEnd, this);
568 add(newInterval);
569 reg = register;
570 }
571
572 /**
573 * Create a new compound interval of a single Basic interval
574 */
575 CompoundInterval(BasicInterval i, Register register) {
576 BasicInterval newInterval = new MappedBasicInterval(i.getBegin(), i.getEnd(), this);
577 add(newInterval);
578 reg = register;
579 }
580
581 /**
582 * Dangerous constructor: use with care.
583 */
584 CompoundInterval(Register r) {
585 reg = r;
586 }
587
588 /**
589 * Copy the ranges into a new interval associated with a register r.
590 */
591 CompoundInterval copy(Register r) {
592 CompoundInterval result = new CompoundInterval(r);
593
594 for (Iterator<BasicInterval> i = iterator(); i.hasNext();) {
595 BasicInterval b = i.next();
596 result.add(b);
597 }
598 return result;
599 }
600
601 /**
602 * Copy the ranges into a new interval associated with a register r.
603 * Copy only the basic intervals up to and including stop.
604 */
605 CompoundInterval copy(Register r, BasicInterval stop) {
606 CompoundInterval result = new CompoundInterval(r);
607
608 for (Iterator<BasicInterval> i = iterator(); i.hasNext();) {
609 BasicInterval b = i.next();
610 result.add(b);
611 if (b.sameRange(stop)) return result;
612 }
613 return result;
614 }
615
616 /**
617 * Add a new live range to this compound interval.
618 *
619 * @param live the new live range
620 * @param bb the basic block for live
621 * @return the new basic interval if one was created; null otherwise
622 */
623 BasicInterval addRange(LiveIntervalElement live, BasicBlock bb) {
624
625 if (shouldConcatenate(live, bb)) {
626 // concatenate with the last basic interval
627 BasicInterval last = last();
628 last.setEnd(getDfnEnd(live, bb));
629 return null;
630 } else {
631 // create a new basic interval and append it to the list.
632 BasicInterval newInterval = new MappedBasicInterval(getDfnBegin(live, bb), getDfnEnd(live, bb), this);
633 add(newInterval);
634 return newInterval;
635 }
636 }
637
638 /**
639 * Should we simply merge the live interval <code>live</code> into a
640 * previous BasicInterval?
641 *
642 * @param live the live interval being queried
643 * @param bb the basic block in which live resides.
644 */
645 private boolean shouldConcatenate(LiveIntervalElement live, BasicBlock bb) {
646
647 BasicInterval last = last();
648
649 // Make sure the new live range starts after the last basic interval
650 if (VM.VerifyAssertions) {
651 VM._assert(last.getEnd() <= getDfnBegin(live, bb));
652 }
653
654 int dfnBegin = getDfnBegin(live, bb);
655 if (live.getBegin() != null) {
656 if (live.getBegin() == bb.firstRealInstruction()) {
657 // live starts the basic block. Now make sure it is contiguous
658 // with the last interval.
659 return last.getEnd() + 1 >= dfnBegin;
660 } else {
661 // live does not start the basic block. Merge with last iff
662 // last and live share an instruction. This happens when a
663 // register is def'ed and use'd in the same instruction.
664 return last.getEnd() == dfnBegin;
665 }
666 } else {
667 // live.getBegin == null.
668 // Merge if it is contiguous with the last interval.
669 int dBegin = getDFN(bb.firstInstruction());
670 return last.getEnd() + 1 >= dBegin;
671 }
672 }
673
674 /**
675 * Assign this compound interval to a free spill location.
676 *
677 * @param spillManager governing spill location manager
678 */
679 void spill(SpillLocationManager spillManager) {
680 spillInterval = spillManager.findOrCreateSpillLocation(this);
681 RegisterAllocatorState.setSpill(reg, spillInterval.getOffset());
682 RegisterAllocatorState.clearOneToOne(reg);
683 if (VERBOSE_DEBUG) {
684 System.out.println("Assigned " + reg + " to location " + spillInterval.getOffset());
685 }
686 }
687
688 /**
689 * Has this interval been spilled?
690 */
691 boolean isSpilled() {
692 return (RegisterAllocatorState.getSpill(getRegister()) != 0);
693 }
694
695 /**
696 * Assign this compound interval to a physical register.
697 */
698 void assign(Register r) {
699 getRegister().allocateToRegister(r);
700 }
701
702 /**
703 * Has this interval been assigned to a physical register?
704 */
705 boolean isAssigned() {
706 return (RegisterAllocatorState.getMapping(getRegister()) != null);
707 }
708
709 /**
710 * Get the physical register this interval is assigned to. null if
711 * none assigned.
712 */
713 Register getAssignment() {
714 return RegisterAllocatorState.getMapping(getRegister());
715 }
716
717 /**
718 * Merge this interval with another, non-intersecting interval.
719 * Precondition: BasicInterval stop is an interval in i. This version
720 * will only merge basic intervals up to and including stop into this.
721 */
722 void addNonIntersectingInterval(CompoundInterval i, BasicInterval stop) {
723 SortedSet<BasicInterval> headSet = i.headSetInclusive(stop);
724 addAll(headSet);
725 }
726
727 /**
728 * Compute the headSet() [from java.util.SortedSet] but include all
729 * elements less than upperBound <em>inclusive</em>
730 */
731 SortedSet<BasicInterval> headSetInclusive(BasicInterval upperBound) {
732 BasicInterval newUpperBound = new BasicInterval(upperBound.getBegin() + 1, upperBound.getEnd());
733 return headSet(newUpperBound);
734 }
735
736 /**
737 * Compute the headSet() [from java.util.SortedSet] but include all
738 * elements less than upperBound <em>inclusive</em>
739 */
740 SortedSet<BasicInterval> headSetInclusive(int upperBound) {
741 BasicInterval newUpperBound = new BasicInterval(upperBound + 1, upperBound + 1);
742 return headSet(newUpperBound);
743 }
744
745 /**
746 * Compute the tailSet() [from java.util.SortedSet] but include all
747 * elements greater than lowerBound <em>inclusive</em>
748 */
749 SortedSet<BasicInterval> tailSetInclusive(int lowerBound) {
750 BasicInterval newLowerBound = new BasicInterval(lowerBound - 1, lowerBound - 1);
751 return tailSet(newLowerBound);
752 }
753
754 /**
755 * Remove some basic intervals from this compound interval, and return
756 * the intervals actually removed.
757 *
758 * PRECONDITION: all basic intervals in i must appear in this compound
759 * interval, unless they end after the end of this interval
760 */
761 CompoundInterval removeIntervalsAndCache(CompoundInterval i) {
762 CompoundInterval result = new CompoundInterval(i.getRegister());
763 Iterator<BasicInterval> myIterator = iterator();
764 Iterator<BasicInterval> otherIterator = i.iterator();
765 BasicInterval current = myIterator.hasNext() ? myIterator.next() : null;
766 BasicInterval currentI = otherIterator.hasNext() ? otherIterator.next() : null;
767
768 while (currentI != null && current != null) {
769 if (current.startsBefore(currentI)) {
770 current = myIterator.hasNext() ? myIterator.next() : null;
771 } else if (currentI.startsBefore(current)) {
772 currentI = otherIterator.hasNext() ? otherIterator.next() : null;
773 } else {
774 if (VM.VerifyAssertions) VM._assert(current.sameRange(currentI));
775
776 currentI = otherIterator.hasNext() ? otherIterator.next() : null;
777 BasicInterval next = myIterator.hasNext() ? myIterator.next() : null;
778 // add the interval to the cache
779 result.add(current);
780 current = next;
781 }
782 }
783
784 // SJF: the loop as written is slightly more efficient than calling
785 // removeAll(). However, for some reason, replacing the loop with
786 // the call to removeAll breaks the compiler on OptTestHarness
787 // -oc:O2 -method RVMMethod replaceCharWithString -. This is deeply
788 // disturbing. TODO: fix it. (Hope the problem goes away if/when
789 // we migrate to classpath libraries).
790 // removeAll(result);
791 for (BasicInterval b : result) {
792 remove(b);
793 }
794
795 return result;
796 }
797
798 /**
799 * SJF: Apparently our java.util implementation of removeAll()
800 * doesn't work. Perhaps I've somehow screwed up the comparator with
801 * the "consistent with equals" property?
802 * It breaks javalex on BaseOptMarkSweep on IA32
803 * Hopefully this problem will go away if/when we switch to classpath.
804 * Else, perhaps I'll ditch use of java.util Collections and write my
805 * own collection classes.
806 * In the meantime, here's an ugly hack to get around the problem.
807 */
808 void removeAll(CompoundInterval c) {
809 for (BasicInterval b : c) {
810 remove(b);
811 }
812 }
813
814 /**
815 * Return the lowest DFN in this compound interval.
816 */
817 int getLowerBound() {
818 BasicInterval b = first();
819 return b.getBegin();
820 }
821
822 /**
823 * Return the highest DFN in this compound interval.
824 */
825 int getUpperBound() {
826 BasicInterval b = last();
827 return b.getEnd();
828 }
829
830 /**
831 * Does this interval intersect with i?
832 */
833 boolean intersects(CompoundInterval i) {
834
835 if (isEmpty()) return false;
836 if (i.isEmpty()) return false;
837
838 // Walk over the basic intervals of this interval and i.
839 // Restrict the walking to intervals that might intersect.
840 int lower = Math.max(getLowerBound(), i.getLowerBound());
841 int upper = Math.min(getUpperBound(), i.getUpperBound());
842
843 // we may have to move one interval lower on each side.
844 BasicInterval b = getBasicInterval(lower);
845 int myLower = (b == null) ? lower : b.getBegin();
846 if (myLower > upper) return false;
847 b = i.getBasicInterval(lower);
848 int otherLower = (b == null) ? lower : b.getBegin();
849 if (otherLower > upper) return false;
850
851 SortedSet<BasicInterval> myTailSet = tailSetInclusive(myLower);
852 SortedSet<BasicInterval> otherTailSet = i.tailSetInclusive(otherLower);
853 Iterator<BasicInterval> myIterator = myTailSet.iterator();
854 Iterator<BasicInterval> otherIterator = otherTailSet.iterator();
855
856 BasicInterval current = myIterator.hasNext() ? myIterator.next() : null;
857 BasicInterval currentI = otherIterator.hasNext() ? otherIterator.next() : null;
858
859 while (current != null && currentI != null) {
860 if (current.getBegin() > upper) break;
861 if (currentI.getBegin() > upper) break;
862 if (current.intersects(currentI)) return true;
863
864 if (current.startsBefore(currentI)) {
865 current = myIterator.hasNext() ? myIterator.next() : null;
866 } else {
867 currentI = otherIterator.hasNext() ? otherIterator.next() : null;
868 }
869 }
870 return false;
871 }
872
873 /**
874 * Return the first basic interval that contains a given
875 * instruction.
876 *
877 * If there is no such interval, return null;
878 * @param s The instruction in question
879 */
880 BasicInterval getBasicInterval(Instruction s) {
881 return getBasicInterval(getDFN(s));
882 }
883
884 /**
885 * Return the first basic interval that contains the given
886 * instruction.
887 *
888 * If there is no such interval, return null;
889 * @param n The DFN of the instruction in question
890 */
891 BasicInterval getBasicInterval(int n) {
892 SortedSet<BasicInterval> headSet = headSetInclusive(n);
893 if (!headSet.isEmpty()) {
894 BasicInterval last = headSet.last();
895 return last.contains(n) ? last : null;
896 } else {
897 return null;
898 }
899 }
900
901 /**
902 * Make a String representation
903 */
904 @Override
905 public String toString() {
906 String str = "[" + getRegister() + "]:";
907 for (Iterator<BasicInterval> i = iterator(); i.hasNext();) {
908 BasicInterval b = i.next();
909 str = str + b;
910 }
911 return str;
912 }
913 }
914
915 /**
916 * "Active set" for linear scan register allocation.
917 * This version is maintained sorted in order of increasing
918 * live interval end point.
919 */
920 static final class ActiveSet extends IncreasingEndMappedIntervalSet {
921 /** Support for Set serialization */
922 static final long serialVersionUID = 2570397490575294294L;
923 /**
924 * Governing ir
925 */
926 private final IR ir;
927
928 /**
929 * Manager of spill locations;
930 */
931 private final SpillLocationManager spillManager;
932
933 /**
934 * An object to help estimate spill costs
935 */
936 private final transient SpillCostEstimator spillCost;
937
938 /**
939 * Have we spilled anything?
940 */
941 private boolean spilled;
942
943 /**
944 * Default constructor
945 */
946 ActiveSet(IR ir, SpillLocationManager sm) {
947 super();
948 spilled = false;
949 this.ir = ir;
950 this.spillManager = sm;
951
952 switch (ir.options.REGALLOC_SPILL_COST_ESTIMATE) {
953 case OptOptions.REGALLOC_SIMPLE_SPILL_COST:
954 spillCost = new SimpleSpillCost(ir);
955 break;
956 case OptOptions.REGALLOC_BRAINDEAD_SPILL_COST:
957 spillCost = new BrainDeadSpillCost(ir);
958 break;
959 case OptOptions.REGALLOC_BLOCK_COUNT_SPILL_COST:
960 spillCost = new BlockCountSpillCost(ir);
961 break;
962 default:
963 OptimizingCompilerException.UNREACHABLE("unsupported spill cost");
964 spillCost = null;
965 }
966 }
967
968 /**
969 * Have we spilled anything?
970 */
971 boolean spilledSomething() {
972 return spilled;
973 }
974
975 /**
976 * For each new basic interval, we scan the list of active basic
977 * intervals in order of increasing end point. We remove any "expired"
978 * intervals - those
979 * intervals that no longer overlap the new interval because their
980 * end point precedes the new interval's start point - and makes the
981 * corresponding register available for allocation
982 *
983 * @param newInterval the new interval
984 */
985 void expireOldIntervals(BasicInterval newInterval) {
986
987 for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
988 MappedBasicInterval bi = (MappedBasicInterval) e.next();
989
990 // break out of the loop when we reach an interval that is still
991 // alive
992 int newStart = newInterval.getBegin();
993 if (bi.endsAfter(newStart)) break;
994
995 if (VERBOSE_DEBUG) System.out.println("Expire " + bi);
996
997 // note that the bi interval no longer is live
998 freeInterval(bi);
999
1000 // remove bi from the active set
1001 e.remove();
1002
1003 }
1004 }
1005
1006 /**
1007 * Take action when a basic interval becomes inactive
1008 */
1009 void freeInterval(MappedBasicInterval bi) {
1010 CompoundInterval container = bi.container;
1011 Register r = container.getRegister();
1012
1013 if (r.isPhysical()) {
1014 r.deallocateRegister();
1015 return;
1016 }
1017
1018 if (container.isSpilled()) {
1019 // free the spill location iff this is the last interval in the
1020 // compound interval.
1021 BasicInterval last = container.last();
1022 if (last.sameRange(bi)) {
1023 spillManager.freeInterval(container.getSpillInterval());
1024 }
1025 } else {
1026 // free the assigned register
1027 if (VM.VerifyAssertions) VM._assert(container.getAssignment().isAllocated());
1028 container.getAssignment().deallocateRegister();
1029 }
1030
1031 }
1032
1033 /**
1034 * Assign a basic interval to either a register or a spill location.
1035 */
1036 void allocate(BasicInterval newInterval, CompoundInterval container) {
1037
1038 if (DEBUG) {
1039 System.out.println("Allocate " + newInterval + " " + container.getRegister());
1040 }
1041
1042 Register r = container.getRegister();
1043
1044 if (container.isSpilled()) {
1045 // We previously decided to spill the compound interval. No further
1046 // action is needed.
1047 if (VERBOSE_DEBUG) System.out.println("Previously spilled " + container);
1048 } else {
1049 if (container.isAssigned()) {
1050 // The compound interval was previously assigned to a physical
1051 // register.
1052 Register phys = container.getAssignment();
1053 if (!currentlyActive(phys)) {
1054 // The assignment of newInterval to phys is still OK.
1055 // Update the live ranges of phys to include the new basic
1056 // interval
1057 if (VERBOSE_DEBUG) {
1058 System.out.println("Previously assigned to " +
1059 phys +
1060 " " +
1061 container +
1062 " phys interval " +
1063 getInterval(phys));
1064 }
1065 updatePhysicalInterval(phys, newInterval);
1066 if (VERBOSE_DEBUG) {
1067 System.out.println(" now phys interval " + getInterval(phys));
1068 }
1069 // Mark the physical register as currently allocated
1070 phys.allocateRegister();
1071 } else {
1072 // The previous assignment is not OK, since the physical
1073 // register is now in use elsewhere.
1074 if (DEBUG) {
1075 System.out.println("Previously assigned, " + phys + " " + container);
1076 }
1077 // first look and see if there's another free register for
1078 // container.
1079 if (VERBOSE_DEBUG) System.out.println("Looking for free register");
1080 Register freeR = findAvailableRegister(container);
1081 if (VERBOSE_DEBUG) System.out.println("Free register? " + freeR);
1082
1083 if (freeR == null) {
1084 // Did not find a free register to assign. So, spill one of
1085 // the two intervals concurrently allocated to phys.
1086
1087 CompoundInterval currentAssignment = getCurrentInterval(phys);
1088 // choose which of the two intervals to spill
1089 double costA = spillCost.getCost(container.getRegister());
1090 double costB = spillCost.getCost(currentAssignment.getRegister());
1091 if (VERBOSE_DEBUG) {
1092 System.out.println("Current assignment " + currentAssignment + " cost " + costB);
1093 }
1094 if (VERBOSE_DEBUG) {
1095 System.out.println("Cost of spilling" + container + " cost " + costA);
1096 }
1097 CompoundInterval toSpill = (costA < costB) ? container : currentAssignment;
1098 // spill it.
1099 Register p = toSpill.getAssignment();
1100 toSpill.spill(spillManager);
1101 spilled = true;
1102 if (VERBOSE_DEBUG) {
1103 System.out.println("Spilled " + toSpill + " from " + p);
1104 }
1105 CompoundInterval physInterval = getInterval(p);
1106 physInterval.removeAll(toSpill);
1107 if (VERBOSE_DEBUG) System.out.println(" after spill phys" + getInterval(p));
1108 if (toSpill != container) updatePhysicalInterval(p, newInterval);
1109 if (VERBOSE_DEBUG) {
1110 System.out.println(" now phys interval " + getInterval(p));
1111 }
1112 } else {
1113 // found a free register for container! use it!
1114 if (DEBUG) {
1115 System.out.println("Switch container " + container + "from " + phys + " to " + freeR);
1116 }
1117 CompoundInterval physInterval = getInterval(phys);
1118 if (DEBUG) {
1119 System.out.println("Before switch phys interval" + physInterval);
1120 }
1121 physInterval.removeAll(container);
1122 if (DEBUG) {
1123 System.out.println("Intervals of " + phys + " now " + physInterval);
1124 }
1125
1126 container.assign(freeR);
1127 updatePhysicalInterval(freeR, container, newInterval);
1128 if (VERBOSE_DEBUG) {
1129 System.out.println("Intervals of " + freeR + " now " + getInterval(freeR));
1130 }
1131 // mark the free register found as currently allocated.
1132 freeR.allocateRegister();
1133 }
1134 }
1135 } else {
1136 // This is the first attempt to allocate the compound interval.
1137 // Attempt to find a free physical register for this interval.
1138 Register phys = findAvailableRegister(r);
1139 if (phys != null) {
1140 // Found a free register. Perform the register assignment.
1141 container.assign(phys);
1142 if (DEBUG) {
1143 System.out.println("First allocation " + phys + " " + container);
1144 }
1145 updatePhysicalInterval(phys, newInterval);
1146 if (VERBOSE_DEBUG) System.out.println(" now phys" + getInterval(phys));
1147 // Mark the physical register as currently allocated.
1148 phys.allocateRegister();
1149 } else {
1150 // Could not find a free physical register. Some member of the
1151 // active set must be spilled. Choose a spill candidate.
1152 CompoundInterval spillCandidate = getSpillCandidate(container);
1153 if (VM.VerifyAssertions) {
1154 VM._assert(!spillCandidate.isSpilled());
1155 VM._assert((spillCandidate.getRegister().getType() == r.getType()) ||
1156 (spillCandidate.getRegister().isNatural() && r.isNatural()));
1157 VM._assert(!ir.stackManager.getRestrictions().mustNotSpill(spillCandidate.getRegister()));
1158 if (spillCandidate.getAssignment() != null) {
1159 VM._assert(!ir.stackManager.getRestrictions().
1160 isForbidden(r, spillCandidate.getAssignment()));
1161 }
1162 }
1163 if (spillCandidate != container) {
1164 // spill a previously allocated interval.
1165 phys = spillCandidate.getAssignment();
1166 spillCandidate.spill(spillManager);
1167 spilled = true;
1168 if (VERBOSE_DEBUG) {
1169 System.out.println("Spilled " + spillCandidate + " from " + phys);
1170 }
1171 CompoundInterval physInterval = getInterval(phys);
1172 if (VERBOSE_DEBUG) {
1173 System.out.println(" assigned " + phys + " to " + container);
1174 }
1175 physInterval.removeAll(spillCandidate);
1176 if (VERBOSE_DEBUG) System.out.println(" after spill phys" + getInterval(phys));
1177 updatePhysicalInterval(phys, newInterval);
1178 if (VERBOSE_DEBUG) {
1179 System.out.println(" now phys interval " + getInterval(phys));
1180 }
1181 container.assign(phys);
1182 } else {
1183 // spill the new interval.
1184 if (VERBOSE_DEBUG) System.out.println("spilled " + container);
1185 container.spill(spillManager);
1186 spilled = true;
1187 }
1188 }
1189 }
1190 }
1191 }
1192
1193 /**
1194 * Update the interval representing the allocations of a physical
1195 * register p to include a new interval i
1196 */
1197 private void updatePhysicalInterval(Register p, BasicInterval i) {
1198 // Get a representation of the intervals already assigned to p.
1199 CompoundInterval physInterval = getInterval(p);
1200 if (physInterval == null) {
1201 // no interval yet. create one.
1202 setInterval(p, new CompoundInterval(i, p));
1203 } else {
1204 // incorporate i into the set of intervals assigned to p
1205 CompoundInterval ci = new CompoundInterval(i, p);
1206 if (VM.VerifyAssertions) VM._assert(!ci.intersects(physInterval));
1207 physInterval.addAll(ci);
1208 }
1209 }
1210
1211 /**
1212 * Update the interval representing the allocations of a physical
1213 * register p to include a new compound interval c. Include only
1214 * those basic intervals in c up to and including basic interval stop.
1215 */
1216 private void updatePhysicalInterval(Register p, CompoundInterval c, BasicInterval stop) {
1217 // Get a representation of the intervals already assigned to p.
1218 CompoundInterval physInterval = getInterval(p);
1219 if (physInterval == null) {
1220 // no interval yet. create one.
1221 setInterval(p, c.copy(p, stop));
1222 } else {
1223 // incorporate c into the set of intervals assigned to p
1224 if (VM.VerifyAssertions) VM._assert(!c.intersects(physInterval));
1225 // copy to a new BasicInterval so "equals" will work as expected,
1226 // since "stop" may be a MappedBasicInterval.
1227 stop = new BasicInterval(stop.getBegin(), stop.getEnd());
1228 physInterval.addNonIntersectingInterval(c, stop);
1229 }
1230 }
1231
1232 /**
1233 * Is a particular physical register currently allocated to an
1234 * interval in the active set?
1235 */
1236 boolean currentlyActive(Register r) {
1237 for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
1238 MappedBasicInterval i = (MappedBasicInterval) e.next();
1239 CompoundInterval container = i.container;
1240 if (RegisterAllocatorState.getMapping(container.getRegister()) == r) {
1241 return true;
1242 }
1243 }
1244 return false;
1245 }
1246
1247 /**
1248 * Given that a physical register r is currently allocated to an
1249 * interval in the active set, return the interval.
1250 */
1251 CompoundInterval getCurrentInterval(Register r) {
1252 for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
1253 MappedBasicInterval i = (MappedBasicInterval) e.next();
1254 CompoundInterval container = i.container;
1255 if (RegisterAllocatorState.getMapping(container.getRegister()) == r) {
1256 return container;
1257 }
1258 }
1259 OptimizingCompilerException.UNREACHABLE("getCurrentInterval", "Not Currently Active ", r.toString());
1260 return null;
1261 }
1262
1263 /**
1264 * try to find a free physical register to allocate to the compound
1265 * interval. if no free physical register is found, return null;
1266 */
1267 Register findAvailableRegister(CompoundInterval ci) {
1268
1269 if (ir.options.FREQ_FOCUS_EFFORT && ci.isInfrequent()) {
1270 // don't bother trying to find an available register
1271 return null;
1272 }
1273
1274 Register r = ci.getRegister();
1275 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1276
1277 // first attempt to allocate to the preferred register
1278 if (ir.options.REGALLOC_COALESCE_MOVES) {
1279 Register p = getPhysicalPreference(ci);
1280 if (p != null) {
1281 if (DEBUG_COALESCE) {
1282 System.out.println("REGISTER PREFERENCE " + ci + " " + p);
1283 }
1284 return p;
1285 }
1286 }
1287
1288 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
1289 int type = PhysicalRegisterSet.getPhysicalRegisterType(r);
1290
1291 // next attempt to allocate to a volatile
1292 if (!restrict.allVolatilesForbidden(r)) {
1293 for (Enumeration<Register> e = phys.enumerateVolatiles(type); e.hasMoreElements();) {
1294 Register p = e.nextElement();
1295 if (allocateToPhysical(ci, p)) {
1296 return p;
1297 }
1298 }
1299 }
1300
1301 // next attempt to allocate to a Nonvolatile. we allocate the
1302 // novolatiles backwards.
1303 for (Enumeration<Register> e = phys.enumerateNonvolatilesBackwards(type); e.hasMoreElements();) {
1304 Register p = e.nextElement();
1305 if (allocateToPhysical(ci, p)) {
1306 return p;
1307 }
1308 }
1309
1310 // no allocation succeeded.
1311 return null;
1312 }
1313
1314 /**
1315 * Try to find a free physical register to allocate to a symbolic
1316 * register.
1317 */
1318 Register findAvailableRegister(Register symb) {
1319
1320 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1321
1322 // first attempt to allocate to the preferred register
1323 if (ir.options.REGALLOC_COALESCE_MOVES) {
1324 Register p = getPhysicalPreference(symb);
1325 if (p != null) {
1326 if (DEBUG_COALESCE) {
1327 System.out.println("REGISTER PREFERENCE " + symb + " " + p);
1328 }
1329 return p;
1330 }
1331 }
1332
1333 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
1334 int type = PhysicalRegisterSet.getPhysicalRegisterType(symb);
1335
1336 // next attempt to allocate to a volatile
1337 if (!restrict.allVolatilesForbidden(symb)) {
1338 for (Enumeration<Register> e = phys.enumerateVolatiles(type); e.hasMoreElements();) {
1339 Register p = e.nextElement();
1340 if (allocateNewSymbolicToPhysical(symb, p)) {
1341 return p;
1342 }
1343 }
1344 }
1345
1346 // next attempt to allocate to a Nonvolatile. we allocate the
1347 // novolatiles backwards.
1348 for (Enumeration<Register> e = phys.enumerateNonvolatilesBackwards(type); e.hasMoreElements();) {
1349 Register p = e.nextElement();
1350 if (allocateNewSymbolicToPhysical(symb, p)) {
1351 return p;
1352 }
1353 }
1354
1355 // no allocation succeeded.
1356 return null;
1357 }
1358
1359 /**
1360 * Given the current state of the register allocator, compute the
1361 * available physical register to which a symbolic register has the
1362 * highest preference.
1363 *
1364 * @param r the symbolic register in question.
1365 * @return the preferred register. null if no preference found.
1366 */
1367 private Register getPhysicalPreference(Register r) {
1368 // a mapping from Register to Integer
1369 // (physical register to weight);
1370 HashMap<Register, Integer> map = new HashMap<Register, Integer>();
1371
1372 CoalesceGraph graph = ir.stackManager.getPreferences().getGraph();
1373 SpaceEffGraphNode node = graph.findNode(r);
1374
1375 // Return null if no affinities.
1376 if (node == null) return null;
1377
1378 // walk through all in edges of the node, searching for affinity
1379 for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
1380 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
1381 CoalesceGraph.Node src = (CoalesceGraph.Node) edge.from();
1382 Register neighbor = src.getRegister();
1383 if (neighbor.isSymbolic()) {
1384 // if r is assigned to a physical register r2, treat the
1385 // affinity as an affinity for r2
1386 Register r2 = RegisterAllocatorState.getMapping(r);
1387 if (r2 != null && r2.isPhysical()) {
1388 neighbor = r2;
1389 }
1390 }
1391 if (neighbor.isPhysical()) {
1392 // if this is a candidate interval, update its weight
1393 if (allocateNewSymbolicToPhysical(r, neighbor)) {
1394 int w = edge.getWeight();
1395 Integer oldW = map.get(neighbor);
1396 if (oldW == null) {
1397 map.put(neighbor, w);
1398 } else {
1399 map.put(neighbor, oldW + w);
1400 }
1401 break;
1402 }
1403 }
1404 }
1405 // walk through all out edges of the node, searching for affinity
1406 for (Enumeration<GraphEdge> in = node.outEdges(); in.hasMoreElements();) {
1407 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
1408 CoalesceGraph.Node dest = (CoalesceGraph.Node) edge.to();
1409 Register neighbor = dest.getRegister();
1410 if (neighbor.isSymbolic()) {
1411 // if r is assigned to a physical register r2, treat the
1412 // affinity as an affinity for r2
1413 Register r2 = RegisterAllocatorState.getMapping(r);
1414 if (r2 != null && r2.isPhysical()) {
1415 neighbor = r2;
1416 }
1417 }
1418 if (neighbor.isPhysical()) {
1419 // if this is a candidate interval, update its weight
1420 if (allocateNewSymbolicToPhysical(r, neighbor)) {
1421 int w = edge.getWeight();
1422 Integer oldW = map.get(neighbor);
1423 if (oldW == null) {
1424 map.put(neighbor, w);
1425 } else {
1426 map.put(neighbor, oldW + w);
1427 }
1428 break;
1429 }
1430 }
1431 }
1432 // OK, now find the highest preference.
1433 Register result = null;
1434 int weight = -1;
1435 for (Map.Entry<Register, Integer> entry : map.entrySet()) {
1436 int w = entry.getValue();
1437 if (w > weight) {
1438 weight = w;
1439 result = entry.getKey();
1440 }
1441 }
1442 return result;
1443 }
1444
1445 /**
1446 * Given the current state of the register allocator, compute the
1447 * available physical register to which an interval has the highest
1448 * preference.
1449 *
1450 * @return the preferred register. null if no preference found.
1451 */
1452 private Register getPhysicalPreference(CompoundInterval ci) {
1453 // a mapping from Register to Integer
1454 // (physical register to weight);
1455 HashMap<Register, Integer> map = new HashMap<Register, Integer>();
1456 Register r = ci.getRegister();
1457
1458 CoalesceGraph graph = ir.stackManager.getPreferences().getGraph();
1459 SpaceEffGraphNode node = graph.findNode(r);
1460
1461 // Return null if no affinities.
1462 if (node == null) return null;
1463
1464 // walk through all in edges of the node, searching for affinity
1465 for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
1466 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
1467 CoalesceGraph.Node src = (CoalesceGraph.Node) edge.from();
1468 Register neighbor = src.getRegister();
1469 if (neighbor.isSymbolic()) {
1470 // if r is assigned to a physical register r2, treat the
1471 // affinity as an affinity for r2
1472 Register r2 = RegisterAllocatorState.getMapping(r);
1473 if (r2 != null && r2.isPhysical()) {
1474 neighbor = r2;
1475 }
1476 }
1477 if (neighbor.isPhysical()) {
1478 // if this is a candidate interval, update its weight
1479 if (allocateToPhysical(ci, neighbor)) {
1480 int w = edge.getWeight();
1481 Integer oldW = map.get(neighbor);
1482 if (oldW == null) {
1483 map.put(neighbor, w);
1484 } else {
1485 map.put(neighbor, oldW + w);
1486 }
1487 break;
1488 }
1489 }
1490 }
1491 // walk through all out edges of the node, searching for affinity
1492 for (Enumeration<GraphEdge> in = node.outEdges(); in.hasMoreElements();) {
1493 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
1494 CoalesceGraph.Node dest = (CoalesceGraph.Node) edge.to();
1495 Register neighbor = dest.getRegister();
1496 if (neighbor.isSymbolic()) {
1497 // if r is assigned to a physical register r2, treat the
1498 // affinity as an affinity for r2
1499 Register r2 = RegisterAllocatorState.getMapping(r);
1500 if (r2 != null && r2.isPhysical()) {
1501 neighbor = r2;
1502 }
1503 }
1504 if (neighbor.isPhysical()) {
1505 // if this is a candidate interval, update its weight
1506 if (allocateToPhysical(ci, neighbor)) {
1507 int w = edge.getWeight();
1508 Integer oldW = map.get(neighbor);
1509 if (oldW == null) {
1510 map.put(neighbor, w);
1511 } else {
1512 map.put(neighbor, oldW + w);
1513 }
1514 break;
1515 }
1516 }
1517 }
1518 // OK, now find the highest preference.
1519 Register result = null;
1520 int weight = -1;
1521 for (Map.Entry<Register, Integer> entry : map.entrySet()) {
1522 int w = entry.getValue();
1523 if (w > weight) {
1524 weight = w;
1525 result = entry.getKey();
1526 }
1527 }
1528 return result;
1529 }
1530
1531 /**
1532 * Check whether it's ok to allocate an interval i to physical
1533 * register p. If so, return true; If not, return false.
1534 */
1535 private boolean allocateToPhysical(CompoundInterval i, Register p) {
1536 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1537 Register r = i.getRegister();
1538 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
1539 if (p != null && !phys.isAllocatable(p)) return false;
1540
1541 if (VERBOSE_DEBUG && p != null) {
1542 if (!p.isAvailable()) System.out.println("unavailable " + i + p);
1543 if (restrict.isForbidden(r, p)) System.out.println("forbidden" + i + p);
1544 }
1545
1546 if ((p != null) && p.isAvailable() && !restrict.isForbidden(r, p)) {
1547 CompoundInterval pInterval = getInterval(p);
1548 if (pInterval == null) {
1549 // no assignment to p yet
1550 return true;
1551 } else {
1552 if (!i.intersects(pInterval)) {
1553 return true;
1554 }
1555 }
1556 }
1557 return false;
1558 }
1559
1560 /**
1561 * Check whether it's ok to allocate symbolic register to a physical
1562 * register p. If so, return true; If not, return false.
1563 *
1564 * NOTE: This routine assumes we're processing the first interval of
1565 * register symb; so p.isAvailable() is the key information needed.
1566 */
1567 private boolean allocateNewSymbolicToPhysical(Register symb, Register p) {
1568 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1569 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
1570 if (p != null && !phys.isAllocatable(p)) return false;
1571
1572 if (VERBOSE_DEBUG && p != null) {
1573 if (!p.isAvailable()) System.out.println("unavailable " + symb + p);
1574 if (restrict.isForbidden(symb, p)) System.out.println("forbidden" + symb + p);
1575 }
1576
1577 return (p != null) && p.isAvailable() && !restrict.isForbidden(symb, p);
1578 }
1579
1580 /**
1581 * choose one of the active intervals or the newInterval to spill.
1582 */
1583 private CompoundInterval getSpillCandidate(CompoundInterval newInterval) {
1584 if (VERBOSE_DEBUG) System.out.println("GetSpillCandidate from " + this);
1585
1586 if (ir.options.FREQ_FOCUS_EFFORT && newInterval.isInfrequent()) {
1587 // if it's legal to spill this infrequent interval, then just do so!
1588 // don't spend any more effort.
1589 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1590 if (!restrict.mustNotSpill(newInterval.getRegister())) {
1591 return newInterval;
1592 }
1593 }
1594
1595 return spillMinUnitCost(newInterval);
1596 }
1597
1598 /**
1599 * Choose the interval with the min unit cost (defined as the number
1600 * of defs and uses)
1601 */
1602 private CompoundInterval spillMinUnitCost(CompoundInterval newInterval) {
1603 if (VERBOSE_DEBUG) {
1604 System.out.println(" interval caused a spill: " + newInterval);
1605 }
1606 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1607 Register r = newInterval.getRegister();
1608 double minCost = spillCost.getCost(r);
1609 if (VERBOSE_DEBUG) {
1610 System.out.println(" spill cost: " + r + " " + minCost);
1611 }
1612 CompoundInterval result = newInterval;
1613 if (restrict.mustNotSpill(result.getRegister())) {
1614 if (VERBOSE_DEBUG) {
1615 System.out.println(" must not spill: " + result.getRegister());
1616 }
1617 result = null;
1618 minCost = Double.MAX_VALUE;
1619 }
1620 for (Iterator<BasicInterval> e = iterator(); e.hasNext();) {
1621 MappedBasicInterval b = (MappedBasicInterval) e.next();
1622 CompoundInterval i = b.container;
1623 Register newR = i.getRegister();
1624 if (VERBOSE_DEBUG) {
1625 if (i.isSpilled()) {
1626 System.out.println(" not candidate, already spilled: " + newR);
1627 }
1628 if ((r.getType() != newR.getType()) || (r.isNatural() && newR.isNatural())) {
1629 System.out.println(" not candidate, type mismatch : " + r.getType() + " " + newR + " " + newR.getType());
1630 }
1631 if (restrict.mustNotSpill(newR)) {
1632 System.out.println(" not candidate, must not spill: " + newR);
1633 }
1634 }
1635 if (!newR.isPhysical() &&
1636 !i.isSpilled() &&
1637 (r.getType() == newR.getType() || (r.isNatural() && newR.isNatural())) &&
1638 !restrict.mustNotSpill(newR)) {
1639 // Found a potential spill interval. Check if the assignment
1640 // works if we spill this interval.
1641 if (checkAssignmentIfSpilled(newInterval, i)) {
1642 double iCost = spillCost.getCost(newR);
1643 if (VERBOSE_DEBUG) {
1644 System.out.println(" potential candidate " + i + " cost " + iCost);
1645 }
1646 if (iCost < minCost) {
1647 if (VERBOSE_DEBUG) System.out.println(" best candidate so far" + i);
1648 minCost = iCost;
1649 result = i;
1650 }
1651 } else {
1652 if (VERBOSE_DEBUG) {
1653 System.out.println(" not a candidate, insufficient range: " + i);
1654 }
1655 }
1656 }
1657 }
1658 if (VM.VerifyAssertions) {
1659 VM._assert(result != null);
1660 }
1661 return result;
1662 }
1663
1664 /**
1665 * Check whether, if we spilled interval spill, we could then assign
1666 * interval i to physical register spill.getRegister().
1667 *
1668 * @return true if the allocation would fit. false otherwise
1669 */
1670 private boolean checkAssignmentIfSpilled(CompoundInterval i, CompoundInterval spill) {
1671 Register r = spill.getAssignment();
1672
1673 RegisterRestrictions restrict = ir.stackManager.getRestrictions();
1674 if (restrict.isForbidden(i.getRegister(), r)) return false;
1675
1676 // 1. Speculatively simulate the spill.
1677 CompoundInterval rI = getInterval(r);
1678 CompoundInterval cache = rI.removeIntervalsAndCache(spill);
1679
1680 // 2. Check the fit.
1681 boolean result = !rI.intersects(i);
1682
1683 // 3. Undo the simulated spill.
1684 rI.addAll(cache);
1685
1686 return result;
1687 }
1688
1689 /**
1690 * Find the basic interval for register r containing instruction s.
1691 * If there are two such intervals, return the 1st one.
1692 * If there is none, return null.
1693 */
1694 BasicInterval getBasicInterval(Register r, Instruction s) {
1695 CompoundInterval c = getInterval(r);
1696 if (c == null) return null;
1697 return c.getBasicInterval(s);
1698 }
1699
1700 }
1701
1702 /**
1703 * phase to compute linear scan intervals.
1704 */
1705 public static final class IntervalAnalysis extends CompilerPhase implements Operators {
1706 /**
1707 * the governing ir
1708 */
1709 IR ir;
1710
1711 /**
1712 * a list of basic blocks in topological order
1713 */
1714 private BasicBlock listOfBlocks;
1715
1716 /**
1717 * a reverse topological list of basic blocks
1718 */
1719 private BasicBlock reverseTopFirst;
1720
1721 /**
1722 * Constructor for this compiler phase
1723 */
1724 private static final Constructor<CompilerPhase> constructor =
1725 getCompilerPhaseConstructor(IntervalAnalysis.class);
1726
1727 /**
1728 * Get a constructor object for this compiler phase
1729 * @return compiler phase constructor
1730 */
1731 @Override
1732 public Constructor<CompilerPhase> getClassConstructor() {
1733 return constructor;
1734 }
1735
1736 /**
1737 * should we perform this phase? yes.
1738 */
1739 @Override
1740 public boolean shouldPerform(OptOptions options) { return true; }
1741
1742 /**
1743 * a name for this phase.
1744 */
1745 @Override
1746 public String getName() { return "Interval Analysis"; }
1747
1748 /**
1749 * should we print the ir?
1750 */
1751 @Override
1752 public boolean printingEnabled(OptOptions options, boolean before) {
1753 return false;
1754 }
1755
1756 /**
1757 * compute live intervals for this ir
1758 * the result is a sorted (by beginning point) set of compound
1759 * intervals, stored in the private 'intervals' field.
1760 *
1761 * note: this implementation bashes the 'scratchobject' field on all
1762 * registers and the 'scratch' field on instructions.
1763 *
1764 * @param ir the ir
1765 */
1766 @Override
1767 public void perform(IR ir) {
1768 this.ir = ir;
1769
1770 ControlFlowGraph cfg = ir.cfg;
1771 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
1772 LinearScanState state = new LinearScanState();
1773 ir.MIRInfo.linearScanState = state;
1774
1775 // create topological list and a reverse topological list
1776 // the results are on listOfBlocks and reverseTopFirst lists
1777 createTopAndReverseList(cfg);
1778
1779 // give dfn values to each instruction
1780 assignDepthFirstNumbers(cfg);
1781
1782 // initialize registers
1783 initializeRegisters();
1784
1785 int lastBeginSeen = -1;
1786
1787 // visit each basic block in the listOfBlocks list
1788 for (BasicBlock bb = listOfBlocks; bb != null; bb = (BasicBlock) bb.nextSorted) {
1789
1790 // visit each live interval for this basic block
1791 for (LiveIntervalElement live = bb.getFirstLiveIntervalElement(); live != null; live = live.getNext()) {
1792
1793 // check that we process live intervals in order of increasing
1794 // begin.
1795 if (VM.VerifyAssertions) {
1796 int begin = getDfnBegin(live, bb);
1797 VM._assert(begin >= lastBeginSeen);
1798 lastBeginSeen = begin;
1799 }
1800
1801 // skip registers which are not allocated.
1802 if (live.getRegister().isPhysical() && !phys.isAllocatable(live.getRegister())) {
1803 continue;
1804 }
1805
1806 CompoundInterval resultingInterval = processLiveInterval(live, bb);
1807 if (!bb.getInfrequent() && resultingInterval != null) {
1808 resultingInterval.setFrequent();
1809 }
1810 }
1811 }
1812
1813 // debug support
1814 if (VERBOSE_DEBUG) {
1815 VM.sysWrite("**** start of interval dump " + ir.method + " ****\n");
1816 VM.sysWrite(ir.MIRInfo.linearScanState.intervals.toString());
1817 VM.sysWrite("**** end of interval dump ****\n");
1818 }
1819 }
1820
1821 /**
1822 * create topological list and a reverse topological list
1823 * the results are on listOfBlocks and reverseTopFirst lists
1824 * @param cfg the control flow graph
1825 */
1826 private void createTopAndReverseList(ControlFlowGraph cfg) {
1827 // dfs: create a list of nodes (basic blocks) in a topological order
1828 cfg.clearDFS();
1829 listOfBlocks = cfg.entry();
1830 listOfBlocks.sortDFS();
1831
1832 // this loop reverses the topological list by using the sortedPrev field
1833 reverseTopFirst = null;
1834 for (BasicBlock bb = listOfBlocks; bb != null; bb = (BasicBlock) bb.nextSorted) {
1835
1836 // put back pointers in the "prev" field
1837 // set reverseTopFirst to be the more recent node we've seen,
1838 // it will be the front of the list when we are done
1839 bb.sortedPrev = reverseTopFirst;
1840 reverseTopFirst = bb;
1841 }
1842 }
1843
1844 /**
1845 * this method processes all basic blocks, do the following to each block
1846 * 1) add it to the begining of the "listOfBlocks" list
1847 * 2) number the instructions
1848 * 3) process the instructions that restrict physical register
1849 * assignment
1850 * @param cfg the control flow graph
1851 */
1852 void assignDepthFirstNumbers(ControlFlowGraph cfg) {
1853
1854 int curDfn = ir.numberInstructions() - 1;
1855
1856 listOfBlocks = null;
1857 for (BasicBlock bb = reverseTopFirst; bb != null; bb = (BasicBlock) bb.sortedPrev) {
1858
1859 // insert bb at the front of the list
1860 bb.nextSorted = listOfBlocks;
1861 listOfBlocks = bb;
1862
1863 // number the instructions last to first
1864 Enumeration<Instruction> e = bb.reverseInstrEnumerator();
1865 while (e.hasMoreElements()) {
1866 Instruction inst = e.nextElement();
1867 setDFN(inst, curDfn);
1868 curDfn--;
1869 }
1870 }
1871
1872 if (DEBUG) { printDfns(ir); }
1873 }
1874
1875 /**
1876 * Initialize the interval for each register to null.
1877 */
1878 private void initializeRegisters() {
1879 for (Register reg = ir.regpool.getFirstSymbolicRegister(); reg != null; reg = reg.getNext()) {
1880 setInterval(reg, null);
1881 RegisterAllocatorState.setSpill(reg, 0);
1882 // clear the 'long' type if it's persisted to here.
1883 if (VM.BuildFor32Addr && reg.isLong()) {
1884 reg.clearType();
1885 reg.setInteger();
1886 }
1887 }
1888 }
1889
1890 /**
1891 * for each live interval associated with this block
1892 * we either add a new interval, or extend a previous interval
1893 * if it is contiguous
1894 *
1895 * @param live the liveintervalelement for a basic block/reg pair
1896 * @param bb the basic block
1897 * @return the resulting CompoundInterval. null if the live interval
1898 * is not relevant to register allocation.
1899 */
1900 private CompoundInterval processLiveInterval(LiveIntervalElement live, BasicBlock bb) {
1901
1902 // get the reg and (adjusted) begin, end pair for this interval
1903 Register reg = live.getRegister();
1904 int dfnend = getDfnEnd(live, bb);
1905 int dfnbegin = getDfnBegin(live, bb);
1906
1907 if (MUTATE_FMOV && reg.isFloatingPoint()) {
1908 Operators.helper.mutateFMOVs(live, reg, dfnbegin, dfnend);
1909 }
1910
1911 // check for an existing live interval for this register
1912 CompoundInterval existingInterval = getInterval(reg);
1913 if (existingInterval == null) {
1914 // create a new live interval
1915 CompoundInterval newInterval = new CompoundInterval(dfnbegin, dfnend, reg);
1916 if (VERBOSE_DEBUG) System.out.println("created a new interval " + newInterval);
1917
1918 // associate the interval with the register
1919 setInterval(reg, newInterval);
1920
1921 // add the new interval to the sorted set of intervals.
1922 BasicInterval b = newInterval.first();
1923 ir.MIRInfo.linearScanState.intervals.add(b);
1924
1925 return newInterval;
1926
1927 } else {
1928 // add the new live range to the existing interval
1929 ArrayList<BasicInterval> intervals = ir.MIRInfo.linearScanState.intervals;
1930 BasicInterval added = existingInterval.addRange(live, bb);
1931 if (added != null) {
1932 intervals.add(added);
1933 }
1934 if (VERBOSE_DEBUG) System.out.println("Extended old interval " + reg);
1935 if (VERBOSE_DEBUG) System.out.println(existingInterval);
1936
1937 return existingInterval;
1938 }
1939 }
1940 }
1941
1942 /**
1943 * The following class manages allocation and reuse of spill locations.
1944 */
1945 static class SpillLocationManager implements PhysicalRegisterConstants {
1946
1947 /**
1948 * The governing IR
1949 */
1950 private final IR ir;
1951
1952 /**
1953 * Set of spill locations which were previously allocated, but may be
1954 * free since the assigned register is no longer live.
1955 */
1956 final HashSet<SpillLocationInterval> freeIntervals = new HashSet<SpillLocationInterval>();
1957
1958 /**
1959 * Return a spill location that is valid to hold the contents of
1960 * compound interval ci.
1961 */
1962 SpillLocationInterval findOrCreateSpillLocation(CompoundInterval ci) {
1963 SpillLocationInterval result = null;
1964
1965 Register r = ci.getRegister();
1966 int type = PhysicalRegisterSet.getPhysicalRegisterType(r);
1967 if (type == -1) {
1968 type = DOUBLE_REG;
1969 }
1970 int spillSize = PhysicalRegisterSet.getSpillSize(type);
1971
1972 // Search the free intervals and try to find an interval to
1973 // reuse. First look for the preferred interval.
1974 if (ir.options.REGALLOC_COALESCE_SPILLS) {
1975 result = getSpillPreference(ci, spillSize);
1976 if (result != null) {
1977 if (DEBUG_COALESCE) {
1978 System.out.println("SPILL PREFERENCE " + ci + " " + result);
1979 }
1980 freeIntervals.remove(result);
1981 }
1982 }
1983
1984 // Now search for any free interval.
1985 if (result == null) {
1986 for (SpillLocationInterval s : freeIntervals) {
1987 if (s.getSize() == spillSize && !s.intersects(ci)) {
1988 result = s;
1989 freeIntervals.remove(result);
1990 break;
1991 }
1992 }
1993 }
1994
1995 if (result == null) {
1996 // Could not find an interval to reuse. Create a new interval.
1997 int location = ir.stackManager.allocateNewSpillLocation(type);
1998 result = new SpillLocationInterval(location, spillSize);
1999 }
2000
2001 // Update the spill location interval to hold the new spill
2002 result.addAll(ci);
2003
2004 return result;
2005 }
2006
2007 /**
2008 * Record that a particular interval is potentially available for
2009 * reuse
2010 */
2011 void freeInterval(SpillLocationInterval i) {
2012 freeIntervals.add(i);
2013 }
2014
2015 /**
2016 * Constructor.
2017 */
2018 SpillLocationManager(IR ir) {
2019 this.ir = ir;
2020 }
2021
2022 /**
2023 * Given the current state of the register allocator, compute the
2024 * available spill location to which ci has the highest preference.
2025 *
2026 * @param ci the interval to spill
2027 * @param spillSize the size of spill location needed
2028 * @return the interval to spill to. null if no preference found.
2029 */
2030 SpillLocationInterval getSpillPreference(CompoundInterval ci, int spillSize) {
2031 // a mapping from SpillLocationInterval to Integer
2032 // (spill location to weight);
2033 HashMap<SpillLocationInterval, Integer> map = new HashMap<SpillLocationInterval, Integer>();
2034 Register r = ci.getRegister();
2035
2036 CoalesceGraph graph = ir.stackManager.getPreferences().getGraph();
2037 SpaceEffGraphNode node = graph.findNode(r);
2038
2039 // Return null if no affinities.
2040 if (node == null) return null;
2041
2042 // walk through all in edges of the node, searching for spill
2043 // location affinity
2044 for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
2045 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
2046 CoalesceGraph.Node src = (CoalesceGraph.Node) edge.from();
2047 Register neighbor = src.getRegister();
2048 if (neighbor.isSymbolic() && neighbor.isSpilled()) {
2049 int spillOffset = RegisterAllocatorState.getSpill(neighbor);
2050 // if this is a candidate interval, update its weight
2051 for (SpillLocationInterval s : freeIntervals) {
2052 if (s.getOffset() == spillOffset && s.getSize() == spillSize && !s.intersects(ci)) {
2053 int w = edge.getWeight();
2054 Integer oldW = map.get(s);
2055 if (oldW == null) {
2056 map.put(s, w);
2057 } else {
2058 map.put(s, oldW + w);
2059 }
2060 break;
2061 }
2062 }
2063 }
2064 }
2065
2066 // walk through all out edges of the node, searching for spill
2067 // location affinity
2068 for (Enumeration<GraphEdge> in = node.inEdges(); in.hasMoreElements();) {
2069 CoalesceGraph.Edge edge = (CoalesceGraph.Edge) in.nextElement();
2070 CoalesceGraph.Node dest = (CoalesceGraph.Node) edge.to();
2071 Register neighbor = dest.getRegister();
2072 if (neighbor.isSymbolic() && neighbor.isSpilled()) {
2073 int spillOffset = RegisterAllocatorState.getSpill(neighbor);
2074 // if this is a candidate interval, update its weight
2075 for (SpillLocationInterval s : freeIntervals) {
2076 if (s.getOffset() == spillOffset && s.getSize() == spillSize && !s.intersects(ci)) {
2077 int w = edge.getWeight();
2078 Integer oldW = map.get(s);
2079 if (oldW == null) {
2080 map.put(s, w);
2081 } else {
2082 map.put(s, oldW + w);
2083 }
2084 break;
2085 }
2086 }
2087 }
2088 }
2089
2090 // OK, now find the highest preference.
2091 SpillLocationInterval result = null;
2092 int weight = -1;
2093 for (Map.Entry<SpillLocationInterval, Integer> entry : map.entrySet()) {
2094 int w = entry.getValue();
2095 if (w > weight) {
2096 weight = w;
2097 result = entry.getKey();
2098 }
2099 }
2100 return result;
2101 }
2102 }
2103
2104 /**
2105 * The following represents the intervals assigned to a particular spill
2106 * location
2107 */
2108 static class SpillLocationInterval extends CompoundInterval {
2109 /** Support for Set serialization */
2110 static final long serialVersionUID = 2854333172650538517L;
2111 /**
2112 * The spill location, an offset from the frame pointer
2113 */
2114 private final int frameOffset;
2115
2116 int getOffset() {
2117 return frameOffset;
2118 }
2119
2120 /**
2121 * The size of the spill location, in bytes.
2122 */
2123 private final int size;
2124
2125 int getSize() {
2126 return size;
2127 }
2128
2129 SpillLocationInterval(int frameOffset, int size) {
2130 super(null);
2131 this.frameOffset = frameOffset;
2132 this.size = size;
2133 }
2134
2135 @Override
2136 public String toString() {
2137 return super.toString() + "<Offset:" + frameOffset + "," + size + ">";
2138 }
2139
2140 /**
2141 * Redefine hash code for reproducibility.
2142 */
2143 @Override
2144 public int hashCode() {
2145 BasicInterval first = first();
2146 BasicInterval last = last();
2147 return frameOffset + (first.getBegin() << 4) + (last.getEnd() << 12);
2148 }
2149 }
2150
2151 /**
2152 * Implements a set of Basic Intervals, sorted by start number.
2153 * This version does NOT use container-mapping as a function in the comparator.
2154 */
2155 static class IncreasingStartIntervalSet extends IntervalSet {
2156 /** Support for Set serialization */
2157 static final long serialVersionUID = -7086728932911844728L;
2158
2159 private static class StartComparator implements Comparator<BasicInterval> {
2160 @Override
2161 public int compare(BasicInterval b1, BasicInterval b2) {
2162 int result = b1.getBegin() - b2.getBegin();
2163 if (result == 0) {
2164 result = b1.getEnd() - b2.getEnd();
2165 }
2166 return result;
2167 }
2168 }
2169
2170 static final StartComparator c = new StartComparator();
2171
2172 IncreasingStartIntervalSet() {
2173 super(c /*,true*/);
2174 }
2175 }
2176
2177 /**
2178 * Implements a set of Basic Intervals, sorted by start number.
2179 * This version uses container-mapping as a function in the comparator.
2180 */
2181 static class IncreasingStartMappedIntervalSet extends IntervalSet {
2182 /** Support for Set serialization */
2183 static final long serialVersionUID = -975667667343524421L;
2184
2185 private static class StartComparator implements Comparator<BasicInterval> {
2186 @Override
2187 public int compare(BasicInterval b1, BasicInterval b2) {
2188 int result = b1.getBegin() - b2.getBegin();
2189 if (result == 0) {
2190 result = b1.getEnd() - b2.getEnd();
2191 }
2192 if (result == 0) {
2193 if (b1 instanceof MappedBasicInterval) {
2194 if (b2 instanceof MappedBasicInterval) {
2195 MappedBasicInterval mb1 = (MappedBasicInterval) b1;
2196 MappedBasicInterval mb2 = (MappedBasicInterval) b2;
2197 return mb1.container.getRegister().number - mb2.container.getRegister().number;
2198 }
2199 }
2200 }
2201 return result;
2202 }
2203 }
2204
2205 static final StartComparator c = new StartComparator();
2206
2207 IncreasingStartMappedIntervalSet() {
2208 super(c);
2209 }
2210 }
2211
2212 /**
2213 * Implements a set of Basic Intervals, sorted by end number.
2214 * This version uses container-mapping as a function in the comparator.
2215 */
2216 static class IncreasingEndMappedIntervalSet extends IntervalSet {
2217 /** Support for Set serialization */
2218 static final long serialVersionUID = -3121737650157210290L;
2219
2220 private static class EndComparator implements Comparator<BasicInterval> {
2221 @Override
2222 public int compare(BasicInterval b1, BasicInterval b2) {
2223 int result = b1.getEnd() - b2.getEnd();
2224 if (result == 0) {
2225 result = b1.getBegin() - b2.getBegin();
2226 }
2227 if (result == 0) {
2228 if (b1 instanceof MappedBasicInterval) {
2229 if (b2 instanceof MappedBasicInterval) {
2230 MappedBasicInterval mb1 = (MappedBasicInterval) b1;
2231 MappedBasicInterval mb2 = (MappedBasicInterval) b2;
2232 return mb1.container.getRegister().number - mb2.container.getRegister().number;
2233 }
2234 }
2235 }
2236 return result;
2237 }
2238 }
2239
2240 static final EndComparator c = new EndComparator();
2241
2242 IncreasingEndMappedIntervalSet() {
2243 super(c);
2244 }
2245 }
2246
2247 abstract static class IntervalSet extends TreeSet<BasicInterval> {
2248
2249 /**
2250 * Create an interval set sorted by increasing start or end number
2251 */
2252 IntervalSet(Comparator<BasicInterval> c) {
2253 super(c);
2254 }
2255
2256 /**
2257 * Return a String representation
2258 */
2259 @Override
2260 public String toString() {
2261 String result = "";
2262 for (BasicInterval b : this) {
2263 result = result + b + "\n";
2264 }
2265 return result;
2266 }
2267 }
2268
2269 /**
2270 * Update GC maps after register allocation but before inserting spill
2271 * code.
2272 */
2273 static final class UpdateGCMaps1 extends CompilerPhase {
2274
2275 @Override
2276 public boolean shouldPerform(OptOptions options) {
2277 return true;
2278 }
2279
2280 /**
2281 * Return this instance of this phase. This phase contains no
2282 * per-compilation instance fields.
2283 * @param ir not used
2284 * @return this
2285 */
2286 @Override
2287 public CompilerPhase newExecution(IR ir) {
2288 return this;
2289 }
2290
2291 @Override
2292 public String getName() {
2293 return "Update GCMaps 1";
2294 }
2295
2296 @Override
2297 public boolean printingEnabled(OptOptions options, boolean before) {
2298 return false;
2299 }
2300
2301 /**
2302 * Iterate over the IR-based GC map collection and for each entry
2303 * replace the symbolic reg with the real reg or spill it was allocated
2304 * @param ir the IR
2305 */
2306 @Override
2307 public void perform(IR ir) {
2308
2309 for (GCIRMapElement GCelement : ir.MIRInfo.gcIRMap) {
2310 if (GC_DEBUG) {
2311 VM.sysWrite("GCelement " + GCelement);
2312 }
2313
2314 for (RegSpillListElement elem : GCelement.regSpillList()) {
2315 Register symbolic = elem.getSymbolicReg();
2316
2317 if (GC_DEBUG) {
2318 VM.sysWrite("get location for " + symbolic + '\n');
2319 }
2320
2321 if (symbolic.isAllocated()) {
2322 Register ra = RegisterAllocatorState.getMapping(symbolic);
2323 elem.setRealReg(ra);
2324 if (GC_DEBUG) { VM.sysWrite(ra + "\n"); }
2325
2326 } else if (symbolic.isSpilled()) {
2327 int spill = symbolic.getSpillAllocated();
2328 elem.setSpill(spill);
2329 if (GC_DEBUG) { VM.sysWrite(spill + "\n"); }
2330 } else {
2331 OptimizingCompilerException.UNREACHABLE("LinearScan", "register not alive:", symbolic.toString());
2332 }
2333 }
2334 }
2335 }
2336 }
2337
2338 /**
2339 * Update GC Maps again, to account for changes induced by spill code.
2340 */
2341 static final class UpdateGCMaps2 extends CompilerPhase {
2342 /**
2343 * Return this instance of this phase. This phase contains no
2344 * per-compilation instance fields.
2345 * @param ir not used
2346 * @return this
2347 */
2348 @Override
2349 public CompilerPhase newExecution(IR ir) {
2350 return this;
2351 }
2352
2353 @Override
2354 public boolean shouldPerform(OptOptions options) {
2355 return true;
2356 }
2357
2358 @Override
2359 public String getName() {
2360 return "Update GCMaps 2";
2361 }
2362
2363 @Override
2364 public boolean printingEnabled(OptOptions options, boolean before) {
2365 return false;
2366 }
2367
2368 /**
2369 * @param ir the IR
2370 */
2371 @Override
2372 public void perform(IR ir) {
2373 PhysicalRegisterSet phys = ir.regpool.getPhysicalRegisterSet();
2374 ScratchMap scratchMap = ir.stackManager.getScratchMap();
2375
2376 if (GC_DEBUG) {
2377 System.out.println("SCRATCH MAP:\n" + scratchMap);
2378 }
2379 if (scratchMap.isEmpty()) return;
2380
2381 // Walk over each instruction that has a GC point.
2382 for (GCIRMapElement GCelement : ir.MIRInfo.gcIRMap) {
2383 // new elements to add to the gc map
2384 HashSet<RegSpillListElement> newElements = new HashSet<RegSpillListElement>();
2385
2386 Instruction GCinst = GCelement.getInstruction();
2387
2388 // Get the linear-scan DFN for this instruction.
2389 int dfn = GCinst.scratch;
2390
2391 if (GC_DEBUG) {
2392 VM.sysWrite("GCelement at " + dfn + " , " + GCelement);
2393 }
2394
2395 // a set of elements to delete from the GC Map
2396 HashSet<RegSpillListElement> toDelete = new HashSet<RegSpillListElement>(3);
2397
2398 // For each element in the GC Map ...
2399 for (RegSpillListElement elem : GCelement.regSpillList()) {
2400 if (GC_DEBUG) {
2401 VM.sysWrite("Update " + elem + "\n");
2402 }
2403 if (elem.isSpill()) {
2404 // check if the spilled value currently is cached in a scratch
2405 // register
2406 Register r = elem.getSymbolicReg();
2407 Register scratch = scratchMap.getScratch(r, dfn);
2408 if (scratch != null) {
2409 if (GC_DEBUG) {
2410 VM.sysWrite("cached in scratch register " + scratch + "\n");
2411 }
2412 // we will add a new element noting that the scratch register
2413 // also must be including in the GC map
2414 RegSpillListElement newElem = new RegSpillListElement(r);
2415 newElem.setRealReg(scratch);
2416 newElements.add(newElem);
2417 // if the scratch register is dirty, then delete the spill
2418 // location from the map, since it doesn't currently hold a
2419 // valid value
2420 if (scratchMap.isDirty(GCinst, r)) {
2421 toDelete.add(elem);
2422 }
2423 }
2424 } else {
2425 // check if the physical register is currently spilled.
2426 int n = elem.getRealRegNumber();
2427 Register r = phys.get(n);
2428 if (scratchMap.isScratch(r, dfn)) {
2429 // The regalloc state knows where the physical register r is
2430 // spilled.
2431 if (GC_DEBUG) {
2432 VM.sysWrite("CHANGE to spill location " + RegisterAllocatorState.getSpill(r) + "\n");
2433 }
2434 elem.setSpill(RegisterAllocatorState.getSpill(r));
2435 }
2436 }
2437
2438 }
2439 // delete all obsolete elements
2440 for (RegSpillListElement deadElem : toDelete) {
2441 GCelement.deleteRegSpillElement(deadElem);
2442 }
2443
2444 // add each new Element to the gc map
2445 for (RegSpillListElement newElem : newElements) {
2446 GCelement.addRegSpillElement(newElem);
2447 }
2448 }
2449 }
2450 }
2451
2452 /**
2453 * Insert Spill Code after register assignment.
2454 */
2455 static final class SpillCode extends CompilerPhase implements Operators {
2456 /**
2457 * Return this instance of this phase. This phase contains no
2458 * per-compilation instance fields.
2459 * @param ir not used
2460 * @return this
2461 */
2462 @Override
2463 public CompilerPhase newExecution(IR ir) {
2464 return this;
2465 }
2466
2467 @Override
2468 public boolean shouldPerform(OptOptions options) {
2469 return true;
2470 }
2471
2472 @Override
2473 public String getName() {
2474 return "Spill Code";
2475 }
2476
2477 @Override
2478 public boolean printingEnabled(OptOptions options, boolean before) {
2479 return false;
2480 }
2481
2482 /**
2483 * @param ir the IR
2484 */
2485 @Override
2486 public void perform(IR ir) {
2487 replaceSymbolicRegisters(ir);
2488
2489 // Generate spill code if necessary
2490 if (ir.hasSysCall() || ir.MIRInfo.linearScanState.spilledSomething) {
2491 StackManager stackMan = (StackManager) ir.stackManager;
2492 stackMan.insertSpillCode(ir.MIRInfo.linearScanState.active);
2493 // stackMan.insertSpillCode();
2494 }
2495
2496 if (VM.BuildForIA32 && !VM.BuildForSSE2Full) {
2497 Operators.helper.rewriteFPStack(ir);
2498 }
2499 }
2500
2501 /**
2502 * Iterate over the IR and replace each symbolic register with its
2503 * allocated physical register.
2504 * Also used by ClassWriter
2505 */
2506 public static void replaceSymbolicRegisters(IR ir) {
2507 for (Enumeration<Instruction> inst = ir.forwardInstrEnumerator(); inst.hasMoreElements();) {
2508 Instruction s = inst.nextElement();
2509 for (Enumeration<Operand> ops = s.getOperands(); ops.hasMoreElements();) {
2510 Operand op = ops.nextElement();
2511 if (op.isRegister()) {
2512 RegisterOperand rop = op.asRegister();
2513 Register r = rop.getRegister();
2514 if (r.isSymbolic() && !r.isSpilled()) {
2515 Register p = RegisterAllocatorState.getMapping(r);
2516 if (VM.VerifyAssertions) VM._assert(p != null);
2517 rop.setRegister(p);
2518 }
2519 }
2520 }
2521 }
2522 }
2523
2524 }
2525
2526 /**
2527 * Update GC maps after register allocation but before inserting spill
2528 * code.
2529 */
2530 public static final class UpdateOSRMaps extends CompilerPhase {
2531
2532 @Override
2533 public boolean shouldPerform(OptOptions options) {
2534 return true;
2535 }
2536
2537 /**
2538 * Return this instance of this phase. This phase contains no
2539 * per-compilation instance fields.
2540 * @param ir not used
2541 * @return this
2542 */
2543 @Override
2544 public CompilerPhase newExecution(IR ir) {
2545 return this;
2546 }
2547
2548 @Override
2549 public String getName() {
2550 return "Update OSRMaps";
2551 }
2552
2553 @Override
2554 public boolean printingEnabled(OptOptions options, boolean before) {
2555 return false;
2556 }
2557
2558 /**
2559 * Iterate over the IR-based OSR map, and update symbolic registers
2560 * with real reg number or spill locations.
2561 * Verify there are only two types of operands:
2562 * ConstantOperand
2563 * RegisterOperand
2564 * for integer constant, we save the value of the integer
2565 *
2566 * The LONG register has another half part.
2567 *
2568 * CodeSpill replaces any allocated symbolic register by
2569 * physical registers.
2570 */
2571 @Override
2572 public void perform(IR ir) throws OptimizingCompilerException {
2573 // list of OsrVariableMapElement
2574 //LinkedList<VariableMapElement> mapList = ir.MIRInfo.osrVarMap.list;
2575 //for (int numOsrs=0, m=mapList.size(); numOsrs<m; numOsrs++) {
2576 // VariableMapElement elm = mapList.get(numOsrs);
2577 /* for each osr instruction */
2578 for (VariableMapElement elm : ir.MIRInfo.osrVarMap.list) {
2579
2580 // for each inlined method
2581 //LinkedList<MethodVariables> mvarsList = elm.mvars; XXX Remove once proven correct
2582 //for (int numMvars=0, n=mvarsList.size(); numMvars<n; numMvars++) {
2583 // MethodVariables mvar = mvarsList.get(numMvars);
2584 for (MethodVariables mvar : elm.mvars) {
2585
2586 // for each tuple
2587 //LinkedList<LocalRegPair> tupleList = mvar.tupleList;
2588 //for (int numTuple=0, k=tupleList.size(); numTuple<k; numTuple++) {
2589 //LocalRegPair tuple = tupleList.get(numTuple);
2590 for (LocalRegPair tuple : mvar.tupleList) {
2591
2592 Operand op = tuple.operand;
2593 if (op.isRegister()) {
2594 Register sym_reg = ((RegisterOperand) op).getRegister();
2595
2596 setRealPosition(ir, tuple, sym_reg);
2597
2598 // get another half part of long register
2599 if (VM.BuildFor32Addr && (tuple.typeCode == OSRConstants.LongTypeCode)) {
2600
2601 LocalRegPair other = tuple._otherHalf;
2602 Operand other_op = other.operand;
2603
2604 if (VM.VerifyAssertions) VM._assert(other_op.isRegister());
2605
2606 Register other_reg = ((RegisterOperand) other_op).getRegister();
2607 setRealPosition(ir, other, other_reg);
2608 }
2609 /* According to ConvertToLowLevelIR, StringConstant, LongConstant,
2610 * NullConstant, FloatConstant, and DoubleConstant are all materialized
2611 * The only thing left is the integer constants which could encode
2612 * non-moveable objects.
2613 * POTENTIAL DRAWBACKS: since any long, float, and double are moved
2614 * to register and treated as use, it may consume more registers and
2615 * add unnecessary MOVEs.
2616 *
2617 * Perhaps, ConvertToLowLevelIR can skip OsrPoint instruction.
2618 */
2619 } else if (op.isIntConstant()) {
2620 setTupleValue(tuple, OSRConstants.ICONST, ((IntConstantOperand) op).value);
2621 if (VM.BuildFor32Addr && (tuple.typeCode == OSRConstants.LongTypeCode)) {
2622 LocalRegPair other = tuple._otherHalf;
2623 Operand other_op = other.operand;
2624
2625 if (VM.VerifyAssertions) VM._assert(other_op.isIntConstant());
2626 setTupleValue(other, OSRConstants.ICONST, ((IntConstantOperand) other_op).value);
2627 }
2628 } else if (op.isAddressConstant()) {
2629 setTupleValue(tuple, OSRConstants.ACONST, ((AddressConstantOperand) op).value.toWord());
2630 } else if (VM.BuildFor64Addr && op.isLongConstant()) {
2631 setTupleValue(tuple, OSRConstants.LCONST, Word.fromLong(((LongConstantOperand) op).value));
2632 } else {
2633 throw new OptimizingCompilerException("LinearScan", "Unexpected operand type at ", op.toString());
2634 } // for the op type
2635 } // for each tuple
2636 } // for each inlined method
2637 } // for each osr instruction
2638 } // end of method
2639
2640 void setRealPosition(IR ir, LocalRegPair tuple, Register sym_reg) {
2641 if (VM.VerifyAssertions) VM._assert(sym_reg != null);
2642
2643 int REG_MASK = 0x01F;
2644
2645 // now it is not symbolic register anymore.
2646 // is is really confusing that sometimes a sym reg is a phy,
2647 // and sometimes not.
2648 if (sym_reg.isAllocated()) {
2649 setTupleValue(tuple, OSRConstants.PHYREG, sym_reg.number & REG_MASK);
2650 } else if (sym_reg.isPhysical()) {
2651 setTupleValue(tuple, OSRConstants.PHYREG, sym_reg.number & REG_MASK);
2652 } else if (sym_reg.isSpilled()) {
2653 setTupleValue(tuple, OSRConstants.SPILL, sym_reg.getSpillAllocated());
2654 } else {
2655 dumpIR(ir, "PANIC");
2656 throw new RuntimeException("LinearScan PANIC in OSRMAP, " + sym_reg + " is not alive");
2657 }
2658 } // end of setRealPosition
2659
2660 static void setTupleValue(LocalRegPair tuple, byte type, int value) {
2661 tuple.valueType = type;
2662 tuple.value = Word.fromIntSignExtend(value);
2663 } // end of setTupleValue
2664
2665 static void setTupleValue(LocalRegPair tuple, byte type, Word value) {
2666 tuple.valueType = type;
2667 tuple.value = value;
2668 } // end of setTupleValue
2669 } // end of inner class
2670 }