--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Interval.java	Tue Sep 01 11:49:35 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,1304 +0,0 @@
-/*
- * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.graal.lir.alloc.trace;
-
-import static com.oracle.graal.compiler.common.GraalOptions.*;
-import static com.oracle.graal.lir.LIRValueUtil.*;
-import static jdk.internal.jvmci.code.ValueUtil.*;
-
-import java.util.*;
-
-import jdk.internal.jvmci.code.*;
-import jdk.internal.jvmci.common.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.util.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.lir.*;
-
-/**
- * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
- */
-final class Interval {
-
-    /**
-     * A pair of intervals.
-     */
-    static final class Pair {
-
-        public final Interval first;
-        public final Interval second;
-
-        public Pair(Interval first, Interval second) {
-            this.first = first;
-            this.second = second;
-        }
-    }
-
-    /**
-     * A set of interval lists, one per {@linkplain RegisterBinding binding} type.
-     */
-    static final class RegisterBindingLists {
-
-        /**
-         * List of intervals whose binding is currently {@link RegisterBinding#Fixed}.
-         */
-        public Interval fixed;
-
-        /**
-         * List of intervals whose binding is currently {@link RegisterBinding#Any}.
-         */
-        public Interval any;
-
-        /**
-         * List of intervals whose binding is currently {@link RegisterBinding#Stack}.
-         */
-        public Interval stack;
-
-        public RegisterBindingLists(Interval fixed, Interval any, Interval stack) {
-            this.fixed = fixed;
-            this.any = any;
-            this.stack = stack;
-        }
-
-        /**
-         * Gets the list for a specified binding.
-         *
-         * @param binding specifies the list to be returned
-         * @return the list of intervals whose binding is {@code binding}
-         */
-        public Interval get(RegisterBinding binding) {
-            switch (binding) {
-                case Any:
-                    return any;
-                case Fixed:
-                    return fixed;
-                case Stack:
-                    return stack;
-            }
-            throw JVMCIError.shouldNotReachHere();
-        }
-
-        /**
-         * Sets the list for a specified binding.
-         *
-         * @param binding specifies the list to be replaced
-         * @param list a list of intervals whose binding is {@code binding}
-         */
-        public void set(RegisterBinding binding, Interval list) {
-            assert list != null;
-            switch (binding) {
-                case Any:
-                    any = list;
-                    break;
-                case Fixed:
-                    fixed = list;
-                    break;
-                case Stack:
-                    stack = list;
-                    break;
-            }
-        }
-
-        /**
-         * Adds an interval to a list sorted by {@linkplain Interval#currentFrom() current from}
-         * positions.
-         *
-         * @param binding specifies the list to be updated
-         * @param interval the interval to add
-         */
-        public void addToListSortedByCurrentFromPositions(RegisterBinding binding, Interval interval) {
-            Interval list = get(binding);
-            Interval prev = null;
-            Interval cur = list;
-            while (cur.currentFrom() < interval.currentFrom()) {
-                prev = cur;
-                cur = cur.next;
-            }
-            Interval result = list;
-            if (prev == null) {
-                // add to head of list
-                result = interval;
-            } else {
-                // add before 'cur'
-                prev.next = interval;
-            }
-            interval.next = cur;
-            set(binding, result);
-        }
-
-        /**
-         * Adds an interval to a list sorted by {@linkplain Interval#from() start} positions and
-         * {@linkplain Interval#firstUsage(RegisterPriority) first usage} positions.
-         *
-         * @param binding specifies the list to be updated
-         * @param interval the interval to add
-         */
-        public void addToListSortedByStartAndUsePositions(RegisterBinding binding, Interval interval) {
-            Interval list = get(binding);
-            Interval prev = null;
-            Interval cur = list;
-            while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) {
-                prev = cur;
-                cur = cur.next;
-            }
-            if (prev == null) {
-                list = interval;
-            } else {
-                prev.next = interval;
-            }
-            interval.next = cur;
-            set(binding, list);
-        }
-
-        /**
-         * Removes an interval from a list.
-         *
-         * @param binding specifies the list to be updated
-         * @param i the interval to remove
-         */
-        public void remove(RegisterBinding binding, Interval i) {
-            Interval list = get(binding);
-            Interval prev = null;
-            Interval cur = list;
-            while (cur != i) {
-                assert cur != null && cur != Interval.EndMarker : "interval has not been found in list: " + i;
-                prev = cur;
-                cur = cur.next;
-            }
-            if (prev == null) {
-                set(binding, cur.next);
-            } else {
-                prev.next = cur.next;
-            }
-        }
-    }
-
-    /**
-     * Constants denoting the register usage priority for an interval. The constants are declared in
-     * increasing order of priority are are used to optimize spilling when multiple overlapping
-     * intervals compete for limited registers.
-     */
-    public enum RegisterPriority {
-        /**
-         * No special reason for an interval to be allocated a register.
-         */
-        None,
-
-        /**
-         * Priority level for intervals live at the end of a loop.
-         */
-        LiveAtLoopEnd,
-
-        /**
-         * Priority level for intervals that should be allocated to a register.
-         */
-        ShouldHaveRegister,
-
-        /**
-         * Priority level for intervals that must be allocated to a register.
-         */
-        MustHaveRegister;
-
-        public static final RegisterPriority[] VALUES = values();
-
-        /**
-         * Determines if this priority is higher than or equal to a given priority.
-         */
-        public boolean greaterEqual(RegisterPriority other) {
-            return ordinal() >= other.ordinal();
-        }
-
-        /**
-         * Determines if this priority is lower than a given priority.
-         */
-        public boolean lessThan(RegisterPriority other) {
-            return ordinal() < other.ordinal();
-        }
-    }
-
-    /**
-     * Constants denoting whether an interval is bound to a specific register. This models platform
-     * dependencies on register usage for certain instructions.
-     */
-    enum RegisterBinding {
-        /**
-         * Interval is bound to a specific register as required by the platform.
-         */
-        Fixed,
-
-        /**
-         * Interval has no specific register requirements.
-         */
-        Any,
-
-        /**
-         * Interval is bound to a stack slot.
-         */
-        Stack;
-
-        public static final RegisterBinding[] VALUES = values();
-    }
-
-    /**
-     * Constants denoting the linear-scan states an interval may be in with respect to the
-     * {@linkplain Interval#from() start} {@code position} of the interval being processed.
-     */
-    enum State {
-        /**
-         * An interval that starts after {@code position}.
-         */
-        Unhandled,
-
-        /**
-         * An interval that {@linkplain Interval#covers covers} {@code position} and has an assigned
-         * register.
-         */
-        Active,
-
-        /**
-         * An interval that starts before and ends after {@code position} but does not
-         * {@linkplain Interval#covers cover} it due to a lifetime hole.
-         */
-        Inactive,
-
-        /**
-         * An interval that ends before {@code position} or is spilled to memory.
-         */
-        Handled;
-    }
-
-    /**
-     * Constants used in optimization of spilling of an interval.
-     */
-    public enum SpillState {
-        /**
-         * Starting state of calculation: no definition found yet.
-         */
-        NoDefinitionFound,
-
-        /**
-         * One definition has already been found. Two consecutive definitions are treated as one
-         * (e.g. a consecutive move and add because of two-operand LIR form). The position of this
-         * definition is given by {@link Interval#spillDefinitionPos()}.
-         */
-        NoSpillStore,
-
-        /**
-         * One spill move has already been inserted.
-         */
-        OneSpillStore,
-
-        /**
-         * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere
-         * on the dominator path between the definition and the usages.
-         */
-        SpillInDominator,
-
-        /**
-         * The interval should be stored immediately after its definition to prevent multiple
-         * redundant stores.
-         */
-        StoreAtDefinition,
-
-        /**
-         * The interval starts in memory (e.g. method parameter), so a store is never necessary.
-         */
-        StartInMemory,
-
-        /**
-         * The interval has more than one definition (e.g. resulting from phi moves), so stores to
-         * memory are not optimized.
-         */
-        NoOptimization
-    }
-
-    /**
-     * List of use positions. Each entry in the list records the use position and register priority
-     * associated with the use position. The entries in the list are in descending order of use
-     * position.
-     *
-     */
-    public static final class UsePosList {
-
-        private IntList list;
-
-        /**
-         * Creates a use list.
-         *
-         * @param initialCapacity the initial capacity of the list in terms of entries
-         */
-        public UsePosList(int initialCapacity) {
-            list = new IntList(initialCapacity * 2);
-        }
-
-        private UsePosList(IntList list) {
-            this.list = list;
-        }
-
-        /**
-         * Splits this list around a given position. All entries in this list with a use position
-         * greater or equal than {@code splitPos} are removed from this list and added to the
-         * returned list.
-         *
-         * @param splitPos the position for the split
-         * @return a use position list containing all entries removed from this list that have a use
-         *         position greater or equal than {@code splitPos}
-         */
-        public UsePosList splitAt(int splitPos) {
-            int i = size() - 1;
-            int len = 0;
-            while (i >= 0 && usePos(i) < splitPos) {
-                --i;
-                len += 2;
-            }
-            int listSplitIndex = (i + 1) * 2;
-            IntList childList = list;
-            list = IntList.copy(this.list, listSplitIndex, len);
-            childList.setSize(listSplitIndex);
-            UsePosList child = new UsePosList(childList);
-            return child;
-        }
-
-        /**
-         * Gets the use position at a specified index in this list.
-         *
-         * @param index the index of the entry for which the use position is returned
-         * @return the use position of entry {@code index} in this list
-         */
-        public int usePos(int index) {
-            return list.get(index << 1);
-        }
-
-        /**
-         * Gets the register priority for the use position at a specified index in this list.
-         *
-         * @param index the index of the entry for which the register priority is returned
-         * @return the register priority of entry {@code index} in this list
-         */
-        public RegisterPriority registerPriority(int index) {
-            return RegisterPriority.VALUES[list.get((index << 1) + 1)];
-        }
-
-        public void add(int usePos, RegisterPriority registerPriority) {
-            assert list.size() == 0 || usePos(size() - 1) > usePos;
-            list.add(usePos);
-            list.add(registerPriority.ordinal());
-        }
-
-        public int size() {
-            return list.size() >> 1;
-        }
-
-        public void removeLowestUsePos() {
-            list.setSize(list.size() - 2);
-        }
-
-        public void setRegisterPriority(int index, RegisterPriority registerPriority) {
-            list.set((index << 1) + 1, registerPriority.ordinal());
-        }
-
-        @Override
-        public String toString() {
-            StringBuilder buf = new StringBuilder("[");
-            for (int i = size() - 1; i >= 0; --i) {
-                if (buf.length() != 1) {
-                    buf.append(", ");
-                }
-                RegisterPriority prio = registerPriority(i);
-                buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio);
-            }
-            return buf.append("]").toString();
-        }
-    }
-
-    /**
-     * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval
-     * prior to register allocation.
-     */
-    public final AllocatableValue operand;
-
-    /**
-     * The operand number for this interval's {@linkplain #operand operand}.
-     */
-    public final int operandNumber;
-
-    /**
-     * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this
-     * interval. In case of a spilled interval which is re-materialized this is
-     * {@link Value#ILLEGAL}.
-     */
-    private AllocatableValue location;
-
-    /**
-     * The stack slot to which all splits of this interval are spilled if necessary.
-     */
-    private StackSlotValue spillSlot;
-
-    /**
-     * The kind of this interval.
-     */
-    private LIRKind kind;
-
-    /**
-     * The head of the list of ranges describing this interval. This list is sorted by
-     * {@linkplain LIRInstruction#id instruction ids}.
-     */
-    private Range first;
-
-    /**
-     * List of (use-positions, register-priorities) pairs, sorted by use-positions.
-     */
-    private UsePosList usePosList;
-
-    /**
-     * Iterator used to traverse the ranges of an interval.
-     */
-    private Range current;
-
-    /**
-     * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.
-     */
-    Interval next;
-
-    /**
-     * The linear-scan state of this interval.
-     */
-    State state;
-
-    private int cachedTo; // cached value: to of last range (-1: not cached)
-
-    /**
-     * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split
-     * parent}, it points to itself.
-     */
-    private Interval splitParent;
-
-    /**
-     * List of all intervals that are split off from this interval. This is only used if this is a
-     * {@linkplain #isSplitParent() split parent}.
-     */
-    private List<Interval> splitChildren = Collections.emptyList();
-
-    /**
-     * Current split child that has been active or inactive last (always stored in split parents).
-     */
-    private Interval currentSplitChild;
-
-    /**
-     * Specifies if move is inserted between currentSplitChild and this interval when interval gets
-     * active the first time.
-     */
-    private boolean insertMoveWhenActivated;
-
-    /**
-     * For spill move optimization.
-     */
-    private SpillState spillState;
-
-    /**
-     * Position where this interval is defined (if defined only once).
-     */
-    private int spillDefinitionPos;
-
-    /**
-     * This interval should be assigned the same location as the hint interval.
-     */
-    private Interval locationHint;
-
-    /**
-     * The value with which a spilled child interval can be re-materialized. Currently this must be
-     * a Constant.
-     */
-    private JavaConstant materializedValue;
-
-    /**
-     * The number of times {@link #addMaterializationValue(JavaConstant)} is called.
-     */
-    private int numMaterializationValuesAdded;
-
-    void assignLocation(AllocatableValue newLocation) {
-        if (isRegister(newLocation)) {
-            assert this.location == null : "cannot re-assign location for " + this;
-            if (newLocation.getLIRKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) {
-                this.location = asRegister(newLocation).asValue(kind);
-                return;
-            }
-        } else if (isIllegal(newLocation)) {
-            assert canMaterialize();
-        } else {
-            assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this;
-            assert isStackSlotValue(newLocation);
-            assert !newLocation.getLIRKind().equals(LIRKind.Illegal);
-            assert newLocation.getLIRKind().equals(this.kind);
-        }
-        this.location = newLocation;
-    }
-
-    /**
-     * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to
-     * this interval.
-     */
-    public AllocatableValue location() {
-        return location;
-    }
-
-    public LIRKind kind() {
-        assert !isRegister(operand) : "cannot access type for fixed interval";
-        return kind;
-    }
-
-    public void setKind(LIRKind kind) {
-        assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type";
-        this.kind = kind;
-    }
-
-    public Range first() {
-        return first;
-    }
-
-    public int from() {
-        return first.from;
-    }
-
-    int to() {
-        if (cachedTo == -1) {
-            cachedTo = calcTo();
-        }
-        assert cachedTo == calcTo() : "invalid cached value";
-        return cachedTo;
-    }
-
-    int numUsePositions() {
-        return usePosList.size();
-    }
-
-    public void setLocationHint(Interval interval) {
-        locationHint = interval;
-    }
-
-    public boolean isSplitParent() {
-        return splitParent == this;
-    }
-
-    boolean isSplitChild() {
-        return splitParent != this;
-    }
-
-    /**
-     * Gets the split parent for this interval.
-     */
-    public Interval splitParent() {
-        assert splitParent.isSplitParent() : "not a split parent: " + this;
-        return splitParent;
-    }
-
-    /**
-     * Gets the canonical spill slot for this interval.
-     */
-    public StackSlotValue spillSlot() {
-        return splitParent().spillSlot;
-    }
-
-    public void setSpillSlot(StackSlotValue slot) {
-        assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot";
-        splitParent().spillSlot = slot;
-    }
-
-    Interval currentSplitChild() {
-        return splitParent().currentSplitChild;
-    }
-
-    void makeCurrentSplitChild() {
-        splitParent().currentSplitChild = this;
-    }
-
-    boolean insertMoveWhenActivated() {
-        return insertMoveWhenActivated;
-    }
-
-    void setInsertMoveWhenActivated(boolean b) {
-        insertMoveWhenActivated = b;
-    }
-
-    // for spill optimization
-    public SpillState spillState() {
-        return splitParent().spillState;
-    }
-
-    public int spillDefinitionPos() {
-        return splitParent().spillDefinitionPos;
-    }
-
-    public void setSpillState(SpillState state) {
-        assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
-        splitParent().spillState = state;
-    }
-
-    public void setSpillDefinitionPos(int pos) {
-        assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice";
-        splitParent().spillDefinitionPos = pos;
-    }
-
-    // returns true if this interval has a shadow copy on the stack that is always correct
-    public boolean alwaysInMemory() {
-        return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) &&
-                        !canMaterialize();
-    }
-
-    void removeFirstUsePos() {
-        usePosList.removeLowestUsePos();
-    }
-
-    // test intersection
-    boolean intersects(Interval i) {
-        return first.intersects(i.first);
-    }
-
-    int intersectsAt(Interval i) {
-        return first.intersectsAt(i.first);
-    }
-
-    // range iteration
-    void rewindRange() {
-        current = first;
-    }
-
-    void nextRange() {
-        assert this != EndMarker : "not allowed on sentinel";
-        current = current.next;
-    }
-
-    int currentFrom() {
-        return current.from;
-    }
-
-    int currentTo() {
-        return current.to;
-    }
-
-    boolean currentAtEnd() {
-        return current == Range.EndMarker;
-    }
-
-    boolean currentIntersects(Interval it) {
-        return current.intersects(it.current);
-    }
-
-    int currentIntersectsAt(Interval it) {
-        return current.intersectsAt(it.current);
-    }
-
-    /**
-     * Sentinel interval to denote the end of an interval list.
-     */
-    static final Interval EndMarker = new Interval(Value.ILLEGAL, -1);
-
-    Interval(AllocatableValue operand, int operandNumber) {
-        assert operand != null;
-        this.operand = operand;
-        this.operandNumber = operandNumber;
-        if (isRegister(operand)) {
-            location = operand;
-        } else {
-            assert isIllegal(operand) || isVariable(operand);
-        }
-        this.kind = LIRKind.Illegal;
-        this.first = Range.EndMarker;
-        this.usePosList = new UsePosList(4);
-        this.current = Range.EndMarker;
-        this.next = EndMarker;
-        this.cachedTo = -1;
-        this.spillState = SpillState.NoDefinitionFound;
-        this.spillDefinitionPos = -1;
-        splitParent = this;
-        currentSplitChild = this;
-    }
-
-    /**
-     * Sets the value which is used for re-materialization.
-     */
-    public void addMaterializationValue(JavaConstant value) {
-        if (numMaterializationValuesAdded == 0) {
-            materializedValue = value;
-        } else {
-            // Interval is defined on multiple places -> no materialization is possible.
-            materializedValue = null;
-        }
-        numMaterializationValuesAdded++;
-    }
-
-    /**
-     * Returns true if this interval can be re-materialized when spilled. This means that no
-     * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored.
-     */
-    public boolean canMaterialize() {
-        return getMaterializedValue() != null;
-    }
-
-    /**
-     * Returns a value which can be moved to a register instead of a restore-move from stack.
-     */
-    public JavaConstant getMaterializedValue() {
-        return splitParent().materializedValue;
-    }
-
-    int calcTo() {
-        assert first != Range.EndMarker : "interval has no range";
-
-        Range r = first;
-        while (r.next != Range.EndMarker) {
-            r = r.next;
-        }
-        return r.to;
-    }
-
-    // consistency check of split-children
-    boolean checkSplitChildren() {
-        if (!splitChildren.isEmpty()) {
-            assert isSplitParent() : "only split parents can have children";
-
-            for (int i = 0; i < splitChildren.size(); i++) {
-                Interval i1 = splitChildren.get(i);
-
-                assert i1.splitParent() == this : "not a split child of this interval";
-                assert i1.kind().equals(kind()) : "must be equal for all split children";
-                assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children";
-
-                for (int j = i + 1; j < splitChildren.size(); j++) {
-                    Interval i2 = splitChildren.get(j);
-
-                    assert !i1.operand.equals(i2.operand) : "same register number";
-
-                    if (i1.from() < i2.from()) {
-                        assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping";
-                    } else {
-                        assert i2.from() < i1.from() : "intervals start at same opId";
-                        assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping";
-                    }
-                }
-            }
-        }
-
-        return true;
-    }
-
-    public Interval locationHint(boolean searchSplitChild) {
-        if (!searchSplitChild) {
-            return locationHint;
-        }
-
-        if (locationHint != null) {
-            assert locationHint.isSplitParent() : "ony split parents are valid hint registers";
-
-            if (locationHint.location != null && isRegister(locationHint.location)) {
-                return locationHint;
-            } else if (!locationHint.splitChildren.isEmpty()) {
-                // search the first split child that has a register assigned
-                int len = locationHint.splitChildren.size();
-                for (int i = 0; i < len; i++) {
-                    Interval interval = locationHint.splitChildren.get(i);
-                    if (interval.location != null && isRegister(interval.location)) {
-                        return interval;
-                    }
-                }
-            }
-        }
-
-        // no hint interval found that has a register assigned
-        return null;
-    }
-
-    Interval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, TraceLinearScan allocator) {
-        assert isSplitParent() : "can only be called for split parents";
-        assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
-
-        if (splitChildren.isEmpty()) {
-            assert this.covers(opId, mode) : this + " does not cover " + opId;
-            return this;
-        } else {
-            Interval result = null;
-            int len = splitChildren.size();
-
-            // in outputMode, the end of the interval (opId == cur.to()) is not valid
-            int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1);
-
-            int i;
-            for (i = 0; i < len; i++) {
-                Interval cur = splitChildren.get(i);
-                if (cur.from() <= opId && opId < cur.to() + toOffset) {
-                    if (i > 0) {
-                        // exchange current split child to start of list (faster access for next
-                        // call)
-                        Util.atPutGrow(splitChildren, i, splitChildren.get(0), null);
-                        Util.atPutGrow(splitChildren, 0, cur, null);
-                    }
-
-                    // interval found
-                    result = cur;
-                    break;
-                }
-            }
-
-            assert checkSplitChild(result, opId, allocator, toOffset, mode);
-            return result;
-        }
-    }
-
-    private boolean checkSplitChild(Interval result, int opId, TraceLinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) {
-        if (result == null) {
-            // this is an error
-            StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
-            if (!splitChildren.isEmpty()) {
-                Interval firstChild = splitChildren.get(0);
-                Interval lastChild = splitChildren.get(splitChildren.size() - 1);
-                msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
-            }
-            throw new JVMCIError("Linear Scan Error: %s", msg);
-        }
-
-        if (!splitChildren.isEmpty()) {
-            for (Interval interval : splitChildren) {
-                if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
-                    TTY.println(String.format("two valid result intervals found for opId %d: %d and %d", opId, result.operandNumber, interval.operandNumber));
-                    TTY.println(result.logString(allocator));
-                    TTY.println(interval.logString(allocator));
-                    throw new BailoutException("two valid result intervals found");
-                }
-            }
-        }
-        assert result.covers(opId, mode) : "opId not covered by interval";
-        return true;
-    }
-
-    // returns the interval that covers the given opId or null if there is none
-    Interval getIntervalCoveringOpId(int opId) {
-        assert opId >= 0 : "invalid opId";
-        assert opId < to() : "can only look into the past";
-
-        if (opId >= from()) {
-            return this;
-        }
-
-        Interval parent = splitParent();
-        Interval result = null;
-
-        assert !parent.splitChildren.isEmpty() : "no split children available";
-        int len = parent.splitChildren.size();
-
-        for (int i = len - 1; i >= 0; i--) {
-            Interval cur = parent.splitChildren.get(i);
-            if (cur.from() <= opId && opId < cur.to()) {
-                assert result == null : "covered by multiple split children " + result + " and " + cur;
-                result = cur;
-            }
-        }
-
-        return result;
-    }
-
-    // returns the last split child that ends before the given opId
-    Interval getSplitChildBeforeOpId(int opId) {
-        assert opId >= 0 : "invalid opId";
-
-        Interval parent = splitParent();
-        Interval result = null;
-
-        assert !parent.splitChildren.isEmpty() : "no split children available";
-        int len = parent.splitChildren.size();
-
-        for (int i = len - 1; i >= 0; i--) {
-            Interval cur = parent.splitChildren.get(i);
-            if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
-                result = cur;
-            }
-        }
-
-        assert result != null : "no split child found";
-        return result;
-    }
-
-    // checks if opId is covered by any split child
-    boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) {
-        assert isSplitParent() : "can only be called for split parents";
-        assert opId >= 0 : "invalid opId (method can not be called for spill moves)";
-
-        if (splitChildren.isEmpty()) {
-            // simple case if interval was not split
-            return covers(opId, mode);
-
-        } else {
-            // extended case: check all split children
-            int len = splitChildren.size();
-            for (int i = 0; i < len; i++) {
-                Interval cur = splitChildren.get(i);
-                if (cur.covers(opId, mode)) {
-                    return true;
-                }
-            }
-            return false;
-        }
-    }
-
-    private RegisterPriority adaptPriority(RegisterPriority priority) {
-        /*
-         * In case of re-materialized values we require that use-operands are registers, because we
-         * don't have the value in a stack location. (Note that ShouldHaveRegister means that the
-         * operand can also be a StackSlot).
-         */
-        if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) {
-            return RegisterPriority.MustHaveRegister;
-        }
-        return priority;
-    }
-
-    // Note: use positions are sorted descending . first use has highest index
-    int firstUsage(RegisterPriority minRegisterPriority) {
-        assert isVariable(operand) : "cannot access use positions for fixed intervals";
-
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i));
-            if (registerPriority.greaterEqual(minRegisterPriority)) {
-                return usePosList.usePos(i);
-            }
-        }
-        return Integer.MAX_VALUE;
-    }
-
-    int nextUsage(RegisterPriority minRegisterPriority, int from) {
-        assert isVariable(operand) : "cannot access use positions for fixed intervals";
-
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            int usePos = usePosList.usePos(i);
-            if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
-                return usePos;
-            }
-        }
-        return Integer.MAX_VALUE;
-    }
-
-    int nextUsageExact(RegisterPriority exactRegisterPriority, int from) {
-        assert isVariable(operand) : "cannot access use positions for fixed intervals";
-
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            int usePos = usePosList.usePos(i);
-            if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) {
-                return usePos;
-            }
-        }
-        return Integer.MAX_VALUE;
-    }
-
-    int previousUsage(RegisterPriority minRegisterPriority, int from) {
-        assert isVariable(operand) : "cannot access use positions for fixed intervals";
-
-        int prev = -1;
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            int usePos = usePosList.usePos(i);
-            if (usePos > from) {
-                return prev;
-            }
-            if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
-                prev = usePos;
-            }
-        }
-        return prev;
-    }
-
-    public void addUsePos(int pos, RegisterPriority registerPriority) {
-        assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
-
-        // do not add use positions for precolored intervals because they are never used
-        if (registerPriority != RegisterPriority.None && isVariable(operand)) {
-            if (DetailedAsserts.getValue()) {
-                for (int i = 0; i < usePosList.size(); i++) {
-                    assert pos <= usePosList.usePos(i) : "already added a use-position with lower position";
-                    if (i > 0) {
-                        assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending";
-                    }
-                }
-            }
-
-            // Note: addUse is called in descending order, so list gets sorted
-            // automatically by just appending new use positions
-            int len = usePosList.size();
-            if (len == 0 || usePosList.usePos(len - 1) > pos) {
-                usePosList.add(pos, registerPriority);
-            } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) {
-                assert usePosList.usePos(len - 1) == pos : "list not sorted correctly";
-                usePosList.setRegisterPriority(len - 1, registerPriority);
-            }
-        }
-    }
-
-    public void addRange(int from, int to) {
-        assert from < to : "invalid range";
-        assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval";
-        assert from <= first().to : "not inserting at begin of interval";
-
-        if (first.from <= to) {
-            assert first != Range.EndMarker;
-            // join intersecting ranges
-            first.from = Math.min(from, first().from);
-            first.to = Math.max(to, first().to);
-        } else {
-            // insert new range
-            first = new Range(from, to, first());
-        }
-    }
-
-    Interval newSplitChild(TraceLinearScan allocator) {
-        // allocate new interval
-        Interval parent = splitParent();
-        Interval result = allocator.createDerivedInterval(parent);
-        result.setKind(kind());
-
-        result.splitParent = parent;
-        result.setLocationHint(parent);
-
-        // insert new interval in children-list of parent
-        if (parent.splitChildren.isEmpty()) {
-            assert isSplitParent() : "list must be initialized at first split";
-
-            // Create new non-shared list
-            parent.splitChildren = new ArrayList<>(4);
-            parent.splitChildren.add(this);
-        }
-        parent.splitChildren.add(result);
-
-        return result;
-    }
-
-    /**
-     * Splits this interval at a specified position and returns the remainder as a new <i>child</i>
-     * interval of this interval's {@linkplain #splitParent() parent} interval.
-     * <p>
-     * When an interval is split, a bi-directional link is established between the original
-     * <i>parent</i> interval and the <i>children</i> intervals that are split off this interval.
-     * When a split child is split again, the new created interval is a direct child of the original
-     * parent. That is, there is no tree of split children stored, just a flat list. All split
-     * children are spilled to the same {@linkplain #spillSlot spill slot}.
-     *
-     * @param splitPos the position at which to split this interval
-     * @param allocator the register allocator context
-     * @return the child interval split off from this interval
-     */
-    Interval split(int splitPos, TraceLinearScan allocator) {
-        assert isVariable(operand) : "cannot split fixed intervals";
-
-        // allocate new interval
-        Interval result = newSplitChild(allocator);
-
-        // split the ranges
-        Range prev = null;
-        Range cur = first;
-        while (cur != Range.EndMarker && cur.to <= splitPos) {
-            prev = cur;
-            cur = cur.next;
-        }
-        assert cur != Range.EndMarker : "split interval after end of last range";
-
-        if (cur.from < splitPos) {
-            result.first = new Range(splitPos, cur.to, cur.next);
-            cur.to = splitPos;
-            cur.next = Range.EndMarker;
-
-        } else {
-            assert prev != null : "split before start of first range";
-            result.first = cur;
-            prev.next = Range.EndMarker;
-        }
-        result.current = result.first;
-        cachedTo = -1; // clear cached value
-
-        // split list of use positions
-        result.usePosList = usePosList.splitAt(splitPos);
-
-        if (DetailedAsserts.getValue()) {
-            for (int i = 0; i < usePosList.size(); i++) {
-                assert usePosList.usePos(i) < splitPos;
-            }
-            for (int i = 0; i < result.usePosList.size(); i++) {
-                assert result.usePosList.usePos(i) >= splitPos;
-            }
-        }
-        return result;
-    }
-
-    /**
-     * Splits this interval at a specified position and returns the head as a new interval (this
-     * interval is the tail).
-     *
-     * Currently, only the first range can be split, and the new interval must not have split
-     * positions
-     */
-    Interval splitFromStart(int splitPos, TraceLinearScan allocator) {
-        assert isVariable(operand) : "cannot split fixed intervals";
-        assert splitPos > from() && splitPos < to() : "can only split inside interval";
-        assert splitPos > first.from && splitPos <= first.to : "can only split inside first range";
-        assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present";
-
-        // allocate new interval
-        Interval result = newSplitChild(allocator);
-
-        // the new interval has only one range (checked by assertion above,
-        // so the splitting of the ranges is very simple
-        result.addRange(first.from, splitPos);
-
-        if (splitPos == first.to) {
-            assert first.next != Range.EndMarker : "must not be at end";
-            first = first.next;
-        } else {
-            first.from = splitPos;
-        }
-
-        return result;
-    }
-
-    // returns true if the opId is inside the interval
-    boolean covers(int opId, LIRInstruction.OperandMode mode) {
-        Range cur = first;
-
-        while (cur != Range.EndMarker && cur.to < opId) {
-            cur = cur.next;
-        }
-        if (cur != Range.EndMarker) {
-            assert cur.to != cur.next.from : "ranges not separated";
-
-            if (mode == LIRInstruction.OperandMode.DEF) {
-                return cur.from <= opId && opId < cur.to;
-            } else {
-                return cur.from <= opId && opId <= cur.to;
-            }
-        }
-        return false;
-    }
-
-    // returns true if the interval has any hole between holeFrom and holeTo
-    // (even if the hole has only the length 1)
-    boolean hasHoleBetween(int holeFrom, int holeTo) {
-        assert holeFrom < holeTo : "check";
-        assert from() <= holeFrom && holeTo <= to() : "index out of interval";
-
-        Range cur = first;
-        while (cur != Range.EndMarker) {
-            assert cur.to < cur.next.from : "no space between ranges";
-
-            // hole-range starts before this range . hole
-            if (holeFrom < cur.from) {
-                return true;
-
-                // hole-range completely inside this range . no hole
-            } else {
-                if (holeTo <= cur.to) {
-                    return false;
-
-                    // overlapping of hole-range with this range . hole
-                } else {
-                    if (holeFrom <= cur.to) {
-                        return true;
-                    }
-                }
-            }
-
-            cur = cur.next;
-        }
-
-        return false;
-    }
-
-    @Override
-    public String toString() {
-        String from = "?";
-        String to = "?";
-        if (first != null && first != Range.EndMarker) {
-            from = String.valueOf(from());
-            // to() may cache a computed value, modifying the current object, which is a bad idea
-            // for a printing function. Compute it directly instead.
-            to = String.valueOf(calcTo());
-        }
-        String locationString = this.location == null ? "" : "@" + this.location;
-        return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
-    }
-
-    /**
-     * Gets the use position information for this interval.
-     */
-    public UsePosList usePosList() {
-        return usePosList;
-    }
-
-    /**
-     * Gets a single line string for logging the details of this interval to a log stream.
-     *
-     * @param allocator the register allocator context
-     */
-    public String logString(TraceLinearScan allocator) {
-        StringBuilder buf = new StringBuilder(100);
-        buf.append(operandNumber).append(':').append(operand).append(' ');
-        if (!isRegister(operand)) {
-            if (location != null) {
-                buf.append("location{").append(location).append("} ");
-            }
-        }
-
-        buf.append("hints{").append(splitParent.operandNumber);
-        Interval hint = locationHint(false);
-        if (hint != null && hint.operandNumber != splitParent.operandNumber) {
-            buf.append(", ").append(hint.operandNumber);
-        }
-        buf.append("} ranges{");
-
-        // print ranges
-        Range cur = first;
-        while (cur != Range.EndMarker) {
-            if (cur != first) {
-                buf.append(", ");
-            }
-            buf.append(cur);
-            cur = cur.next;
-            assert cur != null : "range list not closed with range sentinel";
-        }
-        buf.append("} uses{");
-
-        // print use positions
-        int prev = -1;
-        for (int i = usePosList.size() - 1; i >= 0; --i) {
-            assert prev < usePosList.usePos(i) : "use positions not sorted";
-            if (i != usePosList.size() - 1) {
-                buf.append(", ");
-            }
-            buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i));
-            prev = usePosList.usePos(i);
-        }
-        buf.append("} spill-state{").append(spillState()).append("}");
-        if (canMaterialize()) {
-            buf.append(" (remat:").append(getMaterializedValue().toString()).append(")");
-        }
-        return buf.toString();
-    }
-
-    List<Interval> getSplitChildren() {
-        return Collections.unmodifiableList(splitChildren);
-    }
-}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalWalker.java	Tue Sep 01 12:03:14 2015 +0200
@@ -24,9 +24,9 @@
 
 import com.oracle.graal.debug.*;
 
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBindingLists;
-import com.oracle.graal.lir.alloc.trace.Interval.State;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBindingLists;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.State;
 
 /**
  */
