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 */
23package org.graalvm.compiler.lir.alloc.trace.lsra;
24
25import static jdk.vm.ci.code.ValueUtil.asRegister;
26import static jdk.vm.ci.code.ValueUtil.isIllegal;
27import static jdk.vm.ci.code.ValueUtil.isRegister;
28import static jdk.vm.ci.code.ValueUtil.isStackSlot;
29import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
30import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
31import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
32
33import java.util.ArrayList;
34import java.util.Arrays;
35import java.util.Collections;
36import java.util.EnumSet;
37import java.util.List;
38
39import org.graalvm.compiler.core.common.LIRKind;
40import org.graalvm.compiler.core.common.util.Util;
41import org.graalvm.compiler.debug.Assertions;
42import org.graalvm.compiler.debug.GraalError;
43import org.graalvm.compiler.lir.LIRInstruction;
44import org.graalvm.compiler.lir.Variable;
45import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
46import org.graalvm.compiler.options.OptionValues;
47
48import jdk.vm.ci.code.RegisterValue;
49import jdk.vm.ci.code.StackSlot;
50import jdk.vm.ci.meta.AllocatableValue;
51import jdk.vm.ci.meta.JavaConstant;
52import jdk.vm.ci.meta.Value;
53import jdk.vm.ci.meta.ValueKind;
54
55/**
56 * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
57 */
58final 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    public void setLocationHint(IntervalHint interval) {
369        locationHint = interval;
370    }
371
372    public boolean hasHint() {
373        return locationHint != null;
374    }
375
376    public boolean isSplitParent() {
377        return splitParent == this;
378    }
379
380    boolean isSplitChild() {
381        return splitParent != this;
382    }
383
384    /**
385     * Gets the split parent for this interval.
386     */
387    public TraceInterval splitParent() {
388        assert splitParent.isSplitParent() : "not a split parent: " + this;
389        return splitParent;
390    }
391
392    /**
393     * Gets the canonical spill slot for this interval.
394     */
395    public AllocatableValue spillSlot() {
396        return splitParent().spillSlot;
397    }
398
399    public void setSpillSlot(AllocatableValue slot) {
400        assert isStackSlotValue(slot);
401        assert spillSlot() == null || (isVirtualStackSlot(spillSlot()) && isStackSlot(slot)) : String.format("cannot overwrite existing spill slot %s of interval %s with %s", spillSlot(), this, slot);
402        splitParent().spillSlot = slot;
403    }
404
405    TraceInterval currentSplitChild() {
406        return splitParent().currentSplitChild;
407    }
408
409    void makeCurrentSplitChild() {
410        splitParent().currentSplitChild = this;
411    }
412
413    boolean insertMoveWhenActivated() {
414        return insertMoveWhenActivated;
415    }
416
417    void setInsertMoveWhenActivated(boolean b) {
418        insertMoveWhenActivated = b;
419    }
420
421    // for spill optimization
422    public SpillState spillState() {
423        return splitParent().spillState;
424    }
425
426    public int spillDefinitionPos() {
427        return splitParent().spillDefinitionPos;
428    }
429
430    public void setSpillState(SpillState state) {
431        assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
432        splitParent().spillState = state;
433    }
434
435    public void setSpillDefinitionPos(int pos) {
436        assert spillState() == SpillState.NoDefinitionFound || spillState() == SpillState.NoSpillStore || spillDefinitionPos() == -1 : "cannot set the position twice";
437        int to = to();
438        assert pos < to : String.format("Cannot spill %s at %d", this, pos);
439        splitParent().spillDefinitionPos = pos;
440    }
441
442    /**
443     * Returns true if this interval has a shadow copy on the stack that is correct after
444     * {@code opId}.
445     */
446    public boolean inMemoryAt(int opId) {
447        SpillState spillSt = spillState();
448        return spillSt == SpillState.StartInMemory || (spillSt == SpillState.SpillStore && opId > spillDefinitionPos() && !canMaterialize());
449    }
450
451    public boolean preSpilledAllocated() {
452        return spillState() == SpillState.StartInMemory && numUsePos() == 0 && !hasHint();
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}
985