pkg/native_compiler/lib/back_end/register_allocator.dart

// Copyright (c) 2026, the Dart 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.

import 'dart:math' as math show min, max;
import 'dart:typed_data';

import 'package:cfg/utils/misc.dart';
import 'package:native_compiler/back_end/back_end_state.dart';
import 'package:native_compiler/back_end/constraints.dart';
import 'package:native_compiler/back_end/locations.dart';
import 'package:native_compiler/back_end/safepoint.dart';
import 'package:cfg/ir/constant_value.dart';
import 'package:cfg/ir/instructions.dart';
import 'package:cfg/ir/ir_to_text.dart';
import 'package:cfg/ir/liveness_analysis.dart';
import 'package:cfg/ir/types.dart';
import 'package:cfg/passes/pass.dart';
import 'package:native_compiler/utils/interval_list.dart';

abstract base class RegisterAllocator extends Pass {
  final BackEndState backEndState;

  RegisterAllocator(this.backEndState) : super('RegisterAllocation');
}

/// Linear scan register allocator.
///
/// Allocates registers on the linearized control flow.
/// Live ranges are represented as a sequence of intervals.
///
/// The original idea of linear scan register allocation is described in
/// Massimiliano Poletto and Vivek Sarkar "Linear scan register allocation" (1999).
///
/// This variant of linear scan is largerly based on
/// "Linear Scan Register Allocation for the Java HotSpot Client Compiler",
/// by Christian Wimmer (2004).
/// http://www.christianwimmer.at/Publications/Wimmer04a/Wimmer04a.pdf
///
final class LinearScanRegisterAllocator extends RegisterAllocator {
  // Step of instruction positions in the linearized control flow.
  // Increment positions by 2 to leave space for ParallelMove instructions
  // which can be inserted later between instructions.
  static const int step = 2;

  static const bool trace = const bool.fromEnvironment('trace.regalloc');

  static const int maxPosition = 0x7fffffff;

  final Constraints constraints;

  /// Instruction id -> instruction position in the
  /// linearized control flow.
  late final Int32List _instructionPos;

  /// Instruction position ~/ step -> instruction id.
  late final Int32List _instructionByPos;

  /// Instruction id -> LiveRange corresponding to the instruction output.
  late final List<LiveRange?> _liveRanges;

  /// Instruction id -> its Safepoint.
  late final List<Safepoint?> _safepoints;

  /// Instruction position ~/ step -> position of the next instruction with a safepoint.
  late final Int32List _nextSafepointPos;

  /// Locations of instruction inputs/outputs/temps.
  final Map<OperandId, Location> _operandLocations = {};

  /// Live ranges corresponding to the fixed register locations.
  late final List<LiveRange?> _cpuRegLiveRanges;
  late final List<LiveRange?> _fpuRegLiveRanges;

  /// Register index -> [Location].
  late List<PhysicalRegister?> _registerLocations;

  /// List of live ranges which were not handled yet by [allocate].
  late List<LiveRange> _unhandled;
  int _unhandledIndex = -1;

  /// For each register, list of live ranges allocated to this register,
  /// or null if register is not allocatable.
  late List<List<LiveRange>?> _allocated;

  LinearScanRegisterAllocator(super.backEndState, this.constraints);

  RegisterClass registerClass(Definition instr) =>
      instr.type is DoubleType && backEndState.unboxing.hasUnboxedResult(instr)
      ? RegisterClass.fpu
      : RegisterClass.cpu;

  int instructionPos(Instruction instr) => _instructionPos[instr.id];
  int blockStartPos(Block block) => instructionPos(block);
  int blockEndPos(Block block) => instructionPos(block.lastInstruction);

  Instruction instructionByPos(int pos) =>
      graph.instructions[_instructionByPos[pos ~/ step]];

  bool hasLiveRange(Definition instr) => instr is! Constant;

  LiveRange liveRangeFor(Definition instr) {
    assert(hasLiveRange(instr));
    return _liveRanges[instr.id] ??= LiveRange(
      registerClass(instr),
      isObjectPointer: !backEndState.unboxing.hasUnboxedResult(instr),
    );
  }

  LiveRange regLiveRange(PhysicalRegister r) => (r is Register)
      ? (_cpuRegLiveRanges[r.index] ??= LiveRange(
          RegisterClass.cpu,
          isObjectPointer: false,
          isPhysical: true,
        ))
      : (_fpuRegLiveRanges[r.index] ??= LiveRange(
          RegisterClass.fpu,
          isObjectPointer: false,
          isPhysical: true,
        ));

  @override
  void run() {
    numberInstructions();

    final liveness = SSALivenessAnalysis(graph);
    liveness.analyze();

    buildLiveRanges(liveness);

    coalesceLiveRanges();

    allocate(
      RegisterClass.cpu,
      constraints.getNumberOfRegisters(),
      constraints.getAllocatableRegisters(),
      _cpuRegLiveRanges,
    );
    allocate(
      RegisterClass.fpu,
      constraints.getNumberOfFPRegisters(),
      constraints.getAllocatableFPRegisters(),
      _fpuRegLiveRanges,
    );

    resolveDataFlow(liveness);

    backEndState.safepoints = _safepoints;
    backEndState.operandLocations = _operandLocations;
    backEndState.stackFrame.finalize();
  }

