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 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;
103
104 /**
105 * Bit map specifying which operands are used (before being defined) in this block. That is,
106 * these are the values that are live upon entry to the block. The bit index of an operand
107 * is its {@linkplain LinearScan#operandNumber(Value) operand number}.
108 */
109 public BitSet liveGen;
110
111 /**
112 * Bit map specifying which operands are defined/overwritten in this block. The bit index of
113 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}.
114 */
115 public BitSet liveKill;
116 }
117
118 public static final int DOMINATOR_SPILL_MOVE_ID = -2;
119 private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1;
120
121 private final LIR ir;
122 private final FrameMapBuilder frameMapBuilder;
123 private final RegisterAttributes[] registerAttributes;
124 private final RegisterArray registers;
125 private final RegisterAllocationConfig regAllocConfig;
126 private final MoveFactory moveFactory;
127
128 private final BlockMap<BlockData> blockData;
129
130 /**
131 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change.
132 */
133 private final AbstractBlockBase<?>[] sortedBlocks;
134
135 /**
136 * @see #intervals()
137 */
138 private Interval[] intervals;
139
140 /**
141 * The number of valid entries in {@link #intervals}.
142 */
143 private int intervalsSize;
144
145 /**
146 * The index of the first entry in {@link #intervals} for a
147 * {@linkplain #createDerivedInterval(Interval) derived interval}.
148 */
149 private int firstDerivedIntervalIndex = -1;
150
151 /**
152 * Intervals sorted by {@link Interval#from()}.
153 */
154 private Interval[] sortedIntervals;
155
156 /**
157 * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
158 * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this
159 * array.
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 /**
224 * Converts an operand (variable or register) to an index in a flat address space covering all
225 * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
226 * by this allocator.
227 */
228 int operandNumber(Value operand) {
229 if (isRegister(operand)) {
230 int number = asRegister(operand).number;
231 assert number < firstVariableNumber;
232 return number;
233 }
234 assert isVariable(operand) : operand;
235 return firstVariableNumber + ((Variable) operand).index;
236 }
237
238 /**
239 * Gets the number of operands. This value will increase by 1 for new variable.
240 */
241 int operandSize() {
242 return firstVariableNumber + numVariables;
243 }
244
245 /**
246 * Gets the highest operand number for a register operand. This value will never change.
247 */
248 int maxRegisterNumber() {
249 return firstVariableNumber - 1;
250 }
251
252 public BlockData getBlockData(AbstractBlockBase<?> block) {
253 return blockData.get(block);
254 }
255
256 void initBlockData(AbstractBlockBase<?> block) {
257 blockData.put(block, new BlockData());
258 }
259
260 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
261
262 @Override
263 public boolean apply(Interval i) {
264 return isRegister(i.operand);
265 }
266 };
267
268 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
269
270 @Override
271 public boolean apply(Interval i) {
272 return isVariable(i.operand);
273 }
274 };
275
276 static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() {
277
278 @Override
279 public boolean apply(Interval i) {
280 return !isRegister(i.operand);
281 }
282 };
283
284 /**
285 * Gets an object describing the attributes of a given register according to this register
286 * configuration.
287 */
288 public RegisterAttributes attributes(Register reg) {
289 return registerAttributes[reg.number];
290 }
291
292 void assignSpillSlot(Interval interval) {
293 /*
294 * Assign the canonical spill slot of the parent (if a part of the interval is already
295 * spilled) or allocate a new spill slot.
296 */
297 if (interval.canMaterialize()) {
298 interval.assignLocation(Value.ILLEGAL);
299 } else if (interval.spillSlot() != null) {
300 interval.assignLocation(interval.spillSlot());
301 } else {
302 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind());
303 interval.setSpillSlot(slot);
304 interval.assignLocation(slot);
305 }
306 }
307
308 /**
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++;
350 assert intervalsSize <= intervals.length;
351 /*
352 * Note that these variables are not managed and must therefore never be inserted into the
353 * LIR
354 */
355 Variable variable = new Variable(source.kind(), numVariables++);
356
357 Interval interval = createInterval(variable);
358 assert intervals[intervalsSize - 1] == interval;
359 return interval;
360 }
361
362 // access to block list (sorted in linear scan order)
363 public int blockCount() {
364 return sortedBlocks.length;
365 }
366
367 public AbstractBlockBase<?> blockAt(int index) {
368 return sortedBlocks[index];
369 }
370
371 /**
372 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
373 * block. These sets do not include any operands allocated as a result of creating
374 * {@linkplain #createDerivedInterval(Interval) derived intervals}.
375 */
376 public int liveSetSize() {
377 return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
378 }
379
380 int numLoops() {
381 return ir.getControlFlowGraph().getLoops().size();
382 }
383
384 Interval intervalFor(int operandNumber) {
385 return intervals[operandNumber];
386 }
387
388 public Interval intervalFor(Value operand) {
389 int operandNumber = operandNumber(operand);
390 assert operandNumber < intervalsSize;
391 return intervals[operandNumber];
392 }
393
394 public Interval getOrCreateInterval(AllocatableValue operand) {
395 Interval ret = intervalFor(operand);
396 if (ret == null) {
397 return createInterval(operand);
398 } else {
399 return ret;
400 }
401 }
402
403 void initOpIdMaps(int numInstructions) {
404 opIdToInstructionMap = new LIRInstruction[numInstructions];
405 opIdToBlockMap = new AbstractBlockBase<?>[numInstructions];
406 }
407
408 void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) {
409 opIdToInstructionMap[index] = op;
410 opIdToBlockMap[index] = block;
411 }
412
413 /**
414 * Gets the highest instruction id allocated by this object.
415 */
416 int maxOpId() {
417 assert opIdToInstructionMap.length > 0 : "no operations";
418 return (opIdToInstructionMap.length - 1) << 1;
419 }
420
421 /**
422 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR
423 * instructions in a method have an index one greater than their linear-scan order predecessor
424 * with the first instruction having an index of 0.
425 */
426 private static int opIdToIndex(int opId) {
427 return opId >> 1;
428 }
429
430 /**
431 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}.
432 *
433 * @param opId an instruction {@linkplain LIRInstruction#id id}
434 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id}
435 */
436 public LIRInstruction instructionForId(int opId) {
437 assert isEven(opId) : "opId not even";
438 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
439 assert instr.id() == opId;
440 return instr;
441 }
442
443 /**
444 * Gets the block containing a given instruction.
445 *
446 * @param opId an instruction {@linkplain LIRInstruction#id id}
447 * @return the block containing the instruction denoted by {@code opId}
448 */
449 public AbstractBlockBase<?> blockForId(int opId) {
450 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range";
451 return opIdToBlockMap[opIdToIndex(opId)];
452 }
453
454 boolean isBlockBegin(int opId) {
455 return opId == 0 || blockForId(opId) != blockForId(opId - 1);
456 }
457
458 boolean coversBlockBegin(int opId1, int opId2) {
459 return blockForId(opId1) != blockForId(opId2);
460 }
461
462 /**
463 * Determines if an {@link LIRInstruction} destroys all caller saved registers.
464 *
465 * @param opId an instruction {@linkplain LIRInstruction#id id}
466 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved
467 * registers.
468 */
469 boolean hasCall(int opId) {
470 assert isEven(opId) : "opId not even";
471 return instructionForId(opId).destroysCallerSavedRegisters();
472 }
473
474 abstract static class IntervalPredicate {
475
476 abstract boolean apply(Interval i);
477 }
478
479 public boolean isProcessed(Value operand) {
480 return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable();
481 }
482
483 // * Phase 5: actual register allocation
484
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
562 if (sortedFromMax <= from) {
563 sortedList[sortedIdx++] = interval;
564 sortedFromMax = interval.from();
565 } else {
566 // the assumption that the intervals are already sorted failed,
567 // so this interval must be sorted in manually
568 int j;
569 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) {
570 sortedList[j + 1] = sortedList[j];
571 }
572 sortedList[j + 1] = interval;
573 sortedIdx++;
574 }
575 }
576 }
577 sortedIntervals = sortedList;
578 }
579
580 void sortIntervalsAfterAllocation() {
581 if (firstDerivedIntervalIndex == -1) {
582 // no intervals have been added during allocation, so sorted list is already up to date
583 return;
584 }
585
586 Interval[] oldList = sortedIntervals;
587 Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
588 int oldLen = oldList.length;
589 int newLen = newList.length;
590
591 // conventional sort-algorithm for new intervals
592 Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
593
594 // merge old and new list (both already sorted) into one combined list
595 Interval[] combinedList = new Interval[oldLen + newLen];
596 int oldIdx = 0;
597 int newIdx = 0;
598
599 while (oldIdx + newIdx < combinedList.length) {
600 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) {
601 combinedList[oldIdx + newIdx] = oldList[oldIdx];
602 oldIdx++;
603 } else {
604 combinedList[oldIdx + newIdx] = newList[newIdx];
605 newIdx++;
606 }
607 }
608
609 sortedIntervals = combinedList;
610 }
611
612 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
613 // instead of returning null
614 public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
615 Interval result = interval.getSplitChildAtOpId(opId, mode, this);
616
617 if (result != null) {
618 if (Debug.isLogEnabled()) {
619 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
620 }
621 return result;
622 }
623 throw new GraalError("LinearScan: interval is null");
624 }
625
626 static AllocatableValue canonicalSpillOpr(Interval interval) {
627 assert interval.spillSlot() != null : "canonical spill slot not set";
628 return interval.spillSlot();
629 }
630
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() {
701 return new LinearScanOptimizeSpillPositionPhase(this);
702 }
703
704 protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() {
705 return new LinearScanResolveDataFlowPhase(this);
706 }
707
708 protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() {
709 return new LinearScanEliminateSpillMovePhase(this);
710 }
711
712 protected LinearScanAssignLocationsPhase createAssignLocationsPhase() {
713 return new LinearScanAssignLocationsPhase(this);
714 }
715
716 @SuppressWarnings("try")
717 public void printIntervals(String label) {
718 if (Debug.isLogEnabled()) {
719 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
720 for (Interval interval : intervals) {
721 if (interval != null) {
722 Debug.log("%s", interval.logString(this));
723 }
724 }
725
726 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
727 for (int i = 0; i < blockCount(); i++) {
728 AbstractBlockBase<?> block = blockAt(i);
729 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
730 }
731 }
732 }
733 }
734 Debug.dump(Debug.BASIC_LOG_LEVEL, new LinearScanIntervalDumper(Arrays.copyOf(intervals, intervalsSize)), label);
735 }
736
737 public void printLir(String label, @SuppressWarnings("unused") boolean hirValid) {
738 Debug.dump(Debug.INFO_LOG_LEVEL, ir, label);
739 }
740
741 boolean verify() {
742 // (check that all intervals have a correct register and that no registers are overwritten)
743 verifyIntervals();
744
745 verifyRegisters();
746
747 Debug.log("no errors found");
748
749 return true;
750 }
751
752 @SuppressWarnings("try")
753 private void verifyRegisters() {
754 // Enable this logging to get output for the verification process.
755 try (Indent indent = Debug.logAndIndent("verifying register allocation")) {
756 RegisterVerifier verifier = new RegisterVerifier(this);
757 verifier.verify(blockAt(0));
758 }
759 }
760
761 @SuppressWarnings("try")
762 protected void verifyIntervals() {
763 try (Indent indent = Debug.logAndIndent("verifying intervals")) {
764 int len = intervalsSize;
765
766 for (int i = 0; i < len; i++) {
767 Interval i1 = intervals[i];
768 if (i1 == null) {
769 continue;
770 }
771
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;
819 }
820 Value l1 = i1.location();
821 Value l2 = i2.location();
822 if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) {
823 throw GraalError.shouldNotReachHere(String.format("Intervals %d and %d overlap and have the same register assigned\n%s\n%s", i1.operandNumber, i2.operandNumber,
824 i1.logString(this), i2.logString(this)));
825 }
826 }
827 }
828 }
829 }
830
831 class CheckConsumer implements ValueConsumer {
832
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 }
896 }
897 }
898 }
899
900 public LIR getLIR() {
901 return ir;
902 }
903
904 public FrameMapBuilder getFrameMapBuilder() {
905 return frameMapBuilder;
906 }
907
908 public AbstractBlockBase<?>[] sortedBlocks() {
909 return sortedBlocks;
910 }
911
912 public RegisterArray getRegisters() {
913 return registers;
914 }
915
916 public RegisterAllocationConfig getRegisterAllocationConfig() {
917 return regAllocConfig;
918 }
919
920 public boolean callKillsRegisters() {
921 return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved();
922 }
923
924 boolean neverSpillConstants() {
925 return neverSpillConstants;
926 }
927
928 }