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