Created
August 2, 2017 09:06
-
-
Save t81lal/5205c676928d3f537a3b6ada08bf3219 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class ComputeLinearScanOrder : public StackObj { | |
private: | |
int _max_block_id; // the highest block_id of a block | |
int _num_blocks; // total number of blocks (smaller than _max_block_id) | |
int _num_loops; // total number of loops | |
bool _iterative_dominators;// method requires iterative computation of dominatiors | |
BlockList* _linear_scan_order; // the resulting list of blocks in correct order | |
ResourceBitMap _visited_blocks; // used for recursive processing of blocks | |
ResourceBitMap _active_blocks; // used for recursive processing of blocks | |
ResourceBitMap _dominator_blocks; // temproary BitMap used for computation of dominator | |
intArray _forward_branches; // number of incoming forward branches for each block | |
BlockList _loop_end_blocks; // list of all loop end blocks collected during count_edges | |
BitMap2D _loop_map; // two-dimensional bit set: a bit is set if a block is contained in a loop | |
BlockList _work_list; // temporary list (used in mark_loops and compute_order) | |
BlockList _loop_headers; | |
Compilation* _compilation; | |
// accessors for _visited_blocks and _active_blocks | |
void init_visited() { _active_blocks.clear(); _visited_blocks.clear(); } | |
bool is_visited(BlockBegin* b) const { return _visited_blocks.at(b->block_id()); } | |
bool is_active(BlockBegin* b) const { return _active_blocks.at(b->block_id()); } | |
void set_visited(BlockBegin* b) { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); } | |
void set_active(BlockBegin* b) { assert(!is_active(b), "already set"); _active_blocks.set_bit(b->block_id()); } | |
void clear_active(BlockBegin* b) { assert(is_active(b), "not already"); _active_blocks.clear_bit(b->block_id()); } | |
// accessors for _forward_branches | |
void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); } | |
int dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); } | |
// accessors for _loop_map | |
bool is_block_in_loop (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); } | |
void set_block_in_loop (int loop_idx, BlockBegin* b) { _loop_map.set_bit(loop_idx, b->block_id()); } | |
void clear_block_in_loop(int loop_idx, int block_id) { _loop_map.clear_bit(loop_idx, block_id); } | |
// count edges between blocks | |
void count_edges(BlockBegin* cur, BlockBegin* parent); | |
// loop detection | |
void mark_loops(); | |
void clear_non_natural_loops(BlockBegin* start_block); | |
void assign_loop_depth(BlockBegin* start_block); | |
// computation of final block order | |
BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b); | |
void compute_dominator(BlockBegin* cur, BlockBegin* parent); | |
int compute_weight(BlockBegin* cur); | |
bool ready_for_processing(BlockBegin* cur); | |
void sort_into_work_list(BlockBegin* b); | |
void append_block(BlockBegin* cur); | |
void compute_order(BlockBegin* start_block); | |
// fixup of dominators for non-natural loops | |
bool compute_dominators_iter(); | |
void compute_dominators(); | |
// debug functions | |
NOT_PRODUCT(void print_blocks();) | |
DEBUG_ONLY(void verify();) | |
Compilation* compilation() const { return _compilation; } | |
public: | |
ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block); | |
// accessors for final result | |
BlockList* linear_scan_order() const { return _linear_scan_order; } | |
int num_loops() const { return _num_loops; } | |
}; | |
ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) : | |
_max_block_id(BlockBegin::number_of_blocks()), | |
_num_blocks(0), | |
_num_loops(0), | |
_iterative_dominators(false), | |
_visited_blocks(_max_block_id), | |
_active_blocks(_max_block_id), | |
_dominator_blocks(_max_block_id), | |
_forward_branches(_max_block_id, _max_block_id, 0), | |
_loop_end_blocks(8), | |
_work_list(8), | |
_linear_scan_order(NULL), // initialized later with correct size | |
_loop_map(0), // initialized later with correct size | |
_compilation(c) | |
{ | |
TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order")); | |
count_edges(start_block, NULL); | |
if (compilation()->is_profiling()) { | |
ciMethod *method = compilation()->method(); | |
if (!method->is_accessor()) { | |
ciMethodData* md = method->method_data_or_null(); | |
assert(md != NULL, "Sanity"); | |
md->set_compilation_stats(_num_loops, _num_blocks); | |
} | |
} | |
if (_num_loops > 0) { | |
mark_loops(); | |
clear_non_natural_loops(start_block); | |
assign_loop_depth(start_block); | |
} | |
compute_order(start_block); | |
compute_dominators(); | |
NOT_PRODUCT(print_blocks()); | |
DEBUG_ONLY(verify()); | |
} | |
// Traverse the CFG: | |
// * count total number of blocks | |
// * count all incoming edges and backward incoming edges | |
// * number loop header blocks | |
// * create a list with all loop end blocks | |
void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != NULL ? parent->block_id() : -1)); | |
assert(cur->dominator() == NULL, "dominator already initialized"); | |
if (is_active(cur)) { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch")); | |
assert(is_visited(cur), "block must be visisted when block is active"); | |
assert(parent != NULL, "must have parent"); | |
cur->set(BlockBegin::backward_branch_target_flag); | |
// When a loop header is also the start of an exception handler, then the backward branch is | |
// an exception edge. Because such edges are usually critical edges which cannot be split, the | |
// loop must be excluded here from processing. | |
if (cur->is_set(BlockBegin::exception_entry_flag)) { | |
// Make sure that dominators are correct in this weird situation | |
_iterative_dominators = true; | |
return; | |
} | |
cur->set(BlockBegin::linear_scan_loop_header_flag); | |
parent->set(BlockBegin::linear_scan_loop_end_flag); | |
assert(parent->number_of_sux() == 1 && parent->sux_at(0) == cur, | |
"loop end blocks must have one successor (critical edges are split)"); | |
_loop_end_blocks.append(parent); | |
return; | |
} | |
// increment number of incoming forward branches | |
inc_forward_branches(cur); | |
if (is_visited(cur)) { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited")); | |
return; | |
} | |
_num_blocks++; | |
set_visited(cur); | |
set_active(cur); | |
// recursive call for all successors | |
int i; | |
for (i = cur->number_of_sux() - 1; i >= 0; i--) { | |
count_edges(cur->sux_at(i), cur); | |
} | |
for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { | |
count_edges(cur->exception_handler_at(i), cur); | |
} | |
clear_active(cur); | |
// Each loop has a unique number. | |
// When multiple loops are nested, assign_loop_depth assumes that the | |
// innermost loop has the lowest number. This is guaranteed by setting | |
// the loop number after the recursive calls for the successors above | |
// have returned. | |
if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) { | |
assert(cur->loop_index() == -1, "cannot set loop-index twice"); | |
TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops)); | |
cur->set_loop_index(_num_loops); | |
_loop_headers.append(cur); | |
_num_loops++; | |
} | |
TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id())); | |
} | |
void ComputeLinearScanOrder::mark_loops() { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops")); | |
_loop_map = BitMap2D(_num_loops, _max_block_id); | |
for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) { | |
BlockBegin* loop_end = _loop_end_blocks.at(i); | |
BlockBegin* loop_start = loop_end->sux_at(0); | |
int loop_idx = loop_start->loop_index(); | |
TRACE_LINEAR_SCAN(3, tty->print_cr("Processing loop from B%d to B%d (loop %d):", loop_start->block_id(), loop_end->block_id(), loop_idx)); | |
assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set"); | |
assert(loop_end->number_of_sux() == 1, "incorrect number of successors"); | |
assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set"); | |
assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set"); | |
assert(_work_list.is_empty(), "work list must be empty before processing"); | |
// add the end-block of the loop to the working list | |
_work_list.push(loop_end); | |
set_block_in_loop(loop_idx, loop_end); | |
do { | |
BlockBegin* cur = _work_list.pop(); | |
TRACE_LINEAR_SCAN(3, tty->print_cr(" processing B%d", cur->block_id())); | |
assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list"); | |
// recursive processing of all predecessors ends when start block of loop is reached | |
if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) { | |
for (int j = cur->number_of_preds() - 1; j >= 0; j--) { | |
BlockBegin* pred = cur->pred_at(j); | |
if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) { | |
// this predecessor has not been processed yet, so add it to work list | |
TRACE_LINEAR_SCAN(3, tty->print_cr(" pushing B%d", pred->block_id())); | |
_work_list.push(pred); | |
set_block_in_loop(loop_idx, pred); | |
} | |
} | |
} | |
} while (!_work_list.is_empty()); | |
} | |
} | |
// check for non-natural loops (loops where the loop header does not dominate | |
// all other loop blocks = loops with mulitple entries). | |
// such loops are ignored | |
void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) { | |
for (int i = _num_loops - 1; i >= 0; i--) { | |
if (is_block_in_loop(i, start_block)) { | |
// loop i contains the entry block of the method | |
// -> this is not a natural loop, so ignore it | |
TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i)); | |
BlockBegin *loop_header = _loop_headers.at(i); | |
assert(loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Must be loop header"); | |
for (int j = 0; j < loop_header->number_of_preds(); j++) { | |
BlockBegin *pred = loop_header->pred_at(j); | |
pred->clear(BlockBegin::linear_scan_loop_end_flag); | |
} | |
loop_header->clear(BlockBegin::linear_scan_loop_header_flag); | |
for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) { | |
clear_block_in_loop(i, block_id); | |
} | |
_iterative_dominators = true; | |
} | |
} | |
} | |
void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing loop-depth and weight")); | |
init_visited(); | |
assert(_work_list.is_empty(), "work list must be empty before processing"); | |
_work_list.append(start_block); | |
do { | |
BlockBegin* cur = _work_list.pop(); | |
if (!is_visited(cur)) { | |
set_visited(cur); | |
TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id())); | |
// compute loop-depth and loop-index for the block | |
assert(cur->loop_depth() == 0, "cannot set loop-depth twice"); | |
int i; | |
int loop_depth = 0; | |
int min_loop_idx = -1; | |
for (i = _num_loops - 1; i >= 0; i--) { | |
if (is_block_in_loop(i, cur)) { | |
loop_depth++; | |
min_loop_idx = i; | |
} | |
} | |
cur->set_loop_depth(loop_depth); | |
cur->set_loop_index(min_loop_idx); | |
// append all unvisited successors to work list | |
for (i = cur->number_of_sux() - 1; i >= 0; i--) { | |
_work_list.append(cur->sux_at(i)); | |
} | |
for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) { | |
_work_list.append(cur->exception_handler_at(i)); | |
} | |
} | |
} while (!_work_list.is_empty()); | |
} | |
BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) { | |
assert(a != NULL && b != NULL, "must have input blocks"); | |
_dominator_blocks.clear(); | |
while (a != NULL) { | |
_dominator_blocks.set_bit(a->block_id()); | |
assert(a->dominator() != NULL || a == _linear_scan_order->at(0), "dominator must be initialized"); | |
a = a->dominator(); | |
} | |
while (b != NULL && !_dominator_blocks.at(b->block_id())) { | |
assert(b->dominator() != NULL || b == _linear_scan_order->at(0), "dominator must be initialized"); | |
b = b->dominator(); | |
} | |
assert(b != NULL, "could not find dominator"); | |
return b; | |
} | |
void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) { | |
if (cur->dominator() == NULL) { | |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id())); | |
cur->set_dominator(parent); | |
} else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) { | |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id())); | |
// Does not hold for exception blocks | |
assert(cur->number_of_preds() > 1 || cur->is_set(BlockBegin::exception_entry_flag), ""); | |
cur->set_dominator(common_dominator(cur->dominator(), parent)); | |
} | |
// Additional edge to xhandler of all our successors | |
// range check elimination needs that the state at the end of a | |
// block be valid in every block it dominates so cur must dominate | |
// the exception handlers of its successors. | |
int num_cur_xhandler = cur->number_of_exception_handlers(); | |
for (int j = 0; j < num_cur_xhandler; j++) { | |
BlockBegin* xhandler = cur->exception_handler_at(j); | |
compute_dominator(xhandler, parent); | |
} | |
} | |
int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) { | |
BlockBegin* single_sux = NULL; | |
if (cur->number_of_sux() == 1) { | |
single_sux = cur->sux_at(0); | |
} | |
// limit loop-depth to 15 bit (only for security reason, it will never be so big) | |
int weight = (cur->loop_depth() & 0x7FFF) << 16; | |
// general macro for short definition of weight flags | |
// the first instance of INC_WEIGHT_IF has the highest priority | |
int cur_bit = 15; | |
#define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--; | |
// this is necessery for the (very rare) case that two successing blocks have | |
// the same loop depth, but a different loop index (can happen for endless loops | |
// with exception handlers) | |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag)); | |
// loop end blocks (blocks that end with a backward branch) are added | |
// after all other blocks of the loop. | |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag)); | |
// critical edge split blocks are prefered because than they have a bigger | |
// proability to be completely empty | |
INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag)); | |
// exceptions should not be thrown in normal control flow, so these blocks | |
// are added as late as possible | |
INC_WEIGHT_IF(cur->end()->as_Throw() == NULL && (single_sux == NULL || single_sux->end()->as_Throw() == NULL)); | |
INC_WEIGHT_IF(cur->end()->as_Return() == NULL && (single_sux == NULL || single_sux->end()->as_Return() == NULL)); | |
// exceptions handlers are added as late as possible | |
INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag)); | |
// guarantee that weight is > 0 | |
weight |= 1; | |
#undef INC_WEIGHT_IF | |
assert(cur_bit >= 0, "too many flags"); | |
assert(weight > 0, "weight cannot become negative"); | |
return weight; | |
} | |
bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) { | |
// Discount the edge just traveled. | |
// When the number drops to zero, all forward branches were processed | |
if (dec_forward_branches(cur) != 0) { | |
return false; | |
} | |
assert(_linear_scan_order->find(cur) == -1, "block already processed (block can be ready only once)"); | |
assert(_work_list.find(cur) == -1, "block already in work-list (block can be ready only once)"); | |
return true; | |
} | |
void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) { | |
assert(_work_list.find(cur) == -1, "block already in work list"); | |
int cur_weight = compute_weight(cur); | |
// the linear_scan_number is used to cache the weight of a block | |
cur->set_linear_scan_number(cur_weight); | |
#ifndef PRODUCT | |
if (StressLinearScan) { | |
_work_list.insert_before(0, cur); | |
return; | |
} | |
#endif | |
_work_list.append(NULL); // provide space for new element | |
int insert_idx = _work_list.length() - 1; | |
while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) { | |
_work_list.at_put(insert_idx, _work_list.at(insert_idx - 1)); | |
insert_idx--; | |
} | |
_work_list.at_put(insert_idx, cur); | |
TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id())); | |
TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number())); | |
#ifdef ASSERT | |
for (int i = 0; i < _work_list.length(); i++) { | |
assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set"); | |
assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist"); | |
} | |
#endif | |
} | |
void ComputeLinearScanOrder::append_block(BlockBegin* cur) { | |
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())); | |
assert(_linear_scan_order->find(cur) == -1, "cannot add the same block twice"); | |
// currently, the linear scan order and code emit order are equal. | |
// therefore the linear_scan_number and the weight of a block must also | |
// be equal. | |
cur->set_linear_scan_number(_linear_scan_order->length()); | |
_linear_scan_order->append(cur); | |
} | |
void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order")); | |
// the start block is always the first block in the linear scan order | |
_linear_scan_order = new BlockList(_num_blocks); | |
append_block(start_block); | |
assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction"); | |
BlockBegin* std_entry = ((Base*)start_block->end())->std_entry(); | |
BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry(); | |
BlockBegin* sux_of_osr_entry = NULL; | |
if (osr_entry != NULL) { | |
// special handling for osr entry: | |
// ignore the edge between the osr entry and its successor for processing | |
// the osr entry block is added manually below | |
assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor"); | |
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"); | |
sux_of_osr_entry = osr_entry->sux_at(0); | |
dec_forward_branches(sux_of_osr_entry); | |
compute_dominator(osr_entry, start_block); | |
_iterative_dominators = true; | |
} | |
compute_dominator(std_entry, start_block); | |
// start processing with standard entry block | |
assert(_work_list.is_empty(), "list must be empty before processing"); | |
if (ready_for_processing(std_entry)) { | |
sort_into_work_list(std_entry); | |
} else { | |
assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)"); | |
} | |
do { | |
BlockBegin* cur = _work_list.pop(); | |
if (cur == sux_of_osr_entry) { | |
// the osr entry block is ignored in normal processing, it is never added to the | |
// work list. Instead, it is added as late as possible manually here. | |
append_block(osr_entry); | |
compute_dominator(cur, osr_entry); | |
} | |
append_block(cur); | |
int i; | |
int num_sux = cur->number_of_sux(); | |
// changed loop order to get "intuitive" order of if- and else-blocks | |
for (i = 0; i < num_sux; i++) { | |
BlockBegin* sux = cur->sux_at(i); | |
compute_dominator(sux, cur); | |
if (ready_for_processing(sux)) { | |
sort_into_work_list(sux); | |
} | |
} | |
num_sux = cur->number_of_exception_handlers(); | |
for (i = 0; i < num_sux; i++) { | |
BlockBegin* sux = cur->exception_handler_at(i); | |
if (ready_for_processing(sux)) { | |
sort_into_work_list(sux); | |
} | |
} | |
} while (_work_list.length() > 0); | |
} | |
bool ComputeLinearScanOrder::compute_dominators_iter() { | |
bool changed = false; | |
int num_blocks = _linear_scan_order->length(); | |
assert(_linear_scan_order->at(0)->dominator() == NULL, "must not have dominator"); | |
assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors"); | |
for (int i = 1; i < num_blocks; i++) { | |
BlockBegin* block = _linear_scan_order->at(i); | |
BlockBegin* dominator = block->pred_at(0); | |
int num_preds = block->number_of_preds(); | |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: Processing B%d", block->block_id())); | |
for (int j = 0; j < num_preds; j++) { | |
BlockBegin *pred = block->pred_at(j); | |
TRACE_LINEAR_SCAN(4, tty->print_cr(" DOM: Subrocessing B%d", pred->block_id())); | |
if (block->is_set(BlockBegin::exception_entry_flag)) { | |
dominator = common_dominator(dominator, pred); | |
int num_pred_preds = pred->number_of_preds(); | |
for (int k = 0; k < num_pred_preds; k++) { | |
dominator = common_dominator(dominator, pred->pred_at(k)); | |
} | |
} else { | |
dominator = common_dominator(dominator, pred); | |
} | |
} | |
if (dominator != block->dominator()) { | |
TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: updating dominator of B%d from B%d to B%d", block->block_id(), block->dominator()->block_id(), dominator->block_id())); | |
block->set_dominator(dominator); | |
changed = true; | |
} | |
} | |
return changed; | |
} | |
void ComputeLinearScanOrder::compute_dominators() { | |
TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators)); | |
// iterative computation of dominators is only required for methods with non-natural loops | |
// and OSR-methods. For all other methods, the dominators computed when generating the | |
// linear scan block order are correct. | |
if (_iterative_dominators) { | |
do { | |
TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation")); | |
} while (compute_dominators_iter()); | |
} | |
// check that dominators are correct | |
assert(!compute_dominators_iter(), "fix point not reached"); | |
// Add Blocks to dominates-Array | |
int num_blocks = _linear_scan_order->length(); | |
for (int i = 0; i < num_blocks; i++) { | |
BlockBegin* block = _linear_scan_order->at(i); | |
BlockBegin *dom = block->dominator(); | |
if (dom) { | |
assert(dom->dominator_depth() != -1, "Dominator must have been visited before"); | |
dom->dominates()->append(block); | |
block->set_dominator_depth(dom->dominator_depth() + 1); | |
} else { | |
block->set_dominator_depth(0); | |
} | |
} | |
} | |
#ifndef PRODUCT | |
void ComputeLinearScanOrder::print_blocks() { | |
if (TraceLinearScanLevel >= 2) { | |
tty->print_cr("----- loop information:"); | |
for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { | |
BlockBegin* cur = _linear_scan_order->at(block_idx); | |
tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id()); | |
for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { | |
tty->print ("%d ", is_block_in_loop(loop_idx, cur)); | |
} | |
tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth()); | |
} | |
} | |
if (TraceLinearScanLevel >= 1) { | |
tty->print_cr("----- linear-scan block order:"); | |
for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) { | |
BlockBegin* cur = _linear_scan_order->at(block_idx); | |
tty->print("%4d: B%2d loop: %2d depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth()); | |
tty->print(cur->is_set(BlockBegin::exception_entry_flag) ? " ex" : " "); | |
tty->print(cur->is_set(BlockBegin::critical_edge_split_flag) ? " ce" : " "); | |
tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : " "); | |
tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag) ? " le" : " "); | |
if (cur->dominator() != NULL) { | |
tty->print(" dom: B%d ", cur->dominator()->block_id()); | |
} else { | |
tty->print(" dom: NULL "); | |
} | |
if (cur->number_of_preds() > 0) { | |
tty->print(" preds: "); | |
for (int j = 0; j < cur->number_of_preds(); j++) { | |
BlockBegin* pred = cur->pred_at(j); | |
tty->print("B%d ", pred->block_id()); | |
} | |
} | |
if (cur->number_of_sux() > 0) { | |
tty->print(" sux: "); | |
for (int j = 0; j < cur->number_of_sux(); j++) { | |
BlockBegin* sux = cur->sux_at(j); | |
tty->print("B%d ", sux->block_id()); | |
} | |
} | |
if (cur->number_of_exception_handlers() > 0) { | |
tty->print(" ex: "); | |
for (int j = 0; j < cur->number_of_exception_handlers(); j++) { | |
BlockBegin* ex = cur->exception_handler_at(j); | |
tty->print("B%d ", ex->block_id()); | |
} | |
} | |
tty->cr(); | |
} | |
} | |
} | |
#endif | |
#ifdef ASSERT | |
void ComputeLinearScanOrder::verify() { | |
assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list"); | |
if (StressLinearScan) { | |
// blocks are scrambled when StressLinearScan is used | |
return; | |
} | |
// check that all successors of a block have a higher linear-scan-number | |
// and that all predecessors of a block have a lower linear-scan-number | |
// (only backward branches of loops are ignored) | |
int i; | |
for (i = 0; i < _linear_scan_order->length(); i++) { | |
BlockBegin* cur = _linear_scan_order->at(i); | |
assert(cur->linear_scan_number() == i, "incorrect linear_scan_number"); | |
assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->find(cur), "incorrect linear_scan_number"); | |
int j; | |
for (j = cur->number_of_sux() - 1; j >= 0; j--) { | |
BlockBegin* sux = cur->sux_at(j); | |
assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->find(sux), "incorrect linear_scan_number"); | |
if (!sux->is_set(BlockBegin::backward_branch_target_flag)) { | |
assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order"); | |
} | |
if (cur->loop_depth() == sux->loop_depth()) { | |
assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); | |
} | |
} | |
for (j = cur->number_of_preds() - 1; j >= 0; j--) { | |
BlockBegin* pred = cur->pred_at(j); | |
assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->find(pred), "incorrect linear_scan_number"); | |
if (!cur->is_set(BlockBegin::backward_branch_target_flag)) { | |
assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order"); | |
} | |
if (cur->loop_depth() == pred->loop_depth()) { | |
assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index"); | |
} | |
assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors"); | |
} | |
// check dominator | |
if (i == 0) { | |
assert(cur->dominator() == NULL, "first block has no dominator"); | |
} else { | |
assert(cur->dominator() != NULL, "all but first block must have dominator"); | |
} | |
// Assertion does not hold for exception handlers | |
assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator"); | |
} | |
// check that all loops are continuous | |
for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) { | |
int block_idx = 0; | |
assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop"); | |
// skip blocks before the loop | |
while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { | |
block_idx++; | |
} | |
// skip blocks of loop | |
while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) { | |
block_idx++; | |
} | |
// after the first non-loop block, there must not be another loop-block | |
while (block_idx < _num_blocks) { | |
assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order"); | |
block_idx++; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment