src/share/vm/c1/c1_IR.cpp

Print this page
rev 4136 : 7153771: array bound check elimination for c1
Summary: when possible optimize out array bound checks, inserting predicates when needed.
Reviewed-by:

*** 180,207 **** // Implementation of CodeEmitInfo // Stack must be NON-null ! CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers) : _scope(stack->scope()) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack) , _exception_handlers(exception_handlers) ! , _is_method_handle_invoke(false) { assert(_stack != NULL, "must be non null"); } CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack) : _scope(info->_scope) , _exception_handlers(NULL) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack == NULL ? info->_stack : stack) ! , _is_method_handle_invoke(info->_is_method_handle_invoke) { // deep copy of exception handlers if (info->_exception_handlers != NULL) { _exception_handlers = new XHandlers(info->_exception_handlers); } --- 180,209 ---- // Implementation of CodeEmitInfo // Stack must be NON-null ! CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers, bool deoptimize_on_exception) : _scope(stack->scope()) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack) , _exception_handlers(exception_handlers) ! , _is_method_handle_invoke(false) ! , _deoptimize_on_exception(deoptimize_on_exception) { assert(_stack != NULL, "must be non null"); } CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack) : _scope(info->_scope) , _exception_handlers(NULL) , _scope_debug_info(NULL) , _oop_map(NULL) , _stack(stack == NULL ? info->_stack : stack) ! , _is_method_handle_invoke(info->_is_method_handle_invoke) ! , _deoptimize_on_exception(info->_deoptimize_on_exception) { // deep copy of exception handlers if (info->_exception_handlers != NULL) { _exception_handlers = new XHandlers(info->_exception_handlers); }
*** 237,247 **** _top_scope = new IRScope(compilation, NULL, -1, method, osr_bci, true); _code = NULL; } ! void IR::optimize() { Optimizer opt(this); if (!compilation()->profile_branches()) { if (DoCEE) { opt.eliminate_conditional_expressions(); #ifndef PRODUCT --- 239,249 ---- _top_scope = new IRScope(compilation, NULL, -1, method, osr_bci, true); _code = NULL; } ! void IR::optimize_blocks() { Optimizer opt(this); if (!compilation()->profile_branches()) { if (DoCEE) { opt.eliminate_conditional_expressions(); #ifndef PRODUCT
*** 255,264 **** --- 257,270 ---- if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); } if (PrintIR || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); } #endif } } + } + + void IR::eliminate_null_checks() { + Optimizer opt(this); if (EliminateNullChecks) { opt.eliminate_null_checks(); #ifndef PRODUCT if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); } if (PrintIR || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); }
*** 427,436 **** --- 433,443 ---- BitMap _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(); }
*** 592,601 **** --- 599,609 ---- 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())); }
*** 654,663 **** --- 662,682 ---- 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; }
*** 727,739 **** 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())); ! assert(cur->number_of_preds() > 1, ""); cur->set_dominator(common_dominator(cur->dominator(), parent)); } } int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) { BlockBegin* single_sux = NULL; --- 746,769 ---- 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;
*** 896,906 **** } } num_sux = cur->number_of_exception_handlers(); for (i = 0; i < num_sux; i++) { BlockBegin* sux = cur->exception_handler_at(i); - compute_dominator(sux, cur); if (ready_for_processing(sux)) { sort_into_work_list(sux); } } } while (_work_list.length() > 0); --- 926,935 ----
*** 916,927 **** 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(); ! for (int i = 1; i < num_preds; i++) { ! dominator = common_dominator(dominator, block->pred_at(i)); } 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())); --- 945,971 ---- 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()));
*** 944,953 **** --- 988,1012 ---- } 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() {
*** 1030,1040 **** 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->index_of(sux), "incorrect linear_scan_number"); ! if (!cur->is_set(BlockBegin::linear_scan_loop_end_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"); } --- 1089,1099 ---- 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->index_of(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"); }
*** 1042,1052 **** 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->index_of(pred), "incorrect linear_scan_number"); ! if (!cur->is_set(BlockBegin::linear_scan_loop_header_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"); } --- 1101,1111 ---- 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->index_of(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"); }
*** 1058,1068 **** if (i == 0) { assert(cur->dominator() == NULL, "first block has no dominator"); } else { assert(cur->dominator() != NULL, "all but first block must have dominator"); } ! assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0), "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; --- 1117,1128 ---- 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;
*** 1247,1259 **** --- 1307,1335 ---- preds->append(block); } } }; + class VerifyBlockBeginField : public BlockClosure { + + public: + + virtual void block_do(BlockBegin *block) { + + Instruction *cur = block; + while (cur) { + assert(cur->block() == block, "Block begin is not correct"); + cur = cur->next(); + } + } + }; + void IR::verify() { #ifdef ASSERT PredecessorValidator pv(this); + VerifyBlockBeginField verifier; + this->iterate_postorder(&verifier); #endif } #endif // PRODUCT