# HG changeset patch
# User Josef Eisl <josef.eisl@jku.at>
# Date 1441634582 -7200
# Node ID c8faebfb7aed931b6f0c48ff585a215d3a2654cf
# Parent  b887efbf86e363c05a8287e2a294f5bdc8c2e01d
TraceRA: clean-up and simplify.

diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedInterval.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedInterval.java	Mon Sep 07 16:03:02 2015 +0200
@@ -0,0 +1,308 @@
+/*
+ * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.*;
+
+/**
+ * Represents a fixed interval.
+ */
+public final class FixedInterval extends IntervalHint {
+
+    static final class FixedList {
+
+        public FixedInterval fixed;
+
+        public FixedList(FixedInterval fixed) {
+            this.fixed = fixed;
+        }
+
+        /**
+         * Gets the fixed list.
+         */
+        public FixedInterval getFixed() {
+            return fixed;
+        }
+
+        /**
+         * Sets the fixed list.
+         */
+        public void setFixed(FixedInterval list) {
+            fixed = list;
+        }
+
+        /**
+         * Adds an interval to a list sorted by {@linkplain FixedInterval#currentFrom() current
+         * from} positions.
+         *
+         * @param interval the interval to add
+         */
+        public void addToListSortedByCurrentFromPositions(FixedInterval interval) {
+            FixedInterval list = getFixed();
+            FixedInterval prev = null;
+            FixedInterval cur = list;
+            while (cur.currentFrom() < interval.currentFrom()) {
+                prev = cur;
+                cur = cur.next;
+            }
+            FixedInterval result = list;
+            if (prev == null) {
+                // add to head of list
+                result = interval;
+            } else {
+                // add before 'cur'
+                prev.next = interval;
+            }
+            interval.next = cur;
+            setFixed(result);
+        }
+
+    }
+
+    /**
+     * The fixed operand of this interval.
+     */
+    public final AllocatableValue operand;
+
+    /**
+     * The head of the list of ranges describing this interval. This list is sorted by
+     * {@linkplain LIRInstruction#id instruction ids}.
+     */
+    private FixedRange first;
+
+    /**
+     * Iterator used to traverse the ranges of an interval.
+     */
+    private FixedRange current;
+
+    /**
+     * Link to next interval in a sorted list of intervals that ends with {@link #EndMarker}.
+     */
+    FixedInterval next;
+
+    private int cachedTo; // cached value: to of last range (-1: not cached)
+
+    public FixedRange first() {
+        return first;
+    }
+
+    @Override
+    public int from() {
+        return first.from;
+    }
+
+    public int to() {
+        if (cachedTo == -1) {
+            cachedTo = calcTo();
+        }
+        assert cachedTo == calcTo() : "invalid cached value";
+        return cachedTo;
+    }
+
+    // test intersection
+    boolean intersects(TraceInterval i) {
+        return first.intersects(i);
+    }
+
+    int intersectsAt(TraceInterval i) {
+        return first.intersectsAt(i);
+    }
+
+    // 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 == FixedRange.EndMarker;
+    }
+
+    boolean currentIntersects(TraceInterval it) {
+        return current.intersects(it);
+    }
+
+    int currentIntersectsAt(TraceInterval it) {
+        return current.intersectsAt(it);
+    }
+
+    // range creation
+    public void setFrom(int from) {
+        assert !isEmpty();
+        first().from = from;
+    }
+
+    private boolean isEmpty() {
+        return first() == FixedRange.EndMarker;
+    }
+
+    public void addRange(int from, int to) {
+        if (isEmpty()) {
+            first = new FixedRange(from, to, first());
+            return;
+        }
+        if (to <= to() && from >= from()) {
+            return;
+        }
+        if (from() == to) {
+            first().from = from;
+        } else {
+            first = new FixedRange(from, to, first());
+        }
+    }
+
+    @Override
+    public AllocatableValue location() {
+        return operand;
+    }
+
+    /**
+     * Sentinel interval to denote the end of an interval list.
+     */
+    static final FixedInterval EndMarker = new FixedInterval(Value.ILLEGAL);
+
+    FixedInterval(AllocatableValue operand) {
+        assert operand != null;
+        this.operand = operand;
+        this.first = FixedRange.EndMarker;
+        this.current = FixedRange.EndMarker;
+        this.next = FixedInterval.EndMarker;
+        this.cachedTo = -1;
+    }
+
+    int calcTo() {
+        assert first != FixedRange.EndMarker : "interval has no range";
+
+        FixedRange r = first;
+        while (r.next != FixedRange.EndMarker) {
+            r = r.next;
+        }
+        return r.to;
+    }
+
+    // returns true if the opId is inside the interval
+    boolean covers(int opId, LIRInstruction.OperandMode mode) {
+        FixedRange cur = first;
+
+        while (cur != FixedRange.EndMarker && cur.to < opId) {
+            cur = cur.next;
+        }
+        if (cur != FixedRange.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";
+
+        FixedRange cur = first;
+        while (cur != FixedRange.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 != FixedRange.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.operand;
+        return asRegister(operand).number + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
+    }
+
+    /**
+     * Gets a single line string for logging the details of this interval to a log stream.
+     */
+    @Override
+    public String logString(TraceLinearScan allocator) {
+        StringBuilder buf = new StringBuilder(100);
+        buf.append("fix ").append(asRegister(operand).number).append(':').append(operand).append(' ');
+
+        buf.append(" ranges{");
+
+        // print ranges
+        FixedRange cur = first;
+        while (cur != FixedRange.EndMarker) {
+            if (cur != first) {
+                buf.append(", ");
+            }
+            buf.append(cur);
+            cur = cur.next;
+            assert cur != null : "range list not closed with range sentinel";
+        }
+        buf.append("}");
+        return buf.toString();
+    }
+
+}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedRange.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/FixedRange.java	Mon Sep 07 16:03:02 2015 +0200
@@ -0,0 +1,109 @@
+/*
+ * Copyright (c) 2015, 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;
+
+/**
+ * Represents a range of integers from a start (inclusive) to an end (exclusive).
+ */
+public final class FixedRange {
+
+    public static final FixedRange EndMarker = new FixedRange(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
+
+    /**
+     * The start of the range, inclusive.
+     */
+    public int from;
+
+    /**
+     * The end of the range, exclusive.
+     */
+    public int to;
+
+    /**
+     * A link to allow the range to be put into a singly linked list.
+     */
+    public FixedRange next;
+
+    boolean intersects(TraceInterval i) {
+        return intersectsAt(i) != -1;
+    }
+
+    /**
+     * Creates a new range.
+     *
+     * @param from the start of the range, inclusive
+     * @param to the end of the range, exclusive
+     * @param next link to the next range in a linked list
+     */
+    FixedRange(int from, int to, FixedRange next) {
+        this.from = from;
+        this.to = to;
+        this.next = next;
+    }
+
+    int intersectsAt(TraceInterval other) {
+        FixedRange range = this;
+        assert other != null : "null ranges not allowed";
+        assert range != EndMarker && other != TraceInterval.EndMarker : "empty ranges not allowed";
+        int intervalFrom = other.from();
+        int intervalTo = other.to();
+
+        do {
+            if (range.from < intervalFrom) {
+                if (range.to <= intervalFrom) {
+                    range = range.next;
+                    if (range == EndMarker) {
+                        return -1;
+                    }
+                } else {
+                    return intervalFrom;
+                }
+            } else {
+                if (intervalFrom < range.from) {
+                    if (intervalTo <= range.from) {
+                        return -1;
+                    }
+                    return range.from;
+                } else {
+                    assert range.from == intervalFrom;
+                    if (range.from == range.to) {
+                        range = range.next;
+                        if (range == EndMarker) {
+                            return -1;
+                        }
+                    } else {
+                        if (intervalFrom == intervalTo) {
+                            return -1;
+                        }
+                        return range.from;
+                    }
+                }
+            }
+        } while (true);
+    }
+
+    @Override
+    public String toString() {
+        return "[" + from + ", " + to + "]";
+    }
+}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalHint.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/IntervalHint.java	Mon Sep 07 16:03:02 2015 +0200
@@ -0,0 +1,37 @@
+/*
+ * Copyright (c) 2015, 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 jdk.internal.jvmci.meta.*;
+
+/**
+ * An interval that is a hint for an {@code TraceInterval interval}.
+ */
+abstract class IntervalHint {
+
+    public abstract AllocatableValue location();
+
+    public abstract int from();
+
+    public abstract String logString(TraceLinearScan allocator);
+}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Range.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/Range.java	Thu Sep 03 19:01:59 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,116 +0,0 @@
-/*
- * Copyright (c) 2009, 2011, 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;
-
-/**
- * Represents a range of integers from a start (inclusive) to an end (exclusive.
- */
-final class Range {
-
-    public static final Range EndMarker = new Range(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
-
-    /**
-     * The start of the range, inclusive.
-     */
-    public int from;
-
-    /**
-     * The end of the range, exclusive.
-     */
-    public int to;
-
-    /**
-     * A link to allow the range to be put into a singly linked list.
-     */
-    public Range next;
-
-    boolean intersects(Range r) {
-        return intersectsAt(r) != -1;
-    }
-
-    /**
-     * Creates a new range.
-     *
-     * @param from the start of the range, inclusive
-     * @param to the end of the range, exclusive
-     * @param next link to the next range in a linked list
-     */
-    Range(int from, int to, Range next) {
-        this.from = from;
-        this.to = to;
-        this.next = next;
-    }
-
-    int intersectsAt(Range other) {
-        Range r1 = this;
-        Range r2 = other;
-
-        assert r2 != null : "null ranges not allowed";
-        assert r1 != EndMarker && r2 != EndMarker : "empty ranges not allowed";
-
-        do {
-            if (r1.from < r2.from) {
-                if (r1.to <= r2.from) {
-                    r1 = r1.next;
-                    if (r1 == EndMarker) {
-                        return -1;
-                    }
-                } else {
-                    return r2.from;
-                }
-            } else {
-                if (r2.from < r1.from) {
-                    if (r2.to <= r1.from) {
-                        r2 = r2.next;
-                        if (r2 == EndMarker) {
-                            return -1;
-                        }
-                    } else {
-                        return r1.from;
-                    }
-                } else { // r1.from() == r2.from()
-                    if (r1.from == r1.to) {
-                        r1 = r1.next;
-                        if (r1 == EndMarker) {
-                            return -1;
-                        }
-                    } else {
-                        if (r2.from == r2.to) {
-                            r2 = r2.next;
-                            if (r2 == EndMarker) {
-                                return -1;
-                            }
-                        } else {
-                            return r1.from;
-                        }
-                    }
-                }
-            }
-        } while (true);
-    }
-
-    @Override
-    public String toString() {
-        return "[" + from + ", " + to + "]";
-    }
-}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/RegisterVerifier.java	Mon Sep 07 16:03:02 2015 +0200
@@ -53,7 +53,7 @@
 
     // currently, only registers are processed
     int stateSize() {
-        return allocator.maxRegisterNumber() + 1;
+        return allocator.numRegisters();
     }
 
     // accessors
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceInterval.java	Mon Sep 07 16:03:02 2015 +0200
@@ -39,99 +39,44 @@
 /**
  * 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;
+final class TraceInterval extends IntervalHint {
 
-        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;
+    static final class AnyList {
 
         /**
          * 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;
+        public AnyList(TraceInterval any) {
             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}
+         * Gets the any list.
          */
-        public TraceInterval get(RegisterBinding binding) {
-            switch (binding) {
-                case Any:
-                    return any;
-                case Fixed:
-                    return fixed;
-                case Stack:
-                    return stack;
-            }
-            throw JVMCIError.shouldNotReachHere();
+        public TraceInterval getAny() {
+            return any;
         }
 
         /**
-         * 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}
+         * Sets the any list.
          */
-        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;
-            }
+        public void setAny(TraceInterval list) {
+            any = list;
         }
 
         /**
-         * Adds an interval to a list sorted by {@linkplain TraceInterval#currentFrom() current
-         * from} positions.
+         * Adds an interval to a list sorted by {@linkplain TraceInterval#from() 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);
+        public void addToListSortedByFromPositions(TraceInterval interval) {
+            TraceInterval list = getAny();
             TraceInterval prev = null;
             TraceInterval cur = list;
-            while (cur.currentFrom() < interval.currentFrom()) {
+            while (cur.from() < interval.from()) {
                 prev = cur;
                 cur = cur.next;
             }
@@ -144,18 +89,17 @@
                 prev.next = interval;
             }
             interval.next = cur;
-            set(binding, result);
+            setAny(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);
+        public void addToListSortedByStartAndUsePositions(TraceInterval interval) {
+            TraceInterval list = getAny();
             TraceInterval prev = null;
             TraceInterval cur = list;
             while (cur.from() < interval.from() || (cur.from() == interval.from() && cur.firstUsage(RegisterPriority.None) < interval.firstUsage(RegisterPriority.None))) {
@@ -168,17 +112,16 @@
                 prev.next = interval;
             }
             interval.next = cur;
-            set(binding, list);
+            setAny(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);
+        public void removeAny(TraceInterval i) {
+            TraceInterval list = getAny();
             TraceInterval prev = null;
             TraceInterval cur = list;
             while (cur != i) {
@@ -187,7 +130,7 @@
                 cur = cur.next;
             }
             if (prev == null) {
-                set(binding, cur.next);
+                setAny(cur.next);
             } else {
                 prev.next = cur.next;
             }
@@ -235,6 +178,10 @@
         public boolean lessThan(RegisterPriority other) {
             return ordinal() < other.ordinal();
         }
+
+        public CharSequence shortName() {
+            return name().subSequence(0, 1);
+        }
     }
 
     /**
@@ -334,105 +281,6 @@
     }
 
     /**
-     * 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.
      */
@@ -461,10 +309,14 @@
     private LIRKind kind;
 
     /**
-     * The head of the list of ranges describing this interval. This list is sorted by
-     * {@linkplain LIRInstruction#id instruction ids}.
+     * The start of the range, inclusive.
      */
-    private Range first;
+    public int intFrom;
+
+    /**
+     * The end of the range, exclusive.
+     */
+    public int intTo;
 
     /**
      * List of (use-positions, register-priorities) pairs, sorted by use-positions.
@@ -472,11 +324,6 @@
     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;
@@ -486,8 +333,6 @@
      */
     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.
@@ -524,7 +369,7 @@
     /**
      * This interval should be assigned the same location as the hint interval.
      */
-    private TraceInterval locationHint;
+    private IntervalHint locationHint;
 
     /**
      * The value with which a spilled child interval can be re-materialized. Currently this must be
@@ -559,6 +404,7 @@
      * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to
      * this interval.
      */
+    @Override
     public AllocatableValue location() {
         return location;
     }
@@ -573,27 +419,28 @@
         this.kind = kind;
     }
 
-    public Range first() {
-        return first;
+    public boolean isEmpty() {
+        return intFrom == Integer.MAX_VALUE && intTo == Integer.MAX_VALUE;
     }
 
+    public void setFrom(int pos) {
+        intFrom = pos;
+    }
+
+    @Override
     public int from() {
-        return first.from;
+        return intFrom;
     }
 
     int to() {
-        if (cachedTo == -1) {
-            cachedTo = calcTo();
-        }
-        assert cachedTo == calcTo() : "invalid cached value";
-        return cachedTo;
+        return intTo;
     }
 
     int numUsePositions() {
         return usePosList.size();
     }
 
-    public void setLocationHint(TraceInterval interval) {
+    public void setLocationHint(IntervalHint interval) {
         locationHint = interval;
     }
 
@@ -672,41 +519,25 @@
 
     // test intersection
     boolean intersects(TraceInterval i) {
-        return first.intersects(i.first);
+        return intersectsAt(i) != -1;
     }
 
     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;
-    }
+        TraceInterval i1;
+        TraceInterval i2;
+        if (i.from() < this.from()) {
+            i1 = i;
+            i2 = this;
+        } else {
+            i1 = this;
+            i2 = i;
+        }
+        assert i1.from() <= i2.from();
 
-    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);
+        if (i1.to() <= i2.from()) {
+            return -1;
+        }
+        return i2.from();
     }
 
     /**
@@ -724,11 +555,10 @@
             assert isIllegal(operand) || isVariable(operand);
         }
         this.kind = LIRKind.Illegal;
-        this.first = Range.EndMarker;
+        this.intFrom = Integer.MAX_VALUE;
+        this.intTo = Integer.MAX_VALUE;
         this.usePosList = new UsePosList(4);
-        this.current = Range.EndMarker;
         this.next = EndMarker;
-        this.cachedTo = -1;
         this.spillState = SpillState.NoDefinitionFound;
         this.spillDefinitionPos = -1;
         splitParent = this;
@@ -763,16 +593,6 @@
         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()) {
@@ -803,23 +623,26 @@
         return true;
     }
 
-    public TraceInterval locationHint(boolean searchSplitChild) {
+    public IntervalHint locationHint(boolean searchSplitChild) {
         if (!searchSplitChild) {
             return locationHint;
         }
 
         if (locationHint != null) {
-            assert locationHint.isSplitParent() : "ony split parents are valid hint registers";
+            assert !(locationHint instanceof TraceInterval) || ((TraceInterval) locationHint).isSplitParent() : "ony split parents are valid hint registers";
 
-            if (locationHint.location != null && isRegister(locationHint.location)) {
+            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;
+            } else if (locationHint instanceof TraceInterval) {
+                TraceInterval hint = (TraceInterval) locationHint;
+                if (!hint.splitChildren.isEmpty()) {
+                    // search the first split child that has a register assigned
+                    int len = hint.splitChildren.size();
+                    for (int i = 0; i < len; i++) {
+                        TraceInterval interval = hint.splitChildren.get(i);
+                        if (interval.location != null && isRegister(interval.location)) {
+                            return interval;
+                        }
                     }
                 }
             }
@@ -1026,7 +849,7 @@
     }
 
     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);
+        assert isEmpty() || 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)) {
@@ -1053,17 +876,12 @@
 
     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());
+        if (from < intFrom) {
+            intFrom = from;
+        }
+        if (intTo == Integer.MAX_VALUE || intTo < to) {
+            intTo = to;
         }
     }
 
@@ -1110,26 +928,9 @@
         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
+        result.intTo = intTo;
+        result.intFrom = splitPos;
+        intTo = splitPos;
 
         // split list of use positions
         result.usePosList = usePosList.splitAt(splitPos);
@@ -1145,97 +946,21 @@
         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;
-            }
+        if (mode == LIRInstruction.OperandMode.DEF) {
+            return from() <= opId && opId < 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;
+        return from() <= opId && opId <= to();
     }
 
     @Override
     public String toString() {
         String from = "?";
         String to = "?";
-        if (first != null && first != Range.EndMarker) {
+        if (!isEmpty()) {
             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());
+            to = String.valueOf(to());
         }
         String locationString = this.location == null ? "" : "@" + this.location;
         return operandNumber + ":" + operand + (isRegister(operand) ? "" : locationString) + "[" + from + "," + to + "]";
@@ -1253,9 +978,10 @@
      *
      * @param allocator the register allocator context
      */
+    @Override
     public String logString(TraceLinearScan allocator) {
         StringBuilder buf = new StringBuilder(100);
-        buf.append(operandNumber).append(':').append(operand).append(' ');
+        buf.append("any ").append(operandNumber).append(':').append(operand).append(' ');
         if (!isRegister(operand)) {
             if (location != null) {
                 buf.append("location{").append(location).append("} ");
@@ -1263,22 +989,14 @@
         }
 
         buf.append("hints{").append(splitParent.operandNumber);
-        TraceInterval hint = locationHint(false);
-        if (hint != null && hint.operandNumber != splitParent.operandNumber) {
-            buf.append(", ").append(hint.operandNumber);
+        IntervalHint hint = locationHint(false);
+        if (hint != null) {
+            buf.append(", ").append(hint.location());
         }
         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";
-        }
+        // print range
+        buf.append("[" + from() + ", " + to() + "]");
         buf.append("} uses{");
 
         // print use positions
@@ -1288,7 +1006,7 @@
             if (i != usePosList.size() - 1) {
                 buf.append(", ");
             }
-            buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i));
+            buf.append(usePosList.usePos(i)).append(':').append(usePosList.registerPriority(i).shortName());
             prev = usePosList.usePos(i);
         }
         buf.append("} spill-state{").append(spillState()).append("}");
