src/main/java/com/android/tools/r8/ir/regalloc/LiveIntervals.java

// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.regalloc;

import static com.android.tools.r8.dex.Constants.U16BIT_MAX;
import static com.android.tools.r8.dex.Constants.U8BIT_MAX;

import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.utils.CfgPrinter;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.function.IntConsumer;

public class LiveIntervals implements Comparable<LiveIntervals> {

  public static final int NO_REGISTER = Integer.MIN_VALUE;
  public static final int CHILDREN_SORTING_CUTOFF = 100;

  private final Value value;
  private LiveIntervals nextConsecutive;
  private LiveIntervals previousConsecutive;
  private final LiveIntervals splitParent;
  private final List<LiveIntervals> splitChildren = new ArrayList<>();
  private final IntArrayList sortedSplitChildrenEnds = new IntArrayList();
  private boolean sortedChildren = false;
  private List<LiveRange> ranges = new ArrayList<>();
  private final TreeSet<LiveIntervalsUse> uses = new TreeSet<>();
  private int numberOfConsecutiveRegisters = -1;
  private int register = NO_REGISTER;
  private Integer hint;
  private boolean spilled = false;
  private boolean usedInMonitorOperations = false;

  // Only registers up to and including the registerLimit are allowed for this interval.
  private int registerLimit = U16BIT_MAX;

  // Max register used for any of the non-spilled splits for these live intervals or for any of the
  // live intervals that this live interval is connected to by phi moves. This is used to
  // conservatively determine if it is safe to use rematerialization for this value.
  private int maxNonSpilledRegister = NO_REGISTER;
  private boolean isRematerializable = false;

  public LiveIntervals(Value value) {
    this.value = value;
    usedInMonitorOperations = value.usedInMonitorOperation();
    splitParent = this;
    value.setLiveIntervals(this);
  }

  public LiveIntervals(LiveIntervals splitParent) {
    this.splitParent = splitParent;
    value = splitParent.value;
    usedInMonitorOperations = splitParent.usedInMonitorOperations;
  }

  private int toInstructionPosition(int position) {
    return position % 2 == 0 ? position : position + 1;
  }

  private int toGapPosition(int position) {
    return position % 2 == 1 ? position : position - 1;
  }

  public Value getValue() {
    return value;
  }

  public ValueType getType() {
    return value.outType();
  }

  public int requiredRegisters() {
    return getType().requiredRegisters();
  }

  public void setHint(LiveIntervals intervals, PriorityQueue<LiveIntervals> unhandled) {
    // Do not set hints if they cannot be used anyway.
    if (!overlaps(intervals)) {
      // The hint is used in sorting the unhandled intervals. Therefore, if the hint changes
      // we have to remove and reinsert the interval to get the sorting updated.
      boolean removed = unhandled.remove(this);
      hint = intervals.getRegister();
      if (removed) {
        unhandled.add(this);
      }
    }
  }

  public Integer getHint() {
    return hint;
  }

  public void setSpilled(boolean value) {
    // Check that we always spill arguments to their original register.
    assert getRegister() != NO_REGISTER;
    assert !(value && isArgumentInterval()) || getRegister() == getSplitParent().getRegister();
    spilled = value;
  }

  public boolean isSpilled() {
    return spilled;
  }

  private boolean isRematerializable() {
    assert splitParent == this;
    return isRematerializable;
  }

  private boolean allSplitsAreSpilled() {
    assert isSpilled();
    for (LiveIntervals splitChild : splitChildren) {
      assert splitChild.isSpilled();
    }
    return true;
  }

  public boolean isSpilledAndRematerializable() {
    return isSpilled() && splitParent.isRematerializable();
  }

  public void link(LiveIntervals next) {
    assert numberOfConsecutiveRegisters == -1;
    nextConsecutive = next;
    next.previousConsecutive = this;
  }

  public boolean isLinked() {
    return splitParent.previousConsecutive != null || splitParent.nextConsecutive != null;
  }

  public boolean isArgumentInterval() {
    Instruction definition = this.splitParent.value.definition;
    return definition != null && definition.isArgument();
  }

