truffle: src/share/vm/opto/loopPredicate.cpp comparison

comparison src/share/vm/opto/loopPredicate.cpp @ 3345:bad7ecd0b6ed

5091921: Sign flip issues in loop optimizer Summary: Fix integer overflow problem in the code generated by loop optimizer. Reviewed-by: never

author	kvn
date	Wed, 04 May 2011 13:12:42 -0700
parents	2e038ad0c1d0
children	4e761e7e6e12

comparison

equal deleted inserted replaced

-:0139aac70fb5
+:bad7ecd0b6ed
 Node* old_entry = iff->in(0);
 // Cut predicate from old place.
 Node* old = predicate_proj;
 igvn->_worklist.push(old);
-for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) {
+for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin;) {
 Node* use = old->last_out(i);  // for each use...
 igvn->hash_delete(use);
 igvn->_worklist.push(use);
 // Update use-def info
 uint uses_found = 0;
 return predicate_proj;
 }
 //--------------------------clone_loop_predicates-----------------------
 // Interface from IGVN
-Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry) {
+Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
-return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, false, NULL, this);
+return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, false, clone_limit_check, NULL, this);
 }
-Node* PhaseIterGVN::move_loop_predicates(Node* old_entry, Node* new_entry) {
+Node* PhaseIterGVN::move_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
-return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, true, NULL, this);
+return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, true, clone_limit_check, NULL, this);
 }
 // Interface from PhaseIdealLoop
-Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry) {
+Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
-return clone_loop_predicates(old_entry, new_entry, false, this, &this->_igvn);
+return clone_loop_predicates(old_entry, new_entry, false, clone_limit_check, this, &this->_igvn);
 }
-Node* PhaseIdealLoop::move_loop_predicates(Node* old_entry, Node* new_entry) {
+Node* PhaseIdealLoop::move_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) {
-return clone_loop_predicates(old_entry, new_entry, true, this, &this->_igvn);
+return clone_loop_predicates(old_entry, new_entry, true, clone_limit_check, this, &this->_igvn);
 }
 // Clone loop predicates to cloned loops (peeled, unswitched, split_if).
 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry,
 bool move_predicates,
+bool clone_limit_check,
 PhaseIdealLoop* loop_phase,
 PhaseIterGVN* igvn) {
 #ifdef ASSERT
 if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) {
 if (new_entry != NULL)
 assert(false, "not IfTrue, IfFalse, Region or SafePoint");
 }
 #endif
 // Search original predicates
 Node* entry = old_entry;
