|
/*
* Copyright (c) 2005, 2022, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "c1/c1_CFGPrinter.hpp"
#include "c1/c1_CodeStubs.hpp"
#include "c1/c1_Compilation.hpp"
#include "c1/c1_FrameMap.hpp"
#include "c1/c1_IR.hpp"
#include "c1/c1_LIRGenerator.hpp"
#include "c1/c1_LinearScan.hpp"
#include "c1/c1_ValueStack.hpp"
#include "code/vmreg.inline.hpp"
#include "runtime/timerTrace.hpp"
#include "utilities/bitMap.inline.hpp"
#ifndef PRODUCT
static LinearScanStatistic _stat_before_alloc;
static LinearScanStatistic _stat_after_asign;
static LinearScanStatistic _stat_final;
static LinearScanTimers _total_timer;
// helper macro for short definition of timer
#define TIME_LINEAR_SCAN(timer_name) TraceTime _block_timer("", _total_timer.timer(LinearScanTimers::timer_name), TimeLinearScan || TimeEachLinearScan, Verbose);
#else
#define TIME_LINEAR_SCAN(timer_name)
#endif
#ifdef ASSERT
// helper macro for short definition of trace-output inside code
#define TRACE_LINEAR_SCAN(level, code) \
if (TraceLinearScanLevel >= level) { \
code; \
}
#else
#define TRACE_LINEAR_SCAN(level, code)
#endif
// Map BasicType to spill size in 32-bit words, matching VMReg's notion of words
#ifdef _LP64
static int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 0, 2, 1, 2, 1, -1};
#else
static int type2spill_size[T_CONFLICT+1]={ -1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0, 1, -1, 1, 1, -1};
#endif
// Implementation of LinearScan
LinearScan::LinearScan(IR* ir, LIRGenerator* gen, FrameMap* frame_map)
: _compilation(ir->compilation())
, _ir(ir)
, _gen(gen)
, _frame_map(frame_map)
, _cached_blocks(*ir->linear_scan_order())
, _num_virtual_regs(gen->max_virtual_register_number())
, _has_fpu_registers(false)
, _num_calls(-1)
, _max_spills(0)
, _unused_spill_slot(-1)
, _intervals(0) // initialized later with correct length
, _new_intervals_from_allocation(NULL)
, _sorted_intervals(NULL)
, _needs_full_resort(false)
, _lir_ops(0) // initialized later with correct length
, _block_of_op(0) // initialized later with correct length
, _has_info(0)
, _has_call(0)
, _interval_in_loop(0) // initialized later with correct length
, _scope_value_cache(0) // initialized later with correct length
#ifdef IA32
, _fpu_stack_allocator(NULL)
#endif
{
assert(this->ir() != NULL, "check if valid");
assert(this->compilation() != NULL, "check if valid");
assert(this->gen() != NULL, "check if valid");
assert(this->frame_map() != NULL, "check if valid");
}
// ********** functions for converting LIR-Operands to register numbers
//
// Emulate a flat register file comprising physical integer registers,
// physical floating-point registers and virtual registers, in that order.
// Virtual registers already have appropriate numbers, since V0 is
// the number of physical registers.
// Returns -1 for hi word if opr is a single word operand.
//
// Note: the inverse operation (calculating an operand for register numbers)
// is done in calc_operand_for_interval()
int LinearScan::reg_num(LIR_Opr opr) {
assert(opr->is_register(), "should not call this otherwise");
if (opr->is_virtual_register()) {
assert(opr->vreg_number() >= nof_regs, "found a virtual register with a fixed-register number");
return opr->vreg_number();
} else if (opr->is_single_cpu()) {
return opr->cpu_regnr();
} else if (opr->is_double_cpu()) {
return opr->cpu_regnrLo();
#ifdef X86
} else if (opr->is_single_xmm()) {
return opr->fpu_regnr() + pd_first_xmm_reg;
} else if (opr->is_double_xmm()) {
return opr->fpu_regnrLo() + pd_first_xmm_reg;
#endif
} else if (opr->is_single_fpu()) {
return opr->fpu_regnr() + pd_first_fpu_reg;
} else if (opr->is_double_fpu()) {
return opr->fpu_regnrLo() + pd_first_fpu_reg;
} else {
ShouldNotReachHere();
return -1;
}
}
int LinearScan::reg_numHi(LIR_Opr opr) {
assert(opr->is_register(), "should not call this otherwise");
if (opr->is_virtual_register()) {
return -1;
} else if (opr->is_single_cpu()) {
return -1;
} else if (opr->is_double_cpu()) {
return opr->cpu_regnrHi();
#ifdef X86
} else if (opr->is_single_xmm()) {
return -1;
} else if (opr->is_double_xmm()) {
return -1;
#endif
} else if (opr->is_single_fpu()) {
return -1;
} else if (opr->is_double_fpu()) {
return opr->fpu_regnrHi() + pd_first_fpu_reg;
} else {
ShouldNotReachHere();
return -1;
}
}
// ********** functions for classification of intervals
bool LinearScan::is_precolored_interval(const Interval* i) {
return i->reg_num() < LinearScan::nof_regs;
}
bool LinearScan::is_virtual_interval(const Interval* i) {
return i->reg_num() >= LIR_Opr::vreg_base;
}
bool LinearScan::is_precolored_cpu_interval(const Interval* i) {
return i->reg_num() < LinearScan::nof_cpu_regs;
}
bool LinearScan::is_virtual_cpu_interval(const Interval* i) {
#if defined(__SOFTFP__) || defined(E500V2)
return i->reg_num() >= LIR_Opr::vreg_base;
#else
return i->reg_num() >= LIR_Opr::vreg_base && (i->type() != T_FLOAT && i->type() != T_DOUBLE);
#endif // __SOFTFP__ or E500V2
}
bool LinearScan::is_precolored_fpu_interval(const Interval* i) {
return i->reg_num() >= LinearScan::nof_cpu_regs && i->reg_num() < LinearScan::nof_regs;
}
bool LinearScan::is_virtual_fpu_interval(const Interval* i) {
#if defined(__SOFTFP__) || defined(E500V2)
return false;
#else
return i->reg_num() >= LIR_Opr::vreg_base && (i->type() == T_FLOAT || i->type() == T_DOUBLE);
#endif // __SOFTFP__ or E500V2
}
bool LinearScan::is_in_fpu_register(const Interval* i) {
// fixed intervals not needed for FPU stack allocation
return i->reg_num() >= nof_regs && pd_first_fpu_reg <= i->assigned_reg() && i->assigned_reg() <= pd_last_fpu_reg;
}
bool LinearScan::is_oop_interval(const Interval* i) {
// fixed intervals never contain oops
return i->reg_num() >= nof_regs && i->type() == T_OBJECT;
}
// ********** General helper functions
// compute next unused stack index that can be used for spilling
int LinearScan::allocate_spill_slot(bool double_word) {
int spill_slot;
if (double_word) {
if ((_max_spills & 1) == 1) {
// alignment of double-word values
// the hole because of the alignment is filled with the next single-word value
assert(_unused_spill_slot == -1, "wasting a spill slot");
_unused_spill_slot = _max_spills;
_max_spills++;
}
spill_slot = _max_spills;
_max_spills += 2;
} else if (_unused_spill_slot != -1) {
// re-use hole that was the result of a previous double-word alignment
spill_slot = _unused_spill_slot;
_unused_spill_slot = -1;
} else {
spill_slot = _max_spills;
_max_spills++;
}
int result = spill_slot + LinearScan::nof_regs + frame_map()->argcount();
// if too many slots used, bailout compilation.
if (result > 2000) {
bailout("too many stack slots used");
}
return result;
}
void LinearScan::assign_spill_slot(Interval* it) {
// assign the canonical spill slot of the parent (if a part of the interval
// is already spilled) or allocate a new spill slot
if (it->canonical_spill_slot() >= 0) {
it->assign_reg(it->canonical_spill_slot());
} else {
int spill = allocate_spill_slot(type2spill_size[it->type()] == 2);
it->set_canonical_spill_slot(spill);
it->assign_reg(spill);
}
}
void LinearScan::propagate_spill_slots() {
if (!frame_map()->finalize_frame(max_spills())) {
bailout("frame too large");
}
}
// create a new interval with a predefined reg_num
// (only used for parent intervals that are created during the building phase)
Interval* LinearScan::create_interval(int reg_num) {
assert(_intervals.at(reg_num) == NULL, "overwriting existing interval");
Interval* interval = new Interval(reg_num);
_intervals.at_put(reg_num, interval);
// assign register number for precolored intervals
if (reg_num < LIR_Opr::vreg_base) {
interval->assign_reg(reg_num);
}
return interval;
}
// assign a new reg_num to the interval and append it to the list of intervals
// (only used for child intervals that are created during register allocation)
void LinearScan::append_interval(Interval* it) {
it->set_reg_num(_intervals.length());
_intervals.append(it);
IntervalList* new_intervals = _new_intervals_from_allocation;
if (new_intervals == NULL) {
new_intervals = _new_intervals_from_allocation = new IntervalList();
}
new_intervals->append(it);
}
// copy the vreg-flags if an interval is split
void LinearScan::copy_register_flags(Interval* from, Interval* to) {
if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::byte_reg)) {
gen()->set_vreg_flag(to->reg_num(), LIRGenerator::byte_reg);
}
if (gen()->is_vreg_flag_set(from->reg_num(), LIRGenerator::callee_saved)) {
gen()->set_vreg_flag(to->reg_num(), LIRGenerator::callee_saved);
}
// Note: do not copy the must_start_in_memory flag because it is not necessary for child
// intervals (only the very beginning of the interval must be in memory)
}
// ********** spill move optimization
// eliminate moves from register to stack if stack slot is known to be correct
// called during building of intervals
void LinearScan::change_spill_definition_pos(Interval* interval, int def_pos) {
assert(interval->is_split_parent(), "can only be called for split parents");
switch (interval->spill_state()) {
case noDefinitionFound:
assert(interval->spill_definition_pos() == -1, "must no be set before");
interval->set_spill_definition_pos(def_pos);
interval->set_spill_state(oneDefinitionFound);
break;
case oneDefinitionFound:
assert(def_pos <= interval->spill_definition_pos(), "positions are processed in reverse order when intervals are created");
if (def_pos < interval->spill_definition_pos() - 2) {
// second definition found, so no spill optimization possible for this interval
interval->set_spill_state(noOptimization);
} else {
// two consecutive definitions (because of two-operand LIR form)
assert(block_of_op_with_id(def_pos) == block_of_op_with_id(interval->spill_definition_pos()), "block must be equal");
}
break;
case noOptimization:
// nothing to do
break;
default:
assert(false, "other states not allowed at this time");
}
}
// called during register allocation
void LinearScan::change_spill_state(Interval* interval, int spill_pos) {
switch (interval->spill_state()) {
case oneDefinitionFound: {
int def_loop_depth = block_of_op_with_id(interval->spill_definition_pos())->loop_depth();
int spill_loop_depth = block_of_op_with_id(spill_pos)->loop_depth();
if (def_loop_depth < spill_loop_depth) {
// the loop depth of the spilling position is higher then the loop depth
// at the definition of the interval -> move write to memory out of loop
// by storing at definitin of the interval
interval->set_spill_state(storeAtDefinition);
} else {
// the interval is currently spilled only once, so for now there is no
// reason to store the interval at the definition
interval->set_spill_state(oneMoveInserted);
}
break;
}
case oneMoveInserted: {
// the interval is spilled more then once, so it is better to store it to
// memory at the definition
interval->set_spill_state(storeAtDefinition);
break;
}
case storeAtDefinition:
case startInMemory:
case noOptimization:
case noDefinitionFound:
// nothing to do
break;
default:
assert(false, "other states not allowed at this time");
}
}
bool LinearScan::must_store_at_definition(const Interval* i) {
return i->is_split_parent() && i->spill_state() == storeAtDefinition;
}
// called once before assignment of register numbers
void LinearScan::eliminate_spill_moves() {
TIME_LINEAR_SCAN(timer_eliminate_spill_moves);
TRACE_LINEAR_SCAN(3, tty->print_cr("***** Eliminating unnecessary spill moves"));
// collect all intervals that must be stored after their definion.
// the list is sorted by Interval::spill_definition_pos
Interval* interval;
Interval* temp_list;
create_unhandled_lists(&interval, &temp_list, must_store_at_definition, NULL);
#ifdef ASSERT
Interval* prev = NULL;
Interval* temp = interval;
while (temp != Interval::end()) {
assert(temp->spill_definition_pos() > 0, "invalid spill definition pos");
if (prev != NULL) {
assert(temp->from() >= prev->from(), "intervals not sorted");
assert(temp->spill_definition_pos() >= prev->spill_definition_pos(), "when intervals are sorted by from, then they must also be sorted by spill_definition_pos");
}
assert(temp->canonical_spill_slot() >= LinearScan::nof_regs, "interval has no spill slot assigned");
assert(temp->spill_definition_pos() >= temp->from(), "invalid order");
assert(temp->spill_definition_pos() <= temp->from() + 2, "only intervals defined once at their start-pos can be optimized");
TRACE_LINEAR_SCAN(4, tty->print_cr("interval %d (from %d to %d) must be stored at %d", temp->reg_num(), temp->from(), temp->to(), temp->spill_definition_pos()));
temp = temp->next();
}
#endif
LIR_InsertionBuffer insertion_buffer;
int num_blocks = block_count();
for (int i = 0; i < num_blocks; i++) {
BlockBegin* block = block_at(i);
LIR_OpList* instructions = block->lir()->instructions_list();
int num_inst = instructions->length();
bool has_new = false;
// iterate all instructions of the block. skip the first because it is always a label
for (int j = 1; j < num_inst; j++) {
LIR_Op* op = instructions->at(j);
int op_id = op->id();
if (op_id == -1) {
// remove move from register to stack if the stack slot is guaranteed to be correct.
// only moves that have been inserted by LinearScan can be removed.
assert(op->code() == lir_move, "only moves can have a op_id of -1");
assert(op->as_Op1() != NULL, "move must be LIR_Op1");
assert(op->as_Op1()->result_opr()->is_virtual(), "LinearScan inserts only moves to virtual registers");
LIR_Op1* op1 = (LIR_Op1*)op;
Interval* interval = interval_at(op1->result_opr()->vreg_number());
if (interval->assigned_reg() >= LinearScan::nof_regs && interval->always_in_memory()) {
// move target is a stack slot that is always correct, so eliminate instruction
TRACE_LINEAR_SCAN(4, tty->print_cr("eliminating move from interval %d to %d", op1->in_opr()->vreg_number(), op1->result_opr()->vreg_number()));
instructions->at_put(j, NULL); // NULL-instructions are deleted by assign_reg_num
}
} else {
// insert move from register to stack just after the beginning of the interval
assert(interval == Interval::end() || interval->spill_definition_pos() >= op_id, "invalid order");
assert(interval == Interval::end() || (interval->is_split_parent() && interval->spill_state() == storeAtDefinition), "invalid interval");
while (interval != Interval::end() && interval->spill_definition_pos() == op_id) {
if (!has_new) {
// prepare insertion buffer (appended when all instructions of the block are processed)
insertion_buffer.init(block->lir());
has_new = true;
}
LIR_Opr from_opr = operand_for_interval(interval);
LIR_Opr to_opr = canonical_spill_opr(interval);
assert(from_opr->is_fixed_cpu() || from_opr->is_fixed_fpu(), "from operand must be a register");
assert(to_opr->is_stack(), "to operand must be a stack slot");
insertion_buffer.move(j, from_opr, to_opr);
TRACE_LINEAR_SCAN(4, tty->print_cr("inserting move after definition of interval %d to stack slot %d at op_id %d", interval->reg_num(), interval->canonical_spill_slot() - LinearScan::nof_regs, op_id));
interval = interval->next();
}
}
} // end of instruction iteration
if (has_new) {
block->lir()->append(&insertion_buffer);
}
} // end of block iteration
assert(interval == Interval::end(), "missed an interval");
}
// ********** Phase 1: number all instructions in all blocks
// Compute depth-first and linear scan block orders, and number LIR_Op nodes for linear scan.
void LinearScan::number_instructions() {
{
// dummy-timer to measure the cost of the timer itself
// (this time is then subtracted from all other timers to get the real value)
TIME_LINEAR_SCAN(timer_do_nothing);
}
TIME_LINEAR_SCAN(timer_number_instructions);
// Assign IDs to LIR nodes and build a mapping, lir_ops, from ID to LIR_Op node.
int num_blocks = block_count();
int num_instructions = 0;
int i;
for (i = 0; i < num_blocks; i++) {
num_instructions += block_at(i)->lir()->instructions_list()->length();
}
// initialize with correct length
_lir_ops = LIR_OpArray(num_instructions, num_instructions, NULL);
_block_of_op = BlockBeginArray(num_instructions, num_instructions, NULL);
int op_id = 0;
int idx = 0;
for (i = 0; i < num_blocks; i++) {
BlockBegin* block = block_at(i);
block->set_first_lir_instruction_id(op_id);
LIR_OpList* instructions = block->lir()->instructions_list();
int num_inst = instructions->length();
for (int j = 0; j < num_inst; j++) {
LIR_Op* op = instructions->at(j);
op->set_id(op_id);
_lir_ops.at_put(idx, op);
_block_of_op.at_put(idx, block);
assert(lir_op_with_id(op_id) == op, "must match");
idx++;
op_id += 2; // numbering of lir_ops by two
}
block->set_last_lir_instruction_id(op_id - 2);
}
assert(idx == num_instructions, "must match");
assert(idx * 2 == op_id, "must match");
_has_call.initialize(num_instructions);
_has_info.initialize(num_instructions);
}
// ********** Phase 2: compute local live sets separately for each block
// (sets live_gen and live_kill for each block)
void LinearScan::set_live_gen_kill(Value value, LIR_Op* op, BitMap& live_gen, BitMap& live_kill) {
LIR_Opr opr = value->operand();
Constant* con = value->as_Constant();
// check some asumptions about debug information
assert(!value->type()->is_illegal(), "if this local is used by the interpreter it shouldn't be of indeterminate type");
assert(con == NULL || opr->is_virtual() || opr->is_constant() || opr->is_illegal(), "assumption: Constant instructions have only constant operands");
assert(con != NULL || opr->is_virtual(), "assumption: non-Constant instructions have only virtual operands");
if ((con == NULL || con->is_pinned()) && opr->is_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
int reg = opr->vreg_number();
if (!live_kill.at(reg)) {
live_gen.set_bit(reg);
TRACE_LINEAR_SCAN(4, tty->print_cr(" Setting live_gen for value %c%d, LIR op_id %d, register number %d", value->type()->tchar(), value->id(), op->id(), reg));
}
}
}
void LinearScan::compute_local_live_sets() {
TIME_LINEAR_SCAN(timer_compute_local_live_sets);
int num_blocks = block_count();
int live_size = live_set_size();
bool local_has_fpu_registers = false;
int local_num_calls = 0;
LIR_OpVisitState visitor;
BitMap2D local_interval_in_loop = BitMap2D(_num_virtual_regs, num_loops());
// iterate all blocks
for (int i = 0; i < num_blocks; i++) {
BlockBegin* block = block_at(i);
ResourceBitMap live_gen(live_size);
ResourceBitMap live_kill(live_size);
if (block->is_set(BlockBegin::exception_entry_flag)) {
// Phi functions at the begin of an exception handler are
// implicitly defined (= killed) at the beginning of the block.
for_each_phi_fun(block, phi,
if (!phi->is_illegal()) { live_kill.set_bit(phi->operand()->vreg_number()); }
);
}
LIR_OpList* instructions = block->lir()->instructions_list();
int num_inst = instructions->length();
// iterate all instructions of the block. skip the first because it is always a label
assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
for (int j = 1; j < num_inst; j++) {
LIR_Op* op = instructions->at(j);
// visit operation to collect all operands
visitor.visit(op);
if (visitor.has_call()) {
_has_call.set_bit(op->id() >> 1);
local_num_calls++;
}
if (visitor.info_count() > 0) {
_has_info.set_bit(op->id() >> 1);
}
// iterate input operands of instruction
int k, n, reg;
n = visitor.opr_count(LIR_OpVisitState::inputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
assert(opr->is_register(), "visitor should only return register operands");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
reg = opr->vreg_number();
if (!live_kill.at(reg)) {
live_gen.set_bit(reg);
TRACE_LINEAR_SCAN(4, tty->print_cr(" Setting live_gen for register %d at instruction %d", reg, op->id()));
}
if (block->loop_index() >= 0) {
local_interval_in_loop.set_bit(reg, block->loop_index());
}
local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
}
#ifdef ASSERT
// fixed intervals are never live at block boundaries, so
// they need not be processed in live sets.
// this is checked by these assertions to be sure about it.
// the entry block may have incoming values in registers, which is ok.
if (!opr->is_virtual_register() && block != ir()->start()) {
reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
assert(live_kill.at(reg), "using fixed register that is not defined in this block");
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
assert(live_kill.at(reg), "using fixed register that is not defined in this block");
}
}
#endif
}
// Add uses of live locals from interpreter's point of view for proper debug information generation
n = visitor.info_count();
for (k = 0; k < n; k++) {
CodeEmitInfo* info = visitor.info_at(k);
ValueStack* stack = info->stack();
for_each_state_value(stack, value,
set_live_gen_kill(value, op, live_gen, live_kill);
local_has_fpu_registers = local_has_fpu_registers || value->type()->is_float_kind();
);
}
// iterate temp operands of instruction
n = visitor.opr_count(LIR_OpVisitState::tempMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
assert(opr->is_register(), "visitor should only return register operands");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
reg = opr->vreg_number();
live_kill.set_bit(reg);
if (block->loop_index() >= 0) {
local_interval_in_loop.set_bit(reg, block->loop_index());
}
local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
}
#ifdef ASSERT
// fixed intervals are never live at block boundaries, so
// they need not be processed in live sets
// process them only in debug mode so that this can be checked
if (!opr->is_virtual_register()) {
reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
live_kill.set_bit(reg_num(opr));
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
live_kill.set_bit(reg);
}
}
#endif
}
// iterate output operands of instruction
n = visitor.opr_count(LIR_OpVisitState::outputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::outputMode, k);
assert(opr->is_register(), "visitor should only return register operands");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
reg = opr->vreg_number();
live_kill.set_bit(reg);
if (block->loop_index() >= 0) {
local_interval_in_loop.set_bit(reg, block->loop_index());
}
local_has_fpu_registers = local_has_fpu_registers || opr->is_virtual_fpu();
}
#ifdef ASSERT
// fixed intervals are never live at block boundaries, so
// they need not be processed in live sets
// process them only in debug mode so that this can be checked
if (!opr->is_virtual_register()) {
reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
live_kill.set_bit(reg_num(opr));
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
live_kill.set_bit(reg);
}
}
#endif
}
} // end of instruction iteration
block->set_live_gen (live_gen);
block->set_live_kill(live_kill);
block->set_live_in (ResourceBitMap(live_size));
block->set_live_out (ResourceBitMap(live_size));
TRACE_LINEAR_SCAN(4, tty->print("live_gen B%d ", block->block_id()); print_bitmap(block->live_gen()));
TRACE_LINEAR_SCAN(4, tty->print("live_kill B%d ", block->block_id()); print_bitmap(block->live_kill()));
} // end of block iteration
// propagate local calculated information into LinearScan object
_has_fpu_registers = local_has_fpu_registers;
compilation()->set_has_fpu_code(local_has_fpu_registers);
_num_calls = local_num_calls;
_interval_in_loop = local_interval_in_loop;
}
// ********** Phase 3: perform a backward dataflow analysis to compute global live sets
// (sets live_in and live_out for each block)
void LinearScan::compute_global_live_sets() {
TIME_LINEAR_SCAN(timer_compute_global_live_sets);
int num_blocks = block_count();
bool change_occurred;
bool change_occurred_in_block;
int iteration_count = 0;
ResourceBitMap live_out(live_set_size()); // scratch set for calculations
// Perform a backward dataflow analysis to compute live_out and live_in for each block.
// The loop is executed until a fixpoint is reached (no changes in an iteration)
// Exception handlers must be processed because not all live values are
// present in the state array, e.g. because of global value numbering
do {
change_occurred = false;
// iterate all blocks in reverse order
for (int i = num_blocks - 1; i >= 0; i--) {
BlockBegin* block = block_at(i);
change_occurred_in_block = false;
// live_out(block) is the union of live_in(sux), for successors sux of block
int n = block->number_of_sux();
int e = block->number_of_exception_handlers();
if (n + e > 0) {
// block has successors
if (n > 0) {
live_out.set_from(block->sux_at(0)->live_in());
for (int j = 1; j < n; j++) {
live_out.set_union(block->sux_at(j)->live_in());
}
} else {
live_out.clear();
}
for (int j = 0; j < e; j++) {
live_out.set_union(block->exception_handler_at(j)->live_in());
}
if (!block->live_out().is_same(live_out)) {
// A change occurred. Swap the old and new live out sets to avoid copying.
ResourceBitMap temp = block->live_out();
block->set_live_out(live_out);
live_out = temp;
change_occurred = true;
change_occurred_in_block = true;
}
}
if (iteration_count == 0 || change_occurred_in_block) {
// live_in(block) is the union of live_gen(block) with (live_out(block) & !live_kill(block))
// note: live_in has to be computed only in first iteration or if live_out has changed!
ResourceBitMap live_in = block->live_in();
live_in.set_from(block->live_out());
live_in.set_difference(block->live_kill());
live_in.set_union(block->live_gen());
}
#ifdef ASSERT
if (TraceLinearScanLevel >= 4) {
char c = ' ';
if (iteration_count == 0 || change_occurred_in_block) {
c = '*';
}
tty->print("(%d) live_in%c B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_in());
tty->print("(%d) live_out%c B%d ", iteration_count, c, block->block_id()); print_bitmap(block->live_out());
}
#endif
}
iteration_count++;
if (change_occurred && iteration_count > 50) {
BAILOUT("too many iterations in compute_global_live_sets");
}
} while (change_occurred);
#ifdef ASSERT
// check that fixed intervals are not live at block boundaries
// (live set must be empty at fixed intervals)
for (int i = 0; i < num_blocks; i++) {
BlockBegin* block = block_at(i);
for (int j = 0; j < LIR_Opr::vreg_base; j++) {
assert(block->live_in().at(j) == false, "live_in set of fixed register must be empty");
assert(block->live_out().at(j) == false, "live_out set of fixed register must be empty");
assert(block->live_gen().at(j) == false, "live_gen set of fixed register must be empty");
}
}
#endif
// check that the live_in set of the first block is empty
ResourceBitMap live_in_args(ir()->start()->live_in().size());
if (!ir()->start()->live_in().is_same(live_in_args)) {
#ifdef ASSERT
tty->print_cr("Error: live_in set of first block must be empty (when this fails, virtual registers are used before they are defined)");
tty->print_cr("affected registers:");
print_bitmap(ir()->start()->live_in());
// print some additional information to simplify debugging
for (unsigned int i = 0; i < ir()->start()->live_in().size(); i++) {
if (ir()->start()->live_in().at(i)) {
Instruction* instr = gen()->instruction_for_vreg(i);
tty->print_cr("* vreg %d (HIR instruction %c%d)", i, instr == NULL ? ' ' : instr->type()->tchar(), instr == NULL ? 0 : instr->id());
for (int j = 0; j < num_blocks; j++) {
BlockBegin* block = block_at(j);
if (block->live_gen().at(i)) {
tty->print_cr(" used in block B%d", block->block_id());
}
if (block->live_kill().at(i)) {
tty->print_cr(" defined in block B%d", block->block_id());
}
}
}
}
#endif
// when this fails, virtual registers are used before they are defined.
assert(false, "live_in set of first block must be empty");
// bailout of if this occurs in product mode.
bailout("live_in set of first block not empty");
}
}
// ********** Phase 4: build intervals
// (fills the list _intervals)
void LinearScan::add_use(Value value, int from, int to, IntervalUseKind use_kind) {
assert(!value->type()->is_illegal(), "if this value is used by the interpreter it shouldn't be of indeterminate type");
LIR_Opr opr = value->operand();
Constant* con = value->as_Constant();
if ((con == NULL || con->is_pinned()) && opr->is_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
add_use(opr, from, to, use_kind);
}
}
void LinearScan::add_def(LIR_Opr opr, int def_pos, IntervalUseKind use_kind) {
TRACE_LINEAR_SCAN(2, tty->print(" def "); opr->print(tty); tty->print_cr(" def_pos %d (%d)", def_pos, use_kind));
assert(opr->is_register(), "should not be called otherwise");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
add_def(opr->vreg_number(), def_pos, use_kind, opr->type_register());
} else {
int reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
add_def(reg, def_pos, use_kind, opr->type_register());
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
add_def(reg, def_pos, use_kind, opr->type_register());
}
}
}
void LinearScan::add_use(LIR_Opr opr, int from, int to, IntervalUseKind use_kind) {
TRACE_LINEAR_SCAN(2, tty->print(" use "); opr->print(tty); tty->print_cr(" from %d to %d (%d)", from, to, use_kind));
assert(opr->is_register(), "should not be called otherwise");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
add_use(opr->vreg_number(), from, to, use_kind, opr->type_register());
} else {
int reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
add_use(reg, from, to, use_kind, opr->type_register());
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
add_use(reg, from, to, use_kind, opr->type_register());
}
}
}
void LinearScan::add_temp(LIR_Opr opr, int temp_pos, IntervalUseKind use_kind) {
TRACE_LINEAR_SCAN(2, tty->print(" temp "); opr->print(tty); tty->print_cr(" temp_pos %d (%d)", temp_pos, use_kind));
assert(opr->is_register(), "should not be called otherwise");
if (opr->is_virtual_register()) {
assert(reg_num(opr) == opr->vreg_number() && !is_valid_reg_num(reg_numHi(opr)), "invalid optimization below");
add_temp(opr->vreg_number(), temp_pos, use_kind, opr->type_register());
} else {
int reg = reg_num(opr);
if (is_processed_reg_num(reg)) {
add_temp(reg, temp_pos, use_kind, opr->type_register());
}
reg = reg_numHi(opr);
if (is_valid_reg_num(reg) && is_processed_reg_num(reg)) {
add_temp(reg, temp_pos, use_kind, opr->type_register());
}
}
}
void LinearScan::add_def(int reg_num, int def_pos, IntervalUseKind use_kind, BasicType type) {
Interval* interval = interval_at(reg_num);
if (interval != NULL) {
assert(interval->reg_num() == reg_num, "wrong interval");
if (type != T_ILLEGAL) {
interval->set_type(type);
}
Range* r = interval->first();
if (r->from() <= def_pos) {
// Update the starting point (when a range is first created for a use, its
// start is the beginning of the current block until a def is encountered.)
r->set_from(def_pos);
interval->add_use_pos(def_pos, use_kind);
} else {
// Dead value - make vacuous interval
// also add use_kind for dead intervals
interval->add_range(def_pos, def_pos + 1);
interval->add_use_pos(def_pos, use_kind);
TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: def of reg %d at %d occurs without use", reg_num, def_pos));
}
} else {
// Dead value - make vacuous interval
// also add use_kind for dead intervals
interval = create_interval(reg_num);
if (type != T_ILLEGAL) {
interval->set_type(type);
}
interval->add_range(def_pos, def_pos + 1);
interval->add_use_pos(def_pos, use_kind);
TRACE_LINEAR_SCAN(2, tty->print_cr("Warning: dead value %d at %d in live intervals", reg_num, def_pos));
}
change_spill_definition_pos(interval, def_pos);
if (use_kind == noUse && interval->spill_state() <= startInMemory) {
// detection of method-parameters and roundfp-results
// TODO: move this directly to position where use-kind is computed
interval->set_spill_state(startInMemory);
}
}
void LinearScan::add_use(int reg_num, int from, int to, IntervalUseKind use_kind, BasicType type) {
Interval* interval = interval_at(reg_num);
if (interval == NULL) {
interval = create_interval(reg_num);
}
assert(interval->reg_num() == reg_num, "wrong interval");
if (type != T_ILLEGAL) {
interval->set_type(type);
}
interval->add_range(from, to);
interval->add_use_pos(to, use_kind);
}
void LinearScan::add_temp(int reg_num, int temp_pos, IntervalUseKind use_kind, BasicType type) {
Interval* interval = interval_at(reg_num);
if (interval == NULL) {
interval = create_interval(reg_num);
}
assert(interval->reg_num() == reg_num, "wrong interval");
if (type != T_ILLEGAL) {
interval->set_type(type);
}
interval->add_range(temp_pos, temp_pos + 1);
interval->add_use_pos(temp_pos, use_kind);
}
// the results of this functions are used for optimizing spilling and reloading
// if the functions return shouldHaveRegister and the interval is spilled,
// it is not reloaded to a register.
IntervalUseKind LinearScan::use_kind_of_output_operand(LIR_Op* op, LIR_Opr opr) {
if (op->code() == lir_move) {
assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
LIR_Op1* move = (LIR_Op1*)op;
LIR_Opr res = move->result_opr();
bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);
if (result_in_memory) {
// Begin of an interval with must_start_in_memory set.
// This interval will always get a stack slot first, so return noUse.
return noUse;
} else if (move->in_opr()->is_stack()) {
// method argument (condition must be equal to handle_method_arguments)
return noUse;
} else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
// Move from register to register
if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
// special handling of phi-function moves inside osr-entry blocks
// input operand must have a register instead of output operand (leads to better register allocation)
return shouldHaveRegister;
}
}
}
if (opr->is_virtual() &&
gen()->is_vreg_flag_set(opr->vreg_number(), LIRGenerator::must_start_in_memory)) {
// result is a stack-slot, so prevent immediate reloading
return noUse;
}
// all other operands require a register
return mustHaveRegister;
}
IntervalUseKind LinearScan::use_kind_of_input_operand(LIR_Op* op, LIR_Opr opr) {
if (op->code() == lir_move) {
assert(op->as_Op1() != NULL, "lir_move must be LIR_Op1");
LIR_Op1* move = (LIR_Op1*)op;
LIR_Opr res = move->result_opr();
bool result_in_memory = res->is_virtual() && gen()->is_vreg_flag_set(res->vreg_number(), LIRGenerator::must_start_in_memory);
if (result_in_memory) {
// Move to an interval with must_start_in_memory set.
// To avoid moves from stack to stack (not allowed) force the input operand to a register
return mustHaveRegister;
} else if (move->in_opr()->is_register() && move->result_opr()->is_register()) {
// Move from register to register
if (block_of_op_with_id(op->id())->is_set(BlockBegin::osr_entry_flag)) {
// special handling of phi-function moves inside osr-entry blocks
// input operand must have a register instead of output operand (leads to better register allocation)
return mustHaveRegister;
}
// The input operand is not forced to a register (moves from stack to register are allowed),
// but it is faster if the input operand is in a register
return shouldHaveRegister;
}
}
#if defined(X86) || defined(S390)
if (op->code() == lir_cmove) {
// conditional moves can handle stack operands
assert(op->result_opr()->is_register(), "result must always be in a register");
return shouldHaveRegister;
}
// optimizations for second input operand of arithmehtic operations on Intel
// this operand is allowed to be on the stack in some cases
BasicType opr_type = opr->type_register();
if (opr_type == T_FLOAT || opr_type == T_DOUBLE) {
if (IA32_ONLY( (UseSSE == 1 && opr_type == T_FLOAT) || UseSSE >= 2 ) NOT_IA32( true )) {
// SSE float instruction (T_DOUBLE only supported with SSE2)
switch (op->code()) {
case lir_cmp:
case lir_add:
case lir_sub:
case lir_mul:
case lir_div:
{
assert(op->as_Op2() != NULL, "must be LIR_Op2");
LIR_Op2* op2 = (LIR_Op2*)op;
if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
return shouldHaveRegister;
}
}
default:
break;
}
} else {
// FPU stack float instruction
switch (op->code()) {
case lir_add:
case lir_sub:
case lir_mul:
case lir_div:
{
assert(op->as_Op2() != NULL, "must be LIR_Op2");
LIR_Op2* op2 = (LIR_Op2*)op;
if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
return shouldHaveRegister;
}
}
default:
break;
}
}
// We want to sometimes use logical operations on pointers, in particular in GC barriers.
// Since 64bit logical operations do not current support operands on stack, we have to make sure
// T_OBJECT doesn't get spilled along with T_LONG.
} else if (opr_type != T_LONG LP64_ONLY(&& opr_type != T_OBJECT)) {
// integer instruction (note: long operands must always be in register)
switch (op->code()) {
case lir_cmp:
case lir_add:
case lir_sub:
case lir_logic_and:
case lir_logic_or:
case lir_logic_xor:
{
assert(op->as_Op2() != NULL, "must be LIR_Op2");
LIR_Op2* op2 = (LIR_Op2*)op;
if (op2->in_opr1() != op2->in_opr2() && op2->in_opr2() == opr) {
assert((op2->result_opr()->is_register() || op->code() == lir_cmp) && op2->in_opr1()->is_register(), "cannot mark second operand as stack if others are not in register");
return shouldHaveRegister;
}
}
default:
break;
}
}
#endif // X86 || S390
// all other operands require a register
return mustHaveRegister;
}
void LinearScan::handle_method_arguments(LIR_Op* op) {
// special handling for method arguments (moves from stack to virtual register):
// the interval gets no register assigned, but the stack slot.
// it is split before the first use by the register allocator.
if (op->code() == lir_move) {
assert(op->as_Op1() != NULL, "must be LIR_Op1");
LIR_Op1* move = (LIR_Op1*)op;
if (move->in_opr()->is_stack()) {
#ifdef ASSERT
int arg_size = compilation()->method()->arg_size();
LIR_Opr o = move->in_opr();
if (o->is_single_stack()) {
assert(o->single_stack_ix() >= 0 && o->single_stack_ix() < arg_size, "out of range");
} else if (o->is_double_stack()) {
assert(o->double_stack_ix() >= 0 && o->double_stack_ix() < arg_size, "out of range");
} else {
ShouldNotReachHere();
}
assert(move->id() > 0, "invalid id");
assert(block_of_op_with_id(move->id())->number_of_preds() == 0, "move from stack must be in first block");
assert(move->result_opr()->is_virtual(), "result of move must be a virtual register");
TRACE_LINEAR_SCAN(4, tty->print_cr("found move from stack slot %d to vreg %d", o->is_single_stack() ? o->single_stack_ix() : o->double_stack_ix(), reg_num(move->result_opr())));
#endif
Interval* interval = interval_at(reg_num(move->result_opr()));
int stack_slot = LinearScan::nof_regs + (move->in_opr()->is_single_stack() ? move->in_opr()->single_stack_ix() : move->in_opr()->double_stack_ix());
interval->set_canonical_spill_slot(stack_slot);
interval->assign_reg(stack_slot);
}
}
}
void LinearScan::handle_doubleword_moves(LIR_Op* op) {
// special handling for doubleword move from memory to register:
// in this case the registers of the input address and the result
// registers must not overlap -> add a temp range for the input registers
if (op->code() == lir_move) {
assert(op->as_Op1() != NULL, "must be LIR_Op1");
LIR_Op1* move = (LIR_Op1*)op;
if (move->result_opr()->is_double_cpu() && move->in_opr()->is_pointer()) {
LIR_Address* address = move->in_opr()->as_address_ptr();
if (address != NULL) {
if (address->base()->is_valid()) {
add_temp(address->base(), op->id(), noUse);
}
if (address->index()->is_valid()) {
add_temp(address->index(), op->id(), noUse);
}
}
}
}
}
void LinearScan::add_register_hints(LIR_Op* op) {
switch (op->code()) {
case lir_move: // fall through
case lir_convert: {
assert(op->as_Op1() != NULL, "lir_move, lir_convert must be LIR_Op1");
LIR_Op1* move = (LIR_Op1*)op;
LIR_Opr move_from = move->in_opr();
LIR_Opr move_to = move->result_opr();
if (move_to->is_register() && move_from->is_register()) {
Interval* from = interval_at(reg_num(move_from));
Interval* to = interval_at(reg_num(move_to));
if (from != NULL && to != NULL) {
to->set_register_hint(from);
TRACE_LINEAR_SCAN(4, tty->print_cr("operation at op_id %d: added hint from interval %d to %d", move->id(), from->reg_num(), to->reg_num()));
}
}
break;
}
case lir_cmove: {
assert(op->as_Op4() != NULL, "lir_cmove must be LIR_Op4");
LIR_Op4* cmove = (LIR_Op4*)op;
LIR_Opr move_from = cmove->in_opr1();
LIR_Opr move_to = cmove->result_opr();
if (move_to->is_register() && move_from->is_register()) {
Interval* from = interval_at(reg_num(move_from));
Interval* to = interval_at(reg_num(move_to));
if (from != NULL && to != NULL) {
to->set_register_hint(from);
TRACE_LINEAR_SCAN(4, tty->print_cr("operation at op_id %d: added hint from interval %d to %d", cmove->id(), from->reg_num(), to->reg_num()));
}
}
break;
}
default:
break;
}
}
void LinearScan::build_intervals() {
TIME_LINEAR_SCAN(timer_build_intervals);
// initialize interval list with expected number of intervals
// (32 is added to have some space for split children without having to resize the list)
_intervals = IntervalList(num_virtual_regs() + 32);
// initialize all slots that are used by build_intervals
_intervals.at_put_grow(num_virtual_regs() - 1, NULL, NULL);
// create a list with all caller-save registers (cpu, fpu, xmm)
// when an instruction is a call, a temp range is created for all these registers
int num_caller_save_registers = 0;
int caller_save_registers[LinearScan::nof_regs];
int i;
for (i = 0; i < FrameMap::nof_caller_save_cpu_regs(); i++) {
LIR_Opr opr = FrameMap::caller_save_cpu_reg_at(i);
assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
caller_save_registers[num_caller_save_registers++] = reg_num(opr);
}
// temp ranges for fpu registers are only created when the method has
// virtual fpu operands. Otherwise no allocation for fpu registers is
// performed and so the temp ranges would be useless
if (has_fpu_registers()) {
#ifdef X86
if (UseSSE < 2) {
#endif // X86
for (i = 0; i < FrameMap::nof_caller_save_fpu_regs; i++) {
LIR_Opr opr = FrameMap::caller_save_fpu_reg_at(i);
assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
caller_save_registers[num_caller_save_registers++] = reg_num(opr);
}
#ifdef X86
}
#endif // X86
#ifdef X86
if (UseSSE > 0) {
int num_caller_save_xmm_regs = FrameMap::get_num_caller_save_xmms();
for (i = 0; i < num_caller_save_xmm_regs; i ++) {
LIR_Opr opr = FrameMap::caller_save_xmm_reg_at(i);
assert(opr->is_valid() && opr->is_register(), "FrameMap should not return invalid operands");
assert(reg_numHi(opr) == -1, "missing addition of range for hi-register");
caller_save_registers[num_caller_save_registers++] = reg_num(opr);
}
}
#endif // X86
}
assert(num_caller_save_registers <= LinearScan::nof_regs, "out of bounds");
LIR_OpVisitState visitor;
// iterate all blocks in reverse order
for (i = block_count() - 1; i >= 0; i--) {
BlockBegin* block = block_at(i);
LIR_OpList* instructions = block->lir()->instructions_list();
int block_from = block->first_lir_instruction_id();
int block_to = block->last_lir_instruction_id();
assert(block_from == instructions->at(0)->id(), "must be");
assert(block_to == instructions->at(instructions->length() - 1)->id(), "must be");
// Update intervals for registers live at the end of this block;
ResourceBitMap live = block->live_out();
int size = (int)live.size();
for (int number = (int)live.get_next_one_offset(0, size); number < size; number = (int)live.get_next_one_offset(number + 1, size)) {
assert(live.at(number), "should not stop here otherwise");
assert(number >= LIR_Opr::vreg_base, "fixed intervals must not be live on block bounds");
TRACE_LINEAR_SCAN(2, tty->print_cr("live in %d to %d", number, block_to + 2));
add_use(number, block_from, block_to + 2, noUse, T_ILLEGAL);
// add special use positions for loop-end blocks when the
// interval is used anywhere inside this loop. It's possible
// that the block was part of a non-natural loop, so it might
// have an invalid loop index.
if (block->is_set(BlockBegin::linear_scan_loop_end_flag) &&
block->loop_index() != -1 &&
is_interval_in_loop(number, block->loop_index())) {
interval_at(number)->add_use_pos(block_to + 1, loopEndMarker);
}
}
// iterate all instructions of the block in reverse order.
// skip the first instruction because it is always a label
// definitions of intervals are processed before uses
assert(visitor.no_operands(instructions->at(0)), "first operation must always be a label");
for (int j = instructions->length() - 1; j >= 1; j--) {
LIR_Op* op = instructions->at(j);
int op_id = op->id();
// visit operation to collect all operands
visitor.visit(op);
// add a temp range for each register if operation destroys caller-save registers
if (visitor.has_call()) {
for (int k = 0; k < num_caller_save_registers; k++) {
add_temp(caller_save_registers[k], op_id, noUse, T_ILLEGAL);
}
TRACE_LINEAR_SCAN(4, tty->print_cr("operation destroys all caller-save registers"));
}
// Add any platform dependent temps
pd_add_temps(op);
// visit definitions (output and temp operands)
int k, n;
n = visitor.opr_count(LIR_OpVisitState::outputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::outputMode, k);
assert(opr->is_register(), "visitor should only return register operands");
add_def(opr, op_id, use_kind_of_output_operand(op, opr));
}
n = visitor.opr_count(LIR_OpVisitState::tempMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::tempMode, k);
assert(opr->is_register(), "visitor should only return register operands");
add_temp(opr, op_id, mustHaveRegister);
}
// visit uses (input operands)
n = visitor.opr_count(LIR_OpVisitState::inputMode);
for (k = 0; k < n; k++) {
LIR_Opr opr = visitor.opr_at(LIR_OpVisitState::inputMode, k);
assert(opr->is_register(), "visitor should only return register operands");
add_use(opr, block_from, op_id, use_kind_of_input_operand(op, opr));
}
// Add uses of live locals from interpreter's point of view for proper
// debug information generation
// Treat these operands as temp values (if the life range is extended
// to a call site, the value would be in a register at the call otherwise)
n = visitor.info_count();
for (k = 0; k < n; k++) {
CodeEmitInfo* info = visitor.info_at(k);
ValueStack* stack = info->stack();
for_each_state_value(stack, value,
add_use(value, block_from, op_id + 1, noUse);
);
}
// special steps for some instructions (especially moves)
handle_method_arguments(op);
handle_doubleword_moves(op);
add_register_hints(op);
} // end of instruction iteration
} // end of block iteration
// add the range [0, 1[ to all fixed intervals
// -> the register allocator need not handle unhandled fixed intervals
for (int n = 0; n < LinearScan::nof_regs; n++) {
Interval* interval = interval_at(n);
if (interval != NULL) {
interval->add_range(0, 1);
}
}
}
// ********** Phase 5: actual register allocation
int LinearScan::interval_cmp(Interval** a, Interval** b) {
if (*a != NULL) {
if (*b != NULL) {
return (*a)->from() - (*b)->from();
} else {
return -1;
}
} else {
if (*b != NULL) {
return 1;
} else {
return 0;
}
}
}
#ifndef PRODUCT
int interval_cmp(Interval* const& l, Interval* const& r) {
return l->from() - r->from();
}
bool find_interval(Interval* interval, IntervalArray* intervals) {
bool found;
int idx = intervals->find_sorted<Interval*, interval_cmp>(interval, found);
if (!found) {
return false;
}
int from = interval->from();
// The index we've found using binary search is pointing to an interval
// that is defined in the same place as the interval we were looking for.
// So now we have to look around that index and find exact interval.
for (int i = idx; i >= 0; i--) {
if (intervals->at(i) == interval) {
return true;
}
if (intervals->at(i)->from() != from) {
break;
}
}
for (int i = idx + 1; i < intervals->length(); i++) {
if (intervals->at(i) == interval) {
return true;
}
if (intervals->at(i)->from() != from) {
break;
}
}
return false;
}
bool LinearScan::is_sorted(IntervalArray* intervals) {
int from = -1;
int null_count = 0;
for (int i = 0; i < intervals->length(); i++) {
Interval* it = intervals->at(i);
if (it != NULL) {
assert(from <= it->from(), "Intervals are unordered");
from = it->from();
} else {
null_count++;
}
}
assert(null_count == 0, "Sorted intervals should not contain nulls");
null_count = 0;
for (int i = 0; i < interval_count(); i++) {
Interval* interval = interval_at(i);
if (interval != NULL) {
assert(find_interval(interval, intervals), "Lists do not contain same intervals");
} else {
null_count++;
}
}
assert(interval_count() - null_count == intervals->length(),
"Sorted list should contain the same amount of non-NULL intervals as unsorted list");
return true;
}
#endif
void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
if (*prev != NULL) {
(*prev)->set_next(interval);
} else {
*first = interval;
}
*prev = interval;
}
void LinearScan::create_unhandled_lists(Interval** list1, Interval** list2, bool (is_list1)(const Interval* i), bool (is_list2)(const Interval* i)) {
assert(is_sorted(_sorted_intervals), "interval list is not sorted");
*list1 = *list2 = Interval::end();
Interval* list1_prev = NULL;
Interval* list2_prev = NULL;
Interval* v;
const int n = _sorted_intervals->length();
for (int i = 0; i < n; i++) {
v = _sorted_intervals->at(i);
if (v == NULL) continue;
if (is_list1(v)) {
add_to_list(list1, &list1_prev, v);
} else if (is_list2 == NULL || is_list2(v)) {
add_to_list(list2, &list2_prev, v);
}
}
if (list1_prev != NULL) list1_prev->set_next(Interval::end());
if (list2_prev != NULL) list2_prev->set_next(Interval::end());
assert(list1_prev == NULL || list1_prev->next() == Interval::end(), "linear list ends not with sentinel");
assert(list2_prev == NULL || list2_prev->next() == Interval::end(), "linear list ends not with sentinel");
}
void LinearScan::sort_intervals_before_allocation() {
TIME_LINEAR_SCAN(timer_sort_intervals_before);
if (_needs_full_resort) {
// There is no known reason why this should occur but just in case...
assert(false, "should never occur");
// Re-sort existing interval list because an Interval::from() has changed
_sorted_intervals->sort(interval_cmp);
_needs_full_resort = false;
}
IntervalList* unsorted_list = &_intervals;
int unsorted_len = unsorted_list->length();
int sorted_len = 0;
int unsorted_idx;
int sorted_idx = 0;
int sorted_from_max = -1;
// calc number of items for sorted list (sorted list must not contain NULL values)
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
if (unsorted_list->at(unsorted_idx) != NULL) {
sorted_len++;
}
}
IntervalArray* sorted_list = new IntervalArray(sorted_len, sorted_len, NULL);
// special sorting algorithm: the original interval-list is almost sorted,
// only some intervals are swapped. So this is much faster than a complete QuickSort
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
Interval* cur_interval = unsorted_list->at(unsorted_idx);
if (cur_interval != NULL) {
int cur_from = cur_interval->from();
if (sorted_from_max <= cur_from) {
sorted_list->at_put(sorted_idx++, cur_interval);
sorted_from_max = cur_interval->from();
} else {
// the assumption that the intervals are already sorted failed,
// so this interval must be sorted in manually
int j;
for (j = sorted_idx - 1; j >= 0 && cur_from < sorted_list->at(j)->from(); j--) {
sorted_list->at_put(j + 1, sorted_list->at(j));
}
sorted_list->at_put(j + 1, cur_interval);
sorted_idx++;
}
}
}
_sorted_intervals = sorted_list;
assert(is_sorted(_sorted_intervals), "intervals unsorted");
}
void LinearScan::sort_intervals_after_allocation() {
TIME_LINEAR_SCAN(timer_sort_intervals_after);
if (_needs_full_resort) {
// Re-sort existing interval list because an Interval::from() has changed
_sorted_intervals->sort(interval_cmp);
_needs_full_resort = false;
}
IntervalArray* old_list = _sorted_intervals;
IntervalList* new_list = _new_intervals_from_allocation;
int old_len = old_list->length();
int new_len = new_list == NULL ? 0 : new_list->length();
if (new_len == 0) {
// no intervals have been added during allocation, so sorted list is already up to date
assert(is_sorted(_sorted_intervals), "intervals unsorted");
return;
}
// conventional sort-algorithm for new intervals
new_list->sort(interval_cmp);
// merge old and new list (both already sorted) into one combined list
int combined_list_len = old_len + new_len;
IntervalArray* combined_list = new IntervalArray(combined_list_len, combined_list_len, NULL);
int old_idx = 0;
int new_idx = 0;
while (old_idx + new_idx < old_len + new_len) {
if (new_idx >= new_len || (old_idx < old_len && old_list->at(old_idx)->from() <= new_list->at(new_idx)->from())) {
combined_list->at_put(old_idx + new_idx, old_list->at(old_idx));
old_idx++;
} else {
combined_list->at_put(old_idx + new_idx, new_list->at(new_idx));
new_idx++;
}
}
_sorted_intervals = combined_list;
assert(is_sorted(_sorted_intervals), "intervals unsorted");
}
void LinearScan::allocate_registers() {
TIME_LINEAR_SCAN(timer_allocate_registers);
Interval* precolored_cpu_intervals, *not_precolored_cpu_intervals;
Interval* precolored_fpu_intervals, *not_precolored_fpu_intervals;
// collect cpu intervals
create_unhandled_lists(&precolored_cpu_intervals, ¬_precolored_cpu_intervals,
is_precolored_cpu_interval, is_virtual_cpu_interval);
// collect fpu intervals
create_unhandled_lists(&precolored_fpu_intervals, ¬_precolored_fpu_intervals,
is_precolored_fpu_interval, is_virtual_fpu_interval);
// this fpu interval collection cannot be moved down below with the allocation section as
// the cpu_lsw.walk() changes interval positions.
if (!has_fpu_registers()) {
#ifdef ASSERT
assert(not_precolored_fpu_intervals == Interval::end(), "missed an uncolored fpu interval");
#else
if (not_precolored_fpu_intervals != Interval::end()) {
BAILOUT("missed an uncolored fpu interval");
}
#endif
}
// allocate cpu registers
LinearScanWalker cpu_lsw(this, precolored_cpu_intervals, not_precolored_cpu_intervals);
cpu_lsw.walk();
cpu_lsw.finish_allocation();
if (has_fpu_registers()) {
// allocate fpu registers
LinearScanWalker fpu_lsw(this, precolored_fpu_intervals, not_precolored_fpu_intervals);
fpu_lsw.walk();
fpu_lsw.finish_allocation();
}
}
// ********** Phase 6: resolve data flow
// (insert moves at edges between blocks if intervals have been split)
// wrapper for Interval::split_child_at_op_id that performs a bailout in product mode
// instead of returning NULL
Interval* LinearScan::split_child_at_op_id(Interval* interval, int op_id, LIR_OpVisitState::OprMode mode) {
Interval* result = interval->split_child_at_op_id(op_id, mode);
if (result != NULL) {
return result;
}
assert(false, "must find an interval, but do a clean bailout in product mode");
result = new Interval(LIR_Opr::vreg_base);
result->assign_reg(0);
result->set_type(T_INT);
BAILOUT_("LinearScan: interval is NULL", result);
}
Interval* LinearScan::interval_at_block_begin(BlockBegin* block, int reg_num) {
assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
assert(interval_at(reg_num) != NULL, "no interval found");
return split_child_at_op_id(interval_at(reg_num), block->first_lir_instruction_id(), LIR_OpVisitState::outputMode);
}
Interval* LinearScan::interval_at_block_end(BlockBegin* block, int reg_num) {
assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
assert(interval_at(reg_num) != NULL, "no interval found");
return split_child_at_op_id(interval_at(reg_num), block->last_lir_instruction_id() + 1, LIR_OpVisitState::outputMode);
}
Interval* LinearScan::interval_at_op_id(int reg_num, int op_id) {
assert(LinearScan::nof_regs <= reg_num && reg_num < num_virtual_regs(), "register number out of bounds");
assert(interval_at(reg_num) != NULL, "no interval found");
return split_child_at_op_id(interval_at(reg_num), op_id, LIR_OpVisitState::inputMode);
}
void LinearScan::resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
DEBUG_ONLY(move_resolver.check_empty());
const int size = live_set_size();
const ResourceBitMap live_at_edge = to_block->live_in();
// visit all registers where the live_at_edge bit is set
for (int r = (int)live_at_edge.get_next_one_offset(0, size); r < size; r = (int)live_at_edge.get_next_one_offset(r + 1, size)) {
assert(r < num_virtual_regs(), "live information set for not existing interval");
assert(from_block->live_out().at(r) && to_block->live_in().at(r), "interval not live at this edge");
Interval* from_interval = interval_at_block_end(from_block, r);
Interval* to_interval = interval_at_block_begin(to_block, r);
if (from_interval != to_interval && (from_interval->assigned_reg() != to_interval->assigned_reg() || from_interval->assigned_regHi() != to_interval->assigned_regHi())) {
// need to insert move instruction
move_resolver.add_mapping(from_interval, to_interval);
}
}
}
void LinearScan::resolve_find_insert_pos(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) {
--> --------------------
--> maximum size reached
--> --------------------
¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.114Angebot
Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können
¤
|
Lebenszyklus
Die hierunter aufgelisteten Ziele sind für diese Firma wichtig
Ziele
Entwicklung einer Software für die statische Quellcodeanalyse
|