  public LiveIntervals getStartOfConsecutive() {
    LiveIntervals current = this;
    while (current.previousConsecutive != null) {
      current = current.previousConsecutive;
    }
    return current;
  }

  public LiveIntervals getNextConsecutive() {
    return nextConsecutive;
  }

  public LiveIntervals getPreviousConsecutive() {
    return previousConsecutive;
  }

  public int numberOfConsecutiveRegisters() {
    LiveIntervals start = getStartOfConsecutive();
    if (start.numberOfConsecutiveRegisters != -1) {
      assert start.numberOfConsecutiveRegisters == computeNumberOfConsecutiveRegisters();
      return start.numberOfConsecutiveRegisters;
    }
    return computeNumberOfConsecutiveRegisters();
  }

  private int computeNumberOfConsecutiveRegisters() {
    LiveIntervals start = getStartOfConsecutive();
    int result = 0;
    for (LiveIntervals current = start;
        current != null;
        current = current.nextConsecutive) {
      result += current.requiredRegisters();
    }
    start.numberOfConsecutiveRegisters = result;
    return result;
  }

  public boolean hasSplits() {
    return splitChildren.size() != 0;
  }

  private void sortSplitChildrenIfNeeded() {
    if (!sortedChildren) {
      splitChildren.sort(Comparator.comparingInt(LiveIntervals::getEnd));
      sortedSplitChildrenEnds.clear();
      for (LiveIntervals splitChild : splitChildren) {
        sortedSplitChildrenEnds.add(splitChild.getEnd());
      }
      assert sortedChildrenConsistent();
      sortedChildren = true;
    }
  }

  private boolean sortedChildrenConsistent() {
    for (int i = 0; i < splitChildren.size(); i++) {
      assert splitChildren.get(i).getEnd() == sortedSplitChildrenEnds.getInt(i);
      assert i == 0 || sortedSplitChildrenEnds.getInt(i - 1) <= sortedSplitChildrenEnds.getInt(i);
    }
    return true;
  }

  public List<LiveIntervals> getSplitChildren() {
    return splitChildren;
  }

  public LiveIntervals getSplitParent() {
    return splitParent;
  }

  /**
   * Add a live range to the intervals.
   *
   * @param range the range to add
   */
  public void addRange(LiveRange range) {
    boolean added = tryAddRange(range);
    assert added;
  }

  private boolean tryAddRange(LiveRange range) {
    if (ranges.size() > 0) {
      LiveRange lastRange = ranges.get(ranges.size() - 1);
      if (lastRange.isInfinite()) {
        return false;
      }
      int rangeStartInstructionPosition = toInstructionPosition(range.start);
      int lastRangeEndInstructionPosition = toInstructionPosition(lastRange.end);
      if (lastRangeEndInstructionPosition > rangeStartInstructionPosition) {
        return false;
      }
      if (lastRangeEndInstructionPosition == rangeStartInstructionPosition) {
        lastRange.end = range.end;
        return true;
      }
    }
    ranges.add(range);
    return true;
  }

  /**
   * Record a use for this interval.
   */
  public void addUse(LiveIntervalsUse use) {
    uses.add(use);
    updateRegisterConstraint(use.getLimit());
  }

  public void updateRegisterConstraint(int constraint) {
    registerLimit = Math.min(registerLimit, constraint);
  }

  public TreeSet<LiveIntervalsUse> getUses() {
    return uses;
  }

  public List<LiveRange> getRanges() {
    return ranges;
  }

  public int getStart() {
    assert !ranges.isEmpty();
    return ranges.get(0).start;
  }

  public int getEnd() {
    assert !ranges.isEmpty();
    return ranges.get(ranges.size() - 1).end;
  }

  public int getRegister() {
    return register;
  }

  public int getRegisterLimit() {
    return registerLimit;
  }

  public void setRegister(int n) {
    assert register == NO_REGISTER || register == n;
    register = n;
  }

