src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/alloc/trace/lsra/TraceInterval.java

*** 20,37 ****
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  package org.graalvm.compiler.lir.alloc.trace.lsra;
  
- import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
- import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
- import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
- import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
  import static jdk.vm.ci.code.ValueUtil.asRegister;
  import static jdk.vm.ci.code.ValueUtil.isIllegal;
  import static jdk.vm.ci.code.ValueUtil.isRegister;
  import static jdk.vm.ci.code.ValueUtil.isStackSlot;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.EnumSet;
--- 20,37 ----
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  package org.graalvm.compiler.lir.alloc.trace.lsra;
  
  import static jdk.vm.ci.code.ValueUtil.asRegister;
  import static jdk.vm.ci.code.ValueUtil.isIllegal;
  import static jdk.vm.ci.code.ValueUtil.isRegister;
  import static jdk.vm.ci.code.ValueUtil.isStackSlot;
+ import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts;
+ import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
+ import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
+ import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.EnumSet;
*** 41,50 ****
--- 41,51 ----
  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 org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan;
+ import org.graalvm.compiler.options.OptionValues;
  
  import jdk.vm.ci.code.RegisterValue;
  import jdk.vm.ci.code.StackSlot;
  import jdk.vm.ci.meta.AllocatableValue;
  import jdk.vm.ci.meta.JavaConstant;
*** 337,347 ****
  
      /**
       * List of all intervals that are split off from this interval. This is only used if this is a
       * {@linkplain #isSplitParent() split parent}.
       */
!     private List<TraceInterval> splitChildren = Collections.emptyList();
  
      /**
       * Current split child that has been active or inactive last (always stored in split parents).
       */
      private TraceInterval currentSplitChild;
--- 338,348 ----
  
      /**
       * List of all intervals that are split off from this interval. This is only used if this is a
       * {@linkplain #isSplitParent() split parent}.
       */
!     private ArrayList<TraceInterval> splitChildren = null;
  
      /**
       * Current split child that has been active or inactive last (always stored in split parents).
       */
      private TraceInterval currentSplitChild;
*** 376,385 ****
--- 377,393 ----
      /**
       * The number of times {@link #addMaterializationValue(JavaConstant)} is called.
       */
      private int numMaterializationValuesAdded;
  