  /// Number instructions in the linearized control flow.
  void numberInstructions() {
    _instructionPos = Int32List(graph.instructions.length);
    _instructionByPos = Int32List(graph.instructions.length + 1);
    // Reserve 0 for uninitialized value, use even positions
    // for the instructions.
    int pos = step;
    for (final block in backEndState.codeGenBlockOrder) {
      _instructionPos[block.id] = pos;
      _instructionByPos[pos ~/ step] = block.id;
      assert(pos == blockStartPos(block));
      pos += step;
      for (final instr in block) {
        if (instr is Phi || instr is Constant || instr is Parameter) {
          // All Phis, Constants and Parameters have the same position as their Block.
          _instructionPos[instr.id] = blockStartPos(block);
        } else {
          _instructionPos[instr.id] = pos;
          _instructionByPos[pos ~/ step] = instr.id;
          pos += step;
        }
      }
      assert(pos == blockEndPos(block) + step);
    }

    errorContext.annotator = (Instruction instr) =>
        (instr is ParallelMove) ? null : '[${instructionPos(instr)}]';
  }

  void buildLiveRanges(SSALivenessAnalysis liveness) {
    _liveRanges = List.filled(graph.instructions.length, null, growable: true);
    _cpuRegLiveRanges = List.filled(constraints.getNumberOfRegisters(), null);
    _fpuRegLiveRanges = List.filled(constraints.getNumberOfFPRegisters(), null);
    _safepoints = List.filled(graph.instructions.length, null);
    _nextSafepointPos = Int32List(graph.instructions.length + 1);
    var nextSafepointPos = maxPosition;

    for (final block in backEndState.codeGenBlockOrder.reversed) {
      currentBlock = block;
      final blockStart = blockStartPos(block);
      final blockEnd = blockEndPos(block);

      // Add intervals for values which are live-out.
      for (final instrId in liveness.liveOut(block).elements) {
        final instr = graph.instructions[instrId] as Definition;
        if (hasLiveRange(instr)) {
          final liveRange = liveRangeFor(instr);
          liveRange.addInterval(blockStart, blockEnd);
        }
      }

      // Add uses in the Phis in the successor block.
      if (block.successors.length == 1) {
        final succ = block.successors.single;
        if (succ is JoinBlock) {
          final int predIndex = succ.predecessors.indexOf(block);
          assert(predIndex >= 0);
          for (final phi in succ.phis) {
            final input = phi.inputDefAt(predIndex);
            if (input is! Constant) {
              final inputConstr = constraints
                  .getConstraints(phi)!
                  .inputs[predIndex]!;
              final operandId = OperandId.input(phi.id, predIndex);
              final liveRange = liveRangeFor(input);
              _processInput(
                phi,
                liveRange,
                blockEnd,
                inputConstr,
                operandId,
                null,
              );
            }
          }
        }
      }

      for (final instr in block.reversed) {
        currentInstruction = instr;
        backEndState.stackFrame.allocateArgumentsSlots(instr);
        final pos = instructionPos(instr);
        final constr = constraints.getConstraints(instr);
        _nextSafepointPos[pos ~/ step] = nextSafepointPos;
        if (constr == null) {
          continue;
        }
        final safepoint = constr.safepoint;
        // Ignore Phis as they are processed in the predecessor blocks.
        if (instr is! Phi) {
          // Process inputs.
          for (int i = 0, n = instr.inputCount; i < n; ++i) {
            final input = instr.inputDefAt(i);
            final inputConstr = constr.inputs[i];
            final operandId = OperandId.input(instr.id, i);
            if (input is Constant) {
              if (inputConstr != null) {
                _processConstantInput(
                  instr,
                  input.value,
                  pos,
                  inputConstr,
                  operandId,
                  safepoint,
                );
              }
            } else {
              final liveRange = liveRangeFor(input);
              // Extend range up to block start position.
              // It will be truncated by the definition if needed.
              liveRange.addInterval(blockStart, pos);
              if (inputConstr != null) {
                _processInput(
                  instr,
                  liveRange,
                  pos,
                  inputConstr,
                  operandId,
                  safepoint,
                );
              }
            }
          }
        }
        // Process temps.
        for (int i = 0, n = constr.temps.length; i < n; ++i) {
          final operandId = OperandId.temp(instr.id, i);
          _processTemp(pos, constr.temps[i], operandId);
        }
        // Process output.
        if (instr is Definition && hasLiveRange(instr)) {
          final operandId = OperandId.result(instr.id);
          final liveRange = liveRangeFor(instr);
          final resultConstr = constr.result;
          liveRange.defineAt(
            instructionPos(instr) +
                ((resultConstr is PhysicalRegister ||
                        resultConstr is ParameterStackLocation)
                    ? 1
                    : 0),
          );
          if (resultConstr != null) {
            _processOutput(instr, liveRange, pos, resultConstr, operandId);
          }
        }
        // Process safepoint.
        if (safepoint != null) {
          backEndState.stackFrame.recordReservedLocations(safepoint);
          _safepoints[instr.id] = safepoint;
          nextSafepointPos = pos;
        }
      }

      assert(instructionPos(block) == blockStart);
      _nextSafepointPos[blockStart ~/ step] = nextSafepointPos;

      // Handle safepoint at block start.
      final safepoint = constraints.getConstraints(block)?.safepoint;
      if (safepoint != null) {
        backEndState.stackFrame.recordReservedLocations(safepoint);
        _safepoints[block.id] = safepoint;
        nextSafepointPos = blockStart;
      }
    }

    errorContext.annotator = (Instruction instr) {
      if (instr is ParallelMove) return null;
      return '[${instructionPos(instr)}]' +
          ((instr is Definition && hasLiveRange(instr))
              ? ' ${liveRangeFor(instr)}'
              : '');
    };

    if (trace) {
      print(
        IrToText(
          graph,
          printDominators: true,
          printLoops: true,
          annotator: errorContext.annotator,
        ).toString(),
      );
    }
  }

