LinearScan.java revision 12995:5e441a7ec5e3
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 */ 23package org.graalvm.compiler.lir.alloc.lsra; 24 25import static jdk.vm.ci.code.CodeUtil.isEven; 26import static jdk.vm.ci.code.ValueUtil.asRegister; 27import static jdk.vm.ci.code.ValueUtil.isIllegal; 28import static jdk.vm.ci.code.ValueUtil.isLegal; 29import static jdk.vm.ci.code.ValueUtil.isRegister; 30import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts; 31import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 32import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization; 33 34import java.util.ArrayList; 35import java.util.Arrays; 36import java.util.BitSet; 37import java.util.EnumSet; 38 39import org.graalvm.compiler.core.common.LIRKind; 40import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; 41import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 42import org.graalvm.compiler.core.common.cfg.BlockMap; 43import org.graalvm.compiler.debug.Debug; 44import org.graalvm.compiler.debug.Debug.Scope; 45import org.graalvm.compiler.debug.GraalError; 46import org.graalvm.compiler.debug.Indent; 47import org.graalvm.compiler.lir.LIR; 48import org.graalvm.compiler.lir.LIRInstruction; 49import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; 50import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 51import org.graalvm.compiler.lir.ValueConsumer; 52import org.graalvm.compiler.lir.Variable; 53import org.graalvm.compiler.lir.VirtualStackSlot; 54import org.graalvm.compiler.lir.alloc.lsra.Interval.RegisterBinding; 55import org.graalvm.compiler.lir.framemap.FrameMapBuilder; 56import org.graalvm.compiler.lir.gen.LIRGenerationResult; 57import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; 58import org.graalvm.compiler.lir.phases.AllocationPhase.AllocationContext; 59import org.graalvm.compiler.options.NestedBooleanOptionKey; 60import org.graalvm.compiler.options.Option; 61import org.graalvm.compiler.options.OptionKey; 62import org.graalvm.compiler.options.OptionType; 63import org.graalvm.compiler.options.OptionValues; 64import org.graalvm.util.Pair; 65 66import jdk.vm.ci.code.Register; 67import jdk.vm.ci.code.RegisterArray; 68import jdk.vm.ci.code.RegisterAttributes; 69import jdk.vm.ci.code.RegisterValue; 70import jdk.vm.ci.code.TargetDescription; 71import jdk.vm.ci.meta.AllocatableValue; 72import jdk.vm.ci.meta.Value; 73 74/** 75 * An implementation of the linear scan register allocator algorithm described in 76 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear 77 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck. 78 */ 79public class LinearScan { 80 81 public static class Options { 82 // @formatter:off 83 @Option(help = "Enable spill position optimization", type = OptionType.Debug) 84 public static final OptionKey<Boolean> LIROptLSRAOptimizeSpillPosition = new NestedBooleanOptionKey(LIROptimization, true); 85 // @formatter:on 86 } 87 88 public static class BlockData { 89 90 /** 91 * Bit map specifying which operands are live upon entry to this block. These are values 92 * used in this block or any of its successors where such value are not defined in this 93 * block. The bit index of an operand is its {@linkplain LinearScan#operandNumber(Value) 94 * operand number}. 95 */ 96 public BitSet liveIn; 97 98 /** 99 * Bit map specifying which operands are live upon exit from this block. These are values 100 * used in a successor block that are either defined in this block or were live upon entry 101 * to this block. The bit index of an operand is its 102 * {@linkplain LinearScan#operandNumber(Value) operand number}. 103 */ 104 public BitSet liveOut; 105 106 /** 107 * Bit map specifying which operands are used (before being defined) in this block. That is, 108 * these are the values that are live upon entry to the block. The bit index of an operand 109 * is its {@linkplain LinearScan#operandNumber(Value) operand number}. 110 */ 111 public BitSet liveGen; 112 113 /** 114 * Bit map specifying which operands are defined/overwritten in this block. The bit index of 115 * an operand is its {@linkplain LinearScan#operandNumber(Value) operand number}. 116 */ 117 public BitSet liveKill; 118 } 119 120 public static final int DOMINATOR_SPILL_MOVE_ID = -2; 121 private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; 122 123 private final LIR ir; 124 private final FrameMapBuilder frameMapBuilder; 125 private final RegisterAttributes[] registerAttributes; 126 private final RegisterArray registers; 127 private final RegisterAllocationConfig regAllocConfig; 128 private final MoveFactory moveFactory; 129 130 private final BlockMap<BlockData> blockData; 131 132 /** 133 * List of blocks in linear-scan order. This is only correct as long as the CFG does not change. 134 */ 135 private final AbstractBlockBase<?>[] sortedBlocks; 136 137 /** 138 * @see #intervals() 139 */ 140 private Interval[] intervals; 141 142 /** 143 * The number of valid entries in {@link #intervals}. 144 */ 145 private int intervalsSize; 146 147 /** 148 * The index of the first entry in {@link #intervals} for a 149 * {@linkplain #createDerivedInterval(Interval) derived interval}. 150 */ 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 189 protected LinearScan(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, AbstractBlockBase<?>[] sortedBlocks, 190 boolean neverSpillConstants) { 191 this.ir = res.getLIR(); 192 this.moveFactory = spillMoveFactory; 193 this.frameMapBuilder = res.getFrameMapBuilder(); 194 this.sortedBlocks = sortedBlocks; 195 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap(); 196 this.regAllocConfig = regAllocConfig; 197 198 this.registers = target.arch.getRegisters(); 199 this.firstVariableNumber = getRegisters().size(); 200 this.numVariables = ir.numVariables(); 201 this.blockData = new BlockMap<>(ir.getControlFlowGraph()); 202 this.neverSpillConstants = neverSpillConstants; 203 this.rangeEndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null); 204 this.intervalEndMarker = new Interval(Value.ILLEGAL, Interval.END_MARKER_OPERAND_NUMBER, null, rangeEndMarker); 205 this.intervalEndMarker.next = intervalEndMarker; 206 this.detailedAsserts = DetailedAsserts.getValue(ir.getOptions()); 207 } 208 209 public Interval intervalEndMarker() { 210 return intervalEndMarker; 211 } 212 213 public OptionValues getOptions() { 214 return ir.getOptions(); 215 } 216 217 public int getFirstLirInstructionId(AbstractBlockBase<?> block) { 218 int result = ir.getLIRforBlock(block).get(0).id(); 219 assert result >= 0; 220 return result; 221 } 222 223 public int getLastLirInstructionId(AbstractBlockBase<?> block) { 224 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block); 225 int result = instructions.get(instructions.size() - 1).id(); 226 assert result >= 0; 227 return result; 228 } 229 230 public MoveFactory getSpillMoveFactory() { 231 return moveFactory; 232 } 233 234 protected MoveResolver createMoveResolver() { 235 MoveResolver moveResolver = new MoveResolver(this); 236 assert moveResolver.checkEmpty(); 237 return moveResolver; 238 } 239 240 public static boolean isVariableOrRegister(Value value) { 241 return isVariable(value) || isRegister(value); 242 } 243 244 /** 245 * Converts an operand (variable or register) to an index in a flat address space covering all 246 * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed 247 * by this allocator. 248 */ 249 int operandNumber(Value operand) { 250 if (isRegister(operand)) { 251 int number = asRegister(operand).number; 252 assert number < firstVariableNumber; 253 return number; 254 } 255 assert isVariable(operand) : operand; 256 return firstVariableNumber + ((Variable) operand).index; 257 } 258 259 /** 260 * Gets the number of operands. This value will increase by 1 for new variable. 261 */ 262 int operandSize() { 263 return firstVariableNumber + numVariables; 264 } 265 266 /** 267 * Gets the highest operand number for a register operand. This value will never change. 268 */ 269 int maxRegisterNumber() { 270 return firstVariableNumber - 1; 271 } 272 273 public BlockData getBlockData(AbstractBlockBase<?> block) { 274 return blockData.get(block); 275 } 276 277 void initBlockData(AbstractBlockBase<?> block) { 278 blockData.put(block, new BlockData()); 279 } 280 281 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { 282 283 @Override 284 public boolean apply(Interval i) { 285 return isRegister(i.operand); 286 } 287 }; 288 289 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { 290 291 @Override 292 public boolean apply(Interval i) { 293 return isVariable(i.operand); 294 } 295 }; 296 297 static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() { 298 299 @Override 300 public boolean apply(Interval i) { 301 return !isRegister(i.operand); 302 } 303 }; 304 305 /** 306 * Gets an object describing the attributes of a given register according to this register 307 * configuration. 308 */ 309 public RegisterAttributes attributes(Register reg) { 310 return registerAttributes[reg.number]; 311 } 312 313 void assignSpillSlot(Interval interval) { 314 /* 315 * Assign the canonical spill slot of the parent (if a part of the interval is already 316 * spilled) or allocate a new spill slot. 317 */ 318 if (interval.canMaterialize()) { 319 interval.assignLocation(Value.ILLEGAL); 320 } else if (interval.spillSlot() != null) { 321 interval.assignLocation(interval.spillSlot()); 322 } else { 323 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind()); 324 interval.setSpillSlot(slot); 325 interval.assignLocation(slot); 326 } 327 } 328 329 /** 330 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. 331 */ 332 public Interval[] intervals() { 333 return intervals; 334 } 335 336 void initIntervals() { 337 intervalsSize = operandSize(); 338 intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; 339 } 340 341 /** 342 * Creates a new interval. 343 * 344 * @param operand the operand for the interval 345 * @return the created interval 346 */ 347 Interval createInterval(AllocatableValue operand) { 348 assert isLegal(operand); 349 int operandNumber = operandNumber(operand); 350 Interval interval = new Interval(operand, operandNumber, intervalEndMarker, rangeEndMarker); 351 assert operandNumber < intervalsSize; 352 assert intervals[operandNumber] == null; 353 intervals[operandNumber] = interval; 354 return interval; 355 } 356 357 /** 358 * Creates an interval as a result of splitting or spilling another interval. 359 * 360 * @param source an interval being split of spilled 361 * @return a new interval derived from {@code source} 362 */ 363 Interval createDerivedInterval(Interval source) { 364 if (firstDerivedIntervalIndex == -1) { 365 firstDerivedIntervalIndex = intervalsSize; 366 } 367 if (intervalsSize == intervals.length) { 368 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT) + 1); 369 } 370 intervalsSize++; 371 assert intervalsSize <= intervals.length; 372 /* 373 * Note that these variables are not managed and must therefore never be inserted into the 374 * LIR 375 */ 376 Variable variable = new Variable(source.kind(), numVariables++); 377 378 Interval interval = createInterval(variable); 379 assert intervals[intervalsSize - 1] == interval; 380 return interval; 381 } 382 383 // access to block list (sorted in linear scan order) 384 public int blockCount() { 385 return sortedBlocks.length; 386 } 387 388 public AbstractBlockBase<?> blockAt(int index) { 389 return sortedBlocks[index]; 390 } 391 392 /** 393 * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic 394 * block. These sets do not include any operands allocated as a result of creating 395 * {@linkplain #createDerivedInterval(Interval) derived intervals}. 396 */ 397 public int liveSetSize() { 398 return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex; 399 } 400 401 int numLoops() { 402 return ir.getControlFlowGraph().getLoops().size(); 403 } 404 405 Interval intervalFor(int operandNumber) { 406 return intervals[operandNumber]; 407 } 408 409 public Interval intervalFor(Value operand) { 410 int operandNumber = operandNumber(operand); 411 assert operandNumber < intervalsSize; 412 return intervals[operandNumber]; 413 } 414 415 public Interval getOrCreateInterval(AllocatableValue operand) { 416 Interval ret = intervalFor(operand); 417 if (ret == null) { 418 return createInterval(operand); 419 } else { 420 return ret; 421 } 422 } 423 424 void initOpIdMaps(int numInstructions) { 425 opIdToInstructionMap = new LIRInstruction[numInstructions]; 426 opIdToBlockMap = new AbstractBlockBase<?>[numInstructions]; 427 } 428 429 void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) { 430 opIdToInstructionMap[index] = op; 431 opIdToBlockMap[index] = block; 432 } 433 434 /** 435 * Gets the highest instruction id allocated by this object. 436 */ 437 int maxOpId() { 438 assert opIdToInstructionMap.length > 0 : "no operations"; 439 return (opIdToInstructionMap.length - 1) << 1; 440 } 441 442 /** 443 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All LIR 444 * instructions in a method have an index one greater than their linear-scan order predecessor 445 * with the first instruction having an index of 0. 446 */ 447 private static int opIdToIndex(int opId) { 448 return opId >> 1; 449 } 450 451 /** 452 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. 453 * 454 * @param opId an instruction {@linkplain LIRInstruction#id id} 455 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} 456 */ 457 public LIRInstruction instructionForId(int opId) { 458 assert isEven(opId) : "opId not even"; 459 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; 460 assert instr.id() == opId; 461 return instr; 462 } 463 464 /** 465 * Gets the block containing a given instruction. 466 * 467 * @param opId an instruction {@linkplain LIRInstruction#id id} 468 * @return the block containing the instruction denoted by {@code opId} 469 */ 470 public AbstractBlockBase<?> blockForId(int opId) { 471 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range"; 472 return opIdToBlockMap[opIdToIndex(opId)]; 473 } 474 475 boolean isBlockBegin(int opId) { 476 return opId == 0 || blockForId(opId) != blockForId(opId - 1); 477 } 478 479 boolean coversBlockBegin(int opId1, int opId2) { 480 return blockForId(opId1) != blockForId(opId2); 481 } 482 483 /** 484 * Determines if an {@link LIRInstruction} destroys all caller saved registers. 485 * 486 * @param opId an instruction {@linkplain LIRInstruction#id id} 487 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved 488 * registers. 489 */ 490 boolean hasCall(int opId) { 491 assert isEven(opId) : "opId not even"; 492 return instructionForId(opId).destroysCallerSavedRegisters(); 493 } 494 495 abstract static class IntervalPredicate { 496 497 abstract boolean apply(Interval i); 498 } 499 500 public boolean isProcessed(Value operand) { 501 return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable(); 502 } 503 504 // * Phase 5: actual register allocation 505 506 private static boolean isSorted(Interval[] intervals) { 507 int from = -1; 508 for (Interval interval : intervals) { 509 assert interval != null; 510 assert from <= interval.from(); 511 from = interval.from(); 512 } 513 return true; 514 } 515 516 static Interval addToList(Interval first, Interval prev, Interval interval) { 517 Interval newFirst = first; 518 if (prev != null) { 519 prev.next = interval; 520 } else { 521 newFirst = interval; 522 } 523 return newFirst; 524 } 525 526 Pair<Interval, Interval> createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) { 527 assert isSorted(sortedIntervals) : "interval list is not sorted"; 528 529 Interval list1 = intervalEndMarker; 530 Interval list2 = intervalEndMarker; 531 532 Interval list1Prev = null; 533 Interval list2Prev = null; 534 Interval v; 535 536 int n = sortedIntervals.length; 537 for (int i = 0; i < n; i++) { 538 v = sortedIntervals[i]; 539 if (v == null) { 540 continue; 541 } 542 543 if (isList1.apply(v)) { 544 list1 = addToList(list1, list1Prev, v); 545 list1Prev = v; 546 } else if (isList2 == null || isList2.apply(v)) { 547 list2 = addToList(list2, list2Prev, v); 548 list2Prev = v; 549 } 550 } 551 552 if (list1Prev != null) { 553 list1Prev.next = intervalEndMarker; 554 } 555 if (list2Prev != null) { 556 list2Prev.next = intervalEndMarker; 557 } 558 559 assert list1Prev == null || list1Prev.next.isEndMarker() : "linear list ends not with sentinel"; 560 assert list2Prev == null || list2Prev.next.isEndMarker() : "linear list ends not with sentinel"; 561 562 return Pair.create(list1, list2); 563 } 564 565 protected void sortIntervalsBeforeAllocation() { 566 int sortedLen = 0; 567 for (Interval interval : intervals) { 568 if (interval != null) { 569 sortedLen++; 570 } 571 } 572 573 Interval[] sortedList = new Interval[sortedLen]; 574 int sortedIdx = 0; 575 int sortedFromMax = -1; 576 577 // special sorting algorithm: the original interval-list is almost sorted, 578 // only some intervals are swapped. So this is much faster than a complete QuickSort 579 for (Interval interval : intervals) { 580 if (interval != null) { 581 int from = interval.from(); 582 583 if (sortedFromMax <= from) { 584 sortedList[sortedIdx++] = interval; 585 sortedFromMax = interval.from(); 586 } else { 587 // the assumption that the intervals are already sorted failed, 588 // so this interval must be sorted in manually 589 int j; 590 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) { 591 sortedList[j + 1] = sortedList[j]; 592 } 593 sortedList[j + 1] = interval; 594 sortedIdx++; 595 } 596 } 597 } 598 sortedIntervals = sortedList; 599 } 600 601 void sortIntervalsAfterAllocation() { 602 if (firstDerivedIntervalIndex == -1) { 603 // no intervals have been added during allocation, so sorted list is already up to date 604 return; 605 } 606 607 Interval[] oldList = sortedIntervals; 608 Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize); 609 int oldLen = oldList.length; 610 int newLen = newList.length; 611 612 // conventional sort-algorithm for new intervals 613 Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from()); 614 615 // merge old and new list (both already sorted) into one combined list 616 Interval[] combinedList = new Interval[oldLen + newLen]; 617 int oldIdx = 0; 618 int newIdx = 0; 619 620 while (oldIdx + newIdx < combinedList.length) { 621 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) { 622 combinedList[oldIdx + newIdx] = oldList[oldIdx]; 623 oldIdx++; 624 } else { 625 combinedList[oldIdx + newIdx] = newList[newIdx]; 626 newIdx++; 627 } 628 } 629 630 sortedIntervals = combinedList; 631 } 632 633 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode 634 // instead of returning null 635 public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) { 636 Interval result = interval.getSplitChildAtOpId(opId, mode, this); 637 638 if (result != null) { 639 if (Debug.isLogEnabled()) { 640 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result); 641 } 642 return result; 643 } 644 throw new GraalError("LinearScan: interval is null"); 645 } 646 647 static AllocatableValue canonicalSpillOpr(Interval interval) { 648 assert interval.spillSlot() != null : "canonical spill slot not set"; 649 return interval.spillSlot(); 650 } 651 652 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) { 653 Interval interval = intervalFor(operand); 654 assert interval != null : "interval must exist"; 655 656 if (opId != -1) { 657 /* 658 * Operands are not changed when an interval is split during allocation, so search the 659 * right interval here. 660 */ 661 interval = splitChildAtOpId(interval, opId, mode); 662 } 663 664 return isIllegal(interval.location()) && interval.canMaterialize(); 665 } 666 667 boolean isCallerSave(Value operand) { 668 return attributes(asRegister(operand)).isCallerSave(); 669 } 670 671 @SuppressWarnings("try") 672 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 673 /* 674 * This is the point to enable debug logging for the whole register allocation. 675 */ 676 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { 677 678 createLifetimeAnalysisPhase().apply(target, lirGenRes, context); 679 680 try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) { 681 sortIntervalsBeforeAllocation(); 682 683 createRegisterAllocationPhase().apply(target, lirGenRes, context); 684 685 if (LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue(getOptions())) { 686 createOptimizeSpillPositionPhase().apply(target, lirGenRes, context); 687 } 688 createResolveDataFlowPhase().apply(target, lirGenRes, context); 689 690 sortIntervalsAfterAllocation(); 691 692 if (detailedAsserts) { 693 verify(); 694 } 695 beforeSpillMoveElimination(); 696 createSpillMoveEliminationPhase().apply(target, lirGenRes, context); 697 createAssignLocationsPhase().apply(target, lirGenRes, context); 698 699 if (detailedAsserts) { 700 verifyIntervals(); 701 } 702 } catch (Throwable e) { 703 throw Debug.handle(e); 704 } 705 } 706 } 707 708 protected void beforeSpillMoveElimination() { 709 } 710 711 protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { 712 return new LinearScanLifetimeAnalysisPhase(this); 713 } 714 715 protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase() { 716 return new LinearScanRegisterAllocationPhase(this); 717 } 718 719 protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() { 720 return new LinearScanOptimizeSpillPositionPhase(this); 721 } 722 723 protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { 724 return new LinearScanResolveDataFlowPhase(this); 725 } 726 727 protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { 728 return new LinearScanEliminateSpillMovePhase(this); 729 } 730 731 protected LinearScanAssignLocationsPhase createAssignLocationsPhase() { 732 return new LinearScanAssignLocationsPhase(this); 733 } 734 735 @SuppressWarnings("try") 736 public void printIntervals(String label) { 737 if (Debug.isLogEnabled()) { 738 try (Indent indent = Debug.logAndIndent("intervals %s", label)) { 739 for (Interval interval : intervals) { 740 if (interval != null) { 741 Debug.log("%s", interval.logString(this)); 742 } 743 } 744 745 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { 746 for (int i = 0; i < blockCount(); i++) { 747 AbstractBlockBase<?> block = blockAt(i); 748 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); 749 } 750 } 751 } 752 } 753 Debug.dump(Debug.BASIC_LEVEL, new LinearScanIntervalDumper(Arrays.copyOf(intervals, intervalsSize)), label); 754 } 755 756 public void printLir(String label, @SuppressWarnings("unused") boolean hirValid) { 757 Debug.dump(Debug.INFO_LEVEL, ir, label); 758 } 759 760 boolean verify() { 761 // (check that all intervals have a correct register and that no registers are overwritten) 762 verifyIntervals(); 763 764 verifyRegisters(); 765 766 Debug.log("no errors found"); 767 768 return true; 769 } 770 771 @SuppressWarnings("try") 772 private void verifyRegisters() { 773 // Enable this logging to get output for the verification process. 774 try (Indent indent = Debug.logAndIndent("verifying register allocation")) { 775 RegisterVerifier verifier = new RegisterVerifier(this); 776 verifier.verify(blockAt(0)); 777 } 778 } 779 780 @SuppressWarnings("try") 781 protected void verifyIntervals() { 782 try (Indent indent = Debug.logAndIndent("verifying intervals")) { 783 int len = intervalsSize; 784 785 for (int i = 0; i < len; i++) { 786 Interval i1 = intervals[i]; 787 if (i1 == null) { 788 continue; 789 } 790 791 i1.checkSplitChildren(); 792 793 if (i1.operandNumber != i) { 794 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i); 795 Debug.log(i1.logString(this)); 796 throw new GraalError(""); 797 } 798 799 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) { 800 Debug.log("Interval %d has no type assigned", i1.operandNumber); 801 Debug.log(i1.logString(this)); 802 throw new GraalError(""); 803 } 804 805 if (i1.location() == null) { 806 Debug.log("Interval %d has no register assigned", i1.operandNumber); 807 Debug.log(i1.logString(this)); 808 throw new GraalError(""); 809 } 810 811 if (i1.first().isEndMarker()) { 812 Debug.log("Interval %d has no Range", i1.operandNumber); 813 Debug.log(i1.logString(this)); 814 throw new GraalError(""); 815 } 816 817 for (Range r = i1.first(); !r.isEndMarker(); r = r.next) { 818 if (r.from >= r.to) { 819 Debug.log("Interval %d has zero length range", i1.operandNumber); 820 Debug.log(i1.logString(this)); 821 throw new GraalError(""); 822 } 823 } 824 825 for (int j = i + 1; j < len; j++) { 826 Interval i2 = intervals[j]; 827 if (i2 == null) { 828 continue; 829 } 830 831 // special intervals that are created in MoveResolver 832 // . ignore them because the range information has no meaning there 833 if (i1.from() == 1 && i1.to() == 2) { 834 continue; 835 } 836 if (i2.from() == 1 && i2.to() == 2) { 837 continue; 838 } 839 Value l1 = i1.location(); 840 Value l2 = i2.location(); 841 if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) { 842 throw GraalError.shouldNotReachHere(String.format("Intervals %d and %d overlap and have the same register assigned\n%s\n%s", i1.operandNumber, i2.operandNumber, 843 i1.logString(this), i2.logString(this))); 844 } 845 } 846 } 847 } 848 } 849 850 class CheckConsumer implements ValueConsumer { 851 852 boolean ok; 853 Interval curInterval; 854 855 @Override 856 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { 857 if (isRegister(operand)) { 858 if (intervalFor(operand) == curInterval) { 859 ok = true; 860 } 861 } 862 } 863 } 864 865 @SuppressWarnings("try") 866 void verifyNoOopsInFixedIntervals() { 867 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { 868 CheckConsumer checkConsumer = new CheckConsumer(); 869 870 Interval fixedIntervals; 871 Interval otherIntervals; 872 fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).getLeft(); 873 // to ensure a walking until the last instruction id, add a dummy interval 874 // with a high operation id 875 otherIntervals = new Interval(Value.ILLEGAL, -1, intervalEndMarker, rangeEndMarker); 876 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); 877 IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals); 878 879 for (AbstractBlockBase<?> block : sortedBlocks) { 880 ArrayList<LIRInstruction> instructions = ir.getLIRforBlock(block); 881 882 for (int j = 0; j < instructions.size(); j++) { 883 LIRInstruction op = instructions.get(j); 884 885 if (op.hasState()) { 886 iw.walkBefore(op.id()); 887 boolean checkLive = true; 888 889 /* 890 * Make sure none of the fixed registers is live across an oopmap since we 891 * can't handle that correctly. 892 */ 893 if (checkLive) { 894 for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); !interval.isEndMarker(); interval = interval.next) { 895 if (interval.currentTo() > op.id() + 1) { 896 /* 897 * This interval is live out of this op so make sure that this 898 * interval represents some value that's referenced by this op 899 * either as an input or output. 900 */ 901 checkConsumer.curInterval = interval; 902 checkConsumer.ok = false; 903 904 op.visitEachInput(checkConsumer); 905 op.visitEachAlive(checkConsumer); 906 op.visitEachTemp(checkConsumer); 907 op.visitEachOutput(checkConsumer); 908 909 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point"; 910 } 911 } 912 } 913 } 914 } 915 } 916 } 917 } 918 919 public LIR getLIR() { 920 return ir; 921 } 922 923 public FrameMapBuilder getFrameMapBuilder() { 924 return frameMapBuilder; 925 } 926 927 public AbstractBlockBase<?>[] sortedBlocks() { 928 return sortedBlocks; 929 } 930 931 public RegisterArray getRegisters() { 932 return registers; 933 } 934 935 public RegisterAllocationConfig getRegisterAllocationConfig() { 936 return regAllocConfig; 937 } 938 939 public boolean callKillsRegisters() { 940 return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); 941 } 942 943 boolean neverSpillConstants() { 944 return neverSpillConstants; 945 } 946 947} 948