c1_LinearScan.cpp

/*
 * Copyright (c) 2005, 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "c1/c1_CFGPrinter.hpp"
#include "c1/c1_CodeStubs.hpp"
#include "c1/c1_Compilation.hpp"
#include "c1/c1_FrameMap.hpp"
#include "c1/c1_IR.hpp"
#include "c1/c1_LinearScan.hpp"
#include "c1/c1_LIRGenerator.hpp"
#include "c1/c1_ValueStack.hpp"
#include "code/vmreg.inline.hpp"
#include "runtime/timerTrace.hpp"
#include "utilities/bitMap.inline.hpp"

#ifndef PRODUCT

  static LinearScanStatistic _stat_before_alloc;
  static LinearScanStatistic _stat_after_asign;
  static LinearScanStatistic _stat_final;

  static LinearScanTimers _total_timer;

  // helper macro for short definition of timer
  #define TIME_LINEAR_SCAN(timer_name)  TraceTime _block_timer("", _total_timer.timer(LinearScanTimers::timer_name), TimeLinearScan || TimeEachLinearScan, Verbose);

#else
  #define TIME_LINEAR_SCAN(timer_name)
#endif

#ifdef ASSERT

  // helper macro for short definition of trace-output inside code
  #define TRACE_LINEAR_SCAN(level, code)       \
    if (TraceLinearScanLevel >= level) {       \
      code;                                    \
    }
#else
  #define TRACE_LINEAR_SCAN(level, code)
#endif

// Map BasicType to spill size in 32-bit words, matching VMReg's notion of words
#ifdef _LP64
static int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 0, 2,  1, 2, 1, -1};
#else
static int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0, 1, -1, 1, 1, -1};
#endif


// Implementation of LinearScan

LinearScan::LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map)
 : _compilation(ir->compilation())
 , _ir(ir)
 , _gen(gen)
 , _frame_map(frame_map)
 , _cached_blocks(*ir->linear_scan_order())
 , _num_virtual_regs(gen->max_virtual_register_number())
 , _has_fpu_registers(false)
 , _num_calls(-1)
 , _max_spills(0)
 , _unused_spill_slot(-1)
 , _intervals(0)   // initialized later with correct length
 , _new_intervals_from_allocation(nullptr)
 , _sorted_intervals(nullptr)
 , _needs_full_resort(false)
 , _lir_ops(0)     // initialized later with correct length
 , _block_of_op(0) // initialized later with correct length
 , _has_info(0)
 , _has_call(0)
 , _interval_in_loop(0)  // initialized later with correct length
 , _scope_value_cache(0) // initialized later with correct length
{
  assert(this->ir() != nullptr,          "check if valid");
  assert(this->compilation() != nullptr, "check if valid");
  assert(this->gen() != nullptr,         "check if valid");
  assert(this->frame_map() != nullptr,   "check if valid");
}


// ********** functions for converting LIR-Operands to register numbers
//
// Emulate a flat register file comprising physical integer registers,
// physical floating-point registers and virtual registers, in that order.
// Virtual registers already have appropriate numbers, since V0 is
// the number of physical registers.
// Returns -1 for hi word if opr is a single word operand.
//
// Note: the inverse operation (calculating an operand for register numbers)
//       is done in calc_operand_for_interval()

int LinearScan::reg_num(LIR_Opr opr) {
  assert(opr->is_register(), "should not call this otherwise");

  if (opr->is_virtual_register()) {
    assert(opr->vreg_number() >= nof_regs, "found a virtual register with a fixed-register number");
    return opr->vreg_number();
  } else if (opr->is_single_cpu()) {
    return opr->cpu_regnr();
  } else if (opr->is_double_cpu()) {
    return opr->cpu_regnrLo();
#ifdef X86
  } else if (opr->is_single_xmm()) {
    return opr->fpu_regnr() + pd_first_xmm_reg;
  } else if (opr->is_double_xmm()) {
    return opr->fpu_regnrLo() + pd_first_xmm_reg;
#endif
  } else if (opr->is_single_fpu()) {
    return opr->fpu_regnr() + pd_first_fpu_reg;
  } else if (opr->is_double_fpu()) {
    return opr->fpu_regnrLo() + pd_first_fpu_reg;
  } else {
    ShouldNotReachHere();
    return -1;
  }
}

int LinearScan::reg_numHi(LIR_Opr opr) {
  assert(opr->is_register(), "should not call this otherwise");

  if (opr->is_virtual_register()) {
    return -1;
  } else if (opr->is_single_cpu()) {
    return -1;
  } else if (opr->is_double_cpu()) {
    return opr->cpu_regnrHi();
#ifdef X86
  } else if (opr->is_single_xmm()) {
    return -1;
  } else if (opr->is_double_xmm()) {
    return -1;
#endif
  } else if (opr->is_single_fpu()) {
    return -1;
  } else if (opr->is_double_fpu()) {
    return opr->fpu_regnrHi() + pd_first_fpu_reg;
  } else {
    ShouldNotReachHere();
    return -1;
  }
}


// ********** functions for classification of intervals

bool LinearScan::is_precolored_interval(const Interval* i) {
  return i->reg_num() < LinearScan::nof_regs;
}

bool LinearScan::is_virtual_interval(const Interval* i) {
  return i->reg_num() >= LIR_Opr::vreg_base;
}

bool LinearScan::is_precolored_cpu_interval(const Interval* i) {
  return i->reg_num() < LinearScan::nof_cpu_regs;
}

bool LinearScan::is_virtual_cpu_interval(const Interval* i) {
#if defined(__SOFTFP__) || defined(E500V2)
  return i->reg_num() >= LIR_Opr::vreg_base;
#else
  return i->reg_num() >= LIR_Opr::vreg_base && (i->type() != T_FLOAT && i->type() != T_DOUBLE);
#endif // __SOFTFP__ or E500V2
}

bool LinearScan::is_precolored_fpu_interval(const Interval* i) {
  return i->reg_num() >= LinearScan::nof_cpu_regs && i->reg_num() < LinearScan::nof_regs;
}

bool LinearScan::is_virtual_fpu_interval(const Interval* i) {
#if defined(__SOFTFP__) || defined(E500V2)
  return false;
#else
  return i->reg_num() >= LIR_Opr::vreg_base && (i->type() == T_FLOAT || i->type() == T_DOUBLE);
#endif // __SOFTFP__ or E500V2
}

bool LinearScan::is_in_fpu_register(const Interval* i) {
  // fixed intervals not needed for FPU stack allocation
  return i->reg_num() >= nof_regs && pd_first_fpu_reg <= i->assigned_reg() && i->assigned_reg() <= pd_last_fpu_reg;
}

bool LinearScan::is_oop_interval(const Interval* i) {
  // fixed intervals never contain oops
  return i->reg_num() >= nof_regs && i->type() == T_OBJECT;
}


// ********** General helper functions

// compute next unused stack index that can be used for spilling
int LinearScan::allocate_spill_slot(bool double_word) {
  int spill_slot;
  if (double_word) {
    if ((_max_spills & 1) == 1) {
      // alignment of double-word values
      // the hole because of the alignment is filled with the next single-word value
      assert(_unused_spill_slot == -1, "wasting a spill slot");
      _unused_spill_slot = _max_spills;
      _max_spills++;
    }
    spill_slot = _max_spills;
    _max_spills += 2;

  } else if (_unused_spill_slot != -1) {
    // re-use hole that was the result of a previous double-word alignment
    spill_slot = _unused_spill_slot;
    _unused_spill_slot = -1;

  } else {
    spill_slot = _max_spills;
    _max_spills++;
  }

  int result = spill_slot + LinearScan::nof_regs + frame_map()->argcount();

  // if too many slots used, bailout compilation.
  if (result > 2000) {
    bailout("too many stack slots used");
  }

  return result;
}

void LinearScan::assign_spill_slot(Interval* it) {
  // assign the canonical spill slot of the parent (if a part of the interval
  // is already spilled) or allocate a new spill slot
  if (it->canonical_spill_slot() >= 0) {
    it->assign_reg(it->canonical_spill_slot());
  } else {
    int spill = allocate_spill_slot(type2spill_size[it->type()] == 2);
    it->set_canonical_spill_slot(spill);
    it->assign_reg(spill);
  }
}

void LinearScan::propagate_spill_slots() {
  if (!frame_map()->finalize_frame(max_spills())) {
    bailout("frame too large");
  }
}

// create a new interval with a predefined reg_num
// (only used for parent intervals that are created during the building phase)
Interval* LinearScan::create_interval(int reg_num) {
  assert(_intervals.at(reg_num) == nullptr, "overwriting existing interval");

  Interval* interval = new Interval(reg_num);
  _intervals.at_put(reg_num, interval);

  // assign register number for precolored intervals
  if (reg_num < LIR_Opr::vreg_base) {
    interval->assign_reg(reg_num);
  }
  return interval;
}

// assign a new reg_num to the interval and append it to the list of intervals
// (only used for child intervals that are created during register allocation)
void LinearScan::append_interval(Interval* it) {
  it->set_reg_num(_intervals.length());
  _intervals.append(it);
  IntervalList* new_intervals = _new_intervals_from_allocation;
  if (new_intervals == nullptr) {
    new_intervals = _new_intervals_from_allocation = new IntervalList();
  }
  new_intervals->append(it);
}

// copy the vreg-flags if an interval is split
void LinearScan::copy_register_flags(Interval* from, Interval* to) {
  if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::byte_reg)) {
    gen()->set_vreg_flag(to->reg_num(), LIRGenerator::byte_reg);
  }
  if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::callee_saved)) {
    gen()->set_vreg_flag(to->reg_num(), LIRGenerator::callee_saved);
  }

  // Note: do not copy the must_start_in_memory flag because it is not necessary for child
  //       intervals (only the very beginning of the interval must be in memory)
}


// ********** spill move optimization
// eliminate moves from register to stack if stack slot is known to be correct

// called during building of intervals
void LinearScan::change_spill_definition_pos(Interval* interval, int def_pos) {
  assert(interval->is_split_parent(), "can only be called for split parents");

  switch (interval->spill_state()) {
    case noDefinitionFound:
      assert(interval->spill_definition_pos() == -1, "must no be set before");
      interval->set_spill_definition_pos(def_pos);
      interval->set_spill_state(oneDefinitionFound);
      break;

    case oneDefinitionFound:
      assert(def_pos <= interval->spill_definition_pos(), "positions are processed in reverse order when intervals are created");
      if (def_pos < interval->spill_definition_pos() - 2) {
        // second definition found, so no spill optimization possible for this interval
        interval->set_spill_state(noOptimization);
      } else {
        // two consecutive definitions (because of two-operand LIR form)
        assert(block_of_op_with_id(def_pos) == block_of_op_with_id(interval->spill_definition_pos()), "block must be equal");
      }
      break;

    case noOptimization:
      // nothing to do
      break;

    default:
      assert(false, "other states not allowed at this time");
  }
}

// called during register allocation
void LinearScan::change_spill_state(Interval* interval, int spill_pos) {
  switch (interval->spill_state()) {
    case oneDefinitionFound: {
      int def_loop_depth = block_of_op_with_id(interval->spill_definition_pos())->loop_depth();
      int spill_loop_depth = block_of_op_with_id(spill_pos)->loop_depth();

      if (def_loop_depth < spill_loop_depth) {
        // the loop depth of the spilling position is higher then the loop depth
        // at the definition of the interval -> move write to memory out of loop
        // by storing at definitin of the interval
        interval->set_spill_state(storeAtDefinition);
      } else {
        // the interval is currently spilled only once, so for now there is no
        // reason to store the interval at the definition
        interval->set_spill_state(oneMoveInserted);
      }
      break;
    }

    case oneMoveInserted: {
      // the interval is spilled more then once, so it is better to store it to
      // memory at the definition
      interval->set_spill_state(storeAtDefinition);
      break;
    }

    case storeAtDefinition:
    case startInMemory:
    case noOptimization:
    case noDefinitionFound:
      // nothing to do
      break;

    default:
      assert(false, "other states not allowed at this time");
  }
}


bool LinearScan::must_store_at_definition(const Interval* i) {
  return i->is_split_parent() && i->spill_state() == storeAtDefinition;
}

// called once before assignment of register numbers
void LinearScan::eliminate_spill_moves() {
  TIME_LINEAR_SCAN(timer_eliminate_spill_moves);
  TRACE_LINEAR_SCAN(3, tty->print_cr("***** Eliminating unnecessary spill moves"));

  // collect all intervals that must be stored after their definion.
  // the list is sorted by Interval::spill_definition_pos
  Interval* interval;
  Interval* temp_list;
  create_unhandled_lists(&interval, &temp_list, must_store_at_definition, nullptr);

#ifdef ASSERT
  Interval* prev = nullptr;
  Interval* temp = interval;
  while (temp != Interval::end()) {
    assert(temp->spill_definition_pos() > 0, "invalid spill definition pos");
    if (prev != nullptr) {
      assert(temp->from() >= prev->from(), "intervals not sorted");
      assert(temp->spill_definition_pos() >= prev->spill_definition_pos(), "when intervals are sorted by from, then they must also be sorted by spill_definition_pos");
    }

    assert(temp->canonical_spill_slot() >= LinearScan::nof_regs, "interval has no spill slot assigned");
    assert(temp->spill_definition_pos() >= temp->from(), "invalid order");
    assert(temp->spill_definition_pos() <= temp->from() + 2, "only intervals defined once at their start-pos can be optimized");

    TRACE_LINEAR_SCAN(4, tty->print_cr("interval %d (from %d to %d) must be stored at %d", temp->reg_num(), temp->from(), temp->to(), temp->spill_definition_pos()));

    temp = temp->next();
  }
#endif

  LIR_InsertionBuffer insertion_buffer;
  int num_blocks = block_count();
  for (int i = 0; i < num_blocks; i++) {
    BlockBegin* block = block_at(i);
    LIR_OpList* instructions = block->lir()->instructions_list();
    int         num_inst = instructions->length();
    bool        has_new = false;

    // iterate all instructions of the block. skip the first because it is always a label
    for (int j = 1; j < num_inst; j++) {
      LIR_Op* op = instructions->at(j);
      int op_id = op->id();

      if (op_id == -1) {
        // remove move from register to stack if the stack slot is guaranteed to be correct.
        // only moves that have been inserted by LinearScan can be removed.
        assert(op->code() == lir_move, "only moves can have a op_id of -1");
        assert(op->as_Op1() != nullptr, "move must be LIR_Op1");
        assert(op->as_Op1()->result_opr()->is_virtual(), "LinearScan inserts only moves to virtual registers");

        LIR_Op1* op1 = (LIR_Op1*)op;
        Interval* interval = interval_at(op1->result_opr()->vreg_number());

        if (interval->assigned_reg() >= LinearScan::nof_regs && interval->always_in_memory()) {
          // move target is a stack slot that is always correct, so eliminate instruction
          TRACE_LINEAR_SCAN(4, tty->print_cr("eliminating move from interval %d to %d", op1->in_opr()->vreg_number(), op1->result_opr()->vreg_number()));
          instructions->at_put(j, nullptr); // null-instructions are deleted by assign_reg_num
        }

      } else {
        // insert move from register to stack just after the beginning of the interval
        assert(interval == Interval::end() || interval->spill_definition_pos() >= op_id, "invalid order");
        assert(interval == Interval::end() || (interval->is_split_parent() && interval->spill_state() == storeAtDefinition), "invalid interval");

        while (interval != Interval::end() && interval->spill_definition_pos() == op_id) {
          if (!has_new) {
            // prepare insertion buffer (appended when all instructions of the block are processed)
            insertion_buffer.init(block->lir());
            has_new = true;
          }

          LIR_Opr from_opr = operand_for_interval(interval);
          LIR_Opr to_opr = canonical_spill_opr(interval);
          assert(from_opr->is_fixed_cpu() || from_opr->is_fixed_fpu(), "from operand must be a register");
          assert(to_opr->is_stack(), "to operand must be a stack slot");

          insertion_buffer.move(j, from_opr, to_opr);
          TRACE_LINEAR_SCAN(4, tty->print_cr("inserting move after definition of interval %d to stack slot %d at op_id %d", interval->reg_num(), interval->canonical_spill_slot() - LinearScan::nof_regs, op_id));

          interval = interval->next();
        }
      }
    } // end of instruction iteration

    if (has_new) {
      block->lir()->append(&insertion_buffer);
    }
  } // end of block iteration

  assert(interval == Interval::end(), "missed an interval");
}


// ********** Phase 1: number all instructions in all blocks
// Compute depth-first and linear scan block orders, and number LIR_Op nodes for linear scan.

void LinearScan::number_instructions() {
  {
    // dummy-timer to measure the cost of the timer itself
    // (this time is then subtracted from all other timers to get the real value)
    TIME_LINEAR_SCAN(timer_do_nothing);
  }
  TIME_LINEAR_SCAN(timer_number_instructions);

  // Assign IDs to LIR nodes and build a mapping, lir_ops, from ID to LIR_Op node.
  int num_blocks = block_count();
  int num_instructions = 0;
  int i;
  for (i = 0; i < num_blocks; i++) {
    num_instructions += block_at(i)->lir()->instructions_list()->length();
  }

  // initialize with correct length
  _lir_ops = LIR_OpArray(num_instructions, num_instructions, nullptr);
  _block_of_op = BlockBeginArray(num_instructions, num_instructions, nullptr);

  int op_id = 0;
  int idx = 0;

  for (i = 0; i < num_blocks; i++) {
    BlockBegin* block = block_at(i);
    block->set_first_lir_instruction_id(op_id);
    LIR_OpList* instructions = block->lir()->instructions_list();

    int num_inst = instructions->length();
    for (int j = 0; j < num_inst; j++) {
      LIR_Op* op = instructions->at(j);
      op->set_id(op_id);

      _lir_ops.at_put(idx, op);
      _block_of_op.at_put(idx, block);
      assert(lir_op_with_id(op_id) == op, "must match");

      idx++;
      op_id += 2; // numbering of lir_ops by two
    }
    block->set_last_lir_instruction_id(op_id - 2);
  }
  assert(idx == num_instructions, "must match");
  assert(idx * 2 == op_id, "must match");

  _has_call.initialize(num_instructions);
  _has_info.initialize(num_instructions);
}


// ********** Phase 2: compute local live sets separately for each block
// (sets live_gen and live_kill for each block)

void LinearScan::set_live_gen_kill(Value value, LIR_Op* op, BitMap& live_gen, BitMap& live_kill) {
  LIR_Opr opr = value->operand();
  Constant* con = value->as_Constant();

  // check some asumptions about debug information
  assert(!value->type()->is_illegal(), "if this local is used by the interpreter it shouldn't be of indeterminate type");
  assert(con == nullptr || opr->is_virtual() || opr->is_constant() || opr->is_illegal(), "assumption: Constant instructions have only constant operands");
  assert(con != nullptr || opr->is_virtual(), "assumption: non-Constant instructions have only virtual operands");

  if ((con == nullptr || con->is_pinned()) && opr->is_register()) {
    assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
    int reg = opr->vreg_number();
    if (!live_kill.at(reg)) {
      live_gen.set_bit(reg);
      TRACE_LINEAR_SCAN(4, tty->print_cr("  Setting live_gen for value %c%d, LIR op_id %d, register number %d", value->type()->tchar(), value->id(), op->id(), reg));
    }
  }
}


void LinearScan::compute_local_live_sets() {
  TIME_LINEAR_SCAN(timer_compute_local_live_sets);

  int  num_blocks = block_count();
  int  live_size = live_set_size();
  bool local_has_fpu_registers = false;
  int  local_num_calls = 0;
  LIR_OpVisitState visitor;

  BitMap2D local_interval_in_loop = BitMap2D(_num_virtual_regs, num_loops());

  // iterate all blocks
  for (int i = 0; i < num_blocks; i++) {
    BlockBegin* block = block_at(i);

    ResourceBitMap live_gen(live_size);
    ResourceBitMap live_kill(live_size);

    if (block->is_set(BlockBegin::exception_entry_flag)) {
      // Phi functions at the begin of an exception handler are
      // implicitly defined (= killed) at the beginning of the block.
      for_each_phi_fun(block, phi,
        if (!phi->is_illegal()) { live_kill.set_bit(phi->operand()->vreg_number()); }
      );
    }

    LIR_OpList* instructions = block->lir()->instructions_list();
    int num_inst = instructions->length();

    // iterate all instructions of the block. skip the first because it is always a label
    assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
    for (int j = 1; j < num_inst; j++) {
      LIR_Op* op = instructions->at(j);

      // visit operation to collect all operands
      visitor.visit(op);

      if (visitor.has_call()) {
        _has_call.set_bit(op->id() >> 1);
        local_num_calls++;
      }
      if (visitor.info_count() > 0) {
        _has_info.set_bit(op->id() >> 1);
      }

      // iterate input operands of instruction
      int k, n, reg;
      n = visitor.opr_count(LIR_OpVisitState::inputMode);
      for (k = 0; k < n; k++) {
        LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
        assert(opr->is_register(), "visitor should only return register operands");

        if (opr->is_virtual_register()) {
          assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
          reg = opr->vreg_number();
          if (!live_kill.at(reg)) {
            live_gen.set_bit(reg);
            TRACE_LINEAR_SCAN(4, tty->print_cr("  Setting live_gen for register %d at instruction %d", reg, op->id()));
          }
          if (block->loop_index() >= 0) {
            local_interval_in_loop.set_bit(reg, block->loop_index());
          }
          local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
        }

#ifdef ASSERT
        // fixed intervals are never live at block boundaries, so
        // they need not be processed in live sets.
        // this is checked by these assertions to be sure about it.
        // the entry block may have incoming values in registers, which is ok.
        if (!opr->is_virtual_register() && block != ir()->start()) {
          reg = reg_num(opr);
          if (is_processed_reg_num(reg)) {
            assert(live_kill.at(reg), "using fixed register that is not defined in this block");
          }
          reg = reg_numHi(opr);
          if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
            assert(live_kill.at(reg), "using fixed register that is not defined in this block");
          }
        }
#endif
      }

      // Add uses of live locals from interpreter's point of view for proper debug information generation
      n = visitor.info_count();
      for (k = 0; k < n; k++) {
        CodeEmitInfo* info = visitor.info_at(k);
        ValueStack* stack = info->stack();
        for_each_state_value(stack, value,
          set_live_gen_kill(value, op, live_gen, live_kill);
          local_has_fpu_registers = local_has_fpu_registers || value->type()->is_float_kind();
        );
      }

      // iterate temp operands of instruction
      n = visitor.opr_count(LIR_OpVisitState::tempMode);
      for (k = 0; k < n; k++) {
        LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
        assert(opr->is_register(), "visitor should only return register operands");

        if (opr->is_virtual_register()) {
          assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
          reg = opr->vreg_number();
          live_kill.set_bit(reg);
          if (block->loop_index() >= 0) {
            local_interval_in_loop.set_bit(reg, block->loop_index());
          }
          local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
        }

#ifdef ASSERT
        // fixed intervals are never live at block boundaries, so
        // they need not be processed in live sets
        // process them only in debug mode so that this can be checked
        if (!opr->is_virtual_register()) {
          reg = reg_num(opr);
          if (is_processed_reg_num(reg)) {
            live_kill.set_bit(reg_num(opr));
          }
          reg = reg_numHi(opr);
          if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
            live_kill.set_bit(reg);
          }
        }
#endif
      }

      // iterate output operands of instruction
      n = visitor.opr_count(LIR_OpVisitState::outputMode);
      for (k = 0; k < n; k++) {
        LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::outputMode, k);
        assert(opr->is_register(), "visitor should only return register operands");

        if (opr->is_virtual_register()) {
          assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
          reg = opr->vreg_number();
          live_kill.set_bit(reg);
          if (block->loop_index() >= 0) {
            local_interval_in_loop.set_bit(reg, block->loop_index());
          }
          local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
        }

#ifdef ASSERT
        // fixed intervals are never live at block boundaries, so
        // they need not be processed in live sets
        // process them only in debug mode so that this can be checked
        if (!opr->is_virtual_register()) {
          reg = reg_num(opr);
          if (is_processed_reg_num(reg)) {
            live_kill.set_bit(reg_num(opr));
          }
          reg = reg_numHi(opr);
          if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
            live_kill.set_bit(reg);
          }
        }
#endif
      }
    } // end of instruction iteration

    block->set_live_gen (live_gen);
    block->set_live_kill(live_kill);
    block->set_live_in  (ResourceBitMap(live_size));
    block->set_live_out (ResourceBitMap(live_size));

    TRACE_LINEAR_SCAN(4, tty->print("live_gen  B%d ", block->block_id()); print_bitmap(block->live_gen()));
    TRACE_LINEAR_SCAN(4, tty->print("live_kill B%d ", block->block_id()); print_bitmap(block->live_kill()));
  } // end of block iteration

  // propagate local calculated information into LinearScan object
  _has_fpu_registers = local_has_fpu_registers;
  compilation()->set_has_fpu_code(local_has_fpu_registers);

  _num_calls = local_num_calls;
  _interval_in_loop = local_interval_in_loop;
}


// ********** Phase 3: perform a backward dataflow analysis to compute global live sets
// (sets live_in and live_out for each block)

void LinearScan::compute_global_live_sets() {
  TIME_LINEAR_SCAN(timer_compute_global_live_sets);

  int  num_blocks = block_count();
  bool change_occurred;
  bool change_occurred_in_block;
  int  iteration_count = 0;
  ResourceBitMap live_out(live_set_size()); // scratch set for calculations

  // Perform a backward dataflow analysis to compute live_out and live_in for each block.
  // The loop is executed until a fixpoint is reached (no changes in an iteration)
  // Exception handlers must be processed because not all live values are
  // present in the state array, e.g. because of global value numbering
  do {
    change_occurred = false;

    // iterate all blocks in reverse order
    for (int i = num_blocks - 1; i >= 0; i--) {
      BlockBegin* block = block_at(i);

      change_occurred_in_block = false;

      // live_out(block) is the union of live_in(sux), for successors sux of block
      int n = block->number_of_sux();
      int e = block->number_of_exception_handlers();
      if (n + e > 0) {
        // block has successors
        if (n > 0) {
          live_out.set_from(block->sux_at(0)->live_in());
          for (int j = 1; j < n; j++) {
            live_out.set_union(block->sux_at(j)->live_in());
          }
        } else {
          live_out.clear();
        }
        for (int j = 0; j < e; j++) {
          live_out.set_union(block->exception_handler_at(j)->live_in());
        }

        if (!block->live_out().is_same(live_out)) {
          // A change occurred.  Swap the old and new live out sets to avoid copying.
          ResourceBitMap temp = block->live_out();
          block->set_live_out(live_out);
          live_out = temp;

          change_occurred = true;
          change_occurred_in_block = true;
        }
      }

      if (iteration_count == 0 || change_occurred_in_block) {
        // live_in(block) is the union of live_gen(block) with (live_out(block) & !live_kill(block))
        // note: live_in has to be computed only in first iteration or if live_out has changed!
        ResourceBitMap live_in = block->live_in();
        live_in.set_from(block->live_out());
        live_in.set_difference(block->live_kill());
        live_in.set_union(block->live_gen());
      }

#ifdef ASSERT
      if (TraceLinearScanLevel >= 4) {
        char c = ' ';
        if (iteration_count == 0 || change_occurred_in_block) {
          c = '*';
        }
        tty->print("(%d) live_in%c  B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_in());
        tty->print("(%d) live_out%c B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_out());
      }
#endif
    }
    iteration_count++;

    if (change_occurred && iteration_count > 50) {
      BAILOUT("too many iterations in compute_global_live_sets");
    }
  } while (change_occurred);


#ifdef ASSERT
  // check that fixed intervals are not live at block boundaries
  // (live set must be empty at fixed intervals)
  for (int i = 0; i < num_blocks; i++) {
    BlockBegin* block = block_at(i);
    for (int j = 0; j < LIR_Opr::vreg_base; j++) {
      assert(block->live_in().at(j)  == false, "live_in  set of fixed register must be empty");
      assert(block->live_out().at(j) == false, "live_out set of fixed register must be empty");
      assert(block->live_gen().at(j) == false, "live_gen set of fixed register must be empty");
    }
  }
#endif

  // check that the live_in set of the first block is empty
  ResourceBitMap live_in_args(ir()->start()->live_in().size());
  if (!ir()->start()->live_in().is_same(live_in_args)) {
#ifdef ASSERT
    tty->print_cr("Error: live_in set of first block must be empty (when this fails, virtual registers are used before they are defined)");
    tty->print_cr("affected registers:");
    print_bitmap(ir()->start()->live_in());

    // print some additional information to simplify debugging
    for (unsigned int i = 0; i < ir()->start()->live_in().size(); i++) {
      if (ir()->start()->live_in().at(i)) {
        Instruction* instr = gen()->instruction_for_vreg(i);
        tty->print_cr("* vreg %d (HIR instruction %c%d)", i, instr == nullptr ? ' ' : instr->type()->tchar(), instr == nullptr ? 0 : instr->id());

        for (int j = 0; j < num_blocks; j++) {
          BlockBegin* block = block_at(j);
          if (block->live_gen().at(i)) {
            tty->print_cr("  used in block B%d", block->block_id());
          }
          if (block->live_kill().at(i)) {
            tty->print_cr("  defined in block B%d", block->block_id());
          }
        }
      }
    }

#endif
    // when this fails, virtual registers are used before they are defined.
    assert(false, "live_in set of first block must be empty");
    // bailout of if this occurs in product mode.
    bailout("live_in set of first block not empty");
  }
}


// ********** Phase 4: build intervals
// (fills the list _intervals)

void LinearScan::add_use(Value value, int from, int to, IntervalUseKind use_kind) {
  assert(!value->type()->is_illegal(), "if this value is used by the interpreter it shouldn't be of indeterminate type");
  LIR_Opr opr = value->operand();
  Constant* con = value->as_Constant();

  if ((con == nullptr || con->is_pinned()) && opr->is_register()) {
    assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
    add_use(opr, from, to, use_kind);
  }
}


void LinearScan::add_def(LIR_Opr opr, int def_pos, IntervalUseKind use_kind) {
  TRACE_LINEAR_SCAN(2, tty->print(" def "); opr->print(tty); tty->print_cr(" def_pos %d (%d)", def_pos, use_kind));
  assert(opr->is_register(), "should not be called otherwise");

  if (opr->is_virtual_register()) {
    assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
    add_def(opr->vreg_number(), def_pos, use_kind, opr->type_register());

  } else {
    int reg = reg_num(opr);
    if (is_processed_reg_num(reg)) {
      add_def(reg, def_pos, use_kind, opr->type_register());
    }
    reg = reg_numHi(opr);
    if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
      add_def(reg, def_pos, use_kind, opr->type_register());
    }
  }
}

void LinearScan::add_use(LIR_Opr opr, int from, int to, IntervalUseKind use_kind) {
  TRACE_LINEAR_SCAN(2, tty->print(" use "); opr->print(tty); tty->print_cr(" from %d to %d (%d)", from, to, use_kind));
  assert(opr->is_register(), "should not be called otherwise");

  if (opr->is_virtual_register()) {
    assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
    add_use(opr->vreg_number(), from, to, use_kind, opr->type_register());

  } else {
    int reg = reg_num(opr);
    if (is_processed_reg_num(reg)) {
      add_use(reg, from, to, use_kind, opr->type_register());
    }
    reg = reg_numHi(opr);
    if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
      add_use(reg, from, to, use_kind, opr->type_register());
    }
  }
}

void LinearScan::add_temp(LIR_Opr opr, int temp_pos, IntervalUseKind use_kind) {
  TRACE_LINEAR_SCAN(2, tty->print(" temp "); opr->print(tty); tty->print_cr(" temp_pos %d (%d)", temp_pos, use_kind));
  assert(opr->is_register(), "should not be called otherwise");

  if (opr->is_virtual_register()) {
    assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
    add_temp(opr->vreg_number(), temp_pos, use_kind, opr->type_register());

  } else {
    int reg = reg_num(opr);
    if (is_processed_reg_num(reg)) {
      add_temp(reg, temp_pos, use_kind, opr->type_register());
    }
    reg = reg_numHi(opr);
    if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
      add_temp(reg, temp_pos, use_kind, opr->type_register());
    }
  }
}


void LinearScan::add_def(int reg_num, int def_pos, IntervalUseKind use_kind, BasicType type) {
  Interval* interval = interval_at(reg_num);
  if (interval != nullptr) {
    assert(interval->reg_num() == reg_num, "wrong interval");

    if (type != T_ILLEGAL) {
      interval->set_type(type);
    }

    Range* r = interval->first();
    if (r->from() <= def_pos) {
      // Update the starting point (when a range is first created for a use, its
      // start is the beginning of the current block until a def is encountered.)
      r->set_from(def_pos);
      interval->add_use_pos(def_pos, use_kind);

    } else {
      // Dead value - make vacuous interval
      // also add use_kind for dead intervals
      interval->add_range(def_pos, def_pos + 1);
      interval->add_use_pos(def_pos, use_kind);
      TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: def of reg %d at %d occurs without use", reg_num, def_pos));
    }

  } else {
    // Dead value - make vacuous interval
    // also add use_kind for dead intervals
    interval = create_interval(reg_num);
    if (type != T_ILLEGAL) {
      interval->set_type(type);
    }

    interval->add_range(def_pos, def_pos + 1);
    interval->add_use_pos(def_pos, use_kind);
    TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: dead value %d at %d in live intervals", reg_num, def_pos));
  }

  change_spill_definition_pos(interval, def_pos);
  if (use_kind == noUse && interval->spill_state() <= startInMemory) {
        // detection of method-parameters and roundfp-results
        // TODO: move this directly to position where use-kind is computed
    interval->set_spill_state(startInMemory);
  }
}

void LinearScan::add_use(int reg_num, int from, int to, IntervalUseKind use_kind, BasicType type) {
  Interval* interval = interval_at(reg_num);
  if (interval == nullptr) {
    interval = create_interval(reg_num);
  }
  assert(interval->reg_num() == reg_num, "wrong interval");

  if (type != T_ILLEGAL) {
    interval->set_type(type);
  }

  interval->add_range(from, to);
  interval->add_use_pos(to, use_kind);
}

void LinearScan::add_temp(int reg_num, int temp_pos, IntervalUseKind use_kind, BasicType type) {
  Interval* interval = interval_at(reg_num);
  if (interval == nullptr) {
    interval = create_interval(reg_num);