  void _processInput(
    Instruction instr,
    LiveRange liveRange,
    int pos,
    Constraint constr,
    OperandId operandId,
    Safepoint? safepoint,
  ) {
    if (constr is PhysicalRegister) {
      regLiveRange(constr).addInterval(pos, pos + 1);
      final loc = liveRange.addUse(pos - 1, constr);
      _insertMoveBefore(instr, ParallelMoveStage.input, loc, constr);
      _operandLocations[operandId] = constr;
      safepoint?.addLiveLocation(
        constr,
        isObjectPointer: liveRange.isObjectPointer,
      );
    } else {
      final loc = liveRange.addUse(pos - 1, constr);
      _operandLocations[operandId] = loc;
    }
  }

  // TODO: allocate constants to registers.
  void _processConstantInput(
    Instruction instr,
    ConstantValue value,
    int pos,
    Constraint constr,
    OperandId operandId,
    Safepoint? safepoint,
  ) {
    if (constr is PhysicalRegister) {
      _insertMoveBefore(instr, ParallelMoveStage.input, null, constr, value);
      regLiveRange(constr).addInterval(pos, pos + 1);
      _operandLocations[operandId] = constr;
      safepoint?.addLiveLocation(constr, isObjectPointer: !value.isUnboxed);
    } else {
      final liveRange = LiveRange(
        constr.registerClass,
        isObjectPointer: !value.isUnboxed,
      );
      _liveRanges.add(liveRange);
      liveRange.addInterval(pos - 1, pos);
      final loc = liveRange.addUse(pos - 1, constr);
      _insertMoveBefore(instr, ParallelMoveStage.input, null, loc, value);
      _operandLocations[operandId] = loc;
    }
  }

  void _processTemp(int pos, Constraint constr, OperandId operandId) {
    if (constr is PhysicalRegister) {
      regLiveRange(constr).addInterval(pos, pos + 1);
      _operandLocations[operandId] = constr;
    } else {
      final liveRange = LiveRange(constr.registerClass, isObjectPointer: false);
      _liveRanges.add(liveRange);
      liveRange.addInterval(pos - 1, pos + 1);
      final loc = liveRange.addUse(pos, constr);
      _operandLocations[operandId] = loc;
    }
  }

  void _processOutput(
    Definition instr,
    LiveRange liveRange,
    int pos,
    Constraint constr,
    OperandId operandId,
  ) {
    assert(instr is! ControlFlowInstruction);
    if (constr is PhysicalRegister) {
      regLiveRange(constr).addInterval(pos, pos + 1);
      _operandLocations[operandId] = constr;
      if (instr.hasUses) {
        final loc = liveRange.addUse(pos + 1, constr);
        _insertMoveBefore(
          _nextInstruction(instr),
          ParallelMoveStage.output,
          constr,
          loc,
        );
      }
    } else if (constr is ParameterStackLocation) {
      if (!graph.function.isSuspendable) {
        // Lock spill slot to the parameter location on the stack,
        // unless the current function is suspendable
        // (suspend/resume does not preserve parameters on the stack).
        assert(liveRange.splitFrom == null);
        liveRange.spillSlot = constr;
      }
      _operandLocations[operandId] = constr;
      if (instr.hasUses) {
        final loc = liveRange.addUse(pos + 1, constr);
        _insertMoveBefore(
          _nextInstruction(instr),
          ParallelMoveStage.output,
          constr,
          loc,
        );
      }
    } else {
      final loc = liveRange.addUse(pos, constr);
      _operandLocations[operandId] = loc;
    }
  }

  ParallelMove _parallelMoveBefore(Instruction instr, ParallelMoveStage stage) {
    assert(instr is! Phi);
    assert(instr is! Constant);
    assert(instr is! ParallelMove);
    for (;;) {
      Instruction? prev = instr.previous;
      if (prev is! ParallelMove || prev.stage.index < stage.index) {
        break;
      }
      if (prev.stage == stage) {
        return prev;
      }
      instr = prev;
    }
    final move = ParallelMove(instr.graph, stage);
    move.insertBefore(instr);
    return move;
  }

  void _insertMoveBefore(
    Instruction instr,
    ParallelMoveStage stage,
    Location? src,
    Location dst, [
    ConstantValue? value,
  ]) {
    ParallelMove move = _parallelMoveBefore(instr, stage);
    MoveOp moveOp;
    if (src == null) {
      moveOp = LoadConstant(value!, dst);
    } else {
      assert(value == null);
      moveOp = Move(src, dst);
    }
    move.moves.add(moveOp);
  }

  /// Returns the instruction at the next position after [instr].
  Instruction _nextInstruction(Instruction instr) {
    return instructionByPos(instructionPos(instr) + step);
  }

  /// Tries to merge live ranges which would benefit from
  /// allocation to the same location.
  ///
  /// TODO: Currently only inputs/outputs of phis are merged, but we
  /// can also merge inputs/outputs of instructions reusing
  /// the same register if/when we add "SameAsFirstInput" constraint.
  void coalesceLiveRanges() {
    for (final block in backEndState.codeGenBlockOrder.reversed) {
      if (block is JoinBlock) {
        for (final phi in block.phis) {
          final liveRange = liveRangeFor(phi).bundle;
          for (int i = 0, n = phi.inputCount; i < n; ++i) {
            final input = phi.inputDefAt(i);
            if (input is! Constant) {
              liveRange.tryMerge(liveRangeFor(input).bundle);
            }
          }
        }
      }
    }
  }