@@ -65,7 +65,7 @@
      *
      * @return {@code true} if a register was allocated to the {@code currentInterval} interval
      */
-    protected boolean activateCurrent(@SuppressWarnings({"unused"}) Interval currentInterval) {
+    protected boolean activateCurrent(@SuppressWarnings({"unused"}) TraceInterval currentInterval) {
         return true;
     }
 
@@ -86,16 +86,16 @@
      * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
      *            intervals
      */
-    IntervalWalker(TraceLinearScan allocator, Interval unhandledFixed, Interval unhandledAny) {
+    IntervalWalker(TraceLinearScan allocator, TraceInterval unhandledFixed, TraceInterval unhandledAny) {
         this.allocator = allocator;
 
-        unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, Interval.EndMarker);
-        activeLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
-        inactiveLists = new RegisterBindingLists(Interval.EndMarker, Interval.EndMarker, Interval.EndMarker);
+        unhandledLists = new RegisterBindingLists(unhandledFixed, unhandledAny, TraceInterval.EndMarker);
+        activeLists = new RegisterBindingLists(TraceInterval.EndMarker, TraceInterval.EndMarker, TraceInterval.EndMarker);
+        inactiveLists = new RegisterBindingLists(TraceInterval.EndMarker, TraceInterval.EndMarker, TraceInterval.EndMarker);
         currentPosition = -1;
     }
 
-    protected void removeFromList(Interval interval) {
+    protected void removeFromList(TraceInterval interval) {
         if (interval.state == State.Active) {
             activeLists.remove(RegisterBinding.Any, interval);
         } else {
@@ -112,11 +112,11 @@
     }
 
     private void walkTo(State state, int from, RegisterBinding binding) {
-        Interval prevprev = null;
-        Interval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding);
-        Interval next = prev;
+        TraceInterval prevprev = null;
+        TraceInterval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding);
+        TraceInterval next = prev;
         while (next.currentFrom() <= from) {
-            Interval cur = next;
+            TraceInterval cur = next;
             next = cur.next;
 
             boolean rangeHasChanged = false;
@@ -140,7 +140,7 @@
                     prevprev.next = next;
                 }
                 prev = next;
-                Interval.State newState;
+                TraceInterval.State newState;
                 if (cur.currentAtEnd()) {
                     // move to handled state (not maintained as a list)
                     newState = State.Handled;
@@ -179,24 +179,24 @@
      * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled}
      *         interval at position {@code toOpId}.
      */
-    private Interval nextInterval(int toOpId) {
+    private TraceInterval nextInterval(int toOpId) {
         RegisterBinding binding;
-        Interval any = unhandledLists.any;
-        Interval fixed = unhandledLists.fixed;
+        TraceInterval any = unhandledLists.any;
+        TraceInterval fixed = unhandledLists.fixed;
 
-        if (any != Interval.EndMarker) {
+        if (any != TraceInterval.EndMarker) {
             // intervals may start at same position . prefer fixed interval
-            binding = fixed != Interval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any;
+            binding = fixed != TraceInterval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any;
 
             assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!";
-            assert any == Interval.EndMarker || fixed == Interval.EndMarker || any.from() != fixed.from() || binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first";
+            assert any == TraceInterval.EndMarker || fixed == TraceInterval.EndMarker || any.from() != fixed.from() || binding == RegisterBinding.Fixed : "if fixed and any-Interval start at same position, fixed must be processed first";
 
-        } else if (fixed != Interval.EndMarker) {
+        } else if (fixed != TraceInterval.EndMarker) {
             binding = RegisterBinding.Fixed;
         } else {
             return null;
         }
-        Interval currentInterval = unhandledLists.get(binding);
+        TraceInterval currentInterval = unhandledLists.get(binding);
 
         if (toOpId < currentInterval.from()) {
             return null;
@@ -204,7 +204,7 @@
 
         currentBinding = binding;
         unhandledLists.set(binding, currentInterval.next);
-        currentInterval.next = Interval.EndMarker;
+        currentInterval.next = TraceInterval.EndMarker;
         currentInterval.rewindRange();
         return currentInterval;
     }
@@ -213,12 +213,12 @@
      * Walk up to {@code toOpId}.
      *
      * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and
-     *                {@link #inactiveLists} are populated and {@link Interval#state}s are up to
+     *                {@link #inactiveLists} are populated and {@link TraceInterval#state}s are up to
      *                date.
      */
     protected void walkTo(int toOpId) {
         assert currentPosition <= toOpId : "can not walk backwards";
-        for (Interval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
+        for (TraceInterval currentInterval = nextInterval(toOpId); currentInterval != null; currentInterval = nextInterval(toOpId)) {
             int opId = currentInterval.from();
 
             // set currentPosition prior to call of walkTo
@@ -252,7 +252,7 @@
         }
     }
 
-    private void intervalMoved(Interval interval, State from, State to) {
+    private void intervalMoved(TraceInterval interval, State from, State to) {
         // intervalMoved() is called whenever an interval moves from one interval list to another.
         // In the implementation of this method it is prohibited to move the interval to any list.
         if (Debug.isLogEnabled()) {
@@ -268,9 +268,9 @@
      * any} intervals this is done in {@link #nextInterval(int)}.
      */
     private void updateUnhandledStackIntervals(int opId) {
-        Interval currentInterval = unhandledLists.get(RegisterBinding.Stack);
-        while (currentInterval != Interval.EndMarker && currentInterval.from() <= opId) {
-            Interval next = currentInterval.next;
+        TraceInterval currentInterval = unhandledLists.get(RegisterBinding.Stack);
+        while (currentInterval != TraceInterval.EndMarker && currentInterval.from() <= opId) {
+            TraceInterval next = currentInterval.next;
             if (currentInterval.to() > opId) {
                 currentInterval.state = State.Active;
                 activeLists.addToListSortedByCurrentFromPositions(RegisterBinding.Stack, currentInterval);

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanAssignLocationsPhase.java	Tue Sep 01 12:03:14 2015 +0200
@@ -70,7 +70,7 @@
      */
     protected Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) {
         int opId = op.id();
-        Interval interval = allocator.intervalFor(operand);
+        TraceInterval interval = allocator.intervalFor(operand);
         assert interval != null : "interval must exist";
 
         if (opId != -1) {

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanWalker.java	Tue Sep 01 12:03:14 2015 +0200
@@ -38,10 +38,10 @@
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.StandardOp.ValueMoveOp;
 import com.oracle.graal.lir.alloc.lsra.*;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority;
-import com.oracle.graal.lir.alloc.trace.Interval.SpillState;
-import com.oracle.graal.lir.alloc.trace.Interval.State;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.State;
 
 /**
  */
@@ -52,7 +52,7 @@
     protected final int[] usePos;
     protected final int[] blockPos;
 
-    protected List<Interval>[] spillIntervals;
+    protected List<TraceInterval>[] spillIntervals;
 
     private TraceLocalMoveResolver moveResolver; // for ordering spill moves
 
@@ -66,7 +66,7 @@
      * bootstrap run of Graal). Therefore, we initialize {@link #spillIntervals} with this marker
      * value, and allocate a "real" list only on demand in {@link #setUsePos}.
      */
-    private static final List<Interval> EMPTY_LIST = new ArrayList<>(0);
+    private static final List<TraceInterval> EMPTY_LIST = new ArrayList<>(0);
 
     // accessors mapped to same functions in class LinearScan
     int blockCount() {
@@ -81,7 +81,7 @@
         return allocator.blockForId(opId);
     }
 
-    LinearScanWalker(TraceLinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) {
+    LinearScanWalker(TraceLinearScan allocator, TraceInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
         super(allocator, unhandledFixedFirst, unhandledAnyFirst);
 
         moveResolver = allocator.createMoveResolver();
@@ -117,7 +117,7 @@
         return reg >= minRegisterNumber() && reg <= maxRegisterNumber();
     }
 
-    void excludeFromUse(Interval i) {
+    void excludeFromUse(TraceInterval i) {
         Value location = i.location();
         int i1 = asRegister(location).number;
         if (isRegisterInRange(i1)) {
@@ -125,7 +125,7 @@
         }
     }
 
-    void setUsePos(Interval interval, int usePos, boolean onlyProcessUsePos) {
+    void setUsePos(TraceInterval interval, int usePos, boolean onlyProcessUsePos) {
         if (usePos != -1) {
             assert usePos != 0 : "must use excludeFromUse to set usePos to 0";
             int i = asRegister(interval.location()).number;
@@ -134,7 +134,7 @@
                     this.usePos[i] = usePos;
                 }
                 if (!onlyProcessUsePos) {
-                    List<Interval> list = spillIntervals[i];
+                    List<TraceInterval> list = spillIntervals[i];
                     if (list == EMPTY_LIST) {
                         list = new ArrayList<>(2);
                         spillIntervals[i] = list;
@@ -145,7 +145,7 @@
         }
     }
 
-    void setBlockPos(Interval i, int blockPos) {
+    void setBlockPos(TraceInterval i, int blockPos) {
         if (blockPos != -1) {
             int reg = asRegister(i.location()).number;
             if (isRegisterInRange(reg)) {
@@ -160,8 +160,8 @@
     }
 
     void freeExcludeActiveFixed() {
-        Interval interval = activeLists.get(RegisterBinding.Fixed);
-        while (interval != Interval.EndMarker) {
+        TraceInterval interval = activeLists.get(RegisterBinding.Fixed);
+        while (interval != TraceInterval.EndMarker) {
             assert isRegister(interval.location()) : "active interval must have a register assigned";
             excludeFromUse(interval);
             interval = interval.next;
@@ -169,17 +169,17 @@
     }
 
     void freeExcludeActiveAny() {
-        Interval interval = activeLists.get(RegisterBinding.Any);
-        while (interval != Interval.EndMarker) {
+        TraceInterval interval = activeLists.get(RegisterBinding.Any);
+        while (interval != TraceInterval.EndMarker) {
             assert isRegister(interval.location()) : "active interval must have a register assigned";
             excludeFromUse(interval);
             interval = interval.next;
         }
     }
 
-    void freeCollectInactiveFixed(Interval current) {
-        Interval interval = inactiveLists.get(RegisterBinding.Fixed);
-        while (interval != Interval.EndMarker) {
+    void freeCollectInactiveFixed(TraceInterval current) {
+        TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed);
+        while (interval != TraceInterval.EndMarker) {
             if (current.to() <= interval.currentFrom()) {
                 assert interval.currentIntersectsAt(current) == -1 : "must not intersect";
                 setUsePos(interval, interval.currentFrom(), true);
@@ -190,17 +190,17 @@
         }
     }
 
-    void freeCollectInactiveAny(Interval current) {
-        Interval interval = inactiveLists.get(RegisterBinding.Any);
-        while (interval != Interval.EndMarker) {
+    void freeCollectInactiveAny(TraceInterval current) {
+        TraceInterval interval = inactiveLists.get(RegisterBinding.Any);
+        while (interval != TraceInterval.EndMarker) {
             setUsePos(interval, interval.currentIntersectsAt(current), true);
             interval = interval.next;
         }
     }
 
-    void freeCollectUnhandled(RegisterBinding kind, Interval current) {
-        Interval interval = unhandledLists.get(kind);
-        while (interval != Interval.EndMarker) {
+    void freeCollectUnhandled(RegisterBinding kind, TraceInterval current) {
+        TraceInterval interval = unhandledLists.get(kind);
+        while (interval != TraceInterval.EndMarker) {
             setUsePos(interval, interval.intersectsAt(current), true);
             if (kind == RegisterBinding.Fixed && current.to() <= interval.from()) {
                 setUsePos(interval, interval.from(), true);
@@ -210,24 +210,24 @@
     }
 
     void spillExcludeActiveFixed() {
-        Interval interval = activeLists.get(RegisterBinding.Fixed);
-        while (interval != Interval.EndMarker) {
+        TraceInterval interval = activeLists.get(RegisterBinding.Fixed);
+        while (interval != TraceInterval.EndMarker) {
             excludeFromUse(interval);
             interval = interval.next;
         }
     }
 
-    void spillBlockUnhandledFixed(Interval current) {
-        Interval interval = unhandledLists.get(RegisterBinding.Fixed);
-        while (interval != Interval.EndMarker) {
+    void spillBlockUnhandledFixed(TraceInterval current) {
+        TraceInterval interval = unhandledLists.get(RegisterBinding.Fixed);
+        while (interval != TraceInterval.EndMarker) {
             setBlockPos(interval, interval.intersectsAt(current));
             interval = interval.next;
         }
     }
 
-    void spillBlockInactiveFixed(Interval current) {
-        Interval interval = inactiveLists.get(RegisterBinding.Fixed);
-        while (interval != Interval.EndMarker) {
+    void spillBlockInactiveFixed(TraceInterval current) {
+        TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed);
+        while (interval != TraceInterval.EndMarker) {
             if (current.to() > interval.currentFrom()) {
                 setBlockPos(interval, interval.currentIntersectsAt(current));
             } else {
@@ -239,16 +239,16 @@
     }
 
     void spillCollectActiveAny(RegisterPriority registerPriority) {
-        Interval interval = activeLists.get(RegisterBinding.Any);
-        while (interval != Interval.EndMarker) {
+        TraceInterval interval = activeLists.get(RegisterBinding.Any);
+        while (interval != TraceInterval.EndMarker) {
             setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false);
             interval = interval.next;
         }
     }
 
-    void spillCollectInactiveAny(Interval current) {
-        Interval interval = inactiveLists.get(RegisterBinding.Any);
-        while (interval != Interval.EndMarker) {
+    void spillCollectInactiveAny(TraceInterval current) {
+        TraceInterval interval = inactiveLists.get(RegisterBinding.Any);
+        while (interval != TraceInterval.EndMarker) {
             if (interval.currentIntersects(current)) {
                 setUsePos(interval, Math.min(interval.nextUsage(RegisterPriority.LiveAtLoopEnd, currentPosition), interval.to()), false);
             }
@@ -256,7 +256,7 @@
         }
     }
 
-    void insertMove(int operandId, Interval srcIt, Interval dstIt) {
+    void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) {
         // output all moves here. When source and target are equal, the move is
         // optimized away later in assignRegNums
 
@@ -315,7 +315,7 @@
         return optimalSplitPos;
     }
 
-    int findOptimalSplitPos(Interval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
+    int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
         int optimalSplitPos = -1;
         if (minSplitPos == maxSplitPos) {
             // trivial case, no optimization of split position possible
@@ -424,7 +424,7 @@
     // maxSplitPos in two parts:
     // 1) the left part has already a location assigned
     // 2) the right part is sorted into to the unhandled-list
-    void splitBeforeUsage(Interval interval, int minSplitPos, int maxSplitPos) {
+    void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
 
         try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
 
@@ -464,7 +464,7 @@
             assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
             assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
 
-            Interval splitPart = interval.split(optimalSplitPos, allocator);
+            TraceInterval splitPart = interval.split(optimalSplitPos, allocator);
 
             splitPart.setInsertMoveWhenActivated(moveNecessary);
 
@@ -483,7 +483,7 @@
     // 1) the left part has already a location assigned
     // 2) the right part is always on the stack and therefore ignored in further processing
 
-    void splitForSpilling(Interval interval) {
+    void splitForSpilling(TraceInterval interval) {
         // calculate allowed range of splitting position
         int maxSplitPos = currentPosition;
         int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
@@ -520,7 +520,7 @@
                     // Also kick parent intervals out of register to memory when they have no use
                     // position. This avoids short interval in register surrounded by intervals in
                     // memory . avoid useless moves from memory to register and back
-                    Interval parent = interval;
+                    TraceInterval parent = interval;
                     while (parent != null && parent.isSplitChild()) {
                         parent = parent.getSplitChildBeforeOpId(parent.from());
 
@@ -558,7 +558,7 @@
                     assert allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
                     assert !allocator.isBlockBegin(optimalSplitPos) || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
 
-                    Interval spilledPart = interval.split(optimalSplitPos, allocator);
+                    TraceInterval spilledPart = interval.split(optimalSplitPos, allocator);
                     allocator.assignSpillSlot(spilledPart);
                     handleSpillSlot(spilledPart);
                     changeSpillState(spilledPart, optimalSplitPos);
@@ -584,7 +584,7 @@
     }
 
     // called during register allocation
-    private void changeSpillState(Interval interval, int spillPos) {
+    private void changeSpillState(TraceInterval interval, int spillPos) {
         switch (interval.spillState()) {
             case NoSpillStore: {
                 int defLoopDepth = allocator.blockForId(interval.spillDefinitionPos()).getLoopDepth();
@@ -639,24 +639,24 @@
     /**
      * This is called for every interval that is assigned to a stack slot.
      */
-    protected static void handleSpillSlot(Interval interval) {
+    protected static void handleSpillSlot(TraceInterval interval) {
         assert interval.location() != null && (interval.canMaterialize() || isStackSlotValue(interval.location())) : "interval not assigned to a stack slot " + interval;
         // Do nothing. Stack slots are not processed in this implementation.
     }
 
-    void splitStackInterval(Interval interval) {
+    void splitStackInterval(TraceInterval interval) {
         int minSplitPos = currentPosition + 1;
         int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to());
 
         splitBeforeUsage(interval, minSplitPos, maxSplitPos);
     }
 
-    void splitWhenPartialRegisterAvailable(Interval interval, int registerAvailableUntil) {
+    void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
         int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
         splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
     }
 
-    void splitAndSpillInterval(Interval interval) {
+    void splitAndSpillInterval(TraceInterval interval) {
         assert interval.state == State.Active || interval.state == State.Inactive : "other states not allowed";
 
         int currentPos = currentPosition;
@@ -682,7 +682,7 @@
         }
     }
 
-    boolean allocFreeRegister(Interval interval) {
+    boolean allocFreeRegister(TraceInterval interval) {
         try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) {
 
             initUseLists(true);
@@ -691,7 +691,7 @@
             freeCollectInactiveFixed(interval);
             freeCollectInactiveAny(interval);
             // freeCollectUnhandled(fixedKind, cur);
-            assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
+            assert unhandledLists.get(RegisterBinding.Fixed) == TraceInterval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
 
             // usePos contains the start of the next interval that has this register assigned
             // (either as a fixed register or a normal allocated register in the past)
@@ -708,7 +708,7 @@
             }
 
             Register hint = null;
-            Interval locationHint = interval.locationHint(true);
+            TraceInterval locationHint = interval.locationHint(true);
             if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
                 hint = asRegister(locationHint.location());
                 if (Debug.isLogEnabled()) {
@@ -772,14 +772,14 @@
         assert reg != null : "no register assigned";
 
         for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
-            Interval interval = spillIntervals[reg.number].get(i);
+            TraceInterval interval = spillIntervals[reg.number].get(i);
             removeFromList(interval);
             splitAndSpillInterval(interval);
         }
     }
 
     // Split an Interval and spill it to memory so that cur can be placed in a register
-    void allocLockedRegister(Interval interval) {
+    void allocLockedRegister(TraceInterval interval) {
         try (Indent indent = Debug.logAndIndent("alloc locked register: need to split and spill to get register for %s", interval)) {
 
             // the register must be free at least until this position
@@ -802,7 +802,7 @@
                 initUseLists(false);
                 spillExcludeActiveFixed();
                 // spillBlockUnhandledFixed(cur);
-                assert unhandledLists.get(RegisterBinding.Fixed) == Interval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
+                assert unhandledLists.get(RegisterBinding.Fixed) == TraceInterval.EndMarker : "must not have unhandled fixed intervals because all fixed intervals have a use at position 0";
                 spillBlockInactiveFixed(interval);
                 spillCollectActiveAny(registerPriority);
                 spillCollectInactiveAny(interval);
@@ -893,7 +893,7 @@
         }
     }
 
-    boolean noAllocationPossible(Interval interval) {
+    boolean noAllocationPossible(TraceInterval interval) {
         if (allocator.callKillsRegisters()) {
             // fast calculation of intervals that can never get a register because the
             // the next instruction is a call that blocks all registers
@@ -918,14 +918,14 @@
         return false;
     }
 
-    void initVarsForAlloc(Interval interval) {
+    void initVarsForAlloc(TraceInterval interval) {
         AllocatableRegisters allocatableRegisters = allocator.getRegisterAllocationConfig().getAllocatableRegisters(interval.kind().getPlatformKind());
         availableRegs = allocatableRegisters.allocatableRegisters;
         minReg = allocatableRegisters.minRegisterNumber;
         maxReg = allocatableRegisters.maxRegisterNumber;
     }
 
-    static boolean isMove(LIRInstruction op, Interval from, Interval to) {
+    static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) {
         if (op instanceof ValueMoveOp) {
             ValueMoveOp move = (ValueMoveOp) op;
             if (isVariable(move.getInput()) && isVariable(move.getResult())) {
@@ -937,13 +937,13 @@
 
     // optimization (especially for phi functions of nested loops):
     // assign same spill slot to non-intersecting intervals
-    void combineSpilledIntervals(Interval interval) {
+    void combineSpilledIntervals(TraceInterval interval) {
         if (interval.isSplitChild()) {
             // optimization is only suitable for split parents
             return;
         }
 
-        Interval registerHint = interval.locationHint(false);
+        TraceInterval registerHint = interval.locationHint(false);
         if (registerHint == null) {
             // cur is not the target of a move : otherwise registerHint would be set
             return;
@@ -968,8 +968,8 @@
             return;
         }
 
-        Interval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE, allocator);
-        Interval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF, allocator);
+        TraceInterval beginHint = registerHint.getSplitChildAtOpId(beginPos, LIRInstruction.OperandMode.USE, allocator);
+        TraceInterval endHint = registerHint.getSplitChildAtOpId(endPos, LIRInstruction.OperandMode.DEF, allocator);
         if (beginHint == endHint || beginHint.to() != beginPos || endHint.from() != endPos) {
             // registerHint must be split : otherwise the re-writing of use positions does not work
             return;
@@ -996,7 +996,7 @@
 
     // allocate a physical register or memory location to an interval
     @Override
-    protected boolean activateCurrent(Interval interval) {
+    protected boolean activateCurrent(TraceInterval interval) {
         boolean result = true;
 
         try (Indent indent = Debug.logAndIndent("activating interval %s,  splitParent: %d", interval, interval.splitParent().operandNumber)) {

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java	Tue Sep 01 12:03:14 2015 +0200
@@ -44,10 +44,10 @@
 
     TraceLinearScan allocator;
     List<AbstractBlockBase<?>> workList; // all blocks that must be processed
-    ArrayMap<Interval[]> savedStates; // saved information of previous check
+    ArrayMap<TraceInterval[]> savedStates; // saved information of previous check
 
     // simplified access to methods of LinearScan
-    Interval intervalAt(Value operand) {
+    TraceInterval intervalAt(Value operand) {
         return allocator.intervalFor(operand);
     }
 
@@ -57,11 +57,11 @@
     }
 
     // accessors
-    Interval[] stateForBlock(AbstractBlockBase<?> block) {
+    TraceInterval[] stateForBlock(AbstractBlockBase<?> block) {
         return savedStates.get(block.getId());
     }
 
-    void setStateForBlock(AbstractBlockBase<?> block, Interval[] savedState) {
+    void setStateForBlock(AbstractBlockBase<?> block, TraceInterval[] savedState) {
         savedStates.put(block.getId(), savedState);
     }
 
@@ -81,7 +81,7 @@
     void verify(AbstractBlockBase<?> start) {
         try (Scope s = Debug.scope("RegisterVerifier")) {
             // setup input registers (method arguments) for first block
-            Interval[] inputState = new Interval[stateSize()];
+            TraceInterval[] inputState = new TraceInterval[stateSize()];
             setStateForBlock(start, inputState);
             addToWorkList(start);
 
@@ -98,7 +98,7 @@
     private void processBlock(AbstractBlockBase<?> block) {
         try (Indent indent = Debug.logAndIndent("processBlock B%d", block.getId())) {
             // must copy state because it is modified
-            Interval[] inputState = copy(stateForBlock(block));
+            TraceInterval[] inputState = copy(stateForBlock(block));
 
             try (Indent indent2 = Debug.logAndIndent("Input-State of intervals:")) {
                 printState(inputState);
@@ -118,7 +118,7 @@
         }
     }
 
-    protected void printState(Interval[] inputState) {
+    protected void printState(TraceInterval[] inputState) {
         for (int i = 0; i < stateSize(); i++) {
             Register reg = allocator.getRegisters()[i];
             assert reg.number == i;
@@ -130,8 +130,8 @@
         }
     }
 
-    private void processSuccessor(AbstractBlockBase<?> block, Interval[] inputState) {
-        Interval[] savedState = stateForBlock(block);
+    private void processSuccessor(AbstractBlockBase<?> block, TraceInterval[] inputState) {
+        TraceInterval[] savedState = stateForBlock(block);
 
         if (savedState != null) {
             // this block was already processed before.
@@ -172,11 +172,11 @@
         }
     }
 
-    static Interval[] copy(Interval[] inputState) {
+    static TraceInterval[] copy(TraceInterval[] inputState) {
         return inputState.clone();
     }
 
-    static void statePut(Interval[] inputState, Value location, Interval interval) {
+    static void statePut(TraceInterval[] inputState, Value location, TraceInterval interval) {
         if (location != null && isRegister(location)) {
             Register reg = asRegister(location);
             int regNum = reg.number;
@@ -190,7 +190,7 @@
         }
     }
 
-    static boolean checkState(AbstractBlockBase<?> block, LIRInstruction op, Interval[] inputState, Value operand, Value reg, Interval interval) {
+    static boolean checkState(AbstractBlockBase<?> block, LIRInstruction op, TraceInterval[] inputState, Value operand, Value reg, TraceInterval interval) {
         if (reg != null && isRegister(reg)) {
             if (inputState[asRegister(reg).number] != interval) {
                 throw new JVMCIError(
@@ -201,7 +201,7 @@
         return true;
     }
 
-    void processOperations(AbstractBlockBase<?> block, final Interval[] inputState) {
+    void processOperations(AbstractBlockBase<?> block, final TraceInterval[] inputState) {
         List<LIRInstruction> ops = allocator.getLIR().getLIRforBlock(block);
         InstructionValueConsumer useConsumer = new InstructionValueConsumer() {
 
@@ -209,7 +209,7 @@
             public void visitValue(LIRInstruction op, Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
                 // we skip spill moves inserted by the spill position optimization
                 if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand) && op.id() != TraceLinearScan.DOMINATOR_SPILL_MOVE_ID) {
-                    Interval interval = intervalAt(operand);
+                    TraceInterval interval = intervalAt(operand);
                     if (op.id() != -1) {
                         interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
                     }
@@ -221,7 +221,7 @@
 
         InstructionValueConsumer defConsumer = (op, operand, mode, flags) -> {
             if (TraceLinearScan.isVariableOrRegister(operand) && allocator.isProcessed(operand)) {
-                Interval interval = intervalAt(operand);
+                TraceInterval interval = intervalAt(operand);
                 if (op.id() != -1) {
                     interval = interval.getSplitChildAtOpId(op.id(), mode, allocator);
                 }

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceGlobalMoveResolver.java	Tue Sep 01 12:03:14 2015 +0200
@@ -208,7 +208,7 @@
     }
 
     /**
-     * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is
+     * Checks if the {@linkplain TraceInterval#location() location} of {@code to} is not blocked or is
      * only blocked by {@code from}.
      */
     private boolean safeToProcessMove(Value fromLocation, Value toLocation) {
@@ -275,8 +275,8 @@
     }
 
     /**
-     * @param fromOpr {@link Interval#operand operand} of the {@code from} interval
-     * @param toOpr {@link Interval#operand operand} of the {@code to} interval
+     * @param fromOpr {@link TraceInterval#operand operand} of the {@code from} interval
+     * @param toOpr {@link TraceInterval#operand operand} of the {@code to} interval
      */
     private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) {
         if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) {

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java	Tue Sep 01 12:03:14 2015 +0200
@@ -0,0 +1,1304 @@
+/*
+ * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.lir.alloc.trace;
+
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+import static com.oracle.graal.lir.LIRValueUtil.*;
+import static jdk.internal.jvmci.code.ValueUtil.*;
+
+import java.util.*;
+
+import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.common.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.compiler.common.util.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.*;
+
+/**
+ * Represents an interval in the {@linkplain TraceLinearScan linear scan register allocator}.
+ */
+final class TraceInterval {
+
+    /**
+     * A pair of intervals.
+     */
+    static final class Pair {
+
+        public final TraceInterval first;
+        public final TraceInterval second;
+
+        public Pair(TraceInterval first, TraceInterval second) {
+            this.first = first;
+            this.second = second;
+        }
+    }
+
+    /**
+     * A set of interval lists, one per {@linkplain RegisterBinding binding} type.
+     */
+    static final class RegisterBindingLists {
+
+        /**
+         * List of intervals whose binding is currently {@link RegisterBinding#Fixed}.
+         */
+        public TraceInterval fixed;
+
+        /**
+         * List of intervals whose binding is currently {@link RegisterBinding#Any}.
+         */
+        public TraceInterval any;
+
+        /**
+         * List of intervals whose binding is currently {@link RegisterBinding#Stack}.
+         */
+        public TraceInterval stack;
+
+        public RegisterBindingLists(TraceInterval fixed, TraceInterval any, TraceInterval stack) {
+            this.fixed = fixed;
+            this.any = any;
+            this.stack = stack;
+        }
+
+        /**
+         * Gets the list for a specified binding.
+         *
+         * @param binding specifies the list to be returned
+         * @return the list of intervals whose binding is {@code binding}
+         */
+        public TraceInterval get(RegisterBinding binding) {
+            switch (binding) {
+                case Any:
+                    return any;
+                case Fixed:
+                    return fixed;
+                case Stack:
+                    return stack;
+            }
+            throw JVMCIError.shouldNotReachHere();
+        }
+
+        /**
+         * Sets the list for a specified binding.
+         *
+         * @param binding specifies the list to be replaced
+         * @param list a list of intervals whose binding is {@code binding}
+         */
+        public void set(RegisterBinding binding, TraceInterval list) {
+            assert list != null;
+            switch (binding) {
+                case Any:
+                    any = list;
+                    break;
+                case Fixed:
+                    fixed = list;
+                    break;
+                case Stack:
+                    stack = list;
+                    break;
+            }
+        }
+
+        /**
+         * Adds an interval to a list sorted by {@linkplain TraceInterval#currentFrom() current
+         * from} positions.
+         *
+         * @param binding specifies the list to be updated
+         * @param interval the interval to add
+         */
+        public void addToListSortedByCurrentFromPositions(RegisterBinding binding, TraceInterval interval) {
+            TraceInterval list = get(binding);
+            TraceInterval prev = null;
+            TraceInterval cur = list;
+            while (cur.currentFrom() < interval.currentFrom()) {
+                prev = cur;
+                cur = cur.next;
+            }
+            TraceInterval result = list;
+            if (prev == null) {
+                // add to head of list
+                result = interval;
+            } else {
+                // add before 'cur'
+                prev.next = interval;
+            }
+            interval.next = cur;
+            set(binding, result);
+        }
+
+        /**
+         * Adds an interval to a list sorted by {@linkplain TraceInterval#from() start} positions
+         * and {@linkplain TraceInterval#firstUsage(RegisterPriority) first usage} positions.
+         *
+         * @param binding specifies the list to be updated
+         * @param interval the interval to add
+         */
+        public void addToListSortedByStartAndUsePositions(RegisterBinding binding, TraceInterval interval) {
+            TraceInterval list = get(binding);
+            TraceInterval prev = null;
+            TraceInterval cur = list;
+            while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) {
+                prev = cur;
+                cur = cur.next;
+            }
+            if (prev == null) {
+                list = interval;
+            } else {
+                prev.next = interval;
+            }
+            interval.next = cur;
+            set(binding, list);
+        }
+
+        /**
+         * Removes an interval from a list.
+         *
+         * @param binding specifies the list to be updated
+         * @param i the interval to remove
+         */
+        public void remove(RegisterBinding binding, TraceInterval i) {
+            TraceInterval list = get(binding);
+            TraceInterval prev = null;
+            TraceInterval cur = list;
+            while (cur != i) {
+                assert cur != null && cur != TraceInterval.EndMarker : "interval has not been found in list: " + i;
+                prev = cur;
+                cur = cur.next;
+            }
+            if (prev == null) {
+                set(binding, cur.next);
+            } else {
+                prev.next = cur.next;
+            }
+        }
+    }
+
+    /**
+     * Constants denoting the register usage priority for an interval. The constants are declared in
+     * increasing order of priority are are used to optimize spilling when multiple overlapping
+     * intervals compete for limited registers.
+     */
+    public enum RegisterPriority {
+        /**
+         * No special reason for an interval to be allocated a register.
+         */
+        None,
+
+        /**
+         * Priority level for intervals live at the end of a loop.
+         */
+        LiveAtLoopEnd,
+
+        /**
+         * Priority level for intervals that should be allocated to a register.
+         */
+        ShouldHaveRegister,
+
+        /**
+         * Priority level for intervals that must be allocated to a register.
+         */
+        MustHaveRegister;
+
+        public static final RegisterPriority[] VALUES = values();
+
+        /**
+         * Determines if this priority is higher than or equal to a given priority.
+         */
+        public boolean greaterEqual(RegisterPriority other) {
+            return ordinal() >= other.ordinal();
+        }
+
+        /**
+         * Determines if this priority is lower than a given priority.
+         */
+        public boolean lessThan(RegisterPriority other) {
+            return ordinal() < other.ordinal();
+        }
+    }
+
+    /**
+     * Constants denoting whether an interval is bound to a specific register. This models platform
+     * dependencies on register usage for certain instructions.
+     */
+    enum RegisterBinding {
+        /**
+         * Interval is bound to a specific register as required by the platform.
+         */
+        Fixed,
+
+        /**
+         * Interval has no specific register requirements.
+         */
+        Any,
+
+        /**
+         * Interval is bound to a stack slot.
+         */
+        Stack;
+
+        public static final RegisterBinding[] VALUES = values();
+    }
+
+    /**
+     * Constants denoting the linear-scan states an interval may be in with respect to the
+     * {@linkplain TraceInterval#from() start} {@code position} of the interval being processed.
+     */
+    enum State {
+        /**
+         * An interval that starts after {@code position}.
+         */
+        Unhandled,
+
+        /**
+         * An interval that {@linkplain TraceInterval#covers covers} {@code position} and has an
+         * assigned register.
+         */
+        Active,
+
+        /**
+         * An interval that starts before and ends after {@code position} but does not
+         * {@linkplain TraceInterval#covers cover} it due to a lifetime hole.
+         */
+        Inactive,
+
+        /**
+         * An interval that ends before {@code position} or is spilled to memory.
+         */
+        Handled;
+    }
+
+    /**
+     * Constants used in optimization of spilling of an interval.
+     */
+    public enum SpillState {
+        /**
+         * Starting state of calculation: no definition found yet.
+         */
+        NoDefinitionFound,
+
+        /**
+         * One definition has already been found. Two consecutive definitions are treated as one
+         * (e.g. a consecutive move and add because of two-operand LIR form). The position of this
+         * definition is given by {@link TraceInterval#spillDefinitionPos()}.
+         */
+        NoSpillStore,
+
+        /**
+         * One spill move has already been inserted.
+         */
+        OneSpillStore,
+
+        /**
+         * The interval is spilled multiple times or is spilled in a loop. Place the store somewhere
+         * on the dominator path between the definition and the usages.
+         */
+        SpillInDominator,
+
+        /**
+         * The interval should be stored immediately after its definition to prevent multiple
+         * redundant stores.
+         */
+        StoreAtDefinition,
+
+        /**
+         * The interval starts in memory (e.g. method parameter), so a store is never necessary.
+         */
+        StartInMemory,
+
+        /**
+         * The interval has more than one definition (e.g. resulting from phi moves), so stores to
+         * memory are not optimized.
+         */
+        NoOptimization
+    }
+
+    /**
+     * List of use positions. Each entry in the list records the use position and register priority
+     * associated with the use position. The entries in the list are in descending order of use
+     * position.
+     *
+     */
+    public static final class UsePosList {
+
+        private IntList list;
+
+        /**
+         * Creates a use list.
+         *
+         * @param initialCapacity the initial capacity of the list in terms of entries
+         */
+        public UsePosList(int initialCapacity) {
+            list = new IntList(initialCapacity * 2);
+        }
+
+        private UsePosList(IntList list) {
+            this.list = list;
+        }
+
+        /**
+         * Splits this list around a given position. All entries in this list with a use position
+         * greater or equal than {@code splitPos} are removed from this list and added to the
+         * returned list.
+         *
+         * @param splitPos the position for the split
+         * @return a use position list containing all entries removed from this list that have a use
+         *         position greater or equal than {@code splitPos}
+         */
+        public UsePosList splitAt(int splitPos) {
+            int i = size() - 1;
+            int len = 0;
+            while (i >= 0 && usePos(i) < splitPos) {
+                --i;
+                len += 2;
+            }
+            int listSplitIndex = (i + 1) * 2;
+            IntList childList = list;
+            list = IntList.copy(this.list, listSplitIndex, len);
+            childList.setSize(listSplitIndex);
+            UsePosList child = new UsePosList(childList);
+            return child;
+        }
+
+        /**
+         * Gets the use position at a specified index in this list.
+         *
+         * @param index the index of the entry for which the use position is returned
+         * @return the use position of entry {@code index} in this list
+         */
+        public int usePos(int index) {
+            return list.get(index << 1);
+        }
+
+        /**
+         * Gets the register priority for the use position at a specified index in this list.
+         *
+         * @param index the index of the entry for which the register priority is returned
+         * @return the register priority of entry {@code index} in this list
+         */
+        public RegisterPriority registerPriority(int index) {
+            return RegisterPriority.VALUES[list.get((index << 1) + 1)];
+        }
+
+        public void add(int usePos, RegisterPriority registerPriority) {
+            assert list.size() == 0 || usePos(size() - 1) > usePos;
+            list.add(usePos);
+            list.add(registerPriority.ordinal());
+        }
+
+        public int size() {
+            return list.size() >> 1;
+        }
+
+        public void removeLowestUsePos() {
+            list.setSize(list.size() - 2);
+        }
+
+        public void setRegisterPriority(int index, RegisterPriority registerPriority) {
+            list.set((index << 1) + 1, registerPriority.ordinal());
+        }
+
+        @Override
+        public String toString() {
+            StringBuilder buf = new StringBuilder("[");
+            for (int i = size() - 1; i >= 0; --i) {
+                if (buf.length() != 1) {
+                    buf.append(", ");
+                }
+                RegisterPriority prio = registerPriority(i);
+                buf.append(usePos(i)).append(" -> ").append(prio.ordinal()).append(':').append(prio);
+            }
+            return buf.append("]").toString();
+        }
+    }
+
+    /**
+     * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval
+     * prior to register allocation.
+     */
+    public final AllocatableValue operand;
+
+    /**
+     * The operand number for this interval's {@linkplain #operand operand}.
+     */
+    public final int operandNumber;
+
+    /**
+     * The {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to this
+     * interval. In case of a spilled interval which is re-materialized this is
+     * {@link Value#ILLEGAL}.
+     */
+    private AllocatableValue location;
+
+    /**
+     * The stack slot to which all splits of this interval are spilled if necessary.
+     */
+    private StackSlotValue spillSlot;
+
+    /**
+     * The kind of this interval.
+     */
+    private LIRKind kind;
+
+    /**
+     * The head of the list of ranges describing this interval. This list is sorted by
+     * {@linkplain LIRInstruction#id instruction ids}.
+     */
+    private Range first;
+
+    /**
+     * List of (use-positions, register-priorities) pairs, sorted by use-positions.
+     */
+    private UsePosList usePosList;
+
+    /**
+     * Iterator used to traverse the ranges of an interval.
+     */
+    private Range current;
+
+    /**
+     * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.
+     */
+    TraceInterval next;
+
+    /**
+     * The linear-scan state of this interval.
+     */
+    State state;
+
+    private int cachedTo; // cached value: to of last range (-1: not cached)
+
+    /**
+     * The interval from which this one is derived. If this is a {@linkplain #isSplitParent() split
+     * parent}, it points to itself.
+     */
+    private TraceInterval splitParent;
+
+    /**
+     * List of all intervals that are split off from this interval. This is only used if this is a
+     * {@linkplain #isSplitParent() split parent}.
+     */
+    private List<TraceInterval> splitChildren = Collections.emptyList();
+
+    /**
+     * Current split child that has been active or inactive last (always stored in split parents).
+     */
+    private TraceInterval currentSplitChild;
+
+    /**
+     * Specifies if move is inserted between currentSplitChild and this interval when interval gets
+     * active the first time.
+     */
+    private boolean insertMoveWhenActivated;
+
+    /**
+     * For spill move optimization.
+     */
+    private SpillState spillState;
+
+    /**
+     * Position where this interval is defined (if defined only once).
+     */
+    private int spillDefinitionPos;
+
+    /**
+     * This interval should be assigned the same location as the hint interval.
+     */
+    private TraceInterval locationHint;
+
+    /**
+     * The value with which a spilled child interval can be re-materialized. Currently this must be
+     * a Constant.
+     */
+    private JavaConstant materializedValue;
+
+    /**
+     * The number of times {@link #addMaterializationValue(JavaConstant)} is called.
+     */
+    private int numMaterializationValuesAdded;
+
+    void assignLocation(AllocatableValue newLocation) {
+        if (isRegister(newLocation)) {
+            assert this.location == null : "cannot re-assign location for " + this;
+            if (newLocation.getLIRKind().equals(LIRKind.Illegal) && !kind.equals(LIRKind.Illegal)) {
+                this.location = asRegister(newLocation).asValue(kind);
+                return;
+            }
+        } else if (isIllegal(newLocation)) {
+            assert canMaterialize();
+        } else {
+            assert this.location == null || isRegister(this.location) || (isVirtualStackSlot(this.location) && isStackSlot(newLocation)) : "cannot re-assign location for " + this;
+            assert isStackSlotValue(newLocation);
+            assert !newLocation.getLIRKind().equals(LIRKind.Illegal);
+            assert newLocation.getLIRKind().equals(this.kind);
+        }
+        this.location = newLocation;
+    }
+
+    /**
+     * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to
+     * this interval.
+     */
+    public AllocatableValue location() {
+        return location;
+    }
+
+    public LIRKind kind() {
+        assert !isRegister(operand) : "cannot access type for fixed interval";
+        return kind;
+    }
+
+    public void setKind(LIRKind kind) {
+        assert isRegister(operand) || this.kind().equals(LIRKind.Illegal) || this.kind().equals(kind) : "overwriting existing type";
+        this.kind = kind;
+    }
+
+    public Range first() {
+        return first;
+    }
+
+    public int from() {
+        return first.from;
+    }
+
+    int to() {
+        if (cachedTo == -1) {
+            cachedTo = calcTo();
+        }
+        assert cachedTo == calcTo() : "invalid cached value";
+        return cachedTo;
+    }
+
+    int numUsePositions() {
+        return usePosList.size();
+    }
+
+    public void setLocationHint(TraceInterval interval) {
+        locationHint = interval;
+    }
+
+    public boolean isSplitParent() {
+        return splitParent == this;
+    }
+
+    boolean isSplitChild() {
+        return splitParent != this;
+    }
+
+    /**
+     * Gets the split parent for this interval.
+     */
+    public TraceInterval splitParent() {
+        assert splitParent.isSplitParent() : "not a split parent: " + this;
+        return splitParent;
+    }
+
+    /**
+     * Gets the canonical spill slot for this interval.
+     */
+    public StackSlotValue spillSlot() {
+        return splitParent().spillSlot;
+    }
+
+    public void setSpillSlot(StackSlotValue slot) {
+        assert splitParent().spillSlot == null || (isVirtualStackSlot(splitParent().spillSlot) && isStackSlot(slot)) : "connot overwrite existing spill slot";
+        splitParent().spillSlot = slot;
+    }
+
+    TraceInterval currentSplitChild() {
+        return splitParent().currentSplitChild;
+    }
+
+    void makeCurrentSplitChild() {
+        splitParent().currentSplitChild = this;
+    }
+
+    boolean insertMoveWhenActivated() {
+        return insertMoveWhenActivated;
+    }
+
+    void setInsertMoveWhenActivated(boolean b) {
+        insertMoveWhenActivated = b;
+    }
+
+    // for spill optimization
+    public SpillState spillState() {
+        return splitParent().spillState;
+    }
+
+    public int spillDefinitionPos() {
+        return splitParent().spillDefinitionPos;
+    }
+
+    public void setSpillState(SpillState state) {
+        assert state.ordinal() >= spillState().ordinal() : "state cannot decrease";
+        splitParent().spillState = state;
+    }
+
+    public void setSpillDefinitionPos(int pos) {
+        assert spillState() == SpillState.SpillInDominator || spillState() == SpillState.NoDefinitionFound || spillDefinitionPos() == -1 : "cannot set the position twice";
+        splitParent().spillDefinitionPos = pos;
+    }
+
+    // returns true if this interval has a shadow copy on the stack that is always correct
+    public boolean alwaysInMemory() {
+        return (splitParent().spillState == SpillState.SpillInDominator || splitParent().spillState == SpillState.StoreAtDefinition || splitParent().spillState == SpillState.StartInMemory) &&
+                        !canMaterialize();
+    }
+
+    void removeFirstUsePos() {
+        usePosList.removeLowestUsePos();
+    }
+
+    // test intersection
+    boolean intersects(TraceInterval i) {
+        return first.intersects(i.first);
+    }
+
+    int intersectsAt(TraceInterval i) {
+        return first.intersectsAt(i.first);
+    }
+
+    // range iteration
+    void rewindRange() {
+        current = first;
+    }
+
+    void nextRange() {
+        assert this != EndMarker : "not allowed on sentinel";
+        current = current.next;
+    }
+
+    int currentFrom() {
+        return current.from;
+    }
+
+    int currentTo() {
+        return current.to;
+    }
+
+    boolean currentAtEnd() {
+        return current == Range.EndMarker;
+    }
+
+    boolean currentIntersects(TraceInterval it) {
+        return current.intersects(it.current);
+    }
+
+    int currentIntersectsAt(TraceInterval it) {
+        return current.intersectsAt(it.current);
+    }
+
+    /**
+     * Sentinel interval to denote the end of an interval list.
+     */
+    static final TraceInterval EndMarker = new TraceInterval(Value.ILLEGAL, -1);
+
+    TraceInterval(AllocatableValue operand, int operandNumber) {
+        assert operand != null;
+        this.operand = operand;
+        this.operandNumber = operandNumber;
+        if (isRegister(operand)) {
+            location = operand;
+        } else {
+            assert isIllegal(operand) || isVariable(operand);
+        }
+        this.kind = LIRKind.Illegal;
+        this.first = Range.EndMarker;
+        this.usePosList = new UsePosList(4);
+        this.current = Range.EndMarker;
+        this.next = EndMarker;
+        this.cachedTo = -1;
+        this.spillState = SpillState.NoDefinitionFound;
+        this.spillDefinitionPos = -1;
+        splitParent = this;
+        currentSplitChild = this;
+    }
+
+    /**
+     * Sets the value which is used for re-materialization.
+     */
+    public void addMaterializationValue(JavaConstant value) {
+        if (numMaterializationValuesAdded == 0) {
+            materializedValue = value;
+        } else {
+            // Interval is defined on multiple places -> no materialization is possible.
+            materializedValue = null;
+        }
+        numMaterializationValuesAdded++;
+    }
+
+    /**
+     * Returns true if this interval can be re-materialized when spilled. This means that no
+     * spill-moves are needed. Instead of restore-moves the {@link #materializedValue} is restored.
+     */
+    public boolean canMaterialize() {
+        return getMaterializedValue() != null;
+    }
+
+    /**
+     * Returns a value which can be moved to a register instead of a restore-move from stack.
+     */
+    public JavaConstant getMaterializedValue() {
+        return splitParent().materializedValue;
+    }
+
+    int calcTo() {
+        assert first != Range.EndMarker : "interval has no range";
+
+        Range r = first;
+        while (r.next != Range.EndMarker) {
+            r = r.next;
+        }
+        return r.to;
+    }
+
+    // consistency check of split-children
+    boolean checkSplitChildren() {
+        if (!splitChildren.isEmpty()) {
+            assert isSplitParent() : "only split parents can have children";
+
+            for (int i = 0; i < splitChildren.size(); i++) {
+                TraceInterval i1 = splitChildren.get(i);
+
+                assert i1.splitParent() == this : "not a split child of this interval";
+                assert i1.kind().equals(kind()) : "must be equal for all split children";
+                assert (i1.spillSlot() == null && spillSlot == null) || i1.spillSlot().equals(spillSlot()) : "must be equal for all split children";
+
+                for (int j = i + 1; j < splitChildren.size(); j++) {
+                    TraceInterval i2 = splitChildren.get(j);
+
+                    assert !i1.operand.equals(i2.operand) : "same register number";
+
+                    if (i1.from() < i2.from()) {
+                        assert i1.to() <= i2.from() && i1.to() < i2.to() : "intervals overlapping";
+                    } else {
+                        assert i2.from() < i1.from() : "intervals start at same opId";
+                        assert i2.to() <= i1.from() && i2.to() < i1.to() : "intervals overlapping";
+                    }
+                }
+            }
+        }
+
+        return true;
+    }
+
+    public TraceInterval locationHint(boolean searchSplitChild) {
+        if (!searchSplitChild) {
+            return locationHint;
+        }
+
+        if (locationHint != null) {
+            assert locationHint.isSplitParent() : "ony split parents are valid hint registers";
+
+            if (locationHint.location != null && isRegister(locationHint.location)) {
+                return locationHint;
+            } else if (!locationHint.splitChildren.isEmpty()) {
+                // search the first split child that has a register assigned
+                int len = locationHint.splitChildren.size();
+                for (int i = 0; i < len; i++) {
+                    TraceInterval interval = locationHint.splitChildren.get(i);
+                    if (interval.location != null && isRegister(interval.location)) {
+                        return interval;
+                    }
+                }
+            }
+        }
+
+        // no hint interval found that has a register assigned
+        return null;
+    }
+
+    TraceInterval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode, TraceLinearScan allocator) {
+        assert isSplitParent() : "can only be called for split parents";
+        assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
+
+        if (splitChildren.isEmpty()) {
+            assert this.covers(opId, mode) : this + " does not cover " + opId;
+            return this;
+        } else {
+            TraceInterval result = null;
+            int len = splitChildren.size();
+
+            // in outputMode, the end of the interval (opId == cur.to()) is not valid
+            int toOffset = (mode == LIRInstruction.OperandMode.DEF ? 0 : 1);
+
+            int i;
+            for (i = 0; i < len; i++) {
+                TraceInterval cur = splitChildren.get(i);
+                if (cur.from() <= opId && opId < cur.to() + toOffset) {
+                    if (i > 0) {
+                        // exchange current split child to start of list (faster access for next
+                        // call)
+                        Util.atPutGrow(splitChildren, i, splitChildren.get(0), null);
+                        Util.atPutGrow(splitChildren, 0, cur, null);
+                    }
+
+                    // interval found
+                    result = cur;
+                    break;
+                }
+            }
+
+            assert checkSplitChild(result, opId, allocator, toOffset, mode);
+            return result;
+        }
+    }
+
+    private boolean checkSplitChild(TraceInterval result, int opId, TraceLinearScan allocator, int toOffset, LIRInstruction.OperandMode mode) {
+        if (result == null) {
+            // this is an error
+            StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
+            if (!splitChildren.isEmpty()) {
+                TraceInterval firstChild = splitChildren.get(0);
+                TraceInterval lastChild = splitChildren.get(splitChildren.size() - 1);
+                msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
+            }
+            throw new JVMCIError("Linear Scan Error: %s", msg);
+        }
+
+        if (!splitChildren.isEmpty()) {
+            for (TraceInterval interval : splitChildren) {
+                if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
+                    TTY.println(String.format("two valid result intervals found for opId %d: %d and %d", opId, result.operandNumber, interval.operandNumber));
+                    TTY.println(result.logString(allocator));
+                    TTY.println(interval.logString(allocator));
+                    throw new BailoutException("two valid result intervals found");
+                }
+            }
+        }
+        assert result.covers(opId, mode) : "opId not covered by interval";
+        return true;
+    }
+
+    // returns the interval that covers the given opId or null if there is none
+    TraceInterval getIntervalCoveringOpId(int opId) {
+        assert opId >= 0 : "invalid opId";
+        assert opId < to() : "can only look into the past";
+
+        if (opId >= from()) {
+            return this;
+        }
+
+        TraceInterval parent = splitParent();
+        TraceInterval result = null;
+
+        assert !parent.splitChildren.isEmpty() : "no split children available";
+        int len = parent.splitChildren.size();
+
+        for (int i = len - 1; i >= 0; i--) {
+            TraceInterval cur = parent.splitChildren.get(i);
+            if (cur.from() <= opId && opId < cur.to()) {
+                assert result == null : "covered by multiple split children " + result + " and " + cur;
+                result = cur;
+            }
+        }
+
+        return result;
+    }
+
+    // returns the last split child that ends before the given opId
+    TraceInterval getSplitChildBeforeOpId(int opId) {
+        assert opId >= 0 : "invalid opId";
+
+        TraceInterval parent = splitParent();
+        TraceInterval result = null;
+
+        assert !parent.splitChildren.isEmpty() : "no split children available";
+        int len = parent.splitChildren.size();
+
+        for (int i = len - 1; i >= 0; i--) {
+            TraceInterval cur = parent.splitChildren.get(i);
+            if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
+                result = cur;
+            }
+        }
+
+        assert result != null : "no split child found";
+        return result;
+    }
+
+    // checks if opId is covered by any split child
+    boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) {
+        assert isSplitParent() : "can only be called for split parents";
+        assert opId >= 0 : "invalid opId (method can not be called for spill moves)";
+
+        if (splitChildren.isEmpty()) {
+            // simple case if interval was not split
+            return covers(opId, mode);
+
+        } else {
+            // extended case: check all split children
+            int len = splitChildren.size();
+            for (int i = 0; i < len; i++) {
+                TraceInterval cur = splitChildren.get(i);
+                if (cur.covers(opId, mode)) {
+                    return true;
+                }
+            }
+            return false;
+        }
+    }
+
+    private RegisterPriority adaptPriority(RegisterPriority priority) {
+        /*
+         * In case of re-materialized values we require that use-operands are registers, because we
+         * don't have the value in a stack location. (Note that ShouldHaveRegister means that the
+         * operand can also be a StackSlot).
+         */
+        if (priority == RegisterPriority.ShouldHaveRegister && canMaterialize()) {
+            return RegisterPriority.MustHaveRegister;
+        }
+        return priority;
+    }
+
+    // Note: use positions are sorted descending . first use has highest index
+    int firstUsage(RegisterPriority minRegisterPriority) {
+        assert isVariable(operand) : "cannot access use positions for fixed intervals";
+
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            RegisterPriority registerPriority = adaptPriority(usePosList.registerPriority(i));
+            if (registerPriority.greaterEqual(minRegisterPriority)) {
+                return usePosList.usePos(i);
+            }
+        }
+        return Integer.MAX_VALUE;
+    }
+
+    int nextUsage(RegisterPriority minRegisterPriority, int from) {
+        assert isVariable(operand) : "cannot access use positions for fixed intervals";
+
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            int usePos = usePosList.usePos(i);
+            if (usePos >= from && adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
+                return usePos;
+            }
+        }
+        return Integer.MAX_VALUE;
+    }
+
+    int nextUsageExact(RegisterPriority exactRegisterPriority, int from) {
+        assert isVariable(operand) : "cannot access use positions for fixed intervals";
+
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            int usePos = usePosList.usePos(i);
+            if (usePos >= from && adaptPriority(usePosList.registerPriority(i)) == exactRegisterPriority) {
+                return usePos;
+            }
+        }
+        return Integer.MAX_VALUE;
+    }
+
+    int previousUsage(RegisterPriority minRegisterPriority, int from) {
+        assert isVariable(operand) : "cannot access use positions for fixed intervals";
+
+        int prev = -1;
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            int usePos = usePosList.usePos(i);
+            if (usePos > from) {
+                return prev;
+            }
+            if (adaptPriority(usePosList.registerPriority(i)).greaterEqual(minRegisterPriority)) {
+                prev = usePos;
+            }
+        }
+        return prev;
+    }
+
+    public void addUsePos(int pos, RegisterPriority registerPriority) {
+        assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
+
+        // do not add use positions for precolored intervals because they are never used
+        if (registerPriority != RegisterPriority.None && isVariable(operand)) {
+            if (DetailedAsserts.getValue()) {
+                for (int i = 0; i < usePosList.size(); i++) {
+                    assert pos <= usePosList.usePos(i) : "already added a use-position with lower position";
+                    if (i > 0) {
+                        assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending";
+                    }
+                }
+            }
+
+            // Note: addUse is called in descending order, so list gets sorted
+            // automatically by just appending new use positions
+            int len = usePosList.size();
+            if (len == 0 || usePosList.usePos(len - 1) > pos) {
+                usePosList.add(pos, registerPriority);
+            } else if (usePosList.registerPriority(len - 1).lessThan(registerPriority)) {
+                assert usePosList.usePos(len - 1) == pos : "list not sorted correctly";
+                usePosList.setRegisterPriority(len - 1, registerPriority);
+            }
+        }
+    }
+
+    public void addRange(int from, int to) {
+        assert from < to : "invalid range";
+        assert first() == Range.EndMarker || to < first().next.from : "not inserting at begin of interval";
+        assert from <= first().to : "not inserting at begin of interval";
+
+        if (first.from <= to) {
+            assert first != Range.EndMarker;
+            // join intersecting ranges
+            first.from = Math.min(from, first().from);
+            first.to = Math.max(to, first().to);
+        } else {
+            // insert new range
+            first = new Range(from, to, first());
+        }
+    }
+
+    TraceInterval newSplitChild(TraceLinearScan allocator) {
+        // allocate new interval
+        TraceInterval parent = splitParent();
+        TraceInterval result = allocator.createDerivedInterval(parent);
+        result.setKind(kind());
+
+        result.splitParent = parent;
+        result.setLocationHint(parent);
+
+        // insert new interval in children-list of parent
+        if (parent.splitChildren.isEmpty()) {
+            assert isSplitParent() : "list must be initialized at first split";
+
+            // Create new non-shared list
+            parent.splitChildren = new ArrayList<>(4);
+            parent.splitChildren.add(this);
+        }
+        parent.splitChildren.add(result);
+
+        return result;
+    }
+
+    /**
+     * Splits this interval at a specified position and returns the remainder as a new <i>child</i>
+     * interval of this interval's {@linkplain #splitParent() parent} interval.
+     * <p>
+     * When an interval is split, a bi-directional link is established between the original
+     * <i>parent</i> interval and the <i>children</i> intervals that are split off this interval.
+     * When a split child is split again, the new created interval is a direct child of the original
+     * parent. That is, there is no tree of split children stored, just a flat list. All split
+     * children are spilled to the same {@linkplain #spillSlot spill slot}.
+     *
+     * @param splitPos the position at which to split this interval
+     * @param allocator the register allocator context
+     * @return the child interval split off from this interval
+     */
+    TraceInterval split(int splitPos, TraceLinearScan allocator) {
+        assert isVariable(operand) : "cannot split fixed intervals";
+
+        // allocate new interval
+        TraceInterval result = newSplitChild(allocator);
+
+        // split the ranges
+        Range prev = null;
+        Range cur = first;
+        while (cur != Range.EndMarker && cur.to <= splitPos) {
+            prev = cur;
+            cur = cur.next;
+        }
+        assert cur != Range.EndMarker : "split interval after end of last range";
+
+        if (cur.from < splitPos) {
+            result.first = new Range(splitPos, cur.to, cur.next);
+            cur.to = splitPos;
+            cur.next = Range.EndMarker;
+
+        } else {
+            assert prev != null : "split before start of first range";
+            result.first = cur;
+            prev.next = Range.EndMarker;
+        }
+        result.current = result.first;
+        cachedTo = -1; // clear cached value
+
+        // split list of use positions
+        result.usePosList = usePosList.splitAt(splitPos);
+
+        if (DetailedAsserts.getValue()) {
+            for (int i = 0; i < usePosList.size(); i++) {
+                assert usePosList.usePos(i) < splitPos;
+            }
+            for (int i = 0; i < result.usePosList.size(); i++) {
+                assert result.usePosList.usePos(i) >= splitPos;
+            }
+        }
+        return result;
+    }
+
+    /**
+     * Splits this interval at a specified position and returns the head as a new interval (this
+     * interval is the tail).
+     *
+     * Currently, only the first range can be split, and the new interval must not have split
+     * positions
+     */
+    TraceInterval splitFromStart(int splitPos, TraceLinearScan allocator) {
+        assert isVariable(operand) : "cannot split fixed intervals";
+        assert splitPos > from() && splitPos < to() : "can only split inside interval";
+        assert splitPos > first.from && splitPos <= first.to : "can only split inside first range";
+        assert firstUsage(RegisterPriority.None) > splitPos : "can not split when use positions are present";
+
+        // allocate new interval
+        TraceInterval result = newSplitChild(allocator);
+
+        // the new interval has only one range (checked by assertion above,
+        // so the splitting of the ranges is very simple
+        result.addRange(first.from, splitPos);
+
+        if (splitPos == first.to) {
+            assert first.next != Range.EndMarker : "must not be at end";
+            first = first.next;
+        } else {
+            first.from = splitPos;
+        }
+
+        return result;
+    }
+
+    // returns true if the opId is inside the interval
+    boolean covers(int opId, LIRInstruction.OperandMode mode) {
+        Range cur = first;
+
+        while (cur != Range.EndMarker && cur.to < opId) {
+            cur = cur.next;
+        }
+        if (cur != Range.EndMarker) {
+            assert cur.to != cur.next.from : "ranges not separated";
+
+            if (mode == LIRInstruction.OperandMode.DEF) {
+                return cur.from <= opId && opId < cur.to;
+            } else {
+                return cur.from <= opId && opId <= cur.to;
+            }
+        }
+        return false;
+    }
+
+    // returns true if the interval has any hole between holeFrom and holeTo
+    // (even if the hole has only the length 1)
+    boolean hasHoleBetween(int holeFrom, int holeTo) {
+        assert holeFrom < holeTo : "check";
+        assert from() <= holeFrom && holeTo <= to() : "index out of interval";
+
+        Range cur = first;
+        while (cur != Range.EndMarker) {
+            assert cur.to < cur.next.from : "no space between ranges";
+
+            // hole-range starts before this range . hole
+            if (holeFrom < cur.from) {
+                return true;
+
+                // hole-range completely inside this range . no hole
+            } else {
+                if (holeTo <= cur.to) {
+                    return false;
+
+                    // overlapping of hole-range with this range . hole
+                } else {
+                    if (holeFrom <= cur.to) {
+                        return true;
+                    }
+                }
+            }
+
+            cur = cur.next;
+        }
+
+        return false;
+    }
+
+    @Override
+    public String toString() {
+        String from = "?";
+        String to = "?";
+        if (first != null && first != Range.EndMarker) {
+            from = String.valueOf(from());
+            // to() may cache a computed value, modifying the current object, which is a bad idea
+            // for a printing function. Compute it directly instead.
+            to = String.valueOf(calcTo());
+        }
+        String locationString = this.location == null ? "" : "@" + this.location;
+        return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
+    }
+
+    /**
+     * Gets the use position information for this interval.
+     */
+    public UsePosList usePosList() {
+        return usePosList;
+    }
+
+    /**
+     * Gets a single line string for logging the details of this interval to a log stream.
+     *
+     * @param allocator the register allocator context
+     */
+    public String logString(TraceLinearScan allocator) {
+        StringBuilder buf = new StringBuilder(100);
+        buf.append(operandNumber).append(':').append(operand).append(' ');
+        if (!isRegister(operand)) {
+            if (location != null) {
+                buf.append("location{").append(location).append("} ");
+            }
+        }
+
+        buf.append("hints{").append(splitParent.operandNumber);
+        TraceInterval hint = locationHint(false);
+        if (hint != null && hint.operandNumber != splitParent.operandNumber) {
+            buf.append(", ").append(hint.operandNumber);
+        }
+        buf.append("} ranges{");
+
+        // print ranges
+        Range cur = first;
+        while (cur != Range.EndMarker) {
+            if (cur != first) {
+                buf.append(", ");
+            }
+            buf.append(cur);
+            cur = cur.next;
+            assert cur != null : "range list not closed with range sentinel";
+        }
+        buf.append("} uses{");
+
+        // print use positions
+        int prev = -1;
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            assert prev < usePosList.usePos(i) : "use positions not sorted";
+            if (i != usePosList.size() - 1) {
+                buf.append(", ");
+            }
+            buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i));
+            prev = usePosList.usePos(i);
+        }
+        buf.append("} spill-state{").append(spillState()).append("}");
+        if (canMaterialize()) {
+            buf.append(" (remat:").append(getMaterializedValue().toString()).append(")");
+        }
+        return buf.toString();
+    }
+
+    List<TraceInterval> getSplitChildren() {
+        return Collections.unmodifiableList(splitChildren);
+    }
+}

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Tue Sep 01 12:03:14 2015 +0200
@@ -42,7 +42,7 @@
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
 import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterBinding;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterBinding;
 import com.oracle.graal.lir.framemap.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
@@ -113,7 +113,7 @@
     private final List<? extends AbstractBlockBase<?>> sortedBlocks;
 
     /** @see #intervals() */
-    private Interval[] intervals;
+    private TraceInterval[] intervals;
 
     /**
      * The number of valid entries in {@link #intervals}.
@@ -122,14 +122,14 @@
 
     /**
      * The index of the first entry in {@link #intervals} for a
-     * {@linkplain #createDerivedInterval(Interval) derived interval}.
+     * {@linkplain #createDerivedInterval(TraceInterval) derived interval}.
      */
     private int firstDerivedIntervalIndex = -1;
 
     /**
-     * Intervals sorted by {@link Interval#from()}.
+     * Intervals sorted by {@link TraceInterval#from()}.
      */
-    private Interval[] sortedIntervals;
+    private TraceInterval[] sortedIntervals;
 
     /**
      * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
@@ -233,7 +233,7 @@
     static final IntervalPredicate IS_PRECOLORED_INTERVAL = new IntervalPredicate() {
 
         @Override
-        public boolean apply(Interval i) {
+        public boolean apply(TraceInterval i) {
             return isRegister(i.operand);
         }
     };
@@ -241,7 +241,7 @@
     static final IntervalPredicate IS_VARIABLE_INTERVAL = new IntervalPredicate() {
 
         @Override
-        public boolean apply(Interval i) {
+        public boolean apply(TraceInterval i) {
             return isVariable(i.operand);
         }
     };
@@ -249,7 +249,7 @@
     static final IntervalPredicate IS_STACK_INTERVAL = new IntervalPredicate() {
 
         @Override
-        public boolean apply(Interval i) {
+        public boolean apply(TraceInterval i) {
             return !isRegister(i.operand);
         }
     };
@@ -262,7 +262,7 @@
         return registerAttributes[reg.number];
     }
 
-    void assignSpillSlot(Interval interval) {
+    void assignSpillSlot(TraceInterval interval) {
         /*
          * Assign the canonical spill slot of the parent (if a part of the interval is already
          * spilled) or allocate a new spill slot.
@@ -281,13 +281,13 @@
     /**
      * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
      */
-    public Interval[] intervals() {
+    public TraceInterval[] intervals() {
         return intervals;
     }
 
     void initIntervals() {
         intervalsSize = operandSize();
-        intervals = new Interval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
+        intervals = new TraceInterval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
     }
 
     /**
@@ -296,10 +296,10 @@
      * @param operand the operand for the interval
      * @return the created interval
      */
-    Interval createInterval(AllocatableValue operand) {
+    TraceInterval createInterval(AllocatableValue operand) {
         assert isLegal(operand);
         int operandNumber = operandNumber(operand);
-        Interval interval = new Interval(operand, operandNumber);
+        TraceInterval interval = new TraceInterval(operand, operandNumber);
         assert operandNumber < intervalsSize;
         assert intervals[operandNumber] == null;
         intervals[operandNumber] = interval;
@@ -312,7 +312,7 @@
      * @param source an interval being split of spilled
      * @return a new interval derived from {@code source}
      */
-    Interval createDerivedInterval(Interval source) {
+    TraceInterval createDerivedInterval(TraceInterval source) {
         if (firstDerivedIntervalIndex == -1) {
             firstDerivedIntervalIndex = intervalsSize;
         }
@@ -322,7 +322,7 @@
         intervalsSize++;
         Variable variable = new Variable(source.kind(), ir.nextVariable());
 
-        Interval interval = createInterval(variable);
+        TraceInterval interval = createInterval(variable);
         assert intervals[intervalsSize - 1] == interval;
         return interval;
     }
@@ -339,7 +339,7 @@
     /**
      * Gets the size of the {@link BlockData#liveIn} and {@link BlockData#liveOut} sets for a basic
      * block. These sets do not include any operands allocated as a result of creating
-     * {@linkplain #createDerivedInterval(Interval) derived intervals}.
+     * {@linkplain #createDerivedInterval(TraceInterval) derived intervals}.
      */
     public int liveSetSize() {
         return firstDerivedIntervalIndex == -1 ? operandSize() : firstDerivedIntervalIndex;
@@ -349,18 +349,18 @@
         return ir.getControlFlowGraph().getLoops().size();
     }
 
-    Interval intervalFor(int operandNumber) {
+    TraceInterval intervalFor(int operandNumber) {
         return intervals[operandNumber];
     }
 
-    public Interval intervalFor(Value operand) {
+    public TraceInterval intervalFor(Value operand) {
         int operandNumber = operandNumber(operand);
         assert operandNumber < intervalsSize;
         return intervals[operandNumber];
     }
 
-    public Interval getOrCreateInterval(AllocatableValue operand) {
-        Interval ret = intervalFor(operand);
+    public TraceInterval getOrCreateInterval(AllocatableValue operand) {
+        TraceInterval ret = intervalFor(operand);
         if (ret == null) {
             return createInterval(operand);
         } else {
@@ -441,7 +441,7 @@
 
     abstract static class IntervalPredicate {
 
-        abstract boolean apply(Interval i);
+        abstract boolean apply(TraceInterval i);
     }
 
     public boolean isProcessed(Value operand) {
@@ -450,9 +450,9 @@
 
     // * Phase 5: actual register allocation
 
-    private static boolean isSorted(Interval[] intervals) {
+    private static boolean isSorted(TraceInterval[] intervals) {
         int from = -1;
-        for (Interval interval : intervals) {
+        for (TraceInterval interval : intervals) {
             assert interval != null;
             assert from <= interval.from();
             from = interval.from();
@@ -460,8 +460,8 @@
         return true;
     }
 
-    static Interval addToList(Interval first, Interval prev, Interval interval) {
-        Interval newFirst = first;
+    static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) {
+        TraceInterval newFirst = first;
         if (prev != null) {
             prev.next = interval;
         } else {
@@ -470,15 +470,15 @@
         return newFirst;
     }
 
-    Interval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
+    TraceInterval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
         assert isSorted(sortedIntervals) : "interval list is not sorted";
 
-        Interval list1 = Interval.EndMarker;
-        Interval list2 = Interval.EndMarker;
+        TraceInterval list1 = TraceInterval.EndMarker;
+        TraceInterval list2 = TraceInterval.EndMarker;
 
-        Interval list1Prev = null;
-        Interval list2Prev = null;
-        Interval v;
+        TraceInterval list1Prev = null;
+        TraceInterval list2Prev = null;
+        TraceInterval v;
 
         int n = sortedIntervals.length;
         for (int i = 0; i < n; i++) {
@@ -497,33 +497,33 @@
         }
 
         if (list1Prev != null) {
-            list1Prev.next = Interval.EndMarker;
+            list1Prev.next = TraceInterval.EndMarker;
         }
         if (list2Prev != null) {
-            list2Prev.next = Interval.EndMarker;
+            list2Prev.next = TraceInterval.EndMarker;
         }
 
-        assert list1Prev == null || list1Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
-        assert list2Prev == null || list2Prev.next == Interval.EndMarker : "linear list ends not with sentinel";
+        assert list1Prev == null || list1Prev.next == TraceInterval.EndMarker : "linear list ends not with sentinel";
+        assert list2Prev == null || list2Prev.next == TraceInterval.EndMarker : "linear list ends not with sentinel";
 
-        return new Interval.Pair(list1, list2);
+        return new TraceInterval.Pair(list1, list2);
     }
 
     protected void sortIntervalsBeforeAllocation() {
         int sortedLen = 0;
-        for (Interval interval : intervals) {
+        for (TraceInterval interval : intervals) {
             if (interval != null) {
                 sortedLen++;
             }
         }
 
-        Interval[] sortedList = new Interval[sortedLen];
+        TraceInterval[] sortedList = new TraceInterval[sortedLen];
         int sortedIdx = 0;
         int sortedFromMax = -1;
 
         // special sorting algorithm: the original interval-list is almost sorted,
         // only some intervals are swapped. So this is much faster than a complete QuickSort
-        for (Interval interval : intervals) {
+        for (TraceInterval interval : intervals) {
             if (interval != null) {
                 int from = interval.from();
 
@@ -551,16 +551,16 @@
             return;
         }
 
-        Interval[] oldList = sortedIntervals;
-        Interval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
+        TraceInterval[] oldList = sortedIntervals;
+        TraceInterval[] newList = Arrays.copyOfRange(intervals, firstDerivedIntervalIndex, intervalsSize);
         int oldLen = oldList.length;
         int newLen = newList.length;
 
         // conventional sort-algorithm for new intervals
-        Arrays.sort(newList, (Interval a, Interval b) -> a.from() - b.from());
+        Arrays.sort(newList, (TraceInterval a, TraceInterval b) -> a.from() - b.from());
 
         // merge old and new list (both already sorted) into one combined list
-        Interval[] combinedList = new Interval[oldLen + newLen];
+        TraceInterval[] combinedList = new TraceInterval[oldLen + newLen];
         int oldIdx = 0;
         int newIdx = 0;
 
@@ -579,8 +579,8 @@
 
     // wrapper for Interval.splitChildAtOpId that performs a bailout in product mode
     // instead of returning null
-    public Interval splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode) {
-        Interval result = interval.getSplitChildAtOpId(opId, mode, this);
+    public TraceInterval splitChildAtOpId(TraceInterval interval, int opId, LIRInstruction.OperandMode mode) {
+        TraceInterval result = interval.getSplitChildAtOpId(opId, mode, this);
 
         if (result != null) {
             if (Debug.isLogEnabled()) {
@@ -592,13 +592,13 @@
         throw new BailoutException("LinearScan: interval is null");
     }
 
-    static StackSlotValue canonicalSpillOpr(Interval interval) {
+    static StackSlotValue canonicalSpillOpr(TraceInterval interval) {
         assert interval.spillSlot() != null : "canonical spill slot not set";
         return interval.spillSlot();
     }
 
     boolean isMaterialized(AllocatableValue operand, int opId, OperandMode mode) {
-        Interval interval = intervalFor(operand);
+        TraceInterval interval = intervalFor(operand);
         assert interval != null : "interval must exist";
 
         if (opId != -1) {
@@ -686,7 +686,7 @@
         if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
             if (Debug.isLogEnabled()) {
                 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
-                    for (Interval interval : intervals) {
+                    for (TraceInterval interval : intervals) {
                         if (interval != null) {
                             Debug.log("%s", interval.logString(this));
                         }
@@ -734,7 +734,7 @@
             int len = intervalsSize;
 
             for (int i = 0; i < len; i++) {
-                Interval i1 = intervals[i];
+                TraceInterval i1 = intervals[i];
                 if (i1 == null) {
                     continue;
                 }
@@ -774,7 +774,7 @@
                 }
 
                 for (int j = i + 1; j < len; j++) {
-                    Interval i2 = intervals[j];
+                    TraceInterval i2 = intervals[j];
                     if (i2 == null) {
                         continue;
                     }
@@ -805,7 +805,7 @@
     class CheckConsumer implements ValueConsumer {
 
         boolean ok;
-        Interval curInterval;
+        TraceInterval curInterval;
 
         @Override
         public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
@@ -821,12 +821,12 @@
         try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
             CheckConsumer checkConsumer = new CheckConsumer();
 
-            Interval fixedIntervals;
-            Interval otherIntervals;
+            TraceInterval fixedIntervals;
+            TraceInterval otherIntervals;
             fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
             // to ensure a walking until the last instruction id, add a dummy interval
             // with a high operation id
-            otherIntervals = new Interval(Value.ILLEGAL, -1);
+            otherIntervals = new TraceInterval(Value.ILLEGAL, -1);
             otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
             IntervalWalker iw = new IntervalWalker(this, fixedIntervals, otherIntervals);
 
@@ -845,7 +845,7 @@
                          * can't handle that correctly.
                          */
                         if (checkLive) {
-                            for (Interval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != Interval.EndMarker; interval = interval.next) {
+                            for (TraceInterval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != TraceInterval.EndMarker; interval = interval.next) {
                                 if (interval.currentTo() > op.id() + 1) {
                                     /*
                                      * This interval is live out of this op so make sure that this

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java	Tue Sep 01 12:03:14 2015 +0200
@@ -77,7 +77,7 @@
      */
     protected Value colorLirOperand(LIRInstruction op, Variable operand, OperandMode mode) {
         int opId = op.id();
-        Interval interval = allocator.intervalFor(operand);
+        TraceInterval interval = allocator.intervalFor(operand);
         assert interval != null : "interval must exist";
 
         if (opId != -1) {
@@ -241,7 +241,7 @@
 
         public Value doValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) {
             if (isRegister(value) || isVariable(value)) {
-                Interval interval = allocator.intervalFor(value);
+                TraceInterval interval = allocator.intervalFor(value);
                 assert interval != null : "interval must exist";
                 interval = allocator.splitChildAtOpId(interval, instruction.id(), mode);
 

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Tue Sep 01 12:03:14 2015 +0200
@@ -37,7 +37,7 @@
 import com.oracle.graal.lir.StandardOp.LoadConstantOp;
 import com.oracle.graal.lir.StandardOp.MoveOp;
 import com.oracle.graal.lir.StandardOp.ValueMoveOp;
-import com.oracle.graal.lir.alloc.trace.Interval.SpillState;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState;
 import com.oracle.graal.lir.alloc.trace.TraceLinearScan.IntervalPredicate;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
@@ -48,7 +48,7 @@
     private static final IntervalPredicate mustStoreAtDefinition = new TraceLinearScan.IntervalPredicate() {
 
         @Override
-        public boolean apply(Interval i) {
+        public boolean apply(TraceInterval i) {
             return i.isSplitParent() && i.spillState() == SpillState.StoreAtDefinition;
         }
     };
@@ -82,7 +82,7 @@
              * collect all intervals that must be stored after their definition. The list is sorted
              * by Interval.spillDefinitionPos.
              */
-            Interval interval;
+            TraceInterval interval;
             interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).first;
             if (DetailedAsserts.getValue()) {
                 checkIntervals(interval);
@@ -131,10 +131,10 @@
                              * Insert move from register to stack just after the beginning of the
                              * interval.
                              */
-                            assert interval == Interval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order";
-                            assert interval == Interval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
+                            assert interval == TraceInterval.EndMarker || interval.spillDefinitionPos() >= opId : "invalid order";
+                            assert interval == TraceInterval.EndMarker || (interval.isSplitParent() && interval.spillState() == SpillState.StoreAtDefinition) : "invalid interval";
 
-                            while (interval != Interval.EndMarker && interval.spillDefinitionPos() == opId) {
+                            while (interval != TraceInterval.EndMarker && interval.spillDefinitionPos() == opId) {
                                 if (!interval.canMaterialize()) {
                                     if (!insertionBuffer.initialized()) {
                                         /*
@@ -171,7 +171,7 @@
                 }
             } // end of block iteration
 
-            assert interval == Interval.EndMarker : "missed an interval";
+            assert interval == TraceInterval.EndMarker : "missed an interval";
         }
     }
 
@@ -194,10 +194,10 @@
          */
     }
 
-    private static void checkIntervals(Interval interval) {
-        Interval prev = null;
-        Interval temp = interval;
-        while (temp != Interval.EndMarker) {
+    private static void checkIntervals(TraceInterval interval) {
+        TraceInterval prev = null;
+        TraceInterval temp = interval;
+        while (temp != TraceInterval.EndMarker) {
             assert temp.spillDefinitionPos() > 0 : "invalid spill definition pos";
             if (prev != null) {
                 assert temp.from() >= prev.from() : "intervals not sorted";

--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java	Tue Sep 01 11:49:35 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java	Tue Sep 01 12:03:14 2015 +0200
@@ -48,8 +48,8 @@
 import com.oracle.graal.lir.StandardOp.LoadConstantOp;
 import com.oracle.graal.lir.StandardOp.StackStoreOp;
 import com.oracle.graal.lir.StandardOp.ValueMoveOp;
-import com.oracle.graal.lir.alloc.trace.Interval.RegisterPriority;
-import com.oracle.graal.lir.alloc.trace.Interval.SpillState;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState;
 import com.oracle.graal.lir.alloc.trace.TraceLinearScan.BlockData;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
@@ -88,8 +88,8 @@
         return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock);
     }
 
-    static void setHint(final LIRInstruction op, Interval target, Interval source) {
-        Interval currentHint = target.locationHint(false);
+    static void setHint(final LIRInstruction op, TraceInterval target, TraceInterval source) {
+        TraceInterval currentHint = target.locationHint(false);
         if (currentHint == null || currentHint.from() > target.from()) {
             /*
              * Update hint if there was none or if the hint interval starts after the hinted
@@ -392,7 +392,7 @@
                 BitSet startBlockLiveIn = allocator.getBlockData(allocator.getLIR().getControlFlowGraph().getStartBlock()).liveIn;
                 try (Indent indent2 = Debug.logAndIndent("Error: liveIn set of first block must be empty (when this fails, variables are used before they are defined):")) {
                     for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                        Interval interval = allocator.intervalFor(operandNum);
+                        TraceInterval interval = allocator.intervalFor(operandNum);
                         if (interval != null) {
                             Value operand = interval.operand;
                             Debug.log("var %d; operand=%s; node=%s", operandNum, operand, getSourceForOperandFromDebugContext(operand));
@@ -404,7 +404,7 @@
 
                 // print some additional information to simplify debugging
                 for (int operandNum = startBlockLiveIn.nextSetBit(0); operandNum >= 0; operandNum = startBlockLiveIn.nextSetBit(operandNum + 1)) {
-                    Interval interval = allocator.intervalFor(operandNum);
+                    TraceInterval interval = allocator.intervalFor(operandNum);
                     Value operand = null;
                     Object valueForOperandFromDebugContext = null;
                     if (interval != null) {
@@ -488,7 +488,7 @@
             return;
         }
 
-        Interval interval = allocator.getOrCreateInterval(operand);
+        TraceInterval interval = allocator.getOrCreateInterval(operand);
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
@@ -508,7 +508,7 @@
             return;
         }
 
-        Interval interval = allocator.getOrCreateInterval(operand);
+        TraceInterval interval = allocator.getOrCreateInterval(operand);
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
@@ -528,7 +528,7 @@
         }
         int defPos = op.id();
 
-        Interval interval = allocator.getOrCreateInterval(operand);
+        TraceInterval interval = allocator.getOrCreateInterval(operand);
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
@@ -573,7 +573,7 @@
         if (op instanceof StackStoreOp) {
             StackStoreOp store = (StackStoreOp) op;
             StackSlot slot = asStackSlot(store.getStackSlot());
-            Interval interval = allocator.intervalFor(store.getResult());
+            TraceInterval interval = allocator.intervalFor(store.getResult());
             interval.setSpillSlot(slot);
             interval.setSpillState(SpillState.StartInMemory);
         }
@@ -584,8 +584,8 @@
 
             op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
                 if (TraceLinearScan.isVariableOrRegister(registerHint)) {
-                    Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
-                    Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
+                    TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
+                    TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
 
                     /* hints always point from def to use */
                     if (hintAtDef) {
@@ -610,7 +610,7 @@
      * @param op
      * @param operand
      */
-    protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) {
+    protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, TraceInterval interval, int defPos) {
         assert interval.isSplitParent() : "can only be called for split parents";
 
         switch (interval.spillState()) {
@@ -815,7 +815,7 @@
              * Add the range [0, 1] to all fixed intervals. the register allocator need not handle
              * unhandled fixed intervals.
              */
-            for (Interval interval : allocator.intervals()) {
+            for (TraceInterval interval : allocator.intervals()) {
                 if (interval != null && isRegister(interval.operand)) {
                     interval.addRange(0, 1);
                 }
@@ -826,7 +826,7 @@
 
     protected void postBuildIntervals() {
         // fix spill state for phi/sigma intervals
-        for (Interval interval : allocator.intervals()) {
+        for (TraceInterval interval : allocator.intervals()) {
             if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) {
                 // there was a definition in a phi/sigma
                 interval.setSpillState(SpillState.NoSpillStore);
@@ -852,13 +852,13 @@
                             assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue;
 
                             if (isRegister(fromValue) || isVariable(fromValue)) {
-                                Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue);
-                                Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
+                                TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) fromValue);
+                                TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
                                 setHint(label, to, from);
                             } else if (TraceRAshareSpillInformation.getValue() && TraceUtil.isShadowedRegisterValue(fromValue)) {
                                 ShadowedRegisterValue shadowedRegisterValue = TraceUtil.asShadowedRegisterValue(fromValue);
-                                Interval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister());
-                                Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
+                                TraceInterval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister());
+                                TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
                                 setHint(label, to, from);
                                 to.setSpillSlot(shadowedRegisterValue.getStackSlot());
                                 to.setSpillState(SpillState.StartInMemory);
@@ -872,7 +872,7 @@
          * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming
          * values.
          */
-        for (Interval interval : allocator.intervals()) {
+        for (TraceInterval interval : allocator.intervals()) {
             if (interval != null && isRegister(interval.operand)) {
                 Range range = interval.first();
                 if (range == Range.EndMarker) {
@@ -895,7 +895,7 @@
      *         reload-locations in case the interval of this instruction is spilled. Currently this
      *         can only be a {@link JavaConstant}.
      */
-    protected static JavaConstant getMaterializedValue(LIRInstruction op, Value operand, Interval interval) {
+    protected static JavaConstant getMaterializedValue(LIRInstruction op, Value operand, TraceInterval interval) {
         if (op instanceof LoadConstantOp) {
             LoadConstantOp move = (LoadConstantOp) op;
             if (move.getConstant() instanceof JavaConstant) {
@@ -905,11 +905,11 @@
                  * degradation, because rematerialization always inserts a constant load, even if
                  * the value is not needed in a register.
                  */
-                Interval.UsePosList usePosList = interval.usePosList();
+                TraceInterval.UsePosList usePosList = interval.usePosList();
                 int numUsePos = usePosList.size();
                 for (int useIdx = 0; useIdx < numUsePos; useIdx++) {
-                    Interval.RegisterPriority priority = usePosList.registerPriority(useIdx);
-                    if (priority == Interval.RegisterPriority.ShouldHaveRegister) {
+                    TraceInterval.RegisterPriority priority = usePosList.registerPriority(useIdx);
+                    if (priority == TraceInterval.RegisterPriority.ShouldHaveRegister) {
                         return null;
                     }
                 }