graal-compiler: src/share/vm/c1/c1

comparison src/share/vm/c1/c1_IR.cpp @ 8860:46f6f063b272

7153771: array bound check elimination for c1 Summary: when possible optimize out array bound checks, inserting predicates when needed. Reviewed-by: never, kvn, twisti Contributed-by: thomaswue <thomas.wuerthinger@oracle.com>

author	roland
date	Thu, 21 Mar 2013 09:27:54 +0100
parents	b9a9ed0f8eeb
children	b9a918201d47 ef57c43512d6

comparison

equal deleted inserted replaced

-:98f3af397705
+:46f6f063b272
 // Implementation of CodeEmitInfo
 // Stack must be NON-null
-CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers)
+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) {
+, _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) {
+, _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);
 }
 _top_scope   = new IRScope(compilation, NULL, -1, method, osr_bci, true);
 _code        = NULL;
 }
-void IR::optimize() {
+void IR::optimize_blocks() {
 Optimizer opt(this);
 if (!compilation()->profile_branches()) {
 if (DoCEE) {
 opt.eliminate_conditional_expressions();
 #ifndef PRODUCT
 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); }
 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(); }
 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()));
 }
 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;
 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, "");
+// 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) {
 }
 }
 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);
 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));
+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()));
 } 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() {
 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)) {
+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->index_of(pred), "incorrect linear_scan_number");
-if (!cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
+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");
 }
 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");
+// 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;
 preds->append(block);
 }
 }
 };
+class VerifyBlockBeginField : public BlockClosure {
+public:
+virtual void block_do(BlockBegin *block) {
+for ( Instruction *cur = block; cur != NULL; cur = cur->next()) {
+assert(cur->block() == block, "Block begin is not correct");
+}
+}
+};
 void IR::verify() {
 #ifdef ASSERT
 PredecessorValidator pv(this);
+VerifyBlockBeginField verifier;
+this->iterate_postorder(&verifier);
 #endif
 }
 #endif // PRODUCT

Mercurial > hg > graal-compiler

comparison src/share/vm/c1/c1_IR.cpp @ 8860:46f6f063b272