  void allocate(
    RegisterClass registerClass,
    int numberOfRegisters,
    List<PhysicalRegister> allocatableRegisters,
    List<LiveRange?> blockedRegisters,
  ) {
    _unhandled = <LiveRange>[];
    for (final liveRange in _liveRanges) {
      if (liveRange != null &&
          liveRange.registerClass == registerClass &&
          liveRange.mergedTo == null) {
        _unhandled.add(liveRange);
      }
    }
    _unhandled.sort((a, b) => a.start.compareTo(b.start));
    _unhandledIndex = 0;

    if (trace) {
      print('UNHANDLED:');
      print('----------');
      for (final range in _unhandled) {
        print(range);
      }
      print('----------');
    }

    _registerLocations = List<PhysicalRegister?>.filled(
      numberOfRegisters,
      null,
    );
    _allocated = List<List<LiveRange>?>.filled(numberOfRegisters, null);
    for (final reg in allocatableRegisters) {
      _registerLocations[reg.index] = reg;
      final blocked = blockedRegisters[reg.index];
      assert(blocked == null || blocked.isPhysical);
      _allocated[reg.index] = <LiveRange>[if (blocked != null) blocked];
    }

    if (trace) {
      print('BLOCKED:');
      print('----------');
      for (var reg = 0; reg < _allocated.length; ++reg) {
        final ranges = _allocated[reg];
        if (ranges != null && ranges.isNotEmpty) {
          print('${_registerLocations[reg]}: ${ranges.single}');
        }
      }
      print('----------');
    }

    for (; _unhandledIndex < _unhandled.length; ++_unhandledIndex) {
      final range = _unhandled[_unhandledIndex];
      if (trace) {
        print('Allocating $range');
      }
      advance(range.start);

      if (!allocateFreeRegister(range)) {
        allocateBlockedRegister(range);
      }
    }

    advance(maxPosition);
  }

  void advance(int pos) {
    if (trace) {
      print('Advance to $pos');
    }
    for (var reg = 0; reg < _allocated.length; ++reg) {
      final ranges = _allocated[reg];
      if (ranges == null) {
        continue;
      }
      var i = 0;
      for (var j = 0; j < ranges.length; ++j) {
        final range = ranges[j];
        if (range.advance(pos)) {
          // Live range ended, set its location and move it to [handled].
          if (range.isPhysical) {
            assert(range.uses.isEmpty);
            if (trace) {
              print('Finished blocked $range');
            }
          } else {
            finishLiveRange(range, reg);
          }
        } else {
          ranges[i++] = range;
        }
      }
      ranges.length = i;
    }
  }

  void finishLiveRange(LiveRange range, int reg) {
    final loc = _registerLocations[reg]!;
    if (trace) {
      print('Finished $range, allocated to $loc');
    }
    range.setLocation(loc);
    recordLiveRangeAtSafepoints(range, loc);
  }

  // Update all safepoints in this live range with given location.
  void recordLiveRangeAtSafepoints(LiveRange range, Location loc) {
    final intervals = range.intervals;
    for (var i = 0, n = intervals.length; i < n; ++i) {
      final start = intervals.startAt(i);
      final end = intervals.endAt(i);
      var pos = _nextSafepointPos[(start - 1) ~/ step];
      while (pos < end) {
        final safepoint = _safepoints[instructionByPos(pos).id]!;
        safepoint.addLiveLocation(loc, isObjectPointer: range.isObjectPointer);
        pos = _nextSafepointPos[pos ~/ step];
      }
    }
  }

  /// Tries to allocate a free register for [range].
  bool allocateFreeRegister(LiveRange range) {
    // Handle fixed register location first.
    final preferredRegisterUse = range.firstPreferredRegisterUse;
    if (preferredRegisterUse != null) {
      int fixedRegister =
          (preferredRegisterUse.constraint as PhysicalRegister).index;
      int freeUntil = firstIntersectionWithAllocated(range, fixedRegister);
      if (toSplitPosition(freeUntil) > preferredRegisterUse.pos) {
        // Split [range] if register is not free for the whole duration of the [range].
        if (freeUntil < range.end) {
          if (trace) {
            print('Split $range at $freeUntil');
          }
          addToUnhandled(
            splitBetween(range, preferredRegisterUse.pos, freeUntil),
          );
        }
        if (trace) {
          print(
            'Allocating $range to preferred ${_registerLocations[fixedRegister]}',
          );
        }
        _allocated[fixedRegister]!.add(range);
        return true;
      }
    }
    // Pick a register which is free the longest span.
    var candidate = -1;
    int freeUntil = range.start;
    for (var reg = 0; reg < _allocated.length; ++reg) {
      if (_allocated[reg] == null) continue;
      int intersection = firstIntersectionWithAllocated(range, reg);
      if (toSplitPosition(intersection) > freeUntil) {
        candidate = reg;
        freeUntil = intersection;
      }
      if (intersection == maxPosition) {
        break;
      }
    }
    if (candidate < 0) {
      if (trace) {
        print('Free register is not found');
      }
      return false;
    }
    if (freeUntil < range.end) {
      if (trace) {
        print('Split $range at $freeUntil');
      }
      addToUnhandled(splitBetween(range, range.start, freeUntil));
    }
    if (trace) {
      print('Allocating $range to free ${_registerLocations[candidate]}');
    }
    _allocated[candidate]!.add(range);
    return true;
  }

