86 , _lir_ops(0) // initialized later with correct length |
86 , _lir_ops(0) // initialized later with correct length |
87 , _block_of_op(0) // initialized later with correct length |
87 , _block_of_op(0) // initialized later with correct length |
88 , _has_info(0) |
88 , _has_info(0) |
89 , _has_call(0) |
89 , _has_call(0) |
90 , _scope_value_cache(0) // initialized later with correct length |
90 , _scope_value_cache(0) // initialized later with correct length |
91 , _interval_in_loop(0, 0) // initialized later with correct length |
91 , _interval_in_loop(0) // initialized later with correct length |
92 , _cached_blocks(*ir->linear_scan_order()) |
92 , _cached_blocks(*ir->linear_scan_order()) |
93 #ifdef X86 |
93 #ifdef X86 |
94 , _fpu_stack_allocator(NULL) |
94 , _fpu_stack_allocator(NULL) |
95 #endif |
95 #endif |
96 { |
96 { |
522 block->set_last_lir_instruction_id(op_id - 2); |
522 block->set_last_lir_instruction_id(op_id - 2); |
523 } |
523 } |
524 assert(idx == num_instructions, "must match"); |
524 assert(idx == num_instructions, "must match"); |
525 assert(idx * 2 == op_id, "must match"); |
525 assert(idx * 2 == op_id, "must match"); |
526 |
526 |
527 _has_call = BitMap(num_instructions); _has_call.clear(); |
527 _has_call.initialize(num_instructions); |
528 _has_info = BitMap(num_instructions); _has_info.clear(); |
528 _has_info.initialize(num_instructions); |
529 } |
529 } |
530 |
530 |
531 |
531 |
532 // ********** Phase 2: compute local live sets separately for each block |
532 // ********** Phase 2: compute local live sets separately for each block |
533 // (sets live_gen and live_kill for each block) |
533 // (sets live_gen and live_kill for each block) |
566 |
566 |
567 // iterate all blocks |
567 // iterate all blocks |
568 for (int i = 0; i < num_blocks; i++) { |
568 for (int i = 0; i < num_blocks; i++) { |
569 BlockBegin* block = block_at(i); |
569 BlockBegin* block = block_at(i); |
570 |
570 |
571 BitMap live_gen(live_size); live_gen.clear(); |
571 ResourceBitMap live_gen(live_size); live_gen.clear(); |
572 BitMap live_kill(live_size); live_kill.clear(); |
572 ResourceBitMap live_kill(live_size); live_kill.clear(); |
573 |
573 |
574 if (block->is_set(BlockBegin::exception_entry_flag)) { |
574 if (block->is_set(BlockBegin::exception_entry_flag)) { |
575 // Phi functions at the begin of an exception handler are |
575 // Phi functions at the begin of an exception handler are |
576 // implicitly defined (= killed) at the beginning of the block. |
576 // implicitly defined (= killed) at the beginning of the block. |
577 for_each_phi_fun(block, phi, |
577 for_each_phi_fun(block, phi, |
713 } |
713 } |
714 } // end of instruction iteration |
714 } // end of instruction iteration |
715 |
715 |
716 block->set_live_gen (live_gen); |
716 block->set_live_gen (live_gen); |
717 block->set_live_kill(live_kill); |
717 block->set_live_kill(live_kill); |
718 block->set_live_in (BitMap(live_size)); block->live_in().clear(); |
718 block->set_live_in (ResourceBitMap(live_size)); block->live_in().clear(); |
719 block->set_live_out (BitMap(live_size)); block->live_out().clear(); |
719 block->set_live_out (ResourceBitMap(live_size)); block->live_out().clear(); |
720 |
720 |
721 TRACE_LINEAR_SCAN(4, tty->print("live_gen B%d ", block->block_id()); print_bitmap(block->live_gen())); |
721 TRACE_LINEAR_SCAN(4, tty->print("live_gen B%d ", block->block_id()); print_bitmap(block->live_gen())); |
722 TRACE_LINEAR_SCAN(4, tty->print("live_kill B%d ", block->block_id()); print_bitmap(block->live_kill())); |
722 TRACE_LINEAR_SCAN(4, tty->print("live_kill B%d ", block->block_id()); print_bitmap(block->live_kill())); |
723 } // end of block iteration |
723 } // end of block iteration |
724 |
724 |
739 |
739 |
740 int num_blocks = block_count(); |
740 int num_blocks = block_count(); |
741 bool change_occurred; |
741 bool change_occurred; |
742 bool change_occurred_in_block; |
742 bool change_occurred_in_block; |
743 int iteration_count = 0; |
743 int iteration_count = 0; |
744 BitMap live_out(live_set_size()); live_out.clear(); // scratch set for calculations |
744 ResourceBitMap live_out(live_set_size()); live_out.clear(); // scratch set for calculations |
745 |
745 |
746 // Perform a backward dataflow analysis to compute live_out and live_in for each block. |
746 // Perform a backward dataflow analysis to compute live_out and live_in for each block. |
747 // The loop is executed until a fixpoint is reached (no changes in an iteration) |
747 // The loop is executed until a fixpoint is reached (no changes in an iteration) |
748 // Exception handlers must be processed because not all live values are |
748 // Exception handlers must be processed because not all live values are |
749 // present in the state array, e.g. because of global value numbering |
749 // present in the state array, e.g. because of global value numbering |
773 live_out.set_union(block->exception_handler_at(j)->live_in()); |
773 live_out.set_union(block->exception_handler_at(j)->live_in()); |
774 } |
774 } |
775 |
775 |
776 if (!block->live_out().is_same(live_out)) { |
776 if (!block->live_out().is_same(live_out)) { |
777 // A change occurred. Swap the old and new live out sets to avoid copying. |
777 // A change occurred. Swap the old and new live out sets to avoid copying. |
778 BitMap temp = block->live_out(); |
778 ResourceBitMap temp = block->live_out(); |
779 block->set_live_out(live_out); |
779 block->set_live_out(live_out); |
780 live_out = temp; |
780 live_out = temp; |
781 |
781 |
782 change_occurred = true; |
782 change_occurred = true; |
783 change_occurred_in_block = true; |
783 change_occurred_in_block = true; |
785 } |
785 } |
786 |
786 |
787 if (iteration_count == 0 || change_occurred_in_block) { |
787 if (iteration_count == 0 || change_occurred_in_block) { |
788 // live_in(block) is the union of live_gen(block) with (live_out(block) & !live_kill(block)) |
788 // live_in(block) is the union of live_gen(block) with (live_out(block) & !live_kill(block)) |
789 // note: live_in has to be computed only in first iteration or if live_out has changed! |
789 // note: live_in has to be computed only in first iteration or if live_out has changed! |
790 BitMap live_in = block->live_in(); |
790 ResourceBitMap live_in = block->live_in(); |
791 live_in.set_from(block->live_out()); |
791 live_in.set_from(block->live_out()); |
792 live_in.set_difference(block->live_kill()); |
792 live_in.set_difference(block->live_kill()); |
793 live_in.set_union(block->live_gen()); |
793 live_in.set_union(block->live_gen()); |
794 } |
794 } |
795 |
795 |
824 } |
824 } |
825 } |
825 } |
826 #endif |
826 #endif |
827 |
827 |
828 // check that the live_in set of the first block is empty |
828 // check that the live_in set of the first block is empty |
829 BitMap live_in_args(ir()->start()->live_in().size()); |
829 ResourceBitMap live_in_args(ir()->start()->live_in().size()); |
830 live_in_args.clear(); |
830 live_in_args.clear(); |
831 if (!ir()->start()->live_in().is_same(live_in_args)) { |
831 if (!ir()->start()->live_in().is_same(live_in_args)) { |
832 #ifdef ASSERT |
832 #ifdef ASSERT |
833 tty->print_cr("Error: live_in set of first block must be empty (when this fails, virtual registers are used before they are defined)"); |
833 tty->print_cr("Error: live_in set of first block must be empty (when this fails, virtual registers are used before they are defined)"); |
834 tty->print_cr("affected registers:"); |
834 tty->print_cr("affected registers:"); |
1315 |
1315 |
1316 assert(block_from == instructions->at(0)->id(), "must be"); |
1316 assert(block_from == instructions->at(0)->id(), "must be"); |
1317 assert(block_to == instructions->at(instructions->length() - 1)->id(), "must be"); |
1317 assert(block_to == instructions->at(instructions->length() - 1)->id(), "must be"); |
1318 |
1318 |
1319 // Update intervals for registers live at the end of this block; |
1319 // Update intervals for registers live at the end of this block; |
1320 BitMap live = block->live_out(); |
1320 ResourceBitMap live = block->live_out(); |
1321 int size = (int)live.size(); |
1321 int size = (int)live.size(); |
1322 for (int number = (int)live.get_next_one_offset(0, size); number < size; number = (int)live.get_next_one_offset(number + 1, size)) { |
1322 for (int number = (int)live.get_next_one_offset(0, size); number < size; number = (int)live.get_next_one_offset(number + 1, size)) { |
1323 assert(live.at(number), "should not stop here otherwise"); |
1323 assert(live.at(number), "should not stop here otherwise"); |
1324 assert(number >= LIR_OprDesc::vreg_base, "fixed intervals must not be live on block bounds"); |
1324 assert(number >= LIR_OprDesc::vreg_base, "fixed intervals must not be live on block bounds"); |
1325 TRACE_LINEAR_SCAN(2, tty->print_cr("live in %d to %d", number, block_to + 2)); |
1325 TRACE_LINEAR_SCAN(2, tty->print_cr("live in %d to %d", number, block_to + 2)); |
1715 void LinearScan::resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) { |
1715 void LinearScan::resolve_collect_mappings(BlockBegin* from_block, BlockBegin* to_block, MoveResolver &move_resolver) { |
1716 DEBUG_ONLY(move_resolver.check_empty()); |
1716 DEBUG_ONLY(move_resolver.check_empty()); |
1717 |
1717 |
1718 const int num_regs = num_virtual_regs(); |
1718 const int num_regs = num_virtual_regs(); |
1719 const int size = live_set_size(); |
1719 const int size = live_set_size(); |
1720 const BitMap live_at_edge = to_block->live_in(); |
1720 const ResourceBitMap live_at_edge = to_block->live_in(); |
1721 |
1721 |
1722 // visit all registers where the live_at_edge bit is set |
1722 // visit all registers where the live_at_edge bit is set |
1723 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)) { |
1723 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)) { |
1724 assert(r < num_regs, "live information set for not exisiting interval"); |
1724 assert(r < num_regs, "live information set for not exisiting interval"); |
1725 assert(from_block->live_out().at(r) && to_block->live_in().at(r), "interval not live at this edge"); |
1725 assert(from_block->live_out().at(r) && to_block->live_in().at(r), "interval not live at this edge"); |
1772 void LinearScan::resolve_data_flow() { |
1772 void LinearScan::resolve_data_flow() { |
1773 TIME_LINEAR_SCAN(timer_resolve_data_flow); |
1773 TIME_LINEAR_SCAN(timer_resolve_data_flow); |
1774 |
1774 |
1775 int num_blocks = block_count(); |
1775 int num_blocks = block_count(); |
1776 MoveResolver move_resolver(this); |
1776 MoveResolver move_resolver(this); |
1777 BitMap block_completed(num_blocks); block_completed.clear(); |
1777 ResourceBitMap block_completed(num_blocks); block_completed.clear(); |
1778 BitMap already_resolved(num_blocks); already_resolved.clear(); |
1778 ResourceBitMap already_resolved(num_blocks); already_resolved.clear(); |
1779 |
1779 |
1780 int i; |
1780 int i; |
1781 for (i = 0; i < num_blocks; i++) { |
1781 for (i = 0; i < num_blocks; i++) { |
1782 BlockBegin* block = block_at(i); |
1782 BlockBegin* block = block_at(i); |
1783 |
1783 |
3395 int size = live_set_size(); |
3395 int size = live_set_size(); |
3396 int num_blocks = block_count(); |
3396 int num_blocks = block_count(); |
3397 |
3397 |
3398 for (int i = 0; i < num_blocks; i++) { |
3398 for (int i = 0; i < num_blocks; i++) { |
3399 BlockBegin* block = block_at(i); |
3399 BlockBegin* block = block_at(i); |
3400 BitMap live_at_edge = block->live_in(); |
3400 ResourceBitMap live_at_edge = block->live_in(); |
3401 |
3401 |
3402 // visit all registers where the live_at_edge bit is set |
3402 // visit all registers where the live_at_edge bit is set |
3403 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)) { |
3403 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)) { |
3404 TRACE_LINEAR_SCAN(4, tty->print("checking interval %d of block B%d", r, block->block_id())); |
3404 TRACE_LINEAR_SCAN(4, tty->print("checking interval %d of block B%d", r, block->block_id())); |
3405 |
3405 |
3747 assert(_mapping_to.at(i) != _mapping_to.at(j), "cannot write to same interval twice"); |
3747 assert(_mapping_to.at(i) != _mapping_to.at(j), "cannot write to same interval twice"); |
3748 } |
3748 } |
3749 } |
3749 } |
3750 |
3750 |
3751 |
3751 |
3752 BitMap used_regs(LinearScan::nof_regs + allocator()->frame_map()->argcount() + allocator()->max_spills()); |
3752 ResourceBitMap used_regs(LinearScan::nof_regs + allocator()->frame_map()->argcount() + allocator()->max_spills()); |
3753 used_regs.clear(); |
3753 used_regs.clear(); |
3754 if (!_multiple_reads_allowed) { |
3754 if (!_multiple_reads_allowed) { |
3755 for (i = 0; i < _mapping_from.length(); i++) { |
3755 for (i = 0; i < _mapping_from.length(); i++) { |
3756 Interval* it = _mapping_from.at(i); |
3756 Interval* it = _mapping_from.at(i); |
3757 if (it != NULL) { |
3757 if (it != NULL) { |
6315 DEBUG_ONLY(verify(code)); |
6315 DEBUG_ONLY(verify(code)); |
6316 } |
6316 } |
6317 |
6317 |
6318 void ControlFlowOptimizer::delete_jumps_to_return(BlockList* code) { |
6318 void ControlFlowOptimizer::delete_jumps_to_return(BlockList* code) { |
6319 #ifdef ASSERT |
6319 #ifdef ASSERT |
6320 BitMap return_converted(BlockBegin::number_of_blocks()); |
6320 ResourceBitMap return_converted(BlockBegin::number_of_blocks()); |
6321 return_converted.clear(); |
6321 return_converted.clear(); |
6322 #endif |
6322 #endif |
6323 |
6323 |
6324 for (int i = code->length() - 1; i >= 0; i--) { |
6324 for (int i = code->length() - 1; i >= 0; i--) { |
6325 BlockBegin* block = code->at(i); |
6325 BlockBegin* block = code->at(i); |