  private int computeMaxNonSpilledRegister() {
    assert splitParent == this;
    assert maxNonSpilledRegister == NO_REGISTER;
    if (!isSpilled()) {
      maxNonSpilledRegister = getRegister();
    }
    for (LiveIntervals child : splitChildren) {
      if (!child.isSpilled()) {
        maxNonSpilledRegister = Math.max(maxNonSpilledRegister, child.getRegister());
      }
    }
    return maxNonSpilledRegister;
  }

  public void setMaxNonSpilledRegister(int i) {
    assert i >= splitParent.maxNonSpilledRegister;
    splitParent.maxNonSpilledRegister = i;
  }

  public int getMaxNonSpilledRegister() {
    if (splitParent.maxNonSpilledRegister != NO_REGISTER) {
      return splitParent.maxNonSpilledRegister;
    }
    return splitParent.computeMaxNonSpilledRegister();
  }

  public boolean usesRegister(int n, boolean otherIsWide) {
    if (register == n) {
      return true;
    }
    if (getType().isWide() && register + 1 == n) {
      return true;
    }
    if (otherIsWide && register == n + 1) {
      return true;
    }
    return false;
  }

  public boolean hasConflictingRegisters(LiveIntervals other) {
    return other.usesRegister(register, getType().isWide());
  }

  public void clearRegisterAssignment() {
    register = NO_REGISTER;
    hint = null;
  }

  public boolean overlapsPosition(int position) {
    for (LiveRange range : ranges) {
      if (range.start > position) {
        // Ranges are sorted. When a range starts after position there is no overlap.
        return false;
      }
      if (position < range.end) {
        return true;
      }
    }
    return false;
  }

  public boolean overlaps(LiveIntervals other) {
    return nextOverlap(other) != -1;
  }

  public boolean anySplitOverlaps(LiveIntervals other) {
    LiveIntervals parent = getSplitParent();
    if (parent.overlaps(other)) {
      return true;
    }
    for (LiveIntervals child : parent.getSplitChildren()) {
      if (child.overlaps(other)) {
        return true;
      }
    }
    return false;
  }

  public int nextOverlap(LiveIntervals other) {
    Iterator<LiveRange> it = other.ranges.iterator();
    LiveRange otherRange = it.next();
    for (LiveRange range : ranges) {
      while (otherRange.end <= range.start) {
        if (!it.hasNext()) {
          return -1;
        }
        otherRange = it.next();
      }
      if (otherRange.start < range.end) {
        return otherRange.start;
      }
    }
    return -1;
  }

  public int firstUseAfter(int unhandledStart) {
    for (LiveIntervalsUse use : uses) {
      if (use.getPosition() >= unhandledStart) {
        return use.getPosition();
      }
    }
    return Integer.MAX_VALUE;
  }

  public boolean hasUses() {
    return !uses.isEmpty();
  }

  public int getFirstUse() {
    return uses.first().getPosition();
  }

  public LiveIntervalsUse firstUseWithConstraint() {
    for (LiveIntervalsUse use : uses) {
      if (use.hasConstraint()) {
        return use;
      }
    }
    return null;
  }

  public void forEachRegister(IntConsumer consumer) {
    assert register != NO_REGISTER;
    consumer.accept(register);
    if (getType().isWide()) {
      consumer.accept(register + 1);
    }
  }

