c1_LinearScan.cpp revision 1969
0N/A/*
3158N/A * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1472N/A * or visit www.oracle.com if you need additional information or have any
1472N/A * questions.
0N/A *
0N/A */
0N/A
1879N/A#include "precompiled.hpp"
1879N/A#include "c1/c1_CFGPrinter.hpp"
1879N/A#include "c1/c1_CodeStubs.hpp"
1879N/A#include "c1/c1_Compilation.hpp"
1879N/A#include "c1/c1_FrameMap.hpp"
1879N/A#include "c1/c1_IR.hpp"
1879N/A#include "c1/c1_LIRGenerator.hpp"
1879N/A#include "c1/c1_LinearScan.hpp"
1879N/A#include "c1/c1_ValueStack.hpp"
1879N/A#include "utilities/bitMap.inline.hpp"
1879N/A#ifdef TARGET_ARCH_x86
1879N/A# include "vmreg_x86.inline.hpp"
1879N/A#endif
1879N/A#ifdef TARGET_ARCH_sparc
1879N/A# include "vmreg_sparc.inline.hpp"
1879N/A#endif
1879N/A#ifdef TARGET_ARCH_zero
1879N/A# include "vmreg_zero.inline.hpp"
0N/A#endif
0N/A
0N/A
524N/A#ifndef PRODUCT
524N/A
0N/A static LinearScanStatistic _stat_before_alloc;
0N/A static LinearScanStatistic _stat_after_asign;
0N/A static LinearScanStatistic _stat_final;
0N/A
0N/A static LinearScanTimers _total_timer;
0N/A
0N/A // helper macro for short definition of timer
0N/A #define TIME_LINEAR_SCAN(timer_name) TraceTime _block_timer("", _total_timer.timer(LinearScanTimers::timer_name), TimeLinearScan || TimeEachLinearScan, Verbose);
0N/A
0N/A // helper macro for short definition of trace-output inside code
0N/A #define TRACE_LINEAR_SCAN(level, code) \
0N/A if (TraceLinearScanLevel >= level) { \
0N/A code; \
0N/A }
0N/A
0N/A#else
0N/A
0N/A #define TIME_LINEAR_SCAN(timer_name)
0N/A #define TRACE_LINEAR_SCAN(level, code)
0N/A
0N/A#endif
0N/A
0N/A// Map BasicType to spill size in 32-bit words, matching VMReg's notion of words
0N/A#ifdef _LP64
0N/Astatic int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 0, 1, -1};
0N/A#else
0N/Astatic int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0, 1, -1};
0N/A#endif
0N/A
0N/A
0N/A// Implementation of LinearScan
0N/A
0N/ALinearScan::LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map)
0N/A : _compilation(ir->compilation())
0N/A , _ir(ir)
0N/A , _gen(gen)
0N/A , _frame_map(frame_map)
0N/A , _num_virtual_regs(gen->max_virtual_register_number())
0N/A , _has_fpu_registers(false)
0N/A , _num_calls(-1)
0N/A , _max_spills(0)
0N/A , _unused_spill_slot(-1)
0N/A , _intervals(0) // initialized later with correct length
0N/A , _new_intervals_from_allocation(new IntervalList())
0N/A , _sorted_intervals(NULL)
0N/A , _needs_full_resort(false)
0N/A , _lir_ops(0) // initialized later with correct length
0N/A , _block_of_op(0) // initialized later with correct length
0N/A , _has_info(0)
0N/A , _has_call(0)
0N/A , _scope_value_cache(0) // initialized later with correct length
0N/A , _interval_in_loop(0, 0) // initialized later with correct length
0N/A , _cached_blocks(*ir->linear_scan_order())
0N/A#ifdef X86
0N/A , _fpu_stack_allocator(NULL)
0N/A#endif
0N/A{
0N/A assert(this->ir() != NULL, "check if valid");
0N/A assert(this->compilation() != NULL, "check if valid");
0N/A assert(this->gen() != NULL, "check if valid");
0N/A assert(this->frame_map() != NULL, "check if valid");
0N/A}
0N/A
0N/A
0N/A// ********** functions for converting LIR-Operands to register numbers
0N/A//
0N/A// Emulate a flat register file comprising physical integer registers,
0N/A// physical floating-point registers and virtual registers, in that order.
0N/A// Virtual registers already have appropriate numbers, since V0 is
0N/A// the number of physical registers.
0N/A// Returns -1 for hi word if opr is a single word operand.
0N/A//
0N/A// Note: the inverse operation (calculating an operand for register numbers)
0N/A// is done in calc_operand_for_interval()
0N/A
0N/Aint LinearScan::reg_num(LIR_Opr opr) {
0N/A assert(opr->is_register(), "should not call this otherwise");
0N/A
0N/A if (opr->is_virtual_register()) {
304N/A assert(opr->vreg_number() >= nof_regs, "found a virtual register with a fixed-register number");
0N/A return opr->vreg_number();
0N/A } else if (opr->is_single_cpu()) {
304N/A return opr->cpu_regnr();
304N/A } else if (opr->is_double_cpu()) {
304N/A return opr->cpu_regnrLo();
0N/A#ifdef X86
0N/A } else if (opr->is_single_xmm()) {
0N/A return opr->fpu_regnr() + pd_first_xmm_reg;
0N/A } else if (opr->is_double_xmm()) {
0N/A return opr->fpu_regnrLo() + pd_first_xmm_reg;
0N/A#endif
0N/A } else if (opr->is_single_fpu()) {
0N/A return opr->fpu_regnr() + pd_first_fpu_reg;
0N/A } else if (opr->is_double_fpu()) {
0N/A return opr->fpu_regnrLo() + pd_first_fpu_reg;
0N/A } else {
0N/A ShouldNotReachHere();
0N/A return -1;
0N/A }
0N/A}
0N/A
0N/Aint LinearScan::reg_numHi(LIR_Opr opr) {
0N/A assert(opr->is_register(), "should not call this otherwise");
0N/A
0N/A if (opr->is_virtual_register()) {
0N/A return -1;
0N/A } else if (opr->is_single_cpu()) {
0N/A return -1;
0N/A } else if (opr->is_double_cpu()) {
0N/A return opr->cpu_regnrHi();
0N/A#ifdef X86
0N/A } else if (opr->is_single_xmm()) {
0N/A return -1;
0N/A } else if (opr->is_double_xmm()) {
0N/A return -1;
0N/A#endif
0N/A } else if (opr->is_single_fpu()) {
0N/A return -1;
0N/A } else if (opr->is_double_fpu()) {
0N/A return opr->fpu_regnrHi() + pd_first_fpu_reg;
0N/A } else {
0N/A ShouldNotReachHere();
0N/A return -1;
0N/A }
0N/A}
0N/A
0N/A
0N/A// ********** functions for classification of intervals
0N/A
0N/Abool LinearScan::is_precolored_interval(const Interval* i) {
0N/A return i->reg_num() < LinearScan::nof_regs;
0N/A}
0N/A
0N/Abool LinearScan::is_virtual_interval(const Interval* i) {
0N/A return i->reg_num() >= LIR_OprDesc::vreg_base;
0N/A}
0N/A
0N/Abool LinearScan::is_precolored_cpu_interval(const Interval* i) {
0N/A return i->reg_num() < LinearScan::nof_cpu_regs;
0N/A}
0N/A
0N/Abool LinearScan::is_virtual_cpu_interval(const Interval* i) {
0N/A#if defined(__SOFTFP__) || defined(E500V2)
0N/A return i->reg_num() >= LIR_OprDesc::vreg_base;
0N/A#else
0N/A return i->reg_num() >= LIR_OprDesc::vreg_base && (i->type() != T_FLOAT && i->type() != T_DOUBLE);
0N/A#endif // __SOFTFP__ or E500V2
0N/A}
0N/A
0N/Abool LinearScan::is_precolored_fpu_interval(const Interval* i) {
0N/A return i->reg_num() >= LinearScan::nof_cpu_regs && i->reg_num() < LinearScan::nof_regs;
0N/A}
0N/A
0N/Abool LinearScan::is_virtual_fpu_interval(const Interval* i) {
0N/A#if defined(__SOFTFP__) || defined(E500V2)
0N/A return false;
0N/A#else
0N/A return i->reg_num() >= LIR_OprDesc::vreg_base && (i->type() == T_FLOAT || i->type() == T_DOUBLE);
0N/A#endif // __SOFTFP__ or E500V2
0N/A}
0N/A
0N/Abool LinearScan::is_in_fpu_register(const Interval* i) {
0N/A // fixed intervals not needed for FPU stack allocation
0N/A return i->reg_num() >= nof_regs && pd_first_fpu_reg <= i->assigned_reg() && i->assigned_reg() <= pd_last_fpu_reg;
0N/A}
0N/A
0N/Abool LinearScan::is_oop_interval(const Interval* i) {
0N/A // fixed intervals never contain oops
0N/A return i->reg_num() >= nof_regs && i->type() == T_OBJECT;
0N/A}
0N/A
0N/A
0N/A// ********** General helper functions
0N/A
0N/A// compute next unused stack index that can be used for spilling
0N/Aint LinearScan::allocate_spill_slot(bool double_word) {
0N/A int spill_slot;
0N/A if (double_word) {
0N/A if ((_max_spills & 1) == 1) {
0N/A // alignment of double-word values
0N/A // the hole because of the alignment is filled with the next single-word value
0N/A assert(_unused_spill_slot == -1, "wasting a spill slot");
0N/A _unused_spill_slot = _max_spills;
0N/A _max_spills++;
0N/A }
0N/A spill_slot = _max_spills;
0N/A _max_spills += 2;
0N/A
0N/A } else if (_unused_spill_slot != -1) {
0N/A // re-use hole that was the result of a previous double-word alignment
0N/A spill_slot = _unused_spill_slot;
0N/A _unused_spill_slot = -1;
0N/A
0N/A } else {
0N/A spill_slot = _max_spills;
0N/A _max_spills++;
0N/A }
0N/A
0N/A int result = spill_slot + LinearScan::nof_regs + frame_map()->argcount();
0N/A
0N/A // the class OopMapValue uses only 11 bits for storing the name of the
0N/A // oop location. So a stack slot bigger than 2^11 leads to an overflow
0N/A // that is not reported in product builds. Prevent this by checking the
0N/A // spill slot here (altough this value and the later used location name
0N/A // are slightly different)
0N/A if (result > 2000) {
0N/A bailout("too many stack slots used");
0N/A }
0N/A
0N/A return result;
0N/A}
0N/A
0N/Avoid LinearScan::assign_spill_slot(Interval* it) {
0N/A // assign the canonical spill slot of the parent (if a part of the interval
0N/A // is already spilled) or allocate a new spill slot
0N/A if (it->canonical_spill_slot() >= 0) {
0N/A it->assign_reg(it->canonical_spill_slot());
0N/A } else {
0N/A int spill = allocate_spill_slot(type2spill_size[it->type()] == 2);
0N/A it->set_canonical_spill_slot(spill);
0N/A it->assign_reg(spill);
0N/A }
0N/A}
0N/A
0N/Avoid LinearScan::propagate_spill_slots() {
0N/A if (!frame_map()->finalize_frame(max_spills())) {
0N/A bailout("frame too large");
0N/A }
0N/A}
0N/A
0N/A// create a new interval with a predefined reg_num
304N/A// (only used for parent intervals that are created during the building phase)
304N/AInterval* LinearScan::create_interval(int reg_num) {
304N/A assert(_intervals.at(reg_num) == NULL, "overwriting exisiting interval");
304N/A
0N/A Interval* interval = new Interval(reg_num);
304N/A _intervals.at_put(reg_num, interval);
0N/A
0N/A // assign register number for precolored intervals
0N/A if (reg_num < LIR_OprDesc::vreg_base) {
0N/A interval->assign_reg(reg_num);
0N/A }
0N/A return interval;
0N/A}
0N/A
0N/A// assign a new reg_num to the interval and append it to the list of intervals
0N/A// (only used for child intervals that are created during register allocation)
0N/Avoid LinearScan::append_interval(Interval* it) {
0N/A it->set_reg_num(_intervals.length());
0N/A _intervals.append(it);
0N/A _new_intervals_from_allocation->append(it);
0N/A}
0N/A
0N/A// copy the vreg-flags if an interval is split
0N/Avoid LinearScan::copy_register_flags(Interval* from, Interval* to) {
0N/A if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::byte_reg)) {
0N/A gen()->set_vreg_flag(to->reg_num(), LIRGenerator::byte_reg);
304N/A }
304N/A if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::callee_saved)) {
0N/A gen()->set_vreg_flag(to->reg_num(), LIRGenerator::callee_saved);
304N/A }
0N/A
0N/A // Note: do not copy the must_start_in_memory flag because it is not necessary for child
0N/A // intervals (only the very beginning of the interval must be in memory)
0N/A}
0N/A
0N/A
0N/A// ********** spill move optimization
0N/A// eliminate moves from register to stack if stack slot is known to be correct
0N/A
0N/A// called during building of intervals
0N/Avoid LinearScan::change_spill_definition_pos(Interval* interval, int def_pos) {
0N/A assert(interval->is_split_parent(), "can only be called for split parents");
0N/A
0N/A switch (interval->spill_state()) {
0N/A case noDefinitionFound:
0N/A assert(interval->spill_definition_pos() == -1, "must no be set before");
0N/A interval->set_spill_definition_pos(def_pos);
0N/A interval->set_spill_state(oneDefinitionFound);
0N/A break;
0N/A
0N/A case oneDefinitionFound:
0N/A assert(def_pos <= interval->spill_definition_pos(), "positions are processed in reverse order when intervals are created");
0N/A if (def_pos < interval->spill_definition_pos() - 2) {
0N/A // second definition found, so no spill optimization possible for this interval
0N/A interval->set_spill_state(noOptimization);
0N/A } else {
0N/A // two consecutive definitions (because of two-operand LIR form)
0N/A assert(block_of_op_with_id(def_pos) == block_of_op_with_id(interval->spill_definition_pos()), "block must be equal");
0N/A }
0N/A break;
0N/A
0N/A case noOptimization:
0N/A // nothing to do
0N/A break;
0N/A
0N/A default:
0N/A assert(false, "other states not allowed at this time");
0N/A }
0N/A}
0N/A
0N/A// called during register allocation
0N/Avoid LinearScan::change_spill_state(Interval* interval, int spill_pos) {
0N/A switch (interval->spill_state()) {
0N/A case oneDefinitionFound: {
0N/A int def_loop_depth = block_of_op_with_id(interval->spill_definition_pos())->loop_depth();
0N/A int spill_loop_depth = block_of_op_with_id(spill_pos)->loop_depth();
0N/A
0N/A if (def_loop_depth < spill_loop_depth) {
0N/A // the loop depth of the spilling position is higher then the loop depth
0N/A // at the definition of the interval -> move write to memory out of loop
0N/A // by storing at definitin of the interval
0N/A interval->set_spill_state(storeAtDefinition);
0N/A } else {
0N/A // the interval is currently spilled only once, so for now there is no
0N/A // reason to store the interval at the definition
0N/A interval->set_spill_state(oneMoveInserted);
0N/A }
0N/A break;
0N/A }
0N/A
0N/A case oneMoveInserted: {
0N/A // the interval is spilled more then once, so it is better to store it to
0N/A // memory at the definition
0N/A interval->set_spill_state(storeAtDefinition);
0N/A break;
0N/A }
0N/A
0N/A case storeAtDefinition:
0N/A case startInMemory:
0N/A case noOptimization:
0N/A case noDefinitionFound:
0N/A // nothing to do
0N/A break;
0N/A
0N/A default:
0N/A assert(false, "other states not allowed at this time");
0N/A }
0N/A}
0N/A
0N/A
0N/Abool LinearScan::must_store_at_definition(const Interval* i) {
0N/A return i->is_split_parent() && i->spill_state() == storeAtDefinition;
0N/A}
0N/A
0N/A// called once before asignment of register numbers
0N/Avoid LinearScan::eliminate_spill_moves() {
0N/A TIME_LINEAR_SCAN(timer_eliminate_spill_moves);
0N/A TRACE_LINEAR_SCAN(3, tty->print_cr("***** Eliminating unnecessary spill moves"));
0N/A
0N/A // collect all intervals that must be stored after their definion.
0N/A // the list is sorted by Interval::spill_definition_pos
0N/A Interval* interval;
0N/A Interval* temp_list;
0N/A create_unhandled_lists(&interval, &temp_list, must_store_at_definition, NULL);
0N/A
0N/A#ifdef ASSERT
0N/A Interval* prev = NULL;
0N/A Interval* temp = interval;
0N/A while (temp != Interval::end()) {
0N/A assert(temp->spill_definition_pos() > 0, "invalid spill definition pos");
0N/A if (prev != NULL) {
0N/A assert(temp->from() >= prev->from(), "intervals not sorted");
0N/A 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");
0N/A }
0N/A
0N/A assert(temp->canonical_spill_slot() >= LinearScan::nof_regs, "interval has no spill slot assigned");
0N/A assert(temp->spill_definition_pos() >= temp->from(), "invalid order");
0N/A assert(temp->spill_definition_pos() <= temp->from() + 2, "only intervals defined once at their start-pos can be optimized");
0N/A
0N/A 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()));
0N/A
0N/A temp = temp->next();
0N/A }
0N/A#endif
0N/A
0N/A LIR_InsertionBuffer insertion_buffer;
0N/A int num_blocks = block_count();
0N/A for (int i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A LIR_OpList* instructions = block->lir()->instructions_list();
0N/A int num_inst = instructions->length();
0N/A bool has_new = false;
0N/A
0N/A // iterate all instructions of the block. skip the first because it is always a label
0N/A for (int j = 1; j < num_inst; j++) {
0N/A LIR_Op* op = instructions->at(j);
0N/A int op_id = op->id();
0N/A
0N/A if (op_id == -1) {
0N/A // remove move from register to stack if the stack slot is guaranteed to be correct.
0N/A // only moves that have been inserted by LinearScan can be removed.
0N/A assert(op->code() == lir_move, "only moves can have a op_id of -1");
0N/A assert(op->as_Op1() != NULL, "move must be LIR_Op1");
0N/A assert(op->as_Op1()->result_opr()->is_virtual(), "LinearScan inserts only moves to virtual registers");
0N/A
0N/A LIR_Op1* op1 = (LIR_Op1*)op;
0N/A Interval* interval = interval_at(op1->result_opr()->vreg_number());
0N/A
0N/A if (interval->assigned_reg() >= LinearScan::nof_regs && interval->always_in_memory()) {
0N/A // move target is a stack slot that is always correct, so eliminate instruction
0N/A TRACE_LINEAR_SCAN(4, tty->print_cr("eliminating move from interval %d to %d", op1->in_opr()->vreg_number(), op1->result_opr()->vreg_number()));
0N/A instructions->at_put(j, NULL); // NULL-instructions are deleted by assign_reg_num
0N/A }
0N/A
0N/A } else {
0N/A // insert move from register to stack just after the beginning of the interval
0N/A assert(interval == Interval::end() || interval->spill_definition_pos() >= op_id, "invalid order");
0N/A assert(interval == Interval::end() || (interval->is_split_parent() && interval->spill_state() == storeAtDefinition), "invalid interval");
304N/A
0N/A while (interval != Interval::end() && interval->spill_definition_pos() == op_id) {
0N/A if (!has_new) {
0N/A // prepare insertion buffer (appended when all instructions of the block are processed)
0N/A insertion_buffer.init(block->lir());
304N/A has_new = true;
304N/A }
304N/A
0N/A LIR_Opr from_opr = operand_for_interval(interval);
0N/A LIR_Opr to_opr = canonical_spill_opr(interval);
304N/A assert(from_opr->is_fixed_cpu() || from_opr->is_fixed_fpu(), "from operand must be a register");
0N/A assert(to_opr->is_stack(), "to operand must be a stack slot");
0N/A
0N/A insertion_buffer.move(j, from_opr, to_opr);
0N/A 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));
304N/A
0N/A interval = interval->next();
0N/A }
0N/A }
0N/A } // end of instruction iteration
0N/A
0N/A if (has_new) {
0N/A block->lir()->append(&insertion_buffer);
0N/A }
0N/A } // end of block iteration
0N/A
0N/A assert(interval == Interval::end(), "missed an interval");
0N/A}
0N/A
304N/A
0N/A// ********** Phase 1: number all instructions in all blocks
304N/A// Compute depth-first and linear scan block orders, and number LIR_Op nodes for linear scan.
0N/A
0N/Avoid LinearScan::number_instructions() {
304N/A {
0N/A // dummy-timer to measure the cost of the timer itself
0N/A // (this time is then subtracted from all other timers to get the real value)
0N/A TIME_LINEAR_SCAN(timer_do_nothing);
0N/A }
304N/A TIME_LINEAR_SCAN(timer_number_instructions);
0N/A
0N/A // Assign IDs to LIR nodes and build a mapping, lir_ops, from ID to LIR_Op node.
0N/A int num_blocks = block_count();
0N/A int num_instructions = 0;
304N/A int i;
0N/A for (i = 0; i < num_blocks; i++) {
0N/A num_instructions += block_at(i)->lir()->instructions_list()->length();
304N/A }
304N/A
0N/A // initialize with correct length
0N/A _lir_ops = LIR_OpArray(num_instructions);
0N/A _block_of_op = BlockBeginArray(num_instructions);
0N/A
0N/A int op_id = 0;
1426N/A int idx = 0;
1426N/A
0N/A for (i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A block->set_first_lir_instruction_id(op_id);
0N/A LIR_OpList* instructions = block->lir()->instructions_list();
0N/A
0N/A int num_inst = instructions->length();
0N/A for (int j = 0; j < num_inst; j++) {
0N/A LIR_Op* op = instructions->at(j);
0N/A op->set_id(op_id);
0N/A
0N/A _lir_ops.at_put(idx, op);
0N/A _block_of_op.at_put(idx, block);
0N/A assert(lir_op_with_id(op_id) == op, "must match");
0N/A
0N/A idx++;
0N/A op_id += 2; // numbering of lir_ops by two
0N/A }
0N/A block->set_last_lir_instruction_id(op_id - 2);
0N/A }
0N/A assert(idx == num_instructions, "must match");
0N/A assert(idx * 2 == op_id, "must match");
0N/A
0N/A _has_call = BitMap(num_instructions); _has_call.clear();
0N/A _has_info = BitMap(num_instructions); _has_info.clear();
0N/A}
0N/A
0N/A
0N/A// ********** Phase 2: compute local live sets separately for each block
0N/A// (sets live_gen and live_kill for each block)
1426N/A
0N/Avoid LinearScan::set_live_gen_kill(Value value, LIR_Op* op, BitMap& live_gen, BitMap& live_kill) {
0N/A LIR_Opr opr = value->operand();
304N/A Constant* con = value->as_Constant();
0N/A
0N/A // check some asumptions about debug information
304N/A assert(!value->type()->is_illegal(), "if this local is used by the interpreter it shouldn't be of indeterminate type");
304N/A assert(con == NULL || opr->is_virtual() || opr->is_constant() || opr->is_illegal(), "asumption: Constant instructions have only constant operands");
304N/A assert(con != NULL || opr->is_virtual(), "asumption: non-Constant instructions have only virtual operands");
0N/A
0N/A if ((con == NULL || con->is_pinned()) && opr->is_register()) {
0N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A int reg = opr->vreg_number();
0N/A if (!live_kill.at(reg)) {
0N/A live_gen.set_bit(reg);
0N/A 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));
0N/A }
0N/A }
1426N/A}
1426N/A
304N/A
0N/Avoid LinearScan::compute_local_live_sets() {
0N/A TIME_LINEAR_SCAN(timer_compute_local_live_sets);
0N/A
0N/A int num_blocks = block_count();
0N/A int live_size = live_set_size();
0N/A bool local_has_fpu_registers = false;
0N/A int local_num_calls = 0;
0N/A LIR_OpVisitState visitor;
0N/A
0N/A BitMap2D local_interval_in_loop = BitMap2D(_num_virtual_regs, num_loops());
0N/A local_interval_in_loop.clear();
0N/A
0N/A // iterate all blocks
0N/A for (int i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A
0N/A BitMap live_gen(live_size); live_gen.clear();
0N/A BitMap live_kill(live_size); live_kill.clear();
0N/A
304N/A if (block->is_set(BlockBegin::exception_entry_flag)) {
0N/A // Phi functions at the begin of an exception handler are
0N/A // implicitly defined (= killed) at the beginning of the block.
0N/A for_each_phi_fun(block, phi,
0N/A live_kill.set_bit(phi->operand()->vreg_number())
0N/A );
304N/A }
304N/A
304N/A LIR_OpList* instructions = block->lir()->instructions_list();
304N/A int num_inst = instructions->length();
304N/A
304N/A // iterate all instructions of the block. skip the first because it is always a label
304N/A assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
304N/A for (int j = 1; j < num_inst; j++) {
304N/A LIR_Op* op = instructions->at(j);
304N/A
304N/A // visit operation to collect all operands
304N/A visitor.visit(op);
0N/A
0N/A if (visitor.has_call()) {
0N/A _has_call.set_bit(op->id() >> 1);
0N/A local_num_calls++;
0N/A }
0N/A if (visitor.info_count() > 0) {
0N/A _has_info.set_bit(op->id() >> 1);
304N/A }
304N/A
304N/A // iterate input operands of instruction
304N/A int k, n, reg;
304N/A n = visitor.opr_count(LIR_OpVisitState::inputMode);
304N/A for (k = 0; k < n; k++) {
304N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
304N/A assert(opr->is_register(), "visitor should only return register operands");
304N/A
304N/A if (opr->is_virtual_register()) {
304N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
304N/A reg = opr->vreg_number();
304N/A if (!live_kill.at(reg)) {
304N/A live_gen.set_bit(reg);
0N/A TRACE_LINEAR_SCAN(4, tty->print_cr(" Setting live_gen for register %d at instruction %d", reg, op->id()));
0N/A }
0N/A if (block->loop_index() >= 0) {
0N/A local_interval_in_loop.set_bit(reg, block->loop_index());
0N/A }
0N/A local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
0N/A }
0N/A
0N/A#ifdef ASSERT
0N/A // fixed intervals are never live at block boundaries, so
0N/A // they need not be processed in live sets.
0N/A // this is checked by these assertions to be sure about it.
0N/A // the entry block may have incoming values in registers, which is ok.
304N/A if (!opr->is_virtual_register() && block != ir()->start()) {
0N/A reg = reg_num(opr);
304N/A if (is_processed_reg_num(reg)) {
0N/A assert(live_kill.at(reg), "using fixed register that is not defined in this block");
0N/A }
0N/A reg = reg_numHi(opr);
0N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
0N/A assert(live_kill.at(reg), "using fixed register that is not defined in this block");
1426N/A }
1426N/A }
0N/A#endif
0N/A }
3932N/A
3932N/A // Add uses of live locals from interpreter's point of view for proper debug information generation
3932N/A n = visitor.info_count();
3932N/A for (k = 0; k < n; k++) {
3932N/A CodeEmitInfo* info = visitor.info_at(k);
3932N/A ValueStack* stack = info->stack();
3932N/A for_each_state_value(stack, value,
3932N/A set_live_gen_kill(value, op, live_gen, live_kill)
3932N/A );
3932N/A }
3932N/A
3932N/A // iterate temp operands of instruction
3932N/A n = visitor.opr_count(LIR_OpVisitState::tempMode);
0N/A for (k = 0; k < n; k++) {
0N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
0N/A assert(opr->is_register(), "visitor should only return register operands");
0N/A
0N/A if (opr->is_virtual_register()) {
0N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A reg = opr->vreg_number();
0N/A live_kill.set_bit(reg);
0N/A if (block->loop_index() >= 0) {
0N/A local_interval_in_loop.set_bit(reg, block->loop_index());
3932N/A }
3932N/A local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
3932N/A }
3932N/A
3932N/A#ifdef ASSERT
3932N/A // fixed intervals are never live at block boundaries, so
3932N/A // they need not be processed in live sets
3932N/A // process them only in debug mode so that this can be checked
3932N/A if (!opr->is_virtual_register()) {
3932N/A reg = reg_num(opr);
3932N/A if (is_processed_reg_num(reg)) {
3932N/A live_kill.set_bit(reg_num(opr));
3932N/A }
3932N/A reg = reg_numHi(opr);
3932N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
3932N/A live_kill.set_bit(reg);
3932N/A }
0N/A }
304N/A#endif
0N/A }
3932N/A
3932N/A // iterate output operands of instruction
3932N/A n = visitor.opr_count(LIR_OpVisitState::outputMode);
3932N/A for (k = 0; k < n; k++) {
3932N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::outputMode, k);
3932N/A assert(opr->is_register(), "visitor should only return register operands");
3932N/A
3932N/A if (opr->is_virtual_register()) {
3932N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
3932N/A reg = opr->vreg_number();
3932N/A live_kill.set_bit(reg);
3932N/A if (block->loop_index() >= 0) {
3932N/A local_interval_in_loop.set_bit(reg, block->loop_index());
3932N/A }
3932N/A local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
3932N/A }
3932N/A
3932N/A#ifdef ASSERT
3932N/A // fixed intervals are never live at block boundaries, so
3932N/A // they need not be processed in live sets
3932N/A // process them only in debug mode so that this can be checked
3932N/A if (!opr->is_virtual_register()) {
3932N/A reg = reg_num(opr);
3932N/A if (is_processed_reg_num(reg)) {
3932N/A live_kill.set_bit(reg_num(opr));
3932N/A }
3932N/A reg = reg_numHi(opr);
0N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
0N/A live_kill.set_bit(reg);
304N/A }
0N/A }
0N/A#endif
0N/A }
0N/A } // end of instruction iteration
0N/A
0N/A block->set_live_gen (live_gen);
0N/A block->set_live_kill(live_kill);
0N/A block->set_live_in (BitMap(live_size)); block->live_in().clear();
0N/A block->set_live_out (BitMap(live_size)); block->live_out().clear();
0N/A
0N/A TRACE_LINEAR_SCAN(4, tty->print("live_gen B%d ", block->block_id()); print_bitmap(block->live_gen()));
0N/A TRACE_LINEAR_SCAN(4, tty->print("live_kill B%d ", block->block_id()); print_bitmap(block->live_kill()));
0N/A } // end of block iteration
304N/A
0N/A // propagate local calculated information into LinearScan object
0N/A _has_fpu_registers = local_has_fpu_registers;
0N/A compilation()->set_has_fpu_code(local_has_fpu_registers);
304N/A
0N/A _num_calls = local_num_calls;
0N/A _interval_in_loop = local_interval_in_loop;
0N/A}
304N/A
0N/A
0N/A// ********** Phase 3: perform a backward dataflow analysis to compute global live sets
0N/A// (sets live_in and live_out for each block)
304N/A
0N/Avoid LinearScan::compute_global_live_sets() {
0N/A TIME_LINEAR_SCAN(timer_compute_global_live_sets);
0N/A
0N/A int num_blocks = block_count();
304N/A bool change_occurred;
0N/A bool change_occurred_in_block;
0N/A int iteration_count = 0;
0N/A BitMap live_out(live_set_size()); live_out.clear(); // scratch set for calculations
0N/A
0N/A // Perform a backward dataflow analysis to compute live_out and live_in for each block.
0N/A // The loop is executed until a fixpoint is reached (no changes in an iteration)
0N/A // Exception handlers must be processed because not all live values are
0N/A // present in the state array, e.g. because of global value numbering
0N/A do {
0N/A change_occurred = false;
0N/A
0N/A // iterate all blocks in reverse order
0N/A for (int i = num_blocks - 1; i >= 0; i--) {
0N/A BlockBegin* block = block_at(i);
0N/A
0N/A change_occurred_in_block = false;
1426N/A
0N/A // live_out(block) is the union of live_in(sux), for successors sux of block
1426N/A int n = block->number_of_sux();
0N/A int e = block->number_of_exception_handlers();
0N/A if (n + e > 0) {
0N/A // block has successors
0N/A if (n > 0) {
0N/A live_out.set_from(block->sux_at(0)->live_in());
0N/A for (int j = 1; j < n; j++) {
0N/A live_out.set_union(block->sux_at(j)->live_in());
0N/A }
0N/A } else {
0N/A live_out.clear();
0N/A }
0N/A for (int j = 0; j < e; j++) {
0N/A live_out.set_union(block->exception_handler_at(j)->live_in());
0N/A }
0N/A
0N/A if (!block->live_out().is_same(live_out)) {
0N/A // A change occurred. Swap the old and new live out sets to avoid copying.
0N/A BitMap temp = block->live_out();
0N/A block->set_live_out(live_out);
0N/A live_out = temp;
304N/A
0N/A change_occurred = true;
0N/A change_occurred_in_block = true;
0N/A }
0N/A }
0N/A
0N/A if (iteration_count == 0 || change_occurred_in_block) {
0N/A // live_in(block) is the union of live_gen(block) with (live_out(block) & !live_kill(block))
0N/A // note: live_in has to be computed only in first iteration or if live_out has changed!
304N/A BitMap live_in = block->live_in();
304N/A live_in.set_from(block->live_out());
304N/A live_in.set_difference(block->live_kill());
304N/A live_in.set_union(block->live_gen());
304N/A }
304N/A
304N/A#ifndef PRODUCT
304N/A if (TraceLinearScanLevel >= 4) {
304N/A char c = ' ';
304N/A if (iteration_count == 0 || change_occurred_in_block) {
304N/A c = '*';
304N/A }
304N/A tty->print("(%d) live_in%c B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_in());
304N/A tty->print("(%d) live_out%c B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_out());
304N/A }
304N/A#endif
304N/A }
0N/A iteration_count++;
0N/A
0N/A if (change_occurred && iteration_count > 50) {
0N/A BAILOUT("too many iterations in compute_global_live_sets");
0N/A }
304N/A } while (change_occurred);
304N/A
304N/A
304N/A#ifdef ASSERT
304N/A // check that fixed intervals are not live at block boundaries
304N/A // (live set must be empty at fixed intervals)
304N/A for (int i = 0; i < num_blocks; i++) {
304N/A BlockBegin* block = block_at(i);
304N/A for (int j = 0; j < LIR_OprDesc::vreg_base; j++) {
304N/A assert(block->live_in().at(j) == false, "live_in set of fixed register must be empty");
304N/A assert(block->live_out().at(j) == false, "live_out set of fixed register must be empty");
0N/A assert(block->live_gen().at(j) == false, "live_gen set of fixed register must be empty");
0N/A }
0N/A }
304N/A#endif
304N/A
0N/A // check that the live_in set of the first block is empty
0N/A BitMap live_in_args(ir()->start()->live_in().size());
0N/A live_in_args.clear();
0N/A if (!ir()->start()->live_in().is_same(live_in_args)) {
0N/A#ifdef ASSERT
0N/A tty->print_cr("Error: live_in set of first block must be empty (when this fails, virtual registers are used before they are defined)");
0N/A tty->print_cr("affected registers:");
0N/A print_bitmap(ir()->start()->live_in());
0N/A
0N/A // print some additional information to simplify debugging
0N/A for (unsigned int i = 0; i < ir()->start()->live_in().size(); i++) {
0N/A if (ir()->start()->live_in().at(i)) {
0N/A Instruction* instr = gen()->instruction_for_vreg(i);
0N/A tty->print_cr("* vreg %d (HIR instruction %c%d)", i, instr == NULL ? ' ' : instr->type()->tchar(), instr == NULL ? 0 : instr->id());
0N/A
0N/A for (int j = 0; j < num_blocks; j++) {
0N/A BlockBegin* block = block_at(j);
0N/A if (block->live_gen().at(i)) {
0N/A tty->print_cr(" used in block B%d", block->block_id());
0N/A }
0N/A if (block->live_kill().at(i)) {
0N/A tty->print_cr(" defined in block B%d", block->block_id());
0N/A }
0N/A }
304N/A }
0N/A }
0N/A
0N/A#endif
0N/A // when this fails, virtual registers are used before they are defined.
0N/A assert(false, "live_in set of first block must be empty");
304N/A // bailout of if this occurs in product mode.
0N/A bailout("live_in set of first block not empty");
0N/A }
0N/A}
0N/A
0N/A
0N/A// ********** Phase 4: build intervals
0N/A// (fills the list _intervals)
0N/A
0N/Avoid LinearScan::add_use(Value value, int from, int to, IntervalUseKind use_kind) {
1187N/A assert(!value->type()->is_illegal(), "if this value is used by the interpreter it shouldn't be of indeterminate type");
1187N/A LIR_Opr opr = value->operand();
0N/A Constant* con = value->as_Constant();
0N/A
0N/A if ((con == NULL || con->is_pinned()) && opr->is_register()) {
0N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A add_use(opr, from, to, use_kind);
0N/A }
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::add_def(LIR_Opr opr, int def_pos, IntervalUseKind use_kind) {
0N/A TRACE_LINEAR_SCAN(2, tty->print(" def "); opr->print(tty); tty->print_cr(" def_pos %d (%d)", def_pos, use_kind));
0N/A assert(opr->is_register(), "should not be called otherwise");
0N/A
0N/A if (opr->is_virtual_register()) {
0N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A add_def(opr->vreg_number(), def_pos, use_kind, opr->type_register());
0N/A
0N/A } else {
0N/A int reg = reg_num(opr);
0N/A if (is_processed_reg_num(reg)) {
0N/A add_def(reg, def_pos, use_kind, opr->type_register());
0N/A }
0N/A reg = reg_numHi(opr);
0N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
0N/A add_def(reg, def_pos, use_kind, opr->type_register());
304N/A }
0N/A }
0N/A}
304N/A
304N/Avoid LinearScan::add_use(LIR_Opr opr, int from, int to, IntervalUseKind use_kind) {
0N/A TRACE_LINEAR_SCAN(2, tty->print(" use "); opr->print(tty); tty->print_cr(" from %d to %d (%d)", from, to, use_kind));
0N/A assert(opr->is_register(), "should not be called otherwise");
0N/A
0N/A if (opr->is_virtual_register()) {
304N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A add_use(opr->vreg_number(), from, to, use_kind, opr->type_register());
0N/A
0N/A } else {
0N/A int reg = reg_num(opr);
0N/A if (is_processed_reg_num(reg)) {
0N/A add_use(reg, from, to, use_kind, opr->type_register());
0N/A }
0N/A reg = reg_numHi(opr);
0N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
0N/A add_use(reg, from, to, use_kind, opr->type_register());
0N/A }
1187N/A }
0N/A}
0N/A
0N/Avoid LinearScan::add_temp(LIR_Opr opr, int temp_pos, IntervalUseKind use_kind) {
0N/A TRACE_LINEAR_SCAN(2, tty->print(" temp "); opr->print(tty); tty->print_cr(" temp_pos %d (%d)", temp_pos, use_kind));
0N/A assert(opr->is_register(), "should not be called otherwise");
0N/A
0N/A if (opr->is_virtual_register()) {
0N/A assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
0N/A add_temp(opr->vreg_number(), temp_pos, use_kind, opr->type_register());
0N/A
0N/A } else {
0N/A int reg = reg_num(opr);
0N/A if (is_processed_reg_num(reg)) {
0N/A add_temp(reg, temp_pos, use_kind, opr->type_register());
0N/A }
0N/A reg = reg_numHi(opr);
0N/A if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
0N/A add_temp(reg, temp_pos, use_kind, opr->type_register());
0N/A }
0N/A }
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::add_def(int reg_num, int def_pos, IntervalUseKind use_kind, BasicType type) {
0N/A Interval* interval = interval_at(reg_num);
0N/A if (interval != NULL) {
0N/A assert(interval->reg_num() == reg_num, "wrong interval");
0N/A
0N/A if (type != T_ILLEGAL) {
0N/A interval->set_type(type);
0N/A }
0N/A
0N/A Range* r = interval->first();
0N/A if (r->from() <= def_pos) {
0N/A // Update the starting point (when a range is first created for a use, its
0N/A // start is the beginning of the current block until a def is encountered.)
0N/A r->set_from(def_pos);
0N/A interval->add_use_pos(def_pos, use_kind);
0N/A
0N/A } else {
0N/A // Dead value - make vacuous interval
0N/A // also add use_kind for dead intervals
0N/A interval->add_range(def_pos, def_pos + 1);
0N/A interval->add_use_pos(def_pos, use_kind);
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: def of reg %d at %d occurs without use", reg_num, def_pos));
0N/A }
0N/A
0N/A } else {
304N/A // Dead value - make vacuous interval
304N/A // also add use_kind for dead intervals
0N/A interval = create_interval(reg_num);
0N/A if (type != T_ILLEGAL) {
304N/A interval->set_type(type);
0N/A }
0N/A
0N/A interval->add_range(def_pos, def_pos + 1);
304N/A interval->add_use_pos(def_pos, use_kind);
304N/A TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: dead value %d at %d in live intervals", reg_num, def_pos));
0N/A }
304N/A
304N/A change_spill_definition_pos(interval, def_pos);
304N/A if (use_kind == noUse && interval->spill_state() <= startInMemory) {
0N/A // detection of method-parameters and roundfp-results
0N/A // TODO: move this directly to position where use-kind is computed
0N/A interval->set_spill_state(startInMemory);
0N/A }
0N/A}
0N/A
0N/Avoid LinearScan::add_use(int reg_num, int from, int to, IntervalUseKind use_kind, BasicType type) {
0N/A Interval* interval = interval_at(reg_num);
0N/A if (interval == NULL) {
0N/A interval = create_interval(reg_num);
0N/A }
0N/A assert(interval->reg_num() == reg_num, "wrong interval");
0N/A
0N/A if (type != T_ILLEGAL) {
0N/A interval->set_type(type);
0N/A }
0N/A
0N/A interval->add_range(from, to);
0N/A interval->add_use_pos(to, use_kind);
0N/A}
0N/A
0N/Avoid LinearScan::add_temp(int reg_num, int temp_pos, IntervalUseKind use_kind, BasicType type) {
0N/A Interval* interval = interval_at(reg_num);
304N/A if (interval == NULL) {
304N/A interval = create_interval(reg_num);
0N/A }
304N/A assert(interval->reg_num() == reg_num, "wrong interval");
0N/A
304N/A if (type != T_ILLEGAL) {
0N/A interval->set_type(type);
0N/A }
0N/A
0N/A interval->add_range(temp_pos, temp_pos + 1);
0N/A interval->add_use_pos(temp_pos, use_kind);
0N/A}
0N/A
0N/A
0N/A// the results of this functions are used for optimizing spilling and reloading
0N/A// if the functions return shouldHaveRegister and the interval is spilled,
0N/A// it is not reloaded to a register.
0N/AIntervalUseKind LinearScan::use_kind_of_output_operand(LIR_Op* op, LIR_Opr opr) {
0N/A if (op->code() == lir_move) {
0N/A assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
304N/A LIR_Op1* move = (LIR_Op1*)op;
0N/A LIR_Opr res = move->result_opr();
304N/A bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);
304N/A
0N/A if (result_in_memory) {
304N/A // Begin of an interval with must_start_in_memory set.
0N/A // This interval will always get a stack slot first, so return noUse.
0N/A return noUse;
304N/A
0N/A } else if (move->in_opr()->is_stack()) {
0N/A // method argument (condition must be equal to handle_method_arguments)
0N/A return noUse;
0N/A
0N/A } else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
0N/A // Move from register to register
0N/A if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
0N/A // special handling of phi-function moves inside osr-entry blocks
0N/A // input operand must have a register instead of output operand (leads to better register allocation)
0N/A return shouldHaveRegister;
0N/A }
0N/A }
0N/A }
0N/A
0N/A if (opr->is_virtual() &&
0N/A gen()->is_vreg_flag_set(opr->vreg_number(), LIRGenerator::must_start_in_memory)) {
0N/A // result is a stack-slot, so prevent immediate reloading
304N/A return noUse;
0N/A }
0N/A
0N/A // all other operands require a register
0N/A return mustHaveRegister;
0N/A}
0N/A
0N/AIntervalUseKind LinearScan::use_kind_of_input_operand(LIR_Op* op, LIR_Opr opr) {
0N/A if (op->code() == lir_move) {
0N/A assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
0N/A LIR_Op1* move = (LIR_Op1*)op;
0N/A LIR_Opr res = move->result_opr();
0N/A bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);
0N/A
0N/A if (result_in_memory) {
0N/A // Move to an interval with must_start_in_memory set.
0N/A // To avoid moves from stack to stack (not allowed) force the input operand to a register
304N/A return mustHaveRegister;
304N/A
304N/A } else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
304N/A // Move from register to register
0N/A if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
0N/A // special handling of phi-function moves inside osr-entry blocks
0N/A // input operand must have a register instead of output operand (leads to better register allocation)
0N/A return mustHaveRegister;
0N/A }
0N/A
0N/A // The input operand is not forced to a register (moves from stack to register are allowed),
0N/A // but it is faster if the input operand is in a register
0N/A return shouldHaveRegister;
0N/A }
0N/A }
0N/A
0N/A
0N/A#ifdef X86
0N/A if (op->code() == lir_cmove) {
0N/A // conditional moves can handle stack operands
0N/A assert(op->result_opr()->is_register(), "result must always be in a register");
0N/A return shouldHaveRegister;
0N/A }
0N/A
304N/A // optimizations for second input operand of arithmehtic operations on Intel
304N/A // this operand is allowed to be on the stack in some cases
304N/A BasicType opr_type = opr->type_register();
304N/A if (opr_type == T_FLOAT || opr_type == T_DOUBLE) {
0N/A if ((UseSSE == 1 && opr_type == T_FLOAT) || UseSSE >= 2) {
0N/A // SSE float instruction (T_DOUBLE only supported with SSE2)
0N/A switch (op->code()) {
0N/A case lir_cmp:
0N/A case lir_add:
0N/A case lir_sub:
0N/A case lir_mul:
0N/A case lir_div:
0N/A {
0N/A assert(op->as_Op2() != NULL, "must be LIR_Op2");
0N/A LIR_Op2* op2 = (LIR_Op2*)op;
0N/A if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
0N/A 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");
0N/A return shouldHaveRegister;
0N/A }
0N/A }
0N/A }
0N/A } else {
0N/A // FPU stack float instruction
0N/A switch (op->code()) {
304N/A case lir_add:
304N/A case lir_sub:
0N/A case lir_mul:
0N/A case lir_div:
304N/A {
0N/A assert(op->as_Op2() != NULL, "must be LIR_Op2");
0N/A LIR_Op2* op2 = (LIR_Op2*)op;
0N/A if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
0N/A 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");
0N/A return shouldHaveRegister;
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A } else if (opr_type != T_LONG) {
0N/A // integer instruction (note: long operands must always be in register)
0N/A switch (op->code()) {
0N/A case lir_cmp:
0N/A case lir_add:
304N/A case lir_sub:
304N/A case lir_logic_and:
0N/A case lir_logic_or:
0N/A case lir_logic_xor:
0N/A {
304N/A assert(op->as_Op2() != NULL, "must be LIR_Op2");
0N/A LIR_Op2* op2 = (LIR_Op2*)op;
0N/A if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
0N/A 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");
0N/A return shouldHaveRegister;
3158N/A }
3158N/A }
3158N/A }
3158N/A }
3158N/A#endif // X86
3158N/A
3158N/A // all other operands require a register
3158N/A return mustHaveRegister;
3158N/A}
3158N/A
3158N/A
3158N/Avoid LinearScan::handle_method_arguments(LIR_Op* op) {
3158N/A // special handling for method arguments (moves from stack to virtual register):
3158N/A // the interval gets no register assigned, but the stack slot.
3158N/A // it is split before the first use by the register allocator.
3158N/A
3158N/A if (op->code() == lir_move) {
3158N/A assert(op->as_Op1() != NULL, "must be LIR_Op1");
3158N/A LIR_Op1* move = (LIR_Op1*)op;
3158N/A
3158N/A if (move->in_opr()->is_stack()) {
3158N/A#ifdef ASSERT
3158N/A int arg_size = compilation()->method()->arg_size();
3158N/A LIR_Opr o = move->in_opr();
3158N/A if (o->is_single_stack()) {
3158N/A assert(o->single_stack_ix() >= 0 && o->single_stack_ix() < arg_size, "out of range");
3158N/A } else if (o->is_double_stack()) {
3158N/A assert(o->double_stack_ix() >= 0 && o->double_stack_ix() < arg_size, "out of range");
3158N/A } else {
3158N/A ShouldNotReachHere();
3158N/A }
3158N/A
3158N/A assert(move->id() > 0, "invalid id");
3158N/A assert(block_of_op_with_id(move->id())->number_of_preds() == 0, "move from stack must be in first block");
3158N/A assert(move->result_opr()->is_virtual(), "result of move must be a virtual register");
3158N/A
3158N/A 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())));
3158N/A#endif
3158N/A
3158N/A Interval* interval = interval_at(reg_num(move->result_opr()));
3158N/A
3158N/A int stack_slot = LinearScan::nof_regs + (move->in_opr()->is_single_stack() ? move->in_opr()->single_stack_ix() : move->in_opr()->double_stack_ix());
3158N/A interval->set_canonical_spill_slot(stack_slot);
3158N/A interval->assign_reg(stack_slot);
3158N/A }
3158N/A }
3158N/A}
3158N/A
3158N/Avoid LinearScan::handle_doubleword_moves(LIR_Op* op) {
3158N/A // special handling for doubleword move from memory to register:
3158N/A // in this case the registers of the input address and the result
3158N/A // registers must not overlap -> add a temp range for the input registers
3158N/A if (op->code() == lir_move) {
3158N/A assert(op->as_Op1() != NULL, "must be LIR_Op1");
3158N/A LIR_Op1* move = (LIR_Op1*)op;
3158N/A
3158N/A if (move->result_opr()->is_double_cpu() && move->in_opr()->is_pointer()) {
3158N/A LIR_Address* address = move->in_opr()->as_address_ptr();
3158N/A if (address != NULL) {
3158N/A if (address->base()->is_valid()) {
3158N/A add_temp(address->base(), op->id(), noUse);
3158N/A }
3158N/A if (address->index()->is_valid()) {
3158N/A add_temp(address->index(), op->id(), noUse);
3158N/A }
3158N/A }
3158N/A }
3158N/A }
3158N/A}
3158N/A
3158N/Avoid LinearScan::add_register_hints(LIR_Op* op) {
3158N/A switch (op->code()) {
3158N/A case lir_move: // fall through
3158N/A case lir_convert: {
3158N/A assert(op->as_Op1() != NULL, "lir_move, lir_convert must be LIR_Op1");
3158N/A LIR_Op1* move = (LIR_Op1*)op;
3158N/A
3158N/A LIR_Opr move_from = move->in_opr();
3158N/A LIR_Opr move_to = move->result_opr();
3158N/A
3158N/A if (move_to->is_register() && move_from->is_register()) {
3158N/A Interval* from = interval_at(reg_num(move_from));
3158N/A Interval* to = interval_at(reg_num(move_to));
3158N/A if (from != NULL && to != NULL) {
3158N/A to->set_register_hint(from);
3158N/A 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()));
3158N/A }
3158N/A }
3158N/A break;
3158N/A }
3158N/A case lir_cmove: {
3158N/A assert(op->as_Op2() != NULL, "lir_cmove must be LIR_Op2");
3158N/A LIR_Op2* cmove = (LIR_Op2*)op;
3158N/A
3158N/A LIR_Opr move_from = cmove->in_opr1();
3158N/A LIR_Opr move_to = cmove->result_opr();
3158N/A
3158N/A if (move_to->is_register() && move_from->is_register()) {
3158N/A Interval* from = interval_at(reg_num(move_from));
3158N/A Interval* to = interval_at(reg_num(move_to));
3158N/A if (from != NULL && to != NULL) {
3158N/A to->set_register_hint(from);
3158N/A 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()));
3158N/A }
3158N/A }
3158N/A break;
3158N/A }
3158N/A }
3158N/A}
3158N/A
3158N/A
3158N/Avoid LinearScan::build_intervals() {
3158N/A TIME_LINEAR_SCAN(timer_build_intervals);
3158N/A
3158N/A // initialize interval list with expected number of intervals
3158N/A // (32 is added to have some space for split children without having to resize the list)
3158N/A _intervals = IntervalList(num_virtual_regs() + 32);
3158N/A // initialize all slots that are used by build_intervals
3158N/A _intervals.at_put_grow(num_virtual_regs() - 1, NULL, NULL);
3158N/A
3158N/A // create a list with all caller-save registers (cpu, fpu, xmm)
3158N/A // when an instruction is a call, a temp range is created for all these registers
3158N/A int num_caller_save_registers = 0;
3158N/A int caller_save_registers[LinearScan::nof_regs];
3158N/A
3158N/A int i;
3158N/A for (i = 0; i < FrameMap::nof_caller_save_cpu_regs(); i++) {
3158N/A LIR_Opr opr = FrameMap::caller_save_cpu_reg_at(i);
3158N/A assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
3158N/A assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
3158N/A caller_save_registers[num_caller_save_registers++] = reg_num(opr);
3158N/A }
3158N/A
3158N/A // temp ranges for fpu registers are only created when the method has
3158N/A // virtual fpu operands. Otherwise no allocation for fpu registers is
3158N/A // perfomed and so the temp ranges would be useless
3158N/A if (has_fpu_registers()) {
3158N/A#ifdef X86
3158N/A if (UseSSE < 2) {
3158N/A#endif
3158N/A for (i = 0; i < FrameMap::nof_caller_save_fpu_regs; i++) {
3158N/A LIR_Opr opr = FrameMap::caller_save_fpu_reg_at(i);
3158N/A assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
3158N/A assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
3158N/A caller_save_registers[num_caller_save_registers++] = reg_num(opr);
3158N/A }
3158N/A#ifdef X86
3158N/A }
3158N/A if (UseSSE > 0) {
3158N/A for (i = 0; i < FrameMap::nof_caller_save_xmm_regs; i++) {
3158N/A LIR_Opr opr = FrameMap::caller_save_xmm_reg_at(i);
3158N/A assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
3158N/A assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
3158N/A caller_save_registers[num_caller_save_registers++] = reg_num(opr);
3158N/A }
3158N/A }
3158N/A#endif
3158N/A }
3158N/A assert(num_caller_save_registers <= LinearScan::nof_regs, "out of bounds");
3158N/A
3158N/A
3158N/A LIR_OpVisitState visitor;
3158N/A
3158N/A // iterate all blocks in reverse order
3158N/A for (i = block_count() - 1; i >= 0; i--) {
3158N/A BlockBegin* block = block_at(i);
3158N/A LIR_OpList* instructions = block->lir()->instructions_list();
3158N/A int block_from = block->first_lir_instruction_id();
3158N/A int block_to = block->last_lir_instruction_id();
3158N/A
3158N/A assert(block_from == instructions->at(0)->id(), "must be");
3158N/A assert(block_to == instructions->at(instructions->length() - 1)->id(), "must be");
3158N/A
3158N/A // Update intervals for registers live at the end of this block;
3158N/A BitMap live = block->live_out();
3158N/A int size = (int)live.size();
3158N/A for (int number = (int)live.get_next_one_offset(0, size); number < size; number = (int)live.get_next_one_offset(number + 1, size)) {
3158N/A assert(live.at(number), "should not stop here otherwise");
3158N/A assert(number >= LIR_OprDesc::vreg_base, "fixed intervals must not be live on block bounds");
3158N/A TRACE_LINEAR_SCAN(2, tty->print_cr("live in %d to %d", number, block_to + 2));
3158N/A
3158N/A add_use(number, block_from, block_to + 2, noUse, T_ILLEGAL);
3158N/A
3158N/A // add special use positions for loop-end blocks when the
3158N/A // interval is used anywhere inside this loop. It's possible
3158N/A // that the block was part of a non-natural loop, so it might
3158N/A // have an invalid loop index.
3158N/A if (block->is_set(BlockBegin::linear_scan_loop_end_flag) &&
3158N/A block->loop_index() != -1 &&
3158N/A is_interval_in_loop(number, block->loop_index())) {
3158N/A interval_at(number)->add_use_pos(block_to + 1, loopEndMarker);
3158N/A }
3158N/A }
3158N/A
3158N/A // iterate all instructions of the block in reverse order.
3158N/A // skip the first instruction because it is always a label
3158N/A // definitions of intervals are processed before uses
3158N/A assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
3158N/A for (int j = instructions->length() - 1; j >= 1; j--) {
3158N/A LIR_Op* op = instructions->at(j);
3158N/A int op_id = op->id();
3158N/A
3932N/A // visit operation to collect all operands
4010N/A visitor.visit(op);
3932N/A
3932N/A // add a temp range for each register if operation destroys caller-save registers
3932N/A if (visitor.has_call()) {
3932N/A for (int k = 0; k < num_caller_save_registers; k++) {
4010N/A add_temp(caller_save_registers[k], op_id, noUse, T_ILLEGAL);
3932N/A }
3932N/A TRACE_LINEAR_SCAN(4, tty->print_cr("operation destroys all caller-save registers"));
3932N/A }
3932N/A
3932N/A // Add any platform dependent temps
3932N/A pd_add_temps(op);
3932N/A
3932N/A // visit definitions (output and temp operands)
3932N/A int k, n;
3932N/A n = visitor.opr_count(LIR_OpVisitState::outputMode);
3932N/A for (k = 0; k < n; k++) {
3932N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::outputMode, k);
3932N/A assert(opr->is_register(), "visitor should only return register operands");
3932N/A add_def(opr, op_id, use_kind_of_output_operand(op, opr));
3932N/A }
3932N/A
4010N/A n = visitor.opr_count(LIR_OpVisitState::tempMode);
3932N/A for (k = 0; k < n; k++) {
3932N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
4010N/A assert(opr->is_register(), "visitor should only return register operands");
4010N/A add_temp(opr, op_id, mustHaveRegister);
3932N/A }
3932N/A
3932N/A // visit uses (input operands)
3932N/A n = visitor.opr_count(LIR_OpVisitState::inputMode);
3932N/A for (k = 0; k < n; k++) {
3932N/A LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
4010N/A assert(opr->is_register(), "visitor should only return register operands");
3932N/A add_use(opr, block_from, op_id, use_kind_of_input_operand(op, opr));
4010N/A }
3932N/A
3932N/A // Add uses of live locals from interpreter's point of view for proper
4010N/A // debug information generation
3932N/A // Treat these operands as temp values (if the life range is extended
3932N/A // to a call site, the value would be in a register at the call otherwise)
4010N/A n = visitor.info_count();
3932N/A for (k = 0; k < n; k++) {
3932N/A CodeEmitInfo* info = visitor.info_at(k);
3932N/A ValueStack* stack = info->stack();
3932N/A for_each_state_value(stack, value,
4010N/A add_use(value, block_from, op_id + 1, noUse);
3932N/A );
3932N/A }
3932N/A
3932N/A // special steps for some instructions (especially moves)
3932N/A handle_method_arguments(op);
3932N/A handle_doubleword_moves(op);
3932N/A add_register_hints(op);
3932N/A
3932N/A } // end of instruction iteration
3932N/A } // end of block iteration
3932N/A
4010N/A
3932N/A // add the range [0, 1[ to all fixed intervals
3932N/A // -> the register allocator need not handle unhandled fixed intervals
3932N/A for (int n = 0; n < LinearScan::nof_regs; n++) {
3932N/A Interval* interval = interval_at(n);
3932N/A if (interval != NULL) {
3932N/A interval->add_range(0, 1);
3932N/A }
4010N/A }
3932N/A}
3932N/A
3932N/A
3932N/A// ********** Phase 5: actual register allocation
3932N/A
3932N/Aint LinearScan::interval_cmp(Interval** a, Interval** b) {
3932N/A if (*a != NULL) {
3932N/A if (*b != NULL) {
3932N/A return (*a)->from() - (*b)->from();
4010N/A } else {
3932N/A return -1;
3932N/A }
3158N/A } else {
0N/A if (*b != NULL) {
0N/A return 1;
0N/A } else {
0N/A return 0;
0N/A }
0N/A }
3158N/A}
3158N/A
3158N/A#ifndef PRODUCT
3158N/Abool LinearScan::is_sorted(IntervalArray* intervals) {
3158N/A int from = -1;
3158N/A int i, j;
3158N/A for (i = 0; i < intervals->length(); i ++) {
3158N/A Interval* it = intervals->at(i);
3158N/A if (it != NULL) {
3158N/A if (from > it->from()) {
3158N/A assert(false, "");
3158N/A return false;
3158N/A }
3158N/A from = it->from();
3158N/A }
3158N/A }
3158N/A
3158N/A // check in both directions if sorted list and unsorted list contain same intervals
3158N/A for (i = 0; i < interval_count(); i++) {
3158N/A if (interval_at(i) != NULL) {
3158N/A int num_found = 0;
3158N/A for (j = 0; j < intervals->length(); j++) {
3158N/A if (interval_at(i) == intervals->at(j)) {
3932N/A num_found++;
0N/A }
2252N/A }
3932N/A assert(num_found == 1, "lists do not contain same intervals");
3932N/A }
0N/A }
3932N/A for (j = 0; j < intervals->length(); j++) {
3932N/A int num_found = 0;
3932N/A for (i = 0; i < interval_count(); i++) {
3932N/A if (interval_at(i) == intervals->at(j)) {
3932N/A num_found++;
4010N/A }
3932N/A }
3932N/A assert(num_found == 1, "lists do not contain same intervals");
3932N/A }
3932N/A
3932N/A return true;
3932N/A}
3932N/A#endif
3932N/A
3932N/Avoid LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
3932N/A if (*prev != NULL) {
3932N/A (*prev)->set_next(interval);
3932N/A } else {
3932N/A *first = interval;
3932N/A }
3932N/A *prev = interval;
3158N/A}
3158N/A
3158N/Avoid LinearScan::create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)) {
3158N/A assert(is_sorted(_sorted_intervals), "interval list is not sorted");
3158N/A
3158N/A *list1 = *list2 = Interval::end();
3158N/A
0N/A Interval* list1_prev = NULL;
0N/A Interval* list2_prev = NULL;
0N/A Interval* v;
0N/A
0N/A const int n = _sorted_intervals->length();
0N/A for (int i = 0; i < n; i++) {
0N/A v = _sorted_intervals->at(i);
0N/A if (v == NULL) continue;
0N/A
0N/A if (is_list1(v)) {
4010N/A add_to_list(list1, &list1_prev, v);
3158N/A } else if (is_list2 == NULL || is_list2(v)) {
3158N/A add_to_list(list2, &list2_prev, v);
3158N/A }
3158N/A }
3158N/A
3158N/A if (list1_prev != NULL) list1_prev->set_next(Interval::end());
3158N/A if (list2_prev != NULL) list2_prev->set_next(Interval::end());
3158N/A
3158N/A assert(list1_prev == NULL || list1_prev->next() == Interval::end(), "linear list ends not with sentinel");
3158N/A assert(list2_prev == NULL || list2_prev->next() == Interval::end(), "linear list ends not with sentinel");
3158N/A}
3158N/A
0N/A
0N/Avoid LinearScan::sort_intervals_before_allocation() {
0N/A TIME_LINEAR_SCAN(timer_sort_intervals_before);
3158N/A
3158N/A if (_needs_full_resort) {
0N/A // There is no known reason why this should occur but just in case...
0N/A assert(false, "should never occur");
3158N/A // Re-sort existing interval list because an Interval::from() has changed
3158N/A _sorted_intervals->sort(interval_cmp);
3158N/A _needs_full_resort = false;
3158N/A }
3158N/A
3158N/A IntervalList* unsorted_list = &_intervals;
3158N/A int unsorted_len = unsorted_list->length();
3158N/A int sorted_len = 0;
3158N/A int unsorted_idx;
3158N/A int sorted_idx = 0;
3158N/A int sorted_from_max = -1;
3158N/A
3158N/A // calc number of items for sorted list (sorted list must not contain NULL values)
3158N/A for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
3158N/A if (unsorted_list->at(unsorted_idx) != NULL) {
3158N/A sorted_len++;
3158N/A }
3158N/A }
3158N/A IntervalArray* sorted_list = new IntervalArray(sorted_len);
3158N/A
3158N/A // special sorting algorithm: the original interval-list is almost sorted,
3158N/A // only some intervals are swapped. So this is much faster than a complete QuickSort
3158N/A for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
3158N/A Interval* cur_interval = unsorted_list->at(unsorted_idx);
3158N/A
3158N/A if (cur_interval != NULL) {
3158N/A int cur_from = cur_interval->from();
3158N/A
3158N/A if (sorted_from_max <= cur_from) {
3158N/A sorted_list->at_put(sorted_idx++, cur_interval);
3158N/A sorted_from_max = cur_interval->from();
3158N/A } else {
3158N/A // the asumption that the intervals are already sorted failed,
3158N/A // so this interval must be sorted in manually
3158N/A int j;
3158N/A for (j = sorted_idx - 1; j >= 0 && cur_from < sorted_list->at(j)->from(); j--) {
3158N/A sorted_list->at_put(j + 1, sorted_list->at(j));
3158N/A }
3158N/A sorted_list->at_put(j + 1, cur_interval);
3158N/A sorted_idx++;
3158N/A }
3158N/A }
3158N/A }
0N/A _sorted_intervals = sorted_list;
0N/A assert(is_sorted(_sorted_intervals), "intervals unsorted");
0N/A}
3158N/A
0N/Avoid LinearScan::sort_intervals_after_allocation() {
0N/A TIME_LINEAR_SCAN(timer_sort_intervals_after);
0N/A
0N/A if (_needs_full_resort) {
0N/A // Re-sort existing interval list because an Interval::from() has changed
0N/A _sorted_intervals->sort(interval_cmp);
0N/A _needs_full_resort = false;
0N/A }
0N/A
0N/A IntervalArray* old_list = _sorted_intervals;
0N/A IntervalList* new_list = _new_intervals_from_allocation;
0N/A int old_len = old_list->length();
3158N/A int new_len = new_list->length();
3158N/A
3158N/A if (new_len == 0) {
3158N/A // no intervals have been added during allocation, so sorted list is already up to date
3158N/A assert(is_sorted(_sorted_intervals), "intervals unsorted");
3158N/A return;
3158N/A }
3158N/A
3158N/A // conventional sort-algorithm for new intervals
3158N/A new_list->sort(interval_cmp);
3932N/A
3158N/A // merge old and new list (both already sorted) into one combined list
3158N/A IntervalArray* combined_list = new IntervalArray(old_len + new_len);
3158N/A int old_idx = 0;
3158N/A int new_idx = 0;
3158N/A
3158N/A while (old_idx + new_idx < old_len + new_len) {
3158N/A if (new_idx >= new_len || (old_idx < old_len && old_list->at(old_idx)->from() <= new_list->at(new_idx)->from())) {
3158N/A combined_list->at_put(old_idx + new_idx, old_list->at(old_idx));
3158N/A old_idx++;
3158N/A } else {
3158N/A combined_list->at_put(old_idx + new_idx, new_list->at(new_idx));
3158N/A new_idx++;
3158N/A }
3158N/A }
3158N/A
3158N/A _sorted_intervals = combined_list;
3158N/A assert(is_sorted(_sorted_intervals), "intervals unsorted");
3158N/A}
3158N/A
3158N/A
3158N/Avoid LinearScan::allocate_registers() {
3158N/A TIME_LINEAR_SCAN(timer_allocate_registers);
3158N/A
3158N/A Interval* precolored_cpu_intervals, *not_precolored_cpu_intervals;
0N/A Interval* precolored_fpu_intervals, *not_precolored_fpu_intervals;
0N/A
3158N/A create_unhandled_lists(&precolored_cpu_intervals, &not_precolored_cpu_intervals, is_precolored_cpu_interval, is_virtual_cpu_interval);
0N/A if (has_fpu_registers()) {
0N/A create_unhandled_lists(&precolored_fpu_intervals, &not_precolored_fpu_intervals, is_precolored_fpu_interval, is_virtual_fpu_interval);
0N/A#ifdef ASSERT
0N/A } else {
0N/A // fpu register allocation is omitted because no virtual fpu registers are present
0N/A // just check this again...
0N/A create_unhandled_lists(&precolored_fpu_intervals, &not_precolored_fpu_intervals, is_precolored_fpu_interval, is_virtual_fpu_interval);
0N/A assert(not_precolored_fpu_intervals == Interval::end(), "missed an uncolored fpu interval");
0N/A#endif
0N/A }
0N/A
0N/A // allocate cpu registers
0N/A LinearScanWalker cpu_lsw(this, precolored_cpu_intervals, not_precolored_cpu_intervals);
0N/A cpu_lsw.walk();
0N/A cpu_lsw.finish_allocation();
0N/A
0N/A if (has_fpu_registers()) {
0N/A // allocate fpu registers
0N/A LinearScanWalker fpu_lsw(this, precolored_fpu_intervals, not_precolored_fpu_intervals);
0N/A fpu_lsw.walk();
0N/A fpu_lsw.finish_allocation();
0N/A }
0N/A}
0N/A
0N/A
0N/A// ********** Phase 6: resolve data flow
0N/A// (insert moves at edges between blocks if intervals have been split)
0N/A
0N/A// wrapper for Interval::split_child_at_op_id that performs a bailout in product mode
0N/A// instead of returning NULL
0N/AInterval* LinearScan::split_child_at_op_id(Interval* interval, int op_id, LIR_OpVisitState::OprMode mode) {
0N/A Interval* result = interval->split_child_at_op_id(op_id, mode);
0N/A if (result != NULL) {
0N/A return result;
0N/A }
0N/A
0N/A assert(false, "must find an interval, but do a clean bailout in product mode");
0N/A result = new Interval(LIR_OprDesc::vreg_base);
0N/A result->assign_reg(0);
0N/A result->set_type(T_INT);
0N/A BAILOUT_("LinearScan: interval is NULL", result);
0N/A}
0N/A
0N/A
0N/AInterval* LinearScan::interval_at_block_begin(BlockBegin* block, int reg_num) {
0N/A assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
0N/A assert(interval_at(reg_num) != NULL, "no interval found");
0N/A
0N/A return split_child_at_op_id(interval_at(reg_num), block->first_lir_instruction_id(), LIR_OpVisitState::outputMode);
0N/A}
0N/A
0N/AInterval* LinearScan::interval_at_block_end(BlockBegin* block, int reg_num) {
0N/A assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
0N/A assert(interval_at(reg_num) != NULL, "no interval found");
0N/A
0N/A return split_child_at_op_id(interval_at(reg_num), block->last_lir_instruction_id() + 1, LIR_OpVisitState::outputMode);
0N/A}
524N/A
0N/AInterval* LinearScan::interval_at_op_id(int reg_num, int op_id) {
0N/A assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
0N/A assert(interval_at(reg_num) != NULL, "no interval found");
0N/A
0N/A return split_child_at_op_id(interval_at(reg_num), op_id, LIR_OpVisitState::inputMode);
0N/A}
0N/A
0N/A
3158N/Avoid LinearScan::resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
0N/A DEBUG_ONLY(move_resolver.check_empty());
0N/A
0N/A const int num_regs = num_virtual_regs();
0N/A const int size = live_set_size();
0N/A const BitMap live_at_edge = to_block->live_in();
0N/A
0N/A // visit all registers where the live_at_edge bit is set
0N/A 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)) {
0N/A assert(r < num_regs, "live information set for not exisiting interval");
304N/A assert(from_block->live_out().at(r) && to_block->live_in().at(r), "interval not live at this edge");
0N/A
0N/A Interval* from_interval = interval_at_block_end(from_block, r);
0N/A Interval* to_interval = interval_at_block_begin(to_block, r);
0N/A
0N/A if (from_interval != to_interval && (from_interval->assigned_reg() != to_interval->assigned_reg() || from_interval->assigned_regHi() != to_interval->assigned_regHi())) {
0N/A // need to insert move instruction
0N/A move_resolver.add_mapping(from_interval, to_interval);
0N/A }
0N/A }
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::resolve_find_insert_pos(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
0N/A if (from_block->number_of_sux() <= 1) {
0N/A TRACE_LINEAR_SCAN(4, tty->print_cr("inserting moves at end of from_block B%d", from_block->block_id()));
0N/A
0N/A LIR_OpList* instructions = from_block->lir()->instructions_list();
0N/A LIR_OpBranch* branch = instructions->last()->as_OpBranch();
0N/A if (branch != NULL) {
0N/A // insert moves before branch
0N/A assert(branch->cond() == lir_cond_always, "block does not end with an unconditional jump");
0N/A move_resolver.set_insert_position(from_block->lir(), instructions->length() - 2);
304N/A } else {
0N/A move_resolver.set_insert_position(from_block->lir(), instructions->length() - 1);
0N/A }
304N/A
0N/A } else {
0N/A TRACE_LINEAR_SCAN(4, tty->print_cr("inserting moves at beginning of to_block B%d", to_block->block_id()));
0N/A#ifdef ASSERT
0N/A assert(from_block->lir()->instructions_list()->at(0)->as_OpLabel() != NULL, "block does not start with a label");
304N/A
0N/A // because the number of predecessor edges matches the number of
0N/A // successor edges, blocks which are reached by switch statements
0N/A // may have be more than one predecessor but it will be guaranteed
0N/A // that all predecessors will be the same.
304N/A for (int i = 0; i < to_block->number_of_preds(); i++) {
0N/A assert(from_block == to_block->pred_at(i), "all critical edges must be broken");
0N/A }
304N/A#endif
0N/A
0N/A move_resolver.set_insert_position(to_block->lir(), 0);
0N/A }
0N/A}
0N/A
0N/A
0N/A// insert necessary moves (spilling or reloading) at edges between blocks if interval has been split
0N/Avoid LinearScan::resolve_data_flow() {
0N/A TIME_LINEAR_SCAN(timer_resolve_data_flow);
0N/A
0N/A int num_blocks = block_count();
0N/A MoveResolver move_resolver(this);
0N/A BitMap block_completed(num_blocks); block_completed.clear();
0N/A BitMap already_resolved(num_blocks); already_resolved.clear();
0N/A
0N/A int i;
0N/A for (i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A
0N/A // check if block has only one predecessor and only one successor
3158N/A if (block->number_of_preds() == 1 && block->number_of_sux() == 1 && block->number_of_exception_handlers() == 0) {
304N/A LIR_OpList* instructions = block->lir()->instructions_list();
0N/A assert(instructions->at(0)->code() == lir_label, "block must start with label");
3158N/A assert(instructions->last()->code() == lir_branch, "block with successors must end with branch");
0N/A assert(instructions->last()->as_OpBranch()->cond() == lir_cond_always, "block with successor must end with unconditional branch");
0N/A
0N/A // check if block is empty (only label and branch)
0N/A if (instructions->length() == 2) {
0N/A BlockBegin* pred = block->pred_at(0);
0N/A BlockBegin* sux = block->sux_at(0);
0N/A
0N/A // prevent optimization of two consecutive blocks
0N/A if (!block_completed.at(pred->linear_scan_number()) && !block_completed.at(sux->linear_scan_number())) {
0N/A 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()));
0N/A block_completed.set_bit(block->linear_scan_number());
0N/A
0N/A // directly resolve between pred and sux (without looking at the empty block between)
0N/A resolve_collect_mappings(pred, sux, move_resolver);
0N/A if (move_resolver.has_mappings()) {
0N/A move_resolver.set_insert_position(block->lir(), 0);
0N/A move_resolver.resolve_and_append_moves();
0N/A }
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A
0N/A for (i = 0; i < num_blocks; i++) {
0N/A if (!block_completed.at(i)) {
0N/A BlockBegin* from_block = block_at(i);
0N/A already_resolved.set_from(block_completed);
0N/A
0N/A int num_sux = from_block->number_of_sux();
0N/A for (int s = 0; s < num_sux; s++) {
0N/A BlockBegin* to_block = from_block->sux_at(s);
0N/A
0N/A // check for duplicate edges between the same blocks (can happen with switch blocks)
3158N/A if (!already_resolved.at(to_block->linear_scan_number())) {
3158N/A TRACE_LINEAR_SCAN(3, tty->print_cr("**** processing edge between B%d and B%d", from_block->block_id(), to_block->block_id()));
3158N/A already_resolved.set_bit(to_block->linear_scan_number());
3158N/A
0N/A // collect all intervals that have been split between from_block and to_block
0N/A resolve_collect_mappings(from_block, to_block, move_resolver);
0N/A if (move_resolver.has_mappings()) {
0N/A resolve_find_insert_pos(from_block, to_block, move_resolver);
0N/A move_resolver.resolve_and_append_moves();
0N/A }
0N/A }
0N/A }
0N/A }
0N/A }
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::resolve_exception_entry(BlockBegin* block, int reg_num, MoveResolver &move_resolver) {
0N/A if (interval_at(reg_num) == NULL) {
0N/A // if a phi function is never used, no interval is created -> ignore this
0N/A return;
0N/A }
0N/A
0N/A Interval* interval = interval_at_block_begin(block, reg_num);
0N/A int reg = interval->assigned_reg();
3158N/A int regHi = interval->assigned_regHi();
0N/A
0N/A if ((reg < nof_regs && interval->always_in_memory()) ||
0N/A (use_fpu_stack_allocation() && reg >= pd_first_fpu_reg && reg <= pd_last_fpu_reg)) {
0N/A // the interval is split to get a short range that is located on the stack
0N/A // in the following two cases:
0N/A // * the interval started in memory (e.g. method parameter), but is currently in a register
0N/A // this is an optimization for exception handling that reduces the number of moves that
0N/A // are necessary for resolving the states when an exception uses this exception handler
0N/A // * the interval would be on the fpu stack at the begin of the exception handler
0N/A // this is not allowed because of the complicated fpu stack handling on Intel
0N/A
0N/A // range that will be spilled to memory
0N/A int from_op_id = block->first_lir_instruction_id();
0N/A int to_op_id = from_op_id + 1; // short live range of length 1
0N/A assert(interval->from() <= from_op_id && interval->to() >= to_op_id,
0N/A "no split allowed between exception entry and first instruction");
0N/A
0N/A if (interval->from() != from_op_id) {
0N/A // the part before from_op_id is unchanged
3158N/A interval = interval->split(from_op_id);
0N/A interval->assign_reg(reg, regHi);
0N/A append_interval(interval);
3158N/A } else {
3158N/A _needs_full_resort = true;
3158N/A }
3158N/A assert(interval->from() == from_op_id, "must be true now");
3158N/A
0N/A Interval* spilled_part = interval;
3158N/A if (interval->to() != to_op_id) {
0N/A // the part after to_op_id is unchanged
0N/A spilled_part = interval->split_from_start(to_op_id);
0N/A append_interval(spilled_part);
0N/A move_resolver.add_mapping(spilled_part, interval);
0N/A }
0N/A assign_spill_slot(spilled_part);
0N/A
0N/A assert(spilled_part->from() == from_op_id && spilled_part->to() == to_op_id, "just checking");
0N/A }
0N/A}
0N/A
0N/Avoid LinearScan::resolve_exception_entry(BlockBegin* block, MoveResolver &move_resolver) {
0N/A assert(block->is_set(BlockBegin::exception_entry_flag), "should not call otherwise");
0N/A DEBUG_ONLY(move_resolver.check_empty());
0N/A
0N/A // visit all registers where the live_in bit is set
0N/A int size = live_set_size();
0N/A 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)) {
0N/A resolve_exception_entry(block, r, move_resolver);
0N/A }
0N/A
0N/A // the live_in bits are not set for phi functions of the xhandler entry, so iterate them separately
0N/A for_each_phi_fun(block, phi,
0N/A resolve_exception_entry(block, phi->operand()->vreg_number(), move_resolver)
0N/A );
0N/A
0N/A if (move_resolver.has_mappings()) {
0N/A // insert moves after first instruction
0N/A move_resolver.set_insert_position(block->lir(), 1);
0N/A move_resolver.resolve_and_append_moves();
0N/A }
3158N/A}
0N/A
0N/A
0N/Avoid LinearScan::resolve_exception_edge(XHandler* handler, int throwing_op_id, int reg_num, Phi* phi, MoveResolver &move_resolver) {
0N/A if (interval_at(reg_num) == NULL) {
0N/A // if a phi function is never used, no interval is created -> ignore this
304N/A return;
0N/A }
0N/A
0N/A // the computation of to_interval is equal to resolve_collect_mappings,
304N/A // but from_interval is more complicated because of phi functions
0N/A BlockBegin* to_block = handler->entry_block();
304N/A Interval* to_interval = interval_at_block_begin(to_block, reg_num);
0N/A
0N/A if (phi != NULL) {
0N/A // phi function of the exception entry block
0N/A // no moves are created for this phi function in the LIR_Generator, so the
0N/A // interval at the throwing instruction must be searched using the operands
0N/A // of the phi function
0N/A Value from_value = phi->operand_at(handler->phi_operand());
0N/A
0N/A // with phi functions it can happen that the same from_value is used in
0N/A // multiple mappings, so notify move-resolver that this is allowed
0N/A move_resolver.set_multiple_reads_allowed();
0N/A
0N/A Constant* con = from_value->as_Constant();
0N/A if (con != NULL && !con->is_pinned()) {
0N/A // unpinned constants may have no register, so add mapping from constant to interval
0N/A move_resolver.add_mapping(LIR_OprFact::value_type(con->type()), to_interval);
0N/A } else {
0N/A // search split child at the throwing op_id
0N/A Interval* from_interval = interval_at_op_id(from_value->operand()->vreg_number(), throwing_op_id);
0N/A move_resolver.add_mapping(from_interval, to_interval);
0N/A }
0N/A
0N/A } else {
0N/A // no phi function, so use reg_num also for from_interval
610N/A // search split child at the throwing op_id
610N/A Interval* from_interval = interval_at_op_id(reg_num, throwing_op_id);
610N/A if (from_interval != to_interval) {
610N/A // optimization to reduce number of moves: when to_interval is on stack and
610N/A // the stack slot is known to be always correct, then no move is necessary
610N/A if (!from_interval->always_in_memory() || from_interval->canonical_spill_slot() != to_interval->assigned_reg()) {
610N/A move_resolver.add_mapping(from_interval, to_interval);
610N/A }
0N/A }
0N/A }
0N/A}
0N/A
0N/Avoid LinearScan::resolve_exception_edge(XHandler* handler, int throwing_op_id, MoveResolver &move_resolver) {
0N/A TRACE_LINEAR_SCAN(4, tty->print_cr("resolving exception handler B%d: throwing_op_id=%d", handler->entry_block()->block_id(), throwing_op_id));
0N/A
0N/A DEBUG_ONLY(move_resolver.check_empty());
0N/A assert(handler->lir_op_id() == -1, "already processed this xhandler");
0N/A DEBUG_ONLY(handler->set_lir_op_id(throwing_op_id));
3158N/A assert(handler->entry_code() == NULL, "code already present");
0N/A
0N/A // visit all registers where the live_in bit is set
0N/A BlockBegin* block = handler->entry_block();
0N/A int size = live_set_size();
0N/A 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)) {
304N/A resolve_exception_edge(handler, throwing_op_id, r, NULL, move_resolver);
0N/A }
0N/A
0N/A // the live_in bits are not set for phi functions of the xhandler entry, so iterate them separately
304N/A for_each_phi_fun(block, phi,
0N/A resolve_exception_edge(handler, throwing_op_id, phi->operand()->vreg_number(), phi, move_resolver)
0N/A );
304N/A
0N/A if (move_resolver.has_mappings()) {
0N/A LIR_List* entry_code = new LIR_List(compilation());
0N/A move_resolver.set_insert_position(entry_code, 0);
0N/A move_resolver.resolve_and_append_moves();
0N/A
0N/A entry_code->jump(handler->entry_block());
0N/A handler->set_entry_code(entry_code);
304N/A }
0N/A}
0N/A
304N/A
0N/Avoid LinearScan::resolve_exception_handlers() {
0N/A MoveResolver move_resolver(this);
304N/A LIR_OpVisitState visitor;
0N/A int num_blocks = block_count();
0N/A
0N/A int i;
0N/A for (i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A if (block->is_set(BlockBegin::exception_entry_flag)) {
0N/A resolve_exception_entry(block, move_resolver);
304N/A }
0N/A }
0N/A
0N/A for (i = 0; i < num_blocks; i++) {
0N/A BlockBegin* block = block_at(i);
0N/A LIR_List* ops = block->lir();
0N/A int num_ops = ops->length();
0N/A
0N/A // iterate all instructions of the block. skip the first because it is always a label
0N/A assert(visitor.no_operands(ops->at(0)), "first operation must always be a label");
0N/A for (int j = 1; j < num_ops; j++) {
0N/A LIR_Op* op = ops->at(j);
304N/A int op_id = op->id();
304N/A
0N/A if (op_id != -1 && has_info(op_id)) {
0N/A // visit operation to collect all operands
304N/A visitor.visit(op);
0N/A assert(visitor.info_count() > 0, "should not visit otherwise");
0N/A
0N/A XHandlers* xhandlers = visitor.all_xhandler();
0N/A int n = xhandlers->length();
0N/A for (int k = 0; k < n; k++) {
0N/A resolve_exception_edge(xhandlers->handler_at(k), op_id, move_resolver);
304N/A }
0N/A
0N/A#ifdef ASSERT
0N/A } else {
0N/A visitor.visit(op);
0N/A assert(visitor.all_xhandler()->length() == 0, "missed exception handler");
0N/A#endif
0N/A }
0N/A }
3158N/A }
3158N/A}
3158N/A
3158N/A
0N/A// ********** Phase 7: assign register numbers back to LIR
0N/A// (includes computation of debug information and oop maps)
0N/A
0N/AVMReg LinearScan::vm_reg_for_interval(Interval* interval) {
3158N/A VMReg reg = interval->cached_vm_reg();
0N/A if (!reg->is_valid() ) {
0N/A reg = vm_reg_for_operand(operand_for_interval(interval));
0N/A interval->set_cached_vm_reg(reg);
0N/A }
0N/A assert(reg == vm_reg_for_operand(operand_for_interval(interval)), "wrong cached value");
0N/A return reg;
0N/A}
0N/A
0N/AVMReg LinearScan::vm_reg_for_operand(LIR_Opr opr) {
304N/A assert(opr->is_oop(), "currently only implemented for oop operands");
0N/A return frame_map()->regname(opr);
0N/A}
0N/A
0N/A
0N/ALIR_Opr LinearScan::operand_for_interval(Interval* interval) {
0N/A LIR_Opr opr = interval->cached_opr();
0N/A if (opr->is_illegal()) {
0N/A opr = calc_operand_for_interval(interval);
0N/A interval->set_cached_opr(opr);
0N/A }
0N/A
0N/A assert(opr == calc_operand_for_interval(interval), "wrong cached value");
0N/A return opr;
0N/A}
0N/A
0N/ALIR_Opr LinearScan::calc_operand_for_interval(const Interval* interval) {
0N/A int assigned_reg = interval->assigned_reg();
0N/A BasicType type = interval->type();
0N/A
0N/A if (assigned_reg >= nof_regs) {
0N/A // stack slot
0N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
0N/A return LIR_OprFact::stack(assigned_reg - nof_regs, type);
0N/A
0N/A } else {
0N/A // register
304N/A switch (type) {
304N/A case T_OBJECT: {
304N/A assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");
304N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
0N/A return LIR_OprFact::single_cpu_oop(assigned_reg);
0N/A }
0N/A
0N/A case T_ADDRESS: {
0N/A assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");
0N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
0N/A return LIR_OprFact::single_cpu_address(assigned_reg);
0N/A }
0N/A
0N/A#ifdef __SOFTFP__
0N/A case T_FLOAT: // fall through
0N/A#endif // __SOFTFP__
0N/A case T_INT: {
0N/A assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");
3158N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
3158N/A return LIR_OprFact::single_cpu(assigned_reg);
0N/A }
0N/A
0N/A#ifdef __SOFTFP__
0N/A case T_DOUBLE: // fall through
0N/A#endif // __SOFTFP__
0N/A case T_LONG: {
0N/A int assigned_regHi = interval->assigned_regHi();
0N/A assert(assigned_reg >= pd_first_cpu_reg && assigned_reg <= pd_last_cpu_reg, "no cpu register");
0N/A assert(num_physical_regs(T_LONG) == 1 ||
0N/A (assigned_regHi >= pd_first_cpu_reg && assigned_regHi <= pd_last_cpu_reg), "no cpu register");
0N/A
0N/A assert(assigned_reg != assigned_regHi, "invalid allocation");
0N/A assert(num_physical_regs(T_LONG) == 1 || assigned_reg < assigned_regHi,
0N/A "register numbers must be sorted (ensure that e.g. a move from eax,ebx to ebx,eax can not occur)");
0N/A assert((assigned_regHi != any_reg) ^ (num_physical_regs(T_LONG) == 1), "must be match");
0N/A if (requires_adjacent_regs(T_LONG)) {
0N/A assert(assigned_reg % 2 == 0 && assigned_reg + 1 == assigned_regHi, "must be sequential and even");
0N/A }
0N/A
304N/A#ifdef _LP64
3158N/A return LIR_OprFact::double_cpu(assigned_reg, assigned_reg);
3158N/A#else
3158N/A#if defined(SPARC) || defined(PPC)
3158N/A return LIR_OprFact::double_cpu(assigned_regHi, assigned_reg);
3158N/A#else
3158N/A return LIR_OprFact::double_cpu(assigned_reg, assigned_regHi);
3158N/A#endif // SPARC
0N/A#endif // LP64
0N/A }
0N/A
0N/A#ifndef __SOFTFP__
3158N/A case T_FLOAT: {
3158N/A#ifdef X86
3158N/A if (UseSSE >= 1) {
3158N/A assert(assigned_reg >= pd_first_xmm_reg && assigned_reg <= pd_last_xmm_reg, "no xmm register");
3158N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
3158N/A return LIR_OprFact::single_xmm(assigned_reg - pd_first_xmm_reg);
0N/A }
0N/A#endif
0N/A
0N/A assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");
0N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register");
3158N/A return LIR_OprFact::single_fpu(assigned_reg - pd_first_fpu_reg);
0N/A }
0N/A
0N/A case T_DOUBLE: {
0N/A#ifdef X86
0N/A if (UseSSE >= 2) {
0N/A assert(assigned_reg >= pd_first_xmm_reg && assigned_reg <= pd_last_xmm_reg, "no xmm register");
0N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register (double xmm values are stored in one register)");
0N/A return LIR_OprFact::double_xmm(assigned_reg - pd_first_xmm_reg);
0N/A }
0N/A#endif
0N/A
0N/A#ifdef SPARC
0N/A assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");
0N/A assert(interval->assigned_regHi() >= pd_first_fpu_reg && interval->assigned_regHi() <= pd_last_fpu_reg, "no fpu register");
0N/A assert(assigned_reg % 2 == 0 && assigned_reg + 1 == interval->assigned_regHi(), "must be sequential and even");
0N/A LIR_Opr result = LIR_OprFact::double_fpu(interval->assigned_regHi() - pd_first_fpu_reg, assigned_reg - pd_first_fpu_reg);
0N/A#elif defined(ARM)
0N/A assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");
0N/A assert(interval->assigned_regHi() >= pd_first_fpu_reg && interval->assigned_regHi() <= pd_last_fpu_reg, "no fpu register");
0N/A assert(assigned_reg % 2 == 0 && assigned_reg + 1 == interval->assigned_regHi(), "must be sequential and even");
0N/A LIR_Opr result = LIR_OprFact::double_fpu(assigned_reg - pd_first_fpu_reg, interval->assigned_regHi() - pd_first_fpu_reg);
304N/A#else
0N/A assert(assigned_reg >= pd_first_fpu_reg && assigned_reg <= pd_last_fpu_reg, "no fpu register");
0N/A assert(interval->assigned_regHi() == any_reg, "must not have hi register (double fpu values are stored in one register on Intel)");
0N/A LIR_Opr result = LIR_OprFact::double_fpu(assigned_reg - pd_first_fpu_reg);
0N/A#endif
0N/A return result;
0N/A }
0N/A#endif // __SOFTFP__
304N/A
0N/A default: {
0N/A ShouldNotReachHere();
0N/A return LIR_OprFact::illegalOpr;
0N/A }
0N/A }
0N/A }
0N/A}
0N/A
304N/ALIR_Opr LinearScan::canonical_spill_opr(Interval* interval) {
0N/A assert(interval->canonical_spill_slot() >= nof_regs, "canonical spill slot not set");
0N/A return LIR_OprFact::stack(interval->canonical_spill_slot() - nof_regs, interval->type());
304N/A}
0N/A
0N/ALIR_Opr LinearScan::color_lir_opr(LIR_Opr opr, int op_id, LIR_OpVisitState::OprMode mode) {
0N/A assert(opr->is_virtual(), "should not call this otherwise");
0N/A
0N/A Interval* interval = interval_at(opr->vreg_number());
0N/A assert(interval != NULL, "interval must exist");
0N/A
0N/A if (op_id != -1) {
304N/A#ifdef ASSERT
0N/A BlockBegin* block = block_of_op_with_id(op_id);
0N/A if (block->number_of_sux() <= 1 && op_id == block->last_lir_instruction_id()) {
0N/A // check if spill moves could have been appended at the end of this block, but
0N/A // before the branch instruction. So the split child information for this branch would
0N/A // be incorrect.
0N/A LIR_OpBranch* branch = block->lir()->instructions_list()->last()->as_OpBranch();
0N/A if (branch != NULL) {
0N/A if (block->live_out().at(opr->vreg_number())) {
0N/A assert(branch->cond() == lir_cond_always, "block does not end with an unconditional jump");
0N/A 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)");
0N/A }
0N/A }
0N/A }
0N/A#endif
0N/A
0N/A // operands are not changed when an interval is split during allocation,
0N/A // so search the right interval here
0N/A interval = split_child_at_op_id(interval, op_id, mode);
0N/A }
0N/A
0N/A LIR_Opr res = operand_for_interval(interval);
0N/A
0N/A#ifdef X86
0N/A // new semantic for is_last_use: not only set on definite end of interval,
0N/A // but also before hole
0N/A // This may still miss some cases (e.g. for dead values), but it is not necessary that the
0N/A // last use information is completely correct
0N/A // information is only needed for fpu stack allocation
0N/A if (res->is_fpu_register()) {
0N/A if (opr->is_last_use() || op_id == interval->to() || (op_id != -1 && interval->has_hole_between(op_id, op_id + 1))) {
304N/A assert(op_id == -1 || !is_block_begin(op_id), "holes at begin of block may also result from control flow");
0N/A res = res->make_last_use();
304N/A }
0N/A }
0N/A#endif
0N/A
0N/A assert(!gen()->is_vreg_flag_set(opr->vreg_number(), LIRGenerator::callee_saved) || !FrameMap::is_caller_save_register(res), "bad allocation");
3158N/A
3158N/A return res;
3158N/A}
3158N/A
3158N/A
3158N/A#ifdef ASSERT
3158N/A// some methods used to check correctness of debug information
3158N/A
3158N/Avoid assert_no_register_values(GrowableArray<ScopeValue*>* values) {
0N/A if (values == NULL) {
0N/A return;
0N/A }
0N/A
0N/A for (int i = 0; i < values->length(); i++) {
0N/A ScopeValue* value = values->at(i);
0N/A
0N/A if (value->is_location()) {
0N/A Location location = ((LocationValue*)value)->location();
0N/A assert(location.where() == Location::on_stack, "value is in register");
0N/A }
0N/A }
0N/A}
0N/A
0N/Avoid assert_no_register_values(GrowableArray<MonitorValue*>* values) {
0N/A if (values == NULL) {
0N/A return;
0N/A }
0N/A
0N/A for (int i = 0; i < values->length(); i++) {
0N/A MonitorValue* value = values->at(i);
0N/A
0N/A if (value->owner()->is_location()) {
0N/A Location location = ((LocationValue*)value->owner())->location();
0N/A assert(location.where() == Location::on_stack, "owner is in register");
0N/A }
0N/A assert(value->basic_lock().where() == Location::on_stack, "basic_lock is in register");
0N/A }
0N/A}
0N/A
0N/Avoid assert_equal(Location l1, Location l2) {
0N/A assert(l1.where() == l2.where() && l1.type() == l2.type() && l1.offset() == l2.offset(), "");
0N/A}
0N/A
0N/Avoid assert_equal(ScopeValue* v1, ScopeValue* v2) {
0N/A if (v1->is_location()) {
0N/A assert(v2->is_location(), "");
304N/A assert_equal(((LocationValue*)v1)->location(), ((LocationValue*)v2)->location());
304N/A } else if (v1->is_constant_int()) {
304N/A assert(v2->is_constant_int(), "");
0N/A assert(((ConstantIntValue*)v1)->value() == ((ConstantIntValue*)v2)->value(), "");
304N/A } else if (v1->is_constant_double()) {
0N/A assert(v2->is_constant_double(), "");
0N/A assert(((ConstantDoubleValue*)v1)->value() == ((ConstantDoubleValue*)v2)->value(), "");
0N/A } else if (v1->is_constant_long()) {
304N/A assert(v2->is_constant_long(), "");
0N/A assert(((ConstantLongValue*)v1)->value() == ((ConstantLongValue*)v2)->value(), "");
0N/A } else if (v1->is_constant_oop()) {
0N/A assert(v2->is_constant_oop(), "");
0N/A assert(((ConstantOopWriteValue*)v1)->value() == ((ConstantOopWriteValue*)v2)->value(), "");
0N/A } else {
0N/A ShouldNotReachHere();
0N/A }
0N/A}
0N/A
0N/Avoid assert_equal(MonitorValue* m1, MonitorValue* m2) {
0N/A assert_equal(m1->owner(), m2->owner());
0N/A assert_equal(m1->basic_lock(), m2->basic_lock());
0N/A}
0N/A
0N/Avoid assert_equal(IRScopeDebugInfo* d1, IRScopeDebugInfo* d2) {
0N/A assert(d1->scope() == d2->scope(), "not equal");
0N/A assert(d1->bci() == d2->bci(), "not equal");
0N/A
0N/A if (d1->locals() != NULL) {
304N/A assert(d1->locals() != NULL && d2->locals() != NULL, "not equal");
512N/A assert(d1->locals()->length() == d2->locals()->length(), "not equal");
0N/A for (int i = 0; i < d1->locals()->length(); i++) {
0N/A assert_equal(d1->locals()->at(i), d2->locals()->at(i));
0N/A }
0N/A } else {
304N/A assert(d1->locals() == NULL && d2->locals() == NULL, "not equal");
304N/A }
304N/A
304N/A if (d1->expressions() != NULL) {
0N/A assert(d1->expressions() != NULL && d2->expressions() != NULL, "not equal");
304N/A assert(d1->expressions()->length() == d2->expressions()->length(), "not equal");
0N/A for (int i = 0; i < d1->expressions()->length(); i++) {
0N/A assert_equal(d1->expressions()->at(i), d2->expressions()->at(i));
0N/A }
304N/A } else {
0N/A assert(d1->expressions() == NULL && d2->expressions() == NULL, "not equal");
0N/A }
0N/A
0N/A if (d1->monitors() != NULL) {
0N/A assert(d1->monitors() != NULL && d2->monitors() != NULL, "not equal");
0N/A assert(d1->monitors()->length() == d2->monitors()->length(), "not equal");
304N/A for (int i = 0; i < d1->monitors()->length(); i++) {
0N/A assert_equal(d1->monitors()->at(i), d2->monitors()->at(i));
0N/A }
0N/A } else {
0N/A assert(d1->monitors() == NULL && d2->monitors() == NULL, "not equal");
0N/A }
0N/A
0N/A if (d1->caller() != NULL) {
0N/A assert(d1->caller() != NULL && d2->caller() != NULL, "not equal");
0N/A assert_equal(d1->caller(), d2->caller());
0N/A } else {
0N/A assert(d1->caller() == NULL && d2->caller() == NULL, "not equal");
0N/A }
0N/A}
0N/A
0N/Avoid check_stack_depth(CodeEmitInfo* info, int stack_end) {
0N/A if (info->stack()->bci() != SynchronizationEntryBCI && !info->scope()->method()->is_native()) {
0N/A Bytecodes::Code code = info->scope()->method()->java_code_at_bci(info->stack()->bci());
0N/A switch (code) {
0N/A case Bytecodes::_ifnull : // fall through
0N/A case Bytecodes::_ifnonnull : // fall through
0N/A case Bytecodes::_ifeq : // fall through
0N/A case Bytecodes::_ifne : // fall through
3158N/A case Bytecodes::_iflt : // fall through
3158N/A case Bytecodes::_ifge : // fall through
3158N/A case Bytecodes::_ifgt : // fall through
3158N/A case Bytecodes::_ifle : // fall through
3158N/A case Bytecodes::_if_icmpeq : // fall through
3158N/A case Bytecodes::_if_icmpne : // fall through
3158N/A case Bytecodes::_if_icmplt : // fall through
3158N/A case Bytecodes::_if_icmpge : // fall through
3158N/A case Bytecodes::_if_icmpgt : // fall through
3158N/A case Bytecodes::_if_icmple : // fall through
3158N/A case Bytecodes::_if_acmpeq : // fall through
3158N/A case Bytecodes::_if_acmpne :
0N/A assert(stack_end >= -Bytecodes::depth(code), "must have non-empty expression stack at if bytecode");
0N/A break;
0N/A }
0N/A }
2252N/A}
0N/A
0N/A#endif // ASSERT
0N/A
0N/A
0N/AIntervalWalker* LinearScan::init_compute_oop_maps() {
0N/A // setup lists of potential oops for walking
0N/A Interval* oop_intervals;
3158N/A Interval* non_oop_intervals;
3158N/A
3158N/A create_unhandled_lists(&oop_intervals, &non_oop_intervals, is_oop_interval, NULL);
3158N/A
3158N/A // intervals that have no oops inside need not to be processed
0N/A // to ensure a walking until the last instruction id, add a dummy interval
0N/A // with a high operation id
0N/A non_oop_intervals = new Interval(any_reg);
0N/A non_oop_intervals->add_range(max_jint - 2, max_jint - 1);
116N/A
116N/A return new IntervalWalker(this, oop_intervals, non_oop_intervals);
116N/A}
116N/A
116N/A
116N/AOopMap* LinearScan::compute_oop_map(IntervalWalker* iw, LIR_Op* op, CodeEmitInfo* info, bool is_call_site) {
116N/A TRACE_LINEAR_SCAN(3, tty->print_cr("creating oop map at op_id %d", op->id()));
116N/A
116N/A // walk before the current operation -> intervals that start at
116N/A // the operation (= output operands of the operation) are not
116N/A // included in the oop map
116N/A iw->walk_before(op->id());
116N/A
116N/A int frame_size = frame_map()->framesize();
116N/A int arg_count = frame_map()->oop_map_arg_count();
116N/A OopMap* map = new OopMap(frame_size, arg_count);
116N/A
116N/A // Check if this is a patch site.
116N/A bool is_patch_info = false;
116N/A if (op->code() == lir_move) {
116N/A assert(!is_call_site, "move must not be a call site");
116N/A assert(op->as_Op1() != NULL, "move must be LIR_Op1");
116N/A LIR_Op1* move = (LIR_Op1*)op;
116N/A
116N/A is_patch_info = move->patch_code() != lir_patch_none;
116N/A }
116N/A
116N/A // Iterate through active intervals
116N/A for (Interval* interval = iw->active_first(fixedKind); interval != Interval::end(); interval = interval->next()) {
116N/A int assigned_reg = interval->assigned_reg();
116N/A
116N/A assert(interval->current_from() <= op->id() && op->id() <= interval->current_to(), "interval should not be active otherwise");
116N/A assert(interval->assigned_regHi() == any_reg, "oop must be single word");
116N/A assert(interval->reg_num() >= LIR_OprDesc::vreg_base, "fixed interval found");
116N/A
116N/A // Check if this range covers the instruction. Intervals that
116N/A // start or end at the current operation are not included in the
116N/A // oop map, except in the case of patching moves. For patching
116N/A // moves, any intervals which end at this instruction are included
116N/A // in the oop map since we may safepoint while doing the patch
116N/A // before we've consumed the inputs.
116N/A if (is_patch_info || op->id() < interval->current_to()) {
116N/A
116N/A // caller-save registers must not be included into oop-maps at calls
116N/A 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");
116N/A
116N/A VMReg name = vm_reg_for_interval(interval);
116N/A map->set_oop(name);
116N/A
116N/A // Spill optimization: when the stack value is guaranteed to be always correct,
116N/A // then it must be added to the oop map even if the interval is currently in a register
116N/A if (interval->always_in_memory() &&
116N/A op->id() > interval->spill_definition_pos() &&
116N/A interval->assigned_reg() != interval->canonical_spill_slot()) {
116N/A assert(interval->spill_definition_pos() > 0, "position not set correctly");
116N/A assert(interval->canonical_spill_slot() >= LinearScan::nof_regs, "no spill slot assigned");
2062N/A assert(interval->assigned_reg() < LinearScan::nof_regs, "interval is on stack, so stack slot is registered twice");
116N/A
116N/A map->set_oop(frame_map()->slot_regname(interval->canonical_spill_slot() - LinearScan::nof_regs));
116N/A }
116N/A }
116N/A }
116N/A
116N/A // add oops from lock stack
116N/A assert(info->stack() != NULL, "CodeEmitInfo must always have a stack");
116N/A int locks_count = info->stack()->total_locks_size();
116N/A for (int i = 0; i < locks_count; i++) {
116N/A map->set_oop(frame_map()->monitor_object_regname(i));
116N/A }
116N/A
116N/A return map;
116N/A}
116N/A
116N/A
116N/Avoid LinearScan::compute_oop_map(IntervalWalker* iw, const LIR_OpVisitState &visitor, LIR_Op* op) {
116N/A assert(visitor.info_count() > 0, "no oop map needed");
116N/A
116N/A // compute oop_map only for first CodeEmitInfo
116N/A // because it is (in most cases) equal for all other infos of the same operation
116N/A CodeEmitInfo* first_info = visitor.info_at(0);
116N/A OopMap* first_oop_map = compute_oop_map(iw, op, first_info, visitor.has_call());
116N/A
116N/A for (int i = 0; i < visitor.info_count(); i++) {
116N/A CodeEmitInfo* info = visitor.info_at(i);
116N/A OopMap* oop_map = first_oop_map;
116N/A
116N/A if (info->stack()->locks_size() != first_info->stack()->locks_size()) {
116N/A // this info has a different number of locks then the precomputed oop map
116N/A // (possible for lock and unlock instructions) -> compute oop map with
116N/A // correct lock information
116N/A oop_map = compute_oop_map(iw, op, info, visitor.has_call());
116N/A }
116N/A
116N/A if (info->_oop_map == NULL) {
116N/A info->_oop_map = oop_map;
116N/A } else {
116N/A // a CodeEmitInfo can not be shared between different LIR-instructions
116N/A // because interval splitting can occur anywhere between two instructions
116N/A // and so the oop maps must be different
116N/A // -> check if the already set oop_map is exactly the one calculated for this operation
116N/A assert(info->_oop_map == oop_map, "same CodeEmitInfo used for multiple LIR instructions");
116N/A }
116N/A }
116N/A}
116N/A
116N/A
116N/A// frequently used constants
116N/AConstantOopWriteValue LinearScan::_oop_null_scope_value = ConstantOopWriteValue(NULL);
116N/AConstantIntValue LinearScan::_int_m1_scope_value = ConstantIntValue(-1);
116N/AConstantIntValue LinearScan::_int_0_scope_value = ConstantIntValue(0);
116N/AConstantIntValue LinearScan::_int_1_scope_value = ConstantIntValue(1);
116N/AConstantIntValue LinearScan::_int_2_scope_value = ConstantIntValue(2);
116N/ALocationValue _illegal_value = LocationValue(Location());
116N/A
116N/Avoid LinearScan::init_compute_debug_info() {
116N/A // cache for frequently used scope values
116N/A // (cpu registers and stack slots)
116N/A _scope_value_cache = ScopeValueArray((LinearScan::nof_cpu_regs + frame_map()->argcount() + max_spills()) * 2, NULL);
116N/A}
116N/A
116N/AMonitorValue* LinearScan::location_for_monitor_index(int monitor_index) {
116N/A Location loc;
116N/A if (!frame_map()->location_for_monitor_object(monitor_index, &loc)) {
116N/A bailout("too large frame");
116N/A }
116N/A ScopeValue* object_scope_value = new LocationValue(loc);
116N/A
116N/A if (!frame_map()->location_for_monitor_lock(monitor_index, &loc)) {
116N/A bailout("too large frame");
116N/A }
116N/A return new MonitorValue(object_scope_value, loc);
116N/A}
116N/A
116N/ALocationValue* LinearScan::location_for_name(int name, Location::Type loc_type) {
116N/A Location loc;
116N/A if (!frame_map()->locations_for_slot(name, loc_type, &loc)) {
116N/A bailout("too large frame");
116N/A }
116N/A return new LocationValue(loc);
116N/A}
116N/A
116N/A
116N/Aint LinearScan::append_scope_value_for_constant(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values) {
116N/A assert(opr->is_constant(), "should not be called otherwise");
116N/A
116N/A LIR_Const* c = opr->as_constant_ptr();
116N/A BasicType t = c->type();
116N/A switch (t) {
116N/A case T_OBJECT: {
116N/A jobject value = c->as_jobject();
116N/A if (value == NULL) {
116N/A scope_values->append(&_oop_null_scope_value);
116N/A } else {
116N/A scope_values->append(new ConstantOopWriteValue(c->as_jobject()));
116N/A }
116N/A return 1;
116N/A }
116N/A
116N/A case T_INT: // fall through
116N/A case T_FLOAT: {
116N/A int value = c->as_jint_bits();
116N/A switch (value) {
116N/A case -1: scope_values->append(&_int_m1_scope_value); break;
116N/A case 0: scope_values->append(&_int_0_scope_value); break;
116N/A case 1: scope_values->append(&_int_1_scope_value); break;
116N/A case 2: scope_values->append(&_int_2_scope_value); break;
116N/A default: scope_values->append(new ConstantIntValue(c->as_jint_bits())); break;
116N/A }
116N/A return 1;
116N/A }
116N/A
116N/A case T_LONG: // fall through
116N/A case T_DOUBLE: {
116N/A#ifdef _LP64
116N/A scope_values->append(&_int_0_scope_value);
116N/A scope_values->append(new ConstantLongValue(c->as_jlong_bits()));
116N/A#else
116N/A if (hi_word_offset_in_bytes > lo_word_offset_in_bytes) {
116N/A scope_values->append(new ConstantIntValue(c->as_jint_hi_bits()));
116N/A scope_values->append(new ConstantIntValue(c->as_jint_lo_bits()));
116N/A } else {
116N/A scope_values->append(new ConstantIntValue(c->as_jint_lo_bits()));
116N/A scope_values->append(new ConstantIntValue(c->as_jint_hi_bits()));
116N/A }
116N/A#endif
116N/A return 2;
116N/A }
116N/A
116N/A case T_ADDRESS: {
116N/A#ifdef _LP64
116N/A scope_values->append(new ConstantLongValue(c->as_jint()));
116N/A#else
116N/A scope_values->append(new ConstantIntValue(c->as_jint()));
116N/A#endif
116N/A return 1;
116N/A }
116N/A
116N/A default:
116N/A ShouldNotReachHere();
116N/A return -1;
116N/A }
116N/A}
116N/A
116N/Aint LinearScan::append_scope_value_for_operand(LIR_Opr opr, GrowableArray<ScopeValue*>* scope_values) {
116N/A if (opr->is_single_stack()) {
116N/A int stack_idx = opr->single_stack_ix();
116N/A bool is_oop = opr->is_oop_register();
116N/A int cache_idx = (stack_idx + LinearScan::nof_cpu_regs) * 2 + (is_oop ? 1 : 0);
116N/A
116N/A ScopeValue* sv = _scope_value_cache.at(cache_idx);
116N/A if (sv == NULL) {
116N/A Location::Type loc_type = is_oop ? Location::oop : Location::normal;
116N/A sv = location_for_name(stack_idx, loc_type);
116N/A _scope_value_cache.at_put(cache_idx, sv);
116N/A }
116N/A
116N/A // check if cached value is correct
116N/A DEBUG_ONLY(assert_equal(sv, location_for_name(stack_idx, is_oop ? Location::oop : Location::normal)));
116N/A
116N/A scope_values->append(sv);
116N/A return 1;
116N/A
116N/A } else if (opr->is_single_cpu()) {
116N/A bool is_oop = opr->is_oop_register();
116N/A int cache_idx = opr->cpu_regnr() * 2 + (is_oop ? 1 : 0);
116N/A Location::Type int_loc_type = NOT_LP64(Location::normal) LP64_ONLY(Location::int_in_long);
116N/A
116N/A ScopeValue* sv = _scope_value_cache.at(cache_idx);
116N/A if (sv == NULL) {
116N/A Location::Type loc_type = is_oop ? Location::oop : int_loc_type;
116N/A VMReg rname = frame_map()->regname(opr);
116N/A sv = new LocationValue(Location::new_reg_loc(loc_type, rname));
116N/A _scope_value_cache.at_put(cache_idx, sv);
116N/A }
116N/A
116N/A // check if cached value is correct
116N/A DEBUG_ONLY(assert_equal(sv, new LocationValue(Location::new_reg_loc(is_oop ? Location::oop : int_loc_type, frame_map()->regname(opr)))));
116N/A
116N/A scope_values->append(sv);
116N/A return 1;
116N/A
116N/A#ifdef X86
116N/A } else if (opr->is_single_xmm()) {
116N/A VMReg rname = opr->as_xmm_float_reg()->as_VMReg();
116N/A LocationValue* sv = new LocationValue(Location::new_reg_loc(Location::normal, rname));
116N/A
116N/A scope_values->append(sv);
116N/A return 1;
116N/A#endif
116N/A
165N/A } else if (opr->is_single_fpu()) {
165N/A#ifdef X86
165N/A // the exact location of fpu stack values is only known
165N/A // during fpu stack allocation, so the stack allocator object
116N/A // must be present
116N/A assert(use_fpu_stack_allocation(), "should not have float stack values without fpu stack allocation (all floats must be SSE2)");
116N/A assert(_fpu_stack_allocator != NULL, "must be present");
116N/A opr = _fpu_stack_allocator->to_fpu_stack(opr);
116N/A#endif
116N/A
116N/A Location::Type loc_type = float_saved_as_double ? Location::float_in_dbl : Location::normal;
116N/A VMReg rname = frame_map()->fpu_regname(opr->fpu_regnr());
116N/A LocationValue* sv = new LocationValue(Location::new_reg_loc(loc_type, rname));
116N/A
116N/A scope_values->append(sv);
116N/A return 1;
116N/A
116N/A } else {
116N/A // double-size operands
116N/A
116N/A ScopeValue* first;
116N/A ScopeValue* second;
116N/A
116N/A if (opr->is_double_stack()) {
116N/A#ifdef _LP64
116N/A Location loc1;
116N/A Location::Type loc_type = opr->type() == T_LONG ? Location::lng : Location::dbl;
116N/A if (!frame_map()->locations_for_slot(opr->double_stack_ix(), loc_type, &loc1, NULL)) {
116N/A bailout("too large frame");
116N/A }
116N/A // Does this reverse on x86 vs. sparc?
116N/A first = new LocationValue(loc1);
116N/A second = &_int_0_scope_value;
116N/A#else
116N/A Location loc1, loc2;
116N/A if (!frame_map()->locations_for_slot(opr->double_stack_ix(), Location::normal, &loc1, &loc2)) {
116N/A bailout("too large frame");
116N/A }
116N/A first = new LocationValue(loc1);
116N/A second = new LocationValue(loc2);
116N/A#endif // _LP64
116N/A
116N/A } else if (opr->is_double_cpu()) {
116N/A#ifdef _LP64
116N/A VMReg rname_first = opr->as_register_lo()->as_VMReg();
116N/A first = new LocationValue(Location::new_reg_loc(Location::lng, rname_first));
116N/A second = &_int_0_scope_value;
116N/A#else
116N/A VMReg rname_first = opr->as_register_lo()->as_VMReg();
116N/A VMReg rname_second = opr->as_register_hi()->as_VMReg();
116N/A
116N/A if (hi_word_offset_in_bytes < lo_word_offset_in_bytes) {
116N/A // lo/hi and swapped relative to first and second, so swap them
116N/A VMReg tmp = rname_first;
116N/A rname_first = rname_second;
116N/A rname_second = tmp;
116N/A }
116N/A
116N/A first = new LocationValue(Location::new_reg_loc(Location::normal, rname_first));
116N/A second = new LocationValue(Location::new_reg_loc(Location::normal, rname_second));
116N/A#endif //_LP64
116N/A
116N/A
116N/A#ifdef X86
116N/A } else if (opr->is_double_xmm()) {
116N/A assert(opr->fpu_regnrLo() == opr->fpu_regnrHi(), "assumed in calculation");
116N/A VMReg rname_first = opr->as_xmm_double_reg()->as_VMReg();
116N/A# ifdef _LP64
116N/A first = new LocationValue(Location::new_reg_loc(Location::dbl, rname_first));
116N/A second = &_int_0_scope_value;
116N/A# else
116N/A first = new LocationValue(Location::new_reg_loc(Location::normal, rname_first));
116N/A // %%% This is probably a waste but we'll keep things as they were for now
116N/A if (true) {
116N/A VMReg rname_second = rname_first->next();
116N/A second = new LocationValue(Location::new_reg_loc(Location::normal, rname_second));
116N/A }
116N/A# endif
116N/A#endif
116N/A
116N/A } else if (opr->is_double_fpu()) {
116N/A // On SPARC, fpu_regnrLo/fpu_regnrHi represents the two halves of
116N/A // the double as float registers in the native ordering. On X86,
116N/A // fpu_regnrLo is a FPU stack slot whose VMReg represents
116N/A // the low-order word of the double and fpu_regnrLo + 1 is the
116N/A // name for the other half. *first and *second must represent the
116N/A // least and most significant words, respectively.
116N/A
116N/A#ifdef X86
116N/A // the exact location of fpu stack values is only known
116N/A // during fpu stack allocation, so the stack allocator object
116N/A // must be present
116N/A assert(use_fpu_stack_allocation(), "should not have float stack values without fpu stack allocation (all floats must be SSE2)");
116N/A assert(_fpu_stack_allocator != NULL, "must be present");
116N/A opr = _fpu_stack_allocator->to_fpu_stack(opr);
116N/A
116N/A assert(opr->fpu_regnrLo() == opr->fpu_regnrHi(), "assumed in calculation (only fpu_regnrHi is used)");
116N/A#endif
116N/A#ifdef SPARC
116N/A assert(opr->fpu_regnrLo() == opr->fpu_regnrHi() + 1, "assumed in calculation (only fpu_regnrHi is used)");
116N/A#endif
116N/A#ifdef ARM
116N/A assert(opr->fpu_regnrHi() == opr->fpu_regnrLo() + 1, "assumed in calculation (only fpu_regnrLo is used)");
116N/A#endif
116N/A#ifdef PPC
116N/A assert(opr->fpu_regnrLo() == opr->fpu_regnrHi(), "assumed in calculation (only fpu_regnrHi is used)");
116N/A#endif
116N/A
116N/A VMReg rname_first = frame_map()->fpu_regname(opr->fpu_regnrHi());
116N/A#ifdef _LP64
116N/A first = new LocationValue(Location::new_reg_loc(Location::dbl, rname_first));
116N/A second = &_int_0_scope_value;
116N/A#else
116N/A first = new LocationValue(Location::new_reg_loc(Location::normal, rname_first));
116N/A // %%% This is probably a waste but we'll keep things as they were for now
116N/A if (true) {
116N/A VMReg rname_second = rname_first->next();
116N/A second = new LocationValue(Location::new_reg_loc(Location::normal, rname_second));
116N/A }
116N/A#endif
116N/A
116N/A } else {
116N/A ShouldNotReachHere();
116N/A first = NULL;
116N/A second = NULL;
0N/A }
0N/A
0N/A assert(first != NULL && second != NULL, "must be set");
1426N/A // The convention the interpreter uses is that the second local
0N/A // holds the first raw word of the native double representation.
0N/A // This is actually reasonable, since locals and stack arrays
0N/A // grow downwards in all implementations.
0N/A // (If, on some machine, the interpreter's Java locals or stack
0N/A // were to grow upwards, the embedded doubles would be word-swapped.)
0N/A scope_values->append(second);
0N/A scope_values->append(first);
0N/A return 2;
0N/A }
0N/A}
0N/A
0N/A
0N/Aint LinearScan::append_scope_value(int op_id, Value value, GrowableArray<ScopeValue*>* scope_values) {
0N/A if (value != NULL) {
0N/A LIR_Opr opr = value->operand();
0N/A Constant* con = value->as_Constant();
0N/A
0N/A assert(con == NULL || opr->is_virtual() || opr->is_constant() || opr->is_illegal(), "asumption: Constant instructions have only constant operands (or illegal if constant is optimized away)");
0N/A assert(con != NULL || opr->is_virtual(), "asumption: non-Constant instructions have only virtual operands");
0N/A
0N/A if (con != NULL && !con->is_pinned() && !opr->is_constant()) {
0N/A // Unpinned constants may have a virtual operand for a part of the lifetime
0N/A // or may be illegal when it was optimized away,
0N/A // so always use a constant operand
0N/A opr = LIR_OprFact::value_type(con->type());
0N/A }
0N/A assert(opr->is_virtual() || opr->is_constant(), "other cases not allowed here");
0N/A
0N/A if (opr->is_virtual()) {
0N/A LIR_OpVisitState::OprMode mode = LIR_OpVisitState::inputMode;
0N/A
0N/A BlockBegin* block = block_of_op_with_id(op_id);
0N/A if (block->number_of_sux() == 1 && op_id == block->last_lir_instruction_id()) {
0N/A // generating debug information for the last instruction of a block.
0N/A // if this instruction is a branch, spill moves are inserted before this branch
0N/A // and so the wrong operand would be returned (spill moves at block boundaries are not
0N/A // considered in the live ranges of intervals)
0N/A // Solution: use the first op_id of the branch target block instead.
0N/A if (block->lir()->instructions_list()->last()->as_OpBranch() != NULL) {
0N/A if (block->live_out().at(opr->vreg_number())) {
0N/A op_id = block->sux_at(0)->first_lir_instruction_id();
0N/A mode = LIR_OpVisitState::outputMode;
0N/A }
0N/A }
0N/A }
0N/A
0N/A // Get current location of operand
0N/A // The operand must be live because debug information is considered when building the intervals
0N/A // if the interval is not live, color_lir_opr will cause an assertion failure
0N/A opr = color_lir_opr(opr, op_id, mode);
0N/A assert(!has_call(op_id) || opr->is_stack() || !is_caller_save(reg_num(opr)), "can not have caller-save register operands at calls");
0N/A
0N/A // Append to ScopeValue array
0N/A return append_scope_value_for_operand(opr, scope_values);
0N/A
0N/A } else {
0N/A assert(value->as_Constant() != NULL, "all other instructions have only virtual operands");
0N/A assert(opr->is_constant(), "operand must be constant");
0N/A
926N/A return append_scope_value_for_constant(opr, scope_values);
0N/A }
304N/A } else {
0N/A // append a dummy value because real value not needed
0N/A scope_values->append(&_illegal_value);
0N/A return 1;
0N/A }
0N/A}
0N/A
0N/A
0N/AIRScopeDebugInfo* LinearScan::compute_debug_info_for_scope(int op_id, IRScope* cur_scope, ValueStack* cur_state, ValueStack* innermost_state) {
926N/A IRScopeDebugInfo* caller_debug_info = NULL;
0N/A
304N/A ValueStack* caller_state = cur_state->caller_state();
0N/A if (caller_state != NULL) {
0N/A // process recursively to compute outermost scope first
0N/A caller_debug_info = compute_debug_info_for_scope(op_id, cur_scope->caller(), caller_state, innermost_state);
0N/A }
0N/A
0N/A // initialize these to null.
0N/A // If we don't need deopt info or there are no locals, expressions or monitors,
0N/A // then these get recorded as no information and avoids the allocation of 0 length arrays.
0N/A GrowableArray<ScopeValue*>* locals = NULL;
0N/A GrowableArray<ScopeValue*>* expressions = NULL;
0N/A GrowableArray<MonitorValue*>* monitors = NULL;
0N/A
304N/A // describe local variable values
304N/A int nof_locals = cur_state->locals_size();
0N/A if (nof_locals > 0) {
0N/A locals = new GrowableArray<ScopeValue*>(nof_locals);
0N/A
0N/A int pos = 0;
0N/A while (pos < nof_locals) {
0N/A assert(pos < cur_state->locals_size(), "why not?");
0N/A
0N/A Value local = cur_state->local_at(pos);
0N/A pos += append_scope_value(op_id, local, locals);
0N/A
0N/A assert(locals->length() == pos, "must match");
0N/A }
0N/A assert(locals->length() == cur_scope->method()->max_locals(), "wrong number of locals");
0N/A assert(locals->length() == cur_state->locals_size(), "wrong number of locals");
304N/A } else if (cur_scope->method()->max_locals() > 0) {
0N/A assert(cur_state->kind() == ValueStack::EmptyExceptionState, "should be");
0N/A nof_locals = cur_scope->method()->max_locals();
0N/A locals = new GrowableArray<ScopeValue*>(nof_locals);
0N/A for(int i = 0; i < nof_locals; i++) {
926N/A locals->append(&_illegal_value);
0N/A }
0N/A }
0N/A
0N/A // describe expression stack
304N/A int nof_stack = cur_state->stack_size();
0N/A if (nof_stack > 0) {
0N/A expressions = new GrowableArray<ScopeValue*>(nof_stack);
0N/A
0N/A int pos = 0;
304N/A while (pos < nof_stack) {
304N/A Value expression = cur_state->stack_at_inc(pos);
512N/A append_scope_value(op_id, expression, expressions);
0N/A
0N/A assert(expressions->length() == pos, "must match");
0N/A }
304N/A assert(expressions->length() == cur_state->stack_size(), "wrong number of stack entries");
0N/A }
0N/A
0N/A // describe monitors
0N/A int nof_locks = cur_state->locks_size();
304N/A if (nof_locks > 0) {
304N/A int lock_offset = cur_state->caller_state() != NULL ? cur_state->caller_state()->total_locks_size() : 0;
0N/A monitors = new GrowableArray<MonitorValue*>(nof_locks);
0N/A for (int i = 0; i < nof_locks; i++) {
0N/A monitors->append(location_for_monitor_index(lock_offset + i));
0N/A }
0N/A }
0N/A
0N/A return new IRScopeDebugInfo(cur_scope, cur_state->bci(), locals, expressions, monitors, caller_debug_info);
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::compute_debug_info(CodeEmitInfo* info, int op_id) {
0N/A TRACE_LINEAR_SCAN(3, tty->print_cr("creating debug information at op_id %d", op_id));
0N/A
0N/A IRScope* innermost_scope = info->scope();
304N/A ValueStack* innermost_state = info->stack();
0N/A
0N/A assert(innermost_scope != NULL && innermost_state != NULL, "why is it missing?");
0N/A
0N/A DEBUG_ONLY(check_stack_depth(info, innermost_state->stack_size()));
0N/A
0N/A if (info->_scope_debug_info == NULL) {
0N/A // compute debug information
0N/A info->_scope_debug_info = compute_debug_info_for_scope(op_id, innermost_scope, innermost_state, innermost_state);
0N/A } else {
0N/A // debug information already set. Check that it is correct from the current point of view
0N/A DEBUG_ONLY(assert_equal(info->_scope_debug_info, compute_debug_info_for_scope(op_id, innermost_scope, innermost_state, innermost_state)));
304N/A }
0N/A}
0N/A
0N/A
0N/Avoid LinearScan::assign_reg_num(LIR_OpList* instructions, IntervalWalker* iw) {
0N/A LIR_OpVisitState visitor;
304N/A int num_inst = instructions->length();
0N/A bool has_dead = false;
0N/A
0N/A for (int j = 0; j < num_inst; j++) {
0N/A LIR_Op* op = instructions->at(j);
0N/A if (op == NULL) { // this can happen when spill-moves are removed in eliminate_spill_moves
0N/A has_dead = true;
304N/A continue;
0N/A }
0N/A int op_id = op->id();
0N/A
0N/A // visit instruction to get list of operands
0N/A visitor.visit(op);
304N/A
304N/A // iterate all modes of the visitor and process all virtual operands
512N/A for_each_visitor_mode(mode) {
512N/A int n = visitor.opr_count(mode);
0N/A for (int k = 0; k < n; k++) {
0N/A LIR_Opr opr = visitor.opr_at(mode, k);
0N/A if (opr->is_virtual_register()) {
0N/A visitor.set_opr_at(mode, k, color_lir_opr(opr, op_id, mode));
304N/A }
304N/A }
0N/A }
0N/A
0N/A if (visitor.info_count() > 0) {
0N/A // exception handling
0N/A if (compilation()->has_exception_handlers()) {
0N/A XHandlers* xhandlers = visitor.all_xhandler();
0N/A int n = xhandlers->length();
0N/A for (int k = 0; k < n; k++) {
0N/A XHandler* handler = xhandlers->handler_at(k);
926N/A if (handler->entry_code() != NULL) {
926N/A assign_reg_num(handler->entry_code()->instructions_list(), NULL);
926N/A }
926N/A }
926N/A } else {
0N/A assert(visitor.all_xhandler()->length() == 0, "missed exception handler");
0N/A }
0N/A
0N/A // compute oop map
0N/A assert(iw != NULL, "needed for compute_oop_map");
0N/A compute_oop_map(iw, visitor, op);
0N/A
0N/A // compute debug information
0N/A if (!use_fpu_stack_allocation()) {
0N/A // compute debug information if fpu stack allocation is not needed.
0N/A // when fpu stack allocation is needed, the debug information can not
0N/A // be computed here because the exact location of fpu operands is not known
0N/A // -> debug information is created inside the fpu stack allocator
0N/A int n = visitor.info_count();
0N/A for (int k = 0; k < n; k++) {
304N/A compute_debug_info(visitor.info_at(k), op_id);
0N/A }
0N/A }
0N/A }
0N/A
0N/A#ifdef ASSERT
0N/A // make sure we haven't made the op invalid.
0N/A op->verify();
0N/A#endif
0N/A
0N/A // remove useless moves
304N/A if (op->code() == lir_move) {
304N/A assert(op->as_Op1() != NULL, "move must be LIR_Op1");
304N/A LIR_Op1* move = (LIR_Op1*)op;
0N/A LIR_Opr src = move->in_opr();
0N/A LIR_Opr dst = move->result_opr();
304N/A if (dst == src ||
0N/A !dst->is_pointer() && !src->is_pointer() &&
0N/A src->is_same_register(dst)) {
0N/A instructions->at_put(j, NULL);
0N/A has_dead = true;
0N/A }
0N/A }
0N/A }
2764N/A
0N/A if (has_dead) {
0N/A // iterate all instructions of the block and remove all null-values.
0N/A int insert_point = 0;
0N/A for (int j = 0; j < num_inst; j++) {
0N/A LIR_Op* op = instructions->at(j);
0N/A if (op != NULL) {
0N/A if (insert_point != j) {
304N/A instructions->at_put(insert_point, op);
304N/A }
304N/A insert_point++;
0N/A }
0N/A }
0N/A instructions->truncate(insert_point);
0N/A }
304N/A}
0N/A
304N/Avoid LinearScan::assign_reg_num() {
0N/A TIME_LINEAR_SCAN(timer_assign_reg_num);
304N/A
304N/A init_compute_debug_info();
0N/A IntervalWalker* iw = init_compute_oop_maps();
304N/A
0N/A int num_blocks = block_count();
0N/A for (int i = 0; i < num_blocks; i++) {
304N/A BlockBegin* block = block_at(i);
0N/A assign_reg_num(block->lir()->instructions_list(), iw);
304N/A }
0N/A}
304N/A
304N/A
0N/Avoid LinearScan::do_linear_scan() {
304N/A NOT_PRODUCT(_total_timer.begin_method());
0N/A
0N/A number_instructions();
0N/A
0N/A NOT_PRODUCT(print_lir(1, "Before Register Allocation"));
512N/A
304N/A compute_local_live_sets();
0N/A compute_global_live_sets();
304N/A CHECK_BAILOUT();
304N/A
304N/A build_intervals();
304N/A CHECK_BAILOUT();
0N/A sort_intervals_before_allocation();
304N/A
0N/A NOT_PRODUCT(print_intervals("Before Register Allocation"));
0N/A NOT_PRODUCT(LinearScanStatistic::compute(this, _stat_before_alloc));
0N/A
0N/A allocate_registers();
0N/A CHECK_BAILOUT();
0N/A
0N/A resolve_data_flow();
304N/A if (compilation()->has_exception_handlers()) {
0N/A resolve_exception_handlers();
0N/A }
304N/A // fill in number of spill slots into frame_map
304N/A propagate_spill_slots();
0N/A CHECK_BAILOUT();
0N/A
0N/A NOT_PRODUCT(print_intervals("After Register Allocation"));
0N/A NOT_PRODUCT(print_lir(2, "LIR after register allocation:"));
0N/A
0N/A sort_intervals_after_allocation();
0N/A
0N/A DEBUG_ONLY(verify());
304N/A
0N/A eliminate_spill_moves();
0N/A assign_reg_num();
0N/A CHECK_BAILOUT();
0N/A
0N/A NOT_PRODUCT(print_lir(2, "LIR after assignment of register numbers:"));
0N/A NOT_PRODUCT(LinearScanStatistic::compute(this, _stat_after_asign));
0N/A
0N/A { TIME_LINEAR_SCAN(timer_allocate_fpu_stack);
0N/A
0N/A if (use_fpu_stack_allocation()) {
0N/A allocate_fpu_stack(); // Only has effect on Intel
0N/A NOT_PRODUCT(print_lir(2, "LIR after FPU stack allocation:"));
304N/A }
0N/A }
0N/A
0N/A { TIME_LINEAR_SCAN(timer_optimize_lir);
0N/A
0N/A EdgeMoveOptimizer::optimize(ir()->code());
304N/A ControlFlowOptimizer::optimize(ir()->code());
304N/A // check that cfg is still correct after optimizations
0N/A ir()->verify();
0N/A }
0N/A
0N/A NOT_PRODUCT(print_lir(1, "Before Code Generation", false));
0N/A NOT_PRODUCT(LinearScanStatistic::compute(this, _stat_final));
0N/A NOT_PRODUCT(_total_timer.end_method(this));
0N/A}
0N/A
0N/A
0N/A// ********** Printing functions
0N/A
0N/A#ifndef PRODUCT
0N/A
0N/Avoid LinearScan::print_timers(double total) {
0N/A _total_timer.print(total);
0N/A}
0N/A
0N/Avoid LinearScan::print_statistics() {
0N/A _stat_before_alloc.print("before allocation");
0N/A _stat_after_asign.print("after assignment of register");
0N/A _stat_final.print("after optimization");
0N/A}
0N/A
0N/Avoid LinearScan::print_bitmap(BitMap& b) {
0N/A for (unsigned int i = 0; i < b.size(); i++) {
0N/A if (b.at(i)) tty->print("%d ", i);
0N/A }
0N/A tty->cr();
0N/A}
0N/A
0N/Avoid LinearScan::print_intervals(const char* label) {
0N/A if (TraceLinearScanLevel >= 1) {
0N/A int i;
0N/A tty->cr();
0N/A tty->print_cr("%s", label);
0N/A
0N/A for (i = 0; i < interval_count(); i++) {
0N/A Interval* interval = interval_at(i);
0N/A if (interval != NULL) {
0N/A interval->print();
0N/A }
0N/A }
0N/A
0N/A tty->cr();
0N/A tty->print_cr("--- Basic Blocks ---");
0N/A for (i = 0; i < block_count(); i++) {
0N/A BlockBegin* block = block_at(i);
0N/A tty->print("B%d [%d, %d, %d, %d] ", block->block_id(), block->first_lir_instruction_id(), block->last_lir_instruction_id(), block->loop_index(), block->loop_depth());
0N/A }
0N/A tty->cr();
0N/A tty->cr();
0N/A }
0N/A
0N/A if (PrintCFGToFile) {
0N/A CFGPrinter::print_intervals(&_intervals, label);
0N/A }
0N/A}
0N/A
0N/Avoid LinearScan::print_lir(int level, const char* label, bool hir_valid) {
0N/A if (TraceLinearScanLevel >= level) {
304N/A tty->cr();
0N/A tty->print_cr("%s", label);
0N/A print_LIR(ir()->linear_scan_order());
0N/A tty->cr();
0N/A }
304N/A
0N/A if (level == 1 && PrintCFGToFile) {
0N/A CFGPrinter::print_cfg(ir()->linear_scan_order(), label, hir_valid, true);
0N/A }
0N/A}
0N/A
0N/A#endif //PRODUCT
0N/A
0N/A
0N/A// ********** verification functions for allocation
0N/A// (check that all intervals have a correct register and that no registers are overwritten)
0N/A#ifdef ASSERT
304N/A
0N/Avoid LinearScan::verify() {
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying intervals ******************************************"));
0N/A verify_intervals();
0N/A
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying that no oops are in fixed intervals ****************"));
0N/A verify_no_oops_in_fixed_intervals();
0N/A
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying that unpinned constants are not alive across block boundaries"));
0N/A verify_constants();
0N/A
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("********* verifying register allocation ********************************"));
0N/A verify_registers();
0N/A
0N/A TRACE_LINEAR_SCAN(2, tty->print_cr("********* no errors found **********************************************"));
0N/A}
0N/A
304N/Avoid LinearScan::verify_intervals() {
0N/A int len = interval_count();
0N/A bool has_error = false;
0N/A
0N/A for (int i = 0; i < len; i++) {
0N/A Interval* i1 = interval_at(i);
0N/A if (i1 == NULL) continue;
0N/A
0N/A i1->check_split_children();
0N/A
304N/A if (i1->reg_num() != i) {
0N/A tty->print_cr("Interval %d is on position %d in list", i1->reg_num(), i); i1->print(); tty->cr();
0N/A has_error = true;
304N/A }
304N/A
0N/A if (i1->reg_num() >= LIR_OprDesc::vreg_base && i1->type() == T_ILLEGAL) {
0N/A tty->print_cr("Interval %d has no type assigned", i1->reg_num()); i1->print(); tty->cr();
0N/A has_error = true;
0N/A }
0N/A
0N/A if (i1->assigned_reg() == any_reg) {
0N/A tty->print_cr("Interval %d has no register assigned", i1->reg_num()); i1->print(); tty->cr();
0N/A has_error = true;
0N/A }
0N/A
0N/A if (i1->assigned_reg() == i1->assigned_regHi()) {
0N/A tty->print_cr("Interval %d: low and high register equal", i1->reg_num()); i1->print(); tty->cr();
0N/A has_error = true;
304N/A }
0N/A
0N/A if (!is_processed_reg_num(i1->assigned_reg())) {
304N/A tty->print_cr("Can not have an Interval for an ignored register"); i1->print(); tty->cr();
0N/A has_error = true;
0N/A }
0N/A
0N/A if (i1->first() == Range::end()) {
0N/A tty->print_cr("Interval %d has no Range", i1->reg_num()); i1->print(); tty->cr();
0N/A has_error = true;
0N/A }
2764N/A
0N/A for (Range* r = i1->first(); r != Range::end(); r = r->next()) {
0N/A if (r->from() >= r->to()) {
0N/A tty->print_cr("Interval %d has zero length range", i1->reg_num()); i1->print(); tty->cr();
0N/A has_error = true;
0N/A }
0N/A }
0N/A
304N/A for (int j = i + 1; j < len; j++) {
304N/A Interval* i2 = interval_at(j);
304N/A if (i2 == NULL) continue;
0N/A
0N/A // special intervals that are created in MoveResolver
0N/A // -> ignore them because the range information has no meaning there
0N/A if (i1->from() == 1 && i1->to() == 2) continue;
304N/A if (i2->from() == 1 && i2->to() == 2) continue;
0N/A
304N/A int r1 = i1->assigned_reg();
0N/A int r1Hi = i1->assigned_regHi();
304N/A int r2 = i2->assigned_reg();
304N/A int r2Hi = i2->assigned_regHi();
0N/A if (i1->intersects(i2) && (r1 == r2 || r1 == r2Hi || (r1Hi != any_reg && (r1Hi == r2 || r1Hi == r2Hi)))) {
304N/A tty->print_cr("Intervals %d and %d overlap and have the same register assigned", i1->reg_num(), i2->reg_num());
0N/A i1->print(); tty->cr();
0N/A i2->print(); tty->cr();
304N/A has_error = true;
0N/A }
304N/A }
0N/A }
304N/A
304N/A assert(has_error == false, "register allocation invalid");
0N/A}
304N/A
0N/A
0N/Avoid LinearScan::verify_no_oops_in_fixed_intervals() {
0N/A Interval* fixed_intervals;
0N/A Interval* other_intervals;
512N/A create_unhandled_lists(&fixed_intervals, &other_intervals, is_precolored_cpu_interval, NULL);
304N/A
0N/A // to ensure a walking until the last instruction id, add a dummy interval
304N/A // with a high operation id
304N/A other_intervals = new Interval(any_reg);
304N/A other_intervals->add_range(max_jint - 2, max_jint - 1);
304N/A IntervalWalker* iw = new IntervalWalker(this, fixed_intervals, other_intervals);
0N/A
304N/A LIR_OpVisitState visitor;
0N/A for (int i = 0; i < block_count(); i++) {
0N/A BlockBegin* block = block_at(i);
0N/A
304N/A LIR_OpList* instructions = block->lir()->instructions_list();
0N/A
0N/A for (int j = 0; j < instructions->length(); j++) {
0N/A LIR_Op* op = instructions->at(j);
0N/A int op_id = op->id();
0N/A
0N/A visitor.visit(op);
0N/A
0N/A if (visitor.info_count() > 0) {
0N/A iw->walk_before(op->id());
304N/A bool check_live = true;
0N/A if (op->code() == lir_move) {
0N/A LIR_Op1* move = (LIR_Op1*)op;
0N/A check_live = (move->patch_code() == lir_patch_none);
0N/A }
0N/A LIR_OpBranch* branch = op->as_OpBranch();
0N/A if (branch != NULL && branch->stub() != NULL && branch->stub()->is_exception_throw_stub()) {
0N/A // Don't bother checking the stub in this case since the
0N/A // exception stub will never return to normal control flow.
0N/A check_live = false;
0N/A }
0N/A
0N/A // Make sure none of the fixed registers is live across an
0N/A // oopmap since we can't handle that correctly.
0N/A if (check_live) {
0N/A for (Interval* interval = iw->active_first(fixedKind);
0N/A interval != Interval::end();
0N/A interval = interval->next()) {
0N/A if (interval->current_to() > op->id() + 1) {
0N/A // This interval is live out of this op so make sure
0N/A // that this interval represents some value that's
0N/A // referenced by this op either as an input or output.
0N/A bool ok = false;
0N/A for_each_visitor_mode(mode) {
0N/A int n = visitor.opr_count(mode);
0N/A for (int k = 0; k < n; k++) {
0N/A LIR_Opr opr = visitor.opr_at(mode, k);
0N/A if (opr->is_fixed_cpu()) {
Error!

 

There was an error!

null

java.lang.NullPointerException