hotspot/src/share/vm/c1/c1_LinearScan.cpp
changeset 38177 b0c9cb06506b
parent 38033 996ce936543f
child 38658 34f9c45625d8
equal deleted inserted replaced
38175:4e2bff1a5467 38177:b0c9cb06506b
    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);