  /// Returns position of the first intersection of [range] with live ranges
  /// allocated to [reg], or [maxPosition] if they do not intersect.
  int firstIntersectionWithAllocated(LiveRange range, int reg) {
    int pos = maxPosition;
    for (final allocated in _allocated[reg]!) {
      final intersection = range.intervals.firstIntersection(
        0,
        allocated.intervals,
        allocated.currentInterval,
      );
      if (intersection >= 0 && intersection < pos) {
        pos = intersection;
      }
    }
    return pos;
  }

  // Find the nearest valid position for live range splitting which doesn't exceed [pos].
  int toSplitPosition(int pos) {
    if (pos.isOdd) {
      // Positions between instructions are always valid.
      return pos;
    }
    final instr = instructionByPos(pos);
    if (instr is Block || instr == instr.block!.lastInstruction) {
      // Block start or end positions are valid for splitting.
      return pos;
    }
    return pos - 1;
  }

  LiveRange splitBetween(LiveRange range, int start, int end) {
    assert(start < end);
    // TODO: figure out more optimal split position using loop boundaries.
    final pos = toSplitPosition(end);
    assert(pos >= start);
    assert(pos <= end);
    return range.splitAt(pos);
  }

  /// Add [tail] to the [_unhandled] list after splitting.
  void addToUnhandled(LiveRange tail) {
    if (trace) {
      print('Add $tail to unhandled');
    }
    final start = tail.start;
    int i = _unhandledIndex + 1;
    for (; i < _unhandled.length; ++i) {
      final range = _unhandled[i];
      if (range.start > start) {
        break;
      }
      _unhandled[i - 1] = range;
    }
    _unhandled[i - 1] = tail;
    --_unhandledIndex;
  }

  void allocateBlockedRegister(LiveRange unallocated) {
    var candidateReg = -1;
    var bestFreeUntil = 0;
    int bestBlockedAt = maxPosition;

    // Select a live range which is not going to be used for the longest time.
    // Spilling this live range would free a register as long as possible.
    void inspectAllocatedRegister(int reg) {
      final ranges = _allocated[reg];
      if (ranges == null) {
        return;
      }
      int freeUntil = maxPosition;
      int blockedAt = maxPosition;
      final start = unallocated.start;
      for (final allocated in ranges) {
        if (allocated.nextIntervalContains(start)) {
          // Active interval.
          if (allocated.isPhysical) {
            return;
          }
          int nextUsePosition =
              allocated.findRegisterUseAfter(start)?.pos ?? allocated.end;
          if (nextUsePosition < freeUntil) {
            freeUntil = nextUsePosition;
          }
        } else {
          // Inactive interval.
          final intersection = unallocated.intervals.firstIntersection(
            0,
            allocated.intervals,
            allocated.currentInterval,
          );
          if (intersection >= 0) {
            if (intersection < freeUntil) {
              freeUntil = intersection;
            }
            if (allocated.isPhysical && intersection < blockedAt) {
              blockedAt = intersection;
            }
          }
        }

        if (freeUntil <= bestFreeUntil) {
          return;
        }
      }
      assert(freeUntil > bestFreeUntil);
      bestFreeUntil = freeUntil;
      bestBlockedAt = blockedAt;
      candidateReg = reg;
    }

    for (var reg = 0; reg < _allocated.length; ++reg) {
      inspectAllocatedRegister(reg);
    }

    assert(bestFreeUntil <= bestBlockedAt);

    int firstUsePos = unallocated.uses.isEmpty
        ? unallocated.start
        : unallocated.uses.last.pos;
    if (bestFreeUntil < firstUsePos) {
      if (unallocated.start < firstUsePos) {
        if (trace) {
          print('Split $unallocated at $firstUsePos');
        }
        addToUnhandled(unallocated.splitAt(firstUsePos));
      }
      spillLiveRange(unallocated);
      return;
    }

    assert(candidateReg >= 0);
    if (bestBlockedAt < unallocated.end) {
      if (trace) {
        print('Split $unallocated at $bestBlockedAt');
      }
      addToUnhandled(unallocated.splitAt(bestBlockedAt));
    }
    assignNonFreeRegister(unallocated, candidateReg);
  }

  void spillLiveRange(LiveRange range) {
    final splitParent = range.splitParent;
    assert(splitParent.registerClass == range.registerClass);
    final spillSlot = allocateSpillSlotFor(splitParent);
    if (trace) {
      print('Spill $range to $spillSlot');
    }
    range.setLocation(spillSlot);
  }

  StackLocation allocateSpillSlotFor(LiveRange range) {
    assert(range.splitParent == range);
    assert(range.mergedTo == null);
    var spillSlot = range.spillSlot;
    if (spillSlot == null) {
      spillSlot = range.spillSlot = backEndState.stackFrame.allocateSpillSlot(
        range.registerClass,
      );
      for (LiveRange? r = range; r != null; r = r.splitNext) {
        recordLiveRangeAtSafepoints(r, spillSlot);
      }
    }
    return spillSlot;
  }

  void assignNonFreeRegister(LiveRange range, int reg) {
    if (trace) {
      print('Assigning non-free ${_registerLocations[reg]} to $range');
    }
    _allocated[reg]!.removeWhere(
      (LiveRange allocated) =>
          !allocated.isPhysical && evictIntersection(allocated, range, reg),
    );
    _allocated[reg]!.add(range);
  }

