Interval.java revision 12968:4d8a004e5c6d
1254885Sdumbbell/* 2254885Sdumbbell * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved. 3254885Sdumbbell * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4254885Sdumbbell * 5254885Sdumbbell * This code is free software; you can redistribute it and/or modify it 6254885Sdumbbell * under the terms of the GNU General Public License version 2 only, as 7254885Sdumbbell * published by the Free Software Foundation. 8254885Sdumbbell * 9254885Sdumbbell * This code is distributed in the hope that it will be useful, but WITHOUT 10254885Sdumbbell * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11254885Sdumbbell * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12254885Sdumbbell * version 2 for more details (a copy is included in the LICENSE file that 13254885Sdumbbell * accompanied this code). 14254885Sdumbbell * 15254885Sdumbbell * You should have received a copy of the GNU General Public License version 16254885Sdumbbell * 2 along with this work; if not, write to the Free Software Foundation, 17254885Sdumbbell * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18254885Sdumbbell * 19254885Sdumbbell * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20254885Sdumbbell * or visit www.oracle.com if you need additional information or have any 21254885Sdumbbell * questions. 22254885Sdumbbell */ 23254885Sdumbbellpackage org.graalvm.compiler.lir.alloc.lsra; 24254885Sdumbbell 25254885Sdumbbellimport static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts; 26254885Sdumbbellimport static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 27254885Sdumbbellimport static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 28254885Sdumbbellimport static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 29254885Sdumbbellimport static jdk.vm.ci.code.ValueUtil.asRegister; 30254885Sdumbbellimport static jdk.vm.ci.code.ValueUtil.isIllegal; 31254885Sdumbbellimport static jdk.vm.ci.code.ValueUtil.isRegister; 32254885Sdumbbellimport static jdk.vm.ci.code.ValueUtil.isStackSlot; 33254885Sdumbbell 34254885Sdumbbellimport java.util.ArrayList; 35254885Sdumbbellimport java.util.Collections; 36254885Sdumbbellimport java.util.EnumSet; 37254885Sdumbbellimport java.util.List; 38254885Sdumbbell 39254885Sdumbbellimport org.graalvm.compiler.core.common.LIRKind; 40254885Sdumbbellimport org.graalvm.compiler.core.common.util.IntList; 41254885Sdumbbellimport org.graalvm.compiler.core.common.util.Util; 42254885Sdumbbellimport org.graalvm.compiler.debug.GraalError; 43254885Sdumbbellimport org.graalvm.compiler.lir.LIRInstruction; 44254885Sdumbbellimport org.graalvm.compiler.lir.Variable; 45254885Sdumbbellimport jdk.vm.ci.code.RegisterValue; 46254885Sdumbbellimport jdk.vm.ci.code.StackSlot; 47254885Sdumbbellimport jdk.vm.ci.meta.AllocatableValue; 48254885Sdumbbellimport jdk.vm.ci.meta.Constant; 49254885Sdumbbellimport jdk.vm.ci.meta.Value; 50254885Sdumbbellimport jdk.vm.ci.meta.ValueKind; 51254885Sdumbbell 52254885Sdumbbell/** 53254885Sdumbbell * Represents an interval in the {@linkplain LinearScan linear scan register allocator}. 54254885Sdumbbell */ 55254885Sdumbbellpublic final class Interval { 56254885Sdumbbell 57254885Sdumbbell /** 58254885Sdumbbell * A set of interval lists, one per {@linkplain RegisterBinding binding} type. 59254885Sdumbbell */ 60254885Sdumbbell static final class RegisterBindingLists { 61254885Sdumbbell 62254885Sdumbbell /** 63254885Sdumbbell * List of intervals whose binding is currently {@link RegisterBinding#Fixed}. 64254885Sdumbbell */ 65254885Sdumbbell public Interval fixed; 66254885Sdumbbell 67254885Sdumbbell /** 68254885Sdumbbell * List of intervals whose binding is currently {@link RegisterBinding#Any}. 69254885Sdumbbell */ 70254885Sdumbbell public Interval any; 71254885Sdumbbell 72254885Sdumbbell /** 73254885Sdumbbell * List of intervals whose binding is currently {@link RegisterBinding#Stack}. 74254885Sdumbbell */ 75254885Sdumbbell public Interval stack; 76254885Sdumbbell 77254885Sdumbbell RegisterBindingLists(Interval fixed, Interval any, Interval stack) { 78254885Sdumbbell this.fixed = fixed; 79254885Sdumbbell this.any = any; 80254885Sdumbbell this.stack = stack; 81254885Sdumbbell } 82254885Sdumbbell 83254885Sdumbbell /** 84254885Sdumbbell * Gets the list for a specified binding. 85254885Sdumbbell * 86254885Sdumbbell * @param binding specifies the list to be returned 87254885Sdumbbell * @return the list of intervals whose binding is {@code binding} 88254885Sdumbbell */ 89254885Sdumbbell public Interval get(RegisterBinding binding) { 90254885Sdumbbell switch (binding) { 91254885Sdumbbell case Any: 92254885Sdumbbell return any; 93254885Sdumbbell case Fixed: 94254885Sdumbbell return fixed; 95254885Sdumbbell case Stack: 96254885Sdumbbell return stack; 97254885Sdumbbell } 98254885Sdumbbell throw GraalError.shouldNotReachHere(); 99254885Sdumbbell } 100254885Sdumbbell 101254885Sdumbbell /** 102254885Sdumbbell * Sets the list for a specified binding. 103254885Sdumbbell * 104254885Sdumbbell * @param binding specifies the list to be replaced 105254885Sdumbbell * @param list a list of intervals whose binding is {@code binding} 106254885Sdumbbell */ 107254885Sdumbbell public void set(RegisterBinding binding, Interval list) { 108254885Sdumbbell assert list != null; 109254885Sdumbbell switch (binding) { 110254885Sdumbbell case Any: 111254885Sdumbbell any = list; 112254885Sdumbbell break; 113254885Sdumbbell case Fixed: 114254885Sdumbbell fixed = list; 115254885Sdumbbell break; 116254885Sdumbbell case Stack: 117254885Sdumbbell stack = list; 118254885Sdumbbell break; 119254885Sdumbbell } 120254885Sdumbbell } 121254885Sdumbbell 122254885Sdumbbell /** 123254885Sdumbbell * Adds an interval to a list sorted by {@linkplain Interval#currentFrom() current from} 124254885Sdumbbell * positions. 125254885Sdumbbell * 126254885Sdumbbell * @param binding specifies the list to be updated 127254885Sdumbbell * @param interval the interval to add 128254885Sdumbbell */ 129254885Sdumbbell public void addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval) { 130254885Sdumbbell Interval list = get(binding); 131254885Sdumbbell Interval prev = null; 132254885Sdumbbell Interval cur = list; 133254885Sdumbbell while (cur.currentFrom() < interval.currentFrom()) { 134254885Sdumbbell prev = cur; 135254885Sdumbbell cur = cur.next; 136254885Sdumbbell } 137254885Sdumbbell Interval result = list; 138254885Sdumbbell if (prev == null) { 139254885Sdumbbell // add to head of list 140254885Sdumbbell result = interval; 141254885Sdumbbell } else { 142254885Sdumbbell // add before 'cur' 143254885Sdumbbell prev.next = interval; 144254885Sdumbbell } 145254885Sdumbbell interval.next = cur; 146254885Sdumbbell set(binding, result); 147254885Sdumbbell } 148254885Sdumbbell 149254885Sdumbbell /** 150254885Sdumbbell * Adds an interval to a list sorted by {@linkplain Interval#from() start} positions and 151254885Sdumbbell * {@linkplain Interval#firstUsage(RegisterPriority) first usage} positions. 152254885Sdumbbell * 153254885Sdumbbell * @param binding specifies the list to be updated 154254885Sdumbbell * @param interval the interval to add 155254885Sdumbbell */ 156254885Sdumbbell public void addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval) { 157254885Sdumbbell Interval list = get(binding); 158254885Sdumbbell Interval prev = null; 159254885Sdumbbell Interval cur = list; 160254885Sdumbbell while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) { 161254885Sdumbbell prev = cur; 162254885Sdumbbell cur = cur.next; 163254885Sdumbbell } 164254885Sdumbbell if (prev == null) { 165254885Sdumbbell list = interval; 166254885Sdumbbell } else { 167254885Sdumbbell prev.next = interval; 168254885Sdumbbell } 169254885Sdumbbell interval.next = cur; 170254885Sdumbbell set(binding, list); 171254885Sdumbbell } 172254885Sdumbbell 173254885Sdumbbell /** 174254885Sdumbbell * Removes an interval from a list. 175254885Sdumbbell * 176254885Sdumbbell * @param binding specifies the list to be updated 177254885Sdumbbell * @param i the interval to remove 178254885Sdumbbell */ 179254885Sdumbbell public void remove(RegisterBinding binding, Interval i) { 180254885Sdumbbell Interval list = get(binding); 181254885Sdumbbell Interval prev = null; 182254885Sdumbbell Interval cur = list; 183254885Sdumbbell while (cur != i) { 184254885Sdumbbell assert cur != null && !cur.isEndMarker() : "interval has not been found in list: " + i; 185254885Sdumbbell prev = cur; 186254885Sdumbbell cur = cur.next; 187254885Sdumbbell } 188254885Sdumbbell if (prev == null) { 189254885Sdumbbell set(binding, cur.next); 190254885Sdumbbell } else { 191254885Sdumbbell prev.next = cur.next; 192254885Sdumbbell } 193254885Sdumbbell } 194254885Sdumbbell } 195254885Sdumbbell 196254885Sdumbbell /** 197254885Sdumbbell * Constants denoting the register usage priority for an interval. The constants are declared in 198254885Sdumbbell * increasing order of priority are are used to optimize spilling when multiple overlapping 199254885Sdumbbell * intervals compete for limited registers. 200254885Sdumbbell */ 201254885Sdumbbell public enum RegisterPriority { 202254885Sdumbbell /** 203254885Sdumbbell * No special reason for an interval to be allocated a register. 204254885Sdumbbell */ 205254885Sdumbbell None, 206254885Sdumbbell 207254885Sdumbbell /** 208254885Sdumbbell * Priority level for intervals live at the end of a loop. 209254885Sdumbbell */ 210254885Sdumbbell LiveAtLoopEnd, 211254885Sdumbbell 212254885Sdumbbell /** 213254885Sdumbbell * Priority level for intervals that should be allocated to a register. 214254885Sdumbbell */ 215254885Sdumbbell ShouldHaveRegister, 216254885Sdumbbell 217254885Sdumbbell /** 218254885Sdumbbell * Priority level for intervals that must be allocated to a register. 219254885Sdumbbell */ 220254885Sdumbbell MustHaveRegister; 221254885Sdumbbell 222254885Sdumbbell public static final RegisterPriority[] VALUES = values(); 223254885Sdumbbell 224254885Sdumbbell /** 225254885Sdumbbell * Determines if this priority is higher than or equal to a given priority. 226254885Sdumbbell */ 227254885Sdumbbell public boolean greaterEqual(RegisterPriority other) { 228254885Sdumbbell return ordinal() >= other.ordinal(); 229254885Sdumbbell } 230254885Sdumbbell 231254885Sdumbbell /** 232254885Sdumbbell * Determines if this priority is lower than a given priority. 233254885Sdumbbell */ 234254885Sdumbbell public boolean lessThan(RegisterPriority other) { 235254885Sdumbbell return ordinal() < other.ordinal(); 236254885Sdumbbell } 237254885Sdumbbell } 238254885Sdumbbell 239254885Sdumbbell /** 240254885Sdumbbell * Constants denoting whether an interval is bound to a specific register. This models platform 241254885Sdumbbell * dependencies on register usage for certain instructions. 242254885Sdumbbell */ 243254885Sdumbbell enum RegisterBinding { 244254885Sdumbbell /** 245254885Sdumbbell * Interval is bound to a specific register as required by the platform. 246254885Sdumbbell */ 247254885Sdumbbell Fixed, 248254885Sdumbbell 249254885Sdumbbell /** 250254885Sdumbbell * Interval has no specific register requirements. 251254885Sdumbbell */ 252254885Sdumbbell Any, 253254885Sdumbbell 254254885Sdumbbell /** 255254885Sdumbbell * Interval is bound to a stack slot. 256254885Sdumbbell */ 257254885Sdumbbell Stack; 258254885Sdumbbell 259254885Sdumbbell public static final RegisterBinding[] VALUES = values(); 260254885Sdumbbell } 261254885Sdumbbell 262254885Sdumbbell /** 263254885Sdumbbell * Constants denoting the linear-scan states an interval may be in with respect to the 264254885Sdumbbell * {@linkplain Interval#from() start} {@code position} of the interval being processed. 265254885Sdumbbell */ 266254885Sdumbbell enum State { 267254885Sdumbbell /** 268254885Sdumbbell * An interval that starts after {@code position}. 269254885Sdumbbell */ 270254885Sdumbbell Unhandled, 271254885Sdumbbell 272254885Sdumbbell /** 273254885Sdumbbell * An interval that {@linkplain Interval#covers covers} {@code position} and has an assigned 274254885Sdumbbell * register. 275254885Sdumbbell */ 276254885Sdumbbell Active, 277254885Sdumbbell 278254885Sdumbbell /** 279254885Sdumbbell * An interval that starts before and ends after {@code position} but does not 280254885Sdumbbell * {@linkplain Interval#covers cover} it due to a lifetime hole. 281254885Sdumbbell */ 282254885Sdumbbell Inactive, 283254885Sdumbbell 284254885Sdumbbell /** 285254885Sdumbbell * An interval that ends before {@code position} or is spilled to memory. 286254885Sdumbbell */ 287254885Sdumbbell Handled; 288254885Sdumbbell } 289254885Sdumbbell 290254885Sdumbbell /** 291254885Sdumbbell * Constants used in optimization of spilling of an interval. 292254885Sdumbbell */ 293254885Sdumbbell public enum SpillState { 294254885Sdumbbell /** 295254885Sdumbbell * Starting state of calculation: no definition found yet. 296254885Sdumbbell */ 297254885Sdumbbell NoDefinitionFound, 298254885Sdumbbell 299254885Sdumbbell /** 300254885Sdumbbell * One definition has already been found. Two consecutive definitions are treated as one 301254885Sdumbbell * (e.g. a consecutive move and add because of two-operand LIR form). The position of this 302254885Sdumbbell * definition is given by {@link Interval#spillDefinitionPos()}. 303254885Sdumbbell */ 304254885Sdumbbell NoSpillStore, 305254885Sdumbbell 306254885Sdumbbell /** 307254885Sdumbbell * One spill move has already been inserted. 308254885Sdumbbell */ 309254885Sdumbbell OneSpillStore, 310254885Sdumbbell 311254885Sdumbbell /** 312254885Sdumbbell * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere 313254885Sdumbbell * on the dominator path between the definition and the usages. 314254885Sdumbbell */ 315254885Sdumbbell SpillInDominator, 316254885Sdumbbell 317254885Sdumbbell /** 318254885Sdumbbell * The interval should be stored immediately after its definition to prevent multiple 319254885Sdumbbell * redundant stores. 320254885Sdumbbell */ 321254885Sdumbbell StoreAtDefinition, 322254885Sdumbbell 323254885Sdumbbell /** 324254885Sdumbbell * The interval starts in memory (e.g. method parameter), so a store is never necessary. 325254885Sdumbbell */ 326254885Sdumbbell StartInMemory, 327254885Sdumbbell 328254885Sdumbbell /** 329254885Sdumbbell * The interval has more than one definition (e.g. resulting from phi moves), so stores to 330254885Sdumbbell * memory are not optimized. 331254885Sdumbbell */ 332254885Sdumbbell NoOptimization; 333254885Sdumbbell 334254885Sdumbbell public static final EnumSet<SpillState> ALWAYS_IN_MEMORY = EnumSet.of(SpillInDominator, StoreAtDefinition, StartInMemory); 335254885Sdumbbell } 336254885Sdumbbell 337254885Sdumbbell /** 338254885Sdumbbell * List of use positions. Each entry in the list records the use position and register priority 339254885Sdumbbell * associated with the use position. The entries in the list are in descending order of use 340254885Sdumbbell * position. 341254885Sdumbbell * 342254885Sdumbbell */ 343254885Sdumbbell public static final class UsePosList { 344254885Sdumbbell 345254885Sdumbbell private IntList list; 346254885Sdumbbell 347254885Sdumbbell /** 348254885Sdumbbell * Creates a use list. 349254885Sdumbbell * 350254885Sdumbbell * @param initialCapacity the initial capacity of the list in terms of entries 351254885Sdumbbell */ 352254885Sdumbbell public UsePosList(int initialCapacity) { 353254885Sdumbbell list = new IntList(initialCapacity * 2); 354254885Sdumbbell } 355254885Sdumbbell 356254885Sdumbbell private UsePosList(IntList list) { 357254885Sdumbbell this.list = list; 358254885Sdumbbell } 359254885Sdumbbell 360254885Sdumbbell /** 361254885Sdumbbell * Splits this list around a given position. All entries in this list with a use position 362254885Sdumbbell * greater or equal than {@code splitPos} are removed from this list and added to the 363254885Sdumbbell * returned list. 364254885Sdumbbell * 365254885Sdumbbell * @param splitPos the position for the split 366254885Sdumbbell * @return a use position list containing all entries removed from this list that have a use 367254885Sdumbbell * position greater or equal than {@code splitPos} 368254885Sdumbbell */ 369254885Sdumbbell public UsePosList splitAt(int splitPos) { 370254885Sdumbbell int i = size() - 1; 371254885Sdumbbell int len = 0; 372254885Sdumbbell while (i >= 0 && usePos(i) < splitPos) { 373254885Sdumbbell --i; 374254885Sdumbbell len += 2; 375254885Sdumbbell } 376254885Sdumbbell int listSplitIndex = (i + 1) * 2; 377254885Sdumbbell IntList childList = list; 378254885Sdumbbell list = IntList.copy(this.list, listSplitIndex, len); 379254885Sdumbbell childList.setSize(listSplitIndex); 380254885Sdumbbell UsePosList child = new UsePosList(childList); 381254885Sdumbbell return child; 382 } 383 384 /** 385 * Gets the use position at a specified index in this list. 386 * 387 * @param index the index of the entry for which the use position is returned 388 * @return the use position of entry {@code index} in this list 389 */ 390 public int usePos(int index) { 391 return list.get(index << 1); 392 } 393 394 /** 395 * Gets the register priority for the use position at a specified index in this list. 396 * 397 * @param index the index of the entry for which the register priority is returned 398 * @return the register priority of entry {@code index} in this list 399 */ 400 public RegisterPriority registerPriority(int index) { 401 return RegisterPriority.VALUES[list.get((index << 1) + 1)]; 402 } 403 404 public void add(int usePos, RegisterPriority registerPriority) { 405 assert list.size() == 0 || usePos(size() - 1) > usePos; 406 list.add(usePos); 407 list.add(registerPriority.ordinal()); 408 } 409 410 public int size() { 411 return list.size() >> 1; 412 } 413 414 public void removeLowestUsePos() { 415 list.setSize(list.size() - 2); 416 } 417 418 public void setRegisterPriority(int index, RegisterPriority registerPriority) { 419 list.set((index << 1) + 1, registerPriority.ordinal()); 420 } 421 422 @Override 423 public String toString() { 424 StringBuilder buf = new StringBuilder("["); 425 for (int i = size() - 1; i >= 0; --i) { 426 if (buf.length() != 1) { 427 buf.append(", "); 428 } 429 RegisterPriority prio = registerPriority(i); 430 buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio); 431 } 432 return buf.append("]").toString(); 433 } 434 } 435 436 protected static final int END_MARKER_OPERAND_NUMBER = Integer.MIN_VALUE; 437 438 /** 439 * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval 440 * prior to register allocation. 441 */ 442 public final AllocatableValue operand; 443 444 /** 445 * The operand number for this interval's {@linkplain #operand operand}. 446 */ 447 public final int operandNumber; 448 449 /** 450 * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this 451 * interval. In case of a spilled interval which is re-materialized this is 452 * {@link Value#ILLEGAL}. 453 */ 454 private AllocatableValue location; 455 456 /** 457 * The stack slot to which all splits of this interval are spilled if necessary. 458 */ 459 private AllocatableValue spillSlot; 460 461 /** 462 * The kind of this interval. 463 */ 464 private ValueKind<?> kind; 465 466 /** 467 * The head of the list of ranges describing this interval. This list is sorted by 468 * {@linkplain LIRInstruction#id instruction ids}. 469 */ 470 private Range first; 471 472 /** 473 * List of (use-positions, register-priorities) pairs, sorted by use-positions. 474 */ 475 private UsePosList usePosList; 476 477 /** 478 * Iterator used to traverse the ranges of an interval. 479 */ 480 private Range current; 481 482 /** 483 * Link to next interval in a sorted list of intervals that ends with 484 * LinearScan.intervalEndMarker. 485 */ 486 Interval next; 487 488 /** 489 * The linear-scan state of this interval. 490 */ 491 State state; 492 493 private int cachedTo; // cached value: to of last range (-1: not cached) 494 495 /** 496 * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split 497 * parent}, it points to itself. 498 */ 499 private Interval splitParent; 500 501 /** 502 * List of all intervals that are split off from this interval. This is only used if this is a 503 * {@linkplain #isSplitParent() split parent}. 504 */ 505 private List<Interval> splitChildren = Collections.emptyList(); 506 507 /** 508 * Current split child that has been active or inactive last (always stored in split parents). 509 */ 510 private Interval currentSplitChild; 511 512 /** 513 * Specifies if move is inserted between currentSplitChild and this interval when interval gets 514 * active the first time. 515 */ 516 private boolean insertMoveWhenActivated; 517 518 /** 519 * For spill move optimization. 520 */ 521 private SpillState spillState; 522 523 /** 524 * Position where this interval is defined (if defined only once). 525 */ 526 private int spillDefinitionPos; 527 528 /** 529 * This interval should be assigned the same location as the hint interval. 530 */ 531 private Interval locationHint; 532 533 /** 534 * The value with which a spilled child interval can be re-materialized. Currently this must be 535 * a Constant. 536 */ 537 private Constant materializedValue; 538 539 /** 540 * The number of times {@link #addMaterializationValue(Constant)} is called. 541 */ 542 private int numMaterializationValuesAdded; 543 544 void assignLocation(AllocatableValue newLocation) { 545 if (isRegister(newLocation)) { 546 assert this.location == null : "cannot re-assign location for " + this; 547 if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) { 548 this.location = asRegister(newLocation).asValue(kind); 549 return; 550 } 551 } else if (isIllegal(newLocation)) { 552 assert canMaterialize(); 553 } else { 554 assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this; 555 assert isStackSlotValue(newLocation); 556 assert !newLocation.getValueKind().equals(LIRKind.Illegal); 557 assert newLocation.getValueKind().equals(this.kind); 558 } 559 this.location = newLocation; 560 } 561 562 /** Returns true is this is the sentinel interval that denotes the end of an interval list. */ 563 public boolean isEndMarker() { 564 return operandNumber == END_MARKER_OPERAND_NUMBER; 565 } 566 567 /** 568 * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to 569 * this interval. 570 */ 571 public AllocatableValue location() { 572 return location; 573 } 574 575 public ValueKind<?> kind() { 576 assert !isRegister(operand) : "cannot access type for fixed interval"; 577 return kind; 578 } 579 580 public void setKind(ValueKind<?> kind) { 581 assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type"; 582 this.kind = kind; 583 } 584 585 public Range first() { 586 return first; 587 } 588 589 public int from() { 590 return first.from; 591 } 592 593 int to() { 594 if (cachedTo == -1) { 595 cachedTo = calcTo(); 596 } 597 assert cachedTo == calcTo() : "invalid cached value"; 598 return cachedTo; 599 } 600 601 int numUsePositions() { 602 return usePosList.size(); 603 } 604 605 public void setLocationHint(Interval interval) { 606 locationHint = interval; 607 } 608 609 public boolean isSplitParent() { 610 return splitParent == this; 611 } 612 613 boolean isSplitChild() { 614 return splitParent != this; 615 } 616 617 /** 618 * Gets the split parent for this interval. 619 */ 620 public Interval splitParent() { 621 assert splitParent.isSplitParent() : "not a split parent: " + this; 622 return splitParent; 623 } 624 625 /** 626 * Gets the canonical spill slot for this interval. 627 */ 628 public AllocatableValue spillSlot() { 629 return splitParent().spillSlot; 630 } 631 632 public void setSpillSlot(AllocatableValue slot) { 633 assert isStackSlotValue(slot); 634 assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot"; 635 splitParent().spillSlot = slot; 636 } 637 638 Interval currentSplitChild() { 639 return splitParent().currentSplitChild; 640 } 641 642 void makeCurrentSplitChild() { 643 splitParent().currentSplitChild = this; 644 } 645 646 boolean insertMoveWhenActivated() { 647 return insertMoveWhenActivated; 648 } 649 650 void setInsertMoveWhenActivated(boolean b) { 651 insertMoveWhenActivated = b; 652 } 653 654 // for spill optimization 655 public SpillState spillState() { 656 return splitParent().spillState; 657 } 658 659 public int spillDefinitionPos() { 660 return splitParent().spillDefinitionPos; 661 } 662 663 public void setSpillState(SpillState state) { 664 assert state.ordinal() >= spillState().ordinal() : "state cannot decrease"; 665 splitParent().spillState = state; 666 } 667 668 public void setSpillDefinitionPos(int pos) { 669 assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice"; 670 splitParent().spillDefinitionPos = pos; 671 } 672 673 // returns true if this interval has a shadow copy on the stack that is always correct 674 public boolean alwaysInMemory() { 675 return SpillState.ALWAYS_IN_MEMORY.contains(spillState()) && !canMaterialize(); 676 } 677 678 void removeFirstUsePos() { 679 usePosList.removeLowestUsePos(); 680 } 681 682 // test intersection 683 boolean intersects(Interval i) { 684 return first.intersects(i.first); 685 } 686 687 int intersectsAt(Interval i) { 688 return first.intersectsAt(i.first); 689 } 690 691 // range iteration 692 void rewindRange() { 693 current = first; 694 } 695 696 void nextRange() { 697 assert !this.isEndMarker() : "not allowed on sentinel"; 698 current = current.next; 699 } 700 701 int currentFrom() { 702 return current.from; 703 } 704 705 int currentTo() { 706 return current.to; 707 } 708 709 boolean currentAtEnd() { 710 return current.isEndMarker(); 711 } 712 713 boolean currentIntersects(Interval it) { 714 return current.intersects(it.current); 715 } 716 717 int currentIntersectsAt(Interval it) { 718 return current.intersectsAt(it.current); 719 } 720 721 Interval(AllocatableValue operand, int operandNumber, Interval intervalEndMarker, Range rangeEndMarker) { 722 assert operand != null; 723 this.operand = operand; 724 this.operandNumber = operandNumber; 725 if (isRegister(operand)) { 726 location = operand; 727 } else { 728 assert isIllegal(operand) || isVariable(operand); 729 } 730 this.kind = LIRKind.Illegal; 731 this.first = rangeEndMarker; 732 this.usePosList = new UsePosList(4); 733 this.current = rangeEndMarker; 734 this.next = intervalEndMarker; 735 this.cachedTo = -1; 736 this.spillState = SpillState.NoDefinitionFound; 737 this.spillDefinitionPos = -1; 738 splitParent = this; 739 currentSplitChild = this; 740 } 741 742 /** 743 * Sets the value which is used for re-materialization. 744 */ 745 public void addMaterializationValue(Constant value) { 746 if (numMaterializationValuesAdded == 0) { 747 materializedValue = value; 748 } else { 749 // Interval is defined on multiple places -> no materialization is possible. 750 materializedValue = null; 751 } 752 numMaterializationValuesAdded++; 753 } 754 755 /** 756 * Returns true if this interval can be re-materialized when spilled. This means that no 757 * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored. 758 */ 759 public boolean canMaterialize() { 760 return getMaterializedValue() != null; 761 } 762 763 /** 764 * Returns a value which can be moved to a register instead of a restore-move from stack. 765 */ 766 public Constant getMaterializedValue() { 767 return splitParent().materializedValue; 768 } 769 770 int calcTo() { 771 assert !first.isEndMarker() : "interval has no range"; 772 773 Range r = first; 774 while (!r.next.isEndMarker()) { 775 r = r.next; 776 } 777 return r.to; 778 } 779 780 // consistency check of split-children 781 boolean checkSplitChildren() { 782 if (!splitChildren.isEmpty()) { 783 assert isSplitParent() : "only split parents can have children"; 784 785 for (int i = 0; i < splitChildren.size(); i++) { 786 Interval i1 = splitChildren.get(i); 787 788 assert i1.splitParent() == this : "not a split child of this interval"; 789 assert i1.kind().equals(kind()) : "must be equal for all split children"; 790 assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children"; 791 792 for (int j = i + 1; j < splitChildren.size(); j++) { 793 Interval i2 = splitChildren.get(j); 794 795 assert !i1.operand.equals(i2.operand) : "same register number"; 796 797 if (i1.from() < i2.from()) { 798 assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping"; 799 } else { 800 assert i2.from() < i1.from() : "intervals start at same opId"; 801 assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping"; 802 } 803 } 804 } 805 } 806 807 return true; 808 } 809 810 public Interval locationHint(boolean searchSplitChild) { 811 if (!searchSplitChild) { 812 return locationHint; 813 } 814 815 if (locationHint != null) { 816 assert locationHint.isSplitParent() : "ony split parents are valid hint registers"; 817 818 if (locationHint.location != null && isRegister(locationHint.location)) { 819 return locationHint; 820 } else if (!locationHint.splitChildren.isEmpty()) { 821 // search the first split child that has a register assigned 822 int len = locationHint.splitChildren.size(); 823 for (int i = 0; i < len; i++) { 824 Interval interval = locationHint.splitChildren.get(i); 825 if (interval.location != null && isRegister(interval.location)) { 826 return interval; 827 } 828 } 829 } 830 } 831 832 // no hint interval found that has a register assigned 833 return null; 834 } 835 836 Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, LinearScan allocator) { 837 assert isSplitParent() : "can only be called for split parents"; 838 assert opId >= 0 : "invalid opId (method cannot be called for spill moves)"; 839 840 if (splitChildren.isEmpty()) { 841 assert this.covers(opId, mode) : this + " does not cover " + opId; 842 return this; 843 } else { 844 Interval result = null; 845 int len = splitChildren.size(); 846 847 // in outputMode, the end of the interval (opId == cur.to()) is not valid 848 int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1); 849 850 int i; 851 for (i = 0; i < len; i++) { 852 Interval cur = splitChildren.get(i); 853 if (cur.from() <= opId && opId < cur.to() + toOffset) { 854 if (i > 0) { 855 // exchange current split child to start of list (faster access for next 856 // call) 857 Util.atPutGrow(splitChildren, i, splitChildren.get(0), null); 858 Util.atPutGrow(splitChildren, 0, cur, null); 859 } 860 861 // interval found 862 result = cur; 863 break; 864 } 865 } 866 867 assert checkSplitChild(result, opId, allocator, toOffset, mode); 868 return result; 869 } 870 } 871 872 private boolean checkSplitChild(Interval result, int opId, LinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) { 873 if (result == null) { 874 // this is an error 875 StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId); 876 if (!splitChildren.isEmpty()) { 877 Interval firstChild = splitChildren.get(0); 878 Interval lastChild = splitChildren.get(splitChildren.size() - 1); 879 msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")"); 880 } 881 throw new GraalError("Linear Scan Error: %s", msg); 882 } 883 884 if (!splitChildren.isEmpty()) { 885 for (Interval interval : splitChildren) { 886 if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) { 887 /* 888 * Should not happen: Try another compilation as it is very unlikely to happen 889 * again. 890 */ 891 throw new GraalError("two valid result intervals found for opId %d: %d and %d\n%s\n", opId, result.operandNumber, interval.operandNumber, 892 result.logString(allocator), interval.logString(allocator)); 893 } 894 } 895 } 896 assert result.covers(opId, mode) : "opId not covered by interval"; 897 return true; 898 } 899 900 // returns the interval that covers the given opId or null if there is none 901 Interval getIntervalCoveringOpId(int opId) { 902 assert opId >= 0 : "invalid opId"; 903 assert opId < to() : "can only look into the past"; 904 905 if (opId >= from()) { 906 return this; 907 } 908 909 Interval parent = splitParent(); 910 Interval result = null; 911 912 assert !parent.splitChildren.isEmpty() : "no split children available"; 913 int len = parent.splitChildren.size(); 914 915 for (int i = len - 1; i >= 0; i--) { 916 Interval cur = parent.splitChildren.get(i); 917 if (cur.from() <= opId && opId < cur.to()) { 918 assert result == null : "covered by multiple split children " + result + " and " + cur; 919 result = cur; 920 } 921 } 922 923 return result; 924 } 925 926 // returns the last split child that ends before the given opId 927 Interval getSplitChildBeforeOpId(int opId) { 928 assert opId >= 0 : "invalid opId"; 929 930 Interval parent = splitParent(); 931 Interval result = null; 932 933 assert !parent.splitChildren.isEmpty() : "no split children available"; 934 int len = parent.splitChildren.size(); 935 936 for (int i = len - 1; i >= 0; i--) { 937 Interval cur = parent.splitChildren.get(i); 938 if (cur.to() <= opId && (result == null || result.to() < cur.to())) { 939 result = cur; 940 } 941 } 942 943 assert result != null : "no split child found"; 944 return result; 945 } 946 947 // checks if opId is covered by any split child 948 boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) { 949 assert isSplitParent() : "can only be called for split parents"; 950 assert opId >= 0 : "invalid opId (method can not be called for spill moves)"; 951 952 if (splitChildren.isEmpty()) { 953 // simple case if interval was not split 954 return covers(opId, mode); 955 956 } else { 957 // extended case: check all split children 958 int len = splitChildren.size(); 959 for (int i = 0; i < len; i++) { 960 Interval cur = splitChildren.get(i); 961 if (cur.covers(opId, mode)) { 962 return true; 963 } 964 } 965 return false; 966 } 967 } 968 969 private RegisterPriority adaptPriority(RegisterPriority priority) { 970 /* 971 * In case of re-materialized values we require that use-operands are registers, because we 972 * don't have the value in a stack location. (Note that ShouldHaveRegister means that the 973 * operand can also be a StackSlot). 974 */ 975 if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) { 976 return RegisterPriority.MustHaveRegister; 977 } 978 return priority; 979 } 980 981 // Note: use positions are sorted descending . first use has highest index 982 int firstUsage(RegisterPriority minRegisterPriority) { 983 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 984 985 for (int i = usePosList.size() - 1; i >= 0; --i) { 986 RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i)); 987 if (registerPriority.greaterEqual(minRegisterPriority)) { 988 return usePosList.usePos(i); 989 } 990 } 991 return Integer.MAX_VALUE; 992 } 993 994 int nextUsage(RegisterPriority minRegisterPriority, int from) { 995 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 996 997 for (int i = usePosList.size() - 1; i >= 0; --i) { 998 int usePos = usePosList.usePos(i); 999 if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { 1000 return usePos; 1001 } 1002 } 1003 return Integer.MAX_VALUE; 1004 } 1005 1006 int nextUsageExact(RegisterPriority exactRegisterPriority, int from) { 1007 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 1008 1009 for (int i = usePosList.size() - 1; i >= 0; --i) { 1010 int usePos = usePosList.usePos(i); 1011 if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) { 1012 return usePos; 1013 } 1014 } 1015 return Integer.MAX_VALUE; 1016 } 1017 1018 int previousUsage(RegisterPriority minRegisterPriority, int from) { 1019 assert isVariable(operand) : "cannot access use positions for fixed intervals"; 1020 1021 int prev = -1; 1022 for (int i = usePosList.size() - 1; i >= 0; --i) { 1023 int usePos = usePosList.usePos(i); 1024 if (usePos > from) { 1025 return prev; 1026 } 1027 if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) { 1028 prev = usePos; 1029 } 1030 } 1031 return prev; 1032 } 1033 1034 public void addUsePos(int pos, RegisterPriority registerPriority, boolean detailedAsserts) { 1035 assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this); 1036 1037 // do not add use positions for precolored intervals because they are never used 1038 if (registerPriority != RegisterPriority.None && isVariable(operand)) { 1039 if (detailedAsserts) { 1040 for (int i = 0; i < usePosList.size(); i++) { 1041 assert pos <= usePosList.usePos(i) : "already added a use-position with lower position"; 1042 if (i > 0) { 1043 assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending"; 1044 } 1045 } 1046 } 1047 1048 // Note: addUse is called in descending order, so list gets sorted 1049 // automatically by just appending new use positions 1050 int len = usePosList.size(); 1051 if (len == 0 || usePosList.usePos(len - 1) > pos) { 1052 usePosList.add(pos, registerPriority); 1053 } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) { 1054 assert usePosList.usePos(len - 1) == pos : "list not sorted correctly"; 1055 usePosList.setRegisterPriority(len - 1, registerPriority); 1056 } 1057 } 1058 } 1059 1060 public void addRange(int from, int to) { 1061 assert from < to : "invalid range"; 1062 assert first().isEndMarker() || to < first().next.from : "not inserting at begin of interval"; 1063 assert from <= first().to : "not inserting at begin of interval"; 1064 1065 if (first.from <= to) { 1066 assert !first.isEndMarker(); 1067 // join intersecting ranges 1068 first.from = Math.min(from, first().from); 1069 first.to = Math.max(to, first().to); 1070 } else { 1071 // insert new range 1072 first = new Range(from, to, first()); 1073 } 1074 } 1075 1076 Interval newSplitChild(LinearScan allocator) { 1077 // allocate new interval 1078 Interval parent = splitParent(); 1079 Interval result = allocator.createDerivedInterval(parent); 1080 result.setKind(kind()); 1081 1082 result.splitParent = parent; 1083 result.setLocationHint(parent); 1084 1085 // insert new interval in children-list of parent 1086 if (parent.splitChildren.isEmpty()) { 1087 assert isSplitParent() : "list must be initialized at first split"; 1088 1089 // Create new non-shared list 1090 parent.splitChildren = new ArrayList<>(4); 1091 parent.splitChildren.add(this); 1092 } 1093 parent.splitChildren.add(result); 1094 1095 return result; 1096 } 1097 1098 /** 1099 * Splits this interval at a specified position and returns the remainder as a new <i>child</i> 1100 * interval of this interval's {@linkplain #splitParent() parent} interval. 1101 * <p> 1102 * When an interval is split, a bi-directional link is established between the original 1103 * <i>parent</i> interval and the <i>children</i> intervals that are split off this interval. 1104 * When a split child is split again, the new created interval is a direct child of the original 1105 * parent. That is, there is no tree of split children stored, just a flat list. All split 1106 * children are spilled to the same {@linkplain #spillSlot spill slot}. 1107 * 1108 * @param splitPos the position at which to split this interval 1109 * @param allocator the register allocator context 1110 * @return the child interval split off from this interval 1111 */ 1112 Interval split(int splitPos, LinearScan allocator) { 1113 assert isVariable(operand) : "cannot split fixed intervals"; 1114 1115 // allocate new interval 1116 Interval result = newSplitChild(allocator); 1117 1118 // split the ranges 1119 Range prev = null; 1120 Range cur = first; 1121 while (!cur.isEndMarker() && cur.to <= splitPos) { 1122 prev = cur; 1123 cur = cur.next; 1124 } 1125 assert !cur.isEndMarker() : "split interval after end of last range"; 1126 1127 if (cur.from < splitPos) { 1128 result.first = new Range(splitPos, cur.to, cur.next); 1129 cur.to = splitPos; 1130 cur.next = allocator.rangeEndMarker; 1131 1132 } else { 1133 assert prev != null : "split before start of first range"; 1134 result.first = cur; 1135 prev.next = allocator.rangeEndMarker; 1136 } 1137 result.current = result.first; 1138 cachedTo = -1; // clear cached value 1139 1140 // split list of use positions 1141 result.usePosList = usePosList.splitAt(splitPos); 1142 1143 if (DetailedAsserts.getValue(allocator.getOptions())) { 1144 for (int i = 0; i < usePosList.size(); i++) { 1145 assert usePosList.usePos(i) < splitPos; 1146 } 1147 for (int i = 0; i < result.usePosList.size(); i++) { 1148 assert result.usePosList.usePos(i) >= splitPos; 1149 } 1150 } 1151 return result; 1152 } 1153 1154 /** 1155 * Splits this interval at a specified position and returns the head as a new interval (this 1156 * interval is the tail). 1157 * 1158 * Currently, only the first range can be split, and the new interval must not have split 1159 * positions 1160 */ 1161 Interval splitFromStart(int splitPos, LinearScan allocator) { 1162 assert isVariable(operand) : "cannot split fixed intervals"; 1163 assert splitPos > from() && splitPos < to() : "can only split inside interval"; 1164 assert splitPos > first.from && splitPos <= first.to : "can only split inside first range"; 1165 assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present"; 1166 1167 // allocate new interval 1168 Interval result = newSplitChild(allocator); 1169 1170 // the new interval has only one range (checked by assertion above, 1171 // so the splitting of the ranges is very simple 1172 result.addRange(first.from, splitPos); 1173 1174 if (splitPos == first.to) { 1175 assert !first.next.isEndMarker() : "must not be at end"; 1176 first = first.next; 1177 } else { 1178 first.from = splitPos; 1179 } 1180 1181 return result; 1182 } 1183 1184 // returns true if the opId is inside the interval 1185 boolean covers(int opId, LIRInstruction.OperandMode mode) { 1186 Range cur = first; 1187 1188 while (!cur.isEndMarker() && cur.to < opId) { 1189 cur = cur.next; 1190 } 1191 if (!cur.isEndMarker()) { 1192 assert cur.to != cur.next.from : "ranges not separated"; 1193 1194 if (mode == LIRInstruction.OperandMode.DEF) { 1195 return cur.from <= opId && opId < cur.to; 1196 } else { 1197 return cur.from <= opId && opId <= cur.to; 1198 } 1199 } 1200 return false; 1201 } 1202 1203 // returns true if the interval has any hole between holeFrom and holeTo 1204 // (even if the hole has only the length 1) 1205 boolean hasHoleBetween(int holeFrom, int holeTo) { 1206 assert holeFrom < holeTo : "check"; 1207 assert from() <= holeFrom && holeTo <= to() : "index out of interval"; 1208 1209 Range cur = first; 1210 while (!cur.isEndMarker()) { 1211 assert cur.to < cur.next.from : "no space between ranges"; 1212 1213 // hole-range starts before this range . hole 1214 if (holeFrom < cur.from) { 1215 return true; 1216 1217 // hole-range completely inside this range . no hole 1218 } else { 1219 if (holeTo <= cur.to) { 1220 return false; 1221 1222 // overlapping of hole-range with this range . hole 1223 } else { 1224 if (holeFrom <= cur.to) { 1225 return true; 1226 } 1227 } 1228 } 1229 1230 cur = cur.next; 1231 } 1232 1233 return false; 1234 } 1235 1236 @Override 1237 public String toString() { 1238 String from = "?"; 1239 String to = "?"; 1240 if (first != null && !first.isEndMarker()) { 1241 from = String.valueOf(from()); 1242 // to() may cache a computed value, modifying the current object, which is a bad idea 1243 // for a printing function. Compute it directly instead. 1244 to = String.valueOf(calcTo()); 1245 } 1246 String locationString = this.location == null ? "" : "@" + this.location; 1247 return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]"; 1248 } 1249 1250 /** 1251 * Gets the use position information for this interval. 1252 */ 1253 public UsePosList usePosList() { 1254 return usePosList; 1255 } 1256 1257 /** 1258 * Gets a single line string for logging the details of this interval to a log stream. 1259 * 1260 * @param allocator the register allocator context 1261 */ 1262 public String logString(LinearScan allocator) { 1263 StringBuilder buf = new StringBuilder(100); 1264 buf.append(operandNumber).append(':').append(operand).append(' '); 1265 if (!isRegister(operand)) { 1266 if (location != null) { 1267 buf.append("location{").append(location).append("} "); 1268 } 1269 } 1270 1271 buf.append("hints{").append(splitParent.operandNumber); 1272 Interval hint = locationHint(false); 1273 if (hint != null && hint.operandNumber != splitParent.operandNumber) { 1274 buf.append(", ").append(hint.operandNumber); 1275 } 1276 buf.append("} ranges{"); 1277 1278 // print ranges 1279 Range cur = first; 1280 while (!cur.isEndMarker()) { 1281 if (cur != first) { 1282 buf.append(", "); 1283 } 1284 buf.append(cur); 1285 cur = cur.next; 1286 assert cur != null : "range list not closed with range sentinel"; 1287 } 1288 buf.append("} uses{"); 1289 1290 // print use positions 1291 int prev = -1; 1292 for (int i = usePosList.size() - 1; i >= 0; --i) { 1293 assert prev < usePosList.usePos(i) : "use positions not sorted"; 1294 if (i != usePosList.size() - 1) { 1295 buf.append(", "); 1296 } 1297 buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i)); 1298 prev = usePosList.usePos(i); 1299 } 1300 buf.append("} spill-state{").append(spillState()).append("}"); 1301 if (canMaterialize()) { 1302 buf.append(" (remat:").append(getMaterializedValue().toString()).append(")"); 1303 } 1304 return buf.toString(); 1305 } 1306 1307 List<Interval> getSplitChildren() { 1308 return Collections.unmodifiableList(splitChildren); 1309 } 1310} 1311