TraceLinearScanPhase.java revision 13017:134219a5b0ec
1/* 2 * Copyright (c) 2009, 2017, 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.trace.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.asRegisterValue; 28import static jdk.vm.ci.code.ValueUtil.isIllegal; 29import static jdk.vm.ci.code.ValueUtil.isLegal; 30import static jdk.vm.ci.code.ValueUtil.isRegister; 31import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts; 32import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 33 34import java.util.ArrayList; 35import java.util.Arrays; 36import java.util.EnumSet; 37 38import org.graalvm.compiler.core.common.LIRKind; 39import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; 40import org.graalvm.compiler.core.common.alloc.Trace; 41import org.graalvm.compiler.core.common.alloc.TraceBuilderResult; 42import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 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.LIRValueUtil; 52import org.graalvm.compiler.lir.StandardOp.BlockEndOp; 53import org.graalvm.compiler.lir.ValueConsumer; 54import org.graalvm.compiler.lir.Variable; 55import org.graalvm.compiler.lir.VirtualStackSlot; 56import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo; 57import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase; 58import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext; 59import org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase; 60import org.graalvm.compiler.lir.alloc.trace.TraceUtil; 61import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterPriority; 62import org.graalvm.compiler.lir.debug.IntervalDumper; 63import org.graalvm.compiler.lir.debug.IntervalDumper.IntervalVisitor; 64import org.graalvm.compiler.lir.framemap.FrameMapBuilder; 65import org.graalvm.compiler.lir.gen.LIRGenerationResult; 66import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; 67import org.graalvm.compiler.lir.phases.LIRPhase; 68import org.graalvm.compiler.options.NestedBooleanOptionKey; 69import org.graalvm.compiler.options.Option; 70import org.graalvm.compiler.options.OptionKey; 71import org.graalvm.compiler.options.OptionType; 72import org.graalvm.compiler.options.OptionValues; 73 74import jdk.vm.ci.code.Register; 75import jdk.vm.ci.code.RegisterArray; 76import jdk.vm.ci.code.RegisterAttributes; 77import jdk.vm.ci.code.RegisterValue; 78import jdk.vm.ci.code.TargetDescription; 79import jdk.vm.ci.meta.AllocatableValue; 80import jdk.vm.ci.meta.Value; 81import jdk.vm.ci.meta.ValueKind; 82 83/** 84 * Implementation of the Linear Scan allocation approach for traces described in 85 * <a href="http://dx.doi.org/10.1145/2972206.2972211">"Trace-based Register Allocation in a JIT 86 * Compiler"</a> by Josef Eisl et al. It is derived from 87 * <a href="http://doi.acm.org/10.1145/1064979.1064998" > "Optimized Interval Splitting in a Linear 88 * Scan Register Allocator"</a> by Christian Wimmer and Hanspeter Moessenboeck. 89 */ 90public final class TraceLinearScanPhase extends TraceAllocationPhase<TraceAllocationContext> { 91 92 public static class Options { 93 // @formatter:off 94 @Option(help = "Enable spill position optimization", type = OptionType.Debug) 95 public static final OptionKey<Boolean> LIROptTraceRAEliminateSpillMoves = new NestedBooleanOptionKey(LIRPhase.Options.LIROptimization, true); 96 // @formatter:on 97 } 98 99 private static final TraceLinearScanRegisterAllocationPhase TRACE_LINEAR_SCAN_REGISTER_ALLOCATION_PHASE = new TraceLinearScanRegisterAllocationPhase(); 100 private static final TraceLinearScanAssignLocationsPhase TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE = new TraceLinearScanAssignLocationsPhase(); 101 private static final TraceLinearScanEliminateSpillMovePhase TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE = new TraceLinearScanEliminateSpillMovePhase(); 102 private static final TraceLinearScanResolveDataFlowPhase TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE = new TraceLinearScanResolveDataFlowPhase(); 103 private static final TraceLinearScanLifetimeAnalysisPhase TRACE_LINEAR_SCAN_LIFETIME_ANALYSIS_PHASE = new TraceLinearScanLifetimeAnalysisPhase(); 104 105 public static final int DOMINATOR_SPILL_MOVE_ID = -2; 106 107 private final FrameMapBuilder frameMapBuilder; 108 private final RegisterAttributes[] registerAttributes; 109 private final RegisterArray registers; 110 private final RegisterAllocationConfig regAllocConfig; 111 private final MoveFactory moveFactory; 112 113 protected final TraceBuilderResult traceBuilderResult; 114 115 private final boolean neverSpillConstants; 116 117 /** 118 * Maps from {@link Variable#index} to a spill stack slot. If 119 * {@linkplain org.graalvm.compiler.lir.alloc.trace.TraceRegisterAllocationPhase.Options#TraceRACacheStackSlots 120 * enabled} a {@link Variable} is always assigned to the same stack slot. 121 */ 122 private final AllocatableValue[] cachedStackSlots; 123 124 private final LIRGenerationResult res; 125 private final GlobalLivenessInfo livenessInfo; 126 127 public TraceLinearScanPhase(TargetDescription target, LIRGenerationResult res, MoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, TraceBuilderResult traceBuilderResult, 128 boolean neverSpillConstants, AllocatableValue[] cachedStackSlots, GlobalLivenessInfo livenessInfo) { 129 this.res = res; 130 this.moveFactory = spillMoveFactory; 131 this.frameMapBuilder = res.getFrameMapBuilder(); 132 this.registerAttributes = regAllocConfig.getRegisterConfig().getAttributesMap(); 133 this.regAllocConfig = regAllocConfig; 134 135 this.registers = target.arch.getRegisters(); 136 this.traceBuilderResult = traceBuilderResult; 137 this.neverSpillConstants = neverSpillConstants; 138 this.cachedStackSlots = cachedStackSlots; 139 this.livenessInfo = livenessInfo; 140 assert livenessInfo != null; 141 } 142 143 public static boolean isVariableOrRegister(Value value) { 144 return isVariable(value) || isRegister(value); 145 } 146 147 abstract static class IntervalPredicate { 148 149 abstract boolean apply(TraceInterval i); 150 } 151 152 static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() { 153 154 @Override 155 public boolean apply(TraceInterval i) { 156 return isRegister(i.operand); 157 } 158 }; 159 160 static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() { 161 162 @Override 163 public boolean apply(TraceInterval i) { 164 return isVariable(i.operand); 165 } 166 }; 167 168 static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() { 169 170 @Override 171 public boolean apply(TraceInterval i) { 172 return !isRegister(i.operand); 173 } 174 }; 175 176 public TraceLinearScan createAllocator(Trace trace) { 177 return new TraceLinearScan(trace); 178 } 179 180 @Override 181 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, TraceAllocationContext traceContext) { 182 createAllocator(trace).allocate(target, lirGenRes, traceContext); 183 } 184 185 private static <T extends IntervalHint> boolean isSortedByFrom(T[] intervals) { 186 int from = -1; 187 for (T interval : intervals) { 188 assert interval != null; 189 assert from <= interval.from(); 190 from = interval.from(); 191 } 192 return true; 193 } 194 195 private static boolean isSortedBySpillPos(TraceInterval[] intervals) { 196 int from = -1; 197 for (TraceInterval interval : intervals) { 198 assert interval != null; 199 assert from <= interval.spillDefinitionPos(); 200 from = interval.spillDefinitionPos(); 201 } 202 return true; 203 } 204 205 private static <T extends IntervalHint> T[] sortIntervalsBeforeAllocation(T[] intervals, T[] sortedList) { 206 int sortedIdx = 0; 207 int sortedFromMax = -1; 208 209 // special sorting algorithm: the original interval-list is almost sorted, 210 // only some intervals are swapped. So this is much faster than a complete QuickSort 211 for (T interval : intervals) { 212 if (interval != null) { 213 int from = interval.from(); 214 215 if (sortedFromMax <= from) { 216 sortedList[sortedIdx++] = interval; 217 sortedFromMax = interval.from(); 218 } else { 219 // the assumption that the intervals are already sorted failed, 220 // so this interval must be sorted in manually 221 int j; 222 for (j = sortedIdx - 1; j >= 0 && from < sortedList[j].from(); j--) { 223 sortedList[j + 1] = sortedList[j]; 224 } 225 sortedList[j + 1] = interval; 226 sortedIdx++; 227 } 228 } 229 } 230 return sortedList; 231 } 232 233 public final class TraceLinearScan implements IntervalDumper { 234 235 /** 236 * Intervals sorted by {@link TraceInterval#from()}. 237 */ 238 private TraceInterval[] sortedIntervals; 239 240 /** 241 * Fixed intervals sorted by {@link FixedInterval#from()}. 242 */ 243 private FixedInterval[] sortedFixedIntervals; 244 245 private final Trace trace; 246 247 public TraceLinearScan(Trace trace) { 248 this.trace = trace; 249 this.fixedIntervals = new FixedInterval[registers.size()]; 250 } 251 252 GlobalLivenessInfo getGlobalLivenessInfo() { 253 return livenessInfo; 254 } 255 256 /** 257 * Converts an operand (variable or register) to an index in a flat address space covering 258 * all the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being 259 * processed by this allocator. 260 */ 261 int operandNumber(Value operand) { 262 assert !isRegister(operand) : "Register do not have operand numbers: " + operand; 263 assert isVariable(operand) : "Unsupported Value " + operand; 264 return ((Variable) operand).index; 265 } 266 267 OptionValues getOptions() { 268 return getLIR().getOptions(); 269 } 270 271 /** 272 * Gets the number of operands. This value will increase by 1 for new variable. 273 */ 274 int operandSize() { 275 return getLIR().numVariables(); 276 } 277 278 /** 279 * Gets the number of registers. This value will never change. 280 */ 281 int numRegisters() { 282 return registers.size(); 283 } 284 285 public int getFirstLirInstructionId(AbstractBlockBase<?> block) { 286 int result = getLIR().getLIRforBlock(block).get(0).id(); 287 assert result >= 0; 288 return result; 289 } 290 291 public int getLastLirInstructionId(AbstractBlockBase<?> block) { 292 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block); 293 int result = instructions.get(instructions.size() - 1).id(); 294 assert result >= 0; 295 return result; 296 } 297 298 /** 299 * Gets an object describing the attributes of a given register according to this register 300 * configuration. 301 */ 302 public RegisterAttributes attributes(Register reg) { 303 return registerAttributes[reg.number]; 304 } 305 306 public MoveFactory getSpillMoveFactory() { 307 return moveFactory; 308 } 309 310 protected TraceLocalMoveResolver createMoveResolver() { 311 TraceLocalMoveResolver moveResolver = new TraceLocalMoveResolver(this); 312 assert moveResolver.checkEmpty(); 313 return moveResolver; 314 } 315 316 void assignSpillSlot(TraceInterval interval) { 317 /* 318 * Assign the canonical spill slot of the parent (if a part of the interval is already 319 * spilled) or allocate a new spill slot. 320 */ 321 if (interval.canMaterialize()) { 322 interval.assignLocation(Value.ILLEGAL); 323 } else if (interval.spillSlot() != null) { 324 interval.assignLocation(interval.spillSlot()); 325 } else { 326 AllocatableValue slot = allocateSpillSlot(interval); 327 interval.setSpillSlot(slot); 328 interval.assignLocation(slot); 329 } 330 } 331 332 /** 333 * Returns a new spill slot or a cached entry if there is already one for the 334 * {@linkplain TraceInterval#operand variable}. 335 */ 336 private AllocatableValue allocateSpillSlot(TraceInterval interval) { 337 int variableIndex = LIRValueUtil.asVariable(interval.splitParent().operand).index; 338 OptionValues options = getOptions(); 339 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) { 340 AllocatableValue cachedStackSlot = cachedStackSlots[variableIndex]; 341 if (cachedStackSlot != null) { 342 TraceRegisterAllocationPhase.globalStackSlots.increment(); 343 assert cachedStackSlot.getValueKind().equals(interval.kind()) : "CachedStackSlot: kind mismatch? " + interval.kind() + " vs. " + cachedStackSlot.getValueKind(); 344 return cachedStackSlot; 345 } 346 } 347 VirtualStackSlot slot = frameMapBuilder.allocateSpillSlot(interval.kind()); 348 if (TraceRegisterAllocationPhase.Options.TraceRACacheStackSlots.getValue(options)) { 349 cachedStackSlots[variableIndex] = slot; 350 } 351 TraceRegisterAllocationPhase.allocatedStackSlots.increment(); 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 372 boolean isBlockEnd(int opId) { 373 boolean isBlockBegin = isBlockBegin(opId + 2); 374 assert isBlockBegin == (instructionForId(opId & (~1)) instanceof BlockEndOp); 375 return isBlockBegin; 376 } 377 378 boolean coversBlockBegin(int opId1, int opId2) { 379 return blockForId(opId1) != blockForId(opId2); 380 } 381 382 /** 383 * Determines if an {@link LIRInstruction} destroys all caller saved registers. 384 * 385 * @param opId an instruction {@linkplain LIRInstruction#id id} 386 * @return {@code true} if the instruction denoted by {@code id} destroys all caller saved 387 * registers. 388 */ 389 boolean hasCall(int opId) { 390 assert isEven(opId) : "opId not even"; 391 return instructionForId(opId).destroysCallerSavedRegisters(); 392 } 393 394 public boolean isProcessed(Value operand) { 395 return !isRegister(operand) || attributes(asRegister(operand)).isAllocatable(); 396 } 397 398 // * Phase 5: actual register allocation 399 400 private TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) { 401 TraceInterval newFirst = first; 402 if (prev != null) { 403 prev.next = interval; 404 } else { 405 newFirst = interval; 406 } 407 return newFirst; 408 } 409 410 TraceInterval createUnhandledListByFrom(IntervalPredicate isList1) { 411 assert isSortedByFrom(sortedIntervals) : "interval list is not sorted"; 412 return createUnhandledList(isList1); 413 } 414 415 TraceInterval createUnhandledListBySpillPos(IntervalPredicate isList1) { 416 assert isSortedBySpillPos(sortedIntervals) : "interval list is not sorted"; 417 return createUnhandledList(isList1); 418 } 419 420 private TraceInterval createUnhandledList(IntervalPredicate isList1) { 421 422 TraceInterval list1 = TraceInterval.EndMarker; 423 424 TraceInterval list1Prev = null; 425 TraceInterval v; 426 427 int n = sortedIntervals.length; 428 for (int i = 0; i < n; i++) { 429 v = sortedIntervals[i]; 430 if (v == null) { 431 continue; 432 } 433 434 if (isList1.apply(v)) { 435 list1 = addToList(list1, list1Prev, v); 436 list1Prev = v; 437 } 438 } 439 440 if (list1Prev != null) { 441 list1Prev.next = TraceInterval.EndMarker; 442 } 443 444 assert list1Prev == null || list1Prev.next == TraceInterval.EndMarker : "linear list ends not with sentinel"; 445 446 return list1; 447 } 448 449 private FixedInterval addToList(FixedInterval first, FixedInterval prev, FixedInterval interval) { 450 FixedInterval newFirst = first; 451 if (prev != null) { 452 prev.next = interval; 453 } else { 454 newFirst = interval; 455 } 456 return newFirst; 457 } 458 459 FixedInterval createFixedUnhandledList() { 460 assert isSortedByFrom(sortedFixedIntervals) : "interval list is not sorted"; 461 462 FixedInterval list1 = FixedInterval.EndMarker; 463 464 FixedInterval list1Prev = null; 465 FixedInterval v; 466 467 int n = sortedFixedIntervals.length; 468 for (int i = 0; i < n; i++) { 469 v = sortedFixedIntervals[i]; 470 if (v == null) { 471 continue; 472 } 473 474 v.rewindRange(); 475 list1 = addToList(list1, list1Prev, v); 476 list1Prev = v; 477 } 478 479 if (list1Prev != null) { 480 list1Prev.next = FixedInterval.EndMarker; 481 } 482 483 assert list1Prev == null || list1Prev.next == FixedInterval.EndMarker : "linear list ends not with sentinel"; 484 485 return list1; 486 } 487 488 // SORTING 489 490 protected void sortIntervalsBeforeAllocation() { 491 int sortedLen = 0; 492 for (TraceInterval interval : intervals()) { 493 if (interval != null) { 494 sortedLen++; 495 } 496 } 497 sortedIntervals = TraceLinearScanPhase.sortIntervalsBeforeAllocation(intervals(), new TraceInterval[sortedLen]); 498 } 499 500 protected void sortFixedIntervalsBeforeAllocation() { 501 int sortedLen = 0; 502 for (FixedInterval interval : fixedIntervals()) { 503 if (interval != null) { 504 sortedLen++; 505 } 506 } 507 sortedFixedIntervals = TraceLinearScanPhase.sortIntervalsBeforeAllocation(fixedIntervals(), new FixedInterval[sortedLen]); 508 } 509 510 void sortIntervalsAfterAllocation() { 511 if (hasDerivedIntervals()) { 512 // no intervals have been added during allocation, so sorted list is already up to 513 // date 514 return; 515 } 516 517 TraceInterval[] oldList = sortedIntervals; 518 TraceInterval[] newList = Arrays.copyOfRange(intervals(), firstDerivedIntervalIndex(), intervalsSize()); 519 int oldLen = oldList.length; 520 int newLen = newList.length; 521 522 // conventional sort-algorithm for new intervals 523 Arrays.sort(newList, (TraceInterval a, TraceInterval b) -> a.from() - b.from()); 524 525 // merge old and new list (both already sorted) into one combined list 526 TraceInterval[] combinedList = new TraceInterval[oldLen + newLen]; 527 int oldIdx = 0; 528 int newIdx = 0; 529 530 while (oldIdx + newIdx < combinedList.length) { 531 if (newIdx >= newLen || (oldIdx < oldLen && oldList[oldIdx].from() <= newList[newIdx].from())) { 532 combinedList[oldIdx + newIdx] = oldList[oldIdx]; 533 oldIdx++; 534 } else { 535 combinedList[oldIdx + newIdx] = newList[newIdx]; 536 newIdx++; 537 } 538 } 539 540 sortedIntervals = combinedList; 541 } 542 543 void sortIntervalsBySpillPos() { 544 // TODO (JE): better algorithm? 545 // conventional sort-algorithm for new intervals 546 Arrays.sort(sortedIntervals, (TraceInterval a, TraceInterval b) -> a.spillDefinitionPos() - b.spillDefinitionPos()); 547 } 548 549 // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode 550 // instead of returning null 551 public TraceInterval splitChildAtOpId(TraceInterval interval, int opId, LIRInstruction.OperandMode mode) { 552 TraceInterval result = interval.getSplitChildAtOpId(opId, mode); 553 554 if (result != null) { 555 if (Debug.isLogEnabled()) { 556 Debug.log("Split child at pos %d of interval %s is %s", opId, interval, result); 557 } 558 return result; 559 } 560 throw new GraalError("LinearScan: interval is null"); 561 } 562 563 AllocatableValue canonicalSpillOpr(TraceInterval interval) { 564 assert interval.spillSlot() != null : "canonical spill slot not set"; 565 return interval.spillSlot(); 566 } 567 568 boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) { 569 TraceInterval interval = intervalFor(operand); 570 assert interval != null : "interval must exist"; 571 572 if (opId != -1) { 573 /* 574 * Operands are not changed when an interval is split during allocation, so search 575 * the right interval here. 576 */ 577 interval = splitChildAtOpId(interval, opId, mode); 578 } 579 580 return isIllegal(interval.location()) && interval.canMaterialize(); 581 } 582 583 boolean isCallerSave(Value operand) { 584 return attributes(asRegister(operand)).isCallerSave(); 585 } 586 587 @SuppressWarnings("try") 588 protected void allocate(TargetDescription target, LIRGenerationResult lirGenRes, TraceAllocationContext traceContext) { 589 MoveFactory spillMoveFactory = traceContext.spillMoveFactory; 590 RegisterAllocationConfig registerAllocationConfig = traceContext.registerAllocationConfig; 591 /* 592 * This is the point to enable debug logging for the whole register allocation. 593 */ 594 try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { 595 TRACE_LINEAR_SCAN_LIFETIME_ANALYSIS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false); 596 597 try (Scope s = Debug.scope("AfterLifetimeAnalysis", this)) { 598 599 printLir("After instruction numbering"); 600 printIntervals("Before register allocation"); 601 602 sortIntervalsBeforeAllocation(); 603 sortFixedIntervalsBeforeAllocation(); 604 605 TRACE_LINEAR_SCAN_REGISTER_ALLOCATION_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false); 606 printIntervals("After register allocation"); 607 608 // resolve intra-trace data-flow 609 TRACE_LINEAR_SCAN_RESOLVE_DATA_FLOW_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this); 610 611 // eliminate spill moves 612 OptionValues options = getOptions(); 613 if (Options.LIROptTraceRAEliminateSpillMoves.getValue(options)) { 614 TRACE_LINEAR_SCAN_ELIMINATE_SPILL_MOVE_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this); 615 } 616 617 TRACE_LINEAR_SCAN_ASSIGN_LOCATIONS_PHASE.apply(target, lirGenRes, trace, spillMoveFactory, registerAllocationConfig, traceBuilderResult, this, false); 618 619 if (DetailedAsserts.getValue(options)) { 620 verifyIntervals(); 621 } 622 } catch (Throwable e) { 623 throw Debug.handle(e); 624 } 625 } 626 } 627 628 public void printLir(String label) { 629 if (Debug.isDumpEnabled(Debug.DETAILED_LEVEL)) { 630 Debug.dump(Debug.DETAILED_LEVEL, sortedBlocks(), "%s (Trace%d)", label, trace.getId()); 631 } 632 } 633 634 boolean verify() { 635 // (check that all intervals have a correct register and that no registers are 636 // overwritten) 637 verifyIntervals(); 638 639 verifyRegisters(); 640 641 Debug.log("no errors found"); 642 643 return true; 644 } 645 646 @SuppressWarnings("try") 647 private void verifyRegisters() { 648 // Enable this logging to get output for the verification process. 649 try (Indent indent = Debug.logAndIndent("verifying register allocation")) { 650 RegisterVerifier verifier = new RegisterVerifier(this); 651 verifier.verify(blockAt(0)); 652 } 653 } 654 655 @SuppressWarnings("try") 656 protected void verifyIntervals() { 657 try (Indent indent = Debug.logAndIndent("verifying intervals")) { 658 int len = intervalsSize(); 659 660 for (int i = 0; i < len; i++) { 661 final TraceInterval i1 = intervals()[i]; 662 if (i1 == null) { 663 continue; 664 } 665 666 i1.checkSplitChildren(); 667 668 if (i1.operandNumber != i) { 669 Debug.log("Interval %d is on position %d in list", i1.operandNumber, i); 670 Debug.log(i1.logString()); 671 throw new GraalError(""); 672 } 673 674 if (isVariable(i1.operand) && i1.kind().equals(LIRKind.Illegal)) { 675 Debug.log("Interval %d has no type assigned", i1.operandNumber); 676 Debug.log(i1.logString()); 677 throw new GraalError(""); 678 } 679 680 if (i1.location() == null) { 681 Debug.log("Interval %d has no register assigned", i1.operandNumber); 682 Debug.log(i1.logString()); 683 throw new GraalError(""); 684 } 685 686 if (i1.isEmpty()) { 687 Debug.log("Interval %d has no Range", i1.operandNumber); 688 Debug.log(i1.logString()); 689 throw new GraalError(""); 690 } 691 692 if (i1.from() >= i1.to()) { 693 Debug.log("Interval %d has zero length range", i1.operandNumber); 694 Debug.log(i1.logString()); 695 throw new GraalError(""); 696 } 697 698 // special intervals that are created in MoveResolver 699 // . ignore them because the range information has no meaning there 700 if (i1.from() == 1 && i1.to() == 2) { 701 continue; 702 } 703 // check any intervals 704 for (int j = i + 1; j < len; j++) { 705 final TraceInterval i2 = intervals()[j]; 706 if (i2 == null) { 707 continue; 708 } 709 710 // special intervals that are created in MoveResolver 711 // . ignore them because the range information has no meaning there 712 if (i2.from() == 1 && i2.to() == 2) { 713 continue; 714 } 715 Value l1 = i1.location(); 716 Value l2 = i2.location(); 717 boolean intersects = i1.intersects(i2); 718 if (intersects && !isIllegal(l1) && (l1.equals(l2))) { 719 throw GraalError.shouldNotReachHere(String.format("Intervals %s and %s overlap and have the same register assigned\n%s\n%s", i1, i2, i1.logString(), i2.logString())); 720 } 721 } 722 // check fixed intervals 723 for (FixedInterval i2 : fixedIntervals()) { 724 if (i2 == null) { 725 continue; 726 } 727 728 Value l1 = i1.location(); 729 Value l2 = i2.location(); 730 boolean intersects = i2.intersects(i1); 731 if (intersects && !isIllegal(l1) && (l1.equals(l2))) { 732 throw GraalError.shouldNotReachHere(String.format("Intervals %s and %s overlap and have the same register assigned\n%s\n%s", i1, i2, i1.logString(), i2.logString())); 733 } 734 } 735 } 736 } 737 } 738 739 class CheckConsumer implements ValueConsumer { 740 741 boolean ok; 742 FixedInterval curInterval; 743 744 @Override 745 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { 746 if (isRegister(operand)) { 747 if (fixedIntervalFor(asRegisterValue(operand)) == curInterval) { 748 ok = true; 749 } 750 } 751 } 752 } 753 754 @SuppressWarnings("try") 755 void verifyNoOopsInFixedIntervals() { 756 try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) { 757 CheckConsumer checkConsumer = new CheckConsumer(); 758 759 TraceInterval otherIntervals; 760 FixedInterval fixedInts = createFixedUnhandledList(); 761 // to ensure a walking until the last instruction id, add a dummy interval 762 // with a high operation id 763 otherIntervals = new TraceInterval(Value.ILLEGAL, -1, getOptions()); 764 otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1); 765 TraceIntervalWalker iw = new TraceIntervalWalker(this, fixedInts, otherIntervals); 766 767 for (AbstractBlockBase<?> block : sortedBlocks()) { 768 ArrayList<LIRInstruction> instructions = getLIR().getLIRforBlock(block); 769 770 for (int j = 0; j < instructions.size(); j++) { 771 LIRInstruction op = instructions.get(j); 772 773 if (op.hasState()) { 774 iw.walkBefore(op.id()); 775 boolean checkLive = true; 776 777 /* 778 * Make sure none of the fixed registers is live across an oopmap since 779 * we can't handle that correctly. 780 */ 781 if (checkLive) { 782 for (FixedInterval interval = iw.activeFixedList.getFixed(); interval != FixedInterval.EndMarker; interval = interval.next) { 783 if (interval.to() > op.id() + 1) { 784 /* 785 * This interval is live out of this op so make sure that 786 * this interval represents some value that's referenced by 787 * this op either as an input or output. 788 */ 789 checkConsumer.curInterval = interval; 790 checkConsumer.ok = false; 791 792 op.visitEachInput(checkConsumer); 793 op.visitEachAlive(checkConsumer); 794 op.visitEachTemp(checkConsumer); 795 op.visitEachOutput(checkConsumer); 796 797 assert checkConsumer.ok : "fixed intervals should never be live across an oopmap point"; 798 } 799 } 800 } 801 } 802 } 803 } 804 } 805 } 806 807 public LIR getLIR() { 808 return res.getLIR(); 809 } 810 811 public FrameMapBuilder getFrameMapBuilder() { 812 return frameMapBuilder; 813 } 814 815 public AbstractBlockBase<?>[] sortedBlocks() { 816 return trace.getBlocks(); 817 } 818 819 public RegisterArray getRegisters() { 820 return registers; 821 } 822 823 public RegisterAllocationConfig getRegisterAllocationConfig() { 824 return regAllocConfig; 825 } 826 827 public boolean callKillsRegisters() { 828 return regAllocConfig.getRegisterConfig().areAllAllocatableRegistersCallerSaved(); 829 } 830 831 boolean neverSpillConstants() { 832 return neverSpillConstants; 833 } 834 835 // IntervalData 836 837 private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT = 1; 838 839 /** 840 * The index of the first entry in {@link #intervals} for a 841 * {@linkplain #createDerivedInterval(TraceInterval) derived interval}. 842 */ 843 private int firstDerivedIntervalIndex = -1; 844 845 /** 846 * @see #fixedIntervals() 847 */ 848 private final FixedInterval[] fixedIntervals; 849 850 /** 851 * @see #intervals() 852 */ 853 private TraceInterval[] intervals; 854 855 /** 856 * The number of valid entries in {@link #intervals}. 857 */ 858 private int intervalsSize; 859 860 /** 861 * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries 862 * should be retrieved with {@link #instructionForId(int)} as the id is not simply an index 863 * into this array. 864 */ 865 private LIRInstruction[] opIdToInstructionMap; 866 867 /** 868 * Map from an instruction {@linkplain LIRInstruction#id id} to the 869 * {@linkplain AbstractBlockBase block} containing the instruction. Entries should be 870 * retrieved with {@link #blockForId(int)} as the id is not simply an index into this array. 871 */ 872 private AbstractBlockBase<?>[] opIdToBlockMap; 873 874 /** 875 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. 876 */ 877 TraceInterval[] intervals() { 878 return intervals; 879 } 880 881 /** 882 * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals. 883 */ 884 FixedInterval[] fixedIntervals() { 885 return fixedIntervals; 886 } 887 888 void initIntervals() { 889 intervalsSize = operandSize(); 890 intervals = new TraceInterval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)]; 891 } 892 893 /** 894 * Creates a new fixed interval. 895 * 896 * @param reg the operand for the interval 897 * @return the created interval 898 */ 899 private FixedInterval createFixedInterval(RegisterValue reg) { 900 FixedInterval interval = new FixedInterval(reg); 901 int operandNumber = reg.getRegister().number; 902 assert fixedIntervals[operandNumber] == null; 903 fixedIntervals[operandNumber] = interval; 904 return interval; 905 } 906 907 /** 908 * Creates a new interval. 909 * 910 * @param operand the operand for the interval 911 * @return the created interval 912 */ 913 private TraceInterval createInterval(AllocatableValue operand) { 914 assert isLegal(operand); 915 int operandNumber = operandNumber(operand); 916 TraceInterval interval = new TraceInterval(operand, operandNumber, getOptions()); 917 assert operandNumber < intervalsSize; 918 assert intervals[operandNumber] == null; 919 intervals[operandNumber] = interval; 920 return interval; 921 } 922 923 /** 924 * Creates an interval as a result of splitting or spilling another interval. 925 * 926 * @param source an interval being split of spilled 927 * @return a new interval derived from {@code source} 928 */ 929 TraceInterval createDerivedInterval(TraceInterval source) { 930 if (firstDerivedIntervalIndex == -1) { 931 firstDerivedIntervalIndex = intervalsSize; 932 } 933 if (intervalsSize == intervals.length) { 934 intervals = Arrays.copyOf(intervals, intervals.length + (intervals.length >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT) + 1); 935 } 936 // increments intervalsSize 937 Variable variable = createVariable(source.kind()); 938 939 assert intervalsSize <= intervals.length; 940 941 TraceInterval interval = createInterval(variable); 942 assert intervals[intervalsSize - 1] == interval; 943 return interval; 944 } 945 946 /** 947 * Creates a new variable for a derived interval. Note that the variable is not 948 * {@linkplain LIR#numVariables() managed} so it must not be inserted into the {@link LIR}. 949 */ 950 private Variable createVariable(ValueKind<?> kind) { 951 return new Variable(kind, intervalsSize++); 952 } 953 954 boolean hasDerivedIntervals() { 955 return firstDerivedIntervalIndex != -1; 956 } 957 958 int firstDerivedIntervalIndex() { 959 return firstDerivedIntervalIndex; 960 } 961 962 public int intervalsSize() { 963 return intervalsSize; 964 } 965 966 FixedInterval fixedIntervalFor(RegisterValue reg) { 967 return fixedIntervals[reg.getRegister().number]; 968 } 969 970 FixedInterval getOrCreateFixedInterval(RegisterValue reg) { 971 FixedInterval ret = fixedIntervalFor(reg); 972 if (ret == null) { 973 return createFixedInterval(reg); 974 } else { 975 return ret; 976 } 977 } 978 979 TraceInterval intervalFor(Value operand) { 980 return intervalFor(operandNumber(operand)); 981 } 982 983 TraceInterval intervalFor(int operandNumber) { 984 assert operandNumber < intervalsSize; 985 return intervals[operandNumber]; 986 } 987 988 TraceInterval getOrCreateInterval(AllocatableValue operand) { 989 TraceInterval ret = intervalFor(operand); 990 if (ret == null) { 991 return createInterval(operand); 992 } else { 993 return ret; 994 } 995 } 996 997 void initOpIdMaps(int numInstructions) { 998 opIdToInstructionMap = new LIRInstruction[numInstructions]; 999 opIdToBlockMap = new AbstractBlockBase<?>[numInstructions]; 1000 } 1001 1002 void putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block) { 1003 opIdToInstructionMap[index] = op; 1004 opIdToBlockMap[index] = block; 1005 } 1006 1007 /** 1008 * Gets the highest instruction id allocated by this object. 1009 */ 1010 int maxOpId() { 1011 assert opIdToInstructionMap.length > 0 : "no operations"; 1012 return (opIdToInstructionMap.length - 1) << 1; 1013 } 1014 1015 /** 1016 * Converts an {@linkplain LIRInstruction#id instruction id} to an instruction index. All 1017 * LIR instructions in a method have an index one greater than their linear-scan order 1018 * predecessor with the first instruction having an index of 0. 1019 */ 1020 private int opIdToIndex(int opId) { 1021 return opId >> 1; 1022 } 1023 1024 /** 1025 * Retrieves the {@link LIRInstruction} based on its {@linkplain LIRInstruction#id id}. 1026 * 1027 * @param opId an instruction {@linkplain LIRInstruction#id id} 1028 * @return the instruction whose {@linkplain LIRInstruction#id} {@code == id} 1029 */ 1030 LIRInstruction instructionForId(int opId) { 1031 assert isEven(opId) : "opId not even"; 1032 LIRInstruction instr = opIdToInstructionMap[opIdToIndex(opId)]; 1033 assert instr.id() == opId; 1034 return instr; 1035 } 1036 1037 /** 1038 * Gets the block containing a given instruction. 1039 * 1040 * @param opId an instruction {@linkplain LIRInstruction#id id} 1041 * @return the block containing the instruction denoted by {@code opId} 1042 */ 1043 AbstractBlockBase<?> blockForId(int opId) { 1044 assert opIdToBlockMap.length > 0 && opId >= 0 && opId <= maxOpId() + 1 : "opId out of range: " + opId; 1045 return opIdToBlockMap[opIdToIndex(opId)]; 1046 } 1047 1048 @SuppressWarnings("try") 1049 public void printIntervals(String label) { 1050 if (Debug.isDumpEnabled(Debug.DETAILED_LEVEL)) { 1051 if (Debug.isLogEnabled()) { 1052 try (Indent indent = Debug.logAndIndent("intervals %s", label)) { 1053 for (FixedInterval interval : fixedIntervals) { 1054 if (interval != null) { 1055 Debug.log("%s", interval.logString()); 1056 } 1057 } 1058 1059 for (TraceInterval interval : intervals) { 1060 if (interval != null) { 1061 Debug.log("%s", interval.logString()); 1062 } 1063 } 1064 1065 try (Indent indent2 = Debug.logAndIndent("Basic Blocks")) { 1066 for (AbstractBlockBase<?> block : trace.getBlocks()) { 1067 Debug.log("B%d [%d, %d, %s] ", block.getId(), getFirstLirInstructionId(block), getLastLirInstructionId(block), block.getLoop()); 1068 } 1069 } 1070 } 1071 } 1072 Debug.dump(Debug.DETAILED_LEVEL, this, "%s (Trace%d)", label, trace.getId()); 1073 } 1074 } 1075 1076 @Override 1077 public void visitIntervals(IntervalVisitor visitor) { 1078 for (FixedInterval interval : fixedIntervals) { 1079 if (interval != null) { 1080 printFixedInterval(interval, visitor); 1081 } 1082 } 1083 for (TraceInterval interval : intervals) { 1084 if (interval != null) { 1085 printInterval(interval, visitor); 1086 } 1087 } 1088 } 1089 1090 boolean hasInterTracePredecessor(AbstractBlockBase<?> block) { 1091 return TraceUtil.hasInterTracePredecessor(traceBuilderResult, trace, block); 1092 } 1093 1094 boolean hasInterTraceSuccessor(AbstractBlockBase<?> block) { 1095 return TraceUtil.hasInterTraceSuccessor(traceBuilderResult, trace, block); 1096 } 1097 1098 } 1099 1100 public static boolean verifyEquals(TraceLinearScan a, TraceLinearScan b) { 1101 assert compareFixed(a.fixedIntervals(), b.fixedIntervals()); 1102 assert compareIntervals(a.intervals(), b.intervals()); 1103 return true; 1104 } 1105 1106 private static boolean compareIntervals(TraceInterval[] a, TraceInterval[] b) { 1107 for (int i = 0; i < Math.max(a.length, b.length); i++) { 1108 if (i >= a.length) { 1109 assert b[i] == null : "missing a interval: " + i + " b: " + b[i]; 1110 continue; 1111 } 1112 if (i >= b.length) { 1113 assert a[i] == null : "missing b interval: " + i + " a: " + a[i]; 1114 continue; 1115 } 1116 compareInterval(a[i], b[i]); 1117 } 1118 return true; 1119 } 1120 1121 private static void compareInterval(TraceInterval a, TraceInterval b) { 1122 if (a == null) { 1123 assert b == null : "First interval is null but second is: " + b; 1124 return; 1125 } 1126 assert b != null : "Second interval is null but forst is: " + a; 1127 assert a.operand.equals(b.operand) : "Operand mismatch: " + a + " vs. " + b; 1128 assert a.from() == b.from() : "From mismatch: " + a + " vs. " + b; 1129 assert a.to() == b.to() : "To mismatch: " + a + " vs. " + b; 1130 assert verifyIntervalsEquals(a, b); 1131 } 1132 1133 private static boolean verifyIntervalsEquals(TraceInterval a, TraceInterval b) { 1134 for (int i = 0; i < Math.max(a.numUsePos(), b.numUsePos()); i++) { 1135 assert i < a.numUsePos() : "missing a usepos: " + i + " b: " + b; 1136 assert i < b.numUsePos() : "missing b usepos: " + i + " a: " + a; 1137 int aPos = a.getUsePos(i); 1138 int bPos = b.getUsePos(i); 1139 assert aPos == bPos : "Use Positions differ: " + aPos + " vs. " + bPos; 1140 RegisterPriority aReg = a.getUsePosRegisterPriority(i); 1141 RegisterPriority bReg = b.getUsePosRegisterPriority(i); 1142 assert aReg == bReg : "Register priority differ: " + aReg + " vs. " + bReg; 1143 } 1144 return true; 1145 } 1146 1147 private static boolean compareFixed(FixedInterval[] a, FixedInterval[] b) { 1148 for (int i = 0; i < Math.max(a.length, b.length); i++) { 1149 if (i >= a.length) { 1150 assert b[i] == null : "missing a interval: " + i + " b: " + b[i]; 1151 continue; 1152 } 1153 if (i >= b.length) { 1154 assert a[i] == null : "missing b interval: " + i + " a: " + a[i]; 1155 continue; 1156 } 1157 compareFixedInterval(a[i], b[i]); 1158 } 1159 return true; 1160 } 1161 1162 private static void compareFixedInterval(FixedInterval a, FixedInterval b) { 1163 if (a == null) { 1164 assert b == null || isEmptyInterval(b) : "First interval is null but second is: " + b; 1165 return; 1166 } 1167 if (b == null) { 1168 assert isEmptyInterval(a) : "Second interval is null but first is: " + a; 1169 return; 1170 } 1171 assert a.operand.equals(b.operand) : "Operand mismatch: " + a + " vs. " + b; 1172 assert a.from() == b.from() : "From mismatch: " + a + " vs. " + b; 1173 assert a.to() == b.to() : "To mismatch: " + a + " vs. " + b; 1174 assert verifyFixeEquas(a, b); 1175 } 1176 1177 private static boolean verifyFixeEquas(FixedInterval a, FixedInterval b) { 1178 a.rewindRange(); 1179 b.rewindRange(); 1180 while (!a.currentAtEnd()) { 1181 assert !b.currentAtEnd() : "Fixed range mismatch: " + a + " vs. " + b; 1182 assert a.currentFrom() == b.currentFrom() : "From range mismatch: " + a + " vs. " + b + " from: " + a.currentFrom() + " vs. " + b.currentFrom(); 1183 assert a.currentTo() == b.currentTo() : "To range mismatch: " + a + " vs. " + b + " from: " + a.currentTo() + " vs. " + b.currentTo(); 1184 a.nextRange(); 1185 b.nextRange(); 1186 } 1187 assert b.currentAtEnd() : "Fixed range mismatch: " + a + " vs. " + b; 1188 return true; 1189 } 1190 1191 private static boolean isEmptyInterval(FixedInterval fixed) { 1192 return fixed.from() == -1 && fixed.to() == 0; 1193 } 1194 1195 private static void printFixedInterval(FixedInterval interval, IntervalVisitor visitor) { 1196 Value hint = null; 1197 AllocatableValue operand = interval.operand; 1198 String type = "fixed"; 1199 visitor.visitIntervalStart(operand, operand, operand, hint, type); 1200 1201 // print ranges 1202 for (FixedRange range = interval.first(); range != FixedRange.EndMarker; range = range.next) { 1203 visitor.visitRange(range.from, range.to); 1204 } 1205 1206 // no use positions 1207 1208 visitor.visitIntervalEnd("NOT_SUPPORTED"); 1209 1210 } 1211 1212 private static void printInterval(TraceInterval interval, IntervalVisitor visitor) { 1213 Value hint = interval.locationHint(false) != null ? interval.locationHint(false).location() : null; 1214 AllocatableValue operand = interval.operand; 1215 String type = isRegister(operand) ? "fixed" : operand.getValueKind().getPlatformKind().toString(); 1216 visitor.visitIntervalStart(interval.splitParent().operand, operand, interval.location(), hint, type); 1217 1218 // print ranges 1219 visitor.visitRange(interval.from(), interval.to()); 1220 1221 // print use positions 1222 int prev = -1; 1223 for (int i = interval.numUsePos() - 1; i >= 0; --i) { 1224 assert prev < interval.getUsePos(i) : "use positions not sorted"; 1225 visitor.visitUsePos(interval.getUsePos(i), interval.getUsePosRegisterPriority(i)); 1226 prev = interval.getUsePos(i); 1227 } 1228 1229 visitor.visitIntervalEnd(interval.spillState()); 1230 } 1231} 1232