// Copyright (c) 2017, 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.ir.code.IRCode.INSTRUCTION_NUMBER_DELTA;
import static com.android.tools.r8.ir.regalloc.LiveIntervals.NO_REGISTER;

import com.android.tools.r8.cf.FixedLocalValue;
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.ir.code.Add;
import com.android.tools.r8.ir.code.And;
import com.android.tools.r8.ir.code.ArithmeticBinop;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.CheckCast;
import com.android.tools.r8.ir.code.DebugLocalsChange;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.Move;
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Or;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Sub;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.ir.code.Xor;
import com.android.tools.r8.ir.regalloc.RegisterPositions.Type;
import com.android.tools.r8.logging.Log;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multisets;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntArraySet;
import it.unimi.dsi.fastutil.ints.IntIterator;
import it.unimi.dsi.fastutil.ints.IntSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;

/**
 * Linear scan register allocator.
 *
 * <p>The implementation is inspired by:
 *
 * <ul>
 *   <li>"Linear Scan Register Allocation in the Context of SSA Form and Register Constraints"
 *   (ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF)</li>
 *   <li>"Linear Scan Register Allocation on SSA Form"
 *   (http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer10a.pdf)</li>
 *   <li>"Linear Scan Register Allocation for the Java HotSpot Client Compiler"
 *   (http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf)</li>
 * </ul>
 */
public class LinearScanRegisterAllocator implements RegisterAllocator {

  public static final int REGISTER_CANDIDATE_NOT_FOUND = -1;
  public static final int MIN_CONSTANT_FREE_FOR_POSITIONS = 5;

  private enum ArgumentReuseMode {
    ALLOW_ARGUMENT_REUSE,
    DISALLOW_ARGUMENT_REUSE
  }

  private static class LocalRange implements Comparable<LocalRange> {
    final Value value;
    final DebugLocalInfo local;
    final int register;
    final int start;
    final int end;

    LocalRange(Value value, int register, int start, int end) {
      assert value.hasLocalInfo();
      this.value = value;
      this.local = value.getLocalInfo();
      this.register = register;
      this.start = start;
      this.end = end;
    }

    @Override
    public int compareTo(LocalRange o) {
      return (start != o.start)
          ? Integer.compare(start, o.start)
          : Integer.compare(end, o.end);
    }

    @Override
    public String toString() {
      return local + " @ r" + register + ": " + new LiveRange(start, end);
    }
  }

  // The max register number that will fit in any dex instruction encoding.
  private static final int MAX_SMALL_REGISTER = Constants.U4BIT_MAX;
  // We put one sentinel in front of the argument chain and one after the argument chain.
  private static final int NUMBER_OF_SENTINEL_REGISTERS = 2;

  // The code for which to allocate registers.
  private final IRCode code;
  // Number of registers used for arguments.
  private final int numberOfArgumentRegisters;
  // Compiler options.
  private final InternalOptions options;

  // Mapping from basic blocks to the set of values live at entry to that basic block.
  private Map<BasicBlock, Set<Value>> liveAtEntrySets;
  // The sentinel value starting the chain of linked argument values.
  private Value preArgumentSentinelValue = null;

  // The set of registers that are free for allocation.
  private TreeSet<Integer> freeRegisters = new TreeSet<>();
  // The max register number used.
  private int maxRegisterNumber = 0;
  // The next available register number not yet included in the set of used registers.
  private int nextUnusedRegisterNumber = 0;

  // List of all top-level live intervals for all SSA values.
  private List<LiveIntervals> liveIntervals = new ArrayList<>();
  // List of active intervals.
  private List<LiveIntervals> active = new LinkedList<>();
  // List of intervals where the current instruction falls into one of their live range holes.
  protected List<LiveIntervals> inactive = new LinkedList<>();
  // List of intervals that no register has been allocated to sorted by first live range.
  protected PriorityQueue<LiveIntervals> unhandled = new PriorityQueue<>();

  // The first register used for parallel moves. After register allocation the parallel move
  // temporary registers are [firstParallelMoveTemporary, maxRegisterNumber].
  private int firstParallelMoveTemporary = NO_REGISTER;
  // Mapping from register number to the number of unused register numbers below that register
  // number. Used for compacting the register numbers if some spill registers are not used
  // because their values can be rematerialized.
  private int[] unusedRegisters = null;

  // Whether or not the code has a move exception instruction. Used to pin the move exception
  // register.
  private boolean hasDedicatedMoveExceptionRegister = false;

  public LinearScanRegisterAllocator(IRCode code, InternalOptions options) {
    this.code = code;
    this.options = options;
    int argumentRegisters = 0;
    for (Instruction instruction : code.blocks.getFirst().getInstructions()) {
      if (instruction.isArgument()) {
        argumentRegisters += instruction.outValue().requiredRegisters();
      }
    }
    numberOfArgumentRegisters = argumentRegisters;
  }

  /**
   * Perform register allocation for the IRCode.
   */
  @Override
  public void allocateRegisters(boolean debug) {
    // There are no linked values prior to register allocation.
    assert noLinkedValues();
    assert code.isConsistentSSA();
    computeNeedsRegister();
    insertArgumentMoves();
    ImmutableList<BasicBlock> blocks = computeLivenessInformation();
    // First attempt to allocate register allowing argument reuse. This will fail if spilling
    // is required or if we end up using more than 16 registers.
    boolean noSpilling =
        performAllocationWithoutMoveInsertion(ArgumentReuseMode.ALLOW_ARGUMENT_REUSE);
    if (!noSpilling || (highestUsedRegister() > MAX_SMALL_REGISTER)) {
      // Redo allocation disallowing argument reuse. This always succeeds.
      clearRegisterAssignments();
      performAllocation(ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE);
    } else {
      // Insert spill and phi moves after allocating with argument reuse. If the moves causes
      // the method to use more than 16 registers we redo allocation disallowing argument
      // reuse. This very rarely happens in practice (12 methods on GMSCore v4 hits that case).
      insertMoves();
      if (highestUsedRegister() > MAX_SMALL_REGISTER) {
        // Redo allocation disallowing argument reuse. This always succeeds.
        clearRegisterAssignments();
        removeSpillAndPhiMoves();
        performAllocation(ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE);
      }
    }

    assert code.isConsistentGraph();
    if (Log.ENABLED) {
      Log.debug(this.getClass(), toString());
    }
    computeUnusedRegisters();
    if (debug) {
      computeDebugInfo(blocks);
    }
    clearUserInfo();
    clearState();
  }

  private static Integer nextInRange(int start, int end, List<Integer> points) {
    while (!points.isEmpty() && points.get(0) < start) {
      points.remove(0);
    }
    if (points.isEmpty()) {
      return null;
    }
    Integer next = points.get(0);
    assert start <= next;
    if (next < end) {
      points.remove(0);
      return next;
    }
    return null;
  }

  private void computeDebugInfo(ImmutableList<BasicBlock> blocks) {
    computeDebugInfo(blocks, liveIntervals, this);
  }

  public static void computeDebugInfo(
      ImmutableList<BasicBlock> blocks, List<LiveIntervals> liveIntervals,
      RegisterAllocator allocator) {
    // Collect live-ranges for all SSA values with local information.
    List<LocalRange> ranges = new ArrayList<>();
    for (LiveIntervals interval : liveIntervals) {
      Value value = interval.getValue();
      if (!value.hasLocalInfo()) {
        continue;
      }
      List<Integer> starts = ListUtils.map(value.getDebugLocalStarts(), Instruction::getNumber);
      List<Integer> ends = ListUtils.map(value.getDebugLocalEnds(), Instruction::getNumber);
      List<LiveRange> liveRanges = new ArrayList<>();
      liveRanges.addAll(interval.getRanges());
      for (LiveIntervals child : interval.getSplitChildren()) {
        assert child.getValue() == value;
        assert child.getSplitChildren() == null || child.getSplitChildren().isEmpty();
        liveRanges.addAll(child.getRanges());
      }
      liveRanges.sort((r1, r2) -> Integer.compare(r1.start, r2.start));
      starts.sort(Integer::compare);
      ends.sort(Integer::compare);

      for (LiveRange liveRange : liveRanges) {
        int start = liveRange.start;
        int end = liveRange.end;
        Integer nextEnd;
        while ((nextEnd = nextInRange(start, end, ends)) != null) {
          // If an argument value has been split, we have disallowed argument reuse and therefore,
          // the argument value is also in the argument register throughout the method. For debug
          // information, we always use the argument register whenever a local corresponds to an
          // argument value. That avoids ending and restarting locals whenever we move arguments
          // to lower register.
          int register = allocator.getArgumentOrAllocateRegisterForValue(value, start);
          ranges.add(new LocalRange(value, register, start, nextEnd));
          Integer nextStart = nextInRange(nextEnd, end, starts);
          if (nextStart == null) {
            start = -1;
            break;
          }
          start = nextStart;
        }
        if (start >= 0) {
          ranges.add(
              new LocalRange(
                  value,
                  allocator.getArgumentOrAllocateRegisterForValue(value, start),
                  start,
                  end));
        }
      }
    }
    if (ranges.isEmpty()) {
      return;
    }
    ranges.sort(LocalRange::compareTo);

    // At each instruction compute the changes to live locals.
    boolean localsChanged = false;
    LinkedList<LocalRange> openRanges = new LinkedList<>();
    Iterator<LocalRange> rangeIterator = ranges.iterator();
    LocalRange nextStartingRange = rangeIterator.next();

    for (BasicBlock block : blocks) {
      // Skip past all spill moves to obtain the instruction number of the actual first instruction.
      InstructionListIterator instructionIterator = block.listIterator();
      instructionIterator.nextUntil(
          i -> !i.isArgument() && !i.isMoveException() && !isSpillInstruction(i));
      Instruction firstInstruction = instructionIterator.previous();
      int firstIndex = firstInstruction.getNumber();

      // Close ranges up-to but excluding the first instruction. Ends are exclusive but the values
      // might be live upon entering the first instruction (if they are used by it). Since we
      // skipped move-exception this closes locals at the move exception which should close as part
      // of the exceptional transfer.
      openRanges.removeIf(openRange -> !isLocalLiveAtInstruction(firstInstruction, openRange));

      // Open ranges up-to but excluding the first instruction. Starts are inclusive but entry is
      // prior to the first instruction.
      while (nextStartingRange != null && nextStartingRange.start < firstIndex) {
        // If the range is live at this index open it. Again the end is inclusive here because the
        // instruction is live at block entry if it is live at entry to the first instruction.
        if (isLocalLiveAtInstruction(firstInstruction, nextStartingRange)) {
          openRanges.add(nextStartingRange);
        }
        nextStartingRange = rangeIterator.hasNext() ? rangeIterator.next() : null;
      }

      // Initialize current locals (registers after any spill instructions).
      Int2ReferenceMap<DebugLocalInfo> currentLocals =
          new Int2ReferenceOpenHashMap<>(openRanges.size());
      for (LocalRange openRange : openRanges) {
        currentLocals.put(openRange.register, openRange.local);
      }

      // Set locals at entry. This will adjust initial local registers in case of spilling.
      setLocalsAtEntry(block, instructionIterator, openRanges, currentLocals, allocator);

      // Iterate the block instructions and emit locals changed events.
      while (instructionIterator.hasNext()) {
        Instruction instruction = instructionIterator.next();
        if (instruction.isDebugLocalRead()) {
          // Remove debug local reads now that local liveness is computed.
          assert !instruction.getDebugValues().isEmpty();
          instruction.clearDebugValues();
          instructionIterator.remove();
        }
        if (isSpillInstruction(instruction)) {
          continue;
        }
        int index = instruction.getNumber();
        ListIterator<LocalRange> it = openRanges.listIterator(0);
        Int2ReferenceMap<DebugLocalInfo> ending = new Int2ReferenceOpenHashMap<>();
        Int2ReferenceMap<DebugLocalInfo> starting = new Int2ReferenceOpenHashMap<>();
        while (it.hasNext()) {
          LocalRange openRange = it.next();
          // Any local change is inserted after the instruction so end is inclusive.
          if (openRange.end <= index) {
            it.remove();
            assert currentLocals.get(openRange.register) == openRange.local;
            currentLocals.remove(openRange.register);
            localsChanged = true;
            ending.put(openRange.register, openRange.local);
          }
        }
        while (nextStartingRange != null && nextStartingRange.start <= index) {
          // If the range is live at this index open it.
          if (index < nextStartingRange.end) {
            openRanges.add(nextStartingRange);
            assert !currentLocals.containsKey(nextStartingRange.register);
            currentLocals.put(nextStartingRange.register, nextStartingRange.local);
            starting.put(nextStartingRange.register, nextStartingRange.local);
            localsChanged = true;
          }
          nextStartingRange = rangeIterator.hasNext() ? rangeIterator.next() : null;
        }
        if (localsChanged && instruction.getBlock().exit() != instruction) {
          DebugLocalsChange change = createLocalsChange(ending, starting);
          if (change != null) {
            instructionIterator.add(change);
          }
        }
        localsChanged = false;
      }
    }
  }

