23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static jdk.vm.ci.code.CodeUtil.isEven;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.isIllegal;
28 import static jdk.vm.ci.code.ValueUtil.isLegal;
29 import static jdk.vm.ci.code.ValueUtil.isRegister;
30 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
32 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
33
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.BitSet;
37 import java.util.EnumSet;
38
39 import org.graalvm.compiler.core.common.LIRKind;
40 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
41 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
42 import org.graalvm.compiler.core.common.cfg.BlockMap;
43 import org.graalvm.compiler.debug.Debug;
44 import org.graalvm.compiler.debug.Debug.Scope;
45 import org.graalvm.compiler.debug.GraalError;
46 import org.graalvm.compiler.debug.Indent;
47 import org.graalvm.compiler.lir.LIR;
48 import org.graalvm.compiler.lir.LIRInstruction;
49 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
50 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
51 import org.graalvm.compiler.lir.ValueConsumer;
52 import org.graalvm.compiler.lir.Variable;
53 import org.graalvm.compiler.lir.VirtualStackSlot;
54 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
55 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
56 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
57 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
58 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
59 import org.graalvm.compiler.options.NestedBooleanOptionKey;
60 import org.graalvm.compiler.options.Option;
61 import org.graalvm.compiler.options.OptionKey;
62 import org.graalvm.compiler.options.OptionType;
63 import org.graalvm.compiler.options.OptionValues;
64 import org.graalvm.util.Pair;
111 public BitSet liveGen;
112
113 /**
114 * Bit map specifying which operands are defined/overwritten in this block. The bit index of
115 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
116 */
117 public BitSet liveKill;
118 }
119
120 public static final int DOMINATOR_SPILL_MOVE_ID = -2;
121 private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
122
123 private final LIR ir;
124 private final FrameMapBuilder frameMapBuilder;
125 private final RegisterAttributes[] registerAttributes;
126 private final RegisterArray registers;
127 private final RegisterAllocationConfig regAllocConfig;
128 private final MoveFactory moveFactory;
129
130 private final BlockMap<BlockData> blockData;
131
132 /**
133 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
134 */
135 private final AbstractBlockBase<?>[] sortedBlocks;
136
137 /**
138 * @see #intervals()
139 */
140 private Interval[] intervals;
141
142 /**
143 * The number of valid entries in {@link #intervals}.
144 */
145 private int intervalsSize;
146
147 /**
148 * The index of the first entry in {@link #intervals} for a
149 * {@linkplain #createDerivedInterval(Interval) derived interval}.
150 */
174 */
175 private final int firstVariableNumber;
176 /**
177 * Number of variables.
178 */
179 private int numVariables;
180 private final boolean neverSpillConstants;
181
182 /**
183 * Sentinel interval to denote the end of an interval list.
184 */
185 protected final Interval intervalEndMarker;
186 public final Range rangeEndMarker;
187 public final boolean detailedAsserts;
188 private final LIRGenerationResult res;
189
190 protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks,
191 boolean neverSpillConstants) {
192 this.ir = res.getLIR();
193 this.res = res;
194 this.moveFactory = spillMoveFactory;
195 this.frameMapBuilder = res.getFrameMapBuilder();
196 this.sortedBlocks = sortedBlocks;
197 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
198 this.regAllocConfig = regAllocConfig;
199
200 this.registers = target.arch.getRegisters();
201 this.firstVariableNumber = getRegisters().size();
202 this.numVariables = ir.numVariables();
203 this.blockData = new BlockMap<>(ir.getControlFlowGraph());
204 this.neverSpillConstants = neverSpillConstants;
205 this.rangeEndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
206 this.intervalEndMarker = new Interval(Value.ILLEGAL, Interval.END_MARKER_OPERAND_NUMBER, null, rangeEndMarker);
207 this.intervalEndMarker.next = intervalEndMarker;
208 this.detailedAsserts = DetailedAsserts.getValue(ir.getOptions());
209 }
210
211 public LIRGenerationResult getLIRGenerationResult() {
212 return res;
213 }
214
215 public Interval intervalEndMarker() {
216 return intervalEndMarker;
217 }
218
219 public OptionValues getOptions() {
220 return ir.getOptions();
221 }
222
223 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
224 int result = ir.getLIRforBlock(block).get(0).id();
225 assert result >= 0;
226 return result;
227 }
228
229 public int getLastLirInstructionId(AbstractBlockBase<?> block) {
230 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
231 int result = instructions.get(instructions.size() - 1).id();
232 assert result >= 0;
233 return result;
234 }
235
236 public MoveFactory getSpillMoveFactory() {
237 return moveFactory;
238 }
239
240 protected MoveResolver createMoveResolver() {
241 MoveResolver moveResolver = new MoveResolver(this);
242 assert moveResolver.checkEmpty();
625
626 while (oldIdx + newIdx < combinedList.length) {
627 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) {
628 combinedList[oldIdx + newIdx] = oldList[oldIdx];
629 oldIdx++;
630 } else {
631 combinedList[oldIdx + newIdx] = newList[newIdx];
632 newIdx++;
633 }
634 }
635
636 sortedIntervals = combinedList;
637 }
638
639 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
640 // instead of returning null
641 public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
642 Interval result = interval.getSplitChildAtOpId(opId, mode, this);
643
644 if (result != null) {
645 if (Debug.isLogEnabled()) {
646 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
647 }
648 return result;
649 }
650 throw new GraalError("LinearScan: interval is null");
651 }
652
653 static AllocatableValue canonicalSpillOpr(Interval interval) {
654 assert interval.spillSlot() != null : "canonical spill slot not set";
655 return interval.spillSlot();
656 }
657
658 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
659 Interval interval = intervalFor(operand);
660 assert interval != null : "interval must exist";
661
662 if (opId != -1) {
663 /*
664 * Operands are not changed when an interval is split during allocation, so search the
665 * right interval here.
666 */
667 interval = splitChildAtOpId(interval, opId, mode);
668 }
669
670 return isIllegal(interval.location()) && interval.canMaterialize();
671 }
672
673 boolean isCallerSave(Value operand) {
674 return attributes(asRegister(operand)).isCallerSave();
675 }
676
677 @SuppressWarnings("try")
678 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
679 /*
680 * This is the point to enable debug logging for the whole register allocation.
681 */
682 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
683
684 createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
685
686 try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
687 sortIntervalsBeforeAllocation();
688
689 createRegisterAllocationPhase().apply(target, lirGenRes, context);
690
691 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(getOptions())) {
692 createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
693 }
694 createResolveDataFlowPhase().apply(target, lirGenRes, context);
695
696 sortIntervalsAfterAllocation();
697
698 if (detailedAsserts) {
699 verify();
700 }
701 beforeSpillMoveElimination();
702 createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
703 createAssignLocationsPhase().apply(target, lirGenRes, context);
704
705 if (detailedAsserts) {
706 verifyIntervals();
707 }
708 } catch (Throwable e) {
709 throw Debug.handle(e);
710 }
711 }
712 }
713
714 protected void beforeSpillMoveElimination() {
715 }
716
717 protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
718 return new LinearScanLifetimeAnalysisPhase(this);
719 }
720
721 protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() {
722 return new LinearScanRegisterAllocationPhase(this);
723 }
724
725 protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
726 return new LinearScanOptimizeSpillPositionPhase(this);
727 }
728
729 protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
730 return new LinearScanResolveDataFlowPhase(this);
731 }
732
733 protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
734 return new LinearScanEliminateSpillMovePhase(this);
735 }
736
737 protected LinearScanAssignLocationsPhase createAssignLocationsPhase() {
738 return new LinearScanAssignLocationsPhase(this);
739 }
740
741 @SuppressWarnings("try")
742 public void printIntervals(String label) {
743 if (Debug.isLogEnabled()) {
744 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
745 for (Interval interval : intervals) {
746 if (interval != null) {
747 Debug.log("%s", interval.logString(this));
748 }
749 }
750
751 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
752 for (int i = 0; i < blockCount(); i++) {
753 AbstractBlockBase<?> block = blockAt(i);
754 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
755 }
756 }
757 }
758 }
759 Debug.dump(Debug.VERBOSE_LEVEL, new LinearScanIntervalDumper(Arrays.copyOf(intervals, intervalsSize)), label);
760 }
761
762 boolean verify() {
763 // (check that all intervals have a correct register and that no registers are overwritten)
764 verifyIntervals();
765
766 verifyRegisters();
767
768 Debug.log("no errors found");
769
770 return true;
771 }
772
773 @SuppressWarnings("try")
774 private void verifyRegisters() {
775 // Enable this logging to get output for the verification process.
776 try (Indent indent = Debug.logAndIndent("verifying register allocation")) {
777 RegisterVerifier verifier = new RegisterVerifier(this);
778 verifier.verify(blockAt(0));
779 }
780 }
781
782 @SuppressWarnings("try")
783 protected void verifyIntervals() {
784 try (Indent indent = Debug.logAndIndent("verifying intervals")) {
785 int len = intervalsSize;
786
787 for (int i = 0; i < len; i++) {
788 Interval i1 = intervals[i];
789 if (i1 == null) {
790 continue;
791 }
792
793 i1.checkSplitChildren();
794
795 if (i1.operandNumber != i) {
796 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
797 Debug.log(i1.logString(this));
798 throw new GraalError("");
799 }
800
801 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
802 Debug.log("Interval %d has no type assigned", i1.operandNumber);
803 Debug.log(i1.logString(this));
804 throw new GraalError("");
805 }
806
807 if (i1.location() == null) {
808 Debug.log("Interval %d has no register assigned", i1.operandNumber);
809 Debug.log(i1.logString(this));
810 throw new GraalError("");
811 }
812
813 if (i1.first().isEndMarker()) {
814 Debug.log("Interval %d has no Range", i1.operandNumber);
815 Debug.log(i1.logString(this));
816 throw new GraalError("");
817 }
818
819 for (Range r = i1.first(); !r.isEndMarker(); r = r.next) {
820 if (r.from >= r.to) {
821 Debug.log("Interval %d has zero length range", i1.operandNumber);
822 Debug.log(i1.logString(this));
823 throw new GraalError("");
824 }
825 }
826
827 for (int j = i + 1; j < len; j++) {
828 Interval i2 = intervals[j];
829 if (i2 == null) {
830 continue;
831 }
832
833 // special intervals that are created in MoveResolver
834 // . ignore them because the range information has no meaning there
835 if (i1.from() == 1 && i1.to() == 2) {
836 continue;
837 }
838 if (i2.from() == 1 && i2.to() == 2) {
839 continue;
840 }
841 Value l1 = i1.location();
842 Value l2 = i2.location();
849 }
850 }
851
852 class CheckConsumer implements ValueConsumer {
853
854 boolean ok;
855 Interval curInterval;
856
857 @Override
858 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
859 if (isRegister(operand)) {
860 if (intervalFor(operand) == curInterval) {
861 ok = true;
862 }
863 }
864 }
865 }
866
867 @SuppressWarnings("try")
868 void verifyNoOopsInFixedIntervals() {
869 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
870 CheckConsumer checkConsumer = new CheckConsumer();
871
872 Interval fixedIntervals;
873 Interval otherIntervals;
874 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).getLeft();
875 // to ensure a walking until the last instruction id, add a dummy interval
876 // with a high operation id
877 otherIntervals = new Interval(Value.ILLEGAL, -1, intervalEndMarker, rangeEndMarker);
878 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
879 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
880
881 for (AbstractBlockBase<?> block : sortedBlocks) {
882 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
883
884 for (int j = 0; j < instructions.size(); j++) {
885 LIRInstruction op = instructions.get(j);
886
887 if (op.hasState()) {
888 iw.walkBefore(op.id());
889 boolean checkLive = true;
|
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static jdk.vm.ci.code.CodeUtil.isEven;
26 import static jdk.vm.ci.code.ValueUtil.asRegister;
27 import static jdk.vm.ci.code.ValueUtil.isIllegal;
28 import static jdk.vm.ci.code.ValueUtil.isLegal;
29 import static jdk.vm.ci.code.ValueUtil.isRegister;
30 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
32 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
33
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.BitSet;
37 import java.util.EnumSet;
38
39 import org.graalvm.compiler.core.common.LIRKind;
40 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
41 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
42 import org.graalvm.compiler.core.common.cfg.BlockMap;
43 import org.graalvm.compiler.debug.DebugContext;
44 import org.graalvm.compiler.debug.GraalError;
45 import org.graalvm.compiler.debug.Indent;
46 import org.graalvm.compiler.lir.LIR;
47 import org.graalvm.compiler.lir.LIRInstruction;
48 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag;
49 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
50 import org.graalvm.compiler.lir.ValueConsumer;
51 import org.graalvm.compiler.lir.Variable;
52 import org.graalvm.compiler.lir.VirtualStackSlot;
53 import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding;
54 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
55 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
56 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
57 import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext;
58 import org.graalvm.compiler.options.NestedBooleanOptionKey;
59 import org.graalvm.compiler.options.Option;
60 import org.graalvm.compiler.options.OptionKey;
61 import org.graalvm.compiler.options.OptionType;
62 import org.graalvm.compiler.options.OptionValues;
63 import org.graalvm.util.Pair;
110 public BitSet liveGen;
111
112 /**
113 * Bit map specifying which operands are defined/overwritten in this block. The bit index of
114 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
115 */
116 public BitSet liveKill;
117 }
118
119 public static final int DOMINATOR_SPILL_MOVE_ID = -2;
120 private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
121
122 private final LIR ir;
123 private final FrameMapBuilder frameMapBuilder;
124 private final RegisterAttributes[] registerAttributes;
125 private final RegisterArray registers;
126 private final RegisterAllocationConfig regAllocConfig;
127 private final MoveFactory moveFactory;
128
129 private final BlockMap<BlockData> blockData;
130 protected final DebugContext debug;
131
132 /**
133 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
134 */
135 private final AbstractBlockBase<?>[] sortedBlocks;
136
137 /**
138 * @see #intervals()
139 */
140 private Interval[] intervals;
141
142 /**
143 * The number of valid entries in {@link #intervals}.
144 */
145 private int intervalsSize;
146
147 /**
148 * The index of the first entry in {@link #intervals} for a
149 * {@linkplain #createDerivedInterval(Interval) derived interval}.
150 */
174 */
175 private final int firstVariableNumber;
176 /**
177 * Number of variables.
178 */
179 private int numVariables;
180 private final boolean neverSpillConstants;
181
182 /**
183 * Sentinel interval to denote the end of an interval list.
184 */
185 protected final Interval intervalEndMarker;
186 public final Range rangeEndMarker;
187 public final boolean detailedAsserts;
188 private final LIRGenerationResult res;
189
190 protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks,
191 boolean neverSpillConstants) {
192 this.ir = res.getLIR();
193 this.res = res;
194 this.debug = ir.getDebug();
195 this.moveFactory = spillMoveFactory;
196 this.frameMapBuilder = res.getFrameMapBuilder();
197 this.sortedBlocks = sortedBlocks;
198 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
199 this.regAllocConfig = regAllocConfig;
200
201 this.registers = target.arch.getRegisters();
202 this.firstVariableNumber = getRegisters().size();
203 this.numVariables = ir.numVariables();
204 this.blockData = new BlockMap<>(ir.getControlFlowGraph());
205 this.neverSpillConstants = neverSpillConstants;
206 this.rangeEndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
207 this.intervalEndMarker = new Interval(Value.ILLEGAL, Interval.END_MARKER_OPERAND_NUMBER, null, rangeEndMarker);
208 this.intervalEndMarker.next = intervalEndMarker;
209 this.detailedAsserts = DetailedAsserts.getValue(ir.getOptions());
210 }
211
212 public LIRGenerationResult getLIRGenerationResult() {
213 return res;
214 }
215
216 public Interval intervalEndMarker() {
217 return intervalEndMarker;
218 }
219
220 public OptionValues getOptions() {
221 return ir.getOptions();
222 }
223
224 public DebugContext getDebug() {
225 return debug;
226 }
227
228 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
229 int result = ir.getLIRforBlock(block).get(0).id();
230 assert result >= 0;
231 return result;
232 }
233
234 public int getLastLirInstructionId(AbstractBlockBase<?> block) {
235 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
236 int result = instructions.get(instructions.size() - 1).id();
237 assert result >= 0;
238 return result;
239 }
240
241 public MoveFactory getSpillMoveFactory() {
242 return moveFactory;
243 }
244
245 protected MoveResolver createMoveResolver() {
246 MoveResolver moveResolver = new MoveResolver(this);
247 assert moveResolver.checkEmpty();
630
631 while (oldIdx + newIdx < combinedList.length) {
632 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) {
633 combinedList[oldIdx + newIdx] = oldList[oldIdx];
634 oldIdx++;
635 } else {
636 combinedList[oldIdx + newIdx] = newList[newIdx];
637 newIdx++;
638 }
639 }
640
641 sortedIntervals = combinedList;
642 }
643
644 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
645 // instead of returning null
646 public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
647 Interval result = interval.getSplitChildAtOpId(opId, mode, this);
648
649 if (result != null) {
650 if (debug.isLogEnabled()) {
651 debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
652 }
653 return result;
654 }
655 throw new GraalError("LinearScan: interval is null");
656 }
657
658 static AllocatableValue canonicalSpillOpr(Interval interval) {
659 assert interval.spillSlot() != null : "canonical spill slot not set";
660 return interval.spillSlot();
661 }
662
663 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
664 Interval interval = intervalFor(operand);
665 assert interval != null : "interval must exist";
666
667 if (opId != -1) {
668 /*
669 * Operands are not changed when an interval is split during allocation, so search the
670 * right interval here.
671 */
672 interval = splitChildAtOpId(interval, opId, mode);
673 }
674
675 return isIllegal(interval.location()) && interval.canMaterialize();
676 }
677
678 boolean isCallerSave(Value operand) {
679 return attributes(asRegister(operand)).isCallerSave();
680 }
681
682 @SuppressWarnings("try")
683 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
684 /*
685 * This is the point to enable debug logging for the whole register allocation.
686 */
687 try (Indent indent = debug.logAndIndent("LinearScan allocate")) {
688
689 createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
690
691 try (DebugContext.Scope s = debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
692 sortIntervalsBeforeAllocation();
693
694 createRegisterAllocationPhase().apply(target, lirGenRes, context);
695
696 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(getOptions())) {
697 createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
698 }
699 createResolveDataFlowPhase().apply(target, lirGenRes, context);
700
701 sortIntervalsAfterAllocation();
702
703 if (detailedAsserts) {
704 verify();
705 }
706 beforeSpillMoveElimination();
707 createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
708 createAssignLocationsPhase().apply(target, lirGenRes, context);
709
710 if (detailedAsserts) {
711 verifyIntervals();
712 }
713 } catch (Throwable e) {
714 throw debug.handle(e);
715 }
716 }
717 }
718
719 protected void beforeSpillMoveElimination() {
720 }
721
722 protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
723 return new LinearScanLifetimeAnalysisPhase(this);
724 }
725
726 protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() {
727 return new LinearScanRegisterAllocationPhase(this);
728 }
729
730 protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
731 return new LinearScanOptimizeSpillPositionPhase(this);
732 }
733
734 protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
735 return new LinearScanResolveDataFlowPhase(this);
736 }
737
738 protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
739 return new LinearScanEliminateSpillMovePhase(this);
740 }
741
742 protected LinearScanAssignLocationsPhase createAssignLocationsPhase() {
743 return new LinearScanAssignLocationsPhase(this);
744 }
745
746 @SuppressWarnings("try")
747 public void printIntervals(String label) {
748 if (debug.isLogEnabled()) {
749 try (Indent indent = debug.logAndIndent("intervals %s", label)) {
750 for (Interval interval : intervals) {
751 if (interval != null) {
752 debug.log("%s", interval.logString(this));
753 }
754 }
755
756 try (Indent indent2 = debug.logAndIndent("Basic Blocks")) {
757 for (int i = 0; i < blockCount(); i++) {
758 AbstractBlockBase<?> block = blockAt(i);
759 debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
760 }
761 }
762 }
763 }
764 debug.dump(DebugContext.VERBOSE_LEVEL, new LinearScanIntervalDumper(Arrays.copyOf(intervals, intervalsSize)), label);
765 }
766
767 boolean verify() {
768 // (check that all intervals have a correct register and that no registers are overwritten)
769 verifyIntervals();
770
771 verifyRegisters();
772
773 debug.log("no errors found");
774
775 return true;
776 }
777
778 @SuppressWarnings("try")
779 private void verifyRegisters() {
780 // Enable this logging to get output for the verification process.
781 try (Indent indent = debug.logAndIndent("verifying register allocation")) {
782 RegisterVerifier verifier = new RegisterVerifier(this);
783 verifier.verify(blockAt(0));
784 }
785 }
786
787 @SuppressWarnings("try")
788 protected void verifyIntervals() {
789 try (Indent indent = debug.logAndIndent("verifying intervals")) {
790 int len = intervalsSize;
791
792 for (int i = 0; i < len; i++) {
793 Interval i1 = intervals[i];
794 if (i1 == null) {
795 continue;
796 }
797
798 i1.checkSplitChildren();
799
800 if (i1.operandNumber != i) {
801 debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
802 debug.log(i1.logString(this));
803 throw new GraalError("");
804 }
805
806 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
807 debug.log("Interval %d has no type assigned", i1.operandNumber);
808 debug.log(i1.logString(this));
809 throw new GraalError("");
810 }
811
812 if (i1.location() == null) {
813 debug.log("Interval %d has no register assigned", i1.operandNumber);
814 debug.log(i1.logString(this));
815 throw new GraalError("");
816 }
817
818 if (i1.first().isEndMarker()) {
819 debug.log("Interval %d has no Range", i1.operandNumber);
820 debug.log(i1.logString(this));
821 throw new GraalError("");
822 }
823
824 for (Range r = i1.first(); !r.isEndMarker(); r = r.next) {
825 if (r.from >= r.to) {
826 debug.log("Interval %d has zero length range", i1.operandNumber);
827 debug.log(i1.logString(this));
828 throw new GraalError("");
829 }
830 }
831
832 for (int j = i + 1; j < len; j++) {
833 Interval i2 = intervals[j];
834 if (i2 == null) {
835 continue;
836 }
837
838 // special intervals that are created in MoveResolver
839 // . ignore them because the range information has no meaning there
840 if (i1.from() == 1 && i1.to() == 2) {
841 continue;
842 }
843 if (i2.from() == 1 && i2.to() == 2) {
844 continue;
845 }
846 Value l1 = i1.location();
847 Value l2 = i2.location();
854 }
855 }
856
857 class CheckConsumer implements ValueConsumer {
858
859 boolean ok;
860 Interval curInterval;
861
862 @Override
863 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
864 if (isRegister(operand)) {
865 if (intervalFor(operand) == curInterval) {
866 ok = true;
867 }
868 }
869 }
870 }
871
872 @SuppressWarnings("try")
873 void verifyNoOopsInFixedIntervals() {
874 try (Indent indent = debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
875 CheckConsumer checkConsumer = new CheckConsumer();
876
877 Interval fixedIntervals;
878 Interval otherIntervals;
879 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).getLeft();
880 // to ensure a walking until the last instruction id, add a dummy interval
881 // with a high operation id
882 otherIntervals = new Interval(Value.ILLEGAL, -1, intervalEndMarker, rangeEndMarker);
883 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
884 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
885
886 for (AbstractBlockBase<?> block : sortedBlocks) {
887 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
888
889 for (int j = 0; j < instructions.size(); j++) {
890 LIRInstruction op = instructions.get(j);
891
892 if (op.hasState()) {
893 iw.walkBefore(op.id());
894 boolean checkLive = true;
|