482 BlockList* linear_scan_order() const { return _linear_scan_order; }
483 int num_loops() const { return _num_loops; }
484 };
485
486
487 ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
488 _max_block_id(BlockBegin::number_of_blocks()),
489 _num_blocks(0),
490 _num_loops(0),
491 _iterative_dominators(false),
492 _visited_blocks(_max_block_id),
493 _active_blocks(_max_block_id),
494 _dominator_blocks(_max_block_id),
495 _forward_branches(_max_block_id, 0),
496 _loop_end_blocks(8),
497 _work_list(8),
498 _linear_scan_order(NULL), // initialized later with correct size
499 _loop_map(0, 0), // initialized later with correct size
500 _compilation(c)
501 {
502 TRACE_LINEAR_SCAN(2, "***** computing linear-scan block order");
503
504 init_visited();
505 count_edges(start_block, NULL);
506
507 if (compilation()->is_profiling()) {
508 ciMethod *method = compilation()->method();
509 if (!method->is_accessor()) {
510 ciMethodData* md = method->method_data_or_null();
511 assert(md != NULL, "Sanity");
512 md->set_compilation_stats(_num_loops, _num_blocks);
513 }
514 }
515
516 if (_num_loops > 0) {
517 mark_loops();
518 clear_non_natural_loops(start_block);
519 assign_loop_depth(start_block);
520 }
521
522 compute_order(start_block);
648
649 // check for non-natural loops (loops where the loop header does not dominate
650 // all other loop blocks = loops with mulitple entries).
651 // such loops are ignored
652 void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) {
653 for (int i = _num_loops - 1; i >= 0; i--) {
654 if (is_block_in_loop(i, start_block)) {
655 // loop i contains the entry block of the method
656 // -> this is not a natural loop, so ignore it
657 TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
658
659 for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
660 clear_block_in_loop(i, block_id);
661 }
662 _iterative_dominators = true;
663 }
664 }
665 }
666
667 void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) {
668 TRACE_LINEAR_SCAN(3, "----- computing loop-depth and weight");
669 init_visited();
670
671 assert(_work_list.is_empty(), "work list must be empty before processing");
672 _work_list.append(start_block);
673
674 do {
675 BlockBegin* cur = _work_list.pop();
676
677 if (!is_visited(cur)) {
678 set_visited(cur);
679 TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id()));
680
681 // compute loop-depth and loop-index for the block
682 assert(cur->loop_depth() == 0, "cannot set loop-depth twice");
683 int i;
684 int loop_depth = 0;
685 int min_loop_idx = -1;
686 for (i = _num_loops - 1; i >= 0; i--) {
687 if (is_block_in_loop(i, cur)) {
688 loop_depth++;
822 #ifdef ASSERT
823 for (int i = 0; i < _work_list.length(); i++) {
824 assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
825 assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
826 }
827 #endif
828 }
829
830 void ComputeLinearScanOrder::append_block(BlockBegin* cur) {
831 TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number()));
832 assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice");
833
834 // currently, the linear scan order and code emit order are equal.
835 // therefore the linear_scan_number and the weight of a block must also
836 // be equal.
837 cur->set_linear_scan_number(_linear_scan_order->length());
838 _linear_scan_order->append(cur);
839 }
840
841 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
842 TRACE_LINEAR_SCAN(3, "----- computing final block order");
843
844 // the start block is always the first block in the linear scan order
845 _linear_scan_order = new BlockList(_num_blocks);
846 append_block(start_block);
847
848 assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
849 BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
850 BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
851
852 BlockBegin* sux_of_osr_entry = NULL;
853 if (osr_entry != NULL) {
854 // special handling for osr entry:
855 // ignore the edge between the osr entry and its successor for processing
856 // the osr entry block is added manually below
857 assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor");
858 assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow");
859
860 sux_of_osr_entry = osr_entry->sux_at(0);
861 dec_forward_branches(sux_of_osr_entry);
862
|
482 BlockList* linear_scan_order() const { return _linear_scan_order; }
483 int num_loops() const { return _num_loops; }
484 };
485
486
487 ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
488 _max_block_id(BlockBegin::number_of_blocks()),
489 _num_blocks(0),
490 _num_loops(0),
491 _iterative_dominators(false),
492 _visited_blocks(_max_block_id),
493 _active_blocks(_max_block_id),
494 _dominator_blocks(_max_block_id),
495 _forward_branches(_max_block_id, 0),
496 _loop_end_blocks(8),
497 _work_list(8),
498 _linear_scan_order(NULL), // initialized later with correct size
499 _loop_map(0, 0), // initialized later with correct size
500 _compilation(c)
501 {
502 TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order"));
503
504 init_visited();
505 count_edges(start_block, NULL);
506
507 if (compilation()->is_profiling()) {
508 ciMethod *method = compilation()->method();
509 if (!method->is_accessor()) {
510 ciMethodData* md = method->method_data_or_null();
511 assert(md != NULL, "Sanity");
512 md->set_compilation_stats(_num_loops, _num_blocks);
513 }
514 }
515
516 if (_num_loops > 0) {
517 mark_loops();
518 clear_non_natural_loops(start_block);
519 assign_loop_depth(start_block);
520 }
521
522 compute_order(start_block);
648
649 // check for non-natural loops (loops where the loop header does not dominate
650 // all other loop blocks = loops with mulitple entries).
651 // such loops are ignored
652 void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) {
653 for (int i = _num_loops - 1; i >= 0; i--) {
654 if (is_block_in_loop(i, start_block)) {
655 // loop i contains the entry block of the method
656 // -> this is not a natural loop, so ignore it
657 TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
658
659 for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
660 clear_block_in_loop(i, block_id);
661 }
662 _iterative_dominators = true;
663 }
664 }
665 }
666
667 void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) {
668 TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing loop-depth and weight"));
669 init_visited();
670
671 assert(_work_list.is_empty(), "work list must be empty before processing");
672 _work_list.append(start_block);
673
674 do {
675 BlockBegin* cur = _work_list.pop();
676
677 if (!is_visited(cur)) {
678 set_visited(cur);
679 TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id()));
680
681 // compute loop-depth and loop-index for the block
682 assert(cur->loop_depth() == 0, "cannot set loop-depth twice");
683 int i;
684 int loop_depth = 0;
685 int min_loop_idx = -1;
686 for (i = _num_loops - 1; i >= 0; i--) {
687 if (is_block_in_loop(i, cur)) {
688 loop_depth++;
822 #ifdef ASSERT
823 for (int i = 0; i < _work_list.length(); i++) {
824 assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
825 assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
826 }
827 #endif
828 }
829
830 void ComputeLinearScanOrder::append_block(BlockBegin* cur) {
831 TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number()));
832 assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice");
833
834 // currently, the linear scan order and code emit order are equal.
835 // therefore the linear_scan_number and the weight of a block must also
836 // be equal.
837 cur->set_linear_scan_number(_linear_scan_order->length());
838 _linear_scan_order->append(cur);
839 }
840
841 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
842 TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order"));
843
844 // the start block is always the first block in the linear scan order
845 _linear_scan_order = new BlockList(_num_blocks);
846 append_block(start_block);
847
848 assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
849 BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
850 BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
851
852 BlockBegin* sux_of_osr_entry = NULL;
853 if (osr_entry != NULL) {
854 // special handling for osr entry:
855 // ignore the edge between the osr entry and its successor for processing
856 // the osr entry block is added manually below
857 assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor");
858 assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow");
859
860 sux_of_osr_entry = osr_entry->sux_at(0);
861 dec_forward_branches(sux_of_osr_entry);
862
|