  private static boolean isLocalLiveAtInstruction(Instruction instruction, LocalRange range) {
    return isLocalLiveAtInstruction(instruction, range.start, range.end, range.value);
  }

  public static boolean isLocalLiveAtInstruction(
      Instruction instruction, LiveRange range, Value value) {
    return isLocalLiveAtInstruction(instruction, range.start, range.end, value);
  }

  private static boolean isLocalLiveAtInstruction(
      Instruction instruction, int start, int end, Value value) {
    int number = instruction.getNumber();
    assert start < number;
    return number < end || (number == end && usesValue(value, instruction));
  }

  private static boolean usesValue(Value usedValue, Instruction instruction) {
    return valuesContain(usedValue, instruction.inValues())
        || valuesContain(usedValue, instruction.getDebugValues());
  }

  private static boolean valuesContain(Value value, Collection<Value> values) {
    for (Value other : values) {
      if (value == other) {
        return true;
      }
      if (value.isPhi()
          && other instanceof FixedLocalValue
          && ((FixedLocalValue) other).getPhi() == value) {
        return true;
      }
    }
    return false;
  }

  private static void setLocalsAtEntry(
      BasicBlock block,
      InstructionListIterator instructionIterator,
      List<LocalRange> openRanges,
      Int2ReferenceMap<DebugLocalInfo> finalLocals,
      RegisterAllocator allocator) {
    // If this is the graph-entry or there are no moves entry locals are current locals.
    if (block.getPredecessors().isEmpty() || block.entry() == instructionIterator.peekNext()) {
      assert !block.entry().isMoveException();
      assert !isSpillInstruction(block.entry());
      block.setLocalsAtEntry(new Int2ReferenceOpenHashMap<>(finalLocals));
      return;
    }
    // Otherwise entry locals are the registers of the predecessor, ie, prior to spill instructions.
    Int2ReferenceMap<DebugLocalInfo> initialLocals =
        new Int2ReferenceOpenHashMap<>(openRanges.size());
    int predecessorExitIndex =
        block.entry().isMoveException()
            ? block.getPredecessors().get(0).exceptionalExit().getNumber()
            : block.getPredecessors().get(0).exit().getNumber();
    for (LocalRange open : openRanges) {
      int predecessorRegister =
          allocator.getArgumentOrAllocateRegisterForValue(open.value, predecessorExitIndex);
      initialLocals.put(predecessorRegister, open.local);
    }
    block.setLocalsAtEntry(initialLocals);

    // Compute the final change in locals and insert it after the last spill instruction.
    Int2ReferenceMap<DebugLocalInfo> ending = new Int2ReferenceOpenHashMap<>();
    Int2ReferenceMap<DebugLocalInfo> starting = new Int2ReferenceOpenHashMap<>();
    for (Entry<DebugLocalInfo> initialLocal : initialLocals.int2ReferenceEntrySet()) {
      if (finalLocals.get(initialLocal.getIntKey()) != initialLocal.getValue()) {
        ending.put(initialLocal.getIntKey(), initialLocal.getValue());
      }
    }
    for (Entry<DebugLocalInfo> finalLocal : finalLocals.int2ReferenceEntrySet()) {
      if (initialLocals.get(finalLocal.getIntKey()) != finalLocal.getValue()) {
        starting.put(finalLocal.getIntKey(), finalLocal.getValue());
      }
    }
    DebugLocalsChange change = createLocalsChange(ending, starting);
    if (change != null) {
      instructionIterator.add(change);
    }
  }

  private static DebugLocalsChange createLocalsChange(
      Int2ReferenceMap<DebugLocalInfo> ending, Int2ReferenceMap<DebugLocalInfo> starting) {
    if (ending.isEmpty() && starting.isEmpty()) {
      return null;
    }
    if (ending.isEmpty() || starting.isEmpty()) {
      return new DebugLocalsChange(ending, starting);
    }
    IntSet unneeded = new IntArraySet(Math.min(ending.size(), starting.size()));
    for (Entry<DebugLocalInfo> entry : ending.int2ReferenceEntrySet()) {
      if (starting.get(entry.getIntKey()) == entry.getValue()) {
        unneeded.add(entry.getIntKey());
      }
    }
    if (unneeded.size() == ending.size() && unneeded.size() == starting.size()) {
      return null;
    }
    IntIterator iterator = unneeded.iterator();
    while (iterator.hasNext()) {
      int key = iterator.nextInt();
      ending.remove(key);
      starting.remove(key);
    }
    return new DebugLocalsChange(ending, starting);
  }

  private void clearState() {
    liveAtEntrySets = null;
    liveIntervals = null;
    active = null;
    inactive = null;
    unhandled = null;
    freeRegisters = null;
  }

  // Compute a table that for each register numbers contains the number of previous register
  // numbers that were unused. This table is then used to slide down the actual registers
  // used to fill the gaps.
  private void computeUnusedRegisters() {
    if (registersUsed() == 0) {
      return;
    }
    // Compute the set of registers that is used based on all live intervals.
    Set<Integer> usedRegisters = new HashSet<>();
    for (LiveIntervals intervals : liveIntervals) {
      addRegisterIfUsed(usedRegisters, intervals);
      for (LiveIntervals childIntervals : intervals.getSplitChildren()) {
        addRegisterIfUsed(usedRegisters, childIntervals);
      }
    }
    // Additionally, we have used temporary registers for parallel move scheduling, those
    // are used as well.
    for (int i = firstParallelMoveTemporary; i < maxRegisterNumber + 1; i++) {
      usedRegisters.add(realRegisterNumberFromAllocated(i));
    }
    // Compute the table based on the set of used registers.
    int unused = 0;
    int[] computed = new int[registersUsed()];
    for (int i = 0; i < registersUsed(); i++) {
      if (!usedRegisters.contains(i)) {
        unused++;
      }
      computed[i] = unused;
    }
    unusedRegisters = computed;
  }

  private void addRegisterIfUsed(Set<Integer> used, LiveIntervals intervals) {
    boolean unused = intervals.isSpilledAndRematerializable(this);
    if (!unused) {
      used.add(realRegisterNumberFromAllocated(intervals.getRegister()));
      if (intervals.getType().isWide()) {
        used.add(realRegisterNumberFromAllocated(intervals.getRegister() + 1));
      }
    }
  }

  @Override
  public boolean argumentValueUsesHighRegister(Value value, int instructionNumber) {
    return isHighRegister(
        getRegisterForValue(value, instructionNumber) + value.requiredRegisters() - 1);
  }

  public int highestUsedRegister() {
    return registersUsed() - 1;
  }

  @Override
  public int registersUsed() {
    int numberOfRegister = maxRegisterNumber + 1 - NUMBER_OF_SENTINEL_REGISTERS;
    if (unusedRegisters != null) {
      return numberOfRegister - unusedRegisters[unusedRegisters.length - 1];
    }
    return numberOfRegister;
  }

  @Override
  public int getRegisterForValue(Value value, int instructionNumber) {
    if (value.isFixedRegisterValue()) {
      return realRegisterNumberFromAllocated(value.asFixedRegisterValue().getRegister());
    }
    LiveIntervals intervals = value.getLiveIntervals();
    if (intervals.hasSplits()) {
      intervals = intervals.getSplitCovering(instructionNumber);
    }
    return getRegisterForIntervals(intervals);
  }

  @Override
  public int getArgumentOrAllocateRegisterForValue(Value value, int instructionNumber) {
    if (value.isArgument()) {
      return getRegisterForIntervals(value.getLiveIntervals());
    }
    return getRegisterForValue(value, instructionNumber);
  }

  private ImmutableList<BasicBlock> computeLivenessInformation() {
    ImmutableList<BasicBlock> blocks = code.numberInstructions();
    liveAtEntrySets = code.computeLiveAtEntrySets();
    computeLiveRanges();
    return blocks;
  }

  private boolean performAllocationWithoutMoveInsertion(ArgumentReuseMode mode) {
    pinArgumentRegisters();
    return performLinearScan(mode);
  }

  private boolean performAllocation(ArgumentReuseMode mode) {
    boolean result = performAllocationWithoutMoveInsertion(mode);
    insertMoves();
    if (mode == ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE) {
      // Now that we know the max register number we can compute whether it is safe to use
      // argument registers in place. If it is, we redo move insertion to get rid of the moves
      // caused by splitting of the argument registers.
      if (unsplitArguments()) {
        removeSpillAndPhiMoves();
        insertMoves();
      }
    }
    return result;
  }

  // When argument register reuse is disallowed, we split argument values to make sure that
  // we can get the argument into low enough registers at uses that require low numbers. After
  // register allocation we can check if it is safe to just use the argument register itself
  // for all uses and thereby avoid moving argument values around.
  private boolean unsplitArguments() {
    boolean argumentRegisterUnsplit = false;
    Value current = preArgumentSentinelValue;
    while (current != null) {
      LiveIntervals intervals = current.getLiveIntervals();
      assert intervals.getRegisterLimit() == Constants.U16BIT_MAX;
      boolean canUseArgumentRegister = true;
      for (LiveIntervals child : intervals.getSplitChildren()) {
        if (child.getRegisterLimit() < highestUsedRegister()) {
          canUseArgumentRegister = false;
          break;
        }
      }
      if (canUseArgumentRegister) {
        argumentRegisterUnsplit = true;
        for (LiveIntervals child : intervals.getSplitChildren()) {
          child.clearRegisterAssignment();
          child.setRegister(intervals.getRegister());
          child.setSpilled(false);
        }
      }
      current = current.getNextConsecutive();
    }
    return argumentRegisterUnsplit;
  }

  private void removeSpillAndPhiMoves() {
    for (BasicBlock block : code.blocks) {
      InstructionListIterator it = block.listIterator();
      while (it.hasNext()) {
        Instruction instruction = it.next();
        if (isSpillInstruction(instruction)) {
          it.remove();
        }
      }
    }
  }