  public LiveIntervals splitBefore(int start) {
    if (toInstructionPosition(start) == toInstructionPosition(getStart())) {
      assert uses.size() == 0 || getFirstUse() != start;
      register = NO_REGISTER;
      return this;
    }

    assert !getValue().isDefinedByInstructionSatisfying(Instruction::isInitClass);

    start = toGapPosition(start);
    LiveIntervals splitChild = new LiveIntervals(splitParent);
    splitParent.splitChildren.add(splitChild);
    splitParent.sortedChildren = false;
    List<LiveRange> beforeSplit = new ArrayList<>();
    List<LiveRange> afterSplit = new ArrayList<>();
    if (start == getEnd()) {
      beforeSplit = ranges;
      afterSplit.add(new LiveRange(start, start));
    } else {
      int rangeToSplitIndex = 0;
      for (; rangeToSplitIndex < ranges.size(); rangeToSplitIndex++) {
        LiveRange range = ranges.get(rangeToSplitIndex);
        if (range.start <= start && range.end > start) {
          break;
        }
        if (range.start > start) {
          break;
        }
      }
      LiveRange rangeToSplit = ranges.get(rangeToSplitIndex);
      beforeSplit.addAll(ranges.subList(0, rangeToSplitIndex));
      if (rangeToSplit.start < start) {
        beforeSplit.add(new LiveRange(rangeToSplit.start, start));
        afterSplit.add(new LiveRange(start, rangeToSplit.end));
      } else {
        afterSplit.add(rangeToSplit);
      }
      afterSplit.addAll(ranges.subList(rangeToSplitIndex + 1, ranges.size()));
    }
    splitChild.ranges = afterSplit;
    ranges = beforeSplit;
    while (!uses.isEmpty() && uses.last().getPosition() >= start) {
      splitChild.addUse(uses.pollLast());
    }
    // Recompute limit after having removed uses from this interval.
    recomputeLimit();
    assert !ranges.isEmpty();
    assert !splitChild.ranges.isEmpty();
    return splitChild;
  }

  public void undoSplits() {
    List<LiveRange> ranges = new ArrayList<>(this.ranges);
    for (LiveIntervals split : splitChildren) {
      ranges.addAll(split.ranges);
      for (LiveIntervalsUse use : split.uses) {
        addUse(use);
      }
    }
    Collections.sort(ranges);
    this.ranges.clear();
    for (LiveRange range : ranges) {
      addRange(range);
    }
    splitChildren.clear();
    recomputeLimit();
  }

  private void recomputeLimit() {
    registerLimit = U16BIT_MAX;
    for (LiveIntervalsUse use : uses) {
      updateRegisterConstraint(use.getLimit());
    }
  }

  public LiveIntervals getSplitCovering(int instructionNumber) {
    assert getSplitParent() == this;
    // Check if this interval itself is covering the instruction.
    if (getStart() <= instructionNumber && getEnd() > instructionNumber) {
      return this;
    }
    // If the instruction number is not in this intervals range, we go through all split children.
    // If we do not find a child that contains the instruction number we return the interval
    // whose end is the instruction number. This is needed when transitioning values across
    // control-flow boundaries.
    LiveIntervals matchingEnd = getEnd() == instructionNumber ? this : null;
    // When there are many children, avoid looking at the ones for which the end is before
    // the instruction number by doing a binary search for the first candidate whose end is after
    // the instruction number.
    int firstCandidate = 0;
    if (splitChildren.size() > CHILDREN_SORTING_CUTOFF) {
      sortSplitChildrenIfNeeded();
      firstCandidate = Collections.binarySearch(sortedSplitChildrenEnds, instructionNumber);
      if (firstCandidate < 0) {
        firstCandidate = -(firstCandidate + 1);
      }
    }
    for (int i = firstCandidate; i < splitChildren.size(); i++) {
      LiveIntervals splitChild = splitChildren.get(i);
      if (splitChild.getStart() <= instructionNumber && splitChild.getEnd() > instructionNumber) {
        return splitChild;
      }
      if (splitChild.getEnd() == instructionNumber) {
        matchingEnd = splitChild;
      }
    }
    if (matchingEnd != null) {
      return matchingEnd;
    }
    assert false : "Couldn't find split covering instruction position.";
    return null;
  }

  public boolean isConstantNumberInterval() {
    return value.definition != null && value.isConstNumber();
  }

  public boolean usedInMonitorOperation() {
    return usedInMonitorOperations;
  }

  public boolean isNewStringInstanceDisallowingSpilling() {
    // Due to b/80118070 some String new-instances must not be spilled.
    return value.definition != null
        && value.definition.isNewInstance()
        && !value.definition.asNewInstance().isSpillingAllowed();
  }

  public int numberOfUsesWithConstraint() {
    int count = 0;
    for (LiveIntervalsUse use : getUses()) {
      if (use.hasConstraint()) {
        count++;
      }
    }
    return count;
  }

