1 /*
2 * Copyright (c) 2009, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
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.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;
64
65 import jdk.vm.ci.code.Register;
66 import jdk.vm.ci.code.RegisterArray;
67 import jdk.vm.ci.code.RegisterAttributes;
68 import jdk.vm.ci.code.RegisterValue;
69 import jdk.vm.ci.code.TargetDescription;
70 import jdk.vm.ci.meta.AllocatableValue;
71 import jdk.vm.ci.meta.Value;
72
73 /**
74 * An implementation of the linear scan register allocator algorithm described in
75 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear
76 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck.
77 */
78 public class LinearScan {
79
80 public static class Options {
81 // @formatter:off
82 @Option(help = "Enable spill position optimization", type = OptionType.Debug)
83 public static final OptionKey<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionKey(LIROptimization, true);
84 // @formatter:on
85 }
86
87 public static class BlockData {
88
89 /**
90 * Bit map specifying which operands are live upon entry to this block. These are values
91 * used in this block or any of its successors where such value are not defined in this
92 * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value)
93 * operand number}.
94 */
95 public BitSet liveIn;
96
97 /**
98 * Bit map specifying which operands are live upon exit from this block. These are values
99 * used in a successor block that are either defined in this block or were live upon entry
100 * to this block. The bit index of an operand is its
101 * {@linkplain LinearScan#operandNumber(Value) operand number}.
102 */
103 public BitSet liveOut;
104
105 /**
106 * Bit map specifying which operands are used (before being defined) in this block. That is,
107 * these are the values that are live upon entry to the block. The bit index of an operand
108 * is its {@linkplain LinearScan#operandNumber(Value) operand number}.
109 */
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 */
151 private int firstDerivedIntervalIndex = -1;
152
153 /**
154 * Intervals sorted by {@link Interval#from()}.
155 */
156 private Interval[] sortedIntervals;
157
158 /**
159 * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
160 * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this
161 * array.
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 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();
248 return moveResolver;
249 }
250
251 public static boolean isVariableOrRegister(Value value) {
252 return isVariable(value) || isRegister(value);
253 }
254
255 /**
256 * Converts an operand (variable or register) to an index in a flat address space covering all
257 * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
258 * by this allocator.
259 */
260 int operandNumber(Value operand) {
261 if (isRegister(operand)) {
262 int number = asRegister(operand).number;
263 assert number < firstVariableNumber;
264 return number;
265 }
266 assert isVariable(operand) : operand;
267 return firstVariableNumber + ((Variable) operand).index;
268 }
269
270 /**
271 * Gets the number of operands. This value will increase by 1 for new variable.
272 */
273 int operandSize() {
274 return firstVariableNumber + numVariables;
275 }
276
277 /**
278 * Gets the highest operand number for a register operand. This value will never change.
279 */
280 int maxRegisterNumber() {
281 return firstVariableNumber - 1;
282 }
283
284 public BlockData getBlockData(AbstractBlockBase<?> block) {
285 return blockData.get(block);
286 }
287
288 void initBlockData(AbstractBlockBase<?> block) {
289 blockData.put(block, new BlockData());
290 }
291
292 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
293
294 @Override
295 public boolean apply(Interval i) {
296 return isRegister(i.operand);
297 }
298 };
299
300 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
301
302 @Override
303 public boolean apply(Interval i) {
304 return isVariable(i.operand);
305 }
306 };
307
308 static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() {
309
310 @Override
311 public boolean apply(Interval i) {
312 return !isRegister(i.operand);
313 }
314 };
315
316 /**
317 * Gets an object describing the attributes of a given register according to this register
318 * configuration.
319 */
320 public RegisterAttributes attributes(Register reg) {
321 return registerAttributes[reg.number];
322 }
323
324 void assignSpillSlot(Interval interval) {
325 /*
326 * Assign the canonical spill slot of the parent (if a part of the interval is already
327 * spilled) or allocate a new spill slot.
328 */
329 if (interval.canMaterialize()) {
330 interval.assignLocation(Value.ILLEGAL);
331 } else if (interval.spillSlot() != null) {
332 interval.assignLocation(interval.spillSlot());
333 } else {
334 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind());
335 interval.setSpillSlot(slot);
336 interval.assignLocation(slot);
337 }
338 }
339
340 /**
341 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
342 */
343 public Interval[] intervals() {
344 return intervals;
345 }
346
347 void initIntervals() {
348 intervalsSize = operandSize();
349 intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
350 }
351
352 /**
353 * Creates a new interval.
354 *
355 * @param operand the operand for the interval
356 * @return the created interval
357 */
358 Interval createInterval(AllocatableValue operand) {
359 assert isLegal(operand);
360 int operandNumber = operandNumber(operand);
361 Interval interval = new Interval(operand, operandNumber, intervalEndMarker, rangeEndMarker);
362 assert operandNumber < intervalsSize;
363 assert intervals[operandNumber] == null;
364 intervals[operandNumber] = interval;
365 return interval;
366 }
367
368 /**
369 * Creates an interval as a result of splitting or spilling another interval.
370 *
371 * @param source an interval being split of spilled
372 * @return a new interval derived from {@code source}
373 */
374 Interval createDerivedInterval(Interval source) {
375 if (firstDerivedIntervalIndex == -1) {
376 firstDerivedIntervalIndex = intervalsSize;
377 }
378 if (intervalsSize == intervals.length) {
379 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT) + 1);
380 }
381 intervalsSize++;
382 assert intervalsSize <= intervals.length;
383 /*
384 * Note that these variables are not managed and must therefore never be inserted into the
385 * LIR
386 */
387 Variable variable = new Variable(source.kind(), numVariables++);
388
389 Interval interval = createInterval(variable);
390 assert intervals[intervalsSize - 1] == interval;
391 return interval;
392 }
393
394 // access to block list (sorted in linear scan order)
395 public int blockCount() {
396 return sortedBlocks.length;
397 }
398
399 public AbstractBlockBase<?> blockAt(int index) {
400 return sortedBlocks[index];
401 }
402
403 /**
404 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
405 * block. These sets do not include any operands allocated as a result of creating
406 * {@linkplain #createDerivedInterval(Interval) derived intervals}.
407 */
408 public int liveSetSize() {
409 return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
410 }
411
412 int numLoops() {
413 return ir.getControlFlowGraph().getLoops().size();
414 }
415
416 Interval intervalFor(int operandNumber) {
417 return intervals[operandNumber];
418 }
419
420 public Interval intervalFor(Value operand) {
421 int operandNumber = operandNumber(operand);
422 assert operandNumber < intervalsSize;
423 return intervals[operandNumber];
424 }
425
426 public Interval getOrCreateInterval(AllocatableValue operand) {
427 Interval ret = intervalFor(operand);
428 if (ret == null) {
429 return createInterval(operand);
430 } else {
431 return ret;
432 }
433 }
434
435 void initOpIdMaps(int numInstructions) {
436 opIdToInstructionMap = new LIRInstruction[numInstructions];
437 opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
438 }
439
440 void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) {
441 opIdToInstructionMap[index] = op;
442 opIdToBlockMap[index] = block;
443 }
444
445 /**
446 * Gets the highest instruction id allocated by this object.
447 */
448 int maxOpId() {
449 assert opIdToInstructionMap.length > 0 : "no operations";
450 return (opIdToInstructionMap.length - 1) << 1;
451 }
452
453 /**
454 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
455 * instructions in a method have an index one greater than their linear-scan order predecessor
456 * with the first instruction having an index of 0.
457 */
458 private static int opIdToIndex(int opId) {
459 return opId >> 1;
460 }
461
462 /**
463 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
464 *
465 * @param opId an instruction {@linkplain LIRInstruction#id id}
466 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
467 */
468 public LIRInstruction instructionForId(int opId) {
469 assert isEven(opId) : "opId not even";
470 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
471 assert instr.id() == opId;
472 return instr;
473 }
474
475 /**
476 * Gets the block containing a given instruction.
477 *
478 * @param opId an instruction {@linkplain LIRInstruction#id id}
479 * @return the block containing the instruction denoted by {@code opId}
480 */
481 public AbstractBlockBase<?> blockForId(int opId) {
482 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range";
483 return opIdToBlockMap[opIdToIndex(opId)];
484 }
485
486 boolean isBlockBegin(int opId) {
487 return opId == 0 || blockForId(opId) != blockForId(opId - 1);
488 }
489
490 boolean coversBlockBegin(int opId1, int opId2) {
491 return blockForId(opId1) != blockForId(opId2);
492 }
493
494 /**
495 * Determines if an {@link LIRInstruction} destroys all caller saved registers.
496 *
497 * @param opId an instruction {@linkplain LIRInstruction#id id}
498 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved
499 * registers.
500 */
501 boolean hasCall(int opId) {
502 assert isEven(opId) : "opId not even";
503 return instructionForId(opId).destroysCallerSavedRegisters();
504 }
505
506 abstract static class IntervalPredicate {
507
508 abstract boolean apply(Interval i);
509 }
510
511 public boolean isProcessed(Value operand) {
512 return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
513 }
514
515 // * Phase 5: actual register allocation
516
517 private static boolean isSorted(Interval[] intervals) {
518 int from = -1;
519 for (Interval interval : intervals) {
520 assert interval != null;
521 assert from <= interval.from();
522 from = interval.from();
523 }
524 return true;
525 }
526
527 static Interval addToList(Interval first, Interval prev, Interval interval) {
528 Interval newFirst = first;
529 if (prev != null) {
530 prev.next = interval;
531 } else {
532 newFirst = interval;
533 }
534 return newFirst;
535 }
536
537 Pair<Interval, Interval> createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
538 assert isSorted(sortedIntervals) : "interval list is not sorted";
539
540 Interval list1 = intervalEndMarker;
541 Interval list2 = intervalEndMarker;
542
543 Interval list1Prev = null;
544 Interval list2Prev = null;
545 Interval v;
546
547 int n = sortedIntervals.length;
548 for (int i = 0; i < n; i++) {
549 v = sortedIntervals[i];
550 if (v == null) {
551 continue;
552 }
553
554 if (isList1.apply(v)) {
555 list1 = addToList(list1, list1Prev, v);
556 list1Prev = v;
557 } else if (isList2 == null || isList2.apply(v)) {
558 list2 = addToList(list2, list2Prev, v);
559 list2Prev = v;
560 }
561 }
562
563 if (list1Prev != null) {
564 list1Prev.next = intervalEndMarker;
565 }
566 if (list2Prev != null) {
567 list2Prev.next = intervalEndMarker;
568 }
569
570 assert list1Prev == null || list1Prev.next.isEndMarker() : "linear list ends not with sentinel";
571 assert list2Prev == null || list2Prev.next.isEndMarker() : "linear list ends not with sentinel";
572
573 return Pair.create(list1, list2);
574 }
575
576 protected void sortIntervalsBeforeAllocation() {
577 int sortedLen = 0;
578 for (Interval interval : intervals) {
579 if (interval != null) {
580 sortedLen++;
581 }
582 }
583
584 Interval[] sortedList = new Interval[sortedLen];
585 int sortedIdx = 0;
586 int sortedFromMax = -1;
587
588 // special sorting algorithm: the original interval-list is almost sorted,
589 // only some intervals are swapped. So this is much faster than a complete QuickSort
590 for (Interval interval : intervals) {
591 if (interval != null) {
592 int from = interval.from();
593
594 if (sortedFromMax <= from) {
595 sortedList[sortedIdx++] = interval;
596 sortedFromMax = interval.from();
597 } else {
598 // the assumption that the intervals are already sorted failed,
599 // so this interval must be sorted in manually
600 int j;
601 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) {
602 sortedList[j + 1] = sortedList[j];
603 }
604 sortedList[j + 1] = interval;
605 sortedIdx++;
606 }
607 }
608 }
609 sortedIntervals = sortedList;
610 }
611
612 void sortIntervalsAfterAllocation() {
613 if (firstDerivedIntervalIndex == -1) {
614 // no intervals have been added during allocation, so sorted list is already up to date
615 return;
616 }
617
618 Interval[] oldList = sortedIntervals;
619 Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
620 int oldLen = oldList.length;
621 int newLen = newList.length;
622
623 // conventional sort-algorithm for new intervals
624 Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
625
626 // merge old and new list (both already sorted) into one combined list
627 Interval[] combinedList = new Interval[oldLen + newLen];
628 int oldIdx = 0;
629 int newIdx = 0;
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();
848 if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) {
849 throw GraalError.shouldNotReachHere(String.format("Intervals %d and %d overlap and have the same register assigned\n%s\n%s", i1.operandNumber, i2.operandNumber,
850 i1.logString(this), i2.logString(this)));
851 }
852 }
853 }
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;
895
896 /*
897 * Make sure none of the fixed registers is live across an oopmap since we
898 * can't handle that correctly.
899 */
900 if (checkLive) {
901 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); !interval.isEndMarker(); interval = interval.next) {
902 if (interval.currentTo() > op.id() + 1) {
903 /*
904 * This interval is live out of this op so make sure that this
905 * interval represents some value that's referenced by this op
906 * either as an input or output.
907 */
908 checkConsumer.curInterval = interval;
909 checkConsumer.ok = false;
910
911 op.visitEachInput(checkConsumer);
912 op.visitEachAlive(checkConsumer);
913 op.visitEachTemp(checkConsumer);
914 op.visitEachOutput(checkConsumer);
915
916 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point";
917 }
918 }
919 }
920 }
921 }
922 }
923 }
924 }
925
926 public LIR getLIR() {
927 return ir;
928 }
929
930 public FrameMapBuilder getFrameMapBuilder() {
931 return frameMapBuilder;
932 }
933
934 public AbstractBlockBase<?>[] sortedBlocks() {
935 return sortedBlocks;
936 }
937
938 public RegisterArray getRegisters() {
939 return registers;
940 }
941
942 public RegisterAllocationConfig getRegisterAllocationConfig() {
943 return regAllocConfig;
944 }
945
946 public boolean callKillsRegisters() {
947 return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
948 }
949
950 boolean neverSpillConstants() {
951 return neverSpillConstants;
952 }
953
954 }