  private static boolean isSpillInstruction(Instruction instruction) {
    Value outValue = instruction.outValue();
    if (outValue != null && outValue.isFixedRegisterValue()) {
      // Only move and const number instructions are inserted for spill and phi moves. The
      // const number instructions are for values that can be rematerialized instead of
      // spilled.
      assert instruction.getNumber() == -1;
      assert instruction.isMove() || instruction.isConstNumber();
      assert !instruction.isDebugInstruction();
      return true;
    }
    return false;
  }

  private void clearRegisterAssignments() {
    freeRegisters.clear();
    maxRegisterNumber = 0;
    nextUnusedRegisterNumber = 0;
    active.clear();
    inactive.clear();
    unhandled.clear();
    for (LiveIntervals intervals : liveIntervals) {
      intervals.clearRegisterAssignment();
    }
  }

  /**
   * Get the register allocated to a given set of live intervals.
   */
  private int getRegisterForIntervals(LiveIntervals intervals) {
    int intervalsRegister = intervals.getRegister();
    return realRegisterNumberFromAllocated(intervalsRegister);
  }

  int unadjustedRealRegisterFromAllocated(int allocated) {
    assert allocated != NO_REGISTER;
    assert allocated >= 0;
    int register;
    if (allocated < numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS) {
      // For the |numberOfArguments| first registers map to the correct argument register.
      // Due to the sentinel register in front of the arguments, the register number returned is
      // the argument number starting from one.
      register = maxRegisterNumber - (numberOfArgumentRegisters - allocated)
          - NUMBER_OF_SENTINEL_REGISTERS;
    } else {
      // For everything else use the lower numbers.
      register = allocated - numberOfArgumentRegisters - NUMBER_OF_SENTINEL_REGISTERS;
    }
    return register;
  }

  int realRegisterNumberFromAllocated(int allocated) {
    int register = unadjustedRealRegisterFromAllocated(allocated);
    // Adjust for spill registers that turn out to be unused because the value can be
    // rematerialized instead of spilled.
    if (unusedRegisters != null) {
      return register - unusedRegisters[register];
    }
    return register;
  }

  private boolean isHighRegister(int register) {
    return register > Constants.U4BIT_MAX;
  }

  private boolean performLinearScan(ArgumentReuseMode mode) {
    unhandled.addAll(liveIntervals);
    LiveIntervals argumentInterval = preArgumentSentinelValue.getLiveIntervals();
    while (argumentInterval != null) {
      assert argumentInterval.getRegister() != NO_REGISTER;
      unhandled.remove(argumentInterval);
      if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
        // All the argument intervals are active in the beginning and have preallocated registers.
        active.add(argumentInterval);
      } else {
        // Treat the argument interval as spilled which will require a load to a different
        // register for all register-constrained usages.
        if (argumentInterval.getUses().size() > 1) {
          LiveIntervalsUse use = argumentInterval.firstUseWithConstraint();
          if (use != null) {
            LiveIntervals split;
            if (argumentInterval.numberOfUsesWithConstraint() == 1) {
              // If there is only one register-constrained use, split before
              // that one use.
              split = argumentInterval.splitBefore(use.getPosition());
            } else {
              // If there are multiple register-constrained users, split right after the definition
              // to make it more likely that arguments get in usable registers from the start.
              split = argumentInterval
                  .splitBefore(argumentInterval.getValue().definition.getNumber() + 1);
            }
            unhandled.add(split);
          }
        }
      }
      argumentInterval = argumentInterval.getNextConsecutive();
    }

    // We have to be careful when it comes to the register allocated for a move exception
    // instruction. For move exception instructions there is no place to put spill or
    // restore moves. The move exception instruction has to be the first instruction in a
    // catch handler.
    //
    // When we allow argument reuse we do not allow any splitting, therefore we cannot get into
    // trouble with move exception registers. When argument reuse is disallowed we block a fixed
    // register to be used only by move exception instructions.
    if (mode != ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
      // Force all move exception ranges to start out with the exception in a fixed register. Split
      // their live ranges which will force another register if used.
      int moveExceptionRegister = NO_REGISTER;
      List<LiveIntervals> moveExceptionIntervals = new ArrayList<>();
      boolean overlappingMoveExceptionIntervals = false;
      for (BasicBlock block : code.blocks) {
        for (Instruction instruction : block.getInstructions()) {
          if (instruction.isMoveException()) {
            hasDedicatedMoveExceptionRegister = true;
            Value exceptionValue = instruction.outValue();
            LiveIntervals intervals = exceptionValue.getLiveIntervals();
            unhandled.remove(intervals);
            if (moveExceptionRegister == NO_REGISTER) {
              moveExceptionRegister = getFreeConsecutiveRegisters(1);
            }
            intervals.setRegister(moveExceptionRegister);
            if (!overlappingMoveExceptionIntervals) {
              for (LiveIntervals other : moveExceptionIntervals) {
                overlappingMoveExceptionIntervals |= other.overlaps(intervals);
              }
            }
            moveExceptionIntervals.add(intervals);
          }
        }
      }
      if (overlappingMoveExceptionIntervals) {
        for (LiveIntervals intervals : moveExceptionIntervals) {
          if (intervals.getUses().size() > 1) {
            LiveIntervalsUse firstUse = intervals.getUses().pollFirst();
            LiveIntervalsUse secondUse = intervals.getUses().pollFirst();
            intervals.getUses().add(firstUse);
            intervals.getUses().add(secondUse);
            LiveIntervals split = intervals.splitBefore(secondUse.getPosition());
            unhandled.add(split);
          }
        }
      }
    }

