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