Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 2005, 2012, 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 "utilities/bitMap.inline.hpp"

 #ifdef TARGET_ARCH_x86

 # include "vmreg_x86.inline.hpp"

 #endif

 #ifdef TARGET_ARCH_sparc

 # include "vmreg_sparc.inline.hpp"

 #endif

 #ifdef TARGET_ARCH_zero

 # include "vmreg_zero.inline.hpp"

 #endif

 #ifdef TARGET_ARCH_arm

 # include "vmreg_arm.inline.hpp"

 #endif

 #ifdef TARGET_ARCH_ppc

 # include "vmreg_ppc.inline.hpp"

 #endif

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

  , _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)

  , _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)

  , _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

 {

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

 #if defined(__SOFTFP__) || defined(E500V2)

   return i->reg_num() >= LIR_OprDesc::vreg_base;

 #else

   return i->reg_num() >= LIR_OprDesc::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_OprDesc::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();

   // 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");

   assert(con != NULL || opr->is_virtual(), "asumption: 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());

   local_interval_in_loop.clear();

   // iterate all blocks

   for (int i = 0; i < num_blocks; i++) {

     BlockBegin* block = block_at(i);

     BitMap live_gen(live_size);  live_gen.clear();

     BitMap live_kill(live_size); live_kill.clear();

     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,

         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)

         );

       }

       // 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  (BitMap(live_size)); block->live_in().clear();

     block->set_live_out (BitMap(live_size)); block->live_out().clear();

     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;

   BitMap live_out(live_set_size()); live_out.clear(); // 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.

           BitMap 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!

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

       }

 #ifndef PRODUCT

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

   BitMap live_in_args(ir()->start()->live_in().size());

   live_in_args.clear();

   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;

     }

   }

 #ifdef X86

   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 ((UseSSE == 1 && opr_type == T_FLOAT) || UseSSE >= 2) {

       // 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;

           }

         }

       }

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

           }

         }

       }

     }

   } else if (opr_type != T_LONG) {

     // 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;

         }

       }

     }

   }

 #endif // X86

   // 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_Op2() != NULL, "lir_cmove must be LIR_Op2");

       LIR_Op2* cmove = (LIR_Op2*)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;

     }

   }

 }

 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

   // perfomed and so the temp ranges would be useless

   if (has_fpu_registers()) {

 #ifdef X86

     if (UseSSE < 2) {

 #endif

       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

     }

     if (UseSSE > 0) {

       for (i = 0; i < FrameMap::nof_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

   }

   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;

     BitMap 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_OprDesc::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

 bool LinearScan::is_sorted(IntervalArray* intervals) {

   int from = -1;

   int i, j;

   for (i = 0; i < intervals->length(); i ++) {

     Interval* it = intervals->at(i);

     if (it != NULL) {

       if (from > it->from()) {

         assert(false, "");

         return false;

       }

       from = it->from();

     }

   }

   // check in both directions if sorted list and unsorted list contain same intervals

   for (i = 0; i < interval_count(); i++) {

     if (interval_at(i) != NULL) {

       int num_found = 0;

       for (j = 0; j < intervals->length(); j++) {

         if (interval_at(i) == intervals->at(j)) {

           num_found++;

         }

       }

       assert(num_found == 1, "lists do not contain same intervals");

     }

   }

   for (j = 0; j < intervals->length(); j++) {

     int num_found = 0;

     for (i = 0; i < interval_count(); i++) {

       if (interval_at(i) == intervals->at(j)) {

         num_found++;

       }

     }

     assert(num_found == 1, "lists do not contain same intervals");

   }

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

   // 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 asumption 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->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

   IntervalArray* combined_list = new IntervalArray(old_len + new_len);

   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;

   create_unhandled_lists(&precolored_cpu_intervals, &not_precolored_cpu_intervals, is_precolored_cpu_interval, is_virtual_cpu_interval);

   if (has_fpu_registers()) {

     create_unhandled_lists(&precolored_fpu_intervals, &not_precolored_fpu_intervals, is_precolored_fpu_interval, is_virtual_fpu_interval);

 #ifdef ASSERT

   } else {

     // fpu register allocation is omitted because no virtual fpu registers are present

     // just check this again...

     create_unhandled_lists(&precolored_fpu_intervals, &not_precolored_fpu_intervals, is_precolored_fpu_interval, is_virtual_fpu_interval);

     assert(not_precolored_fpu_intervals == Interval::end(), "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_OprDesc::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 num_regs = num_virtual_regs();

   const int size = live_set_size();

   const BitMap 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_regs, "live information set for not exisiting 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) {

   if (from_block->number_of_sux() <= 1) {

     TRACE_LINEAR_SCAN(4, tty->print_cr("inserting moves at end of from_block B%d", from_block->block_id()));

     LIR_OpList* instructions = from_block->lir()->instructions_list();

     LIR_OpBranch* branch = instructions->last()->as_OpBranch();

     if (branch != NULL) {

       // insert moves before branch

       assert(branch->cond() == lir_cond_always, "block does not end with an unconditional jump");

       move_resolver.set_insert_position(from_block->lir(), instructions->length() - 2);

     } else {

       move_resolver.set_insert_position(from_block->lir(), instructions->length() - 1);

     }

   } else {

     TRACE_LINEAR_SCAN(4, tty->print_cr("inserting moves at beginning of to_block B%d", to_block->block_id()));

 #ifdef ASSERT

     assert(from_block->lir()->instructions_list()->at(0)->as_OpLabel() != NULL, "block does not start with a label");

     // because the number of predecessor edges matches the number of

     // successor edges, blocks which are reached by switch statements

     // may have be more than one predecessor but it will be guaranteed

     // that all predecessors will be the same.

     for (int i = 0; i < to_block->number_of_preds(); i++) {

       assert(from_block == to_block->pred_at(i), "all critical edges must be broken");

     }

 #endif

     move_resolver.set_insert_position(to_block->lir(), 0);

   }

 }

 // insert necessary moves (spilling or reloading) at edges between blocks if interval has been split

 void LinearScan::resolve_data_flow() {

   TIME_LINEAR_SCAN(timer_resolve_data_flow);

   int num_blocks = block_count();

   MoveResolver move_resolver(this);

   BitMap block_completed(num_blocks);  block_completed.clear();

   BitMap already_resolved(num_blocks); already_resolved.clear();

   int i;

   for (i = 0; i < num_blocks; i++) {

     BlockBegin* block = block_at(i);

     // check if block has only one predecessor and only one successor

     if (block->number_of_preds() == 1 && block->number_of_sux() == 1 && block->number_of_exception_handlers() == 0) {

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

       assert(instructions->at(0)->code() == lir_label, "block must start with label");

       assert(instructions->last()->code() == lir_branch, "block with successors must end with branch");

       assert(instructions->last()->as_OpBranch()->cond() == lir_cond_always, "block with successor must end with unconditional branch");

       // check if block is empty (only label and branch)

       if (instructions->length() == 2) {

         BlockBegin* pred = block->pred_at(0);

         BlockBegin* sux = block->sux_at(0);

         // prevent optimization of two consecutive blocks

         if (!block_completed.at(pred->linear_scan_number()) && !block_completed.at(sux->linear_scan_number())) {

           TRACE_LINEAR_SCAN(3, tty->print_cr("**** optimizing empty block B%d (pred: B%d, sux: B%d)", block->block_id(), pred->block_id(), sux->block_id()));

           block_completed.set_bit(block->linear_scan_number());

           // directly resolve between pred and sux (without looking at the empty block between)

           resolve_collect_mappings(pred, sux, move_resolver);

           if (move_resolver.has_mappings()) {

             move_resolver.set_insert_position(block->lir(), 0);

             move_resolver.resolve_and_append_moves();

           }

         }

       }

     }

   }

   for (i = 0; i < num_blocks; i++) {

     if (!block_completed.at(i)) {

       BlockBegin* from_block = block_at(i);

       already_resolved.set_from(block_completed);

       int num_sux = from_block->number_of_sux();

       for (int s = 0; s < num_sux; s++) {

         BlockBegin* to_block = from_block->sux_at(s);

         // check for duplicate edges between the same blocks (can happen with switch blocks)

         if (!already_resolved.at(to_block->linear_scan_number())) {

           TRACE_LINEAR_SCAN(3, tty->print_cr("**** processing edge between B%d and B%d", from_block->block_id(), to_block->block_id()));

           already_resolved.set_bit(to_block->linear_scan_number());

           // collect all intervals that have been split between from_block and to_block

           resolve_collect_mappings(from_block, to_block, move_resolver);

           if (move_resolver.has_mappings()) {

             resolve_find_insert_pos(from_block, to_block, move_resolver);

             move_resolver.resolve_and_append_moves();

           }

         }

       }

     }

   }

 }

 void LinearScan::resolve_exception_entry(BlockBegin* block, int reg_num, MoveResolver &move_resolver) {

   if (interval_at(reg_num) == NULL) {

     // if a phi function is never used, no interval is created -> ignore this

     return;

   }

   Interval* interval = interval_at_block_begin(block, reg_num);

   int reg = interval->assigned_reg();

   int regHi = interval->assigned_regHi();

   if ((reg < nof_regs && interval->always_in_memory()) ||

       (use_fpu_stack_allocation() && reg >= pd_first_fpu_reg && reg <= pd_last_fpu_reg)) {

     // the interval is split to get a short range that is located on the stack

     // in the following two cases:

     // * the interval started in memory (e.g. method parameter), but is currently in a register

     //   this is an optimization for exception handling that reduces the number of moves that

     //   are necessary for resolving the states when an exception uses this exception handler

     // * the interval would be on the fpu stack at the begin of the exception handler

     //   this is not allowed because of the complicated fpu stack handling on Intel

     // range that will be spilled to memory

     int from_op_id = block->first_lir_instruction_id();

     int to_op_id = from_op_id + 1;  // short live range of length 1

     assert(interval->from() <= from_op_id && interval->to() >= to_op_id,

            "no split allowed between exception entry and first instruction");

     if (interval->from() != from_op_id) {

       // the part before from_op_id is unchanged

       interval = interval->split(from_op_id);

       interval->assign_reg(reg, regHi);

       append_interval(interval);

     } else {

       _needs_full_resort = true;

     }

     assert(interval->from() == from_op_id, "must be true now");

     Interval* spilled_part = interval;

     if (interval->to() != to_op_id) {

       // the part after to_op_id is unchanged

       spilled_part = interval->split_from_start(to_op_id);

       append_interval(spilled_part);

       move_resolver.add_mapping(spilled_part, interval);

     }

     assign_spill_slot(spilled_part);

     assert(spilled_part->from() == from_op_id && spilled_part->to() == to_op_id, "just checking");

   }

 }

 void LinearScan::resolve_exception_entry(BlockBegin* block, MoveResolver &move_resolver) {

   assert(block->is_set(BlockBegin::exception_entry_flag), "should not call otherwise");

   DEBUG_ONLY(move_resolver.check_empty());

   // visit all registers where the live_in bit is set

   int size = live_set_size();

   for (int r = (int)block->live_in().get_next_one_offset(0, size); r < size; r = (int)block->live_in().get_next_one_offset(r + 1, size)) {

     resolve_exception_entry(block, r, move_resolver);

   }

   // the live_in bits are not set for phi functions of the xhandler entry, so iterate them separately

   for_each_phi_fun(block, phi,

     resolve_exception_entry(block, phi->operand()->vreg_number(), move_resolver)

   );

   if (move_resolver.has_mappings()) {

     // insert moves after first instruction

     move_resolver.set_insert_position(block->lir(), 0);

     move_resolver.resolve_and_append_moves();

   }

 }

 void LinearScan::resolve_exception_edge(XHandler* handler, int throwing_op_id, int reg_num, Phi* phi, MoveResolver &move_resolver) {

   if (interval_at(reg_num) == NULL) {

     // if a phi function is never used, no interval is created -> ignore this

     return;

   }

   // the computation of to_interval is equal to resolve_collect_mappings,

   // but from_interval is more complicated because of phi functions

   BlockBegin* to_block = handler->entry_block();

   Interval* to_interval = interval_at_block_begin(to_block, reg_num);

   if (phi != NULL) {

     // phi function of the exception entry block

     // no moves are created for this phi function in the LIR_Generator, so the

     // interval at the throwing instruction must be searched using the operands

     // of the phi function

     Value from_value = phi->operand_at(handler->phi_operand());

     // with phi functions it can happen that the same from_value is used in

     // multiple mappings, so notify move-resolver that this is allowed

     move_resolver.set_multiple_reads_allowed();

     Constant* con = from_value->as_Constant();

     if (con != NULL && !con->is_pinned()) {

       // unpinned constants may have no register, so add mapping from constant to interval

       move_resolver.add_mapping(LIR_OprFact::value_type(con->type()), to_interval);

     } else {

       // search split child at the throwing op_id

       Interval* from_interval = interval_at_op_id(from_value->operand()->vreg_number(), throwing_op_id);

       move_resolver.add_mapping(from_interval, to_interval);

     }

   } else {

     // no phi function, so use reg_num also for from_interval

     // search split child at the throwing op_id

     Interval* from_interval = interval_at_op_id(reg_num, throwing_op_id);

     if (from_interval != to_interval) {

       // optimization to reduce number of moves: when to_interval is on stack and

       // the stack slot is known to be always correct, then no move is necessary

       if (!from_interval->always_in_memory() || from_interval->canonical_spill_slot() != to_interval->assigned_reg()) {

         move_resolver.add_mapping(from_interval, to_interval);

       }

     }

   }

 }

 void LinearScan::resolve_exception_edge(XHandler* handler, int throwing_op_id, MoveResolver &move_resolver) {

   TRACE_LINEAR_SCAN(4, tty->print_cr("resolving exception handler B%d: throwing_op_id=%d", handler->entry_block()->block_id(), throwing_op_id));

   DEBUG_ONLY(move_resolver.check_empty());

   assert(handler->lir_op_id() == -1, "already processed this xhandler");

   DEBUG_ONLY(handler->set_lir_op_id(throwing_op_id));

   assert(handler->entry_code() == NULL, "code already present");

   // visit all registers where the live_in bit is set

   BlockBegin* block = handler->entry_block();

   int size = live_set_size();

   for (int r = (int)block->live_in().get_next_one_offset(0, size); r < size; r = (int)block->live_in().get_next_one_offset(r + 1, size)) {

     resolve_exception_edge(handler, throwing_op_id, r, NULL, move_resolver);

   }

   // the live_in bits are not set for phi functions of the xhandler entry, so iterate them separately

   for_each_phi_fun(block, phi,

     resolve_exception_edge(handler, throwing_op_id, phi->operand()->vreg_number(), phi, move_resolver)

   );

   if (move_resolver.has_mappings()) {

     LIR_List* entry_code = new LIR_List(compilation());

     move_resolver.set_insert_position(entry_code, 0);

     move_resolver.resolve_and_append_moves();

     entry_code->jump(handler->entry_block());

     handler->set_entry_code(entry_code);

   }

 }

 void LinearScan::resolve_exception_handlers() {

   MoveResolver move_resolver(this);

   LIR_OpVisitState visitor;

   int num_blocks = block_count();

   int i;

   for (i = 0; i < num_blocks; i++) {

     BlockBegin* block = block_at(i);

     if (block->is_set(BlockBegin::exception_entry_flag)) {

       resolve_exception_entry(block, move_resolver);

     }

   }

   for (i = 0; i < num_blocks; i++) {

     BlockBegin* block = block_at(i);

     LIR_List* ops = block->lir();

     int num_ops = ops->length();

     // iterate all instructions of the block. skip the first because it is always a label

     assert(visitor.no_operands(ops->at(0)), "first operation must always be a label");

     for (int j = 1; j < num_ops; j++) {

       LIR_Op* op = ops->at(j);

       int op_id = op->id();

       if (op_id != -1 && has_info(op_id)) {

         // visit operation to collect all operands

         visitor.visit(op);

         assert(visitor.info_count() > 0, "should not visit otherwise");

         XHandlers* xhandlers = visitor.all_xhandler();

         int n = xhandlers->length();

         for (int k = 0; k < n; k++) {

           resolve_exception_edge(xhandlers->handler_at(k), op_id, move_resolver);

         }

 #ifdef ASSERT

       } else {

         visitor.visit(op);

         assert(visitor.all_xhandler()->length() == 0, "missed exception handler");

 #endif

       }

     }

   }

 }

 // ********** Phase 7: assign register numbers back to LIR

 // (includes computation of debug information and oop maps)

 VMReg LinearScan::vm_reg_for_interval(Interval* interval) {

   VMReg reg = interval->cached_vm_reg();

   if (!reg->is_valid() ) {

     reg = vm_reg_for_operand(operand_for_interval(interval));

     interval->set_cached_vm_reg(reg);

   }

   assert(reg == vm_reg_for_operand(operand_for_interval(interval)), "wrong cached value");

   return reg;

 }

 VMReg LinearScan::vm_reg_for_operand(LIR_Opr opr) {

   assert(opr->is_oop(), "currently only implemented for oop operands");

   return frame_map()->regname(opr);

 }

 LIR_Opr LinearScan::operand_for_interval(Interval* interval) {

   LIR_Opr opr = interval->cached_opr();

   if (opr->is_illegal()) {

     opr = calc_operand_for_interval(interval);

     interval->set_cached_opr(opr);

   }

   assert(opr == calc_operand_for_interval(interval), "wrong cached value");

   return opr;

 }

 LIR_Opr LinearScan::calc_operand_for_interval(const Interval* interval) {

   int assigned_reg = interval->assigned_reg();

   BasicType type = interval->type();

   if (assigned_reg >= nof_regs) {

     // stack slot

     assert(interval->assigned_regHi() == any_reg, "must not have hi register");

     return LIR_OprFact::stack(assigned_reg - nof_regs, type);

   } else {

     // register

     switch (type) {

       case T_OBJECT: {

         assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register");

         return LIR_OprFact::single_cpu_oop(assigned_reg);

       }

       case T_ADDRESS: {

         assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register");

         return LIR_OprFact::single_cpu_address(assigned_reg);

       }

       case T_METADATA: {

         assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register");

         return LIR_OprFact::single_cpu_metadata(assigned_reg);

       }

 #ifdef __SOFTFP__

       case T_FLOAT:  // fall through

 #endif // __SOFTFP__

       case T_INT: {

         assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register");

         return LIR_OprFact::single_cpu(assigned_reg);

       }

 #ifdef __SOFTFP__

       case T_DOUBLE:  // fall through

 #endif // __SOFTFP__

       case T_LONG: {

         int assigned_regHi = interval->assigned_regHi();

         assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");

         assert(num_physical_regs(T_LONG) == 1 ||

                (assigned_regHi >= pd_first_cpu_reg && assigned_regHi <= pd_last_cpu_reg), "no cpu register");

         assert(assigned_reg != assigned_regHi, "invalid allocation");

         assert(num_physical_regs(T_LONG) == 1 || assigned_reg < assigned_regHi,

                "register numbers must be sorted (ensure that e.g. a move from eax,ebx to ebx,eax can not occur)");

         assert((assigned_regHi != any_reg) ^ (num_physical_regs(T_LONG) == 1), "must be match");

         if (requires_adjacent_regs(T_LONG)) {

           assert(assigned_reg % 2 == 0 && assigned_reg + 1 == assigned_regHi, "must be sequential and even");

         }

 #ifdef _LP64

         return LIR_OprFact::double_cpu(assigned_reg, assigned_reg);

 #else

 #if defined(SPARC) || defined(PPC)

         return LIR_OprFact::double_cpu(assigned_regHi, assigned_reg);

 #else

         return LIR_OprFact::double_cpu(assigned_reg, assigned_regHi);

 #endif // SPARC

 #endif // LP64

       }

 #ifndef __SOFTFP__

       case T_FLOAT: {

 #ifdef X86

         if (UseSSE >= 1) {

           assert(assigned_reg >= pd_first_xmm_reg && assigned_reg <= pd_last_xmm_reg, "no xmm register");

           assert(interval->assigned_regHi() == any_reg, "must not have hi register");

           return LIR_OprFact::single_xmm(assigned_reg - pd_first_xmm_reg);

         }

 #endif

         assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register");

         return LIR_OprFact::single_fpu(assigned_reg - pd_first_fpu_reg);

       }

       case T_DOUBLE: {

 #ifdef X86

         if (UseSSE >= 2) {

           assert(assigned_reg >= pd_first_xmm_reg && assigned_reg <= pd_last_xmm_reg, "no xmm register");

           assert(interval->assigned_regHi() == any_reg, "must not have hi register (double xmm values are stored in one register)");

           return LIR_OprFact::double_xmm(assigned_reg - pd_first_xmm_reg);

         }

 #endif

 #ifdef SPARC

         assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");

         assert(interval->assigned_regHi() >= pd_first_fpu_reg && interval->assigned_regHi() <= pd_last_fpu_reg, "no fpu register");

         assert(assigned_reg % 2 == 0 && assigned_reg + 1 == interval->assigned_regHi(), "must be sequential and even");

         LIR_Opr result = LIR_OprFact::double_fpu(interval->assigned_regHi() - pd_first_fpu_reg, assigned_reg - pd_first_fpu_reg);

 #elif defined(ARM)

         assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");

         assert(interval->assigned_regHi() >= pd_first_fpu_reg && interval->assigned_regHi() <= pd_last_fpu_reg, "no fpu register");

         assert(assigned_reg % 2 == 0 && assigned_reg + 1 == interval->assigned_regHi(), "must be sequential and even");

         LIR_Opr result = LIR_OprFact::double_fpu(assigned_reg - pd_first_fpu_reg, interval->assigned_regHi() - pd_first_fpu_reg);

 #else

         assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");

         assert(interval->assigned_regHi() == any_reg, "must not have hi register (double fpu values are stored in one register on Intel)");

         LIR_Opr result = LIR_OprFact::double_fpu(assigned_reg - pd_first_fpu_reg);

 #endif

         return result;

       }

 #endif // __SOFTFP__

       default: {

         ShouldNotReachHere();

         return LIR_OprFact::illegalOpr;

       }

     }

   }

 }

 LIR_Opr LinearScan::canonical_spill_opr(Interval* interval) {

   assert(interval->canonical_spill_slot() >= nof_regs, "canonical spill slot not set");

   return LIR_OprFact::stack(interval->canonical_spill_slot() - nof_regs, interval->type());

 }

 LIR_Opr LinearScan::color_lir_opr(LIR_Opr opr, int op_id, LIR_OpVisitState::OprMode mode) {

   assert(opr->is_virtual(), "should not call this otherwise");

   Interval* interval = interval_at(opr->vreg_number());

   assert(interval != NULL, "interval must exist");

   if (op_id != -1) {

 #ifdef ASSERT

     BlockBegin* block = block_of_op_with_id(op_id);

     if (block->number_of_sux() <= 1 && op_id == block->last_lir_instruction_id()) {

       // check if spill moves could have been appended at the end of this block, but

       // before the branch instruction. So the split child information for this branch would

       // be incorrect.

       LIR_OpBranch* branch = block->lir()->instructions_list()->last()->as_OpBranch();

       if (branch != NULL) {

         if (block->live_out().at(opr->vreg_number())) {

           assert(branch->cond() == lir_cond_always, "block does not end with an unconditional jump");

           assert(false, "can't get split child for the last branch of a block because the information would be incorrect (moves are inserted before the branch in resolve_data_flow)");

         }

       }

     }

 #endif

     // operands are not changed when an interval is split during allocation,

     // so search the right interval here

     interval = split_child_at_op_id(interval, op_id, mode);

   }

   LIR_Opr res = operand_for_interval(interval);

 #ifdef X86

   // new semantic for is_last_use: not only set on definite end of interval,

   // but also before hole

   // This may still miss some cases (e.g. for dead values), but it is not necessary that the

   // last use information is completely correct

   // information is only needed for fpu stack allocation

   if (res->is_fpu_register()) {

     if (opr->is_last_use() || op_id == interval->to() || (op_id != -1 && interval->has_hole_between(op_id, op_id + 1))) {

       assert(op_id == -1 || !is_block_begin(op_id), "holes at begin of block may also result from control flow");

       res = res->make_last_use();

     }

   }

 #endif

   assert(!gen()->is_vreg_flag_set(opr->vreg_number(), LIRGenerator::callee_saved) || !FrameMap::is_caller_save_register(res), "bad allocation");

   return res;

 }

 #ifdef ASSERT

 // some methods used to check correctness of debug information

 void assert_no_register_values(GrowableArray<ScopeValue*>* values) {

   if (values == NULL) {

     return;

   }

   for (int i = 0; i < values->length(); i++) {

     ScopeValue* value = values->at(i);

     if (value->is_location()) {

       Location location = ((LocationValue*)value)->location();

       assert(location.where() == Location::on_stack, "value is in register");

     }

   }

 }

 void assert_no_register_values(GrowableArray<MonitorValue*>* values) {

   if (values == NULL) {

     return;

   }

   for (int i = 0; i < values->length(); i++) {

     MonitorValue* value = values->at(i);

     if (value->owner()->is_location()) {

       Location location = ((LocationValue*)value->owner())->location();

       assert(location.where() == Location::on_stack, "owner is in register");

     }

     assert(value->basic_lock().where() == Location::on_stack, "basic_lock is in register");

   }

 }

 void assert_equal(Location l1, Location l2) {

   assert(l1.where() == l2.where() && l1.type() == l2.type() && l1.offset() == l2.offset(), "");

 }

 void assert_equal(ScopeValue* v1, ScopeValue* v2) {

   if (v1->is_location()) {

     assert(v2->is_location(), "");

     assert_equal(((LocationValue*)v1)->location(), ((LocationValue*)v2)->location());

   } else if (v1->is_constant_int()) {

     assert(v2->is_constant_int(), "");

     assert(((ConstantIntValue*)v1)->value() == ((ConstantIntValue*)v2)->value(), "");

   } else if (v1->is_constant_double()) {

     assert(v2->is_constant_double(), "");

     assert(((ConstantDoubleValue*)v1)->value() == ((ConstantDoubleValue*)v2)->value(), "");

   } else if (v1->is_constant_long()) {

     assert(v2->is_constant_long(), "");

     assert(((ConstantLongValue*)v1)->value() == ((ConstantLongValue*)v2)->value(), "");

   } else if (v1->is_constant_oop()) {

     assert(v2->is_constant_oop(), "");

     assert(((ConstantOopWriteValue*)v1)->value() == ((ConstantOopWriteValue*)v2)->value(), "");

   } else {

     ShouldNotReachHere();

   }

 }

 void assert_equal(MonitorValue* m1, MonitorValue* m2) {

   assert_equal(m1->owner(), m2->owner());

   assert_equal(m1->basic_lock(), m2->basic_lock());

 }

 void assert_equal(IRScopeDebugInfo* d1, IRScopeDebugInfo* d2) {

   assert(d1->scope() == d2->scope(), "not equal");

   assert(d1->bci() == d2->bci(), "not equal");

   if (d1->locals() != NULL) {

     assert(d1->locals() != NULL && d2->locals() != NULL, "not equal");

     assert(d1->locals()->length() == d2->locals()->length(), "not equal");

     for (int i = 0; i < d1->locals()->length(); i++) {

       assert_equal(d1->locals()->at(i), d2->locals()->at(i));

     }

   } else {

     assert(d1->locals() == NULL && d2->locals() == NULL, "not equal");

   }

   if (d1->expressions() != NULL) {

     assert(d1->expressions() != NULL && d2->expressions() != NULL, "not equal");

     assert(d1->expressions()->length() == d2->expressions()->length(), "not equal");

     for (int i = 0; i < d1->expressions()->length(); i++) {

       assert_equal(d1->expressions()->at(i), d2->expressions()->at(i));

     }

   } else {

     assert(d1->expressions() == NULL && d2->expressions() == NULL, "not equal");

   }

   if (d1->monitors() != NULL) {

     assert(d1->monitors() != NULL && d2->monitors() != NULL, "not equal");

     assert(d1->monitors()->length() == d2->monitors()->length(), "not equal");

     for (int i = 0; i < d1->monitors()->length(); i++) {

       assert_equal(d1->monitors()->at(i), d2->monitors()->at(i));

     }

   } else {

     assert(d1->monitors() == NULL && d2->monitors() == NULL, "not equal");

   }

   if (d1->caller() != NULL) {

     assert(d1->caller() != NULL && d2->caller() != NULL, "not equal");

     assert_equal(d1->caller(), d2->caller());

   } else {

     assert(d1->caller() == NULL && d2->caller() == NULL, "not equal");

   }

 }

 void check_stack_depth(CodeEmitInfo* info, int stack_end) {

   if (info->stack()->bci() != SynchronizationEntryBCI && !info->scope()->method()->is_native()) {

     Bytecodes::Code code = info->scope()->method()->java_code_at_bci(info->stack()->bci());

     switch (code) {

       case Bytecodes::_ifnull    : // fall through

       case Bytecodes::_ifnonnull : // fall through

       case Bytecodes::_ifeq      : // fall through

       case Bytecodes::_ifne      : // fall through

       case Bytecodes::_iflt      : // fall through

       case Bytecodes::_ifge      : // fall through

       case Bytecodes::_ifgt      : // fall through

       case Bytecodes::_ifle      : // fall through

       case Bytecodes::_if_icmpeq : // fall through

       case Bytecodes::_if_icmpne : // fall through

       case Bytecodes::_if_icmplt : // fall through

       case Bytecodes::_if_icmpge : // fall through

       case Bytecodes::_if_icmpgt : // fall through

       case Bytecodes::_if_icmple : // fall through

       case Bytecodes::_if_acmpeq : // fall through

       case Bytecodes::_if_acmpne :

         assert(stack_end >= -Bytecodes::depth(code), "must have non-empty expression stack at if bytecode");

         break;

     }

   }

 }

 #endif // ASSERT

 IntervalWalker* LinearScan::init_compute_oop_maps() {

   // setup lists of potential oops for walking

   Interval* oop_intervals;

   Interval* non_oop_intervals;

   create_unhandled_lists(&oop_intervals, &non_oop_intervals, is_oop_interval, NULL);

   // intervals that have no oops inside need not to be processed

   // to ensure a walking until the last instruction id, add a dummy interval

   // with a high operation id

   non_oop_intervals = new Interval(any_reg);

   non_oop_intervals->add_range(max_jint - 2, max_jint - 1);

   return new IntervalWalker(this, oop_intervals, non_oop_intervals);

 }

 OopMap* LinearScan::compute_oop_map(IntervalWalker* iw, LIR_Op* op, CodeEmitInfo* info, bool is_call_site) {

   TRACE_LINEAR_SCAN(3, tty->print_cr("creating oop map at op_id %d", op->id()));

   // walk before the current operation -> intervals that start at

   // the operation (= output operands of the operation) are not

   // included in the oop map

   iw->walk_before(op->id());

   int frame_size = frame_map()->framesize();

   int arg_count = frame_map()->oop_map_arg_count();

   OopMap* map = new OopMap(frame_size, arg_count);

   // Check if this is a patch site.

   bool is_patch_info = false;

   if (op->code() == lir_move) {

     assert(!is_call_site, "move must not be a call site");

     assert(op->as_Op1() != NULL, "move must be LIR_Op1");

     LIR_Op1* move = (LIR_Op1*)op;

     is_patch_info = move->patch_code() != lir_patch_none;

   }

   // Iterate through active intervals

   for (Interval* interval = iw->active_first(fixedKind); interval != Interval::end(); interval = interval->next()) {

     int assigned_reg = interval->assigned_reg();

     assert(interval->current_from() <= op->id() && op->id() <= interval->current_to(), "interval should not be active otherwise");

     assert(interval->assigned_regHi() == any_reg, "oop must be single word");

     assert(interval->reg_num() >= LIR_OprDesc::vreg_base, "fixed interval found");

     // Check if this range covers the instruction. Intervals that

     // start or end at the current operation are not included in the

     // oop map, except in the case of patching moves.  For patching

     // moves, any intervals which end at this instruction are included

     // in the oop map since we may safepoint while doing the patch

     // before we've consumed the inputs.

     if (is_patch_info || op->id() < interval->current_to()) {

       // caller-save registers must not be included into oop-maps at calls

       assert(!is_call_site || assigned_reg >= nof_regs || !is_caller_save(assigned_reg), "interval is in a caller-save register at a call -> register will be overwritten");

       VMReg name = vm_reg_for_interval(interval);

       set_oop(map, name);

       // Spill optimization: when the stack value is guaranteed to be always correct,

       // then it must be added to the oop map even if the interval is currently in a register

       if (interval->always_in_memory() &&

           op->id() > interval->spill_definition_pos() &&

           interval->assigned_reg() != interval->canonical_spill_slot()) {

         assert(interval->spill_definition_pos() > 0, "position not set correctly");

         assert(interval->canonical_spill_slot() >= LinearScan::nof_regs, "no spill slot assigned");

         assert(interval->assigned_reg() < LinearScan::nof_regs, "interval is on stack, so stack slot is registered twice");

         set_oop(map, frame_map()->slot_regname(interval->canonical_spill_slot() - LinearScan::nof_regs));

       }

     }

   }

   // add oops from lock stack

   assert(info->stack() != NULL, "CodeEmitInfo must always have a stack");

   int locks_count = info->stack()->total_locks_size();

   for (int i = 0; i < locks_count; i++) {

     set_oop(map, frame_map()->monitor_object_regname(i));

   }

   return map;

 }

 void LinearScan::compute_oop_map(IntervalWalker* iw, const LIR_OpVisitState &visitor, LIR_Op* op) {

   assert(visitor.info_count() > 0, "no oop map needed");

   // compute oop_map only for first CodeEmitInfo

   // because it is (in most cases) equal for all other infos of the same operation

   CodeEmitInfo* first_info = visitor.info_at(0);

   OopMap* first_oop_map = compute_oop_map(iw, op, first_info, visitor.has_call());

   for (int i = 0; i < visitor.info_count(); i++) {

     CodeEmitInfo* info = visitor.info_at(i);

     OopMap* oop_map = first_oop_map;

     if (info->stack()->locks_size() != first_info->stack()->locks_size()) {

       // this info has a different number of locks then the precomputed oop map

       // (possible for lock and unlock instructions) -> compute oop map with

       // correct lock information

       oop_map = compute_oop_map(iw, op, info, visitor.has_call());

     }

     if (info->_oop_map == NULL) {

       info->_oop_map = oop_map;

     } else {

       // a CodeEmitInfo can not be shared between different LIR-instructions

       // because interval splitting can occur anywhere between two instructions

       // and so the oop maps must be different

       // -> check if the already set oop_map is exactly the one calculated for this operation

       assert(info->_oop_map == oop_map, "same CodeEmitInfo used for multiple LIR instructions");

     }

   }

 }

 // frequently used constants

 // Allocate them with new so they are never destroyed (otherwise, a

 // forced exit could destroy these objects while they are still in

 // use).

 ConstantOopWriteValue* LinearScan::_oop_null_scope_value = new (ResourceObj::C_HEAP, mtCompiler) ConstantOopWriteValue(NULL);

 ConstantIntValue*      LinearScan::_int_m1_scope_value = new (ResourceObj::C_HEAP, mtCompiler) ConstantIntValue(-1);

 ConstantIntValue*      LinearScan::_int_0_scope_value =  new (ResourceObj::C_HEAP, mtCompiler) ConstantIntValue(0);

 ConstantIntValue*      LinearScan::_int_1_scope_value =  new (ResourceObj::C_HEAP, mtCompiler) ConstantIntValue(1);

 ConstantIntValue*      LinearScan::_int_2_scope_value =  new (ResourceObj::C_HEAP, mtCompiler) ConstantIntValue(2);

 LocationValue*         _illegal_value = new (ResourceObj::C_HEAP, mtCompiler) LocationValue(Location());

 void LinearScan::init_compute_debug_info() {

   // cache for frequently used scope values

   // (cpu registers and stack slots)

   _scope_value_cache = ScopeValueArray((LinearScan::nof_cpu_regs + frame_map()->argcount() + max_spills()) * 2, NULL);

 }

 MonitorValue* LinearScan::location_for_monitor_index(int monitor_index) {

   Location loc;

   if (!frame_map()->location_for_monitor_object(monitor_index, &loc)) {

     bailout("too large frame");

   }

   ScopeValue* object_scope_value = new LocationValue(loc);

   if (!frame_map()->location_for_monitor_lock(monitor_index, &loc)) {

     bailout("too large frame");

   }

   return new MonitorValue(object_scope_value, loc);

 }

 LocationValue* LinearScan::location_for_name(int name, Location::Type loc_type) {

   Location loc;

   if (!frame_map()->locations_for_slot(name, loc_type, &loc)) {

     bailout("too large frame");

   }

   return new LocationValue(loc);

 }

 int LinearScan::append_scope_value_for_constant(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values) {

   assert(opr->is_constant(), "should not be called otherwise");

   LIR_Const* c = opr->as_constant_ptr();

   BasicType t = c->type();

   switch (t) {

     case T_OBJECT: {

       jobject value = c->as_jobject();

       if (value == NULL) {

         scope_values->append(_oop_null_scope_value);

       } else {

         scope_values->append(new ConstantOopWriteValue(c->as_jobject()));

       }

       return 1;

     }

     case T_INT: // fall through

     case T_FLOAT: {

       int value = c->as_jint_bits();

       switch (value) {

         case -1: scope_values->append(_int_m1_scope_value); break;

         case 0:  scope_values->append(_int_0_scope_value); break;

         case 1:  scope_values->append(_int_1_scope_value); break;

         case 2:  scope_values->append(_int_2_scope_value); break;

         default: scope_values->append(new ConstantIntValue(c->as_jint_bits())); break;

       }

       return 1;

     }

     case T_LONG: // fall through

     case T_DOUBLE: {

 #ifdef _LP64

       scope_values->append(_int_0_scope_value);

       scope_values->append(new ConstantLongValue(c->as_jlong_bits()));

 #else

       if (hi_word_offset_in_bytes > lo_word_offset_in_bytes) {

         scope_values->append(new ConstantIntValue(c->as_jint_hi_bits()));

         scope_values->append(new ConstantIntValue(c->as_jint_lo_bits()));

       } else {

         scope_values->append(new ConstantIntValue(c->as_jint_lo_bits()));

         scope_values->append(new ConstantIntValue(c->as_jint_hi_bits()));

       }

 #endif

       return 2;

     }

     case T_ADDRESS: {

 #ifdef _LP64

       scope_values->append(new ConstantLongValue(c->as_jint()));

 #else

       scope_values->append(new ConstantIntValue(c->as_jint()));

 #endif

       return 1;

     }

     default:

       ShouldNotReachHere();

       return -1;

   }

 }

 int LinearScan::append_scope_value_for_operand(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values) {

   if (opr->is_single_stack()) {

     int stack_idx = opr->single_stack_ix();

     bool is_oop = opr->is_oop_register();

     int cache_idx = (stack_idx + LinearScan::nof_cpu_regs) * 2 + (is_oop ? 1 : 0);

     ScopeValue* sv = _scope_value_cache.at(cache_idx);

     if (sv == NULL) {

       Location::Type loc_type = is_oop ? Location::oop : Location::normal;

       sv = location_for_name(stack_idx, loc_type);

       _scope_value_cache.at_put(cache_idx, sv);

     }

     // check if cached value is correct

     DEBUG_ONLY(assert_equal(sv, location_for_name(stack_idx, is_oop ? Location::oop : Location::normal)));

     scope_values->append(sv);

     return 1;

   } else if (opr->is_single_cpu()) {

     bool is_oop = opr->is_oop_register();

     int cache_idx = opr->cpu_regnr() * 2 + (is_oop ? 1 : 0);

     Location::Type int_loc_type = NOT_LP64(Location::normal) LP64_ONLY(Location::int_in_long);

     ScopeValue* sv = _scope_value_cache.at(cache_idx);

     if (sv == NULL) {

       Location::Type loc_type = is_oop ? Location::oop : int_loc_type;

       VMReg rname = frame_map()->regname(opr);

       sv = new LocationValue(Location::new_reg_loc(loc_type, rname));

       _scope_value_cache.at_put(cache_idx, sv);

     }

     // check if cached value is correct

     DEBUG_ONLY(assert_equal(sv, new LocationValue(Location::new_reg_loc(is_oop ? Location::oop : int_loc_type, frame_map()->regname(opr)))));

     scope_values->append(sv);

     return 1;

 #ifdef X86

   } else if (opr->is_single_xmm()) {

     VMReg rname = opr->as_xmm_float_reg()->as_VMReg();

     LocationValue* sv = new LocationValue(Location::new_reg_loc(Location::normal, rname));

     scope_values->append(sv);

     return 1;

 #endif

   } else if (opr->is_single_fpu()) {

 #ifdef X86

     // the exact location of fpu stack values is only known

     // during fpu stack allocation, so the stack allocator object

     // must be present

     assert(use_fpu_stack_allocation(), "should not have float stack values without fpu stack allocation (all floats must be SSE2)");

     assert(_fpu_stack_allocator != NULL, "must be present");

     opr = _fpu_stack_allocator->to_fpu_stack(opr);

 #endif

     Location::Type loc_type = float_saved_as_double ? Location::float_in_dbl : Location::normal;

     VMReg rname = frame_map()->fpu_regname(opr->fpu_regnr());

 #ifndef __SOFTFP__

 #ifndef VM_LITTLE_ENDIAN

     if (! float_saved_as_double) {

       // On big endian system, we may have an issue if float registers use only

       // the low half of the (same) double registers.

       // Both the float and the double could have the same regnr but would correspond

       // to two different addresses once saved.

       // get next safely (no assertion checks)

       VMReg next = VMRegImpl::as_VMReg(1+rname->value());

       if (next->is_reg() &&

           (next->as_FloatRegister() == rname->as_FloatRegister())) {

         // the back-end does use the same numbering for the double and the float

         rname = next; // VMReg for the low bits, e.g. the real VMReg for the float