22 */
23 package org.graalvm.compiler.lir.alloc.trace.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
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Comparator;
36
37 import org.graalvm.compiler.core.common.LIRKind;
38 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
39 import org.graalvm.compiler.core.common.alloc.Trace;
40 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
41 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
42 import org.graalvm.compiler.debug.Debug;
43 import org.graalvm.compiler.debug.Debug.Scope;
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.OperandMode;
49 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
50 import org.graalvm.compiler.lir.Variable;
51 import org.graalvm.compiler.lir.VirtualStackSlot;
52 import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
53 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase;
54 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
55 import org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase;
56 import org.graalvm.compiler.lir.alloc.trace.TraceUtil;
57 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterPriority;
58 import org.graalvm.compiler.lir.debug.IntervalDumper;
59 import org.graalvm.compiler.lir.debug.IntervalDumper.IntervalVisitor;
60 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
61 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
62 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
63 import org.graalvm.compiler.lir.phases.LIRPhase;
119
120 private final LIRGenerationResult res;
121 private final GlobalLivenessInfo livenessInfo;
122
123 public TraceLinearScanPhase(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, TraceBuilderResult traceBuilderResult,
124 boolean neverSpillConstants, AllocatableValue[] cachedStackSlots, GlobalLivenessInfo livenessInfo) {
125 this.res = res;
126 this.moveFactory = spillMoveFactory;
127 this.frameMapBuilder = res.getFrameMapBuilder();
128 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
129 this.regAllocConfig = regAllocConfig;
130
131 this.registers = target.arch.getRegisters();
132 this.traceBuilderResult = traceBuilderResult;
133 this.neverSpillConstants = neverSpillConstants;
134 this.cachedStackSlots = cachedStackSlots;
135 this.livenessInfo = livenessInfo;
136 assert livenessInfo != null;
137 }
138
139 public static boolean isVariableOrRegister(Value value) {
140 return isVariable(value) || isRegister(value);
141 }
142
143 abstract static class IntervalPredicate {
144
145 abstract boolean apply(TraceInterval i);
146 }
147
148 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
149
150 @Override
151 public boolean apply(TraceInterval i) {
152 // all TraceIntervals are variable intervals
153 return true;
154 }
155 };
156 private static final Comparator<TraceInterval> SORT_BY_FROM_COMP = new Comparator<TraceInterval>() {
157
158 @Override
239 public TraceLinearScan(Trace trace) {
240 this.trace = trace;
241 this.fixedIntervals = new FixedInterval[registers.size()];
242 }
243
244 GlobalLivenessInfo getGlobalLivenessInfo() {
245 return livenessInfo;
246 }
247
248 /**
249 * @return {@link Variable#index}
250 */
251 int operandNumber(Variable operand) {
252 return operand.index;
253 }
254
255 OptionValues getOptions() {
256 return getLIR().getOptions();
257 }
258
259 /**
260 * Gets the number of operands. This value will increase by 1 for new variable.
261 */
262 int operandSize() {
263 return getLIR().numVariables();
264 }
265
266 /**
267 * Gets the number of registers. This value will never change.
268 */
269 int numRegisters() {
270 return registers.size();
271 }
272
273 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
274 int result = getLIR().getLIRforBlock(block).get(0).id();
275 assert result >= 0;
276 return result;
277 }
278
309 /*
310 * Assign the canonical spill slot of the parent (if a part of the interval is already
311 * spilled) or allocate a new spill slot.
312 */
313 if (interval.canMaterialize()) {
314 interval.assignLocation(Value.ILLEGAL);
315 } else if (interval.spillSlot() != null) {
316 interval.assignLocation(interval.spillSlot());
317 } else {
318 AllocatableValue slot = allocateSpillSlot(interval);
319 interval.setSpillSlot(slot);
320 interval.assignLocation(slot);
321 }
322 }
323
324 /**
325 * Returns a new spill slot or a cached entry if there is already one for the
326 * {@linkplain TraceInterval variable}.
327 */
328 private AllocatableValue allocateSpillSlot(TraceInterval interval) {
329 int variableIndex = interval.splitParent().operandNumber;
330 OptionValues options = getOptions();
331 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) {
332 AllocatableValue cachedStackSlot = cachedStackSlots[variableIndex];
333 if (cachedStackSlot != null) {
334 TraceRegisterAllocationPhase.globalStackSlots.increment();
335 assert cachedStackSlot.getValueKind().equals(getKind(interval)) : "CachedStackSlot: kind mismatch? " + getKind(interval) + " vs. " + cachedStackSlot.getValueKind();
336 return cachedStackSlot;
337 }
338 }
339 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(getKind(interval));
340 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) {
341 cachedStackSlots[variableIndex] = slot;
342 }
343 TraceRegisterAllocationPhase.allocatedStackSlots.increment();
344 return slot;
345 }
346
347 // access to block list (sorted in linear scan order)
348 public int blockCount() {
349 return sortedBlocks().length;
350 }
351
352 public AbstractBlockBase<?> blockAt(int index) {
353 return sortedBlocks()[index];
354 }
355
356 int numLoops() {
357 return getLIR().getControlFlowGraph().getLoops().size();
358 }
359
360 boolean isBlockBegin(int opId) {
361 return opId == 0 || blockForId(opId) != blockForId(opId - 1);
362 }
363
514 combinedList[oldIdx + newIdx] = newList[newIdx];
515 newIdx++;
516 }
517 }
518
519 sortedIntervals = combinedList;
520 }
521
522 void sortIntervalsBySpillPos() {
523 // TODO (JE): better algorithm?
524 // conventional sort-algorithm for new intervals
525 Arrays.sort(sortedIntervals, SORT_BY_SPILL_POS_COMP);
526 }
527
528 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
529 // instead of returning null
530 public TraceInterval splitChildAtOpId(TraceInterval interval, int opId, LIRInstruction.OperandMode mode) {
531 TraceInterval result = interval.getSplitChildAtOpId(opId, mode);
532
533 if (result != null) {
534 if (Debug.isLogEnabled()) {
535 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result);
536 }
537 return result;
538 }
539 throw new GraalError("LinearScan: interval is null");
540 }
541
542 AllocatableValue canonicalSpillOpr(TraceInterval interval) {
543 assert interval.spillSlot() != null : "canonical spill slot not set";
544 return interval.spillSlot();
545 }
546
547 boolean isMaterialized(Variable operand, int opId, OperandMode mode) {
548 TraceInterval interval = intervalFor(operand);
549 assert interval != null : "interval must exist";
550
551 if (opId != -1) {
552 /*
553 * Operands are not changed when an interval is split during allocation, so search
554 * the right interval here.
555 */
556 interval = splitChildAtOpId(interval, opId, mode);
557 }
558
559 return isIllegal(interval.location()) && interval.canMaterialize();
560 }
561
562 boolean isCallerSave(Value operand) {
563 return attributes(asRegister(operand)).isCallerSave();
564 }
565
566 @SuppressWarnings("try")
567 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, TraceAllocationContext traceContext) {
568 MoveFactory spillMoveFactory = traceContext.spillMoveFactory;
569 RegisterAllocationConfig registerAllocationConfig = traceContext.registerAllocationConfig;
570 /*
571 * This is the point to enable debug logging for the whole register allocation.
572 */
573 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) {
574 TRACE_LINEAR_SCAN_LIFETIME_ANALYSIS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
575
576 try (Scope s = Debug.scope("AfterLifetimeAnalysis", this)) {
577
578 printLir("After instruction numbering");
579 printIntervals("Before register allocation");
580
581 sortIntervalsBeforeAllocation();
582
583 TRACE_LINEAR_SCAN_REGISTER_ALLOCATION_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
584 printIntervals("After register allocation");
585
586 // resolve intra-trace data-flow
587 TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this);
588
589 // eliminate spill moves
590 OptionValues options = getOptions();
591 if (Options.LIROptTraceRAEliminateSpillMoves.getValue(options)) {
592 TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this);
593 }
594
595 TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
596
597 if (DetailedAsserts.getValue(options)) {
598 verifyIntervals();
599 }
600 } catch (Throwable e) {
601 throw Debug.handle(e);
602 }
603 }
604 }
605
606 public void printLir(String label) {
607 if (Debug.isDumpEnabled(Debug.DETAILED_LEVEL)) {
608 Debug.dump(Debug.DETAILED_LEVEL, sortedBlocks(), "%s (Trace%d)", label, trace.getId());
609 }
610 }
611
612 boolean verify() {
613 // (check that all intervals have a correct register and that no registers are
614 // overwritten)
615 verifyIntervals();
616
617 verifyRegisters();
618
619 Debug.log("no errors found");
620
621 return true;
622 }
623
624 @SuppressWarnings("try")
625 private void verifyRegisters() {
626 // Enable this logging to get output for the verification process.
627 try (Indent indent = Debug.logAndIndent("verifying register allocation")) {
628 RegisterVerifier verifier = new RegisterVerifier(this);
629 verifier.verify(blockAt(0));
630 }
631 }
632
633 @SuppressWarnings("try")
634 protected void verifyIntervals() {
635 try (Indent indent = Debug.logAndIndent("verifying intervals")) {
636 int len = intervalsSize();
637
638 for (int i = 0; i < len; i++) {
639 final TraceInterval i1 = intervals()[i];
640 if (i1 == null) {
641 continue;
642 }
643
644 i1.checkSplitChildren();
645
646 if (i1.operandNumber != i) {
647 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
648 Debug.log(i1.logString());
649 throw new GraalError("");
650 }
651
652 if (getKind(i1).equals(LIRKind.Illegal)) {
653 Debug.log("Interval %d has no type assigned", i1.operandNumber);
654 Debug.log(i1.logString());
655 throw new GraalError("");
656 }
657
658 if (i1.location() == null) {
659 Debug.log("Interval %d has no register assigned", i1.operandNumber);
660 Debug.log(i1.logString());
661 throw new GraalError("");
662 }
663
664 if (i1.isEmpty()) {
665 Debug.log("Interval %d has no Range", i1.operandNumber);
666 Debug.log(i1.logString());
667 throw new GraalError("");
668 }
669
670 if (i1.from() >= i1.to()) {
671 Debug.log("Interval %d has zero length range", i1.operandNumber);
672 Debug.log(i1.logString());
673 throw new GraalError("");
674 }
675
676 // special intervals that are created in MoveResolver
677 // . ignore them because the range information has no meaning there
678 if (i1.from() == 1 && i1.to() == 2) {
679 continue;
680 }
681 // check any intervals
682 for (int j = i + 1; j < len; j++) {
683 final TraceInterval i2 = intervals()[j];
684 if (i2 == null) {
685 continue;
686 }
687
688 // special intervals that are created in MoveResolver
689 // . ignore them because the range information has no meaning there
690 if (i2.from() == 1 && i2.to() == 2) {
691 continue;
692 }
941 LIRInstruction instructionForId(int opId) {
942 assert isEven(opId) : "opId not even";
943 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
944 assert instr.id() == opId;
945 return instr;
946 }
947
948 /**
949 * Gets the block containing a given instruction.
950 *
951 * @param opId an instruction {@linkplain LIRInstruction#id id}
952 * @return the block containing the instruction denoted by {@code opId}
953 */
954 AbstractBlockBase<?> blockForId(int opId) {
955 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range: " + opId;
956 return opIdToBlockMap[opIdToIndex(opId)];
957 }
958
959 @SuppressWarnings("try")
960 public void printIntervals(String label) {
961 if (Debug.isDumpEnabled(Debug.DETAILED_LEVEL)) {
962 if (Debug.isLogEnabled()) {
963 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
964 for (FixedInterval interval : fixedIntervals) {
965 if (interval != null) {
966 Debug.log("%s", interval.logString());
967 }
968 }
969
970 for (TraceInterval interval : intervals) {
971 if (interval != null) {
972 Debug.log("%s", interval.logString());
973 }
974 }
975
976 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) {
977 for (AbstractBlockBase<?> block : trace.getBlocks()) {
978 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
979 }
980 }
981 }
982 }
983 Debug.dump(Debug.DETAILED_LEVEL, this, "%s (Trace%d)", label, trace.getId());
984 }
985 }
986
987 @Override
988 public void visitIntervals(IntervalVisitor visitor) {
989 for (FixedInterval interval : fixedIntervals) {
990 if (interval != null) {
991 printFixedInterval(interval, visitor);
992 }
993 }
994 for (TraceInterval interval : intervals) {
995 if (interval != null) {
996 printInterval(interval, visitor);
997 }
998 }
999 }
1000
1001 boolean hasInterTracePredecessor(AbstractBlockBase<?> block) {
1002 return TraceUtil.hasInterTracePredecessor(traceBuilderResult, trace, block);
1003 }
|
22 */
23 package org.graalvm.compiler.lir.alloc.trace.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
33 import java.util.ArrayList;
34 import java.util.Arrays;
35 import java.util.Comparator;
36
37 import org.graalvm.compiler.core.common.LIRKind;
38 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig;
39 import org.graalvm.compiler.core.common.alloc.Trace;
40 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
41 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
42 import org.graalvm.compiler.debug.DebugContext;
43 import org.graalvm.compiler.debug.GraalError;
44 import org.graalvm.compiler.debug.Indent;
45 import org.graalvm.compiler.lir.LIR;
46 import org.graalvm.compiler.lir.LIRInstruction;
47 import org.graalvm.compiler.lir.LIRInstruction.OperandMode;
48 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
49 import org.graalvm.compiler.lir.Variable;
50 import org.graalvm.compiler.lir.VirtualStackSlot;
51 import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo;
52 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase;
53 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
54 import org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase;
55 import org.graalvm.compiler.lir.alloc.trace.TraceUtil;
56 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterPriority;
57 import org.graalvm.compiler.lir.debug.IntervalDumper;
58 import org.graalvm.compiler.lir.debug.IntervalDumper.IntervalVisitor;
59 import org.graalvm.compiler.lir.framemap.FrameMapBuilder;
60 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
61 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
62 import org.graalvm.compiler.lir.phases.LIRPhase;
118
119 private final LIRGenerationResult res;
120 private final GlobalLivenessInfo livenessInfo;
121
122 public TraceLinearScanPhase(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, TraceBuilderResult traceBuilderResult,
123 boolean neverSpillConstants, AllocatableValue[] cachedStackSlots, GlobalLivenessInfo livenessInfo) {
124 this.res = res;
125 this.moveFactory = spillMoveFactory;
126 this.frameMapBuilder = res.getFrameMapBuilder();
127 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap();
128 this.regAllocConfig = regAllocConfig;
129
130 this.registers = target.arch.getRegisters();
131 this.traceBuilderResult = traceBuilderResult;
132 this.neverSpillConstants = neverSpillConstants;
133 this.cachedStackSlots = cachedStackSlots;
134 this.livenessInfo = livenessInfo;
135 assert livenessInfo != null;
136 }
137
138 protected DebugContext getDebug() {
139 return res.getLIR().getDebug();
140 }
141
142 public static boolean isVariableOrRegister(Value value) {
143 return isVariable(value) || isRegister(value);
144 }
145
146 abstract static class IntervalPredicate {
147
148 abstract boolean apply(TraceInterval i);
149 }
150
151 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
152
153 @Override
154 public boolean apply(TraceInterval i) {
155 // all TraceIntervals are variable intervals
156 return true;
157 }
158 };
159 private static final Comparator<TraceInterval> SORT_BY_FROM_COMP = new Comparator<TraceInterval>() {
160
161 @Override
242 public TraceLinearScan(Trace trace) {
243 this.trace = trace;
244 this.fixedIntervals = new FixedInterval[registers.size()];
245 }
246
247 GlobalLivenessInfo getGlobalLivenessInfo() {
248 return livenessInfo;
249 }
250
251 /**
252 * @return {@link Variable#index}
253 */
254 int operandNumber(Variable operand) {
255 return operand.index;
256 }
257
258 OptionValues getOptions() {
259 return getLIR().getOptions();
260 }
261
262 DebugContext getDebug() {
263 return getLIR().getDebug();
264 }
265
266 /**
267 * Gets the number of operands. This value will increase by 1 for new variable.
268 */
269 int operandSize() {
270 return getLIR().numVariables();
271 }
272
273 /**
274 * Gets the number of registers. This value will never change.
275 */
276 int numRegisters() {
277 return registers.size();
278 }
279
280 public int getFirstLirInstructionId(AbstractBlockBase<?> block) {
281 int result = getLIR().getLIRforBlock(block).get(0).id();
282 assert result >= 0;
283 return result;
284 }
285
316 /*
317 * Assign the canonical spill slot of the parent (if a part of the interval is already
318 * spilled) or allocate a new spill slot.
319 */
320 if (interval.canMaterialize()) {
321 interval.assignLocation(Value.ILLEGAL);
322 } else if (interval.spillSlot() != null) {
323 interval.assignLocation(interval.spillSlot());
324 } else {
325 AllocatableValue slot = allocateSpillSlot(interval);
326 interval.setSpillSlot(slot);
327 interval.assignLocation(slot);
328 }
329 }
330
331 /**
332 * Returns a new spill slot or a cached entry if there is already one for the
333 * {@linkplain TraceInterval variable}.
334 */
335 private AllocatableValue allocateSpillSlot(TraceInterval interval) {
336 DebugContext debug = res.getLIR().getDebug();
337 int variableIndex = interval.splitParent().operandNumber;
338 OptionValues options = getOptions();
339 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) {
340 AllocatableValue cachedStackSlot = cachedStackSlots[variableIndex];
341 if (cachedStackSlot != null) {
342 TraceRegisterAllocationPhase.globalStackSlots.increment(debug);
343 assert cachedStackSlot.getValueKind().equals(getKind(interval)) : "CachedStackSlot: kind mismatch? " + getKind(interval) + " vs. " + cachedStackSlot.getValueKind();
344 return cachedStackSlot;
345 }
346 }
347 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(getKind(interval));
348 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) {
349 cachedStackSlots[variableIndex] = slot;
350 }
351 TraceRegisterAllocationPhase.allocatedStackSlots.increment(debug);
352 return slot;
353 }
354
355 // access to block list (sorted in linear scan order)
356 public int blockCount() {
357 return sortedBlocks().length;
358 }
359
360 public AbstractBlockBase<?> blockAt(int index) {
361 return sortedBlocks()[index];
362 }
363
364 int numLoops() {
365 return getLIR().getControlFlowGraph().getLoops().size();
366 }
367
368 boolean isBlockBegin(int opId) {
369 return opId == 0 || blockForId(opId) != blockForId(opId - 1);
370 }
371
522 combinedList[oldIdx + newIdx] = newList[newIdx];
523 newIdx++;
524 }
525 }
526
527 sortedIntervals = combinedList;
528 }
529
530 void sortIntervalsBySpillPos() {
531 // TODO (JE): better algorithm?
532 // conventional sort-algorithm for new intervals
533 Arrays.sort(sortedIntervals, SORT_BY_SPILL_POS_COMP);
534 }
535
536 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
537 // instead of returning null
538 public TraceInterval splitChildAtOpId(TraceInterval interval, int opId, LIRInstruction.OperandMode mode) {
539 TraceInterval result = interval.getSplitChildAtOpId(opId, mode);
540
541 if (result != null) {
542 if (getDebug().isLogEnabled()) {
543 getDebug().log("Split child at pos %d of interval %s is %s", opId, interval, result);
544 }
545 return result;
546 }
547 throw new GraalError("LinearScan: interval is null");
548 }
549
550 AllocatableValue canonicalSpillOpr(TraceInterval interval) {
551 assert interval.spillSlot() != null : "canonical spill slot not set";
552 return interval.spillSlot();
553 }
554
555 boolean isMaterialized(Variable operand, int opId, OperandMode mode) {
556 TraceInterval interval = intervalFor(operand);
557 assert interval != null : "interval must exist";
558
559 if (opId != -1) {
560 /*
561 * Operands are not changed when an interval is split during allocation, so search
562 * the right interval here.
563 */
564 interval = splitChildAtOpId(interval, opId, mode);
565 }
566
567 return isIllegal(interval.location()) && interval.canMaterialize();
568 }
569
570 boolean isCallerSave(Value operand) {
571 return attributes(asRegister(operand)).isCallerSave();
572 }
573
574 @SuppressWarnings("try")
575 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, TraceAllocationContext traceContext) {
576 MoveFactory spillMoveFactory = traceContext.spillMoveFactory;
577 RegisterAllocationConfig registerAllocationConfig = traceContext.registerAllocationConfig;
578 /*
579 * This is the point to enable debug logging for the whole register allocation.
580 */
581 DebugContext debug = res.getLIR().getDebug();
582 try (Indent indent = debug.logAndIndent("LinearScan allocate")) {
583 TRACE_LINEAR_SCAN_LIFETIME_ANALYSIS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
584
585 try (DebugContext.Scope s = debug.scope("AfterLifetimeAnalysis", this)) {
586
587 printLir("After instruction numbering");
588 printIntervals("Before register allocation");
589
590 sortIntervalsBeforeAllocation();
591
592 TRACE_LINEAR_SCAN_REGISTER_ALLOCATION_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
593 printIntervals("After register allocation");
594
595 // resolve intra-trace data-flow
596 TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this);
597
598 // eliminate spill moves
599 OptionValues options = getOptions();
600 if (Options.LIROptTraceRAEliminateSpillMoves.getValue(options)) {
601 TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this);
602 }
603
604 TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false);
605
606 if (DetailedAsserts.getValue(options)) {
607 verifyIntervals();
608 }
609 } catch (Throwable e) {
610 throw debug.handle(e);
611 }
612 }
613 }
614
615 public void printLir(String label) {
616 if (getDebug().isDumpEnabled(DebugContext.DETAILED_LEVEL)) {
617 getDebug().dump(DebugContext.DETAILED_LEVEL, sortedBlocks(), "%s (Trace%d)", label, trace.getId());
618 }
619 }
620
621 boolean verify() {
622 // (check that all intervals have a correct register and that no registers are
623 // overwritten)
624 verifyIntervals();
625
626 verifyRegisters();
627
628 getDebug().log("no errors found");
629
630 return true;
631 }
632
633 @SuppressWarnings("try")
634 private void verifyRegisters() {
635 // Enable this logging to get output for the verification process.
636 try (Indent indent = getDebug().logAndIndent("verifying register allocation")) {
637 RegisterVerifier verifier = new RegisterVerifier(this);
638 verifier.verify(blockAt(0));
639 }
640 }
641
642 @SuppressWarnings("try")
643 protected void verifyIntervals() {
644 DebugContext debug = getDebug();
645 try (Indent indent = debug.logAndIndent("verifying intervals")) {
646 int len = intervalsSize();
647
648 for (int i = 0; i < len; i++) {
649 final TraceInterval i1 = intervals()[i];
650 if (i1 == null) {
651 continue;
652 }
653
654 i1.checkSplitChildren();
655
656 if (i1.operandNumber != i) {
657 debug.log("Interval %d is on position %d in list", i1.operandNumber, i);
658 debug.log(i1.logString());
659 throw new GraalError("");
660 }
661
662 if (getKind(i1).equals(LIRKind.Illegal)) {
663 debug.log("Interval %d has no type assigned", i1.operandNumber);
664 debug.log(i1.logString());
665 throw new GraalError("");
666 }
667
668 if (i1.location() == null) {
669 debug.log("Interval %d has no register assigned", i1.operandNumber);
670 debug.log(i1.logString());
671 throw new GraalError("");
672 }
673
674 if (i1.isEmpty()) {
675 debug.log("Interval %d has no Range", i1.operandNumber);
676 debug.log(i1.logString());
677 throw new GraalError("");
678 }
679
680 if (i1.from() >= i1.to()) {
681 debug.log("Interval %d has zero length range", i1.operandNumber);
682 debug.log(i1.logString());
683 throw new GraalError("");
684 }
685
686 // special intervals that are created in MoveResolver
687 // . ignore them because the range information has no meaning there
688 if (i1.from() == 1 && i1.to() == 2) {
689 continue;
690 }
691 // check any intervals
692 for (int j = i + 1; j < len; j++) {
693 final TraceInterval i2 = intervals()[j];
694 if (i2 == null) {
695 continue;
696 }
697
698 // special intervals that are created in MoveResolver
699 // . ignore them because the range information has no meaning there
700 if (i2.from() == 1 && i2.to() == 2) {
701 continue;
702 }
951 LIRInstruction instructionForId(int opId) {
952 assert isEven(opId) : "opId not even";
953 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)];
954 assert instr.id() == opId;
955 return instr;
956 }
957
958 /**
959 * Gets the block containing a given instruction.
960 *
961 * @param opId an instruction {@linkplain LIRInstruction#id id}
962 * @return the block containing the instruction denoted by {@code opId}
963 */
964 AbstractBlockBase<?> blockForId(int opId) {
965 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range: " + opId;
966 return opIdToBlockMap[opIdToIndex(opId)];
967 }
968
969 @SuppressWarnings("try")
970 public void printIntervals(String label) {
971 DebugContext debug = getDebug();
972 if (debug.isDumpEnabled(DebugContext.DETAILED_LEVEL)) {
973 if (debug.isLogEnabled()) {
974 try (Indent indent = debug.logAndIndent("intervals %s", label)) {
975 for (FixedInterval interval : fixedIntervals) {
976 if (interval != null) {
977 debug.log("%s", interval.logString());
978 }
979 }
980
981 for (TraceInterval interval : intervals) {
982 if (interval != null) {
983 debug.log("%s", interval.logString());
984 }
985 }
986
987 try (Indent indent2 = debug.logAndIndent("Basic Blocks")) {
988 for (AbstractBlockBase<?> block : trace.getBlocks()) {
989 debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop());
990 }
991 }
992 }
993 }
994 debug.dump(DebugContext.DETAILED_LEVEL, this, "%s (Trace%d)", label, trace.getId());
995 }
996 }
997
998 @Override
999 public void visitIntervals(IntervalVisitor visitor) {
1000 for (FixedInterval interval : fixedIntervals) {
1001 if (interval != null) {
1002 printFixedInterval(interval, visitor);
1003 }
1004 }
1005 for (TraceInterval interval : intervals) {
1006 if (interval != null) {
1007 printInterval(interval, visitor);
1008 }
1009 }
1010 }
1011
1012 boolean hasInterTracePredecessor(AbstractBlockBase<?> block) {
1013 return TraceUtil.hasInterTracePredecessor(traceBuilderResult, trace, block);
1014 }
|