< prev index next >
src/share/vm/opto/loopPredicate.cpp
Print this page
rev 5781 : 8173770: Image conversion improvements
Reviewed-by: kvn, vlivanov, dlong, rhalade, mschoene, iignatyev
rev 5783 : 8024069: replace_in_map() should operate on parent maps
Summary: type information gets lost because replace_in_map() doesn't update parent maps
Reviewed-by: kvn, twisti
@@ -26,10 +26,11 @@
#include "opto/loopnode.hpp"
#include "opto/addnode.hpp"
#include "opto/callnode.hpp"
#include "opto/connode.hpp"
#include "opto/loopnode.hpp"
+#include "opto/matcher.hpp"
#include "opto/mulnode.hpp"
#include "opto/rootnode.hpp"
#include "opto/subnode.hpp"
/*
@@ -39,67 +40,10 @@
* the checks inside the loop could be eliminated. Currently, loop predication
* optimization has been applied to remove array range check and loop invariant
* checks (such as null checks).
*/
-//-------------------------------is_uncommon_trap_proj----------------------------
-// Return true if proj is the form of "proj->[region->..]call_uct"
-bool PhaseIdealLoop::is_uncommon_trap_proj(ProjNode* proj, Deoptimization::DeoptReason reason) {
- int path_limit = 10;
- assert(proj, "invalid argument");
- Node* out = proj;
- for (int ct = 0; ct < path_limit; ct++) {
- out = out->unique_ctrl_out();
- if (out == NULL)
- return false;
- if (out->is_CallStaticJava()) {
- int req = out->as_CallStaticJava()->uncommon_trap_request();
- if (req != 0) {
- Deoptimization::DeoptReason trap_reason = Deoptimization::trap_request_reason(req);
- if (trap_reason == reason || reason == Deoptimization::Reason_none) {
- return true;
- }
- }
- return false; // don't do further after call
- }
- if (out->Opcode() != Op_Region)
- return false;
- }
- return false;
-}
-
-//-------------------------------is_uncommon_trap_if_pattern-------------------------
-// Return true for "if(test)-> proj -> ...
-// |
-// V
-// other_proj->[region->..]call_uct"
-//
-// "must_reason_predicate" means the uct reason must be Reason_predicate
-bool PhaseIdealLoop::is_uncommon_trap_if_pattern(ProjNode *proj, Deoptimization::DeoptReason reason) {
- Node *in0 = proj->in(0);
- if (!in0->is_If()) return false;
- // Variation of a dead If node.
- if (in0->outcnt() < 2) return false;
- IfNode* iff = in0->as_If();
-
- // we need "If(Conv2B(Opaque1(...)))" pattern for reason_predicate
- if (reason != Deoptimization::Reason_none) {
- if (iff->in(1)->Opcode() != Op_Conv2B ||
- iff->in(1)->in(1)->Opcode() != Op_Opaque1) {
- return false;
- }
- }
-
- ProjNode* other_proj = iff->proj_out(1-proj->_con)->as_Proj();
- if (is_uncommon_trap_proj(other_proj, reason)) {
- assert(reason == Deoptimization::Reason_none ||
- Compile::current()->is_predicate_opaq(iff->in(1)->in(1)), "should be on the list");
- return true;
- }
- return false;
-}
-
//-------------------------------register_control-------------------------
void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) {
assert(n->is_CFG(), "must be control node");
_igvn.register_new_node_with_optimizer(n);
loop->_body.push(n);
@@ -145,11 +89,11 @@
// We will create a region to guard the uct call if there is no one there.
// The true projecttion (if_cont) of the new_iff is returned.
// This code is also used to clone predicates to clonned loops.
ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
Deoptimization::DeoptReason reason) {
- assert(is_uncommon_trap_if_pattern(cont_proj, reason), "must be a uct if pattern!");
+ assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");
IfNode* iff = cont_proj->in(0)->as_If();
ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
Node *rgn = uncommon_proj->unique_ctrl_out();
assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
@@ -233,11 +177,11 @@
//------------------------------create_new_if_for_predicate------------------------
// Create a new if below new_entry for the predicate to be cloned (IGVN optimization)
ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
Deoptimization::DeoptReason reason) {
assert(new_entry != 0, "only used for clone predicate");
- assert(PhaseIdealLoop::is_uncommon_trap_if_pattern(cont_proj, reason), "must be a uct if pattern!");
+ assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!");
IfNode* iff = cont_proj->in(0)->as_If();
ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con);
Node *rgn = uncommon_proj->unique_ctrl_out();
assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
@@ -420,11 +364,11 @@
//--------------------------find_predicate_insertion_point-------------------
// Find a good location to insert a predicate
ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) {
if (start_c == NULL || !start_c->is_Proj())
return NULL;
- if (is_uncommon_trap_if_pattern(start_c->as_Proj(), reason)) {
+ if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) {
return start_c->as_Proj();
}
return NULL;
}
@@ -642,54 +586,144 @@
// max(scale*i + offset) = scale*(limit-stride) + offset
// (2) stride*scale < 0
// max(scale*i + offset) = scale*init + offset
BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl,
int scale, Node* offset,
- Node* init, Node* limit, Node* stride,
- Node* range, bool upper) {
+ Node* init, Node* limit, jint stride,
+ Node* range, bool upper, bool &overflow) {
+ jint con_limit = limit->is_Con() ? limit->get_int() : 0;
+ jint con_init = init->is_Con() ? init->get_int() : 0;
+ jint con_offset = offset->is_Con() ? offset->get_int() : 0;
+
stringStream* predString = NULL;
if (TraceLoopPredicate) {
predString = new stringStream();
predString->print("rc_predicate ");
}
- Node* max_idx_expr = init;
- int stride_con = stride->get_int();
- if ((stride_con > 0) == (scale > 0) == upper) {
- if (LoopLimitCheck) {
- // With LoopLimitCheck limit is not exact.
- // Calculate exact limit here.
- // Note, counted loop's test is '<' or '>'.
- limit = exact_limit(loop);
- max_idx_expr = new (C) SubINode(limit, stride);
- register_new_node(max_idx_expr, ctrl);
- if (TraceLoopPredicate) predString->print("(limit - stride) ");
+ overflow = false;
+ Node* max_idx_expr = NULL;
+ const TypeInt* idx_type = TypeInt::INT;
+ if ((stride > 0) == (scale > 0) == upper) {
+ if (TraceLoopPredicate) {
+ predString->print(limit->is_Con() ? "(%d " : "(limit ", con_limit);
+ predString->print("- %d) ", stride);
+ }
+ // Check if (limit - stride) may overflow
+ const TypeInt* limit_type = _igvn.type(limit)->isa_int();
+ jint limit_lo = limit_type->_lo;
+ jint limit_hi = limit_type->_hi;
+ jint res_lo = limit_lo - stride;
+ jint res_hi = limit_hi - stride;
+ if ((stride > 0 && (res_lo < limit_lo)) ||
+ (stride < 0 && (res_hi > limit_hi))) {
+ // No overflow possible
+ ConINode* con_stride = _igvn.intcon(stride);
+ set_ctrl(con_stride, C->root());
+ max_idx_expr = new (C) SubINode(limit, con_stride);
+ idx_type = TypeInt::make(limit_lo - stride, limit_hi - stride, limit_type->_widen);
} else {
- max_idx_expr = new (C) SubINode(limit, stride);
- register_new_node(max_idx_expr, ctrl);
- if (TraceLoopPredicate) predString->print("(limit - stride) ");
+ // May overflow
+ overflow = true;
+ limit = new (C) ConvI2LNode(limit);
+ register_new_node(limit, ctrl);
+ ConLNode* con_stride = _igvn.longcon(stride);
+ set_ctrl(con_stride, C->root());
+ max_idx_expr = new (C) SubLNode(limit, con_stride);
}
+ register_new_node(max_idx_expr, ctrl);
} else {
- if (TraceLoopPredicate) predString->print("init ");
+ if (TraceLoopPredicate) {
+ predString->print(init->is_Con() ? "%d " : "init ", con_init);
+ }
+ idx_type = _igvn.type(init)->isa_int();
+ max_idx_expr = init;
}
if (scale != 1) {
ConNode* con_scale = _igvn.intcon(scale);
- max_idx_expr = new (C) MulINode(max_idx_expr, con_scale);
+ set_ctrl(con_scale, C->root());
+ if (TraceLoopPredicate) {
+ predString->print("* %d ", scale);
+ }
+ // Check if (scale * max_idx_expr) may overflow
+ const TypeInt* scale_type = TypeInt::make(scale);
+ MulINode* mul = new (C) MulINode(max_idx_expr, con_scale);
+ idx_type = (TypeInt*)mul->mul_ring(idx_type, scale_type);
+ if (overflow || TypeInt::INT->higher_equal(idx_type)) {
+ // May overflow
+ mul->destruct();
+ if (!overflow) {
+ max_idx_expr = new (C) ConvI2LNode(max_idx_expr);
+ register_new_node(max_idx_expr, ctrl);
+ }
+ overflow = true;
+ con_scale = _igvn.longcon(scale);
+ set_ctrl(con_scale, C->root());
+ max_idx_expr = new (C) MulLNode(max_idx_expr, con_scale);
+ } else {
+ // No overflow possible
+ max_idx_expr = mul;
+ }
register_new_node(max_idx_expr, ctrl);
- if (TraceLoopPredicate) predString->print("* %d ", scale);
}
- if (offset && (!offset->is_Con() || offset->get_int() != 0)){
+ if (offset && (!offset->is_Con() || con_offset != 0)){
+ if (TraceLoopPredicate) {
+ predString->print(offset->is_Con() ? "+ %d " : "+ offset", con_offset);
+ }
+ // Check if (max_idx_expr + offset) may overflow
+ const TypeInt* offset_type = _igvn.type(offset)->isa_int();
+ jint lo = idx_type->_lo + offset_type->_lo;
+ jint hi = idx_type->_hi + offset_type->_hi;
+ if (overflow || (lo > hi) ||
+ ((idx_type->_lo & offset_type->_lo) < 0 && lo >= 0) ||
+ ((~(idx_type->_hi | offset_type->_hi)) < 0 && hi < 0)) {
+ // May overflow
+ if (!overflow) {
+ max_idx_expr = new (C) ConvI2LNode(max_idx_expr);
+ register_new_node(max_idx_expr, ctrl);
+ }
+ overflow = true;
+ offset = new (C) ConvI2LNode(offset);
+ register_new_node(offset, ctrl);
+ max_idx_expr = new (C) AddLNode(max_idx_expr, offset);
+ } else {
+ // No overflow possible
max_idx_expr = new (C) AddINode(max_idx_expr, offset);
+ }
register_new_node(max_idx_expr, ctrl);
- if (TraceLoopPredicate)
- if (offset->is_Con()) predString->print("+ %d ", offset->get_int());
- else predString->print("+ offset ");
}
- CmpUNode* cmp = new (C) CmpUNode(max_idx_expr, range);
+ CmpNode* cmp = NULL;
+ if (overflow) {
+ // Integer expressions may overflow, do long comparison
+ range = new (C) ConvI2LNode(range);
+ register_new_node(range, ctrl);
+ if (!Matcher::has_match_rule(Op_CmpUL)) {
+ // We don't support unsigned long comparisons. Set 'max_idx_expr'
+ // to max_julong if < 0 to make the signed comparison fail.
+ ConINode* sign_pos = _igvn.intcon(BitsPerLong - 1);
+ set_ctrl(sign_pos, C->root());
+ Node* sign_bit_mask = new (C) RShiftLNode(max_idx_expr, sign_pos);
+ register_new_node(sign_bit_mask, ctrl);
+ // OR with sign bit to set all bits to 1 if negative (otherwise no change)
+ max_idx_expr = new (C) OrLNode(max_idx_expr, sign_bit_mask);
+ register_new_node(max_idx_expr, ctrl);
+ // AND with 0x7ff... to unset the sign bit
+ ConLNode* remove_sign_mask = _igvn.longcon(max_jlong);
+ set_ctrl(remove_sign_mask, C->root());
+ max_idx_expr = new (C) AndLNode(max_idx_expr, remove_sign_mask);
+ register_new_node(max_idx_expr, ctrl);
+
+ cmp = new (C) CmpLNode(max_idx_expr, range);
+ } else {
+ cmp = new (C) CmpULNode(max_idx_expr, range);
+ }
+ } else {
+ cmp = new (C) CmpUNode(max_idx_expr, range);
+ }
register_new_node(cmp, ctrl);
BoolNode* bol = new (C) BoolNode(cmp, BoolTest::lt);
register_new_node(bol, ctrl);
if (TraceLoopPredicate) {
@@ -771,11 +805,11 @@
ProjNode* new_predicate_proj = NULL;
ProjNode* proj = if_proj_list.pop()->as_Proj();
IfNode* iff = proj->in(0)->as_If();
- if (!is_uncommon_trap_if_pattern(proj, Deoptimization::Reason_none)) {
+ if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {
if (loop->is_loop_exit(iff)) {
// stop processing the remaining projs in the list because the execution of them
// depends on the condition of "iff" (iff->in(1)).
break;
} else {
@@ -835,12 +869,15 @@
Node* offset = zero;
bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset);
assert(ok, "must be index expression");
Node* init = cl->init_trip();
- Node* limit = cl->limit();
- Node* stride = cl->stride();
+ // Limit is not exact.
+ // Calculate exact limit here.
+ // Note, counted loop's test is '<' or '>'.
+ Node* limit = exact_limit(loop);
+ int stride = cl->stride()->get_int();
// Build if's for the upper and lower bound tests. The
// lower_bound test will dominate the upper bound test and all
// cloned or created nodes will use the lower bound test as
// their declared control.
@@ -854,20 +891,22 @@
rng = invar.clone(rng, ctrl);
if (offset && offset != zero) {
assert(invar.is_invariant(offset), "offset must be loop invariant");
offset = invar.clone(offset, ctrl);
}
+ // If predicate expressions may overflow in the integer range, longs are used.
+ bool overflow = false;
// Test the lower bound
- Node* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false);
+ Node* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false, overflow);
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(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true);
+ Node* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true, overflow);
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);
< prev index next >