jdk-sandbox: comparison src/hotspot/share/opto/loopTransform.cpp

equal deleted inserted replaced

-:a3f1db30ab85
+:bde392011cd8
 set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );
 }
 return n;
 }
-bool PhaseIdealLoop::cast_incr_before_loop(Node* incr, Node* ctrl, Node* loop) {
+Node* PhaseIdealLoop::cast_incr_before_loop(Node* incr, Node* ctrl, Node* loop) {
 Node* castii = new CastIINode(incr, TypeInt::INT, true);
 castii->set_req(0, ctrl);
 register_new_node(castii, ctrl);
 for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
 Node* n = incr->fast_out(i);
 if (n->is_Phi() && n->in(0) == loop) {
 int nrep = n->replace_edge(incr, castii);
-return true;
+return castii;
 }
 }
-return false;
+return NULL;
+}
+// Make a copy of the skeleton range check predicates before the main
+// loop and set the initial value of loop as input. After unrolling,
+// the range of values for the induction variable in the main loop can
+// fall outside the allowed range of values by the array access (main
+// loop is never executed). When that happens, range check
+// CastII/ConvI2L nodes cause some data paths to die. For consistency,
+// the control paths must die too but the range checks were removed by
+// predication. The range checks that we add here guarantee that they
+// do.
+void PhaseIdealLoop::duplicate_predicates(CountedLoopNode* pre_head, Node* min_taken, Node* castii,
+IdealLoopTree* outer_loop, LoopNode* outer_main_head,
+uint dd_main_head) {
+if (UseLoopPredicate) {
+Node* entry = pre_head->in(LoopNode::EntryControl);
+Node* predicate = NULL;
+predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (predicate != NULL) {
+entry = entry->in(0)->in(0);
+}
+predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
+if (predicate != NULL) {
+IfNode* iff = entry->in(0)->as_If();
+ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con);
+Node* rgn = uncommon_proj->unique_ctrl_out();
+assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
+assert(iff->in(1)->in(1)->Opcode() == Op_Opaque1, "unexpected predicate shape");
+entry = entry->in(0)->in(0);
+Node* prev_proj = min_taken;
+while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
+uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con);
+if (uncommon_proj->unique_ctrl_out() != rgn)
+break;
+iff = entry->in(0)->as_If();
+if (iff->in(1)->Opcode() == Op_Opaque4) {
+Node_Stack to_clone(2);
+to_clone.push(iff->in(1), 1);
+uint current = C->unique();
+Node* result = NULL;
+// Look for the opaque node to replace with the init value
+// and clone everything in between. We keep the Opaque4 node
+// so the duplicated predicates are eliminated once loop
+// opts are over: they are here only to keep the IR graph
+// consistent.
+do {
+Node* n = to_clone.node();
+uint i = to_clone.index();
+Node* m = n->in(i);
+int op = m->Opcode();
+if (m->is_Bool() ||
+m->is_Cmp() ||
+op == Op_AndL ||
+op == Op_OrL ||
+op == Op_RShiftL ||
+op == Op_LShiftL ||
+op == Op_AddL ||
+op == Op_AddI ||
+op == Op_MulL ||
+op == Op_MulI ||
+op == Op_SubL ||
+op == Op_SubI ||
+op == Op_ConvI2L) {
+to_clone.push(m, 1);
+continue;
+}
+if (op == Op_Opaque1) {
+if (n->_idx < current) {
+n = n->clone();
+}
+n->set_req(i, castii);
+register_new_node(n, min_taken);
+to_clone.set_node(n);
+}
+for (;;) {
+Node* cur = to_clone.node();
+uint j = to_clone.index();
+if (j+1 < cur->req()) {
+to_clone.set_index(j+1);
+break;
+}
+to_clone.pop();
+if (to_clone.size() == 0) {
+result = cur;
+break;
+}
+Node* next = to_clone.node();
+j = to_clone.index();
+if (cur->_idx >= current) {
+if (next->_idx < current) {
+next = next->clone();
+register_new_node(next, min_taken);
+to_clone.set_node(next);
+}
+assert(next->in(j) != cur, "input should have been cloned");
+next->set_req(j, cur);
+}
+}
+} while (result == NULL);
+assert(result->_idx >= current, "new node expected");
+Node* proj = entry->clone();
+Node* other_proj = uncommon_proj->clone();
+Node* new_iff = iff->clone();
+new_iff->set_req(1, result);
+proj->set_req(0, new_iff);
+other_proj->set_req(0, new_iff);
+Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
+register_new_node(frame, C->start());
+// It's impossible for the predicate to fail at runtime. Use
+// an Halt node.
+Node* halt = new HaltNode(other_proj, frame);
+C->root()->add_req(halt);
+new_iff->set_req(0, prev_proj);
+register_control(new_iff, outer_loop->_parent, prev_proj);
+register_control(proj, outer_loop->_parent, new_iff);
+register_control(other_proj, _ltree_root, new_iff);
+register_control(halt, _ltree_root, other_proj);
+prev_proj = proj;
+}
+entry = entry->in(0)->in(0);
+}
+_igvn.replace_input_of(outer_main_head, LoopNode::EntryControl, prev_proj);
+set_idom(outer_main_head, prev_proj, dd_main_head);
+}
+}
 }
 //------------------------------insert_pre_post_loops--------------------------
 // Insert pre and post loops.  If peel_only is set, the pre-loop can not have
 // more iterations added.  It acts as a 'peel' only, no lower-bound RCE, no
 // the if branch that enters the loop, between the input induction
 // variable value and the induction variable Phi to preserve correct
 // dependencies.
 // CastII for the main loop:
