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