+     private final OptionValues options;
+ 
+     private boolean splitChildrenEmpty() {
+         assert splitChildren == null || !splitChildren.isEmpty();
+         return splitChildren == null;
+     }
+ 
      void assignLocation(AllocatableValue newLocation) {
          if (isRegister(newLocation)) {
              assert this.location == null : "cannot re-assign location for " + this;
              if (newLocation.getValueKind().equals(LIRKind.Illegal) && !kind().equals(LIRKind.Illegal)) {
                  this.location = asRegister(newLocation).asValue(kind());
*** 438,447 ****
--- 446,459 ----
  
      public void setLocationHint(IntervalHint interval) {
          locationHint = interval;
      }
  
+     public boolean hasHint() {
+         return locationHint != null;
+     }
+ 
      public boolean isSplitParent() {
          return splitParent == this;
      }
  
      boolean isSplitChild() {
*** 539,554 ****
      }
  
      /**
       * Sentinel interval to denote the end of an interval list.
       */
!     static final TraceInterval EndMarker = new TraceInterval(Value.ILLEGAL, -1);
  
!     TraceInterval(AllocatableValue operand, int operandNumber) {
          assert operand != null;
          this.operand = operand;
          this.operandNumber = operandNumber;
          if (isRegister(operand)) {
              location = operand;
          } else {
              assert isIllegal(operand) || isVariable(operand);
          }
--- 551,567 ----
      }
  
      /**
       * Sentinel interval to denote the end of an interval list.
       */
!     static final TraceInterval EndMarker = new TraceInterval(Value.ILLEGAL, -1, null);
  
!     TraceInterval(AllocatableValue operand, int operandNumber, OptionValues options) {
          assert operand != null;
          this.operand = operand;
          this.operandNumber = operandNumber;
+         this.options = options;
          if (isRegister(operand)) {
              location = operand;
          } else {
              assert isIllegal(operand) || isVariable(operand);
          }
*** 590,600 ****
          return splitParent().materializedValue;
      }
  
      // consistency check of split-children
      boolean checkSplitChildren() {
!         if (!splitChildren.isEmpty()) {
              assert isSplitParent() : "only split parents can have children";
  
              for (int i = 0; i < splitChildren.size(); i++) {
                  TraceInterval i1 = splitChildren.get(i);
  
--- 603,613 ----
          return splitParent().materializedValue;
      }
  
      // consistency check of split-children
      boolean checkSplitChildren() {
!         if (!splitChildrenEmpty()) {
              assert isSplitParent() : "only split parents can have children";
  
              for (int i = 0; i < splitChildren.size(); i++) {
                  TraceInterval i1 = splitChildren.get(i);
  
*** 630,640 ****
  
              if (locationHint.location() != null && isRegister(locationHint.location())) {
                  return locationHint;
              } 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)) {
--- 643,653 ----
  
              if (locationHint.location() != null && isRegister(locationHint.location())) {
                  return locationHint;
              } else if (locationHint instanceof TraceInterval) {
                  TraceInterval hint = (TraceInterval) locationHint;
!                 if (!hint.splitChildrenEmpty()) {
                      // 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)) {
*** 647,661 ****
  
          // no hint interval found that has a register assigned
          return null;
      }
  
      TraceInterval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode) {
          assert isSplitParent() : "can only be called for split parents";
          assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
  
!         if (splitChildren.isEmpty()) {
              assert this.covers(opId, mode) : this + " does not cover " + opId;
              return this;
          } else {
              TraceInterval result = null;
              int len = splitChildren.size();
--- 660,689 ----
  
          // no hint interval found that has a register assigned
          return null;
      }
  
+     TraceInterval getSplitChildAtOpIdOrNull(int opId, LIRInstruction.OperandMode mode) {
+         /*
+          * TODO(je) could be replace by a simple range check by caching `to` in the split parent
+          * when creating split children.
+          */
+         return getSplitChildAtOpIdIntern(opId, mode, true);
+     }
+ 
      TraceInterval getSplitChildAtOpId(int opId, LIRInstruction.OperandMode mode) {
+         return getSplitChildAtOpIdIntern(opId, mode, false);
+     }
+ 
+     private TraceInterval getSplitChildAtOpIdIntern(int opId, LIRInstruction.OperandMode mode, boolean returnNull) {
          assert isSplitParent() : "can only be called for split parents";
          assert opId >= 0 : "invalid opId (method cannot be called for spill moves)";
  
!         if (splitChildrenEmpty()) {
!             if (returnNull) {
!                 return covers(opId, mode) ? this : null;
!             }
              assert this.covers(opId, mode) : this + " does not cover " + opId;
              return this;
          } else {
              TraceInterval result = null;
              int len = splitChildren.size();
*** 678,705 ****
                      result = cur;
                      break;
                  }
              }
  
!             assert checkSplitChild(result, opId, toOffset, mode);
              return result;
          }
      }
  
      private boolean checkSplitChild(TraceInterval result, int opId, int toOffset, LIRInstruction.OperandMode mode) {
          if (result == null) {
              // this is an error
              StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
!             if (!splitChildren.isEmpty()) {
                  TraceInterval firstChild = splitChildren.get(0);
                  TraceInterval lastChild = splitChildren.get(splitChildren.size() - 1);
                  msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
              }
              throw new GraalError("Linear Scan Error: %s", msg);
          }
  
!         if (!splitChildren.isEmpty()) {
              for (TraceInterval interval : splitChildren) {
                  if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
                      /*
                       * Should not happen: Try another compilation as it is very unlikely to happen
                       * again.
--- 706,733 ----
                      result = cur;
                      break;
                  }
              }
  
!             assert returnNull || checkSplitChild(result, opId, toOffset, mode);
              return result;
          }
      }
  
      private boolean checkSplitChild(TraceInterval result, int opId, int toOffset, LIRInstruction.OperandMode mode) {
          if (result == null) {
              // this is an error
              StringBuilder msg = new StringBuilder(this.toString()).append(" has no child at ").append(opId);
!             if (!splitChildrenEmpty()) {
                  TraceInterval firstChild = splitChildren.get(0);
                  TraceInterval lastChild = splitChildren.get(splitChildren.size() - 1);
                  msg.append(" (first = ").append(firstChild).append(", last = ").append(lastChild).append(")");
              }
              throw new GraalError("Linear Scan Error: %s", msg);
          }
  
!         if (!splitChildrenEmpty()) {
              for (TraceInterval interval : splitChildren) {
                  if (interval != result && interval.from() <= opId && opId < interval.to() + toOffset) {
                      /*
                       * Should not happen: Try another compilation as it is very unlikely to happen
                       * again.
*** 723,733 ****
          }
  
          TraceInterval parent = splitParent();
          TraceInterval result = null;
  
!         assert !parent.splitChildren.isEmpty() : "no split children available";
          int len = parent.splitChildren.size();
  
          for (int i = len - 1; i >= 0; i--) {
              TraceInterval cur = parent.splitChildren.get(i);
              if (cur.from() <= opId && opId < cur.to()) {
--- 751,761 ----
          }
  
          TraceInterval parent = splitParent();
          TraceInterval result = null;
  
!         assert !parent.splitChildrenEmpty() : "no split children available";
          int len = parent.splitChildren.size();
  
          for (int i = len - 1; i >= 0; i--) {
              TraceInterval cur = parent.splitChildren.get(i);
              if (cur.from() <= opId && opId < cur.to()) {
*** 744,754 ****
          assert opId >= 0 : "invalid opId";
  
          TraceInterval parent = splitParent();
          TraceInterval result = null;
  
!         assert !parent.splitChildren.isEmpty() : "no split children available";
          int len = parent.splitChildren.size();
  
          for (int i = len - 1; i >= 0; i--) {
              TraceInterval cur = parent.splitChildren.get(i);
              if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
--- 772,782 ----
          assert opId >= 0 : "invalid opId";
  
          TraceInterval parent = splitParent();
          TraceInterval result = null;
  
!         assert !parent.splitChildrenEmpty() : "no split children available";
          int len = parent.splitChildren.size();
  
          for (int i = len - 1; i >= 0; i--) {
              TraceInterval cur = parent.splitChildren.get(i);
              if (cur.to() <= opId && (result == null || result.to() < cur.to())) {
*** 763,773 ****
      // checks if opId is covered by any split child
      boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) {
          assert isSplitParent() : "can only be called for split parents";
          assert opId >= 0 : "invalid opId (method can not be called for spill moves)";
  
!         if (splitChildren.isEmpty()) {
              // simple case if interval was not split
              return covers(opId, mode);
  
          } else {
              // extended case: check all split children
--- 791,801 ----
      // checks if opId is covered by any split child
      boolean splitChildCovers(int opId, LIRInstruction.OperandMode mode) {
          assert isSplitParent() : "can only be called for split parents";
          assert opId >= 0 : "invalid opId (method can not be called for spill moves)";
  
!         if (splitChildrenEmpty()) {
              // simple case if interval was not split
              return covers(opId, mode);
  
          } else {
              // extended case: check all split children
*** 850,860 ****
      public void addUsePos(int pos, RegisterPriority registerPriority) {
          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)) {
!             if (DetailedAsserts.getValue()) {
                  for (int i = 0; i < numUsePos(); i++) {
                      assert pos <= getUsePos(i) : "already added a use-position with lower position";
                      if (i > 0) {
                          assert getUsePos(i) < getUsePos(i - 1) : "not sorted descending";
                      }
--- 878,888 ----
      public void addUsePos(int pos, RegisterPriority registerPriority) {
          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)) {
!             if (DetailedAsserts.getValue(options)) {
                  for (int i = 0; i < numUsePos(); i++) {
                      assert pos <= getUsePos(i) : "already added a use-position with lower position";
                      if (i > 0) {
                          assert getUsePos(i) < getUsePos(i - 1) : "not sorted descending";
                      }
*** 891,901 ****
  
          result.splitParent = parent;
          result.setLocationHint(parent);
  
          // insert new interval in children-list of parent
!         if (parent.splitChildren.isEmpty()) {
              assert isSplitParent() : "list must be initialized at first split";
  
              // Create new non-shared list
              parent.splitChildren = new ArrayList<>(4);
              parent.splitChildren.add(this);
--- 919,929 ----
  
          result.splitParent = parent;
          result.setLocationHint(parent);
  
          // insert new interval in children-list of parent
!         if (parent.splitChildrenEmpty()) {
              assert isSplitParent() : "list must be initialized at first split";
  
              // Create new non-shared list
              parent.splitChildren = new ArrayList<>(4);
              parent.splitChildren.add(this);
*** 931,941 ****
          intTo = splitPos;
  
          // split list of use positions
          splitUsePosAt(result, splitPos);
  
!         if (DetailedAsserts.getValue()) {
              for (int i = 0; i < numUsePos(); i++) {
                  assert getUsePos(i) < splitPos;
              }
              for (int i = 0; i < result.numUsePos(); i++) {
                  assert result.getUsePos(i) >= splitPos;
--- 959,969 ----
          intTo = splitPos;
  
          // split list of use positions
          splitUsePosAt(result, splitPos);
  
!         if (DetailedAsserts.getValue(options)) {
              for (int i = 0; i < numUsePos(); i++) {
                  assert getUsePos(i) < splitPos;
              }
              for (int i = 0; i < result.numUsePos(); i++) {
                  assert result.getUsePos(i) >= splitPos;