+ProjNode* limit_check_proj = NULL;
+if (LoopLimitCheck) {
+limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (limit_check_proj != NULL) {
+entry = entry->in(0)->in(0);
+}
+}
 if (UseLoopPredicate) {
 ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 if (predicate_proj != NULL) { // right pattern that can be used by loop predication
-assert(entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be");
 if (move_predicates) {
 new_entry =  move_predicate(predicate_proj, new_entry,
 Deoptimization::Reason_predicate,
 loop_phase, igvn);
 assert(new_entry == predicate_proj, "old predicate fall through projection");
 tty->print_cr("Loop Predicate %s: ", move_predicates ? "moved" : "cloned");
 debug_only( new_entry->in(0)->dump(); )
 }
 }
 }
+if (limit_check_proj != NULL && clone_limit_check) {
+// Clone loop limit check last to insert it before loop.
+// Don't clone a limit check which was already finalized
+// for this counted loop (only one limit check is needed).
+if (move_predicates) {
+new_entry =  move_predicate(limit_check_proj, new_entry,
+Deoptimization::Reason_loop_limit_check,
+loop_phase, igvn);
+assert(new_entry == limit_check_proj, "old limit check fall through projection");
+} else {
+new_entry = clone_predicate(limit_check_proj, new_entry,
+Deoptimization::Reason_loop_limit_check,
+loop_phase, igvn);
+assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check");
+}
+if (TraceLoopLimitCheck) {
+tty->print_cr("Loop Limit Check %s: ", move_predicates ? "moved" : "cloned");
+debug_only( new_entry->in(0)->dump(); )
+}
+}
 return new_entry;
 }
 //--------------------------eliminate_loop_predicates-----------------------
 void PhaseIdealLoop::eliminate_loop_predicates(Node* entry) {
+if (LoopLimitCheck) {
+Node* predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (predicate != NULL) {
+entry = entry->in(0)->in(0);
+}
+}
 if (UseLoopPredicate) {
 ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 if (predicate_proj != NULL) { // right pattern that can be used by loop predication
 Node* n = entry->in(0)->in(1)->in(1);
 assert(n->Opcode()==Op_Opaque1, "must be");
 //--------------------------skip_loop_predicates------------------------------
 // Skip related predicates.
 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) {
 Node* predicate = NULL;
+if (LoopLimitCheck) {
+predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (predicate != NULL) {
+entry = entry->in(0)->in(0);
+}
+}
 if (UseLoopPredicate) {
 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 if (predicate != NULL) { // right pattern that can be used by loop predication
-assert(entry->is_Proj() && entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be");
 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");
 entry = entry->in(0)->in(0);
 //--------------------------find_predicate------------------------------------
 // Find a predicate
 Node* PhaseIdealLoop::find_predicate(Node* entry) {
 Node* predicate = NULL;
+if (LoopLimitCheck) {
+predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (predicate != NULL) { // right pattern that can be used by loop predication
+return entry;
+}
+}
 if (UseLoopPredicate) {
 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 if (predicate != NULL) { // right pattern that can be used by loop predication
-assert(entry->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be");
 return entry;
 }
 }
 return NULL;
 }
 return false;
 }
 Node* range = cmp->in(2);
 if (range->Opcode() != Op_LoadRange) {
 const TypeInt* tint = phase->_igvn.type(range)->isa_int();
-if (!OptimizeFill || tint == NULL || tint->empty() || tint->_lo < 0) {
+if (tint == NULL || tint->empty() || tint->_lo < 0) {
 // Allow predication on positive values that aren't LoadRanges.
 // This allows optimization of loops where the length of the
 // array is a known value and doesn't need to be loaded back
 // from the array.
 return false;
 // There are two cases for max(scale*i + offset):
 // (1) stride*scale > 0
 //   max(scale*i + offset) = scale*(limit-stride) + offset
 // (2) stride*scale < 0
 //   max(scale*i + offset) = scale*init + offset
-BoolNode* PhaseIdealLoop::rc_predicate(Node* ctrl,
+BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl,
 int scale, Node* offset,
 Node* init, Node* limit, Node* stride,
 Node* range, bool upper) {
 stringStream* predString = NULL;
 if (TraceLoopPredicate) {
 }
 Node* max_idx_expr  = init;
 int stride_con = stride->get_int();
 if ((stride_con > 0) == (scale > 0) == upper) {
-max_idx_expr = new (C, 3) SubINode(limit, stride);
+if (LoopLimitCheck) {
-register_new_node(max_idx_expr, ctrl);
+// With LoopLimitCheck limit is not exact.
-if (TraceLoopPredicate) predString->print("(limit - stride) ");
+// Calculate exact limit here.
+// Note, counted loop's test is '<' or '>'.
+limit = exact_limit(loop);
+max_idx_expr = new (C, 3) SubINode(limit, stride);
+register_new_node(max_idx_expr, ctrl);
+if (TraceLoopPredicate) predString->print("(limit - stride) ");
+} else {
+max_idx_expr = new (C, 3) SubINode(limit, stride);
+register_new_node(max_idx_expr, ctrl);
+if (TraceLoopPredicate) predString->print("(limit - stride) ");
+}
 } else {
 if (TraceLoopPredicate) predString->print("init ");
 }
 if (scale != 1) {
 if (!loop->_head->is_Loop()) {
 // Could be a simple region when irreducible loops are present.
 return false;
 }
+LoopNode* head = loop->_head->as_Loop();
-if (loop->_head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
+if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) {
 // do nothing for infinite loops
 return false;
 }
 CountedLoopNode *cl = NULL;
-if (loop->_head->is_CountedLoop()) {
+if (head->is_CountedLoop()) {
-cl = loop->_head->as_CountedLoop();
+cl = head->as_CountedLoop();
 // do nothing for iteration-splitted loops
 if (!cl->is_normal_loop()) return false;
 }
-LoopNode *lpn  = loop->_head->as_Loop();
+Node* entry = head->in(LoopNode::EntryControl);
-Node* entry = lpn->in(LoopNode::EntryControl);
+ProjNode *predicate_proj = NULL;
+// Loop limit check predicate should be near the loop.
-ProjNode *predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
+if (LoopLimitCheck) {
+predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
+if (predicate_proj != NULL)
+entry = predicate_proj->in(0)->in(0);
+}
+predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
 if (!predicate_proj) {
 #ifndef PRODUCT
 if (TraceLoopPredicate) {
 tty->print("missing predicate:");
 loop->dump_head();
-lpn->dump(1);
+head->dump(1);
 }
 #endif
 return false;
 }
 ConNode* zero = _igvn.intcon(0);
 Invariance invar(area, loop);
 // Create list of if-projs such that a newer proj dominates all older
 // projs in the list, and they all dominate loop->tail()
 Node_List if_proj_list(area);
-LoopNode *head  = loop->_head->as_Loop();
 Node *current_proj = loop->tail(); //start from tail
 while (current_proj != head) {
 if (loop == get_loop(current_proj) && // still in the loop ?
 current_proj->is_Proj()        && // is a projection  ?
 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ?
 // Range check for counted loops
 const Node*    cmp    = bol->in(1)->as_Cmp();
 Node*          idx    = cmp->in(1);
 assert(!invar.is_invariant(idx), "index is variant");
-assert(cmp->in(2)->Opcode() == Op_LoadRange || OptimizeFill, "must be");
 Node* rng = cmp->in(2);
+assert(rng->Opcode() == Op_LoadRange || _igvn.type(rng)->is_int() >= 0, "must be");
 assert(invar.is_invariant(rng), "range must be invariant");
 int scale    = 1;
 Node* offset = zero;
 bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset);
 assert(ok, "must be index expression");
 assert(invar.is_invariant(offset), "offset must be loop invariant");
 offset = invar.clone(offset, ctrl);
 }
 // Test the lower bound
-Node*  lower_bound_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, rng, false);
+Node*  lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false);
 IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If();
 _igvn.hash_delete(lower_bound_iff);
 lower_bound_iff->set_req(1, lower_bound_bol);
 if (TraceLoopPredicate) tty->print_cr("lower bound check if: %d", lower_bound_iff->_idx);
 // Test the upper bound
-Node* upper_bound_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, rng, true);
+Node* upper_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, true);
 IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If();
 _igvn.hash_delete(upper_bound_iff);
 upper_bound_iff->set_req(1, upper_bound_bol);
 if (TraceLoopPredicate) tty->print_cr("upper bound check if: %d", lower_bound_iff->_idx);

Mercurial > hg > truffle

comparison src/share/vm/opto/loopPredicate.cpp @ 3345:bad7ecd0b6ed