5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package org.graalvm.compiler.lir.alloc.lsra;
24
25 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
26 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
27 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization;
28 import static jdk.vm.ci.code.CodeUtil.isEven;
29 import static jdk.vm.ci.code.ValueUtil.asRegister;
30 import static jdk.vm.ci.code.ValueUtil.isIllegal;
31 import static jdk.vm.ci.code.ValueUtil.isLegal;
32 import static jdk.vm.ci.code.ValueUtil.isRegister;
33
34 import java.util.Arrays;
35 import java.util.BitSet;
36 import java.util.EnumSet;
37 import java.util.List;
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.NestedBooleanOptionValue;
60 import org.graalvm.compiler.options.Option;
61 import org.graalvm.compiler.options.OptionType;
62 import org.graalvm.compiler.options.OptionValue;
63
64 import jdk.vm.ci.code.Register;
65 import jdk.vm.ci.code.RegisterArray;
66 import jdk.vm.ci.code.RegisterAttributes;
67 import jdk.vm.ci.code.RegisterValue;
68 import jdk.vm.ci.code.TargetDescription;
69 import jdk.vm.ci.meta.AllocatableValue;
70 import jdk.vm.ci.meta.Value;
71
72 /**
73 * An implementation of the linear scan register allocator algorithm described in
74 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear
75 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck.
76 */
77 public class LinearScan {
78
79 public static class Options {
80 // @formatter:off
81 @Option(help = "Enable spill position optimization", type = OptionType.Debug)
82 public static final OptionValue<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionValue(LIROptimization, true);
83 // @formatter:on
84 }
85
86 public static class BlockData {
87
88 /**
89 * Bit map specifying which operands are live upon entry to this block. These are values
90 * used in this block or any of its successors where such value are not defined in this
91 * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value)
92 * operand number}.
93 */
94 public BitSet liveIn;
95
96 /**
97 * Bit map specifying which operands are live upon exit from this block. These are values
98 * used in a successor block that are either defined in this block or were live upon entry
99 * to this block. The bit index of an operand is its
100 * {@linkplain LinearScan#operandNumber(Value) operand number}.
101 */
102 public BitSet liveOut;
160 */
161 private LIRInstruction[] opIdToInstructionMap;
162
163 /**
164 * Map from an instruction {@linkplain LIRInstruction#id id} to the
165 * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved
166 * with {@link #blockForId(int)} as the id is not simply an index into this array.
167 */
168 private AbstractBlockBase<?>[] opIdToBlockMap;
169
170 /**
171 * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
172 */
173 private final int firstVariableNumber;
174 /**
175 * Number of variables.
176 */
177 private int numVariables;
178 private final boolean neverSpillConstants;
179
180 protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks,
181 boolean neverSpillConstants) {
182 this.ir = res.getLIR();
183 this.moveFactory = spillMoveFactory;
184 this.frameMapBuilder = res.getFrameMapBuilder();
185 this.sortedBlocks = sortedBlocks;
186 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
187 this.regAllocConfig = regAllocConfig;
188
189 this.registers = target.arch.getRegisters();
190 this.firstVariableNumber = getRegisters().size();
191 this.numVariables = ir.numVariables();
192 this.blockData = new BlockMap<>(ir.getControlFlowGraph());
193 this.neverSpillConstants = neverSpillConstants;
194 }
195
196 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
197 int result = ir.getLIRforBlock(block).get(0).id();
198 assert result >= 0;
199 return result;
200 }
201
202 public int getLastLirInstructionId(AbstractBlockBase<?> block) {
203 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
204 int result = instructions.get(instructions.size() - 1).id();
205 assert result >= 0;
206 return result;
207 }
208
209 public MoveFactory getSpillMoveFactory() {
210 return moveFactory;
211 }
212
213 protected MoveResolver createMoveResolver() {
214 MoveResolver moveResolver = new MoveResolver(this);
215 assert moveResolver.checkEmpty();
216 return moveResolver;
217 }
218
219 public static boolean isVariableOrRegister(Value value) {
220 return isVariable(value) || isRegister(value);
221 }
222
223 /**
309 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
310 */
311 public Interval[] intervals() {
312 return intervals;
313 }
314
315 void initIntervals() {
316 intervalsSize = operandSize();
317 intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
318 }
319
320 /**
321 * Creates a new interval.
322 *
323 * @param operand the operand for the interval
324 * @return the created interval
325 */
326 Interval createInterval(AllocatableValue operand) {
327 assert isLegal(operand);
328 int operandNumber = operandNumber(operand);
329 Interval interval = new Interval(operand, operandNumber);
330 assert operandNumber < intervalsSize;
331 assert intervals[operandNumber] == null;
332 intervals[operandNumber] = interval;
333 return interval;
334 }
335
336 /**
337 * Creates an interval as a result of splitting or spilling another interval.
338 *
339 * @param source an interval being split of spilled
340 * @return a new interval derived from {@code source}
341 */
342 Interval createDerivedInterval(Interval source) {
343 if (firstDerivedIntervalIndex == -1) {
344 firstDerivedIntervalIndex = intervalsSize;
345 }
346 if (intervalsSize == intervals.length) {
347 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT) + 1);
348 }
349 intervalsSize++;
485 private static boolean isSorted(Interval[] intervals) {
486 int from = -1;
487 for (Interval interval : intervals) {
488 assert interval != null;
489 assert from <= interval.from();
490 from = interval.from();
491 }
492 return true;
493 }
494
495 static Interval addToList(Interval first, Interval prev, Interval interval) {
496 Interval newFirst = first;
497 if (prev != null) {
498 prev.next = interval;
499 } else {
500 newFirst = interval;
501 }
502 return newFirst;
503 }
504
505 Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
506 assert isSorted(sortedIntervals) : "interval list is not sorted";
507
508 Interval list1 = Interval.EndMarker;
509 Interval list2 = Interval.EndMarker;
510
511 Interval list1Prev = null;
512 Interval list2Prev = null;
513 Interval v;
514
515 int n = sortedIntervals.length;
516 for (int i = 0; i < n; i++) {
517 v = sortedIntervals[i];
518 if (v == null) {
519 continue;
520 }
521
522 if (isList1.apply(v)) {
523 list1 = addToList(list1, list1Prev, v);
524 list1Prev = v;
525 } else if (isList2 == null || isList2.apply(v)) {
526 list2 = addToList(list2, list2Prev, v);
527 list2Prev = v;
528 }
529 }
530
531 if (list1Prev != null) {
532 list1Prev.next = Interval.EndMarker;
533 }
534 if (list2Prev != null) {
535 list2Prev.next = Interval.EndMarker;
536 }
537
538 assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
539 assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
540
541 return new Interval.Pair(list1, list2);
542 }
543
544 protected void sortIntervalsBeforeAllocation() {
545 int sortedLen = 0;
546 for (Interval interval : intervals) {
547 if (interval != null) {
548 sortedLen++;
549 }
550 }
551
552 Interval[] sortedList = new Interval[sortedLen];
553 int sortedIdx = 0;
554 int sortedFromMax = -1;
555
556 // special sorting algorithm: the original interval-list is almost sorted,
557 // only some intervals are swapped. So this is much faster than a complete QuickSort
558 for (Interval interval : intervals) {
559 if (interval != null) {
560 int from = interval.from();
561
631 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
632 Interval interval = intervalFor(operand);
633 assert interval != null : "interval must exist";
634
635 if (opId != -1) {
636 /*
637 * Operands are not changed when an interval is split during allocation, so search the
638 * right interval here.
639 */
640 interval = splitChildAtOpId(interval, opId, mode);
641 }
642
643 return isIllegal(interval.location()) && interval.canMaterialize();
644 }
645
646 boolean isCallerSave(Value operand) {
647 return attributes(asRegister(operand)).isCallerSave();
648 }
649
650 @SuppressWarnings("try")
651 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) {
652
653 /*
654 * This is the point to enable debug logging for the whole register allocation.
655 */
656 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
657 AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig);
658
659 createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
660
661 try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
662 sortIntervalsBeforeAllocation();
663
664 createRegisterAllocationPhase().apply(target, lirGenRes, context);
665
666 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) {
667 createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
668 }
669 createResolveDataFlowPhase().apply(target, lirGenRes, context);
670
671 sortIntervalsAfterAllocation();
672
673 if (DetailedAsserts.getValue()) {
674 verify();
675 }
676 beforeSpillMoveElimination();
677 createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
678 createAssignLocationsPhase().apply(target, lirGenRes, context);
679
680 if (DetailedAsserts.getValue()) {
681 verifyIntervals();
682 }
683 } catch (Throwable e) {
684 throw Debug.handle(e);
685 }
686 }
687 }
688
689 protected void beforeSpillMoveElimination() {
690 }
691
692 protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
693 return new LinearScanLifetimeAnalysisPhase(this);
694 }
695
696 protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() {
697 return new LinearScanRegisterAllocationPhase(this);
698 }
699
700 protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
772 i1.checkSplitChildren();
773
774 if (i1.operandNumber != i) {
775 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
776 Debug.log(i1.logString(this));
777 throw new GraalError("");
778 }
779
780 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
781 Debug.log("Interval %d has no type assigned", i1.operandNumber);
782 Debug.log(i1.logString(this));
783 throw new GraalError("");
784 }
785
786 if (i1.location() == null) {
787 Debug.log("Interval %d has no register assigned", i1.operandNumber);
788 Debug.log(i1.logString(this));
789 throw new GraalError("");
790 }
791
792 if (i1.first() == Range.EndMarker) {
793 Debug.log("Interval %d has no Range", i1.operandNumber);
794 Debug.log(i1.logString(this));
795 throw new GraalError("");
796 }
797
798 for (Range r = i1.first(); r != Range.EndMarker; r = r.next) {
799 if (r.from >= r.to) {
800 Debug.log("Interval %d has zero length range", i1.operandNumber);
801 Debug.log(i1.logString(this));
802 throw new GraalError("");
803 }
804 }
805
806 for (int j = i + 1; j < len; j++) {
807 Interval i2 = intervals[j];
808 if (i2 == null) {
809 continue;
810 }
811
812 // special intervals that are created in MoveResolver
813 // . ignore them because the range information has no meaning there
814 if (i1.from() == 1 && i1.to() == 2) {
815 continue;
816 }
817 if (i2.from() == 1 && i2.to() == 2) {
818 continue;
833 boolean ok;
834 Interval curInterval;
835
836 @Override
837 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
838 if (isRegister(operand)) {
839 if (intervalFor(operand) == curInterval) {
840 ok = true;
841 }
842 }
843 }
844 }
845
846 @SuppressWarnings("try")
847 void verifyNoOopsInFixedIntervals() {
848 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
849 CheckConsumer checkConsumer = new CheckConsumer();
850
851 Interval fixedIntervals;
852 Interval otherIntervals;
853 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
854 // to ensure a walking until the last instruction id, add a dummy interval
855 // with a high operation id
856 otherIntervals = new Interval(Value.ILLEGAL, -1);
857 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
858 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
859
860 for (AbstractBlockBase<?> block : sortedBlocks) {
861 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
862
863 for (int j = 0; j < instructions.size(); j++) {
864 LIRInstruction op = instructions.get(j);
865
866 if (op.hasState()) {
867 iw.walkBefore(op.id());
868 boolean checkLive = true;
869
870 /*
871 * Make sure none of the fixed registers is live across an oopmap since we
872 * can't handle that correctly.
873 */
874 if (checkLive) {
875 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
876 if (interval.currentTo() > op.id() + 1) {
877 /*
878 * This interval is live out of this op so make sure that this
879 * interval represents some value that's referenced by this op
880 * either as an input or output.
881 */
882 checkConsumer.curInterval = interval;
883 checkConsumer.ok = false;
884
885 op.visitEachInput(checkConsumer);
886 op.visitEachAlive(checkConsumer);
887 op.visitEachTemp(checkConsumer);
888 op.visitEachOutput(checkConsumer);
889
890 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point";
891 }
892 }
893 }
894 }
895 }
|
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
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;
65
66 import jdk.vm.ci.code.Register;
67 import jdk.vm.ci.code.RegisterArray;
68 import jdk.vm.ci.code.RegisterAttributes;
69 import jdk.vm.ci.code.RegisterValue;
70 import jdk.vm.ci.code.TargetDescription;
71 import jdk.vm.ci.meta.AllocatableValue;
72 import jdk.vm.ci.meta.Value;
73
74 /**
75 * An implementation of the linear scan register allocator algorithm described in
76 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear
77 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck.
78 */
79 public class LinearScan {
80
81 public static class Options {
82 // @formatter:off
83 @Option(help = "Enable spill position optimization", type = OptionType.Debug)
84 public static final OptionKey<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionKey(LIROptimization, true);
85 // @formatter:on
86 }
87
88 public static class BlockData {
89
90 /**
91 * Bit map specifying which operands are live upon entry to this block. These are values
92 * used in this block or any of its successors where such value are not defined in this
93 * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value)
94 * operand number}.
95 */
96 public BitSet liveIn;
97
98 /**
99 * Bit map specifying which operands are live upon exit from this block. These are values
100 * used in a successor block that are either defined in this block or were live upon entry
101 * to this block. The bit index of an operand is its
102 * {@linkplain LinearScan#operandNumber(Value) operand number}.
103 */
104 public BitSet liveOut;
162 */
163 private LIRInstruction[] opIdToInstructionMap;
164
165 /**
166 * Map from an instruction {@linkplain LIRInstruction#id id} to the
167 * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be retrieved
168 * with {@link #blockForId(int)} as the id is not simply an index into this array.
169 */
170 private AbstractBlockBase<?>[] opIdToBlockMap;
171
172 /**
173 * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
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
189 protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks,
190 boolean neverSpillConstants) {
191 this.ir = res.getLIR();
192 this.moveFactory = spillMoveFactory;
193 this.frameMapBuilder = res.getFrameMapBuilder();
194 this.sortedBlocks = sortedBlocks;
195 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
196 this.regAllocConfig = regAllocConfig;
197
198 this.registers = target.arch.getRegisters();
199 this.firstVariableNumber = getRegisters().size();
200 this.numVariables = ir.numVariables();
201 this.blockData = new BlockMap<>(ir.getControlFlowGraph());
202 this.neverSpillConstants = neverSpillConstants;
203 this.rangeEndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
204 this.intervalEndMarker = new Interval(Value.ILLEGAL, Interval.END_MARKER_OPERAND_NUMBER, null, rangeEndMarker);
205 this.intervalEndMarker.next = intervalEndMarker;
206 this.detailedAsserts = DetailedAsserts.getValue(ir.getOptions());
207 }
208
209 public Interval intervalEndMarker() {
210 return intervalEndMarker;
211 }
212
213 public OptionValues getOptions() {
214 return ir.getOptions();
215 }
216
217 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
218 int result = ir.getLIRforBlock(block).get(0).id();
219 assert result >= 0;
220 return result;
221 }
222
223 public int getLastLirInstructionId(AbstractBlockBase<?> block) {
224 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
225 int result = instructions.get(instructions.size() - 1).id();
226 assert result >= 0;
227 return result;
228 }
229
230 public MoveFactory getSpillMoveFactory() {
231 return moveFactory;
232 }
233
234 protected MoveResolver createMoveResolver() {
235 MoveResolver moveResolver = new MoveResolver(this);
236 assert moveResolver.checkEmpty();
237 return moveResolver;
238 }
239
240 public static boolean isVariableOrRegister(Value value) {
241 return isVariable(value) || isRegister(value);
242 }
243
244 /**
330 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
331 */
332 public Interval[] intervals() {
333 return intervals;
334 }
335
336 void initIntervals() {
337 intervalsSize = operandSize();
338 intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
339 }
340
341 /**
342 * Creates a new interval.
343 *
344 * @param operand the operand for the interval
345 * @return the created interval
346 */
347 Interval createInterval(AllocatableValue operand) {
348 assert isLegal(operand);
349 int operandNumber = operandNumber(operand);
350 Interval interval = new Interval(operand, operandNumber, intervalEndMarker, rangeEndMarker);
351 assert operandNumber < intervalsSize;
352 assert intervals[operandNumber] == null;
353 intervals[operandNumber] = interval;
354 return interval;
355 }
356
357 /**
358 * Creates an interval as a result of splitting or spilling another interval.
359 *
360 * @param source an interval being split of spilled
361 * @return a new interval derived from {@code source}
362 */
363 Interval createDerivedInterval(Interval source) {
364 if (firstDerivedIntervalIndex == -1) {
365 firstDerivedIntervalIndex = intervalsSize;
366 }
367 if (intervalsSize == intervals.length) {
368 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT) + 1);
369 }
370 intervalsSize++;
506 private static boolean isSorted(Interval[] intervals) {
507 int from = -1;
508 for (Interval interval : intervals) {
509 assert interval != null;
510 assert from <= interval.from();
511 from = interval.from();
512 }
513 return true;
514 }
515
516 static Interval addToList(Interval first, Interval prev, Interval interval) {
517 Interval newFirst = first;
518 if (prev != null) {
519 prev.next = interval;
520 } else {
521 newFirst = interval;
522 }
523 return newFirst;
524 }
525
526 Pair<Interval, Interval> createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
527 assert isSorted(sortedIntervals) : "interval list is not sorted";
528
529 Interval list1 = intervalEndMarker;
530 Interval list2 = intervalEndMarker;
531
532 Interval list1Prev = null;
533 Interval list2Prev = null;
534 Interval v;
535
536 int n = sortedIntervals.length;
537 for (int i = 0; i < n; i++) {
538 v = sortedIntervals[i];
539 if (v == null) {
540 continue;
541 }
542
543 if (isList1.apply(v)) {
544 list1 = addToList(list1, list1Prev, v);
545 list1Prev = v;
546 } else if (isList2 == null || isList2.apply(v)) {
547 list2 = addToList(list2, list2Prev, v);
548 list2Prev = v;
549 }
550 }
551
552 if (list1Prev != null) {
553 list1Prev.next = intervalEndMarker;
554 }
555 if (list2Prev != null) {
556 list2Prev.next = intervalEndMarker;
557 }
558
559 assert list1Prev == null || list1Prev.next.isEndMarker() : "linear list ends not with sentinel";
560 assert list2Prev == null || list2Prev.next.isEndMarker() : "linear list ends not with sentinel";
561
562 return Pair.create(list1, list2);
563 }
564
565 protected void sortIntervalsBeforeAllocation() {
566 int sortedLen = 0;
567 for (Interval interval : intervals) {
568 if (interval != null) {
569 sortedLen++;
570 }
571 }
572
573 Interval[] sortedList = new Interval[sortedLen];
574 int sortedIdx = 0;
575 int sortedFromMax = -1;
576
577 // special sorting algorithm: the original interval-list is almost sorted,
578 // only some intervals are swapped. So this is much faster than a complete QuickSort
579 for (Interval interval : intervals) {
580 if (interval != null) {
581 int from = interval.from();
582
652 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
653 Interval interval = intervalFor(operand);
654 assert interval != null : "interval must exist";
655
656 if (opId != -1) {
657 /*
658 * Operands are not changed when an interval is split during allocation, so search the
659 * right interval here.
660 */
661 interval = splitChildAtOpId(interval, opId, mode);
662 }
663
664 return isIllegal(interval.location()) && interval.canMaterialize();
665 }
666
667 boolean isCallerSave(Value operand) {
668 return attributes(asRegister(operand)).isCallerSave();
669 }
670
671 @SuppressWarnings("try")
672 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) {
673 /*
674 * This is the point to enable debug logging for the whole register allocation.
675 */
676 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
677
678 createLifetimeAnalysisPhase().apply(target, lirGenRes, context);
679
680 try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) {
681 sortIntervalsBeforeAllocation();
682
683 createRegisterAllocationPhase().apply(target, lirGenRes, context);
684
685 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(getOptions())) {
686 createOptimizeSpillPositionPhase().apply(target, lirGenRes, context);
687 }
688 createResolveDataFlowPhase().apply(target, lirGenRes, context);
689
690 sortIntervalsAfterAllocation();
691
692 if (detailedAsserts) {
693 verify();
694 }
695 beforeSpillMoveElimination();
696 createSpillMoveEliminationPhase().apply(target, lirGenRes, context);
697 createAssignLocationsPhase().apply(target, lirGenRes, context);
698
699 if (detailedAsserts) {
700 verifyIntervals();
701 }
702 } catch (Throwable e) {
703 throw Debug.handle(e);
704 }
705 }
706 }
707
708 protected void beforeSpillMoveElimination() {
709 }
710
711 protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
712 return new LinearScanLifetimeAnalysisPhase(this);
713 }
714
715 protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() {
716 return new LinearScanRegisterAllocationPhase(this);
717 }
718
719 protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
791 i1.checkSplitChildren();
792
793 if (i1.operandNumber != i) {
794 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
795 Debug.log(i1.logString(this));
796 throw new GraalError("");
797 }
798
799 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) {
800 Debug.log("Interval %d has no type assigned", i1.operandNumber);
801 Debug.log(i1.logString(this));
802 throw new GraalError("");
803 }
804
805 if (i1.location() == null) {
806 Debug.log("Interval %d has no register assigned", i1.operandNumber);
807 Debug.log(i1.logString(this));
808 throw new GraalError("");
809 }
810
811 if (i1.first().isEndMarker()) {
812 Debug.log("Interval %d has no Range", i1.operandNumber);
813 Debug.log(i1.logString(this));
814 throw new GraalError("");
815 }
816
817 for (Range r = i1.first(); !r.isEndMarker(); r = r.next) {
818 if (r.from >= r.to) {
819 Debug.log("Interval %d has zero length range", i1.operandNumber);
820 Debug.log(i1.logString(this));
821 throw new GraalError("");
822 }
823 }
824
825 for (int j = i + 1; j < len; j++) {
826 Interval i2 = intervals[j];
827 if (i2 == null) {
828 continue;
829 }
830
831 // special intervals that are created in MoveResolver
832 // . ignore them because the range information has no meaning there
833 if (i1.from() == 1 && i1.to() == 2) {
834 continue;
835 }
836 if (i2.from() == 1 && i2.to() == 2) {
837 continue;
852 boolean ok;
853 Interval curInterval;
854
855 @Override
856 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
857 if (isRegister(operand)) {
858 if (intervalFor(operand) == curInterval) {
859 ok = true;
860 }
861 }
862 }
863 }
864
865 @SuppressWarnings("try")
866 void verifyNoOopsInFixedIntervals() {
867 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
868 CheckConsumer checkConsumer = new CheckConsumer();
869
870 Interval fixedIntervals;
871 Interval otherIntervals;
872 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).getLeft();
873 // to ensure a walking until the last instruction id, add a dummy interval
874 // with a high operation id
875 otherIntervals = new Interval(Value.ILLEGAL, -1, intervalEndMarker, rangeEndMarker);
876 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
877 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
878
879 for (AbstractBlockBase<?> block : sortedBlocks) {
880 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block);
881
882 for (int j = 0; j < instructions.size(); j++) {
883 LIRInstruction op = instructions.get(j);
884
885 if (op.hasState()) {
886 iw.walkBefore(op.id());
887 boolean checkLive = true;
888
889 /*
890 * Make sure none of the fixed registers is live across an oopmap since we
891 * can't handle that correctly.
892 */
893 if (checkLive) {
894 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); !interval.isEndMarker(); interval = interval.next) {
895 if (interval.currentTo() > op.id() + 1) {
896 /*
897 * This interval is live out of this op so make sure that this
898 * interval represents some value that's referenced by this op
899 * either as an input or output.
900 */
901 checkConsumer.curInterval = interval;
902 checkConsumer.ok = false;
903
904 op.visitEachInput(checkConsumer);
905 op.visitEachAlive(checkConsumer);
906 op.visitEachTemp(checkConsumer);
907 op.visitEachOutput(checkConsumer);
908
909 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point";
910 }
911 }
912 }
913 }
914 }
|