  bool evictIntersection(LiveRange allocated, LiveRange unallocated, int reg) {
    final intersection = unallocated.intervals.firstIntersection(
      0,
      allocated.intervals,
      allocated.currentInterval,
    );
    if (intersection < 0) {
      if (trace) {
        print(' ... no intersection with $allocated');
      }
      return false;
    }
    final spillPos = unallocated.start;
    final nextUse = allocated.findRegisterUseAfter(spillPos);
    if (nextUse == null) {
      // No more uses which require registers.
      if (trace) {
        print('Split $allocated at $spillPos');
      }
      if (toSplitPosition(spillPos) <= allocated.start) {
        if (trace) {
          print('Spill evicted $allocated');
        }
        spillLiveRange(allocated);
      } else {
        spillLiveRange(splitBetween(allocated, allocated.start, spillPos));
        finishLiveRange(allocated, reg);
      }
    } else {
      final usePos = nextUse.pos;
      final restorePos = (spillPos < intersection)
          ? math.min(intersection, usePos)
          : usePos;
      if (toSplitPosition(spillPos) <= allocated.start) {
        if (trace) {
          print('Split $allocated at $restorePos');
        }
        assert(restorePos > allocated.start);
        addToUnhandled(splitBetween(allocated, spillPos, restorePos));
        spillLiveRange(allocated);
      } else {
        if (trace) {
          print('Split $allocated at $spillPos');
        }
        final rangeToSpill = splitBetween(allocated, allocated.start, spillPos);
        if (trace) {
          print('Split $rangeToSpill at $restorePos');
        }
        addToUnhandled(splitBetween(rangeToSpill, spillPos, restorePos));
        spillLiveRange(rangeToSpill);
        finishLiveRange(allocated, reg);
      }
    }
    return true;
  }

  /// Resolve data flow between blocks and split live ranges.
  void resolveDataFlow(SSALivenessAnalysis liveness) {
    // Allocate spill slots to resolve data flow into catch blocks.
    for (final block in backEndState.codeGenBlockOrder) {
      if (block is CatchBlock) {
        for (final instrId in liveness.liveIn(block).elements) {
          LiveRange? liveRange = _liveRanges[instrId]?.bundle;
          if (liveRange != null && liveRange.spillSlot == null) {
            assert(liveRange.splitParent == liveRange);
            allocateSpillSlotFor(liveRange);
          }
        }
      }
    }
    // Insert moves for split and spilled live ranges.
    for (var i = 0; i < _liveRanges.length; ++i) {
      LiveRange? liveRange = _liveRanges[i];
      if (liveRange == null) {
        continue;
      }
      currentInstruction = (i < graph.instructions.length)
          ? graph.instructions[i]
          : null;
      // Insert moves between split live ranges at split points.
      if (liveRange.mergedTo == null) {
        for (;;) {
          LiveRange? next = liveRange!.splitNext;
          if (next == null) {
            break;
          }
          if (liveRange.end == next.start &&
              liveRange.allocatedLocation != next.allocatedLocation &&
              next.allocatedLocation is! StackLocation) {
            Instruction instr = instructionByPos(roundUp(next.start, step));
            ParallelMoveStage stage = next.start.isOdd
                ? ParallelMoveStage.output
                : ParallelMoveStage.input;
            if (instr is Block) {
              if (instr is JoinBlock && instr.hasPhis) {
                instr = instr.phis.last;
              }
              instr = _nextInstruction(instr);
              stage = ParallelMoveStage.output;
            }
            _insertMoveBefore(
              instr,
              stage,
              liveRange.allocatedLocation!,
              next.allocatedLocation!,
            );
            if (trace) {
              print(
                'Insert split move at ${next.start} (${stage.name} before ${IrToText.instruction(instr)})'
                ' ${liveRange} ${liveRange.allocatedLocation} => $next ${next.allocatedLocation}',
              );
            }
          }
          liveRange = next;
        }
      }
      // Fill in spill slots after definitions if needed
      // (so the value is always available in the spill slot).
      liveRange = _liveRanges[i]!.bundle;
      assert(liveRange.splitParent == liveRange);
      final spillSlot = liveRange.spillSlot;
      if (spillSlot != null &&
          spillSlot is! ParameterStackLocation &&
          i < graph.instructions.length) {
        Instruction instr = graph.instructions[i];
        if ((instr as Definition).hasUses) {
          if (instr is Phi) {
            instr = (instr.block as JoinBlock).phis.last;
          }
          final definitionPos = _liveRanges[i]!.definitionPos;
          assert(definitionPos >= 0);
          assert(
            definitionPos == instructionPos(instr) ||
                definitionPos == instructionPos(instr) + 1,
          );
          LiveRange splitChild = liveRange.findSplitChildAt(definitionPos);
          ParallelMoveStage stage = definitionPos.isOdd
              ? ParallelMoveStage.spill
              : ParallelMoveStage.output;
          if (splitChild.allocatedLocation is! SpillSlot) {
            _insertMoveBefore(
              _nextInstruction(instr),
              stage,
              splitChild.allocatedLocation!,
              spillSlot,
            );
            if (trace) {
              print(
                'Insert spill move at $definitionPos (${stage.name} before ${IrToText.instruction(_nextInstruction(instr))})'
                ' $splitChild ${splitChild.allocatedLocation} => $spillSlot',
              );
            }
          }
        }
      }
    }

    for (final block in backEndState.codeGenBlockOrder) {
      final blockStart = blockStartPos(block);
      for (
        int predIndex = 0, n = block.predecessors.length;
        predIndex < n;
        ++predIndex
      ) {
        final pred = block.predecessors[predIndex];
        final Instruction insertionPoint;
        final ParallelMoveStage stage;
        if (block is JoinBlock) {
          insertionPoint = pred.lastInstruction;
          stage = ParallelMoveStage.input;
        } else {
          insertionPoint = _nextInstruction(block);
          stage = ParallelMoveStage.control;
        }
        final predEnd = blockEndPos(pred);
        // Insert moves between split live ranges at control flow edges
        // which do not match linearized control flow.
        if (block is! CatchBlock) {
          for (final instrId in liveness.liveIn(block).elements) {
            LiveRange? liveRange = _liveRanges[instrId]?.bundle;
            if (liveRange != null) {
              final from = liveRange.findSplitChildAt(predEnd - 1);
              final to = liveRange.findSplitChildAt(blockStart);
              if (from.allocatedLocation != to.allocatedLocation &&
                  to.allocatedLocation is! StackLocation) {
                _insertMoveBefore(
                  insertionPoint,
                  stage,
                  from.allocatedLocation!,
                  to.allocatedLocation!,
                );
              }
            }
          }
        }
        // Insert moves between phis and their inputs.
        if (block is JoinBlock) {
          for (final phi in block.phis) {
            final to = liveRangeFor(phi).bundle.findSplitChildAt(blockStart);
            final input = phi.inputDefAt(predIndex);
            if (input is Constant) {
              _insertMoveBefore(
                insertionPoint,
                stage,
                null,
                to.allocatedLocation!,
                input.value,
              );
            } else {
              final from = liveRangeFor(input).bundle
                  .findSplitChildAt(predEnd - 1);
              if (from.allocatedLocation != to.allocatedLocation) {
                _insertMoveBefore(
                  insertionPoint,
                  stage,
                  from.allocatedLocation!,
                  to.allocatedLocation!,
                );
              }
            }
          }
        }
        // In the beginning of a catch block load live values from
        // their corresponding spill slots.
        if (block is CatchBlock) {
          for (final instrId in liveness.liveIn(block).elements) {
            LiveRange? liveRange = _liveRanges[instrId]?.bundle;
            if (liveRange != null) {
              final to = liveRange.findSplitChildAt(blockStart);
              if (to.allocatedLocation is! StackLocation) {
                _insertMoveBefore(
                  insertionPoint,
                  stage,
                  liveRange.spillSlot!,
                  to.allocatedLocation!,
                );
              }
            }
          }
        }
      }
    }
  }
}

