< prev index next >
src/share/vm/c1/c1_LinearScan.cpp
Print this page
*** 77,87 ****
, _has_fpu_registers(false)
, _num_calls(-1)
, _max_spills(0)
, _unused_spill_slot(-1)
, _intervals(0) // initialized later with correct length
! , _new_intervals_from_allocation(new IntervalList())
, _sorted_intervals(NULL)
, _needs_full_resort(false)
, _lir_ops(0) // initialized later with correct length
, _block_of_op(0) // initialized later with correct length
, _has_info(0)
--- 77,87 ----
, _has_fpu_registers(false)
, _num_calls(-1)
, _max_spills(0)
, _unused_spill_slot(-1)
, _intervals(0) // initialized later with correct length
! , _new_intervals_from_allocation(new GrowableArray<Interval*>())
, _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)
*** 1255,1265 ****
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
--- 1255,1265 ----
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 = GrowableArray<Interval*>(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
*** 1432,1477 ****
}
}
}
#ifndef PRODUCT
! bool LinearScan::is_sorted(IntervalArray* intervals) {
! int from = -1;
! int i, j;
! for (i = 0; i < intervals->length(); i ++) {
! Interval* it = intervals->at(i);
! if (it != NULL) {
! if (from > it->from()) {
! assert(false, "");
return false;
}
! from = it->from();
}
}
! // check in both directions if sorted list and unsorted list contain same intervals
! for (i = 0; i < interval_count(); i++) {
! if (interval_at(i) != NULL) {
! int num_found = 0;
! for (j = 0; j < intervals->length(); j++) {
! if (interval_at(i) == intervals->at(j)) {
! num_found++;
}
}
- assert(num_found == 1, "lists do not contain same intervals");
}
}
- for (j = 0; j < intervals->length(); j++) {
- int num_found = 0;
- for (i = 0; i < interval_count(); i++) {
- if (interval_at(i) == intervals->at(j)) {
- num_found++;
}
}
- assert(num_found == 1, "lists do not contain same intervals");
}
return true;
}
#endif
void LinearScan::add_to_list(Interval** first, Interval** prev, Interval* interval) {
--- 1432,1509 ----
}
}
}
#ifndef PRODUCT
! int interval_cmp(Interval* const& l, Interval* const& r) {
! return l->from() - r->from();
! }
!
! bool find_interval(Interval* interval, GrowableArray<Interval*>* 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(GrowableArray<Interval*>* 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) {
*** 1521,1531 ****
// 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;
--- 1553,1563 ----
// Re-sort existing interval list because an Interval::from() has changed
_sorted_intervals->sort(interval_cmp);
_needs_full_resort = false;
}
! GrowableArray<Interval*>* 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;
*** 1534,1544 ****
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
if (unsorted_list->at(unsorted_idx) != NULL) {
sorted_len++;
}
}
! IntervalArray* sorted_list = new IntervalArray(sorted_len);
// special sorting algorithm: the original interval-list is almost sorted,
// only some intervals are swapped. So this is much faster than a complete QuickSort
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
Interval* cur_interval = unsorted_list->at(unsorted_idx);
--- 1566,1576 ----
for (unsorted_idx = 0; unsorted_idx < unsorted_len; unsorted_idx++) {
if (unsorted_list->at(unsorted_idx) != NULL) {
sorted_len++;
}
}
! GrowableArray<Interval*>* sorted_list = new GrowableArray<Interval*>(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);
*** 1572,1583 ****
// Re-sort existing interval list because an Interval::from() has changed
_sorted_intervals->sort(interval_cmp);
_needs_full_resort = false;
}
! IntervalArray* old_list = _sorted_intervals;
! IntervalList* new_list = _new_intervals_from_allocation;
int old_len = old_list->length();
int new_len = new_list->length();
if (new_len == 0) {
// no intervals have been added during allocation, so sorted list is already up to date
--- 1604,1615 ----
// Re-sort existing interval list because an Interval::from() has changed
_sorted_intervals->sort(interval_cmp);
_needs_full_resort = false;
}
! GrowableArray<Interval*>* old_list = _sorted_intervals;
! GrowableArray<Interval*>* new_list = _new_intervals_from_allocation;
int old_len = old_list->length();
int new_len = new_list->length();
if (new_len == 0) {
// no intervals have been added during allocation, so sorted list is already up to date
*** 1587,1597 ****
// conventional sort-algorithm for new intervals
new_list->sort(interval_cmp);
// merge old and new list (both already sorted) into one combined list
! IntervalArray* combined_list = new IntervalArray(old_len + new_len);
int old_idx = 0;
int new_idx = 0;
while (old_idx + new_idx < old_len + new_len) {
if (new_idx >= new_len || (old_idx < old_len && old_list->at(old_idx)->from() <= new_list->at(new_idx)->from())) {
--- 1619,1630 ----
// 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;
! GrowableArray<Interval*>* combined_list = new GrowableArray<Interval*>(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())) {
*** 3393,3415 ****
// currently, only registers are processed
int state_size() { return LinearScan::nof_regs; }
// accessors
! IntervalList* state_for_block(BlockBegin* block) { return _saved_states.at(block->block_id()); }
! void set_state_for_block(BlockBegin* block, IntervalList* saved_state) { _saved_states.at_put(block->block_id(), saved_state); }
void add_to_work_list(BlockBegin* block) { if (!_work_list.contains(block)) _work_list.append(block); }
// helper functions
! IntervalList* copy(IntervalList* input_state);
! void state_put(IntervalList* input_state, int reg, Interval* interval);
! bool check_state(IntervalList* input_state, int reg, Interval* interval);
void process_block(BlockBegin* block);
! void process_xhandler(XHandler* xhandler, IntervalList* input_state);
! void process_successor(BlockBegin* block, IntervalList* input_state);
! void process_operations(LIR_List* ops, IntervalList* input_state);
public:
RegisterVerifier(LinearScan* allocator)
: _allocator(allocator)
, _work_list(16)
--- 3426,3448 ----
// currently, only registers are processed
int state_size() { return LinearScan::nof_regs; }
// accessors
! GrowableArray<Interval*>* state_for_block(BlockBegin* block) { return _saved_states.at(block->block_id()); }
! void set_state_for_block(BlockBegin* block, GrowableArray<Interval*>* saved_state) { _saved_states.at_put(block->block_id(), saved_state); }
void add_to_work_list(BlockBegin* block) { if (!_work_list.contains(block)) _work_list.append(block); }
// helper functions
! GrowableArray<Interval*>* copy(GrowableArray<Interval*>* input_state);
! void state_put(GrowableArray<Interval*>* input_state, int reg, Interval* interval);
! bool check_state(GrowableArray<Interval*>* input_state, int reg, Interval* interval);
void process_block(BlockBegin* block);
! void process_xhandler(XHandler* xhandler, GrowableArray<Interval*>* input_state);
! void process_successor(BlockBegin* block, GrowableArray<Interval*>* input_state);
! void process_operations(LIR_List* ops, GrowableArray<Interval*>* input_state);
public:
RegisterVerifier(LinearScan* allocator)
: _allocator(allocator)
, _work_list(16)
*** 3427,3437 ****
}
void RegisterVerifier::verify(BlockBegin* start) {
// setup input registers (method arguments) for first block
! IntervalList* input_state = new IntervalList(state_size(), NULL);
CallingConvention* args = compilation()->frame_map()->incoming_arguments();
for (int n = 0; n < args->length(); n++) {
LIR_Opr opr = args->at(n);
if (opr->is_register()) {
Interval* interval = interval_at(reg_num(opr));
--- 3460,3471 ----
}
void RegisterVerifier::verify(BlockBegin* start) {
// setup input registers (method arguments) for first block
! int input_state_len = state_size();
! GrowableArray<Interval*>* input_state = new GrowableArray<Interval*>(input_state_len, input_state_len, NULL);
CallingConvention* args = compilation()->frame_map()->incoming_arguments();
for (int n = 0; n < args->length(); n++) {
LIR_Opr opr = args->at(n);
if (opr->is_register()) {
Interval* interval = interval_at(reg_num(opr));
*** 3459,3469 ****
void RegisterVerifier::process_block(BlockBegin* block) {
TRACE_LINEAR_SCAN(2, tty->cr(); tty->print_cr("process_block B%d", block->block_id()));
// must copy state because it is modified
! IntervalList* input_state = copy(state_for_block(block));
if (TraceLinearScanLevel >= 4) {
tty->print_cr("Input-State of intervals:");
tty->print(" ");
for (int i = 0; i < state_size(); i++) {
--- 3493,3503 ----
void RegisterVerifier::process_block(BlockBegin* block) {
TRACE_LINEAR_SCAN(2, tty->cr(); tty->print_cr("process_block B%d", block->block_id()));
// must copy state because it is modified
! GrowableArray<Interval*>* input_state = copy(state_for_block(block));
if (TraceLinearScanLevel >= 4) {
tty->print_cr("Input-State of intervals:");
tty->print(" ");
for (int i = 0; i < state_size(); i++) {
*** 3484,3494 ****
for (int i = 0; i < block->number_of_sux(); i++) {
process_successor(block->sux_at(i), input_state);
}
}
! void RegisterVerifier::process_xhandler(XHandler* xhandler, IntervalList* input_state) {
TRACE_LINEAR_SCAN(2, tty->print_cr("process_xhandler B%d", xhandler->entry_block()->block_id()));
// must copy state because it is modified
input_state = copy(input_state);
--- 3518,3528 ----
for (int i = 0; i < block->number_of_sux(); i++) {
process_successor(block->sux_at(i), input_state);
}
}
! void RegisterVerifier::process_xhandler(XHandler* xhandler, GrowableArray<Interval*>* input_state) {
TRACE_LINEAR_SCAN(2, tty->print_cr("process_xhandler B%d", xhandler->entry_block()->block_id()));
// must copy state because it is modified
input_state = copy(input_state);
*** 3496,3507 ****
process_operations(xhandler->entry_code(), input_state);
}
process_successor(xhandler->entry_block(), input_state);
}
! void RegisterVerifier::process_successor(BlockBegin* block, IntervalList* input_state) {
! IntervalList* saved_state = state_for_block(block);
if (saved_state != NULL) {
// this block was already processed before.
// check if new input_state is consistent with saved_state
--- 3530,3541 ----
process_operations(xhandler->entry_code(), input_state);
}
process_successor(xhandler->entry_block(), input_state);
}
! void RegisterVerifier::process_successor(BlockBegin* block, GrowableArray<Interval*>* input_state) {
! GrowableArray<Interval*>* saved_state = state_for_block(block);
if (saved_state != NULL) {
// this block was already processed before.
// check if new input_state is consistent with saved_state
*** 3539,3555 ****
add_to_work_list(block);
}
}
! IntervalList* RegisterVerifier::copy(IntervalList* input_state) {
! IntervalList* copy_state = new IntervalList(input_state->length());
! copy_state->push_all(input_state);
return copy_state;
}
! void RegisterVerifier::state_put(IntervalList* input_state, int reg, Interval* interval) {
if (reg != LinearScan::any_reg && reg < state_size()) {
if (interval != NULL) {
TRACE_LINEAR_SCAN(4, tty->print_cr(" reg[%d] = %d", reg, interval->reg_num()));
} else if (input_state->at(reg) != NULL) {
TRACE_LINEAR_SCAN(4, tty->print_cr(" reg[%d] = NULL", reg));
--- 3573,3589 ----
add_to_work_list(block);
}
}
! GrowableArray<Interval*>* RegisterVerifier::copy(GrowableArray<Interval*>* input_state) {
! GrowableArray<Interval*>* copy_state = new GrowableArray<Interval*>(input_state->length());
! copy_state->appendAll(input_state);
return copy_state;
}
! void RegisterVerifier::state_put(GrowableArray<Interval*>* input_state, int reg, Interval* interval) {
if (reg != LinearScan::any_reg && reg < state_size()) {
if (interval != NULL) {
TRACE_LINEAR_SCAN(4, tty->print_cr(" reg[%d] = %d", reg, interval->reg_num()));
} else if (input_state->at(reg) != NULL) {
TRACE_LINEAR_SCAN(4, tty->print_cr(" reg[%d] = NULL", reg));
*** 3557,3577 ****
input_state->at_put(reg, interval);
}
}
! bool RegisterVerifier::check_state(IntervalList* input_state, int reg, Interval* interval) {
if (reg != LinearScan::any_reg && reg < state_size()) {
if (input_state->at(reg) != interval) {
tty->print_cr("!! Error in register allocation: register %d does not contain interval %d", reg, interval->reg_num());
return true;
}
}
return false;
}
! void RegisterVerifier::process_operations(LIR_List* ops, IntervalList* input_state) {
// visit all instructions of the block
LIR_OpVisitState visitor;
bool has_error = false;
for (int i = 0; i < ops->length(); i++) {
--- 3591,3611 ----
input_state->at_put(reg, interval);
}
}
! bool RegisterVerifier::check_state(GrowableArray<Interval*>* input_state, int reg, Interval* interval) {
if (reg != LinearScan::any_reg && reg < state_size()) {
if (input_state->at(reg) != interval) {
tty->print_cr("!! Error in register allocation: register %d does not contain interval %d", reg, interval->reg_num());
return true;
}
}
return false;
}
! void RegisterVerifier::process_operations(LIR_List* ops, GrowableArray<Interval*>* input_state) {
// visit all instructions of the block
LIR_OpVisitState visitor;
bool has_error = false;
for (int i = 0; i < ops->length(); i++) {
*** 4357,4367 ****
// insert new interval in children-list of parent
if (parent->_split_children.length() == 0) {
assert(is_split_parent(), "list must be initialized at first split");
! parent->_split_children = IntervalList(4);
parent->_split_children.append(this);
}
parent->_split_children.append(result);
return result;
--- 4391,4401 ----
// insert new interval in children-list of parent
if (parent->_split_children.length() == 0) {
assert(is_split_parent(), "list must be initialized at first split");
! parent->_split_children = GrowableArray<Interval*>(4);
parent->_split_children.append(this);
}
parent->_split_children.append(result);
return result;
*** 4808,4818 ****
LinearScanWalker::LinearScanWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first)
: IntervalWalker(allocator, unhandled_fixed_first, unhandled_any_first)
, _move_resolver(allocator)
{
for (int i = 0; i < LinearScan::nof_regs; i++) {
! _spill_intervals[i] = new IntervalList(2);
}
}
inline void LinearScanWalker::init_use_lists(bool only_process_use_pos) {
--- 4842,4852 ----
LinearScanWalker::LinearScanWalker(LinearScan* allocator, Interval* unhandled_fixed_first, Interval* unhandled_any_first)
: IntervalWalker(allocator, unhandled_fixed_first, unhandled_any_first)
, _move_resolver(allocator)
{
for (int i = 0; i < LinearScan::nof_regs; i++) {
! _spill_intervals[i] = new GrowableArray<Interval*>(2);
}
}
inline void LinearScanWalker::init_use_lists(bool only_process_use_pos) {
*** 5501,5514 ****
remove_from_list(it);
split_and_spill_interval(it);
}
if (regHi != any_reg) {
! IntervalList* processed = _spill_intervals[reg];
for (int i = 0; i < _spill_intervals[regHi]->length(); i++) {
Interval* it = _spill_intervals[regHi]->at(i);
! if (processed->index_of(it) == -1) {
remove_from_list(it);
split_and_spill_interval(it);
}
}
}
--- 5535,5548 ----
remove_from_list(it);
split_and_spill_interval(it);
}
if (regHi != any_reg) {
! GrowableArray<Interval*>* processed = _spill_intervals[reg];
for (int i = 0; i < _spill_intervals[regHi]->length(); i++) {
Interval* it = _spill_intervals[regHi]->at(i);
! if (processed->find_from_end(it) == -1) {
remove_from_list(it);
split_and_spill_interval(it);
}
}
}
< prev index next >