1 /*
   2  * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.lir.alloc.trace.lsra;
  26 
  27 import static jdk.vm.ci.code.CodeUtil.isOdd;
  28 import static jdk.vm.ci.code.ValueUtil.asRegister;
  29 import static jdk.vm.ci.code.ValueUtil.isRegister;
  30 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
  31 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
  32 
  33 import java.util.ArrayList;
  34 import java.util.Arrays;
  35 import java.util.BitSet;
  36 
  37 import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
  38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  39 import org.graalvm.compiler.core.common.util.Util;
  40 import org.graalvm.compiler.debug.DebugContext;
  41 import org.graalvm.compiler.debug.GraalError;
  42 import org.graalvm.compiler.debug.Indent;
  43 import org.graalvm.compiler.lir.LIRInstruction;
  44 import org.graalvm.compiler.lir.LIRValueUtil;
  45 import org.graalvm.compiler.lir.StandardOp.BlockEndOp;
  46 import org.graalvm.compiler.lir.StandardOp.LabelOp;
  47 import org.graalvm.compiler.lir.StandardOp.ValueMoveOp;
  48 import org.graalvm.compiler.lir.alloc.OutOfRegistersException;
  49 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.RegisterPriority;
  50 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.SpillState;
  51 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceInterval.State;
  52 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
  53 import org.graalvm.compiler.lir.ssa.SSAUtil;
  54 
  55 import jdk.vm.ci.code.Register;
  56 import jdk.vm.ci.meta.Value;
  57 
  58 /**
  59  */
  60 final class TraceLinearScanWalker {
  61 
  62     /**
  63      * Adds an interval to a list sorted by {@linkplain FixedInterval#currentFrom() current from}
  64      * positions.
  65      *
  66      * @param list the list
  67      * @param interval the interval to add
  68      * @return the new head of the list
  69      */
  70     private static FixedInterval addToListSortedByCurrentFromPositions(FixedInterval list, FixedInterval interval) {
  71         FixedInterval prev = null;
  72         FixedInterval cur = list;
  73         while (cur.currentFrom() < interval.currentFrom()) {
  74             prev = cur;
  75             cur = cur.next;
  76         }
  77         FixedInterval result = list;
  78         if (prev == null) {
  79             // add to head of list
  80             result = interval;
  81         } else {
  82             // add before 'cur'
  83             prev.next = interval;
  84         }
  85         interval.next = cur;
  86         return result;
  87     }
  88 
  89     /**
  90      * Adds an interval to a list sorted by {@linkplain TraceInterval#from() current from}
  91      * positions.
  92      *
  93      * @param list the list
  94      * @param interval the interval to add
  95      * @return the new head of the list
  96      */
  97     private static TraceInterval addToListSortedByFromPositions(TraceInterval list, TraceInterval interval) {
  98         TraceInterval prev = null;
  99         TraceInterval cur = list;
 100         while (cur.from() < interval.from()) {
 101             prev = cur;
 102             cur = cur.next;
 103         }
 104         TraceInterval result = list;
 105         if (prev == null) {
 106             // add to head of list
 107             result = interval;
 108         } else {
 109             // add before 'cur'
 110             prev.next = interval;
 111         }
 112         interval.next = cur;
 113         return result;
 114     }
 115 
 116     /**
 117      * Adds an interval to a list sorted by {@linkplain TraceInterval#from() start} positions and
 118      * {@linkplain TraceInterval#firstUsage(RegisterPriority) first usage} positions.
 119      *
 120      * @param list the list
 121      * @param interval the interval to add
 122      * @return the new head of the list
 123      */
 124     private static TraceInterval addToListSortedByStartAndUsePositions(TraceInterval list, TraceInterval interval) {
 125         TraceInterval newHead = list;
 126         TraceInterval prev = null;
 127         TraceInterval cur = newHead;
 128         while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) {
 129             prev = cur;
 130             cur = cur.next;
 131         }
 132         if (prev == null) {
 133             newHead = interval;
 134         } else {
 135             prev.next = interval;
 136         }
 137         interval.next = cur;
 138         return newHead;
 139     }
 140 
 141     /**
 142      * Removes an interval from a list.
 143      *
 144      * @param list the list
 145      * @param interval the interval to remove
 146      * @return the new head of the list
 147      */
 148     private static TraceInterval removeAny(TraceInterval list, TraceInterval interval) {
 149         TraceInterval newHead = list;
 150         TraceInterval prev = null;
 151         TraceInterval cur = newHead;
 152         while (cur != interval) {
 153             assert cur != null && cur != TraceInterval.EndMarker : "interval has not been found in list: " + interval;
 154             prev = cur;
 155             cur = cur.next;
 156         }
 157         if (prev == null) {
 158             newHead = cur.next;
 159         } else {
 160             prev.next = cur.next;
 161         }
 162         return newHead;
 163     }
 164 
 165     private Register[] availableRegs;
 166 
 167     private final int[] usePos;
 168     private final int[] blockPos;
 169     private final BitSet isInMemory;
 170 
 171     private final ArrayList<TraceInterval>[] spillIntervals;
 172 
 173     private TraceLocalMoveResolver moveResolver; // for ordering spill moves
 174 
 175     private int minReg;
 176 
 177     private int maxReg;
 178 
 179     private final TraceLinearScan allocator;
 180     private final DebugContext debug;
 181 
 182     /**
 183      * Sorted list of intervals, not live before the current position.
 184      */
 185     private TraceInterval unhandledAnyList;
 186 
 187     /**
 188      * Sorted list of intervals, live at the current position.
 189      */
 190     private TraceInterval activeAnyList;
 191 
 192     private FixedInterval activeFixedList;
 193 
 194     /**
 195      * Sorted list of intervals in a life time hole at the current position.
 196      */
 197     private FixedInterval inactiveFixedList;
 198 
 199     /**
 200      * The current position (intercept point through the intervals).
 201      */
 202     private int currentPosition;
 203 
 204     /**
 205      * Only 10% of the lists in {@link #spillIntervals} are actually used. But when they are used,
 206      * they can grow quite long. The maximum length observed was 45 (all numbers taken from a
 207      * bootstrap run of Graal). Therefore, we initialize {@link #spillIntervals} with this marker
 208      * value, and allocate a "real" list only on demand in {@link #setUsePos}.
 209      */
 210     private static final ArrayList<TraceInterval> EMPTY_LIST = new ArrayList<>(0);
 211 
 212     // accessors mapped to same functions in class LinearScan
 213     private int blockCount() {
 214         return allocator.blockCount();
 215     }
 216 
 217     private AbstractBlockBase<?> blockAt(int idx) {
 218         return allocator.blockAt(idx);
 219     }
 220 
 221     @SuppressWarnings("unused")
 222     private AbstractBlockBase<?> blockOfOpWithId(int opId) {
 223         return allocator.blockForId(opId);
 224     }
 225 
 226     TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
 227         this.allocator = allocator;
 228         this.debug = allocator.getDebug();
 229 
 230         unhandledAnyList = unhandledAnyFirst;
 231         activeAnyList = TraceInterval.EndMarker;
 232         activeFixedList = FixedInterval.EndMarker;
 233         // we don't need a separate unhandled list for fixed.
 234         inactiveFixedList = unhandledFixedFirst;
 235         currentPosition = -1;
 236 
 237         moveResolver = allocator.createMoveResolver();
 238         int numRegs = allocator.getRegisters().size();
 239         spillIntervals = Util.uncheckedCast(new ArrayList<?>[numRegs]);
 240         for (int i = 0; i < numRegs; i++) {
 241             spillIntervals[i] = EMPTY_LIST;
 242         }
 243         usePos = new int[numRegs];
 244         blockPos = new int[numRegs];
 245         isInMemory = new BitSet(numRegs);
 246     }
 247 
 248     private void initUseLists(boolean onlyProcessUsePos) {
 249         for (Register register : availableRegs) {
 250             int i = register.number;
 251             usePos[i] = Integer.MAX_VALUE;
 252 
 253             if (!onlyProcessUsePos) {
 254                 blockPos[i] = Integer.MAX_VALUE;
 255                 spillIntervals[i].clear();
 256                 isInMemory.clear(i);
 257             }
 258         }
 259     }
 260 
 261     private int maxRegisterNumber() {
 262         return maxReg;
 263     }
 264 
 265     private int minRegisterNumber() {
 266         return minReg;
 267     }
 268 
 269     private boolean isRegisterInRange(int reg) {
 270         return reg >= minRegisterNumber() && reg <= maxRegisterNumber();
 271     }
 272 
 273     private void excludeFromUse(IntervalHint i) {
 274         Value location = i.location();
 275         int i1 = asRegister(location).number;
 276         if (isRegisterInRange(i1)) {
 277             usePos[i1] = 0;
 278         }
 279     }
 280 
 281     private void setUsePos(TraceInterval interval, int usePos, boolean onlyProcessUsePos) {
 282         if (usePos != -1) {
 283             assert usePos != 0 : "must use excludeFromUse to set usePos to 0";
 284             int i = asRegister(interval.location()).number;
 285             if (isRegisterInRange(i)) {
 286                 if (this.usePos[i] > usePos) {
 287                     this.usePos[i] = usePos;
 288                 }
 289                 if (!onlyProcessUsePos) {
 290                     ArrayList<TraceInterval> list = spillIntervals[i];
 291                     if (list == EMPTY_LIST) {
 292                         list = new ArrayList<>(2);
 293                         spillIntervals[i] = list;
 294                     }
 295                     list.add(interval);
 296                     // set is in memory flag
 297                     if (interval.inMemoryAt(currentPosition)) {
 298                         isInMemory.set(i);
 299                     }
 300                 }
 301             }
 302         }
 303     }
 304 
 305     private void setUsePos(FixedInterval interval, int usePos, boolean onlyProcessUsePos) {
 306         assert onlyProcessUsePos;
 307         if (usePos != -1) {
 308             assert usePos != 0 : "must use excludeFromUse to set usePos to 0";
 309             int i = asRegister(interval.location()).number;
 310             if (isRegisterInRange(i)) {
 311                 if (this.usePos[i] > usePos) {
 312                     this.usePos[i] = usePos;
 313                 }
 314             }
 315         }
 316     }
 317 
 318     private void setBlockPos(IntervalHint i, int blockPos) {
 319         if (blockPos != -1) {
 320             int reg = asRegister(i.location()).number;
 321             if (isRegisterInRange(reg)) {
 322                 if (this.blockPos[reg] > blockPos) {
 323                     this.blockPos[reg] = blockPos;
 324                 }
 325                 if (usePos[reg] > blockPos) {
 326                     usePos[reg] = blockPos;
 327                 }
 328             }
 329         }
 330     }
 331 
 332     private void freeExcludeActiveFixed() {
 333         FixedInterval interval = activeFixedList;
 334         while (interval != FixedInterval.EndMarker) {
 335             assert isRegister(interval.location()) : "active interval must have a register assigned";
 336             excludeFromUse(interval);
 337             interval = interval.next;
 338         }
 339     }
 340 
 341     private void freeExcludeActiveAny() {
 342         TraceInterval interval = activeAnyList;
 343         while (interval != TraceInterval.EndMarker) {
 344             assert isRegister(interval.location()) : "active interval must have a register assigned";
 345             excludeFromUse(interval);
 346             interval = interval.next;
 347         }
 348     }
 349 
 350     private void freeCollectInactiveFixed(TraceInterval current) {
 351         FixedInterval interval = inactiveFixedList;
 352         while (interval != FixedInterval.EndMarker) {
 353             if (current.to() <= interval.from()) {
 354                 assert interval.intersectsAt(current) == -1 : "must not intersect";
 355                 setUsePos(interval, interval.from(), true);
 356             } else {
 357                 setUsePos(interval, interval.currentIntersectsAt(current), true);
 358             }
 359             interval = interval.next;
 360         }
 361     }
 362 
 363     private void spillExcludeActiveFixed() {
 364         FixedInterval interval = activeFixedList;
 365         while (interval != FixedInterval.EndMarker) {
 366             excludeFromUse(interval);
 367             interval = interval.next;
 368         }
 369     }
 370 
 371     private void spillBlockInactiveFixed(TraceInterval current) {
 372         FixedInterval interval = inactiveFixedList;
 373         while (interval != FixedInterval.EndMarker) {
 374             if (current.to() > interval.currentFrom()) {
 375                 setBlockPos(interval, interval.currentIntersectsAt(current));
 376             } else {
 377                 assert interval.currentIntersectsAt(current) == -1 : "invalid optimization: intervals intersect";
 378             }
 379 
 380             interval = interval.next;
 381         }
 382     }
 383 
 384     private void spillCollectActiveAny(RegisterPriority registerPriority) {
 385         TraceInterval interval = activeAnyList;
 386         while (interval != TraceInterval.EndMarker) {
 387             setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false);
 388             interval = interval.next;
 389         }
 390     }
 391 
 392     @SuppressWarnings("unused")
 393     private int insertIdAtBasicBlockBoundary(int opId) {
 394         assert allocator.isBlockBegin(opId) : "Not a block begin: " + opId;
 395         assert allocator.instructionForId(opId) instanceof LabelOp;
 396         assert allocator.instructionForId(opId - 2) instanceof BlockEndOp;
 397 
 398         AbstractBlockBase<?> toBlock = allocator.blockForId(opId);
 399         AbstractBlockBase<?> fromBlock = allocator.blockForId(opId - 2);
 400 
 401         if (fromBlock.getSuccessorCount() == 1) {
 402             // insert move in predecessor
 403             return opId - 2;
 404         }
 405         assert toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s->%s", fromBlock, toBlock);
 406         // insert move in successor
 407         return opId + 2;
 408     }
 409 
 410     private void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) {
 411         // output all moves here. When source and target are equal, the move is
 412         // optimized away later in assignRegNums
 413 
 414         int opId = (operandId + 1) & ~1;
 415         AbstractBlockBase<?> opBlock = allocator.blockForId(opId);
 416         assert opId > 0 && allocator.blockForId(opId - 2) == opBlock : "cannot insert move at block boundary";
 417 
 418         // calculate index of instruction inside instruction list of current block
 419         // the minimal index (for a block with no spill moves) can be calculated because the
 420         // numbering of instructions is known.
 421         // When the block already contains spill moves, the index must be increased until the
 422         // correct index is reached.
 423         ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(opBlock);
 424         int index = (opId - instructions.get(0).id()) >> 1;
 425         assert instructions.get(index).id() <= opId : "error in calculation";
 426 
 427         while (instructions.get(index).id() != opId) {
 428             index++;
 429             assert 0 <= index && index < instructions.size() : "index out of bounds";
 430         }
 431         assert 1 <= index && index < instructions.size() : "index out of bounds";
 432         assert instructions.get(index).id() == opId : "error in calculation";
 433 
 434         // insert new instruction before instruction at position index
 435         moveResolver.moveInsertPosition(instructions, index);
 436         moveResolver.addMapping(srcIt, dstIt);
 437     }
 438 
 439     private int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
 440         int fromBlockNr = minBlock.getLinearScanNumber();
 441         int toBlockNr = maxBlock.getLinearScanNumber();
 442 
 443         assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
 444         assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
 445         assert fromBlockNr < toBlockNr : "must cross block boundary";
 446 
 447         // Try to split at end of maxBlock. If this would be after
 448         // maxSplitPos, then use the begin of maxBlock
 449         int optimalSplitPos = allocator.getLastLirInstructionId(maxBlock) + 2;
 450         if (optimalSplitPos > maxSplitPos) {
 451             optimalSplitPos = allocator.getFirstLirInstructionId(maxBlock);
 452         }
 453 
 454         // minimal block probability
 455         double minProbability = maxBlock.probability();
 456         for (int i = toBlockNr - 1; i >= fromBlockNr; i--) {
 457             AbstractBlockBase<?> cur = blockAt(i);
 458 
 459             if (cur.probability() < minProbability) {
 460                 // Block with lower probability found. Split at the end of this block.
 461                 minProbability = cur.probability();
 462                 optimalSplitPos = allocator.getLastLirInstructionId(cur) + 2;
 463             }
 464         }
 465         assert optimalSplitPos > allocator.maxOpId() || allocator.isBlockBegin(optimalSplitPos) : "algorithm must move split pos to block boundary";
 466 
 467         return optimalSplitPos;
 468     }
 469 
 470     @SuppressWarnings({"unused"})
 471     private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
 472         int optimalSplitPos = findOptimalSplitPos0(minSplitPos, maxSplitPos);
 473         if (debug.isLogEnabled()) {
 474             debug.log("optimal split position: %d", optimalSplitPos);
 475         }
 476         return optimalSplitPos;
 477     }
 478 
 479     private int findOptimalSplitPos0(int minSplitPos, int maxSplitPos) {
 480         if (minSplitPos == maxSplitPos) {
 481             // trivial case, no optimization of split position possible
 482             if (debug.isLogEnabled()) {
 483                 debug.log("min-pos and max-pos are equal, no optimization possible");
 484             }
 485             return minSplitPos;
 486 
 487         }
 488         assert minSplitPos < maxSplitPos : "must be true then";
 489         assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
 490 
 491         // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
 492         // beginning of a block, then minSplitPos is also a possible split position.
 493         // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 ==
 494         // minSplitPos
 495         AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1);
 496 
 497         // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
 498         // when an interval ends at the end of the last block of the method
 499         // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
 500         // block at this opId)
 501         AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
 502 
 503         assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
 504         if (minBlock == maxBlock) {
 505             // split position cannot be moved to block boundary : so split as late as possible
 506             if (debug.isLogEnabled()) {
 507                 debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
 508             }
 509             return maxSplitPos;
 510 
 511         }
 512         // seach optimal block boundary between minSplitPos and maxSplitPos
 513         if (debug.isLogEnabled()) {
 514             debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
 515         }
 516 
 517         return findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
 518     }
 519 
 520     // split an interval at the optimal position between minSplitPos and
 521     // maxSplitPos in two parts:
 522     // 1) the left part has already a location assigned
 523     // 2) the right part is sorted into to the unhandled-list
 524     @SuppressWarnings("try")
 525     private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
 526 
 527         try (Indent indent = debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
 528 
 529             assert interval.from() < minSplitPos : "cannot split at start of interval";
 530             assert currentPosition < minSplitPos : "cannot split before current position";
 531             assert minSplitPos <= maxSplitPos : "invalid order";
 532             assert maxSplitPos <= interval.to() : "cannot split after end of interval";
 533 
 534             final int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, true);
 535 
 536             if (optimalSplitPos == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
 537                 // the split position would be just before the end of the interval
 538                 // . no split at all necessary
 539                 if (debug.isLogEnabled()) {
 540                     debug.log("no split necessary because optimal split position is at end of interval");
 541                 }
 542                 return;
 543             }
 544             // must calculate this before the actual split is performed and before split position is
 545             // moved to odd opId
 546             final int optimalSplitPosFinal;
 547             boolean blockBegin = allocator.isBlockBegin(optimalSplitPos);
 548             assert blockBegin || !allocator.isBlockBegin(optimalSplitPos - 1);
 549             boolean moveNecessary = !blockBegin;
 550             if (blockBegin) {
 551                 optimalSplitPosFinal = optimalSplitPos;
 552             } else {
 553                 // move position before actual instruction (odd opId)
 554                 optimalSplitPosFinal = (optimalSplitPos - 1) | 1;
 555             }
 556 
 557             // TODO( je) better define what min split pos max split pos mean.
 558             assert minSplitPos <= optimalSplitPosFinal && optimalSplitPosFinal <= maxSplitPos || minSplitPos == maxSplitPos && optimalSplitPosFinal == minSplitPos - 1 : "out of range";
 559             assert optimalSplitPosFinal <= interval.to() : "cannot split after end of interval";
 560             assert optimalSplitPosFinal > interval.from() : "cannot split at start of interval";
 561 
 562             if (debug.isLogEnabled()) {
 563                 debug.log("splitting at position %d", optimalSplitPosFinal);
 564             }
 565             assert optimalSplitPosFinal > currentPosition : "Can not split interval " + interval + " at current position: " + currentPosition;
 566 
 567             assert blockBegin || ((optimalSplitPosFinal & 1) == 1) : "split pos must be odd when not on block boundary";
 568             assert !blockBegin || ((optimalSplitPosFinal & 1) == 0) : "split pos must be even on block boundary";
 569 
 570             // TODO (je) duplicate code. try to fold
 571             if (optimalSplitPosFinal == interval.to() && interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos) == Integer.MAX_VALUE) {
 572                 // the split position would be just before the end of the interval
 573                 // . no split at all necessary
 574                 if (debug.isLogEnabled()) {
 575                     debug.log("no split necessary because optimal split position is at end of interval");
 576                 }
 577                 return;
 578             }
 579             TraceInterval splitPart = interval.split(optimalSplitPosFinal, allocator);
 580 
 581             splitPart.setInsertMoveWhenActivated(moveNecessary);
 582 
 583             assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
 584             unhandledAnyList = TraceLinearScanWalker.addToListSortedByStartAndUsePositions(unhandledAnyList, splitPart);
 585 
 586             if (debug.isLogEnabled()) {
 587                 debug.log("left interval  %s: %s", moveNecessary ? "      " : "", interval.logString());
 588                 debug.log("right interval %s: %s", moveNecessary ? "(move)" : "", splitPart.logString());
 589             }
 590         }
 591     }
 592 
 593     // split an interval at the optimal position between minSplitPos and
 594     // maxSplitPos in two parts:
 595     // 1) the left part has already a location assigned
 596     // 2) the right part is always on the stack and therefore ignored in further processing
 597     @SuppressWarnings("try")
 598     private void splitForSpilling(TraceInterval interval) {
 599         // calculate allowed range of splitting position
 600         int maxSplitPos = currentPosition;
 601         int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
 602         if (previousUsage == currentPosition) {
 603             /*
 604              * If there is a usage with ShouldHaveRegister priority at the current position fall
 605              * back to MustHaveRegister priority. This only happens if register priority was
 606              * downgraded to MustHaveRegister in #allocLockedRegister.
 607              */
 608             previousUsage = interval.previousUsage(RegisterPriority.MustHaveRegister, maxSplitPos);
 609         }
 610         int minSplitPos = Math.max(previousUsage + 1, interval.from());
 611 
 612         try (Indent indent = debug.logAndIndent("splitting and spilling interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
 613 
 614             assert interval.from() <= minSplitPos : "cannot split before start of interval";
 615             assert minSplitPos <= maxSplitPos : "invalid order";
 616             assert maxSplitPos < interval.to() : "cannot split at end end of interval";
 617             assert currentPosition < interval.to() : "interval must not end before current position";
 618 
 619             if (minSplitPos == interval.from()) {
 620                 // the whole interval is never used, so spill it entirely to memory
 621 
 622                 try (Indent indent2 = debug.logAndIndent("spilling entire interval because split pos is at beginning of interval (use positions: %d)", interval.numUsePos())) {
 623 
 624                     assert interval.firstUsage(RegisterPriority.MustHaveRegister) > currentPosition : String.format("interval %s must not have use position before currentPosition %d", interval,
 625                                     currentPosition);
 626 
 627                     allocator.assignSpillSlot(interval);
 628                     handleSpillSlot(interval);
 629                     changeSpillState(interval, minSplitPos);
 630 
 631                     // Also kick parent intervals out of register to memory when they have no use
 632                     // position. This avoids short interval in register surrounded by intervals in
 633                     // memory . avoid useless moves from memory to register and back
 634                     TraceInterval parent = interval;
 635                     while (parent != null && parent.isSplitChild()) {
 636                         parent = parent.getSplitChildBeforeOpId(parent.from());
 637 
 638                         if (isRegister(parent.location())) {
 639                             if (parent.firstUsage(RegisterPriority.ShouldHaveRegister) == Integer.MAX_VALUE) {
 640                                 // parent is never used, so kick it out of its assigned register
 641                                 if (debug.isLogEnabled()) {
 642                                     debug.log("kicking out interval %d out of its register because it is never used", parent.operandNumber);
 643                                 }
 644                                 allocator.assignSpillSlot(parent);
 645                                 handleSpillSlot(parent);
 646                             } else {
 647                                 // do not go further back because the register is actually used by
 648                                 // the interval
 649                                 parent = null;
 650                             }
 651                         }
 652                     }
 653                 }
 654 
 655             } else {
 656                 // search optimal split pos, split interval and spill only the right hand part
 657                 int optimalSplitPos = findOptimalSplitPos(interval, minSplitPos, maxSplitPos, false);
 658 
 659                 assert minSplitPos <= optimalSplitPos && optimalSplitPos <= maxSplitPos : "out of range";
 660                 assert optimalSplitPos < interval.to() : "cannot split at end of interval";
 661                 assert optimalSplitPos >= interval.from() : "cannot split before start of interval";
 662 
 663                 if (!allocator.isBlockBegin(optimalSplitPos)) {
 664                     // move position before actual instruction (odd opId)
 665                     optimalSplitPos = (optimalSplitPos - 1) | 1;
 666                 }
 667 
 668                 try (Indent indent2 = debug.logAndIndent("splitting at position %d", optimalSplitPos)) {
 669                     assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
 670                     assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
 671 
 672                     TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
 673                     allocator.assignSpillSlot(spilledPart);
 674                     handleSpillSlot(spilledPart);
 675                     changeSpillState(spilledPart, optimalSplitPos);
 676 
 677                     if (!allocator.isBlockBegin(optimalSplitPos)) {
 678                         if (debug.isLogEnabled()) {
 679                             debug.log("inserting move from interval %s to %s", interval, spilledPart);
 680                         }
 681                         insertMove(optimalSplitPos, interval, spilledPart);
 682                     } else {
 683                         if (debug.isLogEnabled()) {
 684                             debug.log("no need to insert move. done by data-flow resolution");
 685                         }
 686                     }
 687 
 688                     // the currentSplitChild is needed later when moves are inserted for reloading
 689                     assert spilledPart.currentSplitChild() == interval : "overwriting wrong currentSplitChild";
 690                     spilledPart.makeCurrentSplitChild();
 691 
 692                     if (debug.isLogEnabled()) {
 693                         debug.log("left interval: %s", interval.logString());
 694                         debug.log("spilled interval   : %s", spilledPart.logString());
 695                     }
 696                 }
 697             }
 698         }
 699     }
 700 
 701     /**
 702      * Change spill state of an interval.
 703      *
 704      * Note: called during register allocation.
 705      *
 706      * @param spillPos position of the spill
 707      */
 708     private void changeSpillState(TraceInterval interval, int spillPos) {
 709         if (TraceLinearScanPhase.Options.LIROptTraceRAEliminateSpillMoves.getValue(allocator.getOptions())) {
 710             switch (interval.spillState()) {
 711                 case NoSpillStore:
 712                     final int minSpillPos = calculateMinSpillPos(interval.spillDefinitionPos(), spillPos);
 713                     final int maxSpillPos = calculateMaxSpillPos(minSpillPos, spillPos);
 714 
 715                     final int optimalSpillPos = findOptimalSpillPos(minSpillPos, maxSpillPos);
 716 
 717                     /* Cannot spill at block begin since it interferes with move resolution. */
 718                     assert isNotBlockBeginOrMerge(optimalSpillPos) : "Spill pos at block begin: " + optimalSpillPos;
 719                     assert !allocator.isBlockEnd(optimalSpillPos) : "Spill pos at block end: " + optimalSpillPos;
 720                     assert (optimalSpillPos & 1) == 0 : "Spill pos must be even " + optimalSpillPos;
 721 
 722                     interval.setSpillDefinitionPos(optimalSpillPos);
 723                     interval.setSpillState(SpillState.SpillStore);
 724                     break;
 725                 case SpillStore:
 726                 case StartInMemory:
 727                 case NoOptimization:
 728                 case NoDefinitionFound:
 729                     // nothing to do
 730                     break;
 731 
 732                 default:
 733                     throw GraalError.shouldNotReachHere("other states not allowed at this time");
 734             }
 735         } else {
 736             interval.setSpillState(SpillState.NoOptimization);
 737         }
 738     }
 739 
 740     private int calculateMinSpillPos(int spillDefinitionPos, int spillPos) {
 741         int spillDefinitionPosEven = spillDefinitionPos & ~1;
 742         if (spillDefinitionPosEven == 0 || !allocator.isBlockBegin(spillDefinitionPosEven) || spillDefinitionPos == spillPos) {
 743             assert !allocator.isBlockEnd(spillDefinitionPosEven) : "Defintion at block end? " + spillDefinitionPos;
 744             return spillDefinitionPos;
 745         }
 746         assert allocator.isBlockBegin(spillDefinitionPosEven);
 747         if (SSAUtil.isMerge(allocator.blockForId(spillDefinitionPos))) {
 748             /* Spill at merge are OK since there will be no resolution moves. */
 749             return spillDefinitionPos;
 750         }
 751         int minSpillPos = spillDefinitionPosEven + 2;
 752         while (allocator.isBlockEnd(minSpillPos)) {
 753             // +2 is block begin, +4 is the instruction afterwards
 754             minSpillPos += 4;
 755         }
 756         assert minSpillPos <= spillPos : String.format("No minSpillPos found. defPos: %d, spillPos: %d, minSpillPos, %d", spillDefinitionPos, spillPos, minSpillPos);
 757         return minSpillPos;
 758     }
 759 
 760     private int calculateMaxSpillPos(final int minSpillPos, int spillPos) {
 761         int spillPosEven = spillPos & ~1;
 762         if (spillPosEven == 0) {
 763             return spillPos;
 764         }
 765         if ((minSpillPos & ~1) == spillPosEven) {
 766             assert isNotBlockBeginOrMerge(spillPos);
 767             return spillPos;
 768         }
 769         int maxSpillPos;
 770         /* Move away from block end. */
 771         if (allocator.isBlockEnd(spillPosEven)) {
 772             /* Block end. Use instruction before. */
 773             maxSpillPos = spillPosEven - 2;
 774         } else if (allocator.isBlockBegin(spillPosEven)) {
 775             /* Block begin. Use instruction before previous block end. */
 776             maxSpillPos = spillPosEven - 4;
 777         } else {
 778             return spillPos;
 779         }
 780         assert !allocator.isBlockEnd(maxSpillPos) : "Can no longer be a block end! " + maxSpillPos;
 781 
 782         /* Skip block begins. */
 783         while (allocator.isBlockBegin(maxSpillPos) && maxSpillPos > minSpillPos) {
 784             // -2 is block end, -4 is the instruction before
 785             maxSpillPos -= 4;
 786         }
 787         assert minSpillPos <= maxSpillPos;
 788         return maxSpillPos;
 789     }
 790 
 791     private boolean isNotBlockBeginOrMerge(int spillPos) {
 792         int spillPosEven = spillPos & ~1;
 793         return spillPosEven == 0 || !allocator.isBlockBegin(spillPosEven) || SSAUtil.isMerge(allocator.blockForId(spillPosEven));
 794     }
 795 
 796     /**
 797      * @param minSpillPos minimal spill position
 798      * @param maxSpillPos maximal spill position
 799      */
 800     private int findOptimalSpillPos(int minSpillPos, int maxSpillPos) {
 801         int optimalSpillPos = findOptimalSpillPos0(minSpillPos, maxSpillPos) & (~1);
 802         if (debug.isLogEnabled()) {
 803             debug.log("optimal spill position: %d", optimalSpillPos);
 804         }
 805         return optimalSpillPos;
 806     }
 807 
 808     private int findOptimalSpillPos0(int minSpillPos, int maxSpillPos) {
 809         if (minSpillPos == maxSpillPos) {
 810             // trivial case, no optimization of split position possible
 811             if (debug.isLogEnabled()) {
 812                 debug.log("min-pos and max-pos are equal, no optimization possible");
 813             }
 814             return minSpillPos;
 815 
 816         }
 817         assert minSpillPos < maxSpillPos : "must be true then";
 818         assert minSpillPos >= 0 : "cannot access minSplitPos - 1 otherwise";
 819 
 820         AbstractBlockBase<?> minBlock = allocator.blockForId(minSpillPos);
 821         AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSpillPos);
 822 
 823         assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
 824         if (minBlock == maxBlock) {
 825             // split position cannot be moved to block boundary : so split as late as possible
 826             if (debug.isLogEnabled()) {
 827                 debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
 828             }
 829             return maxSpillPos;
 830 
 831         }
 832         // search optimal block boundary between minSplitPos and maxSplitPos
 833         if (debug.isLogEnabled()) {
 834             debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
 835         }
 836 
 837         // currently using the same heuristic as for splitting
 838         return findOptimalSpillPos(minBlock, maxBlock, maxSpillPos);
 839     }
 840 
 841     private int findOptimalSpillPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
 842         int fromBlockNr = minBlock.getLinearScanNumber();
 843         int toBlockNr = maxBlock.getLinearScanNumber();
 844 
 845         assert 0 <= fromBlockNr && fromBlockNr < blockCount() : "out of range";
 846         assert 0 <= toBlockNr && toBlockNr < blockCount() : "out of range";
 847         assert fromBlockNr < toBlockNr : "must cross block boundary";
 848 
 849         /*
 850          * Try to split at end of maxBlock. We use last instruction -2 because we want to insert the
 851          * move before the block end op. If this would be after maxSplitPos, then use the
 852          * maxSplitPos.
 853          */
 854         int optimalSplitPos = allocator.getLastLirInstructionId(maxBlock) - 2;
 855         if (optimalSplitPos > maxSplitPos) {
 856             optimalSplitPos = maxSplitPos;
 857         }
 858 
 859         // minimal block probability
 860         double minProbability = maxBlock.probability();
 861         for (int i = toBlockNr - 1; i >= fromBlockNr; i--) {
 862             AbstractBlockBase<?> cur = blockAt(i);
 863 
 864             if (cur.probability() < minProbability) {
 865                 // Block with lower probability found. Split at the end of this block.
 866                 int opIdBeforeBlockEnd = allocator.getLastLirInstructionId(cur) - 2;
 867                 if (allocator.getLIR().getLIRforBlock(cur).size() > 2) {
 868                     minProbability = cur.probability();
 869                     optimalSplitPos = opIdBeforeBlockEnd;
 870                 } else {
 871                     /*
 872                      * Skip blocks with only LabelOp and BlockEndOp since they cause move ordering
 873                      * problems.
 874                      */
 875                     assert allocator.isBlockBegin(opIdBeforeBlockEnd);
 876                 }
 877             }
 878         }
 879         assert optimalSplitPos > allocator.maxOpId() || optimalSplitPos == maxSplitPos || allocator.isBlockEnd(optimalSplitPos + 2) : "algorithm must move split pos to block boundary";
 880         assert !allocator.isBlockBegin(optimalSplitPos);
 881         return optimalSplitPos;
 882     }
 883 
 884     /**
 885      * This is called for every interval that is assigned to a stack slot.
 886      */
 887     private static void handleSpillSlot(TraceInterval interval) {
 888         assert interval.location() != null && (interval.canMaterialize() || isStackSlotValue(interval.location())) : "interval not assigned to a stack slot " + interval;
 889         // Do nothing. Stack slots are not processed in this implementation.
 890     }
 891 
 892     private void splitStackInterval(TraceInterval interval) {
 893         int minSplitPos = currentPosition + 1;
 894         int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to());
 895 
 896         splitBeforeUsage(interval, minSplitPos, maxSplitPos);
 897     }
 898 
 899     private void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
 900         int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
 901         splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
 902     }
 903 
 904     private void splitAndSpillInterval(TraceInterval interval) {
 905         int currentPos = currentPosition;
 906         /*
 907          * Search the position where the interval must have a register and split at the optimal
 908          * position before. The new created part is added to the unhandled list and will get a
 909          * register when it is activated.
 910          */
 911         int minSplitPos = currentPos + 1;
 912         int maxSplitPos = interval.nextUsage(RegisterPriority.MustHaveRegister, minSplitPos);
 913 
 914         if (maxSplitPos <= interval.to()) {
 915             splitBeforeUsage(interval, minSplitPos, maxSplitPos);
 916         } else {
 917             debug.log("No more usage, no need to split: %s", interval);
 918         }
 919 
 920         assert interval.nextUsage(RegisterPriority.MustHaveRegister, currentPos) == Integer.MAX_VALUE : "the remaining part is spilled to stack and therefore has no register";
 921         splitForSpilling(interval);
 922     }
 923 
 924     @SuppressWarnings("try")
 925     private boolean allocFreeRegister(TraceInterval interval) {
 926         try (Indent indent = debug.logAndIndent("trying to find free register for %s", interval)) {
 927 
 928             initUseLists(true);
 929             freeExcludeActiveFixed();
 930             freeCollectInactiveFixed(interval);
 931             freeExcludeActiveAny();
 932             // freeCollectUnhandled(fixedKind, cur);
 933 
 934             // usePos contains the start of the next interval that has this register assigned
 935             // (either as a fixed register or a normal allocated register in the past)
 936             // only intervals overlapping with cur are processed, non-overlapping invervals can be
 937             // ignored safely
 938             if (debug.isLogEnabled()) {
 939                 // Enable this logging to see all register states
 940                 try (Indent indent2 = debug.logAndIndent("state of registers:")) {
 941                     for (Register register : availableRegs) {
 942                         int i = register.number;
 943                         debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
 944                     }
 945                 }
 946             }
 947 
 948             Register hint = null;
 949             IntervalHint locationHint = interval.locationHint(true);
 950             if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
 951                 hint = asRegister(locationHint.location());
 952                 if (debug.isLogEnabled()) {
 953                     debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
 954                 }
 955             }
 956             assert interval.location() == null : "register already assigned to interval";
 957 
 958             // the register must be free at least until this position
 959             int regNeededUntil = interval.from() + 1;
 960             int intervalTo = interval.to();
 961 
 962             boolean needSplit = false;
 963             int splitPos = -1;
 964 
 965             Register reg = null;
 966             Register minFullReg = null;
 967             Register maxPartialReg = null;
 968 
 969             for (Register availableReg : availableRegs) {
 970                 int number = availableReg.number;
 971                 if (usePos[number] >= intervalTo) {
 972                     // this register is free for the full interval
 973                     if (minFullReg == null || availableReg.equals(hint) || (usePos[number] < usePos[minFullReg.number] && !minFullReg.equals(hint))) {
 974                         minFullReg = availableReg;
 975                     }
 976                 } else if (usePos[number] > regNeededUntil) {
 977                     // this register is at least free until regNeededUntil
 978                     if (maxPartialReg == null || availableReg.equals(hint) || (usePos[number] > usePos[maxPartialReg.number] && !maxPartialReg.equals(hint))) {
 979                         maxPartialReg = availableReg;
 980                     }
 981                 }
 982             }
 983 
 984             if (minFullReg != null) {
 985                 reg = minFullReg;
 986             } else if (maxPartialReg != null) {
 987                 needSplit = true;
 988                 reg = maxPartialReg;
 989             } else {
 990                 return false;
 991             }
 992 
 993             splitPos = usePos[reg.number];
 994             interval.assignLocation(reg.asValue(allocator.getKind(interval)));
 995             if (debug.isLogEnabled()) {
 996                 debug.log("selected register %d (%s)", reg.number, reg);
 997             }
 998 
 999             assert splitPos > 0 : "invalid splitPos";
1000             if (needSplit) {
1001                 // register not available for full interval, so split it
1002                 splitWhenPartialRegisterAvailable(interval, splitPos);
1003             }
1004             // only return true if interval is completely assigned
1005             return true;
1006         }
1007     }
1008 
1009     private void splitAndSpillIntersectingIntervals(Register reg) {
1010         assert reg != null : "no register assigned";
1011 
1012         for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
1013             TraceInterval interval = spillIntervals[reg.number].get(i);
1014             removeFromList(interval);
1015             splitAndSpillInterval(interval);
1016         }
1017     }
1018 
1019     // Split an Interval and spill it to memory so that cur can be placed in a register
1020     @SuppressWarnings("try")
1021     private void allocLockedRegister(TraceInterval interval) {
1022         try (Indent indent = debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
1023 
1024             // the register must be free at least until this position
1025             int firstUsage = interval.firstUsage(RegisterPriority.MustHaveRegister);
1026             int firstShouldHaveUsage = interval.firstUsage(RegisterPriority.ShouldHaveRegister);
1027             int regNeededUntil = Math.min(firstUsage, interval.from() + 1);
1028             int intervalTo = interval.to();
1029             assert regNeededUntil >= 0 && regNeededUntil < Integer.MAX_VALUE : "interval has no use";
1030 
1031             Register reg;
1032             Register ignore;
1033             /*
1034              * In the common case we don't spill registers that have _any_ use position that is
1035              * closer than the next use of the current interval, but if we can't spill the current
1036              * interval we weaken this strategy and also allow spilling of intervals that have a
1037              * non-mandatory requirements (no MustHaveRegister use position).
1038              */
1039             for (RegisterPriority registerPriority = RegisterPriority.LiveAtLoopEnd; true; registerPriority = RegisterPriority.MustHaveRegister) {
1040                 // collect current usage of registers
1041                 initUseLists(false);
1042                 spillExcludeActiveFixed();
1043                 // spillBlockUnhandledFixed(cur);
1044                 spillBlockInactiveFixed(interval);
1045                 spillCollectActiveAny(registerPriority);
1046                 if (debug.isLogEnabled()) {
1047                     printRegisterState();
1048                 }
1049 
1050                 reg = null;
1051                 ignore = interval.location() != null && isRegister(interval.location()) ? asRegister(interval.location()) : null;
1052 
1053                 for (Register availableReg : availableRegs) {
1054                     int number = availableReg.number;
1055                     if (availableReg.equals(ignore)) {
1056                         // this register must be ignored
1057                     } else if (usePos[number] > regNeededUntil) {
1058                         /*
1059                          * If the use position is the same, prefer registers (active intervals)
1060                          * where the value is already on the stack.
1061                          */
1062                         if (reg == null || (usePos[number] > usePos[reg.number]) || (usePos[number] == usePos[reg.number] && (!isInMemory.get(reg.number) && isInMemory.get(number)))) {
1063                             reg = availableReg;
1064                         }
1065                     }
1066                 }
1067 
1068                 if (debug.isLogEnabled()) {
1069                     debug.log("Register Selected: %s", reg);
1070                 }
1071 
1072                 int regUsePos = (reg == null ? 0 : usePos[reg.number]);
1073                 if (regUsePos <= firstShouldHaveUsage) {
1074                     /* Check if there is another interval that is already in memory. */
1075                     if (reg == null || interval.inMemoryAt(currentPosition) || !isInMemory.get(reg.number)) {
1076                         if (debug.isLogEnabled()) {
1077                             debug.log("able to spill current interval. firstUsage(register): %d, usePos: %d", firstUsage, regUsePos);
1078                         }
1079 
1080                         if (firstUsage <= interval.from() + 1) {
1081                             if (registerPriority.equals(RegisterPriority.LiveAtLoopEnd)) {
1082                                 /*
1083                                  * Tool of last resort: we can not spill the current interval so we
1084                                  * try to spill an active interval that has a usage but do not
1085                                  * require a register.
1086                                  */
1087                                 debug.log("retry with register priority must have register");
1088                                 continue;
1089                             }
1090                             String description = "cannot spill interval (" + interval + ") that is used in first instruction (possible reason: no register found) firstUsage=" + firstUsage +
1091                                             ", interval.from()=" + interval.from() + "; already used candidates: " + Arrays.toString(availableRegs);
1092                             /*
1093                              * assign a reasonable register and do a bailout in product mode to
1094                              * avoid errors
1095                              */
1096                             allocator.assignSpillSlot(interval);
1097                             if (debug.isDumpEnabled(DebugContext.INFO_LEVEL)) {
1098                                 dumpLIRAndIntervals(description);
1099                             }
1100                             throw new OutOfRegistersException("LinearScan: no register found", description);
1101                         }
1102 
1103                         splitAndSpillInterval(interval);
1104                         return;
1105                     }
1106                 }
1107                 // common case: break out of the loop
1108                 break;
1109             }
1110 
1111             boolean needSplit = blockPos[reg.number] <= intervalTo;
1112 
1113             int splitPos = blockPos[reg.number];
1114 
1115             if (debug.isLogEnabled()) {
1116                 debug.log("decided to use register %d", reg.number);
1117             }
1118             assert splitPos > 0 : "invalid splitPos";
1119             assert needSplit || splitPos > interval.from() : "splitting interval at from";
1120 
1121             interval.assignLocation(reg.asValue(allocator.getKind(interval)));
1122             if (needSplit) {
1123                 // register not available for full interval : so split it
1124                 splitWhenPartialRegisterAvailable(interval, splitPos);
1125             }
1126 
1127             // perform splitting and spilling for all affected intervals
1128             splitAndSpillIntersectingIntervals(reg);
1129             return;
1130         }
1131     }
1132 
1133     private void dumpLIRAndIntervals(String description) {
1134         debug.dump(DebugContext.INFO_LEVEL, allocator.getLIR(), description);
1135         allocator.printIntervals(description);
1136     }
1137 
1138     @SuppressWarnings("try")
1139     private void printRegisterState() {
1140         try (Indent indent2 = debug.logAndIndent("state of registers:")) {
1141             for (Register reg : availableRegs) {
1142                 int i = reg.number;
1143                 try (Indent indent3 = debug.logAndIndent("reg %d: usePos: %d, blockPos: %d, inMemory: %b, intervals: ", i, usePos[i], blockPos[i], isInMemory.get(i))) {
1144                     for (int j = 0; j < spillIntervals[i].size(); j++) {
1145                         debug.log("%s", spillIntervals[i].get(j));
1146                     }
1147                 }
1148             }
1149         }
1150     }
1151 
1152     private boolean noAllocationPossible(TraceInterval interval) {
1153         if (allocator.callKillsRegisters()) {
1154             // fast calculation of intervals that can never get a register because the
1155             // the next instruction is a call that blocks all registers
1156             // Note: this only works if a call kills all registers
1157 
1158             // check if this interval is the result of a split operation
1159             // (an interval got a register until this position)
1160             int pos = interval.from();
1161             if (isOdd(pos)) {
1162                 // the current instruction is a call that blocks all registers
1163                 if (pos < allocator.maxOpId() && allocator.hasCall(pos + 1) && interval.to() > pos + 1) {
1164                     if (debug.isLogEnabled()) {
1165                         debug.log("free register cannot be available because all registers blocked by following call");
1166                     }
1167 
1168                     // safety check that there is really no register available
1169                     assert !allocFreeRegister(interval) : "found a register for this interval";
1170                     return true;
1171                 }
1172             }
1173         }
1174         return false;
1175     }
1176 
1177     private void initVarsForAlloc(TraceInterval interval) {
1178         AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(allocator.getKind(interval).getPlatformKind());
1179         availableRegs = allocatableRegisters.allocatableRegisters;
1180         minReg = allocatableRegisters.minRegisterNumber;
1181         maxReg = allocatableRegisters.maxRegisterNumber;
1182     }
1183 
1184     private static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) {
1185         if (ValueMoveOp.isValueMoveOp(op)) {
1186             ValueMoveOp move = ValueMoveOp.asValueMoveOp(op);
1187             if (isVariable(move.getInput()) && isVariable(move.getResult())) {
1188                 return move.getInput() != null && LIRValueUtil.asVariable(move.getInput()).index == from.operandNumber && move.getResult() != null &&
1189                                 LIRValueUtil.asVariable(move.getResult()).index == to.operandNumber;
1190             }
1191         }
1192         return false;
1193     }
1194 
1195     // optimization (especially for phi functions of nested loops):
1196     // assign same spill slot to non-intersecting intervals
1197     private void combineSpilledIntervals(TraceInterval interval) {
1198         if (interval.isSplitChild()) {
1199             // optimization is only suitable for split parents
1200             return;
1201         }
1202 
1203         IntervalHint locationHint = interval.locationHint(false);
1204         if (locationHint == null || !(locationHint instanceof TraceInterval)) {
1205             return;
1206         }
1207         TraceInterval registerHint = (TraceInterval) locationHint;
1208         assert registerHint.isSplitParent() : "register hint must be split parent";
1209 
1210         if (interval.spillState() != SpillState.NoOptimization || registerHint.spillState() != SpillState.NoOptimization) {
1211             // combining the stack slots for intervals where spill move optimization is applied
1212             // is not benefitial and would cause problems
1213             return;
1214         }
1215 
1216         int beginPos = interval.from();
1217         int endPos = interval.to();
1218         if (endPos > allocator.maxOpId() || isOdd(beginPos) || isOdd(endPos)) {
1219             // safety check that lirOpWithId is allowed
1220             return;
1221         }
1222 
1223         if (!isMove(allocator.instructionForId(beginPos), registerHint, interval) || !isMove(allocator.instructionForId(endPos), interval, registerHint)) {
1224             // cur and registerHint are not connected with two moves
1225             return;
1226         }
1227 
1228         TraceInterval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE);
1229         TraceInterval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF);
1230         if (beginHint == endHint || beginHint.to() != beginPos || endHint.from() != endPos) {
1231             // registerHint must be split : otherwise the re-writing of use positions does not work
1232             return;
1233         }
1234 
1235         assert beginHint.location() != null : "must have register assigned";
1236         assert endHint.location() == null : "must not have register assigned";
1237         assert interval.firstUsage(RegisterPriority.MustHaveRegister) == beginPos : "must have use position at begin of interval because of move";
1238         assert endHint.firstUsage(RegisterPriority.MustHaveRegister) == endPos : "must have use position at begin of interval because of move";
1239 
1240         if (isRegister(beginHint.location())) {
1241             // registerHint is not spilled at beginPos : so it would not be benefitial to
1242             // immediately spill cur
1243             return;
1244         }
1245         assert registerHint.spillSlot() != null : "must be set when part of interval was spilled";
1246 
1247         // modify intervals such that cur gets the same stack slot as registerHint
1248         // delete use positions to prevent the intervals to get a register at beginning
1249         interval.setSpillSlot(registerHint.spillSlot());
1250         interval.removeFirstUsePos();
1251         endHint.removeFirstUsePos();
1252     }
1253 
1254     // allocate a physical register or memory location to an interval
1255     @SuppressWarnings("try")
1256     private boolean activateCurrent(TraceInterval interval) {
1257         if (debug.isLogEnabled()) {
1258             logCurrentStatus();
1259         }
1260         boolean result = true;
1261 
1262         try (Indent indent = debug.logAndIndent("activating interval %s,  splitParent: %d", interval, interval.splitParent().operandNumber)) {
1263 
1264             if (interval.location() != null && isStackSlotValue(interval.location())) {
1265                 // activating an interval that has a stack slot assigned . split it at first use
1266                 // position
1267                 // used for method parameters
1268                 if (debug.isLogEnabled()) {
1269                     debug.log("interval has spill slot assigned (method parameter) . split it before first use");
1270                 }
1271                 splitStackInterval(interval);
1272                 result = false;
1273 
1274             } else {
1275                 if (interval.location() == null) {
1276                     // interval has not assigned register . normal allocation
1277                     // (this is the normal case for most intervals)
1278                     if (debug.isLogEnabled()) {
1279                         debug.log("normal allocation of register");
1280                     }
1281 
1282                     // assign same spill slot to non-intersecting intervals
1283                     combineSpilledIntervals(interval);
1284 
1285                     initVarsForAlloc(interval);
1286                     if (noAllocationPossible(interval) || !allocFreeRegister(interval)) {
1287                         // no empty register available.
1288                         // split and spill another interval so that this interval gets a register
1289                         allocLockedRegister(interval);
1290                     }
1291 
1292                     // spilled intervals need not be move to active-list
1293                     if (!isRegister(interval.location())) {
1294                         result = false;
1295                     }
1296                 }
1297             }
1298 
1299             // load spilled values that become active from stack slot to register
1300             if (interval.insertMoveWhenActivated()) {
1301                 assert interval.isSplitChild();
1302                 assert interval.currentSplitChild() != null;
1303                 assert interval.currentSplitChild().operandNumber != interval.operandNumber : "cannot insert move between same interval";
1304                 if (debug.isLogEnabled()) {
1305                     debug.log("Inserting move from interval %d to %d because insertMoveWhenActivated is set", interval.currentSplitChild().operandNumber, interval.operandNumber);
1306                 }
1307 
1308                 insertMove(interval.from(), interval.currentSplitChild(), interval);
1309             }
1310             interval.makeCurrentSplitChild();
1311 
1312         }
1313 
1314         return result; // true = interval is moved to active list
1315     }
1316 
1317     void finishAllocation() {
1318         // must be called when all intervals are allocated
1319         moveResolver.resolveAndAppendMoves();
1320     }
1321 
1322     @SuppressWarnings("try")
1323     private void logCurrentStatus() {
1324         try (Indent i = debug.logAndIndent("active:")) {
1325             logList(debug, activeFixedList);
1326             logList(debug, activeAnyList);
1327         }
1328         try (Indent i = debug.logAndIndent("inactive(fixed):")) {
1329             logList(debug, inactiveFixedList);
1330         }
1331     }
1332 
1333     void walk() {
1334         walkTo(Integer.MAX_VALUE);
1335     }
1336 
1337     private void removeFromList(TraceInterval interval) {
1338         activeAnyList = TraceLinearScanWalker.removeAny(activeAnyList, interval);
1339     }
1340 
1341     /**
1342      * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}.
1343      *
1344      * Fixed intervals can switch back and forth between the states {@link State#Active} and
1345      * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not
1346      * managed).
1347      */
1348     @SuppressWarnings("try")
1349     private void walkToFixed(State state, int from) {
1350         assert state == State.Active || state == State.Inactive : "wrong state";
1351         FixedInterval prevprev = null;
1352         FixedInterval prev = (state == State.Active) ? activeFixedList : inactiveFixedList;
1353         FixedInterval next = prev;
1354         if (debug.isLogEnabled()) {
1355             try (Indent i = debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
1356                 logList(debug, next);
1357             }
1358         }
1359         while (next.currentFrom() <= from) {
1360             FixedInterval cur = next;
1361             next = cur.next;
1362 
1363             boolean rangeHasChanged = false;
1364             while (cur.currentTo() <= from) {
1365                 cur.nextRange();
1366                 rangeHasChanged = true;
1367             }
1368 
1369             // also handle move from inactive list to active list
1370             rangeHasChanged = rangeHasChanged || (state == State.Inactive && cur.currentFrom() <= from);
1371 
1372             if (rangeHasChanged) {
1373                 // remove cur from list
1374                 if (prevprev == null) {
1375                     if (state == State.Active) {
1376                         activeFixedList = next;
1377                     } else {
1378                         inactiveFixedList = next;
1379                     }
1380                 } else {
1381                     prevprev.next = next;
1382                 }
1383                 prev = next;
1384                 TraceInterval.State newState;
1385                 if (cur.currentAtEnd()) {
1386                     // move to handled state (not maintained as a list)
1387                     newState = State.Handled;
1388                 } else {
1389                     if (cur.currentFrom() <= from) {
1390                         // sort into active list
1391                         activeFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(activeFixedList, cur);
1392                         newState = State.Active;
1393                     } else {
1394                         // sort into inactive list
1395                         inactiveFixedList = TraceLinearScanWalker.addToListSortedByCurrentFromPositions(inactiveFixedList, cur);
1396                         newState = State.Inactive;
1397                     }
1398                     if (prev == cur) {
1399                         assert state == newState;
1400                         prevprev = prev;
1401                         prev = cur.next;
1402                     }
1403                 }
1404                 intervalMoved(debug, cur, state, newState);
1405             } else {
1406                 prevprev = prev;
1407                 prev = cur.next;
1408             }
1409         }
1410     }
1411 
1412     /**
1413      * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
1414      *
1415      * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then
1416      * to {@link State#Handled} but handled intervals are not managed.
1417      */
1418     @SuppressWarnings("try")
1419     private void walkToAny(int from) {
1420         TraceInterval prevprev = null;
1421         TraceInterval prev = activeAnyList;
1422         TraceInterval next = prev;
1423         if (debug.isLogEnabled()) {
1424             try (Indent i = debug.logAndIndent("walkToAny(%d):", from)) {
1425                 logList(debug, next);
1426             }
1427         }
1428         while (next.from() <= from) {
1429             TraceInterval cur = next;
1430             next = cur.next;
1431 
1432             if (cur.to() <= from) {
1433                 // remove cur from list
1434                 if (prevprev == null) {
1435                     activeAnyList = next;
1436                 } else {
1437                     prevprev.next = next;
1438                 }
1439                 intervalMoved(debug, cur, State.Active, State.Handled);
1440             } else {
1441                 prevprev = prev;
1442             }
1443             prev = next;
1444         }
1445     }
1446 
1447     /**
1448      * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at
1449      * {@code toOpId}. The returned interval is removed.
1450      *
1451      * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}.
1452      *
1453      * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled}
1454      *         interval at position {@code toOpId}.
1455      */
1456     private TraceInterval nextInterval(int toOpId) {
1457         TraceInterval any = unhandledAnyList;
1458 
1459         if (any != TraceInterval.EndMarker) {
1460             TraceInterval currentInterval = unhandledAnyList;
1461             if (toOpId < currentInterval.from()) {
1462                 return null;
1463             }
1464 
1465             unhandledAnyList = currentInterval.next;
1466             currentInterval.next = TraceInterval.EndMarker;
1467             return currentInterval;
1468         }
1469         return null;
1470 
1471     }
1472 
1473     /**
1474      * Walk up to {@code toOpId}.
1475      *
1476      * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
1477      *                and {@link #inactiveFixedList} are populated.
1478      */
1479     @SuppressWarnings("try")
1480     private void walkTo(int toOpId) {
1481         assert currentPosition <= toOpId : "can not walk backwards";
1482         for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
1483             int opId = currentInterval.from();
1484 
1485             // set currentPosition prior to call of walkTo
1486             currentPosition = opId;
1487 
1488             // update unhandled stack intervals
1489             // updateUnhandledStackIntervals(opId);
1490 
1491             // call walkTo even if currentPosition == id
1492             walkToFixed(State.Active, opId);
1493             walkToFixed(State.Inactive, opId);
1494             walkToAny(opId);
1495 
1496             try (Indent indent = debug.logAndIndent("walk to op %d", opId)) {
1497                 if (activateCurrent(currentInterval)) {
1498                     activeAnyList = TraceLinearScanWalker.addToListSortedByFromPositions(activeAnyList, currentInterval);
1499                     intervalMoved(debug, currentInterval, State.Unhandled, State.Active);
1500                 }
1501             }
1502         }
1503         // set currentPosition prior to call of walkTo
1504         currentPosition = toOpId;
1505 
1506         if (currentPosition <= allocator.maxOpId()) {
1507             // update unhandled stack intervals
1508             // updateUnhandledStackIntervals(toOpId);
1509 
1510             // call walkTo if still in range
1511             walkToFixed(State.Active, toOpId);
1512             walkToFixed(State.Inactive, toOpId);
1513             walkToAny(toOpId);
1514         }
1515     }
1516 
1517     private static void logList(DebugContext debug, FixedInterval i) {
1518         for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
1519             debug.log("%s", interval.logString());
1520         }
1521     }
1522 
1523     private static void logList(DebugContext debug, TraceInterval i) {
1524         for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
1525             debug.log("%s", interval.logString());
1526         }
1527     }
1528 
1529     private static void intervalMoved(DebugContext debug, IntervalHint interval, State from, State to) {
1530         // intervalMoved() is called whenever an interval moves from one interval list to another.
1531         // In the implementation of this method it is prohibited to move the interval to any list.
1532         if (debug.isLogEnabled()) {
1533             debug.log("interval moved from %s to %s: %s", from, to, interval.logString());
1534         }
1535     }
1536 }