Quelle c1_LinearScan.cpp Sprache: C

/*
* Copyright (c) 2005, 2022, 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 "precompiled.hpp"
#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_LIRGenerator.hpp"
#include "c1/c1_LinearScan.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(NULL)
, _sorted_intervals(NULL)
, _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
#ifdef IA32
, _fpu_stack_allocator(NULL)
#endif
{
  assert(this->ir() != NULL,          "check if valid");
  assert(this->compilation() != NULL, "check if valid");
  assert(this->gen() != NULL,         "check if valid");
  assert(this->frame_map() != NULL,   "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) == NULL, "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 == NULL) {
    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, NULL);

#ifdef ASSERT
  Interval* prev = NULL;
  Interval* temp = interval;
  while (temp != Interval::end()) {
    assert(temp->spill_definition_pos() > 0, "invalid spill definition pos");
    if (prev != NULL) {
      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() != NULL, "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, NULL); // 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, NULL);
  _block_of_op = BlockBeginArray(num_instructions, num_instructions, NULL);

  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 == NULL || opr->is_virtual() || opr->is_constant() || opr->is_illegal(), "assumption: Constant instructions have only constant operands");
  assert(con != NULL || opr->is_virtual(), "assumption: non-Constant instructions have only virtual operands");

  if ((con == NULL || 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 == NULL ? ' ' : instr->type()->tchar(), instr == NULL ? 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 == NULL || 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 != NULL) {
    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 == NULL) {
    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 == NULL) {
    interval = create_interval(reg_num);
  }
  assert(interval->reg_num() == reg_num, "wrong interval");

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

  interval->add_range(temp_pos, temp_pos + 1);
  interval->add_use_pos(temp_pos, use_kind);
}

// the results of this functions are used for optimizing spilling and reloading
// if the functions return shouldHaveRegister and the interval is spilled,
// it is not reloaded to a register.
IntervalUseKind LinearScan::use_kind_of_output_operand(LIR_Op* op, LIR_Opr opr) {
  if (op->code() == lir_move) {
    assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
    LIR_Op1* move = (LIR_Op1*)op;
    LIR_Opr res = move->result_opr();
    bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);

    if (result_in_memory) {
      // Begin of an interval with must_start_in_memory set.
      // This interval will always get a stack slot first, so return noUse.
      return noUse;

    } else if (move->in_opr()->is_stack()) {
      // method argument (condition must be equal to handle_method_arguments)
      return noUse;

    } else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
      // Move from register to register
      if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
        // special handling of phi-function moves inside osr-entry blocks
        // input operand must have a register instead of output operand (leads to better register allocation)
        return shouldHaveRegister;
      }
    }
  }

  if (opr->is_virtual() &&
      gen()->is_vreg_flag_set(opr->vreg_number(), LIRGenerator::must_start_in_memory)) {
    // result is a stack-slot, so prevent immediate reloading
    return noUse;
  }

  // all other operands require a register
  return mustHaveRegister;
}

IntervalUseKind LinearScan::use_kind_of_input_operand(LIR_Op* op, LIR_Opr opr) {
  if (op->code() == lir_move) {
    assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
    LIR_Op1* move = (LIR_Op1*)op;
    LIR_Opr res = move->result_opr();
    bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);

    if (result_in_memory) {
      // Move to an interval with must_start_in_memory set.
      // To avoid moves from stack to stack (not allowed) force the input operand to a register
      return mustHaveRegister;

    } else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
      // Move from register to register
      if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
        // special handling of phi-function moves inside osr-entry blocks
        // input operand must have a register instead of output operand (leads to better register allocation)
        return mustHaveRegister;
      }

      // The input operand is not forced to a register (moves from stack to register are allowed),
      // but it is faster if the input operand is in a register
      return shouldHaveRegister;
    }
  }

#if defined(X86) || defined(S390)
  if (op->code() == lir_cmove) {
    // conditional moves can handle stack operands
    assert(op->result_opr()->is_register(), "result must always be in a register");
    return shouldHaveRegister;
  }

  // optimizations for second input operand of arithmehtic operations on Intel
  // this operand is allowed to be on the stack in some cases
  BasicType opr_type = opr->type_register();
  if (opr_type == T_FLOAT || opr_type == T_DOUBLE) {
    if (IA32_ONLY( (UseSSE == 1 && opr_type == T_FLOAT) || UseSSE >= 2 ) NOT_IA32( true )) {
      // SSE float instruction (T_DOUBLE only supported with SSE2)
      switch (op->code()) {
        case lir_cmp:
        case lir_add:
        case lir_sub:
        case lir_mul:
        case lir_div:
        {
          assert(op->as_Op2() != NULL, "must be LIR_Op2");
          LIR_Op2* op2 = (LIR_Op2*)op;
          if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
            assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
            return shouldHaveRegister;
          }
        }
        default:
          break;
      }
    } else {
      // FPU stack float instruction
      switch (op->code()) {
        case lir_add:
        case lir_sub:
        case lir_mul:
        case lir_div:
        {
          assert(op->as_Op2() != NULL, "must be LIR_Op2");
          LIR_Op2* op2 = (LIR_Op2*)op;
          if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
            assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
            return shouldHaveRegister;
          }
        }
        default:
          break;
      }
    }
    // We want to sometimes use logical operations on pointers, in particular in GC barriers.
    // Since 64bit logical operations do not current support operands on stack, we have to make sure
    // T_OBJECT doesn't get spilled along with T_LONG.
  } else if (opr_type != T_LONG LP64_ONLY(&& opr_type != T_OBJECT)) {
    // integer instruction (note: long operands must always be in register)
    switch (op->code()) {
      case lir_cmp:
      case lir_add:
      case lir_sub:
      case lir_logic_and:
      case lir_logic_or:
      case lir_logic_xor:
      {
        assert(op->as_Op2() != NULL, "must be LIR_Op2");
        LIR_Op2* op2 = (LIR_Op2*)op;
        if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
          assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
          return shouldHaveRegister;
        }
      }
      default:
        break;
    }
  }
#endif // X86 || S390

  // all other operands require a register
  return mustHaveRegister;
}

void LinearScan::handle_method_arguments(LIR_Op* op) {
  // special handling for method arguments (moves from stack to virtual register):
  // the interval gets no register assigned, but the stack slot.
  // it is split before the first use by the register allocator.

  if (op->code() == lir_move) {
    assert(op->as_Op1() != NULL, "must be LIR_Op1");
    LIR_Op1* move = (LIR_Op1*)op;

    if (move->in_opr()->is_stack()) {
#ifdef ASSERT
      int arg_size = compilation()->method()->arg_size();
      LIR_Opr o = move->in_opr();
      if (o->is_single_stack()) {
        assert(o->single_stack_ix() >= 0 && o->single_stack_ix() < arg_size, "out of range");
      } else if (o->is_double_stack()) {
        assert(o->double_stack_ix() >= 0 && o->double_stack_ix() < arg_size, "out of range");
      } else {
        ShouldNotReachHere();
      }

      assert(move->id() > 0, "invalid id");
      assert(block_of_op_with_id(move->id())->number_of_preds() == 0, "move from stack must be in first block");
      assert(move->result_opr()->is_virtual(), "result of move must be a virtual register");

      TRACE_LINEAR_SCAN(4, tty->print_cr("found move from stack slot %d to vreg %d", o->is_single_stack() ? o->single_stack_ix() : o->double_stack_ix(), reg_num(move->result_opr())));
#endif

      Interval* interval = interval_at(reg_num(move->result_opr()));

      int stack_slot = LinearScan::nof_regs + (move->in_opr()->is_single_stack() ? move->in_opr()->single_stack_ix() : move->in_opr()->double_stack_ix());
      interval->set_canonical_spill_slot(stack_slot);
      interval->assign_reg(stack_slot);
    }
  }
}

void LinearScan::handle_doubleword_moves(LIR_Op* op) {
  // special handling for doubleword move from memory to register:
  // in this case the registers of the input address and the result
  // registers must not overlap -> add a temp range for the input registers
  if (op->code() == lir_move) {
    assert(op->as_Op1() != NULL, "must be LIR_Op1");
    LIR_Op1* move = (LIR_Op1*)op;

    if (move->result_opr()->is_double_cpu() && move->in_opr()->is_pointer()) {
      LIR_Address* address = move->in_opr()->as_address_ptr();
      if (address != NULL) {
        if (address->base()->is_valid()) {
          add_temp(address->base(), op->id(), noUse);
        }
        if (address->index()->is_valid()) {
          add_temp(address->index(), op->id(), noUse);
        }
      }
    }
  }
}

void LinearScan::add_register_hints(LIR_Op* op) {
  switch (op->code()) {
    case lir_move:      // fall through
    case lir_convert: {
      assert(op->as_Op1() != NULL, "lir_move, lir_convert must be LIR_Op1");
      LIR_Op1* move = (LIR_Op1*)op;

      LIR_Opr move_from = move->in_opr();
      LIR_Opr move_to = move->result_opr();

      if (move_to->is_register() && move_from->is_register()) {
        Interval* from = interval_at(reg_num(move_from));
        Interval* to = interval_at(reg_num(move_to));
        if (from != NULL && to != NULL) {
          to->set_register_hint(from);
          TRACE_LINEAR_SCAN(4, tty->print_cr("operation at op_id %d: added hint from interval %d to %d", move->id(), from->reg_num(), to->reg_num()));
        }
      }
      break;
    }
    case lir_cmove: {
      assert(op->as_Op4() != NULL, "lir_cmove must be LIR_Op4");
      LIR_Op4* cmove = (LIR_Op4*)op;

      LIR_Opr move_from = cmove->in_opr1();
      LIR_Opr move_to   = cmove->result_opr();

      if (move_to->is_register() && move_from->is_register()) {
        Interval* from = interval_at(reg_num(move_from));
        Interval* to = interval_at(reg_num(move_to));
        if (from != NULL && to != NULL) {
          to->set_register_hint(from);
          TRACE_LINEAR_SCAN(4, tty->print_cr("operation at op_id %d: added hint from interval %d to %d", cmove->id(), from->reg_num(), to->reg_num()));
        }
      }
      break;
    }
    default:
      break;
  }
}

void LinearScan::build_intervals() {
  TIME_LINEAR_SCAN(timer_build_intervals);

  // initialize interval list with expected number of intervals
  // (32 is added to have some space for split children without having to resize the list)
  _intervals = IntervalList(num_virtual_regs() + 32);
  // initialize all slots that are used by build_intervals
  _intervals.at_put_grow(num_virtual_regs() - 1, NULL, NULL);

  // create a list with all caller-save registers (cpu, fpu, xmm)
  // when an instruction is a call, a temp range is created for all these registers
  int num_caller_save_registers = 0;
  int caller_save_registers[LinearScan::nof_regs];

  int i;
  for (i = 0; i < FrameMap::nof_caller_save_cpu_regs(); i++) {
    LIR_Opr opr = FrameMap::caller_save_cpu_reg_at(i);
    assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
    assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
    caller_save_registers[num_caller_save_registers++] = reg_num(opr);
  }

  // temp ranges for fpu registers are only created when the method has
  // virtual fpu operands. Otherwise no allocation for fpu registers is
  // performed and so the temp ranges would be useless
  if (has_fpu_registers()) {
#ifdef X86
    if (UseSSE < 2) {
#endif // X86
      for (i = 0; i < FrameMap::nof_caller_save_fpu_regs; i++) {
        LIR_Opr opr = FrameMap::caller_save_fpu_reg_at(i);
        assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
        assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
        caller_save_registers[num_caller_save_registers++] = reg_num(opr);
      }
#ifdef X86
    }
#endif // X86

#ifdef X86
    if (UseSSE > 0) {
      int num_caller_save_xmm_regs = FrameMap::get_num_caller_save_xmms();
      for (i = 0; i < num_caller_save_xmm_regs; i ++) {
        LIR_Opr opr = FrameMap::caller_save_xmm_reg_at(i);
        assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
        assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
        caller_save_registers[num_caller_save_registers++] = reg_num(opr);
      }
    }
#endif // X86
  }
  assert(num_caller_save_registers <= LinearScan::nof_regs, "out of bounds");

  LIR_OpVisitState visitor;

  // iterate all blocks in reverse order
  for (i = block_count() - 1; i >= 0; i--) {
    BlockBegin* block = block_at(i);
    LIR_OpList* instructions = block->lir()->instructions_list();
    int         block_from =   block->first_lir_instruction_id();
    int         block_to =     block->last_lir_instruction_id();

    assert(block_from == instructions->at(0)->id(), "must be");
    assert(block_to   == instructions->at(instructions->length() - 1)->id(), "must be");

    // Update intervals for registers live at the end of this block;
    ResourceBitMap live = block->live_out();
    int size = (int)live.size();
    for (int number = (int)live.get_next_one_offset(0, size); number < size; number = (int)live.get_next_one_offset(number + 1, size)) {
      assert(live.at(number), "should not stop here otherwise");
      assert(number >= LIR_Opr::vreg_base, "fixed intervals must not be live on block bounds");
      TRACE_LINEAR_SCAN(2, tty->print_cr("live in %d to %d", number, block_to + 2));

      add_use(number, block_from, block_to + 2, noUse, T_ILLEGAL);

      // add special use positions for loop-end blocks when the
      // interval is used anywhere inside this loop.  It's possible
      // that the block was part of a non-natural loop, so it might
      // have an invalid loop index.
      if (block->is_set(BlockBegin::linear_scan_loop_end_flag) &&
          block->loop_index() != -1 &&
          is_interval_in_loop(number, block->loop_index())) {
        interval_at(number)->add_use_pos(block_to + 1, loopEndMarker);
      }
    }

    // iterate all instructions of the block in reverse order.
    // skip the first instruction because it is always a label
    // definitions of intervals are processed before uses
    assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
    for (int j = instructions->length() - 1; j >= 1; j--) {
      LIR_Op* op = instructions->at(j);
      int op_id = op->id();

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

      // add a temp range for each register if operation destroys caller-save registers
      if (visitor.has_call()) {
        for (int k = 0; k < num_caller_save_registers; k++) {
          add_temp(caller_save_registers[k], op_id, noUse, T_ILLEGAL);
        }
        TRACE_LINEAR_SCAN(4, tty->print_cr("operation destroys all caller-save registers"));
      }

      // Add any platform dependent temps
      pd_add_temps(op);

      // visit definitions (output and temp operands)
      int k, n;
      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");
        add_def(opr, op_id, use_kind_of_output_operand(op, opr));
      }

      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");
        add_temp(opr, op_id, mustHaveRegister);
      }

      // visit uses (input operands)
      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");
        add_use(opr, block_from, op_id, use_kind_of_input_operand(op, opr));
      }

      // Add uses of live locals from interpreter's point of view for proper
      // debug information generation
      // Treat these operands as temp values (if the life range is extended
      // to a call site, the value would be in a register at the call otherwise)
      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,
          add_use(value, block_from, op_id + 1, noUse);
        );
      }

      // special steps for some instructions (especially moves)
      handle_method_arguments(op);
      handle_doubleword_moves(op);
      add_register_hints(op);

    } // end of instruction iteration
  } // end of block iteration

  // add the range [0, 1[ to all fixed intervals
  // -> the register allocator need not handle unhandled fixed intervals
  for (int n = 0; n < LinearScan::nof_regs; n++) {
    Interval* interval = interval_at(n);
    if (interval != NULL) {
      interval->add_range(0, 1);
    }
  }
}

// ********** Phase 5: actual register allocation

int LinearScan::interval_cmp(Interval** a, Interval** b) {
  if (*a != NULL) {
    if (*b != NULL) {
      return (*a)->from() - (*b)->from();
    } else {
      return -1;
    }
  } else {
    if (*b != NULL) {
      return 1;
    } else {
      return 0;
    }
  }
}

#ifndef PRODUCT
int interval_cmp(Interval* const& l, Interval* const& r) {
  return l->from() - r->from();
}

bool find_interval(Interval* interval, IntervalArray* intervals) {
  bool found;
  int idx = intervals->find_sorted<Interval*, interval_cmp>(interval, found);

  if (!found) {
    return false;
  }

  int from = interval->from();

  // The index we've found using binary search is pointing to an interval
  // that is defined in the same place as the interval we were looking for.
  // So now we have to look around that index and find exact interval.
  for (int i = idx; i >= 0; i--) {
    if (intervals->at(i) == interval) {
      return true;
    }
    if (intervals->at(i)->from() != from) {
      break;
    }
  }

  for (int i = idx + 1; i < intervals->length(); i++) {
    if (intervals->at(i) == interval) {
      return true;
    }
    if (intervals->at(i)->from() != from) {
      break;
    }
  }

  return false;
}

bool LinearScan::is_sorted(IntervalArray* intervals) {
  int from = -1;
  int null_count = 0;

  for (int i = 0; i < intervals->length(); i++) {
    Interval* it = intervals->at(i);
    if (it != NULL) {
      assert(from <= it->from(), "Intervals are unordered");
      from = it->from();
    } else {
      null_count++;
    }
  }

  assert(null_count == 0, "Sorted intervals should not contain nulls");

  null_count = 0;

  for (int i = 0; i < interval_count(); i++) {
    Interval* interval = interval_at(i);
    if (interval != NULL) {
      assert(find_interval(interval, intervals), "Lists do not contain same intervals");
    } else {
      null_count++;
    }
  }

  assert(interval_count() - null_count == intervals->length(),
      "Sorted list should contain the same amount of non-NULL intervals as unsorted list");

  return true;
}
#endif

void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
  if (*prev != NULL) {
    (*prev)->set_next(interval);
  } else {
    *first = interval;
  }
  *prev = interval;
}

void LinearScan::create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)) {
  assert(is_sorted(_sorted_intervals), "interval list is not sorted");

  *list1 = *list2 = Interval::end();

  Interval* list1_prev = NULL;
  Interval* list2_prev = NULL;
  Interval* v;

  const int n = _sorted_intervals->length();
  for (int i = 0; i < n; i++) {
    v = _sorted_intervals->at(i);
    if (v == NULL) continue;

    if (is_list1(v)) {
      add_to_list(list1, &list1_prev, v);
    } else if (is_list2 == NULL || is_list2(v)) {
      add_to_list(list2, &list2_prev, v);
    }
  }

  if (list1_prev != NULL) list1_prev->set_next(Interval::end());
  if (list2_prev != NULL) list2_prev->set_next(Interval::end());

  assert(list1_prev == NULL || list1_prev->next() == Interval::end(), "linear list ends not with sentinel");
  assert(list2_prev == NULL || list2_prev->next() == Interval::end(), "linear list ends not with sentinel");
}

void LinearScan::sort_intervals_before_allocation() {
  TIME_LINEAR_SCAN(timer_sort_intervals_before);

  if (_needs_full_resort) {
    // There is no known reason why this should occur but just in case...
    assert(false, "should never occur");
    // Re-sort existing interval list because an Interval::from() has changed
    _sorted_intervals->sort(interval_cmp);
    _needs_full_resort = false;
  }

  IntervalList* unsorted_list = &_intervals;
  int unsorted_len = unsorted_list->length();
  int sorted_len = 0;
  int unsorted_idx;
  int sorted_idx = 0;
  int sorted_from_max = -1;

  // calc number of items for sorted list (sorted list must not contain NULL values)
  for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
    if (unsorted_list->at(unsorted_idx) != NULL) {
      sorted_len++;
    }
  }
  IntervalArray* sorted_list = new IntervalArray(sorted_len, sorted_len, NULL);

  // special sorting algorithm: the original interval-list is almost sorted,
  // only some intervals are swapped. So this is much faster than a complete QuickSort
  for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
    Interval* cur_interval = unsorted_list->at(unsorted_idx);

    if (cur_interval != NULL) {
      int cur_from = cur_interval->from();

      if (sorted_from_max <= cur_from) {
        sorted_list->at_put(sorted_idx++, cur_interval);
        sorted_from_max = cur_interval->from();
      } else {
        // the assumption that the intervals are already sorted failed,
        // so this interval must be sorted in manually
        int j;
        for (j = sorted_idx - 1; j >= 0 && cur_from < sorted_list->at(j)->from(); j--) {
          sorted_list->at_put(j + 1, sorted_list->at(j));
        }
        sorted_list->at_put(j + 1, cur_interval);
        sorted_idx++;
      }
    }
  }
  _sorted_intervals = sorted_list;
  assert(is_sorted(_sorted_intervals), "intervals unsorted");
}

void LinearScan::sort_intervals_after_allocation() {
  TIME_LINEAR_SCAN(timer_sort_intervals_after);

  if (_needs_full_resort) {
    // Re-sort existing interval list because an Interval::from() has changed
    _sorted_intervals->sort(interval_cmp);
    _needs_full_resort = false;
  }

  IntervalArray* old_list = _sorted_intervals;
  IntervalList* new_list = _new_intervals_from_allocation;
  int old_len = old_list->length();
  int new_len = new_list == NULL ? 0 : new_list->length();

  if (new_len == 0) {
    // no intervals have been added during allocation, so sorted list is already up to date
    assert(is_sorted(_sorted_intervals), "intervals unsorted");
    return;
  }

  // conventional sort-algorithm for new intervals
  new_list->sort(interval_cmp);

  // merge old and new list (both already sorted) into one combined list
  int combined_list_len = old_len + new_len;
  IntervalArray* combined_list = new IntervalArray(combined_list_len, combined_list_len, NULL);
  int old_idx = 0;
  int new_idx = 0;

  while (old_idx + new_idx < old_len + new_len) {
    if (new_idx >= new_len || (old_idx < old_len && old_list->at(old_idx)->from() <= new_list->at(new_idx)->from())) {
      combined_list->at_put(old_idx + new_idx, old_list->at(old_idx));
      old_idx++;
    } else {
      combined_list->at_put(old_idx + new_idx, new_list->at(new_idx));
      new_idx++;
    }
  }

  _sorted_intervals = combined_list;
  assert(is_sorted(_sorted_intervals), "intervals unsorted");
}

void LinearScan::allocate_registers() {
  TIME_LINEAR_SCAN(timer_allocate_registers);

  Interval* precolored_cpu_intervals, *not_precolored_cpu_intervals;
  Interval* precolored_fpu_intervals, *not_precolored_fpu_intervals;

  // collect cpu intervals
  create_unhandled_lists(&precolored_cpu_intervals, ¬_precolored_cpu_intervals,
                         is_precolored_cpu_interval, is_virtual_cpu_interval);

  // collect fpu intervals
  create_unhandled_lists(&precolored_fpu_intervals, ¬_precolored_fpu_intervals,
                         is_precolored_fpu_interval, is_virtual_fpu_interval);
  // this fpu interval collection cannot be moved down below with the allocation section as
  // the cpu_lsw.walk() changes interval positions.

  if (!has_fpu_registers()) {
#ifdef ASSERT
    assert(not_precolored_fpu_intervals == Interval::end(), "missed an uncolored fpu interval");
#else
    if (not_precolored_fpu_intervals != Interval::end()) {
      BAILOUT("missed an uncolored fpu interval");
    }
#endif
  }

  // allocate cpu registers
  LinearScanWalker cpu_lsw(this, precolored_cpu_intervals, not_precolored_cpu_intervals);
  cpu_lsw.walk();
  cpu_lsw.finish_allocation();

  if (has_fpu_registers()) {
    // allocate fpu registers
    LinearScanWalker fpu_lsw(this, precolored_fpu_intervals, not_precolored_fpu_intervals);
    fpu_lsw.walk();
    fpu_lsw.finish_allocation();
  }
}

// ********** Phase 6: resolve data flow
// (insert moves at edges between blocks if intervals have been split)

// wrapper for Interval::split_child_at_op_id that performs a bailout in product mode
// instead of returning NULL
Interval* LinearScan::split_child_at_op_id(Interval* interval, int op_id, LIR_OpVisitState::OprMode mode) {
  Interval* result = interval->split_child_at_op_id(op_id, mode);
  if (result != NULL) {
    return result;
  }

  assert(false, "must find an interval, but do a clean bailout in product mode");
  result = new Interval(LIR_Opr::vreg_base);
  result->assign_reg(0);
  result->set_type(T_INT);
  BAILOUT_("LinearScan: interval is NULL", result);
}

Interval* LinearScan::interval_at_block_begin(BlockBegin* block, int reg_num) {
  assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
  assert(interval_at(reg_num) != NULL, "no interval found");

  return split_child_at_op_id(interval_at(reg_num), block->first_lir_instruction_id(), LIR_OpVisitState::outputMode);
}

Interval* LinearScan::interval_at_block_end(BlockBegin* block, int reg_num) {
  assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
  assert(interval_at(reg_num) != NULL, "no interval found");

  return split_child_at_op_id(interval_at(reg_num), block->last_lir_instruction_id() + 1, LIR_OpVisitState::outputMode);
}

Interval* LinearScan::interval_at_op_id(int reg_num, int op_id) {
  assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
  assert(interval_at(reg_num) != NULL, "no interval found");

  return split_child_at_op_id(interval_at(reg_num), op_id, LIR_OpVisitState::inputMode);
}

void LinearScan::resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
  DEBUG_ONLY(move_resolver.check_empty());

  const int size = live_set_size();
  const ResourceBitMap live_at_edge = to_block->live_in();

  // visit all registers where the live_at_edge bit is set
  for (int r = (int)live_at_edge.get_next_one_offset(0, size); r < size; r = (int)live_at_edge.get_next_one_offset(r + 1, size)) {
    assert(r < num_virtual_regs(), "live information set for not existing interval");
    assert(from_block->live_out().at(r) && to_block->live_in().at(r), "interval not live at this edge");

    Interval* from_interval = interval_at_block_end(from_block, r);
    Interval* to_interval = interval_at_block_begin(to_block, r);

    if (from_interval != to_interval && (from_interval->assigned_reg() != to_interval->assigned_reg() || from_interval->assigned_regHi() != to_interval->assigned_regHi())) {
      // need to insert move instruction
      move_resolver.add_mapping(from_interval, to_interval);
    }
  }
}

void LinearScan::resolve_find_insert_pos(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
--> --------------------

--> maximum size reached

--> --------------------

quality90%

¤ Dauer der Verarbeitung: 0.29 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.