  @Override
  public int compareTo(LiveIntervals other) {
    // Sort by interval start instruction number.
    int startDiff = getStart() - other.getStart();
    if (startDiff != 0) return startDiff;
    // Then sort by register number of hints to make sure that a phi
    // does not take a low register that is the hint for another phi.
    if (hint != null && other.hint != null) {
      int registerDiff = hint - other.hint;
      if (registerDiff != 0) return registerDiff;
    }
    // Intervals with hints go first so intervals without hints
    // do not take registers from intervals with hints.
    if (hint != null && other.hint == null) return -1;
    if (hint == null && other.hint != null) return 1;
    // Tie-breaker: no values have equal numbers.
    int result = value.getNumber() - other.value.getNumber();
    assert result != 0;
    return result;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("(cons ");
    // Use the field here to avoid toString to have side effects.
    builder.append(numberOfConsecutiveRegisters);
    builder.append("): ");
    for (LiveRange range : getRanges()) {
      builder.append(range);
      builder.append(" ");
    }
    builder.append("\n");
    return builder.toString();
  }

  public String toAscciArtString() {
    StringBuilder builder = new StringBuilder();
    int current = 0;
    for (LiveRange range : getRanges()) {
      if (range.isInfinite()) {
        builder.append("--- infinite ---...");
        break;
      }
      for (; current < range.start; current++) {
        builder.append(" ");
      }
      for (; current < range.end; current++) {
        builder.append("-");
      }
    }
    return builder.toString();
  }

  public void print(CfgPrinter printer, int number, int parentNumber) {
    printer.append(number * 10000 + register) // range number
        .sp().append("object") // range type
        .sp().append(parentNumber * 10000 + getSplitParent().getRegister()) // split parent
        .sp().append(-1); // hint
    for (LiveRange range : getRanges()) {
      printer.sp().append(range.toString());
    }
    for (LiveIntervalsUse use : getUses()) {
      printer.sp().append(use.getPosition()).sp().append("M");
    }
    printer.append(" \"\"").ln();
    int delta = 0;
    for (LiveIntervals splitChild : splitChildren) {
      delta += 10000;
      splitChild.print(printer, number + delta, number);
    }
  }

  public void computeRematerializable(LinearScanRegisterAllocator allocator) {
    assert splitParent == this;
    if (value.isArgument()) {
      isRematerializable = true;
      return;
    }

    // TODO(ager): rematerialize const string as well. However, in that case we have to be very
    // careful with methods with synchronization. If we rematerialize in a block that has no
    // other throwing instructions we can end up with lock-level verification issues. The
    // rematerialized throwing const-string instruction is not covered by the catch range going
    // to the monitor-exit instruction and we can leave the method without unlocking the monitor.
    if (!value.isConstNumber()) {
      return;
    }

    // If the constant is spilled when flowing to a phi and the phi has a register higher than what
    // can be const rematerialized then this value is not rematerializable and needs a register even
    // when spilled.
    for (Phi phi : value.uniquePhiUsers()) {
      int reg = allocator.unadjustedRealRegisterFromAllocated(phi.getLiveIntervals().getRegister());
      if (reg >= U8BIT_MAX) {
        for (int predIndex = 0; predIndex < phi.getOperands().size(); predIndex++) {
          Value operand = phi.getOperand(predIndex);
          if (operand == value) {
            int predExit = phi.getBlock().getPredecessors().get(predIndex).exit().getNumber();
            if (getSplitCovering(predExit).isSpilled()) {
              return;
            }
          }
        }
      }
    }

    // If one of the non-spilled splits uses a register that is higher than U8BIT_MAX we cannot
    // rematerialize it using a ConstNumber instruction and we use spill moves instead of
    // rematerialization. We use this check both before and after we have computed the set
    // of unused registers. We therefore have to be careful to use the same max number for
    // these computations. We use the unadjusted real register number to make sure that
    // isRematerializable for the same intervals does not change from one phase of
    // compilation to the next.
    if (getMaxNonSpilledRegister() == NO_REGISTER) {
      assert allSplitsAreSpilled();
      isRematerializable = true;
      return;
    }
    int max = allocator.unadjustedRealRegisterFromAllocated(getMaxNonSpilledRegister());
    isRematerializable = max < U8BIT_MAX;
  }
}