*** old/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/Interval.java	Mon Mar 20 17:39:46 2017
--- new/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/lsra/Interval.java	Mon Mar 20 17:39:46 2017

*** 40,50 ****
--- 40,49 ----
  import org.graalvm.compiler.core.common.util.IntList;
  import org.graalvm.compiler.core.common.util.Util;
  import org.graalvm.compiler.debug.GraalError;
  import org.graalvm.compiler.lir.LIRInstruction;
  import org.graalvm.compiler.lir.Variable;
  
  import jdk.vm.ci.code.RegisterValue;
  import jdk.vm.ci.code.StackSlot;
  import jdk.vm.ci.meta.AllocatableValue;
  import jdk.vm.ci.meta.Constant;
  import jdk.vm.ci.meta.Value;

*** 54,77 ****
--- 53,62 ----
   * Represents an interval in the {@linkplain LinearScan linear scan register allocator}.
   */
  public final class Interval {
  
      /**
       * A pair of intervals.
       */
      static final class Pair {
  
          public final Interval first;
          public final Interval second;
  
          Pair(Interval first, Interval second) {
              this.first = first;
              this.second = second;
          }
      }
  
      /**
       * A set of interval lists, one per {@linkplain RegisterBinding binding} type.
       */
      static final class RegisterBindingLists {
  
          /**

*** 194,204 ****
--- 179,189 ----
          public void remove(RegisterBinding binding, Interval i) {
              Interval list = get(binding);
              Interval prev = null;
              Interval cur = list;
              while (cur != i) {
!                 assert cur != null && cur != Interval.EndMarker : "interval has not been found in list: " + i;
!                 assert cur != null && !cur.isEndMarker() : "interval has not been found in list: " + i;
                  prev = cur;
                  cur = cur.next;
              }
              if (prev == null) {
                  set(binding, cur.next);

*** 446,455 ****
--- 431,442 ----
              }
              return buf.append("]").toString();
          }
      }
  
+     protected static final int END_MARKER_OPERAND_NUMBER = Integer.MIN_VALUE;
+ 
      /**
       * The {@linkplain RegisterValue register} or {@linkplain Variable variable} for this interval
       * prior to register allocation.
       */
      public final AllocatableValue operand;

*** 491,501 ****
--- 478,489 ----
       * 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}.
+      * LinearScan.intervalEndMarker.
       */
      Interval next;
  
      /**
       * The linear-scan state of this interval.

*** 569,578 ****
--- 557,571 ----
              assert newLocation.getValueKind().equals(this.kind);
          }
          this.location = newLocation;
      }
  
+     /** Returns true is this is the sentinel interval that denotes the end of an interval list. */
+     public boolean isEndMarker() {
+         return operandNumber == END_MARKER_OPERAND_NUMBER;
+     }
+ 
      /**
       * Gets the {@linkplain RegisterValue register} or {@linkplain StackSlot spill slot} assigned to
       * this interval.
       */
      public AllocatableValue location() {

*** 699,709 ****
--- 692,702 ----
      void rewindRange() {
          current = first;
      }
  
      void nextRange() {
!         assert this != EndMarker : "not allowed on sentinel";
!         assert !this.isEndMarker() : "not allowed on sentinel";
          current = current.next;
      }
  
      int currentFrom() {
          return current.from;

*** 712,751 ****
--- 705,739 ----
      int currentTo() {
          return current.to;
      }
  
      boolean currentAtEnd() {
!         return current == Range.EndMarker;
!         return current.isEndMarker();
      }
  
      boolean currentIntersects(Interval it) {
          return current.intersects(it.current);
      }
  
      int currentIntersectsAt(Interval it) {
          return current.intersectsAt(it.current);
      }
  
      /**
       * Sentinel interval to denote the end of an interval list.
       */
      static final Interval EndMarker = new Interval(Value.ILLEGAL, -1);
  
      Interval(AllocatableValue operand, int operandNumber) {
+     Interval(AllocatableValue operand, int operandNumber, Interval intervalEndMarker, Range rangeEndMarker) {
          assert operand != null;
          this.operand = operand;
          this.operandNumber = operandNumber;
          if (isRegister(operand)) {
              location = operand;
          } else {
              assert isIllegal(operand) || isVariable(operand);
          }
          this.kind = LIRKind.Illegal;
!         this.first = Range.EndMarker;
!         this.first = rangeEndMarker;
          this.usePosList = new UsePosList(4);
!         this.current = Range.EndMarker;
!         this.next = EndMarker;
!         this.current = rangeEndMarker;
!         this.next = intervalEndMarker;
          this.cachedTo = -1;
          this.spillState = SpillState.NoDefinitionFound;
          this.spillDefinitionPos = -1;
          splitParent = this;
          currentSplitChild = this;

*** 778,791 ****
--- 766,779 ----
      public Constant getMaterializedValue() {
          return splitParent().materializedValue;
      }
  
      int calcTo() {
!         assert first != Range.EndMarker : "interval has no range";
!         assert !first.isEndMarker() : "interval has no range";
  
          Range r = first;
!         while (r.next != Range.EndMarker) {
!         while (!r.next.isEndMarker()) {
              r = r.next;
          }
          return r.to;
      }
  

*** 1041,1056 ****
--- 1029,1044 ----
              }
          }
          return prev;
      }
  
!     public void addUsePos(int pos, RegisterPriority registerPriority, boolean detailedAsserts) {
          assert covers(pos, LIRInstruction.OperandMode.USE) : String.format("use position %d not covered by live range of interval %s", pos, this);
  
          // do not add use positions for precolored intervals because they are never used
          if (registerPriority != RegisterPriority.None && isVariable(operand)) {
!             if (DetailedAsserts.getValue()) {
!             if (detailedAsserts) {
                  for (int i = 0; i < usePosList.size(); i++) {
                      assert pos <= usePosList.usePos(i) : "already added a use-position with lower position";
                      if (i > 0) {
                          assert usePosList.usePos(i) < usePosList.usePos(i - 1) : "not sorted descending";
                      }

*** 1069,1083 ****
--- 1057,1071 ----
          }
      }
  
      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 first().isEndMarker() || 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;
!             assert !first.isEndMarker();
              // join intersecting ranges
              first.from = Math.min(from, first().from);
              first.to = Math.max(to, first().to);
          } else {
              // insert new range

*** 1128,1160 ****
--- 1116,1148 ----
          Interval result = newSplitChild(allocator);
  
          // split the ranges
          Range prev = null;
          Range cur = first;
!         while (cur != Range.EndMarker && cur.to <= splitPos) {
!         while (!cur.isEndMarker() && cur.to <= splitPos) {
              prev = cur;
              cur = cur.next;
          }
!         assert cur != Range.EndMarker : "split interval after end of last range";
!         assert !cur.isEndMarker() : "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;
!             cur.next = allocator.rangeEndMarker;
  
          } else {
              assert prev != null : "split before start of first range";
              result.first = cur;
!             prev.next = Range.EndMarker;
!             prev.next = allocator.rangeEndMarker;
          }
          result.current = result.first;
          cachedTo = -1; // clear cached value
  
          // split list of use positions
          result.usePosList = usePosList.splitAt(splitPos);
  
!         if (DetailedAsserts.getValue(allocator.getOptions())) {
              for (int i = 0; i < usePosList.size(); i++) {
                  assert usePosList.usePos(i) < splitPos;
              }
              for (int i = 0; i < result.usePosList.size(); i++) {
                  assert result.usePosList.usePos(i) >= splitPos;

*** 1182,1192 ****
--- 1170,1180 ----
          // 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";
!             assert !first.next.isEndMarker() : "must not be at end";
              first = first.next;
          } else {
              first.from = splitPos;
          }
  

*** 1195,1208 ****
--- 1183,1196 ----
  
      // 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) {
!         while (!cur.isEndMarker() && cur.to < opId) {
              cur = cur.next;
          }
!         if (cur != Range.EndMarker) {
!         if (!cur.isEndMarker()) {
              assert cur.to != cur.next.from : "ranges not separated";
  
              if (mode == LIRInstruction.OperandMode.DEF) {
                  return cur.from <= opId && opId < cur.to;
              } else {

*** 1217,1227 ****
--- 1205,1215 ----
      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) {
!         while (!cur.isEndMarker()) {
              assert cur.to < cur.next.from : "no space between ranges";
  
              // hole-range starts before this range . hole
              if (holeFrom < cur.from) {
                  return true;

*** 1247,1257 ****
--- 1235,1245 ----
  
      @Override
      public String toString() {
          String from = "?";
          String to = "?";
!         if (first != null && first != Range.EndMarker) {
!         if (first != null && !first.isEndMarker()) {
              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());
          }

*** 1287,1297 ****
--- 1275,1285 ----
          }
          buf.append("} ranges{");
  
          // print ranges
          Range cur = first;
!         while (cur != Range.EndMarker) {
!         while (!cur.isEndMarker()) {
              if (cur != first) {
                  buf.append(", ");
              }
              buf.append(cur);
              cur = cur.next;