/// Single use of a [LiveRange].
class UsePosition {
  final int pos;
  final VirtualLocation vloc;
  Constraint constraint;

  UsePosition(this.pos, this.vloc, this.constraint);

  @override
  String toString() => 'Use[$pos, $constraint]';
}

/// A unit of register allocation.
///
/// Combines multiple related non-intersecting live ranges
/// which would benefit from being allocating to the same location.
/// Has a list of live intervals [s1, e1), [s2, e2), ...., [sN, eN).
class LiveRange {
  static const int maxUseIndex = 0xffffffff;

  static const int registerClassMask = 1 << 0;
  static const int isObjectPointerFlag = 1 << 1;
  static const int isPhysicalFlag = 1 << 2;

  int _flags;

  // List of intervals.
  IntervalList intervals = IntervalList();

  // Uses of this live range in the descending order.
  List<UsePosition> uses = [];

  // Live range where this live range was merged.
  LiveRange? mergedTo;

  // Original live range which was split.
  LiveRange? splitFrom;

  // Next live range which was split from this live range.
  LiveRange? splitNext;

  // Location assigned to this live range.
  Location? allocatedLocation;

  // Spill slot assigned to this live range (and all its split siblings).
  StackLocation? spillSlot;

  // Position of the Definition for this live range.
  int definitionPos = -1;

  // Used for the currently tracked live ranges (both active and inactive).
  // Index in [intervals].
  int currentInterval = 0;
  // uses.length - index in [uses].
  int currentUse = 1;

  LiveRange(
    RegisterClass registerClass, {
    required bool isObjectPointer,
    bool isPhysical = false,
  }) : assert((registerClass.index & registerClassMask) == registerClass.index),
       assert(registerClass == .cpu || !isObjectPointer),
       _flags =
           registerClass.index |
           (isObjectPointer ? isObjectPointerFlag : 0) |
           (isPhysical ? isPhysicalFlag : 0);

  RegisterClass get registerClass =>
      RegisterClass.values[_flags & registerClassMask];

  // Whether this live range is an object pointer and should be scanned by GC.
  bool get isObjectPointer => (_flags & isObjectPointerFlag) != 0;

  // Whether this live range represents a blocked physical register
  // or an allocatable/splittable/spillable live range.
  bool get isPhysical => (_flags & isPhysicalFlag) != 0;

  /// Add interval [start, end) to this live range.
  ///
  /// Intervals should be added in the descending order by the end position.
  /// Intersecting intervals are not allowed except nested intervals with
  /// the same starting position (which are ignored).
  void addInterval(int start, int end) {
    intervals.addInterval(start, end);
  }

