1 /* 2 * Copyright (c) 2009, 2018, 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.lsra; 26 27 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 28 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 29 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 30 import static jdk.vm.ci.code.ValueUtil.asRegister; 31 import static jdk.vm.ci.code.ValueUtil.isIllegal; 32 import static jdk.vm.ci.code.ValueUtil.isRegister; 33 import static jdk.vm.ci.code.ValueUtil.isStackSlot; 34 35 import java.util.ArrayList; 36 import java.util.Collections; 37 import java.util.EnumSet; 38 import java.util.List; 39 40 import org.graalvm.compiler.core.common.LIRKind; 41 import org.graalvm.compiler.core.common.util.IntList; 42 import org.graalvm.compiler.core.common.util.Util; 43 import org.graalvm.compiler.debug.Assertions; 44 import org.graalvm.compiler.debug.GraalError; 45 import org.graalvm.compiler.lir.LIRInstruction; 46 import org.graalvm.compiler.lir.Variable; 47 import jdk.vm.ci.code.RegisterValue; 48 import jdk.vm.ci.code.StackSlot; 49 import jdk.vm.ci.meta.AllocatableValue; 50 import jdk.vm.ci.meta.Constant; 51 import jdk.vm.ci.meta.Value; 52 import jdk.vm.ci.meta.ValueKind; 53 54 /** 55 * Represents an interval in the {@linkplain LinearScan linear scan register allocator}. 56 */ 57 public final class Interval { 58 59 /** 60 * A set of interval lists, one per {@linkplain RegisterBinding binding} type. 61 */ 62 static final class RegisterBindingLists { 63 64 /** 65 * List of intervals whose binding is currently {@link RegisterBinding#Fixed}. 66 */ 67 public Interval fixed; 68 69 /** 70 * List of intervals whose binding is currently {@link RegisterBinding#Any}. 71 */ 72 public Interval any; 73 74 /** 75 * List of intervals whose binding is currently {@link RegisterBinding#Stack}. 76 */ 77 public Interval stack; 78 RegisterBindingLists(Interval fixed, Interval any, Interval stack)79 RegisterBindingLists(Interval fixed, Interval any, Interval stack) { 80 this.fixed = fixed; 81 this.any = any; 82 this.stack = stack; 83 } 84 85 /** 86 * Gets the list for a specified binding. 87 * 88 * @param binding specifies the list to be returned 89 * @return the list of intervals whose binding is {@code binding} 90 */ get(RegisterBinding binding)91 public Interval get(RegisterBinding binding) { 92 switch (binding) { 93 case Any: 94 return any; 95 case Fixed: 96 return fixed; 97 case Stack: 98 return stack; 99 } 100 throw GraalError.shouldNotReachHere(); 101 } 102 103 /** 104 * Sets the list for a specified binding. 105 * 106 * @param binding specifies the list to be replaced 107 * @param list a list of intervals whose binding is {@code binding} 108 */ set(RegisterBinding binding, Interval list)109 public void set(RegisterBinding binding, Interval list) { 110 assert list != null; 111 switch (binding) { 112 case Any: 113 any = list; 114 break; 115 case Fixed: 116 fixed = list; 117 break; 118 case Stack: 119 stack = list; 120 break; 121 } 122 } 123 124 /** 125 * Adds an interval to a list sorted by {@linkplain Interval#currentFrom() current from} 126 * positions. 127 * 128 * @param binding specifies the list to be updated 129 * @param interval the interval to add 130 */ addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval)131 public void addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval) { 132 Interval list = get(binding); 133 Interval prev = null; 134 Interval cur = list; 135 while (cur.currentFrom() < interval.currentFrom()) { 136 prev = cur; 137 cur = cur.next; 138 } 139 Interval result = list; 140 if (prev == null) { 141 // add to head of list 142 result = interval; 143 } else { 144 // add before 'cur' 145 prev.next = interval; 146 } 147 interval.next = cur; 148 set(binding, result); 149 } 150 151 /** 152 * Adds an interval to a list sorted by {@linkplain Interval#from() start} positions and 153 * {@linkplain Interval#firstUsage(RegisterPriority) first usage} positions. 154 * 155 * @param binding specifies the list to be updated 156 * @param interval the interval to add 157 */ addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval)158 public void addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval) { 159 Interval list = get(binding); 160 Interval prev = null; 161 Interval cur = list; 162 while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) { 163 prev = cur; 164 cur = cur.next; 165 } 166 if (prev == null) { 167 list = interval; 168 } else { 169 prev.next = interval; 170 } 171 interval.next = cur; 172 set(binding, list); 173 } 174 175 /** 176 * Removes an interval from a list. 177 * 178 * @param binding specifies the list to be updated 179 * @param i the interval to remove 180 */ remove(RegisterBinding binding, Interval i)181 public void remove(RegisterBinding binding, Interval i) { 182 Interval list = get(binding); 183 Interval prev = null; 184 Interval cur = list; 185 while (cur != i) { 186 assert cur != null && !cur.isEndMarker() : "interval has not been found in list: " + i; 187 prev = cur; 188 cur = cur.next; 189 } 190 if (prev == null) { 191 set(binding, cur.next); 192 } else { 193 prev.next = cur.next; 194 } 195 } 196 } 197 198 /** 199 * Constants denoting the register usage priority for an interval. The constants are declared in 200 * increasing order of priority are are used to optimize spilling when multiple overlapping 201 * intervals compete for limited registers. 202 */ 203 public enum RegisterPriority { 204 /** 205 * No special reason for an interval to be allocated a register. 206 */ 207 None, 208 209 /** 210 * Priority level for intervals live at the end of a loop. 211 */ 212 LiveAtLoopEnd, 213 214 /** 215 * Priority level for intervals that should be allocated to a register. 216 */ 217 ShouldHaveRegister, 218 219 /** 220 * Priority level for intervals that must be allocated to a register. 221 */ 222 MustHaveRegister; 223 224 public static final RegisterPriority[] VALUES = values(); 225 226 /** 227 * Determines if this priority is higher than or equal to a given priority. 228 */ greaterEqual(RegisterPriority other)229 public boolean greaterEqual(RegisterPriority other) { 230 return ordinal() >= other.ordinal(); 231 } 232 233 /** 234 * Determines if this priority is lower than a given priority. 235 */ lessThan(RegisterPriority other)236 public boolean lessThan(RegisterPriority other) { 237 return ordinal() < other.ordinal(); 238 } 239 } 240 241 /** 242 * Constants denoting whether an interval is bound to a specific register. This models platform 243 * dependencies on register usage for certain instructions. 244 */ 245 enum RegisterBinding { 246 /** 247 * Interval is bound to a specific register as required by the platform. 248 */ 249 Fixed, 250 251 /** 252 * Interval has no specific register requirements. 253 */ 254 Any, 255 256 /** 257 * Interval is bound to a stack slot. 258 */ 259 Stack; 260 261 public static final RegisterBinding[] VALUES = values(); 262 } 263 264 /** 265 * Constants denoting the linear-scan states an interval may be in with respect to the 266 * {@linkplain Interval#from() start} {@code position} of the interval being processed. 267 */ 268 enum State { 269 /** 270 * An interval that starts after {@code position}. 271 */ 272 Unhandled, 273 274 /** 275 * An interval that {@linkplain Interval#covers covers} {@code position} and has an assigned 276 * register. 277 */ 278 Active, 279 280 /** 281 * An interval that starts before and ends after {@code position} but does not 282 * {@linkplain Interval#covers cover} it due to a lifetime hole. 283 */ 284 Inactive, 285 286 /** 287 * An interval that ends before {@code position} or is spilled to memory. 288 */ 289 Handled; 290 } 291 292 /** 293 * Constants used in optimization of spilling of an interval. 294 */ 295 public enum SpillState { 296 /** 297 * Starting state of calculation: no definition found yet. 298 */ 299 NoDefinitionFound, 300 301 /** 302 * One definition has already been found. Two consecutive definitions are treated as one 303 * (e.g. a consecutive move and add because of two-operand LIR form). The position of this 304 * definition is given by {@link Interval#spillDefinitionPos()}. 305 */ 306 NoSpillStore, 307 308 /** 309 * One spill move has already been inserted. 310 */ 311 OneSpillStore, 312 313 /** 314 * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere 315 * on the dominator path between the definition and the usages. 316 */ 317 SpillInDominator, 318 319 /** 320 * The interval should be stored immediately after its definition to prevent multiple 321 * redundant stores. 322 */ 323 StoreAtDefinition, 324 325 /** 326 * The interval starts in memory (e.g. method parameter), so a store is never necessary. 327 */ 328 StartInMemory, 329 330 /** 331 * The interval has more than one definition (e.g. resulting from phi moves), so stores to 332 * memory are not optimized. 333 */ 334 NoOptimization; 335 336 public static final EnumSet<SpillState> ALWAYS_IN_MEMORY = EnumSet.of(SpillInDominator, StoreAtDefinition, StartInMemory); 337 } 338 339 /** 340 * List of use positions. Each entry in the list records the use position and register priority 341 * associated with the use position. The entries in the list are in descending order of use 342 * position. 343 * 344 */ 345 public static final class UsePosList { 346 347 private IntList list; 348 349 /** 350 * Creates a use list. 351 * 352 * @param initialCapacity the initial capacity of the list in terms of entries 353 */ UsePosList(int initialCapacity)354 public UsePosList(int initialCapacity) { 355 list = new IntList(initialCapacity * 2); 356 } 357 UsePosList(IntList list)358 private UsePosList(IntList list) { 359 this.list = list; 360 } 361 362 /** 363 * Splits this list around a given position. All entries in this list with a use position 364 * greater or equal than {@code splitPos} are removed from this list and added to the 365 * returned list. 366 * 367 * @param splitPos the position for the split 368 * @return a use position list containing all entries removed from this list that have a use 369 * position greater or equal than {@code splitPos} 370 */ splitAt(int splitPos)371 public UsePosList splitAt(int splitPos) { 372 int i = size() - 1; 373 int len = 0; 374 while (i >= 0 && usePos(i) < splitPos) { 375 --i; 376 len += 2; 377 } 378 int listSplitIndex = (i + 1) * 2; 379 IntList childList = list; 380 list = IntList.copy(this.list, listSplitIndex, len); 381 childList.setSize(listSplitIndex); 382 UsePosList child = new UsePosList(childList); 383 return child; 384 } 385 386 /** 387 * Gets the use position at a specified index in this list. 388 * 389 * @param index the index of the entry for which the use position is returned 390 * @return the use position of entry {@code index} in this list 391 */ usePos(int index)392 public int usePos(int index) { 393 return list.get(index << 1); 394 } 395 396 /** 397 * Gets the register priority for the use position at a specified index in this list. 398 * 399 * @param index the index of the entry for which the register priority is returned 400 * @return the register priority of entry {@code index} in this list 401 */ registerPriority(int index)402 public RegisterPriority registerPriority(int index) { 403 return RegisterPriority.VALUES[list.get((index << 1) + 1)]; 404 } 405 add(int usePos, RegisterPriority registerPriority)406 public void add(int usePos, RegisterPriority registerPriority) { 407 assert list.size() == 0 || usePos(size() - 1) > usePos; 408 list.add(usePos); 409 list.add(registerPriority.ordinal()); 410 } 411 size()412 public int size() { 413 return list.size() >> 1; 414 } 415 removeLowestUsePos()416 public void removeLowestUsePos() { 417 list.setSize(list.size() - 2); 418 } 419 setRegisterPriority(int index, RegisterPriority registerPriority)420 public void setRegisterPriority(int index, RegisterPriority registerPriority) { 421 list.set((index << 1) + 1, registerPriority.ordinal()); 422 } 423 424 @Override toString()425 public String toString() { 426 StringBuilder buf = new StringBuilder("["); 427 for (int i = size() - 1; i >= 0; --i) { 428 if (buf.length() != 1) { 429 buf.append(", "); 430 } 431 RegisterPriority prio = registerPriority(i); 432 buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio); 433 } 434 return buf.append("]").toString(); 435 } 436 } 437 438 protected static final int END_MARKER_OPERAND_NUMBER = Integer.MIN_VALUE; 439 440 /** 441 * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval 442 * prior to register allocation. 443 */ 444 public final AllocatableValue operand; 445 446 /** 447 * The operand number for this interval's {@linkplain #operand operand}. 448 */ 449 public final int operandNumber; 450 451 /** 452 * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this 453 * interval. In case of a spilled interval which is re-materialized this is 454 * {@link Value#ILLEGAL}. 455 */ 456 private AllocatableValue location; 457 458 /** 459 * The stack slot to which all splits of this interval are spilled if necessary. 460 */ 461 private AllocatableValue spillSlot; 462 463 /** 464 * The kind of this interval. 465 */ 466 private ValueKind<?> kind; 467 468 /** 469 * The head of the list of ranges describing this interval. This list is sorted by 470 * {@linkplain LIRInstruction#id instruction ids}. 471 */ 472 private Range first; 473 474 /** 475 * List of (use-positions, register-priorities) pairs, sorted by use-positions. 476 */ 477 private UsePosList usePosList; 478 479 /** 480 * Iterator used to traverse the ranges of an interval. 481 */ 482 private Range current; 483 484 /** 485 * Link to next interval in a sorted list of intervals that ends with 486 * LinearScan.intervalEndMarker. 487 */ 488 Interval next; 489 490 /** 491 * The linear-scan state of this interval. 492 */ 493 State state; 494 495 private int cachedTo; // cached value: to of last range (-1: not cached) 496 497 /** 498 * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split 499 * parent}, it points to itself. 500 */ 501 private Interval splitParent; 502 503 /** 504 * List of all intervals that are split off from this interval. This is only used if this is a 505 * {@linkplain #isSplitParent() split parent}. 506 */ 507 private List<Interval> splitChildren = Collections.emptyList(); 508 509 /** 510 * Current split child that has been active or inactive last (always stored in split parents). 511 */ 512 private Interval currentSplitChild; 513 514 /** 515 * Specifies if move is inserted between currentSplitChild and this interval when interval gets 516 * active the first time. 517 */ 518 private boolean insertMoveWhenActivated; 519 520 /** 521 * For spill move optimization. 522 */ 523 private SpillState spillState; 524 525 /** 526 * Position where this interval is defined (if defined only once). 527 */ 528 private int spillDefinitionPos; 529 530 /** 531 * This interval should be assigned the same location as the hint interval. 532 */ 533 private Interval locationHint; 534 535 /** 536 * The value with which a spilled child interval can be re-materialized. Currently this must be 537 * a Constant. 538 */ 539 private Constant materializedValue; 540 541 /** 542 * The number of times {@link #addMaterializationValue(Constant)} is called. 543 */ 544 private int numMaterializationValuesAdded; 545 assignLocation(AllocatableValue newLocation)546 void assignLocation(AllocatableValue newLocation) { 547 if (isRegister(newLocation)) { 548 assert this.location == null : "cannot re-assign location for " + this; 549 if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) { 550 this.location = asRegister(newLocation).asValue(kind); 551 return; 552 } 553 } else if (isIllegal(newLocation)) { 554 assert canMaterialize(); 555 } else { 556 assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this; 557 assert isStackSlotValue(newLocation); 558 assert !newLocation.getValueKind().equals(LIRKind.Illegal); 559 assert newLocation.getValueKind().equals(this.kind); 560 } 561 this.location = newLocation; 562 } 563 564 /** Returns true is this is the sentinel interval that denotes the end of an interval list. */ isEndMarker()565 public boolean isEndMarker() { 566 return operandNumber == END_MARKER_OPERAND_NUMBER; 567 } 568 569 /** 570 * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to 571 * this interval. 572 */ location()573 public AllocatableValue location() { 574 return location; 575 } 576 kind()577 public ValueKind<?> kind() { 578 assert !isRegister(operand) : "cannot access type for fixed interval"; 579 return kind; 580 } 581 setKind(ValueKind<?> kind)582 public void setKind(ValueKind<?> kind) { 583 assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type"; 584 this.kind = kind; 585 } 586 first()587 public Range first() { 588 return first; 589 } 590 from()591 public int from() { 592 return first.from; 593 } 594 to()595 int to() { 596 if (cachedTo == -1) { 597 cachedTo = calcTo(); 598 } 599 assert cachedTo == calcTo() : "invalid cached value"; 600 return cachedTo; 601 } 602 numUsePositions()603 int numUsePositions() { 604 return usePosList.size(); 605 } 606 setLocationHint(Interval interval)607 public void setLocationHint(Interval interval) { 608 locationHint = interval; 609 } 610 isSplitParent()611 public boolean isSplitParent() { 612 return splitParent == this; 613 } 614 isSplitChild()615 boolean isSplitChild() { 616 return splitParent != this; 617 } 618 619 /** 620 * Gets the split parent for this interval. 621 */ splitParent()622 public Interval splitParent() { 623 assert splitParent.isSplitParent() : "not a split parent: " + this; 624 return splitParent; 625 } 626 627 /** 628 * Gets the canonical spill slot for this interval. 629 */ spillSlot()630 public AllocatableValue spillSlot() { 631 return splitParent().spillSlot; 632 } 633 setSpillSlot(AllocatableValue slot)634 public void setSpillSlot(AllocatableValue slot) { 635 assert isStackSlotValue(slot); 636 assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot"; 637 splitParent().spillSlot = slot; 638 } 639 currentSplitChild()640 Interval currentSplitChild() { 641 return splitParent().currentSplitChild; 642 } 643 makeCurrentSplitChild()644 void makeCurrentSplitChild() { 645 splitParent().currentSplitChild = this; 646 } 647 insertMoveWhenActivated()648 boolean insertMoveWhenActivated() { 649 return insertMoveWhenActivated; 650 } 651 setInsertMoveWhenActivated(boolean b)652 void setInsertMoveWhenActivated(boolean b) { 653 insertMoveWhenActivated = b; 654 } 655 656 // for spill optimization spillState()657 public SpillState spillState() { 658 return splitParent().spillState; 659 } 660 spillDefinitionPos()661 public int spillDefinitionPos() { 662 return splitParent().spillDefinitionPos; 663 } 664 setSpillState(SpillState state)665 public void setSpillState(SpillState state) { 666 assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; 667 splitParent().spillState = state; 668 } 669 setSpillDefinitionPos(int pos)670 public void setSpillDefinitionPos(int pos) { 671 assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; 672 splitParent().spillDefinitionPos = pos; 673 } 674 675 // returns true if this interval has a shadow copy on the stack that is always correct alwaysInMemory()676 public boolean alwaysInMemory() { 677 return SpillState.ALWAYS_IN_MEMORY.contains(spillState()) && !canMaterialize(); 678 } 679 removeFirstUsePos()680 void removeFirstUsePos() { 681 usePosList.removeLowestUsePos(); 682 } 683 684 // test intersection intersects(Interval i)685 boolean intersects(Interval i) { 686 return first.intersects(i.first); 687 } 688 intersectsAt(Interval i)689 int intersectsAt(Interval i) { 690 return first.intersectsAt(i.first); 691 } 692 693 // range iteration rewindRange()694 void rewindRange() { 695 current = first; 696 } 697 nextRange()698 void nextRange() { 699 assert !this.isEndMarker() : "not allowed on sentinel"; 700 current = current.next; 701 } 702 currentFrom()703 int currentFrom() { 704 return current.from; 705 } 706 currentTo()707 int currentTo() { 708 return current.to; 709 } 710 currentAtEnd()711 boolean currentAtEnd() { 712 return current.isEndMarker(); 713 } 714 currentIntersects(Interval it)715 boolean currentIntersects(Interval it) { 716 return current.intersects(it.current); 717 } 718 currentIntersectsAt(Interval it)719 int currentIntersectsAt(Interval it) { 720 return current.intersectsAt(it.current); 721 } 722 Interval(AllocatableValue operand, int operandNumber, Interval intervalEndMarker, Range rangeEndMarker)723 Interval(AllocatableValue operand, int operandNumber, Interval intervalEndMarker, Range rangeEndMarker) { 724 assert operand != null; 725 this.operand = operand; 726 this.operandNumber = operandNumber; 727 if (isRegister(operand)) { 728 location = operand; 729 } else { 730 assert isIllegal(operand) || isVariable(operand); 731 } 732 this.kind = LIRKind.Illegal; 733 this.first = rangeEndMarker; 734 this.usePosList = new UsePosList(4); 735 this.current = rangeEndMarker; 736 this.next = intervalEndMarker; 737 this.cachedTo = -1; 738 this.spillState = SpillState.NoDefinitionFound; 739 this.spillDefinitionPos = -1; 740 splitParent = this; 741 currentSplitChild = this; 742 } 743 744 /** 745 * Sets the value which is used for re-materialization. 746 */ addMaterializationValue(Constant value)747 public void addMaterializationValue(Constant value) { 748 if (numMaterializationValuesAdded == 0) { 749 materializedValue = value; 750 } else { 751 // Interval is defined on multiple places -> no materialization is possible. 752 materializedValue = null; 753 } 754 numMaterializationValuesAdded++; 755 } 756 757 /** 758 * Returns true if this interval can be re-materialized when spilled. This means that no 759 * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored. 760 */ canMaterialize()761 public boolean canMaterialize() { 762 return getMaterializedValue() != null; 763 } 764 765 /** 766 * Returns a value which can be moved to a register instead of a restore-move from stack. 767 */ getMaterializedValue()768 public Constant getMaterializedValue() { 769 return splitParent().materializedValue; 770 } 771 calcTo()772 int calcTo() { 773 assert !first.isEndMarker() : "interval has no range"; 774 775 Range r = first; 776 while (!r.next.isEndMarker()) { 777 r = r.next; 778 } 779 return r.to; 780 } 781 782 // consistency check of split-children checkSplitChildren()783 boolean checkSplitChildren() { 784 if (!splitChildren.isEmpty()) { 785 assert isSplitParent() : "only split parents can have children"; 786 787 for (int i = 0; i < splitChildren.size(); i++) { 788 Interval i1 = splitChildren.get(i); 789 790 assert i1.splitParent() == this : "not a split child of this interval"; 791 assert i1.kind().equals(kind()) : "must be equal for all split children"; 792 assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children"; 793 794 for (int j = i + 1; j < splitChildren.size(); j++) { 795 Interval i2 = splitChildren.get(j); 796 797 assert !i1.operand.equals(i2.operand) : "same register number"; 798 799 if (i1.from() < i2.from()) { 800 assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping"; 801 } else { 802 assert i2.from() < i1.from() : "intervals start at same opId"; 803 assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping"; 804 } 805 } 806 } 807 } 808 809 return true; 810 } 811 812 public Interval locationHint(boolean searchSplitChild) { 813 if (!searchSplitChild) { 814 return locationHint; 815 } 816 817 if (locationHint != null) { 818 assert locationHint.isSplitParent() : "ony split parents are valid hint registers"; 819 820 if (locationHint.location != null && isRegister(locationHint.location)) { 821 return locationHint; 822 } else if (!locationHint.splitChildren.isEmpty()) { 823 // search the first split child that has a register assigned 824 int len = locationHint.splitChildren.size(); 825 for (int i = 0; i < len; i++) { 826 Interval interval = locationHint.splitChildren.get(i); 827 if (interval.location != null && isRegister(interval.location)) { 828 return interval; 829 } 830 } 831 } 832 } 833 834 // no hint interval found that has a register assigned 835 return null; 836 } 837 838 Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, LinearScan allocator) { 839 assert isSplitParent() : "can only be called for split parents"; 840 assert opId >= 0 : "invalid opId (method cannot be called for spill moves)"; 841 842 if (splitChildren.isEmpty()) { 843 assert this.covers(opId, mode) : this + " does not cover " + opId; 844 return this; 845 } else { 846 Interval result = null; 847 int len = splitChildren.size(); 848 849 // in outputMode, the end of the interval (opId == cur.to()) is not valid 850 int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1); 851 852 int i; 853 for (i = 0; i < len; i++) { 854 Interval cur = splitChildren.get(i); 855 if (cur.from() <= opId && opId < cur.to() + toOffset) { 856 if (i > 0) { 857 // exchange current split child to start of list (faster access for next 858 // call) 859 Util.atPutGrow(splitChildren, i, splitChildren.get(0), null); 860 Util.atPutGrow(splitChildren, 0, cur, null); 861 } 862 863 // interval found 864 result = cur; 865 break; 866 } 867 } 868 869 assert checkSplitChild(result, opId, allocator, toOffset, mode); 870 return result; 871 } 872 } 873 874 private boolean checkSplitChild(Interval result, int opId, LinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { 875 if (result == null) { 876 // this is an error 877 StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId); 878 if (!splitChildren.isEmpty()) { 879 Interval firstChild = splitChildren.get(0); 880 Interval lastChild = splitChildren.get(splitChildren.size() - 1); 881 msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")"); 882 } 883 throw new GraalError("Linear Scan Error: %s", msg); 884 } 885 886 if (!splitChildren.isEmpty()) { 887 for (Interval interval : splitChildren) { 888 if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) { 889 /* 890 * Should not happen: Try another compilation as it is very unlikely to happen 891 * again. 892 */ 893 throw new GraalError("two valid result intervals found for opId %d: %d and %d\n%s\n", opId, result.operandNumber, interval.operandNumber, 894 result.logString(allocator), interval.logString(allocator)); 895 } 896 } 897 } 898 assert result.covers(opId, mode) : "opId not covered by interval"; 899 return true; 900 } 901 902 // returns the interval that covers the given opId or null if there is none 903 Interval getIntervalCoveringOpId(int opId) { 904 assert opId >= 0 : "invalid opId"; 905 assert opId < to() : "can only look into the past"; 906 907 if (opId >= from()) { 908 return this; 909 } 910 911 Interval parent = splitParent(); 912 Interval result = null; 913 914 assert !parent.splitChildren.isEmpty() : "no split children available"; 915 int len = parent.splitChildren.size(); 916 917 for (int i = len - 1; i >= 0; i--) { 918 Interval cur = parent.splitChildren.get(i); 919 if (cur.from() <= opId && opId < cur.to()) { 920 assert result == null : "covered by multiple split children " + result + " and " + cur; 921 result = cur; 922 } 923 } 924 925 return result; 926 } 927 928 // returns the last split child that ends before the given opId 929 Interval getSplitChildBeforeOpId(int opId) { 930 assert opId >= 0 : "invalid opId"; 931 932 Interval parent = splitParent(); 933 Interval result = null; 934 935 assert !parent.splitChildren.isEmpty() : "no split children available"; 936 int len = parent.splitChildren.size(); 937 938 for (int i = len - 1; i >= 0; i--) { 939 Interval cur = parent.splitChildren.get(i); 940 if (cur.to() <= opId && (result == null || result.to() < cur.to())) { 941 result = cur; 942 } 943 } 944 945 assert result != null : "no split child found"; 946 return result; 947 } 948 949 // checks if opId is covered by any split child 950 boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) { 951 assert isSplitParent() : "can only be called for split parents"; 952 assert opId >= 0 : "invalid opId (method can not be called for spill moves)"; 953 954 if (splitChildren.isEmpty()) { 955 // simple case if interval was not split 956 return covers(opId, mode); 957 958 } else { 959 // extended case: check all split children 960 int len = splitChildren.size(); 961 for (int i = 0; i < len; i++) { 962 Interval cur = splitChildren.get(i); 963 if (cur.covers(opId, mode)) { 964 return true; 965 } 966 } 967 return false; 968 } 969 } 970 971 private RegisterPriority adaptPriority(RegisterPriority priority) { 972 /* 973 * In case of re-materialized values we require that use-operands are registers, because we 974 * don't have the value in a stack location. (Note that ShouldHaveRegister means that the 975 * operand can also be a StackSlot). 976 */ 977 if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) { 978 return RegisterPriority.MustHaveRegister; 979 } 980 return priority; 981 } 982 983 // Note: use positions are sorted descending . first use has highest index 984 int firstUsage(RegisterPriority minRegisterPriority) { 985 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 986 987 for (int i = usePosList.size() - 1; i >= 0; --i) { 988 RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i)); 989 if (registerPriority.greaterEqual(minRegisterPriority)) { 990 return usePosList.usePos(i); 991 } 992 } 993 return Integer.MAX_VALUE; 994 } 995 996 int nextUsage(RegisterPriority minRegisterPriority, int from) { 997 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 998 999 for (int i = usePosList.size() - 1; i >= 0; --i) { 1000 int usePos = usePosList.usePos(i); 1001 if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { 1002 return usePos; 1003 } 1004 } 1005 return Integer.MAX_VALUE; 1006 } 1007 1008 int nextUsageExact(RegisterPriority exactRegisterPriority, int from) { 1009 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 1010 1011 for (int i = usePosList.size() - 1; i >= 0; --i) { 1012 int usePos = usePosList.usePos(i); 1013 if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) { 1014 return usePos; 1015 } 1016 } 1017 return Integer.MAX_VALUE; 1018 } 1019 1020 int previousUsage(RegisterPriority minRegisterPriority, int from) { 1021 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 1022 1023 int prev = -1; 1024 for (int i = usePosList.size() - 1; i >= 0; --i) { 1025 int usePos = usePosList.usePos(i); 1026 if (usePos > from) { 1027 return prev; 1028 } 1029 if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { 1030 prev = usePos; 1031 } 1032 } 1033 return prev; 1034 } 1035 1036 public void addUsePos(int pos, RegisterPriority registerPriority, boolean detailedAsserts) { 1037 assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this); 1038 1039 // do not add use positions for precolored intervals because they are never used 1040 if (registerPriority != RegisterPriority.None && isVariable(operand)) { 1041 if (detailedAsserts) { 1042 for (int i = 0; i < usePosList.size(); i++) { 1043 assert pos <= usePosList.usePos(i) : "already added a use-position with lower position"; 1044 if (i > 0) { 1045 assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending"; 1046 } 1047 } 1048 } 1049 1050 // Note: addUse is called in descending order, so list gets sorted 1051 // automatically by just appending new use positions 1052 int len = usePosList.size(); 1053 if (len == 0 || usePosList.usePos(len - 1) > pos) { 1054 usePosList.add(pos, registerPriority); 1055 } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) { 1056 assert usePosList.usePos(len - 1) == pos : "list not sorted correctly"; 1057 usePosList.setRegisterPriority(len - 1, registerPriority); 1058 } 1059 } 1060 } 1061 1062 public void addRange(int from, int to) { 1063 assert from < to : "invalid range"; 1064 assert first().isEndMarker() || to < first().next.from : "not inserting at begin of interval"; 1065 assert from <= first().to : "not inserting at begin of interval"; 1066 1067 if (first.from <= to) { 1068 assert !first.isEndMarker(); 1069 // join intersecting ranges 1070 first.from = Math.min(from, first().from); 1071 first.to = Math.max(to, first().to); 1072 } else { 1073 // insert new range 1074 first = new Range(from, to, first()); 1075 } 1076 } 1077 1078 Interval newSplitChild(LinearScan allocator) { 1079 // allocate new interval 1080 Interval parent = splitParent(); 1081 Interval result = allocator.createDerivedInterval(parent); 1082 result.setKind(kind()); 1083 1084 result.splitParent = parent; 1085 result.setLocationHint(parent); 1086 1087 // insert new interval in children-list of parent 1088 if (parent.splitChildren.isEmpty()) { 1089 assert isSplitParent() : "list must be initialized at first split"; 1090 1091 // Create new non-shared list 1092 parent.splitChildren = new ArrayList<>(4); 1093 parent.splitChildren.add(this); 1094 } 1095 parent.splitChildren.add(result); 1096 1097 return result; 1098 } 1099 1100 /** 1101 * Splits this interval at a specified position and returns the remainder as a new <i>child</i> 1102 * interval of this interval's {@linkplain #splitParent() parent} interval. 1103 * <p> 1104 * When an interval is split, a bi-directional link is established between the original 1105 * <i>parent</i> interval and the <i>children</i> intervals that are split off this interval. 1106 * When a split child is split again, the new created interval is a direct child of the original 1107 * parent. That is, there is no tree of split children stored, just a flat list. All split 1108 * children are spilled to the same {@linkplain #spillSlot spill slot}. 1109 * 1110 * @param splitPos the position at which to split this interval 1111 * @param allocator the register allocator context 1112 * @return the child interval split off from this interval 1113 */ 1114 Interval split(int splitPos, LinearScan allocator) { 1115 assert isVariable(operand) : "cannot split fixed intervals"; 1116 1117 // allocate new interval 1118 Interval result = newSplitChild(allocator); 1119 1120 // split the ranges 1121 Range prev = null; 1122 Range cur = first; 1123 while (!cur.isEndMarker() && cur.to <= splitPos) { 1124 prev = cur; 1125 cur = cur.next; 1126 } 1127 assert !cur.isEndMarker() : "split interval after end of last range"; 1128 1129 if (cur.from < splitPos) { 1130 result.first = new Range(splitPos, cur.to, cur.next); 1131 cur.to = splitPos; 1132 cur.next = allocator.rangeEndMarker; 1133 1134 } else { 1135 assert prev != null : "split before start of first range"; 1136 result.first = cur; 1137 prev.next = allocator.rangeEndMarker; 1138 } 1139 result.current = result.first; 1140 cachedTo = -1; // clear cached value 1141 1142 // split list of use positions 1143 result.usePosList = usePosList.splitAt(splitPos); 1144 1145 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) { 1146 for (int i = 0; i < usePosList.size(); i++) { 1147 assert usePosList.usePos(i) < splitPos; 1148 } 1149 for (int i = 0; i < result.usePosList.size(); i++) { 1150 assert result.usePosList.usePos(i) >= splitPos; 1151 } 1152 } 1153 return result; 1154 } 1155 1156 /** 1157 * Splits this interval at a specified position and returns the head as a new interval (this 1158 * interval is the tail). 1159 * 1160 * Currently, only the first range can be split, and the new interval must not have split 1161 * positions 1162 */ 1163 Interval splitFromStart(int splitPos, LinearScan allocator) { 1164 assert isVariable(operand) : "cannot split fixed intervals"; 1165 assert splitPos > from() && splitPos < to() : "can only split inside interval"; 1166 assert splitPos > first.from && splitPos <= first.to : "can only split inside first range"; 1167 assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present"; 1168 1169 // allocate new interval 1170 Interval result = newSplitChild(allocator); 1171 1172 // the new interval has only one range (checked by assertion above, 1173 // so the splitting of the ranges is very simple 1174 result.addRange(first.from, splitPos); 1175 1176 if (splitPos == first.to) { 1177 assert !first.next.isEndMarker() : "must not be at end"; 1178 first = first.next; 1179 } else { 1180 first.from = splitPos; 1181 } 1182 1183 return result; 1184 } 1185 1186 // returns true if the opId is inside the interval 1187 boolean covers(int opId, LIRInstruction.OperandMode mode) { 1188 Range cur = first; 1189 1190 while (!cur.isEndMarker() && cur.to < opId) { 1191 cur = cur.next; 1192 } 1193 if (!cur.isEndMarker()) { 1194 assert cur.to != cur.next.from : "ranges not separated"; 1195 1196 if (mode == LIRInstruction.OperandMode.DEF) { 1197 return cur.from <= opId && opId < cur.to; 1198 } else { 1199 return cur.from <= opId && opId <= cur.to; 1200 } 1201 } 1202 return false; 1203 } 1204 1205 // returns true if the interval has any hole between holeFrom and holeTo 1206 // (even if the hole has only the length 1) 1207 boolean hasHoleBetween(int holeFrom, int holeTo) { 1208 assert holeFrom < holeTo : "check"; 1209 assert from() <= holeFrom && holeTo <= to() : "index out of interval"; 1210 1211 Range cur = first; 1212 while (!cur.isEndMarker()) { 1213 assert cur.to < cur.next.from : "no space between ranges"; 1214 1215 // hole-range starts before this range . hole 1216 if (holeFrom < cur.from) { 1217 return true; 1218 1219 // hole-range completely inside this range . no hole 1220 } else { 1221 if (holeTo <= cur.to) { 1222 return false; 1223 1224 // overlapping of hole-range with this range . hole 1225 } else { 1226 if (holeFrom <= cur.to) { 1227 return true; 1228 } 1229 } 1230 } 1231 1232 cur = cur.next; 1233 } 1234 1235 return false; 1236 } 1237 1238 @Override 1239 public String toString() { 1240 String from = "?"; 1241 String to = "?"; 1242 if (first != null && !first.isEndMarker()) { 1243 from = String.valueOf(from()); 1244 // to() may cache a computed value, modifying the current object, which is a bad idea 1245 // for a printing function. Compute it directly instead. 1246 to = String.valueOf(calcTo()); 1247 } 1248 String locationString = this.location == null ? "" : "@" + this.location; 1249 return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; 1250 } 1251 1252 /** 1253 * Gets the use position information for this interval. 1254 */ 1255 public UsePosList usePosList() { 1256 return usePosList; 1257 } 1258 1259 /** 1260 * Gets a single line string for logging the details of this interval to a log stream. 1261 * 1262 * @param allocator the register allocator context 1263 */ 1264 public String logString(LinearScan allocator) { 1265 StringBuilder buf = new StringBuilder(100); 1266 buf.append(operandNumber).append(':').append(operand).append(' '); 1267 if (!isRegister(operand)) { 1268 if (location != null) { 1269 buf.append("location{").append(location).append("} "); 1270 } 1271 } 1272 1273 buf.append("hints{").append(splitParent.operandNumber); 1274 Interval hint = locationHint(false); 1275 if (hint != null && hint.operandNumber != splitParent.operandNumber) { 1276 buf.append(", ").append(hint.operandNumber); 1277 } 1278 buf.append("} ranges{"); 1279 1280 // print ranges 1281 Range cur = first; 1282 while (!cur.isEndMarker()) { 1283 if (cur != first) { 1284 buf.append(", "); 1285 } 1286 buf.append(cur); 1287 cur = cur.next; 1288 assert cur != null : "range list not closed with range sentinel"; 1289 } 1290 buf.append("} uses{"); 1291 1292 // print use positions 1293 int prev = -1; 1294 for (int i = usePosList.size() - 1; i >= 0; --i) { 1295 assert prev < usePosList.usePos(i) : "use positions not sorted"; 1296 if (i != usePosList.size() - 1) { 1297 buf.append(", "); 1298 } 1299 buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i)); 1300 prev = usePosList.usePos(i); 1301 } 1302 buf.append("} spill-state{").append(spillState()).append("}"); 1303 if (canMaterialize()) { 1304 buf.append(" (remat:").append(getMaterializedValue().toString()).append(")"); 1305 } 1306 return buf.toString(); 1307 } 1308 1309 List<Interval> getSplitChildren() { 1310 return Collections.unmodifiableList(splitChildren); 1311 } 1312 } 1313