@@ -1301,4 +1019,57 @@
     List<TraceInterval> getSplitChildren() {
         return Collections.unmodifiableList(splitChildren);
     }
+
+    boolean isFixedInterval() {
+        return isRegister(operand);
+    }
+
+    private static boolean isDefinitionPosition(int usePos) {
+        return (usePos & 1) == 1;
+    }
+
+    int currentFrom(int currentPosition) {
+        assert isFixedInterval();
+        for (int i = 0; i < usePosList.size(); i++) {
+            int usePos = usePosList.usePos(i);
+            if (usePos <= currentPosition && isDefinitionPosition(usePos)) {
+                return usePos;
+            }
+
+        }
+        return Integer.MAX_VALUE;
+    }
+
+    int currentIntersectsAt(int currentPosition, TraceInterval current) {
+        assert isFixedInterval();
+        assert !current.isFixedInterval();
+        int from = Integer.MAX_VALUE;
+        int to = Integer.MIN_VALUE;
+
+        for (int i = 0; i < usePosList.size(); i++) {
+            int usePos = usePosList.usePos(i);
+            if (isDefinitionPosition(usePos)) {
+                if (usePos <= currentPosition) {
+                    from = usePos;
+                    break;
+                }
+                to = Integer.MIN_VALUE;
+            } else {
+                if (to < usePos) {
+                    to = usePos;
+                }
+            }
+        }
+        if (from < current.from()) {
+            if (to <= current.from()) {
+                return -1;
+            }
+            return current.from();
+        } else {
+            if (current.to() <= from) {
+                return -1;
+            }
+            return from;
+        }
+    }
 }
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalDumper.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalDumper.java	Mon Sep 07 16:03:02 2015 +0200
@@ -0,0 +1,92 @@
+/*
+ * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*;
+import jdk.internal.jvmci.meta.*;
+
+import com.oracle.graal.lir.debug.*;
+
+final class TraceIntervalDumper implements IntervalDumper {
+    private final FixedInterval[] fixedIntervals;
+    private final TraceInterval[] intervals;
+
+    public TraceIntervalDumper(FixedInterval[] fixedIntervals, TraceInterval[] intervals) {
+        this.fixedIntervals = fixedIntervals;
+        this.intervals = intervals;
+    }
+
+    public void visitIntervals(IntervalVisitor visitor) {
+        for (FixedInterval interval : fixedIntervals) {
+            if (interval != null) {
+                printFixedInterval(interval, visitor);
+            }
+        }
+        for (TraceInterval interval : intervals) {
+            if (interval != null) {
+                printInterval(interval, visitor);
+            }
+        }
+    }
+
+    private static void printFixedInterval(FixedInterval interval, IntervalVisitor visitor) {
+        Value hint = null;
+        AllocatableValue operand = interval.operand;
+        String type = "fixed";
+        char typeChar = operand.getKind().getTypeChar();
+        visitor.visitIntervalStart(operand, operand, operand, hint, type, typeChar);
+
+        // print ranges
+        for (FixedRange range = interval.first(); range != FixedRange.EndMarker; range = range.next) {
+            visitor.visitRange(range.from, range.to);
+        }
+
+        // no use positions
+
+        visitor.visitIntervalEnd("NOT_SUPPORTED");
+
+    }
+
+    private static void printInterval(TraceInterval interval, IntervalVisitor visitor) {
+        Value hint = interval.locationHint(false) != null ? interval.locationHint(false).location() : null;
+        AllocatableValue operand = interval.operand;
+        String type = isRegister(operand) ? "fixed" : operand.getLIRKind().getPlatformKind().toString();
+        char typeChar = operand.getKind().getTypeChar();
+        visitor.visitIntervalStart(interval.splitParent().operand, operand, interval.location(), hint, type, typeChar);
+
+        // print ranges
+        visitor.visitRange(interval.from(), interval.to());
+
+        // print use positions
+        int prev = -1;
+        UsePosList usePosList = interval.usePosList();
+        for (int i = usePosList.size() - 1; i >= 0; --i) {
+            assert prev < usePosList.usePos(i) : "use positions not sorted";
+            visitor.visitUsePos(usePosList.usePos(i), usePosList.registerPriority(i));
+            prev = usePosList.usePos(i);
+        }
+
+        visitor.visitIntervalEnd(interval.spillState());
+    }
+
+}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalWalker.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalWalker.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceIntervalWalker.java	Mon Sep 07 16:03:02 2015 +0200
@@ -22,10 +22,12 @@
  */
 package com.oracle.graal.lir.alloc.trace;
 
-import com.oracle.graal.debug.*;
+import jdk.internal.jvmci.common.*;
 
+import com.oracle.graal.debug.*;
+import com.oracle.graal.lir.alloc.trace.FixedInterval.FixedList;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.AnyList;
 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;
 
 /**
@@ -37,17 +39,18 @@
     /**
      * Sorted list of intervals, not live before the current position.
      */
-    protected RegisterBindingLists unhandledLists;
+    protected AnyList unhandledAnyList;
 
     /**
      * Sorted list of intervals, live at the current position.
      */
-    protected RegisterBindingLists activeLists;
+    protected AnyList activeAnyList;
+    protected FixedList activeFixedList;
 
     /**
      * Sorted list of intervals in a life time hole at the current position.
      */
-    protected RegisterBindingLists inactiveLists;
+    protected FixedList inactiveFixedList;
 
     /**
      * The current position (intercept point through the intervals).
@@ -55,20 +58,43 @@
     protected int currentPosition;
 
     /**
-     * The binding of the current interval being processed.
-     */
-    protected RegisterBinding currentBinding;
-
-    /**
      * Processes the {@code currentInterval} interval in an attempt to allocate a physical register
-     * to it and thus allow it to be moved to a list of {@linkplain #activeLists active} intervals.
+     * to it and thus allow it to be moved to a list of {@linkplain #activeAnyList active}
+     * intervals.
+     *
+     * @param currentInterval The interval to be activated.
      *
      * @return {@code true} if a register was allocated to the {@code currentInterval} interval
      */
