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