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.trace.lsra;
24
25 import static jdk.vm.ci.code.ValueUtil.asRegister;
26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
27 import static jdk.vm.ci.code.ValueUtil.isRegister;
28 import static jdk.vm.ci.code.ValueUtil.isStackSlot;
29 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
30 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
31 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
32
33 import java.util.ArrayList;
34 import java.util.Arrays;
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.Util;
41 import org.graalvm.compiler.debug.Assertions;
42 import org.graalvm.compiler.debug.GraalError;
43 import org.graalvm.compiler.lir.LIRInstruction;
44 import org.graalvm.compiler.lir.Variable;
45 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
46 import org.graalvm.compiler.options.OptionValues;
47
48 import jdk.vm.ci.code.RegisterValue;
49 import jdk.vm.ci.code.StackSlot;
50 import jdk.vm.ci.meta.AllocatableValue;
51 import jdk.vm.ci.meta.JavaConstant;
52 import jdk.vm.ci.meta.Value;
53 import jdk.vm.ci.meta.ValueKind;
54
55 /**
56 * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
57 */
58 final class TraceInterval extends IntervalHint {
59
60 /**
61 * Constants denoting the register usage priority for an interval. The constants are declared in
62 * increasing order of priority are are used to optimize spilling when multiple overlapping
63 * intervals compete for limited registers.
64 */
65 public enum RegisterPriority {
66 /**
67 * No special reason for an interval to be allocated a register.
68 */
69 None,
70
71 /**
72 * Priority level for intervals live at the end of a loop.
73 */
74 LiveAtLoopEnd,
75
76 /**
77 * Priority level for intervals that should be allocated to a register.
78 */
79 ShouldHaveRegister,
80
81 /**
82 * Priority level for intervals that must be allocated to a register.
83 */
84 MustHaveRegister;
85
86 public static final RegisterPriority[] VALUES = values();
87
88 /**
89 * Determines if this priority is higher than or equal to a given priority.
90 */
91 public boolean greaterEqual(RegisterPriority other) {
92 return ordinal() >= other.ordinal();
93 }
94
95 /**
96 * Determines if this priority is lower than a given priority.
97 */
98 public boolean lessThan(RegisterPriority other) {
99 return ordinal() < other.ordinal();
100 }
101
102 public CharSequence shortName() {
103 return name().subSequence(0, 1);
104 }
105 }
106
107 /**
108 * Constants denoting whether an interval is bound to a specific register. This models platform
109 * dependencies on register usage for certain instructions.
110 */
111 enum RegisterBinding {
112 /**
113 * Interval is bound to a specific register as required by the platform.
114 */
115 Fixed,
116
117 /**
118 * Interval has no specific register requirements.
119 */
120 Any,
121
122 /**
123 * Interval is bound to a stack slot.
124 */
125 Stack;
126
127 public static final RegisterBinding[] VALUES = values();
128 }
129
130 /**
131 * Constants denoting the linear-scan states an interval may be in with respect to the
132 * {@linkplain TraceInterval#from() start} {@code position} of the interval being processed.
133 */
134 enum State {
135 /**
136 * An interval that starts after {@code position}.
137 */
138 Unhandled,
139
140 /**
141 * An interval that {@linkplain TraceInterval#covers covers} {@code position} and has an
142 * assigned register.
143 */
144 Active,
145
146 /**
147 * An interval that starts before and ends after {@code position} but does not
148 * {@linkplain TraceInterval#covers cover} it due to a lifetime hole.
149 */
150 Inactive,
151
152 /**
153 * An interval that ends before {@code position} or is spilled to memory.
154 */
155 Handled;
156 }
157
158 /**
159 * Constants used in optimization of spilling of an interval.
160 */
161 public enum SpillState {
162 /**
163 * Starting state of calculation: no definition found yet.
164 */
165 NoDefinitionFound,
166
167 /**
168 * One definition has already been found. Two consecutive definitions are treated as one
169 * (e.g. a consecutive move and add because of two-operand LIR form). The position of this
170 * definition is given by {@link TraceInterval#spillDefinitionPos()}.
171 */
172 NoSpillStore,
173
174 /**
175 * A spill move has already been inserted.
176 */
177 SpillStore,
178
179 /**
180 * The interval starts in memory (e.g. method parameter), so a store is never necessary.
181 */
182 StartInMemory,
183
184 /**
185 * The interval has more than one definition (e.g. resulting from phi moves), so stores to
186 * memory are not optimized.
187 */
188 NoOptimization;
189
190 public static final EnumSet<SpillState> IN_MEMORY = EnumSet.of(SpillStore, StartInMemory);
191 }
192
193 /**
194 * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval
195 * prior to register allocation.
196 */
197 public final Variable operand;
198
199 /**
200 * The operand number for this interval's {@linkplain #operand operand}.
201 */
202 public final int operandNumber;
203
204 /**
205 * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this
206 * interval. In case of a spilled interval which is re-materialized this is
207 * {@link Value#ILLEGAL}.
208 */
209 private AllocatableValue location;
210
211 /**
212 * The stack slot to which all splits of this interval are spilled if necessary.
213 */
214 private AllocatableValue spillSlot;
215
216 /**
217 * The start of the range, inclusive.
218 */
219 private int intFrom;
220
221 /**
222 * The end of the range, exclusive.
223 */
224 private int intTo;
225
226 /**
227 * List of (use-positions, register-priorities) pairs, sorted by use-positions.
228 */
229 private int[] usePosListArray;
230 private int usePosListSize;
231
232 /**
233 * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.
234 */
235 TraceInterval next;
236
237 /**
238 * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split
239 * parent}, it points to itself.
240 */
241 private TraceInterval splitParent;
242
243 /**
244 * List of all intervals that are split off from this interval. This is only used if this is a
245 * {@linkplain #isSplitParent() split parent}.
246 */
247 private ArrayList<TraceInterval> splitChildren = null;
248
249 /**
250 * Current split child that has been active or inactive last (always stored in split parents).
251 */
252 private TraceInterval currentSplitChild;
253
254 /**
255 * Specifies if move is inserted between currentSplitChild and this interval when interval gets
256 * active the first time.
257 */
258 private boolean insertMoveWhenActivated;
259
260 /**
261 * For spill move optimization.
262 */
263 private SpillState spillState;
264
265 /**
266 * Position where this interval is defined (if defined only once).
267 */
268 private int spillDefinitionPos;
269
270 /**
271 * This interval should be assigned the same location as the hint interval.
272 */
273 private IntervalHint locationHint;
274
275 /**
276 * The value with which a spilled child interval can be re-materialized. Currently this must be
277 * a Constant.
278 */
279 private JavaConstant materializedValue;
280
281 /**
282 * Sentinel interval to denote the end of an interval list.
283 */
284 static final TraceInterval EndMarker = new TraceInterval(new Variable(ValueKind.Illegal, Integer.MAX_VALUE), -1);
285
286 TraceInterval(Variable operand) {
287 this(operand, operand.index);
288 }
289
290 private TraceInterval(Variable operand, int operandNumber) {
291 assert operand != null;
292 this.operand = operand;
293 this.operandNumber = operandNumber;
294 if (isRegister(operand)) {
295 location = operand;
296 } else {
297 assert isIllegal(operand) || isVariable(operand);
298 }
299 this.intFrom = Integer.MAX_VALUE;
300 this.intTo = Integer.MAX_VALUE;
301 this.usePosListArray = new int[4 * 2];
302 this.next = EndMarker;
303 this.spillState = SpillState.NoDefinitionFound;
304 this.spillDefinitionPos = -1;
305 splitParent = this;
306 currentSplitChild = this;
307 }
308
309 private boolean splitChildrenEmpty() {
310 assert splitChildren == null || !splitChildren.isEmpty();
311 return splitChildren == null;
312 }
313
314 void assignLocation(AllocatableValue newLocation) {
315 if (isRegister(newLocation)) {
316 assert this.location == null : "cannot re-assign location for " + this;
317 if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind().equals(LIRKind.Illegal)) {
318 this.location = asRegister(newLocation).asValue(kind());
319 return;
320 }
321 } else if (isIllegal(newLocation)) {
322 assert canMaterialize();
323 } else {
324 assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this;
325 assert isStackSlotValue(newLocation);
326 assert !newLocation.getValueKind().equals(LIRKind.Illegal);
327 assert newLocation.getValueKind().equals(this.kind());
328 }
329 this.location = newLocation;
330 }
331
332 /**
333 * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to
334 * this interval.
335 */
336 @Override
337 public AllocatableValue location() {
338 return location;
339 }
340
341 private ValueKind<?> kind() {
342 return operand.getValueKind();
343 }
344
345 public boolean isEmpty() {
346 return intFrom == Integer.MAX_VALUE && intTo == Integer.MAX_VALUE;
347 }
348
349 public void setTo(int pos) {
350 assert intFrom == Integer.MAX_VALUE || intFrom < pos;
351 intTo = pos;
352 }
353
354 public void setFrom(int pos) {
355 assert intTo == Integer.MAX_VALUE || pos < intTo;
356 intFrom = pos;
357 }
358
359 @Override
360 public int from() {
361 return intFrom;
362 }
363
364 int to() {
365 return intTo;
366 }
367
368 int numUsePositions() {
369 return numUsePos();
370 }
371
372 public void setLocationHint(IntervalHint interval) {
373 locationHint = interval;
374 }
375
376 public boolean hasHint() {
377 return locationHint != null;
378 }
379
380 public boolean isSplitParent() {
381 return splitParent == this;
382 }
383
384 boolean isSplitChild() {
385 return splitParent != this;
386 }
387
388 /**
389 * Gets the split parent for this interval.
390 */
391 public TraceInterval splitParent() {
392 assert splitParent.isSplitParent() : "not a split parent: " + this;
393 return splitParent;
394 }
395
396 /**
397 * Gets the canonical spill slot for this interval.
398 */
399 public AllocatableValue spillSlot() {
400 return splitParent().spillSlot;
401 }
402
403 public void setSpillSlot(AllocatableValue slot) {
404 assert isStackSlotValue(slot);
405 assert spillSlot() == null || (isVirtualStackSlot(spillSlot()) && isStackSlot(slot)) : String.format("cannot overwrite existing spill slot %s of interval %s with %s", spillSlot(), this, slot);
406 splitParent().spillSlot = slot;
407 }
408
409 TraceInterval currentSplitChild() {
410 return splitParent().currentSplitChild;
411 }
412
413 void makeCurrentSplitChild() {
414 splitParent().currentSplitChild = this;
415 }
416
417 boolean insertMoveWhenActivated() {
418 return insertMoveWhenActivated;
419 }
420
421 void setInsertMoveWhenActivated(boolean b) {
422 insertMoveWhenActivated = b;
423 }
424
425 // for spill optimization
426 public SpillState spillState() {
427 return splitParent().spillState;
428 }
429
430 public int spillDefinitionPos() {
431 return splitParent().spillDefinitionPos;
432 }
433
434 public void setSpillState(SpillState state) {
435 assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
436 splitParent().spillState = state;
437 }
438
439 public void setSpillDefinitionPos(int pos) {
440 assert spillState() == SpillState.NoDefinitionFound || spillState() == SpillState.NoSpillStore || spillDefinitionPos() == -1 : "cannot set the position twice";
441 int to = to();
442 assert pos < to : String.format("Cannot spill %s at %d", this, pos);
443 splitParent().spillDefinitionPos = pos;
444 }
445
446 /**
447 * Returns true if this interval has a shadow copy on the stack that is correct after
448 * {@code opId}.
449 */
450 public boolean inMemoryAt(int opId) {
451 SpillState spillSt = spillState();
452 return spillSt == SpillState.StartInMemory || (spillSt == SpillState.SpillStore && opId > spillDefinitionPos() && !canMaterialize());
453 }
454
455 // test intersection
456 boolean intersects(TraceInterval i) {
457 return intersectsAt(i) != -1;
458 }
459
460 int intersectsAt(TraceInterval i) {
461 TraceInterval i1;
462 TraceInterval i2;
463 if (i.from() < this.from()) {
464 i1 = i;
465 i2 = this;
466 } else {
467 i1 = this;
468 i2 = i;
469 }
470 assert i1.from() <= i2.from();
471
472 if (i1.to() <= i2.from()) {
473 return -1;
474 }
475 return i2.from();
476 }
477
478 /**
479 * Sets the value which is used for re-materialization.
480 */
481 public void addMaterializationValue(JavaConstant value) {
482 if (materializedValue != null) {
483 throw GraalError.shouldNotReachHere(String.format("Multiple materialization values for %s?", this));
484 }
485 materializedValue = value;
486 }
487
488 /**
489 * Returns true if this interval can be re-materialized when spilled. This means that no
490 * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored.
491 */
492 public boolean canMaterialize() {
493 return getMaterializedValue() != null;
494 }
495
496 /**
497 * Returns a value which can be moved to a register instead of a restore-move from stack.
498 */
499 public JavaConstant getMaterializedValue() {
500 return splitParent().materializedValue;
501 }
502
503 // consistency check of split-children
504 boolean checkSplitChildren() {
505 if (!splitChildrenEmpty()) {
506 assert isSplitParent() : "only split parents can have children";
507
508 for (int i = 0; i < splitChildren.size(); i++) {
509 TraceInterval i1 = splitChildren.get(i);
510
511 assert i1.splitParent() == this : "not a split child of this interval";
512 assert i1.kind().equals(kind()) : "must be equal for all split children";
513 assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children";
514
515 for (int j = i + 1; j < splitChildren.size(); j++) {
516 TraceInterval i2 = splitChildren.get(j);
517
518 assert i1.operandNumber != i2.operandNumber : "same register number";
519
520 if (i1.from() < i2.from()) {
521 assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping";
522 } else {
523 assert i2.from() < i1.from() : "intervals start at same opId";
524 assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping";
525 }
526 }
527 }
528 }
529
530 return true;
531 }
532
533 public IntervalHint locationHint(boolean searchSplitChild) {
534 if (!searchSplitChild) {
535 return locationHint;
536 }
537
538 if (locationHint != null) {
539 assert !(locationHint instanceof TraceInterval) || ((TraceInterval) locationHint).isSplitParent() : "ony split parents are valid hint registers";
540
541 if (locationHint.location() != null && isRegister(locationHint.location())) {
542 return locationHint;
543 } else if (locationHint instanceof TraceInterval) {
544 TraceInterval hint = (TraceInterval) locationHint;
545 if (!hint.splitChildrenEmpty()) {
546 // search the first split child that has a register assigned
547 int len = hint.splitChildren.size();
548 for (int i = 0; i < len; i++) {
549 TraceInterval interval = hint.splitChildren.get(i);
550 if (interval.location != null && isRegister(interval.location)) {
551 return interval;
552 }
553 }
554 }
555 }
556 }
557
558 // no hint interval found that has a register assigned
559 return null;
560 }
561
562 TraceInterval getSplitChildAtOpIdOrNull(int opId, LIRInstruction.OperandMode mode) {
563 /*
564 * TODO(je) could be replace by a simple range check by caching `to` in the split parent
565 * when creating split children.
566 */
567 return getSplitChildAtOpIdIntern(opId, mode, true);
568 }
569
570 TraceInterval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode) {
571 return getSplitChildAtOpIdIntern(opId, mode, false);
572 }
573
574 private TraceInterval getSplitChildAtOpIdIntern(int opId, LIRInstruction.OperandMode mode, boolean returnNull) {
575 assert isSplitParent() : "can only be called for split parents";
576 assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
577
578 if (splitChildrenEmpty()) {
579 if (returnNull) {
580 return covers(opId, mode) ? this : null;
581 }
582 assert this.covers(opId, mode) : this + " does not cover " + opId;
583 return this;
584 } else {
585 TraceInterval result = null;
586 int len = splitChildren.size();
587
588 // in outputMode, the end of the interval (opId == cur.to()) is not valid
589 int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1);
590
591 int i;
592 for (i = 0; i < len; i++) {
593 TraceInterval cur = splitChildren.get(i);
594 if (cur.from() <= opId && opId < cur.to() + toOffset) {
595 if (i > 0) {
596 // exchange current split child to start of list (faster access for next
597 // call)
598 Util.atPutGrow(splitChildren, i, splitChildren.get(0), null);
599 Util.atPutGrow(splitChildren, 0, cur, null);
600 }
601
602 // interval found
603 result = cur;
604 break;
605 }
606 }
607
608 assert returnNull || checkSplitChild(result, opId, toOffset, mode);
609 return result;
610 }
611 }
612
613 private boolean checkSplitChild(TraceInterval result, int opId, int toOffset, LIRInstruction.OperandMode mode) {
614 if (result == null) {
615 // this is an error
616 StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
617 if (!splitChildrenEmpty()) {
618 TraceInterval firstChild = splitChildren.get(0);
619 TraceInterval lastChild = splitChildren.get(splitChildren.size() - 1);
620 msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
621 }
622 throw new GraalError("Linear Scan Error: %s", msg);
623 }
624
625 if (!splitChildrenEmpty()) {
626 for (TraceInterval interval : splitChildren) {
627 if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
628 /*
629 * Should not happen: Try another compilation as it is very unlikely to happen
630 * again.
631 */
632 throw new GraalError("two valid result intervals found for opId %d: %d and %d\n%s\n", opId, result.operandNumber, interval.operandNumber,
633 result.logString(), interval.logString());
634 }
635 }
636 }
637 assert result.covers(opId, mode) : "opId not covered by interval";
638 return true;
639 }
640
641 // returns the last split child that ends before the given opId
642 TraceInterval getSplitChildBeforeOpId(int opId) {
643 assert opId >= 0 : "invalid opId";
644
645 TraceInterval parent = splitParent();
646 TraceInterval result = null;
647
648 assert !parent.splitChildrenEmpty() : "no split children available";
649 int len = parent.splitChildren.size();
650
651 for (int i = len - 1; i >= 0; i--) {
652 TraceInterval cur = parent.splitChildren.get(i);
653 if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
654 result = cur;
655 }
656 }
657
658 assert result != null : "no split child found";
659 return result;
660 }
661
662 private RegisterPriority adaptPriority(RegisterPriority priority) {
663 /*
664 * In case of re-materialized values we require that use-operands are registers, because we
665 * don't have the value in a stack location. (Note that ShouldHaveRegister means that the
666 * operand can also be a StackSlot).
667 */
668 if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) {
669 return RegisterPriority.MustHaveRegister;
670 }
671 return priority;
672 }
673
674 // Note: use positions are sorted descending . first use has highest index
675 int firstUsage(RegisterPriority minRegisterPriority) {
676 for (int i = numUsePos() - 1; i >= 0; --i) {
677 RegisterPriority registerPriority = adaptPriority(getUsePosRegisterPriority(i));
678 if (registerPriority.greaterEqual(minRegisterPriority)) {
679 return getUsePos(i);
680 }
681 }
682 return Integer.MAX_VALUE;
683 }
684
685 int nextUsage(RegisterPriority minRegisterPriority, int from) {
686 for (int i = numUsePos() - 1; i >= 0; --i) {
687 int usePos = getUsePos(i);
688 if (usePos >= from && adaptPriority(getUsePosRegisterPriority(i)).greaterEqual(minRegisterPriority)) {
689 return usePos;
690 }
691 }
692 return Integer.MAX_VALUE;
693 }
694
695 int nextUsageExact(RegisterPriority exactRegisterPriority, int from) {
696
697 for (int i = numUsePos() - 1; i >= 0; --i) {
698 int usePos = getUsePos(i);
699 if (usePos >= from && adaptPriority(getUsePosRegisterPriority(i)) == exactRegisterPriority) {
700 return usePos;
701 }
702 }
703 return Integer.MAX_VALUE;
704 }
705
706 int previousUsage(RegisterPriority minRegisterPriority, int from) {
707 int prev = -1;
708 for (int i = numUsePos() - 1; i >= 0; --i) {
709 int usePos = getUsePos(i);
710 if (usePos > from) {
711 return prev;
712 }
713 if (adaptPriority(getUsePosRegisterPriority(i)).greaterEqual(minRegisterPriority)) {
714 prev = usePos;
715 }
716 }
717 return prev;
718 }
719
720 public void addUsePos(int pos, RegisterPriority registerPriority, OptionValues options) {
721 assert isEmpty() || covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
722
723 // do not add use positions for precolored intervals because they are never used
724 if (registerPriority != RegisterPriority.None) {
725 if (Assertions.detailedAssertionsEnabled(options)) {
726 for (int i = 0; i < numUsePos(); i++) {
727 assert pos <= getUsePos(i) : "already added a use-position with lower position";
728 if (i > 0) {
729 assert getUsePos(i) < getUsePos(i - 1) : "not sorted descending";
730 }
731 }
732 }
733
734 // Note: addUse is called in descending order, so list gets sorted
735 // automatically by just appending new use positions
736 int len = numUsePos();
737 if (len == 0 || getUsePos(len - 1) > pos) {
738 usePosAdd(pos, registerPriority);
739 } else if (getUsePosRegisterPriority(len - 1).lessThan(registerPriority)) {
740 assert getUsePos(len - 1) == pos : "list not sorted correctly";
741 setUsePosRegisterPriority(len - 1, registerPriority);
742 }
743 }
744 }
745
746 public void addRange(int from, int to) {
747 assert from < to : "invalid range";
748
749 if (from < intFrom) {
750 setFrom(from);
751 }
752 if (intTo == Integer.MAX_VALUE || intTo < to) {
753 setTo(to);
754 }
755 }
756
757 TraceInterval newSplitChild(TraceLinearScan allocator) {
758 // allocate new interval
759 TraceInterval parent = splitParent();
760 TraceInterval result = allocator.createDerivedInterval(parent);
761
762 result.splitParent = parent;
763 result.setLocationHint(parent);
764
765 // insert new interval in children-list of parent
766 if (parent.splitChildrenEmpty()) {
767 assert isSplitParent() : "list must be initialized at first split";
768
769 // Create new non-shared list
770 parent.splitChildren = new ArrayList<>(4);
771 parent.splitChildren.add(this);
772 }
773 parent.splitChildren.add(result);
774
775 return result;
776 }
777
778 /**
779 * Splits this interval at a specified position and returns the remainder as a new <i>child</i>
780 * interval of this interval's {@linkplain #splitParent() parent} interval.
781 * <p>
782 * When an interval is split, a bi-directional link is established between the original
783 * <i>parent</i> interval and the <i>children</i> intervals that are split off this interval.
784 * When a split child is split again, the new created interval is a direct child of the original
785 * parent. That is, there is no tree of split children stored, just a flat list. All split
786 * children are spilled to the same {@linkplain #spillSlot spill slot}.
787 *
788 * @param splitPos the position at which to split this interval
789 * @param allocator the register allocator context
790 * @return the child interval split off from this interval
791 */
792 TraceInterval split(int splitPos, TraceLinearScan allocator) {
793
794 // allocate new interval
795 TraceInterval result = newSplitChild(allocator);
796
797 // split the ranges
798 result.setTo(intTo);
799 result.setFrom(splitPos);
800 intTo = splitPos;
801
802 // split list of use positions
803 splitUsePosAt(result, splitPos);
804
805 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) {
806 for (int i = 0; i < numUsePos(); i++) {
807 assert getUsePos(i) < splitPos;
808 }
809 for (int i = 0; i < result.numUsePos(); i++) {
810 assert result.getUsePos(i) >= splitPos;
811 }
812 }
813 return result;
814 }
815
816 // returns true if the opId is inside the interval
817 boolean covers(int opId, LIRInstruction.OperandMode mode) {
818 if (mode == LIRInstruction.OperandMode.DEF) {
819 return from() <= opId && opId < to();
820 }
821 return from() <= opId && opId <= to();
822 }
823
824 @Override
825 public String toString() {
826 String from = "?";
827 String to = "?";
828 if (!isEmpty()) {
829 from = String.valueOf(from());
830 to = String.valueOf(to());
831 }
832 String locationString = this.location == null ? "" : "@" + this.location;
833 return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
834 }
835
836 /**
837 * Gets a single line string for logging the details of this interval to a log stream.
838 */
839 @Override
840 public String logString() {
841 StringBuilder buf = new StringBuilder(100);
842 buf.append("any ").append(operandNumber).append(':').append(operand).append(' ');
843 if (!isRegister(operand)) {
844 if (location != null) {
845 buf.append("location{").append(location).append("} ");
846 }
847 }
848
849 buf.append("hints{").append(splitParent.operandNumber);
850 IntervalHint hint = locationHint(false);
851 if (hint != null) {
852 buf.append(", ").append(hint.location());
853 }
854 buf.append("} ranges{");
855
856 // print range
857 buf.append("[" + from() + ", " + to() + "]");
858 buf.append("} uses{");
859
860 // print use positions
861 int prev = -1;
862 for (int i = numUsePos() - 1; i >= 0; --i) {
863 assert prev < getUsePos(i) : "use positions not sorted";
864 if (i != numUsePos() - 1) {
865 buf.append(", ");
866 }
867 buf.append(getUsePos(i)).append(':').append(getUsePosRegisterPriority(i).shortName());
868 prev = getUsePos(i);
869 }
870 buf.append("} spill-state{").append(spillState()).append("}");
871 if (canMaterialize()) {
872 buf.append(" (remat:").append(getMaterializedValue().toString()).append(")");
873 }
874 return buf.toString();
875 }
876
877 List<TraceInterval> getSplitChildren() {
878 return Collections.unmodifiableList(splitChildren);
879 }
880
881 /*
882 * UsePos
883 *
884 * List of use positions. Each entry in the list records the use position and register priority
885 * associated with the use position. The entries in the list are in descending order of use
886 * position.
887 *
888 */
889
890 /**
891 * Gets the use position at a specified index in this list.
892 *
893 * @param index the index of the entry for which the use position is returned
894 * @return the use position of entry {@code index} in this list
895 */
896 int getUsePos(int index) {
897 return intListGet(index << 1);
898 }
899
900 int numUsePos() {
901 return usePosListSize >> 1;
902 }
903
904 /**
905 * Gets the register priority for the use position at a specified index in this list.
906 *
907 * @param index the index of the entry for which the register priority is returned
908 * @return the register priority of entry {@code index} in this list
909 */
910 RegisterPriority getUsePosRegisterPriority(int index) {
911 return RegisterPriority.VALUES[intListGet((index << 1) + 1)];
912 }
913
914 void removeFirstUsePos() {
915 intListSetSize(usePosListSize - 2);
916 }
917
918 // internal
919
920 private void setUsePosRegisterPriority(int pos, RegisterPriority registerPriority) {
921 int index = (pos << 1) + 1;
922 int value = registerPriority.ordinal();
923 intListSet(index, value);
924 }
925
926 private void usePosAdd(int pos, RegisterPriority registerPriority) {
927 assert usePosListSize == 0 || getUsePos(numUsePos() - 1) > pos;
928 intListAdd(pos);
929 intListAdd(registerPriority.ordinal());
930 }
931
932 private void splitUsePosAt(TraceInterval result, int splitPos) {
933 int i = numUsePos() - 1;
934 int len = 0;
935 while (i >= 0 && getUsePos(i) < splitPos) {
936 --i;
937 len += 2;
938 }
939 int listSplitIndex = (i + 1) * 2;
940 int[] array = new int[len];
941 System.arraycopy(usePosListArray, listSplitIndex, array, 0, len);
942 if (listSplitIndex < usePosListSize) {
943 usePosListSize = listSplitIndex;
944 } else {
945 assert listSplitIndex == usePosListSize : "splitting cannot grow the use position array!";
946 }
947 result.usePosListArray = usePosListArray;
948 result.usePosListSize = usePosListSize;
949 usePosListArray = array;
950 usePosListSize = len;
951 }
952
953 // IntList
954
955 private int intListGet(int index) {
956 if (index >= usePosListSize) {
957 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + usePosListSize);
958 }
959 return usePosListArray[index];
960 }
961
962 private void intListSet(int index, int value) {
963 if (index >= usePosListSize) {
964 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + usePosListSize);
965 }
966 usePosListArray[index] = value;
967 }
968
969 private void intListAdd(int pos) {
970 if (usePosListSize == usePosListArray.length) {
971 int newSize = (usePosListSize * 3) / 2 + 1;
972 usePosListArray = Arrays.copyOf(usePosListArray, newSize);
973 }
974 usePosListArray[usePosListSize++] = pos;
975 }
976
977 private void intListSetSize(int newSize) {
978 if (newSize < usePosListSize) {
979 usePosListSize = newSize;
980 } else if (newSize > usePosListSize) {
981 usePosListArray = Arrays.copyOf(usePosListArray, newSize);
982 }
983 }
984 }