    // Go through each unhandled live interval and find a register for it.
    while (!unhandled.isEmpty()) {
      LiveIntervals unhandledInterval = unhandled.poll();

      setHintForDestRegOfCheckCast(unhandledInterval);
      setHintToPromote2AddrInstruction(unhandledInterval);

      // If this interval value is the src of an argument move. Fix the registers for the
      // consecutive arguments now and add hints to the move sources. This looks forward
      // and propagate hints backwards to avoid many moves in connection with ranged invokes.
      allocateArgumentIntervalsWithSrc(unhandledInterval);
      if (unhandledInterval.getRegister() != NO_REGISTER) {
        // The value itself could be in the chain that has now gotten registers allocated.
        continue;
      }

      int start = unhandledInterval.getStart();
      // Check for active intervals that expired or became inactive.
      Iterator<LiveIntervals> activeIterator = active.iterator();
      while (activeIterator.hasNext()) {
        LiveIntervals activeIntervals = activeIterator.next();
        if (start >= activeIntervals.getEnd()) {
          activeIterator.remove();
          freeRegistersForIntervals(activeIntervals);
        } else if (!activeIntervals.overlapsPosition(start)) {
          activeIterator.remove();
          assert activeIntervals.getRegister() != NO_REGISTER;
          inactive.add(activeIntervals);
          freeRegistersForIntervals(activeIntervals);
        }
      }

      // Check for inactive intervals that expired or became reactivated.
      Iterator<LiveIntervals> inactiveIterator = inactive.iterator();
      while (inactiveIterator.hasNext()) {
        LiveIntervals inactiveIntervals = inactiveIterator.next();
        if (start >= inactiveIntervals.getEnd()) {
          inactiveIterator.remove();
        } else if (inactiveIntervals.overlapsPosition(start)) {
          inactiveIterator.remove();
          assert inactiveIntervals.getRegister() != NO_REGISTER;
          active.add(inactiveIntervals);
          takeRegistersForIntervals(inactiveIntervals);
        }
      }

      // Perform the actual allocation.
      if (unhandledInterval.isLinked() && !unhandledInterval.isArgumentInterval()) {
        allocateLinkedIntervals(unhandledInterval);
      } else {
        if (!allocateSingleInterval(unhandledInterval, mode)) {
          return false;
        }
      }
    }
    return true;
  }

  private void setHintForDestRegOfCheckCast(LiveIntervals unhandledInterval) {
    if (unhandledInterval.getHint() == null &&
        unhandledInterval.getValue().definition instanceof CheckCast) {
      CheckCast checkcast = unhandledInterval.getValue().definition.asCheckCast();
      Value checkcastInput = checkcast.inValues().get(0);
      assert checkcastInput != null;
      if (checkcastInput.getLiveIntervals() != null &&
          !checkcastInput.getLiveIntervals().overlaps(unhandledInterval) &&
          checkcastInput.getLocalInfo() == unhandledInterval.getValue().definition.getLocalInfo()) {
        unhandledInterval.setHint(checkcastInput.getLiveIntervals());
      }
    }
  }

  /*
   * This method tries to promote arithmetic binary instruction to use the 2Addr form.
   * To achieve this goal the output interval of the binary instruction is set with an hint
   * that is the left interval or the right interval if possible when intervals do not overlap.
   */
  private void setHintToPromote2AddrInstruction(LiveIntervals unhandledInterval) {
    if (unhandledInterval.getHint() == null &&
        unhandledInterval.getValue().definition instanceof ArithmeticBinop) {
      ArithmeticBinop binOp = unhandledInterval.getValue().definition.asArithmeticBinop();
      Value left = binOp.leftValue();
      assert left != null;
      if (left.getLiveIntervals() != null &&
          !left.getLiveIntervals().overlaps(unhandledInterval)) {
        unhandledInterval.setHint(left.getLiveIntervals());
      } else {
        Value right = binOp.rightValue();
        assert right != null;
        if (binOp.isCommutative() && right.getLiveIntervals() != null &&
            !right.getLiveIntervals().overlaps(unhandledInterval)) {
          unhandledInterval.setHint(right.getLiveIntervals());
        }
      }
    }
  }

  /**
   * Perform look-ahead and allocate registers for linked argument chains that have the argument
   * interval as an argument move source.
   *
   * <p>The end result of calling this method is that the argument intervals have registers
   * allocated and have been moved from unhandled to inactive. The move sources have their hints
   * updated. The rest of the register allocation state is unchanged.
   */
  private void allocateArgumentIntervalsWithSrc(LiveIntervals srcInterval) {
    Value value = srcInterval.getValue();
    for (Instruction instruction : value.uniqueUsers()) {
      // If there is a move user that is an argument move, we allocate the consecutive
      // registers for the argument intervals and propagate the selected registers back as
      // hints to the sources.
      if (instruction.isMove() && instruction.asMove().dest().isLinked()) {
        Move move = instruction.asMove();
        Value dest = move.dest();
        LiveIntervals destIntervals = dest.getLiveIntervals();
        if (destIntervals.getRegister() == NO_REGISTER) {
          // Save the current register allocation state so we can restore it at the end.
          TreeSet<Integer> savedFreeRegisters = new TreeSet<>(freeRegisters);
          int savedUnusedRegisterNumber = nextUnusedRegisterNumber;
          List<LiveIntervals> savedActive = new LinkedList<>(active);
          List<LiveIntervals> savedInactive = new LinkedList<>(inactive);

          // Add all the active intervals to the inactive set. When allocating linked intervals we
          // check all inactive intervals and exclude the registers for overlapping inactive
          // intervals.
          for (LiveIntervals active : active) {
            // TODO(ager): We could allow the use of all the currently active registers for the
            // ranged invoke (by adding the registers for all the active intervals to freeRegisters
            // here). That could lead to lower register pressure. However, it would also often mean
            // that we cannot allocate the right argument register to the current unhandled
            // interval. Size measurements on GMSCore indicate that blocking the current active
            // registers works the best for code size.
            if (active.isArgumentInterval()) {
              // Allow the ranged invoke to use argument registers if free. This improves register
              // allocation for brigde methods that forwards all of their arguments after check-cast
              // checks on their types.
              freeRegistersForIntervals(active);
            }
            inactive.add(active);
          }

          // Allocate the argument intervals.
          unhandled.remove(destIntervals);
          allocateLinkedIntervals(destIntervals);
          // Restore the register allocation state.
          freeRegisters = savedFreeRegisters;
          for (int i = savedUnusedRegisterNumber; i < nextUnusedRegisterNumber; i++) {
            freeRegisters.add(i);
          }
          active = savedActive;
          inactive = savedInactive;
          // Move all the argument intervals to the inactive set.
          LiveIntervals current = destIntervals.getStartOfConsecutive();
          while (current != null) {
            assert !inactive.contains(current);
            assert !active.contains(current);
            assert !unhandled.contains(current);
            inactive.add(current);
            current = current.getNextConsecutive();
          }
        }
      }
    }
  }

  private void allocateLinkedIntervals(LiveIntervals unhandledInterval) {
    // Exclude the registers that overlap the start of one of the live ranges we are
    // going to assign registers to now.
    LiveIntervals current = unhandledInterval.getStartOfConsecutive();
    Set<Integer> excludedRegisters = new HashSet<>();
    while (current != null) {
      for (LiveIntervals inactiveIntervals : inactive) {
        if (inactiveIntervals.overlaps(current)) {
          excludeRegistersForInterval(inactiveIntervals, excludedRegisters);
        }
      }
      current = current.getNextConsecutive();
    }
    // Select registers.
    current = unhandledInterval.getStartOfConsecutive();
    int numberOfRegister = current.numberOfConsecutiveRegisters();
    int firstRegister = getFreeConsecutiveRegisters(numberOfRegister);
    for (int i = 0; i < numberOfRegister; i++) {
      assert current != null;
      current.setRegister(firstRegister + i);
      if (current.getType().isWide()) {
        assert i < numberOfRegister;
        i++;
      }
      // Propagate hints to the move sources.
      Value value = current.getValue();
      if (!value.isPhi() && value.definition.isMove()) {
        Move move = value.definition.asMove();
        LiveIntervals intervals = move.src().getLiveIntervals();
        intervals.setHint(current);
      }
      if (current != unhandledInterval) {
        // Only the start of unhandledInterval has been reached at this point. All other live
        // intervals in the chain have been assigned registers but their start has not yet been
        // reached. Therefore, they belong in the inactive set.
        unhandled.remove(current);
        assert current.getRegister() != NO_REGISTER;
        inactive.add(current);
        freeRegistersForIntervals(current);
      }
      current = current.getNextConsecutive();
    }
    assert current == null;
    assert unhandledInterval.getRegister() != NO_REGISTER;
    active.add(unhandledInterval);
    // Include the registers for inactive ranges that we had to exclude for this allocation.
    freeRegisters.addAll(excludedRegisters);
  }

  // Update the information about used registers when |register| has been selected for use.
  private void updateRegisterState(int register, boolean needsRegisterPair) {
    int maxRegister = register + (needsRegisterPair ? 1 : 0);
    if (maxRegister >= nextUnusedRegisterNumber) {
      nextUnusedRegisterNumber = maxRegister + 1;
    }
    maxRegisterNumber = Math.max(maxRegisterNumber, maxRegister);
  }

  private int getSpillRegister(LiveIntervals intervals) {
    int registerNumber = nextUnusedRegisterNumber++;
    maxRegisterNumber = registerNumber;
    if (intervals.getType().isWide()) {
      nextUnusedRegisterNumber++;
      maxRegisterNumber++;
    }
    return registerNumber;
  }

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

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

  // Art had a bug (b/68761724) for Android N and O in the arm32 interpreter
  // where an aget-wide instruction using the same register for the array
  // and the first register of the result could lead to the wrong exception
  // being thrown on out of bounds.
  //
  // For instructions of the form 'aget-wide regA, regA, regB' where
  // regB is out of bounds of non-null array in regA, Art would throw a null
  // pointer exception instead of an ArrayIndexOutOfBounds exception.
  //
  // We work around that bug by disallowing aget-wide with the same array
  // and result register.
  private boolean needsArrayGetWideWorkaround(LiveIntervals intervals) {
    if (options.canUseSameArrayAndResultRegisterInArrayGetWide()) {
      return false;
    }
    if (intervals.requiredRegisters() == 1) {
      // Not the live range for a wide value and therefore not the output of aget-wide.
      return false;
    }
    if (intervals.getValue().isPhi()) {
      // If this writes a new register pair it will be via a move and not an aget-wide operation.
      return false;
    }
    if (intervals.getSplitParent() != intervals) {
      // This is a split of a parent interval and therefore if this leads to a write of a
      // register pair it will be via a move and not an aget-wide operation.
      return false;
    }
    Instruction definition = intervals.getValue().definition;
    return definition.isArrayGet() && definition.asArrayGet().outType().isWide();
  }

  // Is the array-get array register the same as the first register we are
  // allocating for the result?
  private boolean isArrayGetArrayRegister(LiveIntervals intervals, int register) {
    assert needsArrayGetWideWorkaround(intervals);
    Value array = intervals.getValue().definition.asArrayGet().array();
    int arrayReg =
        array.getLiveIntervals().getSplitCovering(intervals.getStart()).getRegister();
    assert arrayReg != NO_REGISTER;
    return arrayReg == register;
  }

  private boolean needsSingleResultOverlappingLongOperandsWorkaround(LiveIntervals intervals) {
    if (!options.canHaveCmpLongBug()) {
      return false;
    }
    if (intervals.requiredRegisters() == 2) {
      // Not the live range for a single value and therefore not the output of cmp-long.
      return false;
    }
    if (intervals.getValue().isPhi()) {
      // If this writes a new register pair it will be via a move and not an cmp-long operation.
      return false;
    }
    if (intervals.getSplitParent() != intervals) {
      // This is a split of a parent interval and therefore if this leads to a write of a
      // register it will be via a move and not an cmp-long operation.
      return false;
    }
    Instruction definition = intervals.getValue().definition;
    return definition.isCmp() && definition.asCmp().inValues().get(0).outType().isWide();
  }

  private boolean singleOverlappingLong(int register1, int register2) {
    return register1 == register2 || register1 == (register2 + 1);
  }

  // Is one of the cmp-long argument registers the same as the register we are
  // allocating for the result?
  private boolean isSingleResultOverlappingLongOperands(LiveIntervals intervals, int register) {
    assert needsSingleResultOverlappingLongOperandsWorkaround(intervals);
    Value left = intervals.getValue().definition.asCmp().leftValue();
    Value right = intervals.getValue().definition.asCmp().rightValue();
    int leftReg =
        left.getLiveIntervals().getSplitCovering(intervals.getStart()).getRegister();
    int rightReg =
        right.getLiveIntervals().getSplitCovering(intervals.getStart()).getRegister();
    assert leftReg != NO_REGISTER;
    assert rightReg != NO_REGISTER;
    return singleOverlappingLong(register, leftReg) || singleOverlappingLong(register, rightReg);
  }

  // The dalvik jit had a bug where the long operations add, sub, or, xor and and would write
  // the first part of the result long before reading the second part of the input longs.
  //
  // Therefore, on dalvik, we cannot generate code with overlapping long registers such as:
  //
  // add-long v3, v0, v2
  //
  // Dalvik would add v0 and v2 and write that to v3. It would then read v1 and v3 and produce
  // the wrong result.
  private boolean needsLongResultOverlappingLongOperandsWorkaround(LiveIntervals intervals) {
    if (!options.canHaveOverlappingLongRegisterBug()) {
      return false;
    }
    if (intervals.requiredRegisters() == 1) {
      // Not the live range for a wide value.
      return false;
    }
    if (intervals.getValue().isPhi()) {
      // If this writes a new register pair it will be via a move and not a long operation.
      return false;
    }
    if (intervals.getSplitParent() != intervals) {
      // This is a split of the parent interval and therefore if this leads to a write of a
      // register pair it will be via a move and not a long operation.
      return false;
    }
    Instruction definition = intervals.getValue().definition;
    if (definition.isArithmeticBinop() &&
        definition.asArithmeticBinop().getNumericType() == NumericType.LONG) {
      return definition instanceof Add || definition instanceof Sub;
    }
    if (definition.isLogicalBinop() &&
        definition.asLogicalBinop().getNumericType() == NumericType.LONG) {
      return definition instanceof Or || definition instanceof Xor || definition instanceof And;
    }
    return false;
  }

  private boolean longOverlappingLong(int register1, int register2) {
    return register1 == register2 || register1 == (register2 + 1)
        || (register1 + 1) == register2 || (register1 + 1) == (register2 + 1);
  }

  private boolean isLongResultOverlappingLongOperands(
      LiveIntervals unhandledInterval, int register) {
    assert needsLongResultOverlappingLongOperandsWorkaround(unhandledInterval);
    Value left = unhandledInterval.getValue().definition.asBinop().leftValue();
    Value right = unhandledInterval.getValue().definition.asBinop().rightValue();
    int leftReg =
        left.getLiveIntervals().getSplitCovering(unhandledInterval.getStart()).getRegister();
    int rightReg =
        right.getLiveIntervals().getSplitCovering(unhandledInterval.getStart()).getRegister();
    assert leftReg != NO_REGISTER && rightReg != NO_REGISTER;
    // The dalvik bug is actually only for overlap with the second operand, For now we
    // make sure that there is no overlap with either register of either operand. Some vendor
    // optimization have bees seen to need this more conservative check.
    return longOverlappingLong(register, leftReg) || longOverlappingLong(register, rightReg);
  }

  private boolean allocateSingleInterval(LiveIntervals unhandledInterval, ArgumentReuseMode mode) {
    int registerConstraint = unhandledInterval.getRegisterLimit();
    assert registerConstraint <= Constants.U16BIT_MAX;

    assert unhandledInterval.requiredRegisters() <= 2;
    boolean needsRegisterPair = unhandledInterval.requiredRegisters() == 2;

    // Just use the argument register if an argument split has no register constraint. That will
    // avoid move generation for the argument.
    if (registerConstraint == Constants.U16BIT_MAX && unhandledInterval.isArgumentInterval()) {
      int argumentRegister = unhandledInterval.getSplitParent().getRegister();
      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, argumentRegister);
      return true;
    }

    if (registerConstraint < Constants.U16BIT_MAX) {
      // We always have argument sentinels that will not actually occupy registers. Therefore, we
      // allow the use of NUMBER_OF_SENTINEL_REGISTERS more than the limit.
      registerConstraint += NUMBER_OF_SENTINEL_REGISTERS;
      if (mode == ArgumentReuseMode.DISALLOW_ARGUMENT_REUSE) {
        // We know that none of the argument registers will be reused. Therefore, we allow the
        // use of number of arguments more registers. (We will never use number of arguments +
        // number of sentinel registers of them.)
        registerConstraint += numberOfArgumentRegisters;
      }
    }

    // Set all free positions for possible registers to max integer.
    RegisterPositions freePositions = new RegisterPositions(registerConstraint + 1);

    if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
      // The sentinel registers cannot be used and we block them.
      freePositions.set(0, 0);
      if (options.debug && !code.method.accessFlags.isStatic()) {
        // If we are generating debug information, we pin the this value register since the
        // debugger expects to always be able to find it in the input register.
        assert numberOfArgumentRegisters > 0;
        assert preArgumentSentinelValue.getNextConsecutive().requiredRegisters() == 1;
        freePositions.set(1, 0);
      }
      int lastSentinelRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS - 1;
      if (lastSentinelRegister <= registerConstraint) {
        freePositions.set(lastSentinelRegister, 0);
      }
    } else {
      // Argument reuse is not allowed and we block all the argument registers so that
      // arguments are never free.
      for (int i = 0; i < numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS; i++) {
        if (i <= registerConstraint) {
          freePositions.set(i, 0);
        }
      }
    }

    // If there is a move exception instruction we block register 0 as the move exception
    // register. If we cannot find a free valid register for the move exception value we have no
    // place to put a spill move (because the move exception instruction has to be the
    // first instruction in the handler block).
    if (hasDedicatedMoveExceptionRegister) {
      int moveExceptionRegister = numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS;
      if (moveExceptionRegister <= registerConstraint) {
        freePositions.set(moveExceptionRegister, 0);
      }
    }

    // All the active intervals are not free at this point.
    for (LiveIntervals intervals : active) {
      int activeRegister = intervals.getRegister();
      if (activeRegister <= registerConstraint) {
        for (int i = 0; i < intervals.requiredRegisters(); i++) {
          if (activeRegister + i <= registerConstraint) {
            freePositions.set(activeRegister + i, 0);
          }
        }
      }
    }

    // The register for inactive intervals that overlap with this interval are free until
    // the next overlap.
    for (LiveIntervals intervals : inactive) {
      int inactiveRegister = intervals.getRegister();
      if (inactiveRegister <= registerConstraint && unhandledInterval.overlaps(intervals)) {
        int nextOverlap = unhandledInterval.nextOverlap(intervals);
        for (int i = 0; i < intervals.requiredRegisters(); i++) {
          int register = inactiveRegister + i;
          if (register <= registerConstraint) {
            int unhandledStart = toInstructionPosition(unhandledInterval.getStart());
            if (nextOverlap == unhandledStart) {
              // Don't use the register for an inactive interval that is only free until the next
              // instruction. We can get into this situation when unhandledInterval starts at a
              // gap position.
              freePositions.set(register, 0);
            } else {
              if (nextOverlap < freePositions.get(register)) {
                freePositions.set(register, nextOverlap, intervals);
              }
            }
          }
        }
      }
    }

    // Attempt to use register hints.
    if (useRegisterHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair)) {
      return true;
    }

    // Get the register (pair) that is free the longest. That is the register with the largest
    // free position.
    int candidate = getLargestValidCandidate(
        unhandledInterval, registerConstraint, needsRegisterPair, freePositions, Type.ANY);

    // It is not always possible to find a largest valid candidate. If none of the usable register
    // are free we typically get the last candidate. However, if that candidate has to be
    // discarded in order to workaround bugs we get REGISTER_CANDIDATE_NOT_FOUND. In both cases
    // we need to spill a valid candidate. That path is triggered when largestFreePosition is 0.
    int largestFreePosition = 0;
    if (candidate != REGISTER_CANDIDATE_NOT_FOUND) {
      largestFreePosition = freePositions.get(candidate);
      if (needsRegisterPair) {
        largestFreePosition = Math.min(largestFreePosition, freePositions.get(candidate + 1));
      }
    }

    // Determine what to do based on how long the selected candidate is free.
    if (largestFreePosition == 0) {
      // Not free. We need to spill.
      if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
        // No spilling is allowed when we allow argument reuse. Bailout and start over with
        // argument reuse disallowed.
        return false;
      }
      // If the first use for these intervals is unconstrained, just spill this interval instead
      // of finding another candidate to spill via allocateBlockedRegister.
      if (!unhandledInterval.getUses().first().hasConstraint()) {
        int nextConstrainedPosition = unhandledInterval.firstUseWithConstraint().getPosition();
        int register;
        // Arguments are always in the argument registers, so for arguments just use that register
        // for the unconstrained prefix. For everything else, get a spill register.
        if (unhandledInterval.isArgumentInterval()) {
          register = unhandledInterval.getSplitParent().getRegister();
        } else {
          register = getSpillRegister(unhandledInterval);
        }
        LiveIntervals split = unhandledInterval.splitBefore(nextConstrainedPosition);
        assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
        unhandled.add(split);
      } else {
        allocateBlockedRegister(unhandledInterval);
      }
    } else if (largestFreePosition >= unhandledInterval.getEnd()) {
      // Free for the entire interval. Allocate the register.
      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
    } else {
      if (mode == ArgumentReuseMode.ALLOW_ARGUMENT_REUSE) {
        // No splitting is allowed when we allow argument reuse. Bailout and start over with
        // argument reuse disallowed.
        return false;
      }
      // The candidate is free for the beginning of an interval. We split the interval
      // and use the register for as long as we can.
      LiveIntervals split = unhandledInterval.splitBefore(largestFreePosition);
      assert split != unhandledInterval;
      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, candidate);
      unhandled.add(split);
    }
    return true;
  }

  // Attempt to use the register hint for the unhandled interval in order to avoid generating
  // moves.
  private boolean useRegisterHint(LiveIntervals unhandledInterval, int registerConstraint,
      RegisterPositions freePositions, boolean needsRegisterPair) {
    // If the unhandled interval has a hint we give it that register if it is available without
    // spilling. For phis we also use the hint before looking at the operand registers. The
    // phi could have a hint from an argument moves which it seems more important to honor in
    // practice.
    LiveIntervals hint = unhandledInterval.getHint();
    if (hint != null) {
      int register = hint.getRegister();
      if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair,
          register)) {
        return true;
      }
    }

    // If there is no hint or it cannot be applied we search for a good register for phis using
    // the registers assigned to the operand intervals. We determine all the registers used
    // for operands and try them one by one based on frequency.
    Value value = unhandledInterval.getValue();
    if (value.isPhi()) {
      Phi phi = value.asPhi();
      Multiset<Integer> map = HashMultiset.create();
      List<Value> operands = phi.getOperands();
      for (int i = 0; i < operands.size(); i++) {
        LiveIntervals intervals = operands.get(i).getLiveIntervals();
        if (intervals.hasSplits()) {
          BasicBlock pred = phi.getBlock().getPredecessors().get(i);
          intervals = intervals.getSplitCovering(pred.exit().getNumber());
        }
        int operandRegister = intervals.getRegister();
        if (operandRegister != NO_REGISTER) {
          map.add(operandRegister);
        }
      }
      for (Multiset.Entry<Integer> entry : Multisets.copyHighestCountFirst(map).entrySet()) {
        int register = entry.getElement();
        if (tryHint(unhandledInterval, registerConstraint, freePositions, needsRegisterPair,
            register)) {
          return true;
        }
      }
    }

    return false;
  }

  // Attempt to allocate the hint register to the unhandled intervals.
  private boolean tryHint(LiveIntervals unhandledInterval, int registerConstraint,
      RegisterPositions freePositions, boolean needsRegisterPair, int register) {
    // At some point after the hint has been added, the register allocator can
    // decide to redo allocation for the hint interval. In that case, the hint will be
    // reset to NO_REGISTER and provides no hinting info.
    if (register == NO_REGISTER) {
      return false;
    }
    if (register + (needsRegisterPair ? 1 : 0) <= registerConstraint) {
      int freePosition = freePositions.get(register);
      if (needsRegisterPair) {
        freePosition = Math.min(freePosition, freePositions.get(register + 1));
      }
      if (freePosition >= unhandledInterval.getEnd()) {
        // Check for overlapping long registers issue.
        if (needsLongResultOverlappingLongOperandsWorkaround(unhandledInterval) &&
            isLongResultOverlappingLongOperands(unhandledInterval, register)) {
          return false;
        }
        // Check for aget-wide bug in recent Art VMs.
        if (needsArrayGetWideWorkaround(unhandledInterval) &&
            isArrayGetArrayRegister(unhandledInterval, register)) {
          return false;
        }
        assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, register);
        return true;
      }
    }
    return false;
  }

  private void assignRegister(LiveIntervals intervals, int register) {
    intervals.setRegister(register);
    updateRegisterHints(intervals);
  }

  private void updateRegisterHints(LiveIntervals intervals) {
    Value value = intervals.getValue();
    // If the value flows into a phi, set the hint for all the operand splits that flow into the
    // phi and do not have hints yet.
    for (Phi phi : value.uniquePhiUsers()) {
      LiveIntervals phiIntervals = phi.getLiveIntervals();
      if (phiIntervals.getHint() == null) {
        for (int i = 0; i < phi.getOperands().size(); i++) {
          Value operand = phi.getOperand(i);
          LiveIntervals operandIntervals = operand.getLiveIntervals();
          BasicBlock pred = phi.getBlock().getPredecessors().get(i);
          operandIntervals = operandIntervals.getSplitCovering(pred.exit().getNumber());
          if (operandIntervals.getHint() == null) {
            operandIntervals.setHint(intervals);
          }
        }
      }
    }
    // If the value is a phi and we are at the start of the interval, we set the register as
    // the hint for all of the operand splits flowing into the phi. We set the hint no matter
    // if there is already a hint. We know the register for the phi and want as many operands
    // as possible to be allocated the same register to avoid phi moves.
    if (value.isPhi() && intervals.getSplitParent() == intervals) {
      Phi phi = value.asPhi();
      BasicBlock block = phi.getBlock();
      for (int i = 0; i < phi.getOperands().size(); i++) {
        Value operand = phi.getOperand(i);
        BasicBlock pred = block.getPredecessors().get(i);
        LiveIntervals operandIntervals =
            operand.getLiveIntervals().getSplitCovering(pred.exit().getNumber());
        operandIntervals.setHint(intervals);
      }
    }
  }

  private void assignRegisterToUnhandledInterval(
      LiveIntervals unhandledInterval, boolean needsRegisterPair, int register) {
    assignRegister(unhandledInterval, register);
    takeRegistersForIntervals(unhandledInterval);
    updateRegisterState(register, needsRegisterPair);
    active.add(unhandledInterval);
  }

  private int getLargestCandidate(int registerConstraint, RegisterPositions freePositions,
      boolean needsRegisterPair, RegisterPositions.Type type) {
    int candidate = REGISTER_CANDIDATE_NOT_FOUND;
    int largest = -1;

    for (int i = 0; i <= registerConstraint; i++) {
      if (!freePositions.hasType(i, type)) {
        continue;
      }
      int freePosition = freePositions.get(i);
      if (needsRegisterPair) {
        if (i >= registerConstraint) {
          break;
        }
        freePosition = Math.min(freePosition, freePositions.get(i + 1));
      }
      if (freePosition > largest) {
        candidate = i;
        largest = freePosition;
        if (largest == Integer.MAX_VALUE) {
          break;
        }
      }
    }
    return candidate;
  }

  private int getLargestValidCandidate(LiveIntervals unhandledInterval, int registerConstraint,
      boolean needsRegisterPair, RegisterPositions freePositions, RegisterPositions.Type type) {
    int candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
    if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
      return candidate;
    }
    if (needsLongResultOverlappingLongOperandsWorkaround(unhandledInterval)) {
      int lastCandidate = candidate;
      while (isLongResultOverlappingLongOperands(unhandledInterval, candidate)) {
        // Make the overlapping register unavailable for allocation and try again.
        freePositions.set(candidate, 0);
        candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
        // If there are only invalid candidates of the give type we will end up with the same
        // candidate returned again once we have tried them all. In that case we didn't find a
        // valid register candidate and we need to broaden the search to other types.
        if (lastCandidate == candidate) {
          return REGISTER_CANDIDATE_NOT_FOUND;
        }
        lastCandidate = candidate;
      }
    }
    if (needsSingleResultOverlappingLongOperandsWorkaround(unhandledInterval)) {
      int lastCandidate = candidate;
      while (isSingleResultOverlappingLongOperands(unhandledInterval, candidate)) {
        // Make the overlapping register unavailable for allocation and try again.
        freePositions.set(candidate, 0);
        candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
        // If there are only invalid candidates of the give type we will end up with the same
        // candidate returned again once we have tried them all. In that case we didn't find a
        // valid register candidate and we need to broaden the search to other types.
        if (lastCandidate == candidate) {
          return REGISTER_CANDIDATE_NOT_FOUND;
        }
        lastCandidate = candidate;
      }
    }
    if (needsArrayGetWideWorkaround(unhandledInterval)) {
      int lastCandidate = candidate;
      while (isArrayGetArrayRegister(unhandledInterval, candidate)) {
        // Make the overlapping register unavailable for allocation and try again.
        freePositions.set(candidate, 0);
        candidate = getLargestCandidate(registerConstraint, freePositions, needsRegisterPair, type);
        // If there are only invalid candidates of the give type we will end up with the same
        // candidate returned again once we have tried them all. In that case we didn't find a
        // valid register candidate and we need to broaden the search to other types.
        if (lastCandidate == candidate) {
          return REGISTER_CANDIDATE_NOT_FOUND;
        }
        lastCandidate = candidate;
      }
    }
    return candidate;
  }

  private void allocateBlockedRegister(LiveIntervals unhandledInterval) {
    int registerConstraint = unhandledInterval.getRegisterLimit();
    if (registerConstraint < Constants.U16BIT_MAX) {
      // We always have argument sentinels that will not actually occupy registers. Therefore, we
      // allow the use of NUMBER_OF_SENTINEL_REGISTERS more than the limit. Additionally, we never
      // reuse argument registers and therefore allow the use of numberOfArgumentRegisters as well.
      registerConstraint += numberOfArgumentRegisters;
      registerConstraint += NUMBER_OF_SENTINEL_REGISTERS;
    }

    // Initialize all candidate registers to Integer.MAX_VALUE.
    RegisterPositions usePositions = new RegisterPositions(registerConstraint + 1);
    RegisterPositions blockedPositions = new RegisterPositions(registerConstraint + 1);

    // Compute next use location for all currently active registers.
    for (LiveIntervals intervals : active) {
      int activeRegister = intervals.getRegister();
      if (activeRegister <= registerConstraint) {
        for (int i = 0; i < intervals.requiredRegisters(); i++) {
          if (activeRegister + i <= registerConstraint) {
            int unhandledStart = unhandledInterval.getStart();
            usePositions.set(
                activeRegister + i, intervals.firstUseAfter(unhandledStart), intervals);
          }
        }
      }
    }

    // Compute next use location for all inactive registers that overlaps the unhandled interval.
    for (LiveIntervals intervals : inactive) {
      int inactiveRegister = intervals.getRegister();
      if (inactiveRegister <= registerConstraint && intervals.overlaps(unhandledInterval)) {
        for (int i = 0; i < intervals.requiredRegisters(); i++) {
          if (inactiveRegister + i <= registerConstraint) {
            int firstUse = intervals.firstUseAfter(unhandledInterval.getStart());
            if (firstUse < usePositions.get(inactiveRegister + i)) {
              usePositions.set(inactiveRegister + i, firstUse, intervals);
            }
          }
        }
      }
    }

    // Disallow the reuse of argument registers by always treating them as being used
    // at instruction number 0.
    for (int i = 0; i < numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS; i++) {
      usePositions.set(i, 0);
    }

    // Disallow reuse of the move exception register if we have reserved one.
    if (hasDedicatedMoveExceptionRegister) {
      usePositions.set(numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS, 0);
    }

    // Treat active linked argument intervals as pinned. They cannot be given another register
    // at their uses.
    blockLinkedRegisters(active, unhandledInterval, registerConstraint, usePositions,
        blockedPositions);

    // Treat inactive linked argument intervals as pinned. They cannot be given another register
    // at their uses.
    blockLinkedRegisters(inactive, unhandledInterval, registerConstraint, usePositions,
        blockedPositions);

    // Get the register (pair) that has the highest use position.
    boolean needsRegisterPair = unhandledInterval.requiredRegisters() == 2;

    // First look for a candidate that can be rematerialized.
    int candidate = getLargestValidCandidate(unhandledInterval, registerConstraint,
        needsRegisterPair, usePositions, Type.CONST_NUMBER);
    if (candidate != Integer.MAX_VALUE) {
      // Look for a non-const, non-monitor candidate.
      int otherCandidate = getLargestValidCandidate(
          unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.OTHER);
      if (otherCandidate == Integer.MAX_VALUE || candidate == REGISTER_CANDIDATE_NOT_FOUND) {
        candidate = otherCandidate;
      } else {
        int largestConstUsePosition =
            getLargestPosition(usePositions, candidate, needsRegisterPair);
        if (largestConstUsePosition - MIN_CONSTANT_FREE_FOR_POSITIONS <
            unhandledInterval.getStart()) {
          // The candidate that can be rematerialized has a live range too short to use it.
          candidate = otherCandidate;
        }
      }
      // If looking at constants and non-monitor registers did not find a valid spill candidate
      // we allow ourselves to look at monitor spill candidates as well. Registers holding objects
      // used as monitors should not be spilled if we can avoid it. Spilling them can lead
      // to Art lock verification issues.
      if (candidate == REGISTER_CANDIDATE_NOT_FOUND) {
        candidate = getLargestValidCandidate(
            unhandledInterval, registerConstraint, needsRegisterPair, usePositions, Type.MONITOR);
      }
    }

    int largestUsePosition = getLargestPosition(usePositions, candidate, needsRegisterPair);
    int blockedPosition = getBlockedPosition(blockedPositions, candidate, needsRegisterPair);

    if (largestUsePosition < unhandledInterval.getFirstUse()) {
      // All active and inactive intervals are used before current. Therefore, it is best to spill
      // current itself.
      int splitPosition = unhandledInterval.getFirstUse();
      LiveIntervals split = unhandledInterval.splitBefore(splitPosition);
      assert split != unhandledInterval;
      int registerNumber = getSpillRegister(unhandledInterval);
      assignRegisterToUnhandledInterval(unhandledInterval, needsRegisterPair, registerNumber);
      unhandledInterval.setSpilled(true);
      unhandled.add(split);
    } else if (blockedPosition > unhandledInterval.getEnd()) {
      // Spilling can make a register available for the entire interval.
      assignRegisterAndSpill(unhandledInterval, needsRegisterPair, candidate);
    } else {
      // Spilling only makes a register available for the first part of current.
      LiveIntervals splitChild = unhandledInterval.splitBefore(blockedPosition);
      unhandled.add(splitChild);
      assignRegisterAndSpill(unhandledInterval, needsRegisterPair, candidate);
    }
  }

  private int getLargestPosition(RegisterPositions usePositions, int register,
      boolean needsRegisterPair) {
    int largestUsePosition = usePositions.get(register);

    if (needsRegisterPair) {
      largestUsePosition = Math.min(largestUsePosition, usePositions.get(register + 1));
    }

    return largestUsePosition;
  }

  private int getBlockedPosition(RegisterPositions blockedPositions, int register,
      boolean needsRegisterPair) {
    int blockedPosition = blockedPositions.get(register);

    if (needsRegisterPair) {
      blockedPosition = Math.min(blockedPosition, blockedPositions.get(register + 1));
    }

    return blockedPosition;
  }

  private void assignRegisterAndSpill(
      LiveIntervals unhandledInterval,
      boolean needsRegisterPair,
      int candidate) {
    assignRegister(unhandledInterval, candidate);
    updateRegisterState(candidate, needsRegisterPair);
    // Split and spill intersecting active intervals for this register.
    spillOverlappingActiveIntervals(unhandledInterval, needsRegisterPair, candidate);
    takeRegistersForIntervals(unhandledInterval);
    active.add(unhandledInterval);
    // Split all overlapping inactive intervals for this register. They need to have a new
    // register assigned at the next use.
    splitOverlappingInactiveIntervals(unhandledInterval, needsRegisterPair, candidate);
  }

  protected void splitOverlappingInactiveIntervals(
      LiveIntervals unhandledInterval,
      boolean needsRegisterPair,
      int candidate) {
    List<LiveIntervals> newInactive = new ArrayList<>();
    Iterator<LiveIntervals> inactiveIterator = inactive.iterator();
    while (inactiveIterator.hasNext()) {
      LiveIntervals intervals = inactiveIterator.next();
      if ((intervals.usesRegister(candidate) ||
          (needsRegisterPair && intervals.usesRegister(candidate + 1))) &&
          intervals.overlaps(unhandledInterval)) {
        if (intervals.isLinked() && !intervals.isArgumentInterval()) {
          // If the inactive register is linked but not an argument, it needs to get the
          // same register again at the next use after the start of the unhandled interval.
          // If there are no such uses, we can use a different register for the remainder
          // of the inactive interval and therefore do not have to split here.
          int nextUsePosition = intervals.firstUseAfter(unhandledInterval.getStart());
          if (nextUsePosition != Integer.MAX_VALUE) {
            LiveIntervals split = intervals.splitBefore(nextUsePosition);
            split.setRegister(intervals.getRegister());
            newInactive.add(split);
          }
        }
        if (intervals.getStart() > unhandledInterval.getStart()) {
          // The inactive live intervals hasn't started yet. Clear the temporary register
          // assignment and move back to unhandled for register reassignment.
          intervals.clearRegisterAssignment();
          inactiveIterator.remove();
          unhandled.add(intervals);
        } else {
          // The inactive live intervals is in a live range hole. Split the interval and
          // put the ranges after the hole into the unhandled set for register reassignment.
          LiveIntervals split = intervals.splitBefore(unhandledInterval.getStart());
          unhandled.add(split);
        }
      }
    }
    inactive.addAll(newInactive);
  }

  private void spillOverlappingActiveIntervals(
      LiveIntervals unhandledInterval,
      boolean needsRegisterPair,
      int candidate) {
    List<LiveIntervals> newActive = new ArrayList<>();
    Iterator<LiveIntervals> activeIterator = active.iterator();
    while (activeIterator.hasNext()) {
      LiveIntervals intervals = activeIterator.next();
      if (intervals.usesRegister(candidate) ||
          (needsRegisterPair && intervals.usesRegister(candidate + 1))) {
        activeIterator.remove();
        freeRegistersForIntervals(intervals);
        LiveIntervals splitChild = intervals.splitBefore(unhandledInterval.getStart());
        int registerNumber = getSpillRegister(intervals);
        assignRegister(splitChild, registerNumber);
        splitChild.setSpilled(true);
        takeRegistersForIntervals(splitChild);
        assert splitChild.getRegister() != NO_REGISTER;
        assert intervals.getRegister() != NO_REGISTER;
        newActive.add(splitChild);
        // If the constant is split before its first actual use, mark the constant as being
        // spilled. That will allows us to remove it afterwards if it is rematerializable.
        if (intervals.getValue().isConstNumber()
            && intervals.getStart() == intervals.getValue().definition.getNumber()
            && intervals.getUses().size() == 1) {
          intervals.setSpilled(true);
        }
        if (splitChild.getUses().size() > 0) {
          if (splitChild.isLinked() && !splitChild.isArgumentInterval()) {
            // Spilling a value with a pinned register. We need to move back at the next use.
            LiveIntervals splitOfSplit = splitChild.splitBefore(splitChild.getFirstUse());
            splitOfSplit.setRegister(intervals.getRegister());
            inactive.add(splitOfSplit);
          } else if (intervals.getValue().isConstNumber()) {
            // TODO(ager): Do this for all constants. Currently we only rematerialize const
            // number and therefore we only do it for numbers at this point.
            splitRangesForSpilledConstant(splitChild, registerNumber);
          } else if (intervals.isArgumentInterval()) {
            splitRangesForSpilledArgument(splitChild);
          } else {
            splitRangesForSpilledInterval(splitChild, registerNumber);
          }
        }
      }
    }
    active.addAll(newActive);
  }

  private void splitRangesForSpilledArgument(LiveIntervals spilled) {
    assert spilled.isSpilled();
    assert spilled.isArgumentInterval();
    // Argument intervals are spilled to the original argument register. We don't know what
    // that is yet, and therefore we split before the next use to make sure we get a usable
    // register at the next use.
    if (!spilled.getUses().isEmpty()) {
      LiveIntervals split = spilled.splitBefore(spilled.getUses().first().getPosition());
      unhandled.add(split);
    }
  }

  private void splitRangesForSpilledInterval(LiveIntervals spilled, int registerNumber) {
    // Spilling a non-pinned, non-rematerializable value. We use the value in the spill
    // register for as long as possible to avoid further moves.
    assert spilled.isSpilled();
    assert !spilled.getValue().isConstNumber();
    assert !spilled.isLinked() || spilled.isArgumentInterval();
    if (spilled.isArgumentInterval()) {
      registerNumber = Constants.U16BIT_MAX;
    }
    LiveIntervalsUse firstUseWithLowerLimit = null;
    boolean hasUsesBeforeFirstUseWithLowerLimit = false;
    for (LiveIntervalsUse use : spilled.getUses()) {
      if (registerNumber > use.getLimit()) {
        firstUseWithLowerLimit = use;
        break;
      } else {
        hasUsesBeforeFirstUseWithLowerLimit = true;
      }
    }
    if (hasUsesBeforeFirstUseWithLowerLimit) {
      spilled.setSpilled(false);
    }
    if (firstUseWithLowerLimit != null) {
      LiveIntervals splitOfSplit = spilled.splitBefore(firstUseWithLowerLimit.getPosition());
      unhandled.add(splitOfSplit);
    }
  }

  private void splitRangesForSpilledConstant(LiveIntervals spilled, int spillRegister) {
    // When spilling a constant we should not keep it alive in the spill register, instead
    // we should use rematerialization. We aggressively spill the constant in all gaps
    // between uses that span more than a certain number of instructions. If we needed to
    // spill we are running low on registers and this constant should get out of the way
    // as much as possible.
    assert spilled.isSpilled();
    assert spilled.getValue().isConstNumber();
    assert !spilled.isLinked() || spilled.isArgumentInterval();
    // Do not split range if constant is reused by one of the eleven following instruction.
    int maxGapSize = 11 * INSTRUCTION_NUMBER_DELTA;
    if (!spilled.getUses().isEmpty()) {
      // Split at first use after the spill position and add to unhandled to get a register
      // assigned for rematerialization.
      LiveIntervals split = spilled.splitBefore(spilled.getFirstUse());
      unhandled.add(split);
      // Now repeatedly split for each use that is more than maxGapSize away from the previous use.
      boolean changed = true;
      while (changed) {
        changed = false;
        int previousUse = split.getStart();
        for (LiveIntervalsUse use : split.getUses()) {
          if (use.getPosition() - previousUse > maxGapSize) {
            // Found a use that is more than gap size away from the previous use. Split after
            // the previous use.
            split = split.splitBefore(previousUse + INSTRUCTION_NUMBER_DELTA);
            // If the next use is not at the start of the new split, we split again at the next use
            // and spill the gap.
            if (toGapPosition(use.getPosition()) > split.getStart()) {
              assignRegister(split, spillRegister);
              split.setSpilled(true);
              inactive.add(split);
              split = split.splitBefore(use.getPosition());
            }
            // |split| now starts at the next use - add it to unhandled to get a register
            // assigned for rematerialization.
            unhandled.add(split);
            // Break out of the loop to start iterating the new split uses.
            changed = true;
            break;
          }
          previousUse = use.getPosition();
        }
      }
    }
  }

  private void blockLinkedRegisters(
      List<LiveIntervals> intervalsList, LiveIntervals interval, int registerConstraint,
      RegisterPositions usePositions, RegisterPositions blockedPositions) {
    for (LiveIntervals other : intervalsList) {
      if (other.isLinked()) {
        int register = other.getRegister();
        if (register <= registerConstraint && other.overlaps(interval)) {
          for (int i = 0; i < other.requiredRegisters(); i++) {
            if (register + i <= registerConstraint) {
              int firstUse = other.firstUseAfter(interval.getStart());
              if (firstUse < blockedPositions.get(register + i)) {
                blockedPositions.set(register + i, firstUse, other);
                // If we start blocking registers other than linked arguments, we might need to
                // explicitly update the use positions as well as blocked positions.
                assert usePositions.get(register + i) <= blockedPositions.get(register + i);
              }
            }
          }
        }
      }
    }
  }

  private void insertMoves() {
    SpillMoveSet spillMoves =
        new SpillMoveSet(this, code, numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS);
    for (LiveIntervals intervals : liveIntervals) {
      if (intervals.hasSplits()) {
        LiveIntervals current = intervals;
        PriorityQueue<LiveIntervals> sortedChildren = new PriorityQueue<>();
        sortedChildren.addAll(current.getSplitChildren());
        for (LiveIntervals split = sortedChildren.poll();
            split != null;
            split = sortedChildren.poll()) {
          int position = split.getStart();
          spillMoves.addSpillOrRestoreMove(toGapPosition(position), split, current);
          current = split;
        }
      }
    }

    resolveControlFlow(spillMoves);
    firstParallelMoveTemporary = maxRegisterNumber + 1;
    maxRegisterNumber += spillMoves.scheduleAndInsertMoves(maxRegisterNumber + 1);
  }

  // Resolve control flow by inserting phi moves and by inserting moves when the live intervals
  // change for a value across block boundaries.
  private void resolveControlFlow(SpillMoveSet spillMoves) {
    // For a control-flow graph like the following where a value v is split at an instruction in
    // block C a spill move is inserted in block C to transfer the value from register r0 to
    // register r1. However, that move is not executed when taking the control-flow edge from
    // B to D and therefore resolution will insert a move from r0 to r1 on that edge.
    //
    //             r0            r1
    //   v: |----------------|--------|
    //
    //       A ----> B ----> C ----> D
    //               |               ^
    //               +---------------+
    for (BasicBlock block : code.blocks) {
      for (BasicBlock successor : block.getSuccessors()) {
        // If we are processing an exception edge, we need to use the throwing instruction
        // as the instruction we are coming from.
        int fromInstruction = block.exit().getNumber();
        boolean isCatch = block.hasCatchSuccessor(successor);
        if (isCatch) {
          for (Instruction instruction : block.getInstructions()) {
            if (instruction.instructionTypeCanThrow()) {
              fromInstruction = instruction.getNumber();
              break;
            }
          }
        }
        int toInstruction = successor.entry().getNumber();

        // Insert spill/restore moves when a value changes across a block boundary.
        Set<Value> liveAtEntry = liveAtEntrySets.get(successor);
        for (Value value : liveAtEntry) {
          LiveIntervals parentInterval = value.getLiveIntervals();
          LiveIntervals fromIntervals = parentInterval.getSplitCovering(fromInstruction);
          LiveIntervals toIntervals = parentInterval.getSplitCovering(toInstruction);
          if (fromIntervals != toIntervals) {
            if (block.exit().isGoto() && !isCatch) {
              spillMoves.addOutResolutionMove(fromInstruction - 1, toIntervals, fromIntervals);
            } else if (successor.entry().isMoveException()) {
              spillMoves.addInResolutionMove(toInstruction + 1, toIntervals, fromIntervals);
            } else {
              spillMoves.addInResolutionMove(toInstruction - 1, toIntervals, fromIntervals);
            }
          }
        }

        // Insert phi moves.
        int predIndex = successor.getPredecessors().indexOf(block);
        for (Phi phi : successor.getPhis()) {
          LiveIntervals toIntervals = phi.getLiveIntervals().getSplitCovering(toInstruction);
          Value operand = phi.getOperand(predIndex);
          LiveIntervals fromIntervals =
              operand.getLiveIntervals().getSplitCovering(fromInstruction);
          if (fromIntervals != toIntervals && !toIntervals.isArgumentInterval()) {
            assert block.getSuccessors().size() == 1;
            spillMoves.addPhiMove(fromInstruction - 1, toIntervals, fromIntervals);
          }
        }
      }
    }
  }

  private static void addLiveRange(
      Value value,
      BasicBlock block,
      int end,
      List<LiveIntervals> liveIntervals,
      InternalOptions options) {
    int firstInstructionInBlock = block.entry().getNumber();
    int instructionsSize = block.getInstructions().size() * INSTRUCTION_NUMBER_DELTA;
    int lastInstructionInBlock =
        firstInstructionInBlock + instructionsSize - INSTRUCTION_NUMBER_DELTA;
    int instructionNumber;
    if (value.isPhi()) {
      instructionNumber = firstInstructionInBlock;
    } else {
      Instruction instruction = value.definition;
      instructionNumber = instruction.getNumber();
    }
    if (value.getLiveIntervals() == null) {
      Value current = value.getStartOfConsecutive();
      LiveIntervals intervals = new LiveIntervals(current);
      while (true) {
        liveIntervals.add(intervals);
        Value next = current.getNextConsecutive();
        if (next == null) {
          break;
        }
        LiveIntervals nextIntervals = new LiveIntervals(next);
        intervals.link(nextIntervals);
        current = next;
        intervals = nextIntervals;
      }
    }
    LiveIntervals intervals = value.getLiveIntervals();
    if (firstInstructionInBlock <= instructionNumber &&
        instructionNumber <= lastInstructionInBlock) {
      if (value.isPhi()) {
        // Phis need to interfere with spill restore moves inserted before the instruction because
        // the phi value is defined on the inflowing edge.
        instructionNumber--;
      }
      intervals.addRange(new LiveRange(instructionNumber, end));
      assert unconstrainedForCf(intervals.getRegisterLimit(), options);
      if (options.isGeneratingDex() && !value.isPhi()) {
        int constraint = value.definition.maxOutValueRegister();
        intervals.addUse(new LiveIntervalsUse(instructionNumber, constraint));
      }
    } else {
      intervals.addRange(new LiveRange(firstInstructionInBlock - 1, end));
    }
  }

  private void computeLiveRanges() {
    computeLiveRanges(options, code, liveAtEntrySets, liveIntervals);
    // Art VMs before Android M assume that the register for the receiver never changes its value.
    // This assumption is used during verification. Allowing the receiver register to be
    // overwritten can therefore lead to verification errors. If we could be targeting one of these
    // VMs we block the receiver register throughout the method.
    if (options.canHaveThisTypeVerifierBug() && !code.method.accessFlags.isStatic()) {
      for (Instruction instruction : code.blocks.get(0).getInstructions()) {
        if (instruction.isArgument() && instruction.outValue().isThis()) {
          Value thisValue = instruction.outValue();
          LiveIntervals thisIntervals = thisValue.getLiveIntervals();
          thisIntervals.getRanges().clear();
          thisIntervals.addRange(new LiveRange(0, code.getNextInstructionNumber()));
          for (Set<Value> values : liveAtEntrySets.values()) {
            values.add(thisValue);
          }
          return;
        }
      }
    }
  }

  /**
   * Compute live ranges based on liveAtEntry sets for all basic blocks.
   */
  public static void computeLiveRanges(
      InternalOptions options,
      IRCode code,
      Map<BasicBlock, Set<Value>> liveAtEntrySets,
      List<LiveIntervals> liveIntervals) {
    for (BasicBlock block : code.topologicallySortedBlocks()) {
      Set<Value> live = new HashSet<>();
      List<BasicBlock> successors = block.getSuccessors();
      Set<Value> phiOperands = new HashSet<>();
      for (BasicBlock successor : successors) {
        live.addAll(liveAtEntrySets.get(successor));
        for (Phi phi : successor.getPhis()) {
          live.remove(phi);
          phiOperands.add(phi.getOperand(successor.getPredecessors().indexOf(block)));
          assert phi.getDebugValues().stream().allMatch(Value::needsRegister);
          phiOperands.addAll(phi.getDebugValues());
        }
      }
      live.addAll(phiOperands);
      List<Instruction> instructions = block.getInstructions();
      for (Value value : live) {
        int end = block.entry().getNumber() + instructions.size() * INSTRUCTION_NUMBER_DELTA;
        // Make sure that phi operands do not overlap the phi live range. The phi operand is
        // not live until the next instruction, but only until the gap before the next instruction
        // where the phi value takes over.
        if (phiOperands.contains(value)) {
          end--;
        }
        addLiveRange(value, block, end, liveIntervals, options);
      }
      ListIterator<Instruction> iterator =
          block.getInstructions().listIterator(block.getInstructions().size());
      while (iterator.hasPrevious()) {
        Instruction instruction = iterator.previous();
        Value definition = instruction.outValue();
        if (definition != null) {
          // For instructions that define values which have no use create a live range covering
          // the instruction. This will typically be instructions that can have side effects even
          // if their output is not used.
          if (!definition.isUsed()) {
            addLiveRange(
                definition,
                block,
                instruction.getNumber() + INSTRUCTION_NUMBER_DELTA,
                liveIntervals,
                options);
            assert !options.isGeneratingClassFiles() || instruction.isArgument()
                : "Arguments should be the only potentially unused local in CF";
          }
          live.remove(definition);
        }
        for (Value use : instruction.inValues()) {
          if (use.needsRegister()) {
            assert unconstrainedForCf(instruction.maxInValueRegister(), options);
            if (!live.contains(use)) {
              live.add(use);
              addLiveRange(use, block, instruction.getNumber(), liveIntervals, options);
            }
            if (options.isGeneratingDex()) {
              int inConstraint = instruction.maxInValueRegister();
              LiveIntervals useIntervals = use.getLiveIntervals();
              useIntervals.addUse(new LiveIntervalsUse(instruction.getNumber(), inConstraint));
            }
          }
        }
        if (options.debug) {
          int number = instruction.getNumber();
          for (Value use : instruction.getDebugValues()) {
            assert use.needsRegister();
            if (!live.contains(use)) {
              live.add(use);
              addLiveRange(use, block, number, liveIntervals, options);
            }
          }
        }
      }
    }
  }

  private static boolean unconstrainedForCf(int constraint, InternalOptions options) {
    return !options.isGeneratingClassFiles() || constraint == Constants.U16BIT_MAX;
  }

  private void clearUserInfo() {
    code.blocks.forEach(BasicBlock::clearUserInfo);
  }

  private Value createValue(ValueType type) {
    Value value = code.createValue(type, null);
    value.setNeedsRegister(true);
    return value;
  }

  private void replaceArgument(Invoke invoke, int index, Value newArgument) {
    Value argument = invoke.arguments().get(index);
    invoke.arguments().set(index, newArgument);
    argument.removeUser(invoke);
    newArgument.addUser(invoke);
  }

  private void generateArgumentMoves(Invoke invoke, InstructionListIterator insertAt) {
    // If the invoke instruction require more than 5 registers we link the inputs because they
    // need to be in consecutive registers.
    if (invoke.requiredArgumentRegisters() > 5 && !argumentsAreAlreadyLinked(invoke)) {
      List<Value> arguments = invoke.arguments();
      Value previous = null;
      for (int i = 0; i < arguments.size(); i++) {
        Value argument = arguments.get(i);
        Value newArgument = argument;
        // In debug mode, we have debug instructions that are also moves. Do not generate another
        // move if there already is a move instruction that we can use. We generate moves if:
        //
        // 1. the argument is not defined by a move,
        //
        // 2. the argument is already linked or would cause a cycle if linked, or
        //
        // 3. the argument has a register constraint (the argument moves are there to make the
        //    input value to a ranged invoke unconstrained.)
        if (argument.definition == null ||
            !argument.definition.isMove() ||
            argument.isLinked() ||
            argument == previous ||
            argument.hasRegisterConstraint()) {
          newArgument = createValue(argument.outType());
          Move move = new Move(newArgument, argument);
          move.setBlock(invoke.getBlock());
          move.setPosition(invoke.getPosition());
          replaceArgument(invoke, i, newArgument);
          insertAt.add(move);
        }
        if (previous != null) {
          previous.linkTo(newArgument);
        }
        previous = newArgument;
      }
    }
  }

  private boolean argumentsAreAlreadyLinked(Invoke invoke) {
    Iterator<Value> it = invoke.arguments().iterator();
    Value current = it.next();
    while (it.hasNext()) {
      Value next = it.next();
      if (!current.isLinked() || current.getNextConsecutive() != next) {
        return false;
      }
      current = next;
    }
    return true;
  }

  private Value createSentinelRegisterValue() {
    return createValue(ValueType.OBJECT);
  }

  private LiveIntervals createSentinelLiveInterval(Value sentinelValue) {
    LiveIntervals sentinelInterval = new LiveIntervals(sentinelValue);
    sentinelInterval.addRange(LiveRange.INFINITE);
    liveIntervals.add(sentinelInterval);
    return sentinelInterval;
  }

  private void linkArgumentValues() {
    Value current = preArgumentSentinelValue = createSentinelRegisterValue();
    for (Value argument : code.collectArguments()) {
      current.linkTo(argument);
      current = argument;
    }
    Value endSentinel = createSentinelRegisterValue();
    current.linkTo(endSentinel);
  }

  private void setupArgumentLiveIntervals() {
    Value current = preArgumentSentinelValue;
    LiveIntervals currentIntervals = createSentinelLiveInterval(current);
    current = current.getNextConsecutive();
    int index = 0;
    while (current.getNextConsecutive() != null) {
      // Add a live range to this value from the beginning of the block up to the argument
      // instruction to avoid dead arguments without a range. This may create an actually empty
      // range like [0,0[ but that works, too.
      LiveIntervals argumentInterval = new LiveIntervals(current);
      argumentInterval.addRange(new LiveRange(0, index * INSTRUCTION_NUMBER_DELTA));
      index++;
      liveIntervals.add(argumentInterval);
      currentIntervals.link(argumentInterval);
      currentIntervals = argumentInterval;
      current = current.getNextConsecutive();
    }
    currentIntervals.link(createSentinelLiveInterval(current));
  }

  private void insertArgumentMoves() {
    // Record the constraint that incoming arguments are in consecutive registers.
    // We also insert sentinel registers before and after the arguments at this
    // point.
    linkArgumentValues();
    setupArgumentLiveIntervals();
    for (BasicBlock block : code.blocks) {
      InstructionListIterator it = block.listIterator();
      while (it.hasNext()) {
        Instruction instruction = it.next();
        if (instruction.isInvoke()) {
          // Rewind so moves are inserted before the invoke.
          it.previous();
          // Generate the argument moves.
          generateArgumentMoves(instruction.asInvoke(), it);
          // Move past the move again.
          it.next();
        }
      }
    }
  }

  private void computeNeedsRegister() {
    for (BasicBlock block : code.topologicallySortedBlocks()) {
      for (Instruction instruction : block.getInstructions()) {
        if (instruction.outValue() != null) {
          instruction.outValue().computeNeedsRegister();
        }
      }
    }
  }

  private void pinArgumentRegisters() {
    // Special handling for arguments. Pin their register.
    int register = 0;
    Value current = preArgumentSentinelValue;
    while (current != null) {
      LiveIntervals argumentLiveInterval = current.getLiveIntervals();
      // Pin the argument register. We use getFreeConsecutiveRegisters to make sure that we update
      // the max register number.
      register = getFreeConsecutiveRegisters(argumentLiveInterval.requiredRegisters());
      assignRegister(argumentLiveInterval, register);
      current = current.getNextConsecutive();
    }
    assert register == numberOfArgumentRegisters + NUMBER_OF_SENTINEL_REGISTERS - 1;
  }

  private int getFreeConsecutiveRegisters(int numberOfRegister) {
    List<Integer> unused = new ArrayList<>();
    int first = getNextFreeRegister();
    int current = first;
    while ((current - first + 1) != numberOfRegister) {
      for (int i = 0; i < numberOfRegister - 1; i++) {
        int next = getNextFreeRegister();
        if (next != current + 1) {
          for (int j = first; j <= current; j++) {
            unused.add(j);
          }
          first = next;
          current = first;
          break;
        }
        current++;
      }
    }
    freeRegisters.addAll(unused);
    maxRegisterNumber = Math.max(maxRegisterNumber, first + numberOfRegister - 1);
    return first;
  }

  private int getNextFreeRegister() {
    if (freeRegisters.size() > 0) {
      return freeRegisters.pollFirst();
    }
    return nextUnusedRegisterNumber++;
  }

  private void excludeRegistersForInterval(LiveIntervals intervals, Set<Integer> excluded) {
    int register = intervals.getRegister();
    for (int i = 0; i < intervals.requiredRegisters(); i++) {
      if (freeRegisters.remove(register + i)) {
        excluded.add(register + i);
      }
    }
  }

  private void freeRegistersForIntervals(LiveIntervals intervals) {
    int register = intervals.getRegister();
    freeRegisters.add(register);
    if (intervals.getType().isWide()) {
      freeRegisters.add(register + 1);
    }
  }

  private void takeRegistersForIntervals(LiveIntervals intervals) {
    int register = intervals.getRegister();
    freeRegisters.remove(register);
    if (intervals.getType().isWide()) {
      freeRegisters.remove(register + 1);
    }
  }

  private boolean noLinkedValues() {
    for (BasicBlock block : code.blocks) {
      for (Phi phi : block.getPhis()) {
        assert phi.getNextConsecutive() == null;
      }
      for (Instruction instruction : block.getInstructions()) {
        for (Value value : instruction.inValues()) {
          assert value.getNextConsecutive() == null;
        }
        assert instruction.outValue() == null ||
            instruction.outValue().getNextConsecutive() == null;
      }
    }
    return true;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder("Live ranges:\n");
    for (LiveIntervals intervals : liveIntervals) {
      Value value = intervals.getValue();
      builder.append(value);
      builder.append(" ");
      builder.append(intervals);
    }
    builder.append("\nLive range ascii art: \n");
    for (LiveIntervals intervals : liveIntervals) {
      Value value = intervals.getValue();
      if (intervals.getRegister() == NO_REGISTER) {
        StringUtils.appendRightPadded(builder, value + " (no reg): ", 20);
      } else {
        StringUtils.appendRightPadded(builder, value + " r" + intervals.getRegister() + ": ", 20);
      }
      builder.append("|");
      builder.append(intervals.toAscciArtString());
      builder.append("\n");
    }
    return builder.toString();
  }
}