-    protected boolean activateCurrent(@SuppressWarnings({"unused"}) TraceInterval currentInterval) {
+    protected boolean activateCurrent(TraceInterval currentInterval) {
+        if (Debug.isLogEnabled()) {
+            logCurrentStatus();
+        }
         return true;
     }
 
+    protected void logCurrentStatus() {
+        try (Indent i = Debug.logAndIndent("active:")) {
+            logList(activeFixedList.getFixed());
+            logList(activeAnyList.getAny());
+        }
+        try (Indent i = Debug.logAndIndent("inactive(fixed):")) {
+            logList(inactiveFixedList.getFixed());
+        }
+    }
+
+    private void logList(FixedInterval i) {
+        for (FixedInterval interval = i; interval != FixedInterval.EndMarker; interval = interval.next) {
+            Debug.log("%s", interval.logString(allocator));
+        }
+    }
+
+    private void logList(TraceInterval i) {
+        for (TraceInterval interval = i; interval != TraceInterval.EndMarker; interval = interval.next) {
+            Debug.log("%s", interval.logString(allocator));
+        }
+    }
+
     void walkBefore(int lirOpId) {
         walkTo(lirOpId - 1);
     }
@@ -86,37 +112,46 @@
      * @param unhandledAny the list of unhandled {@linkplain RegisterBinding#Any non-fixed}
      *            intervals
      */
-    TraceIntervalWalker(TraceLinearScan allocator, TraceInterval unhandledFixed, TraceInterval unhandledAny) {
+    TraceIntervalWalker(TraceLinearScan allocator, FixedInterval unhandledFixed, TraceInterval unhandledAny) {
         this.allocator = allocator;
 
-        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);
+        unhandledAnyList = new AnyList(unhandledAny);
+        activeAnyList = new AnyList(TraceInterval.EndMarker);
+        activeFixedList = new FixedList(FixedInterval.EndMarker);
+        // we don't need a separate unhandled list for fixed.
+        inactiveFixedList = new FixedList(unhandledFixed);
         currentPosition = -1;
     }
 
     protected void removeFromList(TraceInterval interval) {
         if (interval.state == State.Active) {
-            activeLists.remove(RegisterBinding.Any, interval);
+            activeAnyList.removeAny(interval);
         } else {
             assert interval.state == State.Inactive : "invalid state";
-            inactiveLists.remove(RegisterBinding.Any, interval);
+            // inactiveAnyLists.removeAny(interval);
+            throw JVMCIError.shouldNotReachHere();
         }
     }
 
-    private void walkTo(State state, int from) {
+    /**
+     * Walks up to {@code from} and updates the state of {@link FixedInterval fixed intervals}.
+     *
+     * Fixed intervals can switch back and forth between the states {@link State#Active} and
+     * {@link State#Inactive} (and eventually to {@link State#Handled} but handled intervals are not
+     * managed).
+     */
+    private void walkToFixed(State state, int from) {
         assert state == State.Active || state == State.Inactive : "wrong state";
-        for (RegisterBinding binding : RegisterBinding.VALUES) {
-            walkTo(state, from, binding);
+        FixedInterval prevprev = null;
+        FixedInterval prev = (state == State.Active) ? activeFixedList.getFixed() : inactiveFixedList.getFixed();
+        FixedInterval next = prev;
+        if (Debug.isLogEnabled()) {
+            try (Indent i = Debug.logAndIndent("walkToFixed(%s, %d):", state, from)) {
+                logList(next);
+            }
         }
-    }
-
-    private void walkTo(State state, int from, RegisterBinding binding) {
-        TraceInterval prevprev = null;
-        TraceInterval prev = (state == State.Active) ? activeLists.get(binding) : inactiveLists.get(binding);
-        TraceInterval next = prev;
         while (next.currentFrom() <= from) {
-            TraceInterval cur = next;
+            FixedInterval cur = next;
             next = cur.next;
 
             boolean rangeHasChanged = false;
@@ -132,9 +167,9 @@
                 // remove cur from list
                 if (prevprev == null) {
                     if (state == State.Active) {
-                        activeLists.set(binding, next);
+                        activeFixedList.setFixed(next);
                     } else {
-                        inactiveLists.set(binding, next);
+                        inactiveFixedList.setFixed(next);
                     }
                 } else {
                     prevprev.next = next;
@@ -144,18 +179,16 @@
                 if (cur.currentAtEnd()) {
                     // move to handled state (not maintained as a list)
                     newState = State.Handled;
-                    cur.state = newState;
                 } else {
                     if (cur.currentFrom() <= from) {
                         // sort into active list
-                        activeLists.addToListSortedByCurrentFromPositions(binding, cur);
+                        activeFixedList.addToListSortedByCurrentFromPositions(cur);
                         newState = State.Active;
                     } else {
                         // sort into inactive list
-                        inactiveLists.addToListSortedByCurrentFromPositions(binding, cur);
+                        inactiveFixedList.addToListSortedByCurrentFromPositions(cur);
                         newState = State.Inactive;
                     }
-                    cur.state = newState;
                     if (prev == cur) {
                         assert state == newState;
                         prevprev = prev;
@@ -171,50 +204,71 @@
     }
 
     /**
-     * Get the next interval from {@linkplain #unhandledLists} which starts before or at
-     * {@code toOpId}. The returned interval is removed and {@link #currentBinding} is set.
+     * Walks up to {@code from} and updates the state of {@link TraceInterval intervals}.
      *
-     * @postcondition all intervals in {@linkplain #unhandledLists} start after {@code toOpId}.
+     * Trace intervals can switch once from {@link State#Unhandled} to {@link State#Active} and then
+     * to {@link State#Handled} but handled intervals are not managed.
+     */
+    private void walkToAny(int from) {
+        TraceInterval prevprev = null;
+        TraceInterval prev = activeAnyList.getAny();
+        TraceInterval next = prev;
+        if (Debug.isLogEnabled()) {
+            try (Indent i = Debug.logAndIndent("walkToAny(%d):", from)) {
+                logList(next);
+            }
+        }
+        while (next.from() <= from) {
+            TraceInterval cur = next;
+            next = cur.next;
+
+            if (cur.to() <= from) {
+                // remove cur from list
+                if (prevprev == null) {
+                    activeAnyList.setAny(next);
+                } else {
+                    prevprev.next = next;
+                }
+                intervalMoved(cur, State.Active, State.Handled);
+            } else {
+                prevprev = prev;
+            }
+            prev = next;
+        }
+    }
+
+    /**
+     * Get the next interval from {@linkplain #unhandledAnyList} which starts before or at
+     * {@code toOpId}. The returned interval is removed.
      *
-     * @return The next interval or null if there is no {@linkplain #unhandledLists unhandled}
+     * @postcondition all intervals in {@linkplain #unhandledAnyList} start after {@code toOpId}.
+     *
+     * @return The next interval or null if there is no {@linkplain #unhandledAnyList unhandled}
      *         interval at position {@code toOpId}.
      */
     private TraceInterval nextInterval(int toOpId) {
-        RegisterBinding binding;
-        TraceInterval any = unhandledLists.any;
-        TraceInterval fixed = unhandledLists.fixed;
+        TraceInterval any = unhandledAnyList.getAny();
 
         if (any != TraceInterval.EndMarker) {
-            // intervals may start at same position . prefer fixed interval
-            binding = fixed != TraceInterval.EndMarker && fixed.from() <= any.from() ? RegisterBinding.Fixed : RegisterBinding.Any;
+            TraceInterval currentInterval = unhandledAnyList.getAny();
+            if (toOpId < currentInterval.from()) {
+                return null;
+            }
 
-            assert binding == RegisterBinding.Fixed && fixed.from() <= any.from() || binding == RegisterBinding.Any && any.from() <= fixed.from() : "wrong interval!!!";
-            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 != TraceInterval.EndMarker) {
-            binding = RegisterBinding.Fixed;
-        } else {
-            return null;
+            unhandledAnyList.setAny(currentInterval.next);
+            currentInterval.next = TraceInterval.EndMarker;
+            return currentInterval;
         }
-        TraceInterval currentInterval = unhandledLists.get(binding);
-
-        if (toOpId < currentInterval.from()) {
-            return null;
-        }
+        return null;
 
-        currentBinding = binding;
-        unhandledLists.set(binding, currentInterval.next);
-        currentInterval.next = TraceInterval.EndMarker;
-        currentInterval.rewindRange();
-        return currentInterval;
     }
 
     /**
      * Walk up to {@code toOpId}.
      *
-     * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeLists} and
-     *                {@link #inactiveLists} are populated and {@link TraceInterval#state}s are up
-     *                to date.
+     * @postcondition {@link #currentPosition} is set to {@code toOpId}, {@link #activeFixedList}
+     *                and {@link #inactiveFixedList} are populated and {@link TraceInterval#state}s
+     *                are up to date.
      */
     @SuppressWarnings("try")
     protected void walkTo(int toOpId) {
@@ -226,16 +280,17 @@
             currentPosition = opId;
 
             // update unhandled stack intervals
-            updateUnhandledStackIntervals(opId);
+            // updateUnhandledStackIntervals(opId);
 
             // call walkTo even if currentPosition == id
-            walkTo(State.Active, opId);
-            walkTo(State.Inactive, opId);
+            walkToFixed(State.Active, opId);
+            walkToFixed(State.Inactive, opId);
+            walkToAny(opId);
 
             try (Indent indent = Debug.logAndIndent("walk to op %d", opId)) {
                 currentInterval.state = State.Active;
                 if (activateCurrent(currentInterval)) {
-                    activeLists.addToListSortedByCurrentFromPositions(currentBinding, currentInterval);
+                    activeAnyList.addToListSortedByFromPositions(currentInterval);
                     intervalMoved(currentInterval, State.Unhandled, State.Active);
                 }
             }
@@ -245,44 +300,20 @@
 
         if (currentPosition <= allocator.maxOpId()) {
             // update unhandled stack intervals
-            updateUnhandledStackIntervals(toOpId);
+            // updateUnhandledStackIntervals(toOpId);
 
             // call walkTo if still in range
-            walkTo(State.Active, toOpId);
-            walkTo(State.Inactive, toOpId);
+            walkToFixed(State.Active, toOpId);
+            walkToFixed(State.Inactive, toOpId);
+            walkToAny(toOpId);
         }
     }
 
-    private void intervalMoved(TraceInterval interval, State from, State to) {
+    private void intervalMoved(IntervalHint 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()) {
             Debug.log("interval moved from %s to %s: %s", from, to, interval.logString(allocator));
         }
     }
-
-    /**
-     * Move {@linkplain #unhandledLists unhandled} stack intervals to
-     * {@linkplain TraceIntervalWalker #activeLists active}.
-     *
-     * Note that for {@linkplain RegisterBinding#Fixed fixed} and {@linkplain RegisterBinding#Any
-     * any} intervals this is done in {@link #nextInterval(int)}.
-     */
-    private void updateUnhandledStackIntervals(int opId) {
-        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);
-                intervalMoved(currentInterval, State.Unhandled, State.Active);
-            } else {
-                currentInterval.state = State.Handled;
-                intervalMoved(currentInterval, State.Unhandled, State.Handled);
-            }
-            currentInterval = next;
-        }
-        unhandledLists.set(RegisterBinding.Stack, currentInterval);
-    }
-
 }
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java	Mon Sep 07 16:03:02 2015 +0200
@@ -32,7 +32,6 @@
 import jdk.internal.jvmci.code.*;
 import jdk.internal.jvmci.common.*;
 import jdk.internal.jvmci.meta.*;
-import jdk.internal.jvmci.options.*;
 
 import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
@@ -42,7 +41,6 @@
 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.TraceInterval.RegisterBinding;
 import com.oracle.graal.lir.framemap.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
@@ -56,13 +54,6 @@
  */
 final class TraceLinearScan {
 
-    public static class Options {
-        // @formatter:off
-        @Option(help = "Use simplified lifetime analysis.", type = OptionType.Debug)
-        public static final OptionValue<Boolean> TraceRAsimpleLifetimeAnalysis = new OptionValue<>(true);
-        // @formatter:on
-    }
-
     public static class BlockData {
 
         /**
@@ -112,6 +103,9 @@
      */
     private final List<? extends AbstractBlockBase<?>> sortedBlocks;
 
+    /** @see #fixedIntervals() */
+    private final FixedInterval[] fixedIntervals;
+
     /** @see #intervals() */
     private TraceInterval[] intervals;
 
@@ -132,6 +126,11 @@
     private TraceInterval[] sortedIntervals;
 
     /**
+     * Fixed intervals sorted by {@link FixedInterval#from()}.
+     */
+    private FixedInterval[] sortedFixedIntervals;
+
+    /**
      * Map from an instruction {@linkplain LIRInstruction#id id} to the instruction. Entries should
      * be retrieved with {@link #instructionForId(int)} as the id is not simply an index into this
      * array.
@@ -145,10 +144,6 @@
      */
     private AbstractBlockBase<?>[] opIdToBlockMap;
 
-    /**
-     * The {@linkplain #operandNumber(Value) number} of the first variable operand allocated.
-     */
-    private final int firstVariableNumber;
     protected final TraceBuilderResult<?> traceBuilderResult;
 
     protected TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig,
@@ -161,7 +156,7 @@
         this.regAllocConfig = regAllocConfig;
 
         this.registers = target.arch.getRegisters();
-        this.firstVariableNumber = getRegisters().length;
+        this.fixedIntervals = new FixedInterval[registers.length];
         this.blockData = new BlockMap<>(ir.getControlFlowGraph());
         this.traceBuilderResult = traceBuilderResult;
     }
@@ -198,28 +193,25 @@
      * the {@linkplain Variable variables} and {@linkplain RegisterValue registers} being processed
      * by this allocator.
      */
+    @SuppressWarnings("static-method")
     int operandNumber(Value operand) {
-        if (isRegister(operand)) {
-            int number = asRegister(operand).number;
-            assert number < firstVariableNumber;
-            return number;
-        }
-        assert isVariable(operand) : operand;
-        return firstVariableNumber + ((Variable) operand).index;
+        assert !isRegister(operand) : "Register do not have operand numbers: " + operand;
+        assert isVariable(operand) : "Unsupported Value " + operand;
+        return ((Variable) operand).index;
     }
 
     /**
      * Gets the number of operands. This value will increase by 1 for new variable.
      */
     int operandSize() {
-        return firstVariableNumber + ir.numVariables();
+        return ir.numVariables();
     }
 
     /**
-     * Gets the highest operand number for a register operand. This value will never change.
+     * Gets the number of registers. This value will never change.
      */
-    int maxRegisterNumber() {
-        return firstVariableNumber - 1;
+    int numRegisters() {
+        return registers.length;
     }
 
     public BlockData getBlockData(AbstractBlockBase<?> block) {
@@ -285,12 +277,33 @@
         return intervals;
     }
 
+    /**
+     * Map from {@linkplain #operandNumber(Value) operand numbers} to intervals.
+     */
+    public FixedInterval[] fixedIntervals() {
+        return fixedIntervals;
+    }
+
     void initIntervals() {
         intervalsSize = operandSize();
         intervals = new TraceInterval[intervalsSize + (intervalsSize >> SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT)];
     }
 
     /**
+     * Creates a new fixed interval.
+     *
+     * @param reg the operand for the interval
+     * @return the created interval
+     */
+    FixedInterval createFixedInterval(RegisterValue reg) {
+        FixedInterval interval = new FixedInterval(reg);
+        int operandNumber = reg.getRegister().number;
+        assert fixedIntervals[operandNumber] == null;
+        fixedIntervals[operandNumber] = interval;
+        return interval;
+    }
+
+    /**
      * Creates a new interval.
      *
      * @param operand the operand for the interval
@@ -349,6 +362,19 @@
         return ir.getControlFlowGraph().getLoops().size();
     }
 
+    public FixedInterval fixedIntervalFor(RegisterValue reg) {
+        return fixedIntervals[reg.getRegister().number];
+    }
+
+    public FixedInterval getOrCreateFixedInterval(RegisterValue reg) {
+        FixedInterval ret = fixedIntervalFor(reg);
+        if (ret == null) {
+            return createFixedInterval(reg);
+        } else {
+            return ret;
+        }
+    }
+
     TraceInterval intervalFor(int operandNumber) {
         return intervals[operandNumber];
     }
@@ -450,9 +476,9 @@
 
     // * Phase 5: actual register allocation
 
-    private static boolean isSorted(TraceInterval[] intervals) {
+    private static <T extends IntervalHint> boolean isSorted(T[] intervals) {
         int from = -1;
-        for (TraceInterval interval : intervals) {
+        for (T interval : intervals) {
             assert interval != null;
             assert from <= interval.from();
             from = interval.from();
@@ -460,7 +486,7 @@
         return true;
     }
 
-    static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) {
+    private static TraceInterval addToList(TraceInterval first, TraceInterval prev, TraceInterval interval) {
         TraceInterval newFirst = first;
         if (prev != null) {
             prev.next = interval;
@@ -470,14 +496,12 @@
         return newFirst;
     }
 
-    TraceInterval.Pair createUnhandledLists(IntervalPredicate isList1, IntervalPredicate isList2) {
+    TraceInterval createUnhandledList(IntervalPredicate isList1) {
         assert isSorted(sortedIntervals) : "interval list is not sorted";
 
         TraceInterval list1 = TraceInterval.EndMarker;
-        TraceInterval list2 = TraceInterval.EndMarker;
 
         TraceInterval list1Prev = null;
-        TraceInterval list2Prev = null;
         TraceInterval v;
 
         int n = sortedIntervals.length;
@@ -490,25 +514,59 @@
             if (isList1.apply(v)) {
                 list1 = addToList(list1, list1Prev, v);
                 list1Prev = v;
-            } else if (isList2 == null || isList2.apply(v)) {
-                list2 = addToList(list2, list2Prev, v);
-                list2Prev = v;
             }
         }
 
         if (list1Prev != null) {
             list1Prev.next = TraceInterval.EndMarker;
         }
-        if (list2Prev != null) {
-            list2Prev.next = TraceInterval.EndMarker;
-        }
 
         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 list1;
+    }
+
+    private static FixedInterval addToList(FixedInterval first, FixedInterval prev, FixedInterval interval) {
+        FixedInterval newFirst = first;
+        if (prev != null) {
+            prev.next = interval;
+        } else {
+            newFirst = interval;
+        }
+        return newFirst;
+    }
+
+    FixedInterval createFixedUnhandledList() {
+        assert isSorted(sortedFixedIntervals) : "interval list is not sorted";
+
+        FixedInterval list1 = FixedInterval.EndMarker;
+
+        FixedInterval list1Prev = null;
+        FixedInterval v;
 
-        return new TraceInterval.Pair(list1, list2);
+        int n = sortedFixedIntervals.length;
+        for (int i = 0; i < n; i++) {
+            v = sortedFixedIntervals[i];
+            if (v == null) {
+                continue;
+            }
+
+            v.rewindRange();
+            list1 = addToList(list1, list1Prev, v);
+            list1Prev = v;
+        }
+
+        if (list1Prev != null) {
+            list1Prev.next = FixedInterval.EndMarker;
+        }
+
+        assert list1Prev == null || list1Prev.next == FixedInterval.EndMarker : "linear list ends not with sentinel";
+
+        return list1;
     }
 
+    // SORTING
+
     protected void sortIntervalsBeforeAllocation() {
         int sortedLen = 0;
         for (TraceInterval interval : intervals) {
@@ -516,14 +574,26 @@
                 sortedLen++;
             }
         }
+        sortedIntervals = sortIntervalsBeforeAllocation(intervals, new TraceInterval[sortedLen]);
+    }
 
-        TraceInterval[] sortedList = new TraceInterval[sortedLen];
+    protected void sortFixedIntervalsBeforeAllocation() {
+        int sortedLen = 0;
+        for (FixedInterval interval : fixedIntervals) {
+            if (interval != null) {
+                sortedLen++;
+            }
+        }
+        sortedFixedIntervals = sortIntervalsBeforeAllocation(fixedIntervals, new FixedInterval[sortedLen]);
+    }
+
+    private static <T extends IntervalHint> T[] sortIntervalsBeforeAllocation(T[] intervals, T[] sortedList) {
         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 (TraceInterval interval : intervals) {
+        for (T interval : intervals) {
             if (interval != null) {
                 int from = interval.from();
 
@@ -542,7 +612,7 @@
                 }
             }
         }
-        sortedIntervals = sortedList;
+        return sortedList;
     }
 
     void sortIntervalsAfterAllocation() {
@@ -630,12 +700,10 @@
 
             try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals())) {
                 sortIntervalsBeforeAllocation();
+                sortFixedIntervalsBeforeAllocation();
 
                 createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
 
-                if (com.oracle.graal.lir.alloc.lsra.LinearScan.Options.LIROptLSRAOptimizeSpillPosition.getValue()) {
-                    createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
-                }
                 // resolve intra-trace data-flow
                 TraceLinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase();
                 dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false);
@@ -654,9 +722,6 @@
     }
 
     protected TraceLinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() {
-        if (Options.TraceRAsimpleLifetimeAnalysis.getValue()) {
-            return new TraceSimpleLifetimeAnalysisPhase(this, traceBuilderResult);
-        }
         return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult);
     }
 
@@ -679,15 +744,17 @@
         return new TraceLinearScanRegisterAllocationPhase(this);
     }
 
-    protected TraceLinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase() {
-        return new TraceLinearScanOptimizeSpillPositionPhase(this);
-    }
-
     @SuppressWarnings("try")
     public void printIntervals(String label) {
         if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) {
             if (Debug.isLogEnabled()) {
                 try (Indent indent = Debug.logAndIndent("intervals %s", label)) {
+                    for (FixedInterval interval : fixedIntervals) {
+                        if (interval != null) {
+                            Debug.log("%s", interval.logString(this));
+                        }
+                    }
+
                     for (TraceInterval interval : intervals) {
                         if (interval != null) {
                             Debug.log("%s", interval.logString(this));
@@ -702,7 +769,7 @@
                     }
                 }
             }
-            Debug.dump(Arrays.copyOf(intervals, intervalsSize), label);
+            Debug.dump(new TraceIntervalDumper(Arrays.copyOf(fixedIntervals, fixedIntervals.length), Arrays.copyOf(intervals, intervalsSize)), label);
         }
     }
 
@@ -738,7 +805,7 @@
             int len = intervalsSize;
 
             for (int i = 0; i < len; i++) {
-                TraceInterval i1 = intervals[i];
+                final TraceInterval i1 = intervals[i];
                 if (i1 == null) {
                     continue;
                 }
@@ -763,39 +830,59 @@
                     throw new JVMCIError("");
                 }
 
-                if (i1.first() == Range.EndMarker) {
+                if (i1.isEmpty()) {
                     Debug.log("Interval %d has no Range", i1.operandNumber);
                     Debug.log(i1.logString(this));
                     throw new JVMCIError("");
                 }
 
-                for (Range r = i1.first(); r != Range.EndMarker; r = r.next) {
-                    if (r.from >= r.to) {
-                        Debug.log("Interval %d has zero length range", i1.operandNumber);
-                        Debug.log(i1.logString(this));
-                        throw new JVMCIError("");
-                    }
+                if (i1.from() >= i1.to()) {
+                    Debug.log("Interval %d has zero length range", i1.operandNumber);
+                    Debug.log(i1.logString(this));
+                    throw new JVMCIError("");
                 }
 
+                // special intervals that are created in MoveResolver
+                // . ignore them because the range information has no meaning there
+                if (i1.from() == 1 && i1.to() == 2) {
+                    continue;
+                }
+                // check any intervals
                 for (int j = i + 1; j < len; j++) {
-                    TraceInterval i2 = intervals[j];
+                    final TraceInterval i2 = intervals[j];
                     if (i2 == null) {
                         continue;
                     }
 
                     // special intervals that are created in MoveResolver
                     // . ignore them because the range information has no meaning there
-                    if (i1.from() == 1 && i1.to() == 2) {
-                        continue;
-                    }
                     if (i2.from() == 1 && i2.to() == 2) {
                         continue;
                     }
                     Value l1 = i1.location();
                     Value l2 = i2.location();
-                    if (i1.intersects(i2) && !isIllegal(l1) && (l1.equals(l2))) {
+                    boolean intersects = i1.intersects(i2);
+                    if (intersects && !isIllegal(l1) && (l1.equals(l2))) {
                         if (DetailedAsserts.getValue()) {
-                            Debug.log("Intervals %d and %d overlap and have the same register assigned", i1.operandNumber, i2.operandNumber);
+                            Debug.log("Intervals %s and %s overlap and have the same register assigned", i1, i2);
+                            Debug.log(i1.logString(this));
+                            Debug.log(i2.logString(this));
+                        }
+                        throw new BailoutException("");
+                    }
+                }
+                // check fixed intervals
+                for (FixedInterval i2 : fixedIntervals) {
+                    if (i2 == null) {
+                        continue;
+                    }
+
+                    Value l1 = i1.location();
+                    Value l2 = i2.location();
+                    boolean intersects = i2.intersects(i1);
+                    if (intersects && !isIllegal(l1) && (l1.equals(l2))) {
+                        if (DetailedAsserts.getValue()) {
+                            Debug.log("Intervals %s and %s overlap and have the same register assigned", i1, i2);
                             Debug.log(i1.logString(this));
                             Debug.log(i2.logString(this));
                         }
@@ -809,12 +896,12 @@
     class CheckConsumer implements ValueConsumer {
 
         boolean ok;
-        TraceInterval curInterval;
+        FixedInterval curInterval;
 
         @Override
         public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) {
             if (isRegister(operand)) {
-                if (intervalFor(operand) == curInterval) {
+                if (fixedIntervalFor(asRegisterValue(operand)) == curInterval) {
                     ok = true;
                 }
             }
@@ -826,14 +913,13 @@
         try (Indent indent = Debug.logAndIndent("verifying that no oops are in fixed intervals *")) {
             CheckConsumer checkConsumer = new CheckConsumer();
 
-            TraceInterval fixedIntervals;
             TraceInterval otherIntervals;
-            fixedIntervals = createUnhandledLists(IS_PRECOLORED_INTERVAL, null).first;
+            FixedInterval fixedInts = createFixedUnhandledList();
             // to ensure a walking until the last instruction id, add a dummy interval
             // with a high operation id
             otherIntervals = new TraceInterval(Value.ILLEGAL, -1);
             otherIntervals.addRange(Integer.MAX_VALUE - 2, Integer.MAX_VALUE - 1);
-            TraceIntervalWalker iw = new TraceIntervalWalker(this, fixedIntervals, otherIntervals);
+            TraceIntervalWalker iw = new TraceIntervalWalker(this, fixedInts, otherIntervals);
 
             for (AbstractBlockBase<?> block : sortedBlocks) {
                 List<LIRInstruction> instructions = ir.getLIRforBlock(block);
@@ -850,8 +936,8 @@
                          * can't handle that correctly.
                          */
                         if (checkLive) {
-                            for (TraceInterval interval = iw.activeLists.get(RegisterBinding.Fixed); interval != TraceInterval.EndMarker; interval = interval.next) {
-                                if (interval.currentTo() > op.id() + 1) {
+                            for (FixedInterval interval = iw.activeFixedList.getFixed(); interval != FixedInterval.EndMarker; interval = interval.next) {
+                                if (interval.to() > op.id() + 1) {
                                     /*
                                      * This interval is live out of this op so make sure that this
                                      * interval represents some value that's referenced by this op
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanEliminateSpillMovePhase.java	Mon Sep 07 16:03:02 2015 +0200
@@ -83,8 +83,7 @@
              * collect all intervals that must be stored after their definition. The list is sorted
              * by Interval.spillDefinitionPos.
              */
-            TraceInterval interval;
-            interval = allocator.createUnhandledLists(mustStoreAtDefinition, null).first;
+            TraceInterval interval = allocator.createUnhandledList(mustStoreAtDefinition);
             if (DetailedAsserts.getValue()) {
                 checkIntervals(interval);
             }
@@ -183,16 +182,6 @@
     protected static boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) {
         // TODO (je) do not eliminate spill moves yet!
         return false;
-        /*
-         * assert isVariable(move.getResult()) : "LinearScan inserts only moves to variables: " +
-         * move;
-         *
-         * Interval curInterval = allocator.intervalFor(move.getResult());
-         *
-         * if (!isRegister(curInterval.location()) && curInterval.alwaysInMemory()) { assert
-         * isStackSlotValue(curInterval.location()) : "Not a stack slot: " + curInterval.location();
-         * return true; } return false;
-         */
     }
 
     private static void checkIntervals(TraceInterval interval) {
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanLifetimeAnalysisPhase.java	Mon Sep 07 16:03:02 2015 +0200
@@ -24,6 +24,7 @@
 
 import static com.oracle.graal.compiler.common.GraalOptions.*;
 import static com.oracle.graal.lir.LIRValueUtil.*;
+import static com.oracle.graal.lir.alloc.trace.TraceLinearScan.*;
 import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.Options.*;
 import static com.oracle.graal.lir.debug.LIRGenerationDebugContext.*;
 import static jdk.internal.jvmci.code.ValueUtil.*;
@@ -56,7 +57,7 @@
 import com.oracle.graal.lir.phases.*;
 import com.oracle.graal.lir.ssi.*;
 
-class TraceLinearScanLifetimeAnalysisPhase extends AllocationPhase {
+final class TraceLinearScanLifetimeAnalysisPhase extends AllocationPhase {
 
     protected final TraceLinearScan allocator;
     private final TraceBuilderResult<?> traceBuilderResult;
@@ -75,8 +76,6 @@
                     RegisterAllocationConfig registerAllocationConfig) {
         numberInstructions();
         allocator.printLir("Before register allocation", true);
-        computeLocalLiveSets();
-        computeGlobalLiveSets();
         buildIntervals();
     }
 
@@ -88,16 +87,16 @@
         return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock);
     }
 
-    static void setHint(final LIRInstruction op, TraceInterval target, TraceInterval source) {
-        TraceInterval currentHint = target.locationHint(false);
-        if (currentHint == null || currentHint.from() > target.from()) {
+    static void setHint(final LIRInstruction op, TraceInterval to, IntervalHint from) {
+        IntervalHint currentHint = to.locationHint(false);
+        if (currentHint == null) {
             /*
              * Update hint if there was none or if the hint interval starts after the hinted
              * interval.
              */
-            target.setLocationHint(source);
+            to.setLocationHint(from);
             if (Debug.isLogEnabled()) {
-                Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target);
+                Debug.log("operation at opId %d: added hint from interval %s to %s", op.id(), from, to);
             }
         }
     }
@@ -478,7 +477,7 @@
          * fixed intervals).
          */
         for (AbstractBlockBase<?> block : allocator.sortedBlocks()) {
-            for (int j = 0; j <= allocator.maxRegisterNumber(); j++) {
+            for (int j = 0; j < allocator.numRegisters(); j++) {
                 assert !allocator.getBlockData(block).liveIn.get(j) : "liveIn  set of fixed register must be empty";
                 assert !allocator.getBlockData(block).liveOut.get(j) : "liveOut set of fixed register must be empty";
                 assert !allocator.getBlockData(block).liveGen.get(j) : "liveGen set of fixed register must be empty";
@@ -490,8 +489,25 @@
         if (!allocator.isProcessed(operand)) {
             return;
         }
+        if (isRegister(operand)) {
+            addFixedUse(asRegisterValue(operand), from, to);
+        } else {
+            assert isVariable(operand) : operand;
+            addVariableUse(asVariable(operand), from, to, registerPriority, kind);
+        }
+    }
 
+    private void addFixedUse(RegisterValue reg, int from, int to) {
+        FixedInterval interval = allocator.getOrCreateFixedInterval(reg);
+        interval.addRange(from, to);
+        if (Debug.isLogEnabled()) {
+            Debug.log("add fixed use: %s, at %d", interval, to);
+        }
+    }
+
+    private void addVariableUse(Variable operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) {
         TraceInterval interval = allocator.getOrCreateInterval(operand);
+
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
@@ -502,7 +518,7 @@
         interval.addUsePos(to & ~1, registerPriority);
 
         if (Debug.isLogEnabled()) {
-            Debug.log("add use: %s, from %d to %d (%s)", interval, from, to, registerPriority.name());
+            Debug.log("add use: %s, at %d (%s)", interval, to, registerPriority.name());
         }
     }
 
@@ -510,13 +526,35 @@
         if (!allocator.isProcessed(operand)) {
             return;
         }
+        if (isRegister(operand)) {
+            addFixedTemp(asRegisterValue(operand), tempPos);
+        } else {
+            assert isVariable(operand) : operand;
+            addVariableTemp(asVariable(operand), tempPos, registerPriority, kind);
+        }
+    }
 
+    private void addFixedTemp(RegisterValue reg, int tempPos) {
+        FixedInterval interval = allocator.getOrCreateFixedInterval(reg);
+        interval.addRange(tempPos, tempPos + 1);
+        if (Debug.isLogEnabled()) {
+            Debug.log("add fixed temp: %s, at %d", interval, tempPos);
+        }
+    }
+
+    private void addVariableTemp(Variable operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) {
         TraceInterval interval = allocator.getOrCreateInterval(operand);
+
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
 
-        interval.addRange(tempPos, tempPos + 1);
+        if (interval.isEmpty()) {
+            interval.addRange(tempPos, tempPos + 1);
+        } else if (interval.from() > tempPos) {
+            interval.setFrom(tempPos);
+        }
+
         interval.addUsePos(tempPos, registerPriority);
         interval.addMaterializationValue(null);
 
@@ -529,23 +567,48 @@
         if (!allocator.isProcessed(operand)) {
             return;
         }
+        if (isRegister(operand)) {
+            addFixedDef(asRegisterValue(operand), op);
+        } else {
+            assert isVariable(operand) : operand;
+            addVariableDef(asVariable(operand), op, registerPriority, kind);
+        }
+    }
+
+    private void addFixedDef(RegisterValue reg, LIRInstruction op) {
+        FixedInterval interval = allocator.getOrCreateFixedInterval(reg);
+        int defPos = op.id();
+        if (interval.from() <= defPos) {
+            /*
+             * Update the starting point (when a range is first created for a use, its start is the
+             * beginning of the current block until a def is encountered).
+             */
+            interval.setFrom(defPos);
+
+        } else {
+            /*
+             * Dead value - make vacuous interval also add register priority for dead intervals
+             */
+            interval.addRange(defPos, defPos + 1);
+            if (Debug.isLogEnabled()) {
+                Debug.log("Warning: def of operand %s at %d occurs without use", reg, defPos);
+            }
+        }
+        if (Debug.isLogEnabled()) {
+            Debug.log("add fixed def: %s, at %d", interval, defPos);
+        }
+    }
+
+    private void addVariableDef(Variable operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) {
         int defPos = op.id();
 
         TraceInterval interval = allocator.getOrCreateInterval(operand);
+
         if (!kind.equals(LIRKind.Illegal)) {
             interval.setKind(kind);
         }
 
-        Range r = interval.first();
-        if (r.from <= defPos) {
-            /*
-             * Update the starting point (when a range is first created for a use, its start is the
-             * beginning of the current block until a def is encountered).
-             */
-            r.from = defPos;
-            interval.addUsePos(defPos, registerPriority);
-
-        } else {
+        if (interval.isEmpty()) {
             /*
              * Dead value - make vacuous interval also add register priority for dead intervals
              */
@@ -554,6 +617,13 @@
             if (Debug.isLogEnabled()) {
                 Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
             }
+        } else {
+            /*
+             * Update the starting point (when a range is first created for a use, its start is the
+             * beginning of the current block until a def is encountered).
+             */
+            interval.setFrom(defPos);
+            interval.addUsePos(defPos, registerPriority);
         }
 
         changeSpillDefinitionPos(op, operand, interval, defPos);
@@ -587,17 +657,27 @@
 
             op.forEachRegisterHint(targetValue, mode, (registerHint, valueMode, valueFlags) -> {
                 if (TraceLinearScan.isVariableOrRegister(registerHint)) {
-                    TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) registerHint);
-                    TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) targetValue);
-
+                    AllocatableValue fromValue;
+                    AllocatableValue toValue;
                     /* hints always point from def to use */
                     if (hintAtDef) {
-                        to.setLocationHint(from);
+                        fromValue = (AllocatableValue) registerHint;
+                        toValue = (AllocatableValue) targetValue;
                     } else {
-                        from.setLocationHint(to);
+                        fromValue = (AllocatableValue) targetValue;
+                        toValue = (AllocatableValue) registerHint;
+                    }
+                    if (isRegister(toValue)) {
+                        /* fixed register: no need for a hint */
+                        return null;
                     }
+
+                    TraceInterval to = allocator.getOrCreateInterval(toValue);
+                    IntervalHint from = getIntervalHint(fromValue);
+
+                    to.setLocationHint(from);
                     if (Debug.isLogEnabled()) {
-                        Debug.log("operation at opId %d: added hint from interval %d to %d", op.id(), from.operandNumber, to.operandNumber);
+                        Debug.log("operation at opId %d: added hint from interval %s to %s", op.id(), from, to);
                     }
 
                     return registerHint;
@@ -607,6 +687,13 @@
         }
     }
 
+    private IntervalHint getIntervalHint(AllocatableValue from) {
+        if (isRegister(from)) {
+            return allocator.getOrCreateFixedInterval(asRegisterValue(from));
+        }
+        return allocator.getOrCreateInterval(from);
+    }
+
     /**
      * Eliminates moves from register to stack if the stack slot is known to be correct.
      *
@@ -657,7 +744,7 @@
     /**
      * Determines the register priority for an instruction's output/result operand.
      */
-    protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
+    protected static RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) {
         if (op instanceof LabelOp) {
             // skip method header
             return RegisterPriority.None;
@@ -718,8 +805,8 @@
             InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
                 if (TraceLinearScan.isVariableOrRegister(operand)) {
                     int opId = op.id();
+                    RegisterPriority p = registerPriorityOfInputOperand(flags);
                     int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
-                    RegisterPriority p = registerPriorityOfInputOperand(flags);
                     addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind());
                     addRegisterHint(op, operand, mode, flags, false);
                 }
@@ -740,35 +827,12 @@
             for (int i = allocator.blockCount() - 1; i >= 0; i--) {
 
                 AbstractBlockBase<?> block = allocator.blockAt(i);
+                // TODO (je) make empty bitset - remove
+                allocator.getBlockData(block).liveIn = new BitSet();
+                allocator.getBlockData(block).liveOut = new BitSet();
                 try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
 
                     List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
-                    final int blockFrom = allocator.getFirstLirInstructionId(block);
-                    int blockTo = allocator.getLastLirInstructionId(block);
-
-                    assert blockFrom == instructions.get(0).id();
-                    assert blockTo == instructions.get(instructions.size() - 1).id();
-
-                    // Update intervals for operands live at the end of this block;
-                    BitSet live = allocator.getBlockData(block).liveOut;
-                    for (int operandNum = live.nextSetBit(0); operandNum >= 0; operandNum = live.nextSetBit(operandNum + 1)) {
-                        assert live.get(operandNum) : "should not stop here otherwise";
-                        AllocatableValue operand = allocator.intervalFor(operandNum).operand;
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("live in %d: %s", operandNum, operand);
-                        }
-
-                        addUse(operand, blockFrom, blockTo + 2, RegisterPriority.None, LIRKind.Illegal);
-
-                        /*
-                         * Add special use positions for loop-end blocks when the interval is used
-                         * anywhere inside this loop. It's possible that the block was part of a
-                         * non-natural loop, so it might have an invalid loop index.
-                         */
-                        if (block.isLoopEnd() && block.getLoop() != null && isIntervalInLoop(operandNum, block.getLoop().getIndex())) {
-                            allocator.intervalFor(operandNum).addUsePos(blockTo + 1, RegisterPriority.LiveAtLoopEnd);
-                        }
-                    }
 
                     /*
                      * Iterate all instructions of the block in reverse order. definitions of
@@ -813,31 +877,29 @@
 
                     } // end of instruction iteration
                 }
+                allocator.printIntervals("After Block " + block);
             } // end of block iteration
 
-            /*
-             * Add the range [0, 1] to all fixed intervals. the register allocator need not handle
-             * unhandled fixed intervals.
-             */
+            // fix spill state for phi/sigma intervals
             for (TraceInterval interval : allocator.intervals()) {
-                if (interval != null && isRegister(interval.operand)) {
-                    interval.addRange(0, 1);
+                if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) {
+                    // there was a definition in a phi/sigma
+                    interval.setSpillState(SpillState.NoSpillStore);
                 }
             }
-        }
-        postBuildIntervals();
-    }
-
-    protected void postBuildIntervals() {
-        // fix spill state for phi/sigma 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);
+            if (TraceRAuseInterTraceHints.getValue()) {
+                addInterTraceHints();
             }
-        }
-        if (TraceRAuseInterTraceHints.getValue()) {
-            addInterTraceHints();
+            /*
+             * Add the range [-1, 0] to all fixed intervals. the register allocator need not handle
+             * unhandled fixed intervals.
+             */
+            for (FixedInterval interval : allocator.fixedIntervals()) {
+                if (interval != null) {
+                    /* We use [-1, 0] to avoid intersection with incoming values. */
+                    interval.addRange(-1, 0);
+                }
+            }
         }
     }
 
@@ -851,17 +913,17 @@
                     BlockEndOp outgoing = SSIUtil.outgoing(lir, pred);
                     for (int i = 0; i < outgoing.getOutgoingSize(); i++) {
                         Value toValue = label.getIncomingValue(i);
-                        if (!isIllegal(toValue)) {
+                        if (!isIllegal(toValue) && !isRegister(toValue)) {
                             Value fromValue = outgoing.getOutgoingValue(i);
                             assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue;
 
-                            if (isRegister(fromValue) || isVariable(fromValue)) {
-                                TraceInterval from = allocator.getOrCreateInterval((AllocatableValue) fromValue);
+                            if (isVariableOrRegister(fromValue)) {
+                                IntervalHint from = getIntervalHint((AllocatableValue) fromValue);
                                 TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
                                 setHint(label, to, from);
                             } else if (TraceRAshareSpillInformation.getValue() && TraceUtil.isShadowedRegisterValue(fromValue)) {
                                 ShadowedRegisterValue shadowedRegisterValue = TraceUtil.asShadowedRegisterValue(fromValue);
-                                TraceInterval from = allocator.getOrCreateInterval(shadowedRegisterValue.getRegister());
+                                IntervalHint from = getIntervalHint(shadowedRegisterValue.getRegister());
                                 TraceInterval to = allocator.getOrCreateInterval((AllocatableValue) toValue);
                                 setHint(label, to, from);
                                 to.setSpillSlot(shadowedRegisterValue.getStackSlot());
@@ -872,21 +934,6 @@
                 }
             }
         }
-        /*
-         * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming
-         * values.
-         */
-        for (TraceInterval interval : allocator.intervals()) {
-            if (interval != null && isRegister(interval.operand)) {
-                Range range = interval.first();
-                if (range == Range.EndMarker) {
-                    interval.addRange(-1, 0);
-                } else if (range.from == 0 && range.to == 1) {
-                    range.from = -1;
-                    range.to = 0;
-                }
-            }
-        }
     }
 
     /**
@@ -909,7 +956,7 @@
                  * degradation, because rematerialization always inserts a constant load, even if
                  * the value is not needed in a register.
                  */
-                TraceInterval.UsePosList usePosList = interval.usePosList();
+                UsePosList usePosList = interval.usePosList();
                 int numUsePos = usePosList.size();
                 for (int useIdx = 0; useIdx < numUsePos; useIdx++) {
                     TraceInterval.RegisterPriority priority = usePosList.registerPriority(useIdx);
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanOptimizeSpillPositionPhase.java	Thu Sep 03 19:01:59 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,234 +0,0 @@
-/*
- * Copyright (c) 2015, 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.cfg.AbstractControlFlowGraph.*;
-import static jdk.internal.jvmci.code.ValueUtil.*;
-
-import java.util.*;
-
-import jdk.internal.jvmci.code.*;
-import com.oracle.graal.debug.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.alloc.*;
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.LIRInstruction.OperandMode;
-import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState;
-import com.oracle.graal.lir.gen.*;
-import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
-import com.oracle.graal.lir.phases.*;
-
-final class TraceLinearScanOptimizeSpillPositionPhase extends AllocationPhase {
-
-    private static final DebugMetric betterSpillPos = Debug.metric("BetterSpillPosition");
-    private static final DebugMetric betterSpillPosWithLowerProbability = Debug.metric("BetterSpillPositionWithLowerProbability");
-
-    private final TraceLinearScan allocator;
-
-    TraceLinearScanOptimizeSpillPositionPhase(TraceLinearScan allocator) {
-        this.allocator = allocator;
-    }
-
-    @Override
-    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
-                    RegisterAllocationConfig registerAllocationConfig) {
-        optimizeSpillPosition();
-        allocator.printIntervals("After optimize spill position");
-    }
-
-    @SuppressWarnings("try")
-    private void optimizeSpillPosition() {
-        try (Indent indent0 = Debug.logAndIndent("OptimizeSpillPositions")) {
-            LIRInsertionBuffer[] insertionBuffers = new LIRInsertionBuffer[allocator.getLIR().linearScanOrder().size()];
-            for (TraceInterval interval : allocator.intervals()) {
-                optimizeInterval(insertionBuffers, interval);
-            }
-            for (LIRInsertionBuffer insertionBuffer : insertionBuffers) {
-                if (insertionBuffer != null) {
-                    assert insertionBuffer.initialized() : "Insertion buffer is nonnull but not initialized!";
-                    insertionBuffer.finish();
-                }
-            }
-        }
-    }
-
-    @SuppressWarnings("try")
-    private void optimizeInterval(LIRInsertionBuffer[] insertionBuffers, TraceInterval interval) {
-        if (interval == null || !interval.isSplitParent() || interval.spillState() != SpillState.SpillInDominator) {
-            return;
-        }
-        AbstractBlockBase<?> defBlock = allocator.blockForId(interval.spillDefinitionPos());
-        AbstractBlockBase<?> spillBlock = null;
-        TraceInterval firstSpillChild = null;
-        try (Indent indent = Debug.logAndIndent("interval %s (%s)", interval, defBlock)) {
-            for (TraceInterval splitChild : interval.getSplitChildren()) {
-                if (isStackSlotValue(splitChild.location())) {
-                    if (firstSpillChild == null || splitChild.from() < firstSpillChild.from()) {
-                        firstSpillChild = splitChild;
-                    } else {
-                        assert firstSpillChild.from() < splitChild.from();
-                    }
-                    // iterate all blocks where the interval has use positions
-                    for (AbstractBlockBase<?> splitBlock : blocksForInterval(splitChild)) {
-                        if (dominates(defBlock, splitBlock)) {
-                            Debug.log("Split interval %s, block %s", splitChild, splitBlock);
-                            if (spillBlock == null) {
-                                spillBlock = splitBlock;
-                            } else {
-                                spillBlock = commonDominator(spillBlock, splitBlock);
-                                assert spillBlock != null;
-                            }
-                        }
-                    }
-                }
-            }
-            if (spillBlock == null) {
-                Debug.log("not spill interval found");
-                // no spill interval
-                interval.setSpillState(SpillState.StoreAtDefinition);
-                return;
-            }
-            Debug.log(3, "Spill block candidate (initial): %s", spillBlock);
-            // move out of loops
-            if (defBlock.getLoopDepth() < spillBlock.getLoopDepth()) {
-                spillBlock = moveSpillOutOfLoop(defBlock, spillBlock);
-            }
-            Debug.log(3, "Spill block candidate (after loop optimizaton): %s", spillBlock);
-
-            /*
-             * The spill block is the begin of the first split child (aka the value is on the
-             * stack).
-             *
-             * The problem is that if spill block has more than one predecessor, the values at the
-             * end of the predecessors might differ. Therefore, we would need a spill move in all
-             * predecessors. To avoid this we spill in the dominator.
-             */
-            assert firstSpillChild != null;
-            if (!defBlock.equals(spillBlock) && spillBlock.equals(allocator.blockForId(firstSpillChild.from()))) {
-                AbstractBlockBase<?> dom = spillBlock.getDominator();
-                if (Debug.isLogEnabled()) {
-                    Debug.log("Spill block (%s) is the beginning of a spill child -> use dominator (%s)", spillBlock, dom);
-                }
-                spillBlock = dom;
-            }
-            if (defBlock.equals(spillBlock)) {
-                Debug.log(3, "Definition is the best choice: %s", defBlock);
-                // definition is the best choice
-                interval.setSpillState(SpillState.StoreAtDefinition);
-                return;
-            }
-            assert dominates(defBlock, spillBlock);
-            betterSpillPos.increment();
-            if (Debug.isLogEnabled()) {
-                Debug.log("Better spill position found (Block %s)", spillBlock);
-            }
-
-            if (defBlock.probability() <= spillBlock.probability()) {
-                Debug.log(3, "Definition has lower probability %s (%f) is lower than spill block %s (%f)", defBlock, defBlock.probability(), spillBlock, spillBlock.probability());
-                // better spill block has the same probability -> do nothing
-                interval.setSpillState(SpillState.StoreAtDefinition);
-                return;
-            }
-
-            LIRInsertionBuffer insertionBuffer = insertionBuffers[spillBlock.getId()];
-            if (insertionBuffer == null) {
-                insertionBuffer = new LIRInsertionBuffer();
-                insertionBuffers[spillBlock.getId()] = insertionBuffer;
-                insertionBuffer.init(allocator.getLIR().getLIRforBlock(spillBlock));
-            }
-            int spillOpId = allocator.getFirstLirInstructionId(spillBlock);
-            // insert spill move
-            AllocatableValue fromLocation = interval.getSplitChildAtOpId(spillOpId, OperandMode.DEF, allocator).location();
-            AllocatableValue toLocation = TraceLinearScan.canonicalSpillOpr(interval);
-            LIRInstruction move = allocator.getSpillMoveFactory().createMove(toLocation, fromLocation);
-            Debug.log(3, "Insert spill move %s", move);
-            move.setId(TraceLinearScan.DOMINATOR_SPILL_MOVE_ID);
-            /*
-             * We can use the insertion buffer directly because we always insert at position 1.
-             */
-            insertionBuffer.append(1, move);
-
-            betterSpillPosWithLowerProbability.increment();
-            interval.setSpillDefinitionPos(spillOpId);
-        }
-    }
-
-    /**
-     * Iterate over all {@link AbstractBlockBase blocks} of an interval.
-     */
-    private class IntervalBlockIterator implements Iterator<AbstractBlockBase<?>> {
-
-        Range range;
-        AbstractBlockBase<?> block;
-
-        public IntervalBlockIterator(TraceInterval interval) {
-            range = interval.first();
-            block = allocator.blockForId(range.from);
-        }
-
-        public AbstractBlockBase<?> next() {
-            AbstractBlockBase<?> currentBlock = block;
-            int nextBlockIndex = block.getLinearScanNumber() + 1;
-            if (nextBlockIndex < allocator.sortedBlocks().size()) {
-                block = allocator.sortedBlocks().get(nextBlockIndex);
-                if (range.to <= allocator.getFirstLirInstructionId(block)) {
-                    range = range.next;
-                    if (range == Range.EndMarker) {
-                        block = null;
-                    } else {
-                        block = allocator.blockForId(range.from);
-                    }
-                }
-            } else {
-                block = null;
-            }
-            return currentBlock;
-        }
-
-        public boolean hasNext() {
-            return block != null;
-        }
-    }
-
-    private Iterable<AbstractBlockBase<?>> blocksForInterval(TraceInterval interval) {
-        return new Iterable<AbstractBlockBase<?>>() {
-            public Iterator<AbstractBlockBase<?>> iterator() {
-                return new IntervalBlockIterator(interval);
-            }
-        };
-    }
-
-    private static AbstractBlockBase<?> moveSpillOutOfLoop(AbstractBlockBase<?> defBlock, AbstractBlockBase<?> spillBlock) {
-        int defLoopDepth = defBlock.getLoopDepth();
-        for (AbstractBlockBase<?> block = spillBlock.getDominator(); !defBlock.equals(block); block = block.getDominator()) {
-            assert block != null : "spill block not dominated by definition block?";
-            if (block.getLoopDepth() <= defLoopDepth) {
-                assert block.getLoopDepth() == defLoopDepth : "Cannot spill an interval outside of the loop where it is defined!";
-                return block;
-            }
-        }
-        return defBlock;
-    }
-}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanRegisterAllocationPhase.java	Mon Sep 07 16:03:02 2015 +0200
@@ -25,8 +25,8 @@
 import java.util.*;
 
 import jdk.internal.jvmci.code.*;
+
 import com.oracle.graal.debug.*;
-
 import com.oracle.graal.compiler.common.alloc.*;
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.lir.gen.*;
@@ -52,12 +52,8 @@
     @SuppressWarnings("try")
     void allocateRegisters() {
         try (Indent indent = Debug.logAndIndent("allocate registers")) {
-            TraceInterval precoloredIntervals;
-            TraceInterval notPrecoloredIntervals;
-
-            TraceInterval.Pair result = allocator.createUnhandledLists(TraceLinearScan.IS_PRECOLORED_INTERVAL, TraceLinearScan.IS_VARIABLE_INTERVAL);
-            precoloredIntervals = result.first;
-            notPrecoloredIntervals = result.second;
+            FixedInterval precoloredIntervals = allocator.createFixedUnhandledList();
+            TraceInterval notPrecoloredIntervals = allocator.createUnhandledList(TraceLinearScan.IS_VARIABLE_INTERVAL);
 
             // allocate cpu registers
             TraceLinearScanWalker lsw = new TraceLinearScanWalker(allocator, precoloredIntervals, notPrecoloredIntervals);
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanWalker.java	Mon Sep 07 16:03:02 2015 +0200
@@ -29,6 +29,7 @@
 import java.util.*;
 
 import jdk.internal.jvmci.code.*;
+import jdk.internal.jvmci.common.*;
 import jdk.internal.jvmci.meta.*;
 
 import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig.AllocatableRegisters;
@@ -38,7 +39,6 @@
 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.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;
@@ -47,12 +47,12 @@
  */
 final class TraceLinearScanWalker extends TraceIntervalWalker {
 
-    protected Register[] availableRegs;
+    private Register[] availableRegs;
 
-    protected final int[] usePos;
-    protected final int[] blockPos;
+    private final int[] usePos;
+    private final int[] blockPos;
 
-    protected List<TraceInterval>[] spillIntervals;
+    private List<TraceInterval>[] spillIntervals;
 
     private TraceLocalMoveResolver moveResolver; // for ordering spill moves
 
@@ -69,19 +69,20 @@
     private static final List<TraceInterval> EMPTY_LIST = new ArrayList<>(0);
 
     // accessors mapped to same functions in class LinearScan
-    int blockCount() {
+    private int blockCount() {
         return allocator.blockCount();
     }
 
-    AbstractBlockBase<?> blockAt(int idx) {
+    private AbstractBlockBase<?> blockAt(int idx) {
         return allocator.blockAt(idx);
     }
 
-    AbstractBlockBase<?> blockOfOpWithId(int opId) {
+    @SuppressWarnings("unused")
+    private AbstractBlockBase<?> blockOfOpWithId(int opId) {
         return allocator.blockForId(opId);
     }
 
-    TraceLinearScanWalker(TraceLinearScan allocator, TraceInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
+    TraceLinearScanWalker(TraceLinearScan allocator, FixedInterval unhandledFixedFirst, TraceInterval unhandledAnyFirst) {
         super(allocator, unhandledFixedFirst, unhandledAnyFirst);
 
         moveResolver = allocator.createMoveResolver();
@@ -93,7 +94,7 @@
         blockPos = new int[allocator.getRegisters().length];
     }
 
-    void initUseLists(boolean onlyProcessUsePos) {
+    private void initUseLists(boolean onlyProcessUsePos) {
         for (Register register : availableRegs) {
             int i = register.number;
             usePos[i] = Integer.MAX_VALUE;
@@ -105,19 +106,19 @@
         }
     }
 
-    int maxRegisterNumber() {
+    private int maxRegisterNumber() {
         return maxReg;
     }
 
-    int minRegisterNumber() {
+    private int minRegisterNumber() {
         return minReg;
     }
 
-    boolean isRegisterInRange(int reg) {
+    private boolean isRegisterInRange(int reg) {
         return reg >= minRegisterNumber() && reg <= maxRegisterNumber();
     }
 
-    void excludeFromUse(TraceInterval i) {
+    private void excludeFromUse(IntervalHint i) {
         Value location = i.location();
         int i1 = asRegister(location).number;
         if (isRegisterInRange(i1)) {
@@ -125,7 +126,7 @@
         }
     }
 
-    void setUsePos(TraceInterval interval, int usePos, boolean onlyProcessUsePos) {
+    private 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;
@@ -145,7 +146,20 @@
         }
     }
 
-    void setBlockPos(TraceInterval i, int blockPos) {
+    private void setUsePos(FixedInterval interval, int usePos, boolean onlyProcessUsePos) {
+        assert onlyProcessUsePos;
+        if (usePos != -1) {
+            assert usePos != 0 : "must use excludeFromUse to set usePos to 0";
+            int i = asRegister(interval.location()).number;
+            if (isRegisterInRange(i)) {
+                if (this.usePos[i] > usePos) {
+                    this.usePos[i] = usePos;
+                }
+            }
+        }
+    }
+
+    private void setBlockPos(IntervalHint i, int blockPos) {
         if (blockPos != -1) {
             int reg = asRegister(i.location()).number;
             if (isRegisterInRange(reg)) {
@@ -159,8 +173,17 @@
         }
     }
 
-    void freeExcludeActiveFixed() {
-        TraceInterval interval = activeLists.get(RegisterBinding.Fixed);
+    private void freeExcludeActiveFixed() {
+        FixedInterval interval = activeFixedList.getFixed();
+        while (interval != FixedInterval.EndMarker) {
+            assert isRegister(interval.location()) : "active interval must have a register assigned";
+            excludeFromUse(interval);
+            interval = interval.next;
+        }
+    }
+
+    private void freeExcludeActiveAny() {
+        TraceInterval interval = activeAnyList.getAny();
         while (interval != TraceInterval.EndMarker) {
             assert isRegister(interval.location()) : "active interval must have a register assigned";
             excludeFromUse(interval);
@@ -168,21 +191,12 @@
         }
     }
 
-    void freeExcludeActiveAny() {
-        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(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);
+    private void freeCollectInactiveFixed(TraceInterval current) {
+        FixedInterval interval = inactiveFixedList.getFixed();
+        while (interval != FixedInterval.EndMarker) {
+            if (current.to() <= interval.from()) {
+                assert interval.intersectsAt(current) == -1 : "must not intersect";
+                setUsePos(interval, interval.from(), true);
             } else {
                 setUsePos(interval, interval.currentIntersectsAt(current), true);
             }
@@ -190,44 +204,17 @@
         }
     }
 
-    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, 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);
-            }
-            interval = interval.next;
-        }
-    }
-
-    void spillExcludeActiveFixed() {
-        TraceInterval interval = activeLists.get(RegisterBinding.Fixed);
-        while (interval != TraceInterval.EndMarker) {
+    private void spillExcludeActiveFixed() {
+        FixedInterval interval = activeFixedList.getFixed();
+        while (interval != FixedInterval.EndMarker) {
             excludeFromUse(interval);
             interval = interval.next;
         }
     }
 
-    void spillBlockUnhandledFixed(TraceInterval current) {
-        TraceInterval interval = unhandledLists.get(RegisterBinding.Fixed);
-        while (interval != TraceInterval.EndMarker) {
-            setBlockPos(interval, interval.intersectsAt(current));
-            interval = interval.next;
-        }
-    }
-
-    void spillBlockInactiveFixed(TraceInterval current) {
-        TraceInterval interval = inactiveLists.get(RegisterBinding.Fixed);
-        while (interval != TraceInterval.EndMarker) {
+    private void spillBlockInactiveFixed(TraceInterval current) {
+        FixedInterval interval = inactiveFixedList.getFixed();
+        while (interval != FixedInterval.EndMarker) {
             if (current.to() > interval.currentFrom()) {
                 setBlockPos(interval, interval.currentIntersectsAt(current));
             } else {
@@ -238,25 +225,15 @@
         }
     }
 
-    void spillCollectActiveAny(RegisterPriority registerPriority) {
-        TraceInterval interval = activeLists.get(RegisterBinding.Any);
+    private void spillCollectActiveAny(RegisterPriority registerPriority) {
+        TraceInterval interval = activeAnyList.getAny();
         while (interval != TraceInterval.EndMarker) {
             setUsePos(interval, Math.min(interval.nextUsage(registerPriority, currentPosition), interval.to()), false);
             interval = interval.next;
         }
     }
 
-    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);
-            }
-            interval = interval.next;
-        }
-    }
-
-    void insertMove(int operandId, TraceInterval srcIt, TraceInterval dstIt) {
+    private 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
 
@@ -285,7 +262,8 @@
         moveResolver.addMapping(srcIt, dstIt);
     }
 
-    int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
+    @SuppressWarnings("unused")
+    private int findOptimalSplitPos(AbstractBlockBase<?> minBlock, AbstractBlockBase<?> maxBlock, int maxSplitPos) {
         int fromBlockNr = minBlock.getLinearScanNumber();
         int toBlockNr = maxBlock.getLinearScanNumber();
 
@@ -315,108 +293,13 @@
         return optimalSplitPos;
     }
 
-    int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
-        int optimalSplitPos = -1;
-        if (minSplitPos == maxSplitPos) {
-            // trivial case, no optimization of split position possible
-            if (Debug.isLogEnabled()) {
-                Debug.log("min-pos and max-pos are equal, no optimization possible");
-            }
-            optimalSplitPos = minSplitPos;
-
-        } else {
-            assert minSplitPos < maxSplitPos : "must be true then";
-            assert minSplitPos > 0 : "cannot access minSplitPos - 1 otherwise";
-
-            // reason for using minSplitPos - 1: when the minimal split pos is exactly at the
-            // beginning of a block, then minSplitPos is also a possible split position.
-            // Use the block before as minBlock, because then minBlock.lastLirInstructionId() + 2 ==
-            // minSplitPos
-            AbstractBlockBase<?> minBlock = allocator.blockForId(minSplitPos - 1);
-
-            // reason for using maxSplitPos - 1: otherwise there would be an assert on failure
-            // when an interval ends at the end of the last block of the method
-            // (in this case, maxSplitPos == allocator().maxLirOpId() + 2, and there is no
-            // block at this opId)
-            AbstractBlockBase<?> maxBlock = allocator.blockForId(maxSplitPos - 1);
-
-            assert minBlock.getLinearScanNumber() <= maxBlock.getLinearScanNumber() : "invalid order";
-            if (minBlock == maxBlock) {
-                // split position cannot be moved to block boundary : so split as late as possible
-                if (Debug.isLogEnabled()) {
-                    Debug.log("cannot move split pos to block boundary because minPos and maxPos are in same block");
-                }
-                optimalSplitPos = maxSplitPos;
-
-            } else {
-                if (interval.hasHoleBetween(maxSplitPos - 1, maxSplitPos) && !allocator.isBlockBegin(maxSplitPos)) {
-                    // Do not move split position if the interval has a hole before maxSplitPos.
-                    // Intervals resulting from Phi-Functions have more than one definition (marked
-                    // as mustHaveRegister) with a hole before each definition. When the register is
-                    // needed
-                    // for the second definition : an earlier reloading is unnecessary.
-                    if (Debug.isLogEnabled()) {
-                        Debug.log("interval has hole just before maxSplitPos, so splitting at maxSplitPos");
-                    }
-                    optimalSplitPos = maxSplitPos;
-
-                } else {
-                    // seach optimal block boundary between minSplitPos and maxSplitPos
-                    if (Debug.isLogEnabled()) {
-                        Debug.log("moving split pos to optimal block boundary between block B%d and B%d", minBlock.getId(), maxBlock.getId());
-                    }
-
-                    if (doLoopOptimization) {
-                        // Loop optimization: if a loop-end marker is found between min- and
-                        // max-position :
-                        // then split before this loop
-                        int loopEndPos = interval.nextUsageExact(RegisterPriority.LiveAtLoopEnd, allocator.getLastLirInstructionId(minBlock) + 2);
-                        if (Debug.isLogEnabled()) {
-                            Debug.log("loop optimization: loop end found at pos %d", loopEndPos);
-                        }
-
-                        assert loopEndPos > minSplitPos : "invalid order";
-                        if (loopEndPos < maxSplitPos) {
-                            // loop-end marker found between min- and max-position
-                            // if it is not the end marker for the same loop as the min-position :
-                            // then move
-                            // the max-position to this loop block.
-                            // Desired result: uses tagged as shouldHaveRegister inside a loop cause
-                            // a reloading
-                            // of the interval (normally, only mustHaveRegister causes a reloading)
-                            AbstractBlockBase<?> loopBlock = allocator.blockForId(loopEndPos);
-
-                            if (Debug.isLogEnabled()) {
-                                Debug.log("interval is used in loop that ends in block B%d, so trying to move maxBlock back from B%d to B%d", loopBlock.getId(), maxBlock.getId(), loopBlock.getId());
-                            }
-                            assert loopBlock != minBlock : "loopBlock and minBlock must be different because block boundary is needed between";
-
-                            int maxSpillPos = allocator.getLastLirInstructionId(loopBlock) + 2;
-                            optimalSplitPos = findOptimalSplitPos(minBlock, loopBlock, maxSpillPos);
-                            if (optimalSplitPos == maxSpillPos) {
-                                optimalSplitPos = -1;
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("loop optimization not necessary");
-                                }
-                            } else {
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("loop optimization successful");
-                                }
-                            }
-                        }
-                    }
-
-                    if (optimalSplitPos == -1) {
-                        // not calculated by loop optimization
-                        optimalSplitPos = findOptimalSplitPos(minBlock, maxBlock, maxSplitPos);
-                    }
-                }
-            }
-        }
+    @SuppressWarnings({"static-method", "unused"})
+    private int findOptimalSplitPos(TraceInterval interval, int minSplitPos, int maxSplitPos, boolean doLoopOptimization) {
+        // TODO (je) implement
+        int optimalSplitPos = maxSplitPos;
         if (Debug.isLogEnabled()) {
             Debug.log("optimal split position: %d", optimalSplitPos);
         }
-
         return optimalSplitPos;
     }
 
@@ -425,7 +308,7 @@
     // 1) the left part has already a location assigned
     // 2) the right part is sorted into to the unhandled-list
     @SuppressWarnings("try")
-    void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
+    private void splitBeforeUsage(TraceInterval interval, int minSplitPos, int maxSplitPos) {
 
         try (Indent indent = Debug.logAndIndent("splitting interval %s between %d and %d", interval, minSplitPos, maxSplitPos)) {
 
@@ -451,9 +334,10 @@
 
             // must calculate this before the actual split is performed and before split position is
             // moved to odd opId
-            boolean moveNecessary = !allocator.isBlockBegin(optimalSplitPos) && !interval.hasHoleBetween(optimalSplitPos - 1, optimalSplitPos);
+            boolean isBlockBegin = allocator.isBlockBegin(optimalSplitPos);
+            boolean moveNecessary = !isBlockBegin;
 
-            if (!allocator.isBlockBegin(optimalSplitPos)) {
+            if (!isBlockBegin) {
                 // move position before actual instruction (odd opId)
                 optimalSplitPos = (optimalSplitPos - 1) | 1;
             }
@@ -462,15 +346,15 @@
                 Debug.log("splitting at position %d", optimalSplitPos);
             }
 
-            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";
+            assert isBlockBegin || ((optimalSplitPos & 1) == 1) : "split pos must be odd when not on block boundary";
+            assert !isBlockBegin || ((optimalSplitPos & 1) == 0) : "split pos must be even on block boundary";
 
             TraceInterval splitPart = interval.split(optimalSplitPos, allocator);
 
             splitPart.setInsertMoveWhenActivated(moveNecessary);
 
             assert splitPart.from() >= currentPosition : "cannot append new interval before current walk position";
-            unhandledLists.addToListSortedByStartAndUsePositions(RegisterBinding.Any, splitPart);
+            unhandledAnyList.addToListSortedByStartAndUsePositions(splitPart);
 
             if (Debug.isLogEnabled()) {
                 Debug.log("left interval  %s: %s", moveNecessary ? "      " : "", interval.logString(allocator));
@@ -484,7 +368,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
     @SuppressWarnings("try")
-    void splitForSpilling(TraceInterval interval) {
+    private void splitForSpilling(TraceInterval interval) {
         // calculate allowed range of splitting position
         int maxSplitPos = currentPosition;
         int previousUsage = interval.previousUsage(RegisterPriority.ShouldHaveRegister, maxSplitPos);
@@ -640,24 +524,24 @@
     /**
      * This is called for every interval that is assigned to a stack slot.
      */
-    protected static void handleSpillSlot(TraceInterval interval) {
+    private 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(TraceInterval interval) {
+    private void splitStackInterval(TraceInterval interval) {
         int minSplitPos = currentPosition + 1;
         int maxSplitPos = Math.min(interval.firstUsage(RegisterPriority.ShouldHaveRegister), interval.to());
 
         splitBeforeUsage(interval, minSplitPos, maxSplitPos);
     }
 
-    void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
+    private void splitWhenPartialRegisterAvailable(TraceInterval interval, int registerAvailableUntil) {
         int minSplitPos = Math.max(interval.previousUsage(RegisterPriority.ShouldHaveRegister, registerAvailableUntil), interval.from() + 1);
         splitBeforeUsage(interval, minSplitPos, registerAvailableUntil);
     }
 
-    void splitAndSpillInterval(TraceInterval interval) {
+    private void splitAndSpillInterval(TraceInterval interval) {
         assert interval.state == State.Active || interval.state == State.Inactive : "other states not allowed";
 
         int currentPos = currentPosition;
@@ -665,8 +549,7 @@
             // the interval is currently inactive, so no spill slot is needed for now.
             // when the split part is activated, the interval has a new chance to get a register,
             // so in the best case no stack slot is necessary
-            assert interval.hasHoleBetween(currentPos - 1, currentPos + 1) : "interval can not be inactive otherwise";
-            splitBeforeUsage(interval, currentPos + 1, currentPos + 1);
+            throw JVMCIError.shouldNotReachHere("TraceIntervals can not be inactive!");
 
         } else {
             // search the position where the interval must have a register and split
@@ -684,16 +567,14 @@
     }
 
     @SuppressWarnings("try")
-    boolean allocFreeRegister(TraceInterval interval) {
+    private boolean allocFreeRegister(TraceInterval interval) {
         try (Indent indent = Debug.logAndIndent("trying to find free register for %s", interval)) {
 
             initUseLists(true);
             freeExcludeActiveFixed();
+            freeCollectInactiveFixed(interval);
             freeExcludeActiveAny();
-            freeCollectInactiveFixed(interval);
-            freeCollectInactiveAny(interval);
             // freeCollectUnhandled(fixedKind, cur);
-            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)
@@ -704,17 +585,17 @@
                 try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
                     for (Register register : availableRegs) {
                         int i = register.number;
-                        Debug.log("reg %d: usePos: %d", register.number, usePos[i]);
+                        Debug.log("reg %d (%s): usePos: %d", register.number, register, usePos[i]);
                     }
                 }
             }
 
             Register hint = null;
-            TraceInterval locationHint = interval.locationHint(true);
+            IntervalHint locationHint = interval.locationHint(true);
             if (locationHint != null && locationHint.location() != null && isRegister(locationHint.location())) {
                 hint = asRegister(locationHint.location());
                 if (Debug.isLogEnabled()) {
-                    Debug.log("hint register %d from interval %s", hint.number, locationHint);
+                    Debug.log("hint register %3d (%4s) from interval %s", hint.number, hint, locationHint);
                 }
             }
             assert interval.location() == null : "register already assigned to interval";
@@ -757,7 +638,7 @@
             splitPos = usePos[reg.number];
             interval.assignLocation(reg.asValue(interval.kind()));
             if (Debug.isLogEnabled()) {
-                Debug.log("selected register %d", reg.number);
+                Debug.log("selected register %d (%s)", reg.number, reg);
             }
 
             assert splitPos > 0 : "invalid splitPos";
@@ -770,7 +651,7 @@
         }
     }
 
-    void splitAndSpillIntersectingIntervals(Register reg) {
+    private void splitAndSpillIntersectingIntervals(Register reg) {
         assert reg != null : "no register assigned";
 
         for (int i = 0; i < spillIntervals[reg.number].size(); i++) {
@@ -782,7 +663,7 @@
 
     // Split an Interval and spill it to memory so that cur can be placed in a register
     @SuppressWarnings("try")
-    void allocLockedRegister(TraceInterval interval) {
+    private 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
@@ -805,10 +686,8 @@
                 initUseLists(false);
                 spillExcludeActiveFixed();
                 // spillBlockUnhandledFixed(cur);
-                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);
                 if (Debug.isLogEnabled()) {
                     printRegisterState();
                 }
@@ -884,7 +763,7 @@
     }
 
     @SuppressWarnings("try")
-    void printRegisterState() {
+    private void printRegisterState() {
         try (Indent indent2 = Debug.logAndIndent("state of registers:")) {
             for (Register reg : availableRegs) {
                 int i = reg.number;
@@ -897,7 +776,7 @@
         }
     }
 
-    boolean noAllocationPossible(TraceInterval interval) {
+    private 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
@@ -914,7 +793,8 @@
                     }
 
                     // safety check that there is really no register available
-                    assert !allocFreeRegister(interval) : "found a register for this interval";
+                    // TODO (je): fix
+                    // assert !allocFreeRegister(interval) : "found a register for this interval";
                     return true;
                 }
             }
@@ -922,14 +802,14 @@
         return false;
     }
 
-    void initVarsForAlloc(TraceInterval interval) {
+    private 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, TraceInterval from, TraceInterval to) {
+    private static boolean isMove(LIRInstruction op, TraceInterval from, TraceInterval to) {
         if (op instanceof ValueMoveOp) {
             ValueMoveOp move = (ValueMoveOp) op;
             if (isVariable(move.getInput()) && isVariable(move.getResult())) {
@@ -941,17 +821,17 @@
 
     // optimization (especially for phi functions of nested loops):
     // assign same spill slot to non-intersecting intervals
-    void combineSpilledIntervals(TraceInterval interval) {
+    private void combineSpilledIntervals(TraceInterval interval) {
         if (interval.isSplitChild()) {
             // optimization is only suitable for split parents
             return;
         }
 
-        TraceInterval registerHint = interval.locationHint(false);
-        if (registerHint == null) {
-            // cur is not the target of a move : otherwise registerHint would be set
+        IntervalHint locationHint = interval.locationHint(false);
+        if (locationHint == null || !(locationHint instanceof TraceInterval)) {
             return;
         }
+        TraceInterval registerHint = (TraceInterval) locationHint;
         assert registerHint.isSplitParent() : "register hint must be split parent";
 
         if (interval.spillState() != SpillState.NoOptimization || registerHint.spillState() != SpillState.NoOptimization) {
@@ -1002,6 +882,9 @@
     @Override
     @SuppressWarnings("try")
     protected boolean activateCurrent(TraceInterval interval) {
+        if (Debug.isLogEnabled()) {
+            logCurrentStatus();
+        }
         boolean result = true;
 
         try (Indent indent = Debug.logAndIndent("activating interval %s,  splitParent: %d", interval, interval.splitParent().operandNumber)) {
@@ -1060,7 +943,7 @@
         return result; // true = interval is moved to active list
     }
 
-    public void finishAllocation() {
+    void finishAllocation() {
         // must be called when all intervals are allocated
         moveResolver.resolveAndAppendMoves();
     }
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceSimpleLifetimeAnalysisPhase.java	Thu Sep 03 19:01:59 2015 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,282 +0,0 @@
-/*
- * Copyright (c) 2015, 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 jdk.internal.jvmci.code.ValueUtil.*;
-
-import java.util.*;
-
-import jdk.internal.jvmci.code.*;
-import jdk.internal.jvmci.meta.*;
-
-import com.oracle.graal.compiler.common.alloc.*;
-import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.lir.*;
-import com.oracle.graal.lir.alloc.trace.TraceInterval.RegisterPriority;
-import com.oracle.graal.lir.alloc.trace.TraceInterval.SpillState;
-import com.oracle.graal.lir.gen.*;
-import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
-
-final class TraceSimpleLifetimeAnalysisPhase extends TraceLinearScanLifetimeAnalysisPhase {
-
-    public TraceSimpleLifetimeAnalysisPhase(TraceLinearScan allocator, TraceBuilderResult<?> traceBuilderResult) {
-        super(allocator, traceBuilderResult);
-    }
-
-    @Override
-    protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory,
-                    RegisterAllocationConfig registerAllocationConfig) {
-        numberInstructions();
-        allocator.printLir("Before register allocation", true);
-        buildIntervals();
-    }
-
-    @Override
-    protected void addUse(AllocatableValue operand, int from, int to, RegisterPriority registerPriority, LIRKind kind) {
-        if (!allocator.isProcessed(operand)) {
-            return;
-        }
-        if (isRegister(operand)) {
-            super.addUse(operand, from, to, registerPriority, kind);
-            return;
-        }
-
-        TraceInterval interval = allocator.getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        Range r = interval.first();
-        if (r == Range.EndMarker) {
-            interval.addRange(from, to);
-        } else if (r.from > from) {
-            r.from = from;
-        }
-
-        // Register use position at even instruction id.
-        interval.addUsePos(to & ~1, registerPriority);
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add use: %s, at %d (%s)", interval, to, registerPriority.name());
-        }
-    }
-
-    @Override
-    protected void addTemp(AllocatableValue operand, int tempPos, RegisterPriority registerPriority, LIRKind kind) {
-        if (!allocator.isProcessed(operand)) {
-            return;
-        }
-        if (isRegister(operand)) {
-            super.addTemp(operand, tempPos, registerPriority, kind);
-            return;
-        }
-
-        TraceInterval interval = allocator.getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        Range r = interval.first();
-        if (r == Range.EndMarker) {
-            interval.addRange(tempPos, tempPos + 1);
-        } else if (r.from > tempPos) {
-            r.from = tempPos;
-        }
-        interval.addUsePos(tempPos, registerPriority);
-        interval.addMaterializationValue(null);
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add temp: %s tempPos %d (%s)", interval, tempPos, RegisterPriority.MustHaveRegister.name());
-        }
-    }
-
-    @Override
-    protected void addDef(AllocatableValue operand, LIRInstruction op, RegisterPriority registerPriority, LIRKind kind) {
-        if (!allocator.isProcessed(operand)) {
-            return;
-        }
-        if (isRegister(operand)) {
-            super.addDef(operand, op, registerPriority, kind);
-            return;
-        }
-        int defPos = op.id();
-
-        TraceInterval interval = allocator.getOrCreateInterval(operand);
-        if (!kind.equals(LIRKind.Illegal)) {
-            interval.setKind(kind);
-        }
-
-        Range r = interval.first();
-        if (r == Range.EndMarker) {
-            /*
-             * Dead value - make vacuous interval also add register priority for dead intervals
-             */
-            interval.addRange(defPos, defPos + 1);
-            interval.addUsePos(defPos, registerPriority);
-            if (Debug.isLogEnabled()) {
-                Debug.log("Warning: def of operand %s at %d occurs without use", operand, defPos);
-            }
-        } else {
-            /*
-             * Update the starting point (when a range is first created for a use, its start is the
-             * beginning of the current block until a def is encountered).
-             */
-            r.from = defPos;
-            interval.addUsePos(defPos, registerPriority);
-
-        }
-
-        changeSpillDefinitionPos(op, operand, interval, defPos);
-        if (registerPriority == RegisterPriority.None && interval.spillState().ordinal() <= SpillState.StartInMemory.ordinal() && isStackSlot(operand)) {
-            // detection of method-parameters and roundfp-results
-            interval.setSpillState(SpillState.StartInMemory);
-        }
-        interval.addMaterializationValue(getMaterializedValue(op, operand, interval));
-
-        if (Debug.isLogEnabled()) {
-            Debug.log("add def: %s defPos %d (%s)", interval, defPos, registerPriority.name());
-        }
-    }
-
-    @Override
-    @SuppressWarnings("try")
-    protected void buildIntervals() {
-
-        try (Indent indent = Debug.logAndIndent("build intervals")) {
-            InstructionValueConsumer outputConsumer = (op, operand, mode, flags) -> {
-                if (TraceLinearScan.isVariableOrRegister(operand)) {
-                    addDef((AllocatableValue) operand, op, registerPriorityOfOutputOperand(op), operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, true);
-                }
-            };
-
-            InstructionValueConsumer tempConsumer = (op, operand, mode, flags) -> {
-                if (TraceLinearScan.isVariableOrRegister(operand)) {
-                    addTemp((AllocatableValue) operand, op.id(), RegisterPriority.MustHaveRegister, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer aliveConsumer = (op, operand, mode, flags) -> {
-                if (TraceLinearScan.isVariableOrRegister(operand)) {
-                    RegisterPriority p = registerPriorityOfInputOperand(flags);
-                    int opId = op.id();
-                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
-                    addUse((AllocatableValue) operand, blockFrom, opId + 1, p, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer inputConsumer = (op, operand, mode, flags) -> {
-                if (TraceLinearScan.isVariableOrRegister(operand)) {
-                    int opId = op.id();
-                    RegisterPriority p = registerPriorityOfInputOperand(flags);
-                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
-                    addUse((AllocatableValue) operand, blockFrom, opId, p, operand.getLIRKind());
-                    addRegisterHint(op, operand, mode, flags, false);
-                }
-            };
-
-            InstructionValueConsumer stateProc = (op, operand, mode, flags) -> {
-                if (TraceLinearScan.isVariableOrRegister(operand)) {
-                    int opId = op.id();
-                    int blockFrom = allocator.getFirstLirInstructionId((allocator.blockForId(opId)));
-                    addUse((AllocatableValue) operand, blockFrom, opId + 1, RegisterPriority.None, operand.getLIRKind());
-                }
-            };
-
-            // create a list with all caller-save registers (cpu, fpu, xmm)
-            Register[] callerSaveRegs = allocator.getRegisterAllocationConfig().getRegisterConfig().getCallerSaveRegisters();
-
-            // iterate all blocks in reverse order
-            for (int i = allocator.blockCount() - 1; i >= 0; i--) {
-
-                AbstractBlockBase<?> block = allocator.blockAt(i);
-                // TODO (je) make empty bitset - remove
-                allocator.getBlockData(block).liveIn = new BitSet();
-                allocator.getBlockData(block).liveOut = new BitSet();
-                try (Indent indent2 = Debug.logAndIndent("handle block %d", block.getId())) {
-
-                    List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block);
-
-                    /*
-                     * Iterate all instructions of the block in reverse order. definitions of
-                     * intervals are processed before uses.
-                     */
-                    for (int j = instructions.size() - 1; j >= 0; j--) {
-                        final LIRInstruction op = instructions.get(j);
-                        final int opId = op.id();
-
-                        try (Indent indent3 = Debug.logAndIndent("handle inst %d: %s", opId, op)) {
-
-                            // add a temp range for each register if operation destroys
-                            // caller-save registers
-                            if (op.destroysCallerSavedRegisters()) {
-                                for (Register r : callerSaveRegs) {
-                                    if (allocator.attributes(r).isAllocatable()) {
-                                        addTemp(r.asValue(), opId, RegisterPriority.None, LIRKind.Illegal);
-                                    }
-                                }
-                                if (Debug.isLogEnabled()) {
-                                    Debug.log("operation destroys all caller-save registers");
-                                }
-                            }
-
-                            op.visitEachOutput(outputConsumer);
-                            op.visitEachTemp(tempConsumer);
-                            op.visitEachAlive(aliveConsumer);
-                            op.visitEachInput(inputConsumer);
-
-                            /*
-                             * Add uses of live locals from interpreter's point of view for proper
-                             * debug information generation. Treat these operands as temp values (if
-                             * the live range is extended to a call site, the value would be in a
-                             * register at the call otherwise).
-                             */
-                            op.visitEachState(stateProc);
-
-                            // special steps for some instructions (especially moves)
-                            handleMethodArguments(op);
-
-                        }
-
-                    } // end of instruction iteration
-                }
-                allocator.printIntervals("After Block " + block);
-            } // end of block iteration
-
-            /*
-             * Add the range [0, 1] to all fixed intervals. the register allocator need not handle
-             * unhandled fixed intervals.
-             */
-            for (TraceInterval interval : allocator.intervals()) {
-                if (interval != null && isRegister(interval.operand)) {
-                    interval.addRange(0, 1);
-                }
-            }
-        }
-        postBuildIntervals();
-    }
-}
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java	Thu Sep 03 19:01:59 2015 +0200
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceTrivialAllocator.java	Mon Sep 07 16:03:02 2015 +0200
@@ -22,30 +22,34 @@
  */
 package com.oracle.graal.lir.alloc.trace;
 
-import static com.oracle.graal.lir.LIRValueUtil.*;
-import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.*;
-
-import java.util.*;
+import static com.oracle.graal.lir.LIRValueUtil.asVariable;
+import static com.oracle.graal.lir.LIRValueUtil.isVariable;
+import static com.oracle.graal.lir.alloc.trace.TraceRegisterAllocationPhase.isTrivialTrace;
 
-import jdk.internal.jvmci.code.*;
-import jdk.internal.jvmci.meta.*;
+import java.util.List;
 
-import com.oracle.graal.compiler.common.alloc.*;
+import jdk.internal.jvmci.code.TargetDescription;
+import jdk.internal.jvmci.meta.Value;
+
+import com.oracle.graal.compiler.common.alloc.RegisterAllocationConfig;
 import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult;
-import com.oracle.graal.compiler.common.cfg.*;
-import com.oracle.graal.lir.*;
+import com.oracle.graal.compiler.common.cfg.AbstractBlockBase;
+import com.oracle.graal.lir.LIR;
+import com.oracle.graal.lir.LIRInstruction;
 import com.oracle.graal.lir.LIRInstruction.OperandFlag;
-import com.oracle.graal.lir.StandardOp.BlockEndOp;
+import com.oracle.graal.lir.StandardOp.JumpOp;
 import com.oracle.graal.lir.StandardOp.LabelOp;
-import com.oracle.graal.lir.gen.*;
+import com.oracle.graal.lir.ValueProcedure;
+import com.oracle.graal.lir.Variable;
+import com.oracle.graal.lir.gen.LIRGenerationResult;
 import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory;
-import com.oracle.graal.lir.phases.*;
-import com.oracle.graal.lir.ssi.*;
-import com.oracle.graal.lir.util.*;
+import com.oracle.graal.lir.phases.AllocationPhase;
+import com.oracle.graal.lir.ssi.SSIUtil;
+import com.oracle.graal.lir.util.VariableVirtualStackValueMap;
 
 /**
  * Allocates a trivial trace i.e. a trace consisting of a single block with no instructions other
- * than the {@link LabelOp} and the {@link BlockEndOp}.
+ * than the {@link LabelOp} and the {@link JumpOp}.
  */
 final class TraceTrivialAllocator extends AllocationPhase {
 
diff -r b887efbf86e3 -r c8faebfb7aed graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/UsePosList.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/UsePosList.java	Mon Sep 07 16:03:02 2015 +0200
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2015, 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 com.oracle.graal.compiler.common.util.*;
+import com.oracle.graal.lir.alloc.trace.TraceInterval.*;
+
+/**
+ * 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 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();
+    }
+}