-bool inserted = cast_incr_before_loop( pre_incr, min_taken, main_head );
+Node* castii = cast_incr_before_loop( pre_incr, min_taken, main_head );
-assert(inserted, "no castII inserted");
+assert(castii != NULL, "no castII inserted");
+duplicate_predicates(pre_head, min_taken, castii, outer_loop, outer_main_head, dd_main_head);
 // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
 // RCE and alignment may change this later.
 Node *cmp_end = pre_end->cmp_node();
 assert( cmp_end->in(2) == limit, "" );
 cur_phi->set_req(LoopNode::EntryControl, fallnew);
 }
 }
 // CastII for the new post loop:
-bool inserted = cast_incr_before_loop(zer_opaq->in(1), zer_taken, post_head);
+Node* castii = cast_incr_before_loop(zer_opaq->in(1), zer_taken, post_head);
-assert(inserted, "no castII inserted");
+assert(castii != NULL, "no castII inserted");
 return new_main_exit;
 }
 //------------------------------is_invariant-----------------------------
 // graph shape is encountered, the compiler bails out loop unrolling;
 // compilation of the method will still succeed.
 if (!is_canonical_loop_entry(loop_head)) {
 return;
 }
-opaq = ctrl->in(0)->in(1)->in(1)->in(2);
+opaq = loop_head->skip_predicates()->in(0)->in(1)->in(1)->in(2);
 // Zero-trip test uses an 'opaque' node which is not shared.
 assert(opaq->outcnt() == 1 && opaq->in(1) == limit, "");
 }
 C->set_major_progress();
 }
 }
 return false;
 }
