/*

 * Copyright 2005-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_c1_LinearScan.cpp.incl"

#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);

  // helper macro for short definition of trace-output inside code

  #define TRACE_LINEAR_SCAN(level, code)       \

    if (TraceLinearScanLevel >= level) {       \

      code;                                    \

    }

#else

  #define TIME_LINEAR_SCAN(timer_name)

  #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, 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};

#endif

// Implementation of LinearScan

LinearScan::LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map)

 : _compilation(ir->compilation())

 , _ir(ir)

 , _gen(gen)

 , _frame_map(frame_map)

 , _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(new IntervalList())

 , _sorted_intervals(NULL)

 , _lir_ops(0)     // initialized later with correct length

 , _block_of_op(0) // initialized later with correct length

 , _has_info(0)

 , _has_call(0)

 , _scope_value_cache(0) // initialized later with correct length

 , _interval_in_loop(0, 0) // initialized later with correct length

 , _cached_blocks(*ir->linear_scan_order())

#ifdef X86

 , _fpu_stack_allocator(NULL)

#endif

{

  // note: to use more than on instance of LinearScan at a time this function call has to

  //       be moved somewhere outside of this constructor:

  Interval::initialize();

  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_OprDesc::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) {

  return i->reg_num() >= LIR_OprDesc::vreg_base && (i->type() != T_FLOAT && i->type() != T_DOUBLE);

}

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) {

  return i->reg_num() >= LIR_OprDesc::vreg_base && (i->type() == T_FLOAT || i->type() == T_DOUBLE);

}

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();

  // the class OopMapValue uses only 11 bits for storing the name of the

  // oop location. So a stack slot bigger than 2^11 leads to an overflow

  // that is not reported in product builds. Prevent this by checking the

  // spill slot here (altough this value and the later used location name

  // are slightly different)

  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 exisiting interval");

  Interval* interval = new Interval(reg_num);

  _intervals.at_put(reg_num, interval);

  // assign register number for precolored intervals

  if (reg_num < LIR_OprDesc::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);

  _new_intervals_from_allocation->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 asignment 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);

  _block_of_op = BlockBeginArray(num_instructions);

  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 = BitMap(num_instructions); _has_call.clear();

  _has_info = BitMap(num_instructions); _has_info.clear();

}

// ********** 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(), "asumption: Constant instructions have only constant operands");