  /// Cut the last use interval to start at [pos].
  void defineAt(int pos) {
    definitionPos = pos;
    if (intervals.isEmpty) {
      // Value is defined but not used.
      // Add synthetic interval. Make sure the intermediate point between
      // instructions is included into the interval as it is used to find
      // output location for a spill move.
      intervals.addInterval(
        pos,
        roundUp(pos + 1, LinearScanRegisterAllocator.step),
      );
    } else {
      assert(intervals.startAt(0) <= pos && pos < intervals.endAt(0));
      intervals.setStartAt(0, pos);
    }
  }

  VirtualLocation addUse(int pos, Constraint constr) {
    if (uses.isNotEmpty) {
      final last = uses.last;
      if (last.pos == pos) {
        // Reuse existing use with the same position.
        if (constr is PhysicalRegister &&
            last.constraint is! PhysicalRegister) {
          last.constraint = constr;
        }
        return last.vloc;
      }
    }
    final vloc = VirtualLocation();
    uses.add(UsePosition(pos, vloc, constr));
    return vloc;
  }

  int get start => intervals.start;
  int get end => intervals.end;

  LiveRange get bundle {
    LiveRange? parent = mergedTo;
    if (parent == null) return this;
    while (parent!.mergedTo != null) {
      parent = parent.mergedTo;
    }
    mergedTo = parent;
    return parent;
  }

  bool intersects(LiveRange other) => intervals.intersects(other.intervals);

  void tryMerge(LiveRange other) {
    assert(mergedTo == null && other.mergedTo == null);
    assert(!intervals.isEmpty && !other.intervals.isEmpty);
    if (this == other ||
        this.intersects(other) ||
        this.registerClass != other.registerClass ||
        this.isObjectPointer != other.isObjectPointer) {
      return;
    }
    intervals.merge(other.intervals);
    uses = _mergeUsePositions(uses, other.uses);
    other.mergedTo = this;
  }

  List<UsePosition> _mergeUsePositions(
    List<UsePosition> list1,
    List<UsePosition> list2,
  ) {
    final list = <UsePosition>[];
    var i = 0;
    var j = 0;
    while (i < list1.length && j < list2.length) {
      final u1 = list1[i];
      final u2 = list2[j];
      if (u1.pos >= u2.pos) {
        list.add(u1);
        ++i;
      } else {
        list.add(u2);
        ++j;
      }
    }
    while (i < list1.length) {
      list.add(list1[i++]);
    }
    while (j < list2.length) {
      list.add(list2[j++]);
    }
    return list;
  }

  LiveRange get splitParent => splitFrom ?? this;

  LiveRange splitAt(int pos) {
    assert(pos > start);
    assert(!isPhysical);
    assert(mergedTo == null);
    assert(splitNext == null || end <= splitNext!.start);
    final sibling = LiveRange(registerClass, isObjectPointer: isObjectPointer);
    sibling.splitFrom = splitParent;
    sibling.splitNext = splitNext;
    sibling.intervals = intervals.splitAt(pos);
    _splitUsePositions(pos, uses, sibling.uses);
    currentUse = math.max(1, currentUse - sibling.uses.length);
    splitNext = sibling;
    return sibling;
  }

  void _splitUsePositions(
    int pos,
    List<UsePosition> src,
    List<UsePosition> dst,
  ) {
    var i = 0;
    for (; i < src.length; ++i) {
      if (src[i].pos < pos) break;
    }
    dst.addAll(src.getRange(0, i));
    src.removeRange(0, i);
  }

  /// Advance [currentInterval] and [currentUse], skipping
  /// intervals and uses which end before [pos].
  /// Returns true if the whole live range ended before [pos].
  bool advance(int pos) {
    if (pos >= end) {
      currentInterval = intervals.length;
      currentUse = uses.length + 1;
      return true;
    }
    while (intervals.endAt(currentInterval) <= pos) {
      ++currentInterval;
    }
    while (currentUse <= uses.length &&
        uses[uses.length - currentUse].pos < pos) {
      ++currentUse;
    }
    return false;
  }

  UsePosition? findRegisterUseAfter(int pos) {
    assert(!isPhysical);
    for (int i = currentUse; i <= uses.length; ++i) {
      final use = uses[uses.length - i];
      if (use.pos >= pos) {
        final constr = use.constraint;
        if (constr is AnyCpuRegister ||
            constr is AnyFpuRegister ||
            constr is PhysicalRegister) {
          return use;
        }
      }
    }
    return null;
  }

  UsePosition? get nextUse =>
      (currentUse <= uses.length) ? uses[uses.length - currentUse] : null;

  (int, int)? get nextInterval => (currentInterval < intervals.length)
      ? (intervals.startAt(currentInterval), intervals.endAt(currentInterval))
      : null;

  bool nextIntervalContains(int pos) =>
      intervals.startAt(currentInterval) <= pos &&
      pos < intervals.endAt(currentInterval);

  UsePosition? get firstPreferredRegisterUse {
    for (final use in uses.reversed) {
      if (use.constraint is PhysicalRegister) {
        return use;
      }
    }
    return null;
  }

  void setLocation(Location loc) {
    assert(!isPhysical);
    allocatedLocation = loc;
    for (final use in uses) {
      use.vloc.location = loc;
    }
  }

  LiveRange findSplitChildAt(int pos) {
    for (LiveRange? range = this; range != null; range = range.splitNext) {
      if (range.start <= pos && pos < range.end) {
        return range;
      }
    }
    throw 'Unable to find cover for pos $pos in $this';
  }

  @override
  String toString() =>
      'LR $intervals ${uses.reversed} next: $nextInterval $nextUse';
}