+// Same as PhaseIdealLoop::duplicate_predicates() but for range checks
+// eliminated by iteration splitting.
+Node* PhaseIdealLoop::add_range_check_predicate(IdealLoopTree* loop, CountedLoopNode* cl,
+Node* predicate_proj, int scale_con, Node* offset,
+Node* limit, jint stride_con) {
+bool overflow = false;
+BoolNode* bol = rc_predicate(loop, predicate_proj, scale_con, offset, cl->init_trip(), NULL, stride_con, limit, (stride_con > 0) != (scale_con > 0), overflow);
+Node* opaque_bol = new Opaque4Node(C, bol, _igvn.intcon(1));
+register_new_node(opaque_bol, predicate_proj);
+IfNode* new_iff = NULL;
+if (overflow) {
+new_iff = new IfNode(predicate_proj, bol, PROB_MAX, COUNT_UNKNOWN);
+} else {
+new_iff = new RangeCheckNode(predicate_proj, bol, PROB_MAX, COUNT_UNKNOWN);
+}
+register_control(new_iff, loop->_parent, predicate_proj);
+Node* iffalse = new IfFalseNode(new_iff);
+register_control(iffalse, _ltree_root, new_iff);
+ProjNode* iftrue = new IfTrueNode(new_iff);
+register_control(iftrue, loop->_parent, new_iff);
+Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
+register_new_node(frame, C->start());
+Node* halt = new HaltNode(iffalse, frame);
+register_control(halt, _ltree_root, iffalse);
+C->root()->add_req(halt);
+return iftrue;
+}
 //------------------------------do_range_check---------------------------------
 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
 int PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) {
 #ifndef PRODUCT
 if (PrintOpto && VerifyLoopOptimizations) {
 if (!is_canonical_loop_entry(cl)) {
 return closed_range_checks;
 }
 // Need to find the main-loop zero-trip guard
-Node *ctrl  = cl->skip_strip_mined()->in(LoopNode::EntryControl);
+Node *ctrl  = cl->skip_predicates();
 Node *iffm = ctrl->in(0);
 Node *opqzm = iffm->in(1)->in(1)->in(2);
 assert(opqzm->in(1) == main_limit, "do not understand situation");
 // Find the pre-loop limit; we will expand its iterations to
 // Count number of range checks and reduce by load range limits, if zero,
 // the loop is in canonical form to multiversion.
 closed_range_checks = 0;
+Node* predicate_proj = cl->skip_strip_mined()->in(LoopNode::EntryControl);
+assert(predicate_proj->is_Proj() && predicate_proj->in(0)->is_If(), "if projection only");
 // Check loop body for tests of trip-counter plus loop-invariant vs loop-variant.
 for( uint i = 0; i < loop->_body.size(); i++ ) {
 Node *iff = loop->_body[i];
 if (iff->Opcode() == Op_If ||
 iff->Opcode() == Op_RangeCheck) { // Test?
 // Here we know 'limit' is loop invariant
 // 'limit' maybe pinned below the zero trip test (probably from a
 // previous round of rce), in which case, it can't be used in the
 // zero trip test expression which must occur before the zero test's if.
-if( limit_c == ctrl ) {
+if (is_dominator(ctrl, limit_c)) {
 continue;  // Don't rce this check but continue looking for other candidates.
 }
 // Check for scaled induction variable plus an offset
 Node *offset = NULL;
 continue;               // Offset is not really loop invariant
 // Here we know 'offset' is loop invariant.
 // As above for the 'limit', the 'offset' maybe pinned below the
 // zero trip test.
-if( offset_c == ctrl ) {
+if (is_dominator(ctrl, offset_c)) {
 continue; // Don't rce this check but continue looking for other candidates.
 }
 #ifdef ASSERT
 if (TraceRangeLimitCheck) {
 tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
 if( b_test._test == BoolTest::lt ) { // Range checks always use lt
 // The underflow and overflow limits: 0 <= scale*I+offset < limit
 add_constraint( stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit );
 // (0-offset)/scale could be outside of loop iterations range.
 conditional_rc = true;
+predicate_proj = add_range_check_predicate(loop, cl, predicate_proj, scale_con, offset, limit, stride_con);
 } else {
 if (PrintOpto) {
 tty->print_cr("missed RCE opportunity");
 }
 continue;             // In release mode, ignore it
 closed_range_checks--;
 }
 } // End of is IF
+}
+if (predicate_proj != cl->skip_strip_mined()->in(LoopNode::EntryControl)) {
+_igvn.replace_input_of(cl->skip_strip_mined(), LoopNode::EntryControl, predicate_proj);
+set_idom(cl->skip_strip_mined(), predicate_proj, dom_depth(cl->skip_strip_mined()));
 }
 // Update loop limits
 if (conditional_rc) {
 pre_limit = (stride_con > 0) ? (Node*)new MinINode(pre_limit, orig_limit)
 }
 }
 #ifdef ASSERT
 static CountedLoopNode* locate_pre_from_main(CountedLoopNode *cl) {
-Node *ctrl  = cl->skip_strip_mined()->in(LoopNode::EntryControl);
+Node *ctrl  = cl->skip_predicates();
 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
 Node *iffm = ctrl->in(0);
 assert(iffm->Opcode() == Op_If, "");
 Node *p_f = iffm->in(0);
 assert(p_f->Opcode() == Op_IfFalse, "");
 if (!main_head->is_main_loop()) {
 return;
 }
 assert(locate_pre_from_main(main_head) == cl, "bad main loop");
-Node* main_iff = main_head->skip_strip_mined()->in(LoopNode::EntryControl)->in(0);
+Node* main_iff = main_head->skip_predicates()->in(0);
 // Remove the Opaque1Node of the pre loop and make it execute all iterations
 phase->_igvn.replace_input_of(pre_cmp, 2, pre_cmp->in(2)->in(2));
 // Remove the Opaque1Node of the main loop so it can be optimized out
 Node* main_cmp = main_iff->in(1)->in(1);
 needs_guard = (init_t->_lo <= limit_t->_hi);
 }
 }
 if (needs_guard) {
 // Check for an obvious zero trip guard.
-Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->skip_strip_mined()->in(LoopNode::EntryControl));
+Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->skip_predicates());
 if (inctrl->Opcode() == Op_IfTrue || inctrl->Opcode() == Op_IfFalse) {
 bool maybe_swapped = (inctrl->Opcode() == Op_IfFalse);
 // The test should look like just the backedge of a CountedLoop
 Node* iff = inctrl->in(0);
 if (iff->is_If()) {

changeset 49487	bde392011cd8
parent 48603	e5da6c246176
child 49600	d7c83c8e4e65