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

equal deleted inserted replaced

-:e77c53775f4e
+:219c4312853e
 #include "opto/addnode.hpp"
 #include "opto/callnode.hpp"
 #include "opto/connode.hpp"
 #include "opto/convertnode.hpp"
 #include "opto/loopnode.hpp"
+#include "opto/matcher.hpp"
 #include "opto/mulnode.hpp"
 #include "opto/opaquenode.hpp"
 #include "opto/rootnode.hpp"
 #include "opto/subnode.hpp"
 //   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* init, Node* limit, jint stride,
-Node* range, bool upper) {
+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;
+overflow = false;
-int stride_con = stride->get_int();
+Node* max_idx_expr = NULL;
-if ((stride_con > 0) == (scale > 0) == upper) {
+const TypeInt* idx_type = TypeInt::INT;
-// Limit is not exact.
+if ((stride > 0) == (scale > 0) == upper) {
-// Calculate exact limit here.
+if (TraceLoopPredicate) {
-// Note, counted loop's test is '<' or '>'.
+if (limit->is_Con()) {
-limit = exact_limit(loop);
+predString->print("(%d ", con_limit);
-max_idx_expr = new SubINode(limit, stride);
+} else {
+predString->print("(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;
+if ((stride > 0 && (java_subtract(limit_lo, stride) < limit_lo)) ||
+(stride < 0 && (java_subtract(limit_hi, stride) > limit_hi))) {
+// No overflow possible
+ConINode* con_stride = _igvn.intcon(stride);
+set_ctrl(con_stride, C->root());
+max_idx_expr = new SubINode(limit, con_stride);
+idx_type = TypeInt::make(limit_lo - stride, limit_hi - stride, limit_type->_widen);
+} else {
+// May overflow
+overflow = true;
+limit = new ConvI2LNode(limit);
+register_new_node(limit, ctrl);
+ConLNode* con_stride = _igvn.longcon(stride);
+set_ctrl(con_stride, C->root());
+max_idx_expr = new SubLNode(limit, con_stride);
+}
 register_new_node(max_idx_expr, ctrl);
-if (TraceLoopPredicate) predString->print("(limit - stride) ");
 } else {
-if (TraceLoopPredicate) predString->print("init ");
+if (TraceLoopPredicate) {
+if (init->is_Con()) {
+predString->print("%d ", con_init);
+} else {
+predString->print("init ");
+}
+}
+idx_type = _igvn.type(init)->isa_int();
+max_idx_expr = init;
 }
 if (scale != 1) {
 ConNode* con_scale = _igvn.intcon(scale);
 set_ctrl(con_scale, C->root());
-max_idx_expr = new MulINode(max_idx_expr, con_scale);
+if (TraceLoopPredicate) {
+predString->print("* %d ", scale);
+}
+// Check if (scale * max_idx_expr) may overflow
+const TypeInt* scale_type = TypeInt::make(scale);
+MulINode* mul = new 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 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 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() || con_offset != 0)){
-if (offset && (!offset->is_Con() || offset->get_int() != 0)){
-max_idx_expr = new AddINode(max_idx_expr, offset);
-register_new_node(max_idx_expr, ctrl);
 if (TraceLoopPredicate) {
 if (offset->is_Con()) {
-predString->print("+ %d ", offset->get_int());
+predString->print("+ %d ", con_offset);
 } else {
-predString->print("+ offset ");
+predString->print("+ offset");
 }
 }
-}
+// Check if (max_idx_expr + offset) may overflow
+const TypeInt* offset_type = _igvn.type(offset)->isa_int();
-CmpUNode* cmp = new CmpUNode(max_idx_expr, range);
+jint lo = java_add(idx_type->_lo, offset_type->_lo);
+jint hi = java_add(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 ConvI2LNode(max_idx_expr);
+register_new_node(max_idx_expr, ctrl);
+}
+overflow = true;
+offset = new ConvI2LNode(offset);
+register_new_node(offset, ctrl);
+max_idx_expr = new AddLNode(max_idx_expr, offset);
+} else {
+// No overflow possible
+max_idx_expr = new AddINode(max_idx_expr, offset);
+}
+register_new_node(max_idx_expr, ctrl);
+}
+CmpNode* cmp = NULL;
+if (overflow) {
+// Integer expressions may overflow, do long comparison
+range = new 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 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 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 AndLNode(max_idx_expr, remove_sign_mask);
+register_new_node(max_idx_expr, ctrl);
+cmp = new CmpLNode(max_idx_expr, range);
+} else {
+cmp = new CmpULNode(max_idx_expr, range);
+}
+} else {
+cmp = new CmpUNode(max_idx_expr, range);
+}
 register_new_node(cmp, ctrl);
 BoolNode* bol = new BoolNode(cmp, BoolTest::lt);
 register_new_node(bol, ctrl);
 if (TraceLoopPredicate) {
 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();
+// Limit is not exact.
-Node* stride  = cl->stride();
+// 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.
-ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, iff->Opcode());
-ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, iff->Opcode());
-assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
-Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0);
 // Perform cloning to keep Invariance state correct since the
 // late schedule will place invariant things in the loop.
+Node *ctrl = predicate_proj->in(0)->as_If()->in(0);
 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
-BoolNode*  lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false);
+BoolNode* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false, overflow);
 // Negate test if necessary
 bool negated = false;
 if (proj->_con != predicate_proj->_con) {
 lower_bound_bol = new BoolNode(lower_bound_bol->in(1), lower_bound_bol->_test.negate());
 register_new_node(lower_bound_bol, ctrl);
 negated = true;
 }
+ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, overflow ? Op_If : iff->Opcode());
 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: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);
 // Test the upper bound
-BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true);
+BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true, overflow);
 negated = false;
 if (proj->_con != predicate_proj->_con) {
 upper_bound_bol = new BoolNode(upper_bound_bol->in(1), upper_bound_bol->_test.negate());
 register_new_node(upper_bound_bol, ctrl);
 negated = true;
 }
+ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate, overflow ? Op_If : iff->Opcode());
+assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
 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: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx);

changeset 46735	219c4312853e
parent 46630	75aa3e39d02c
parent 45965	e29c1363af9a
child 46983	1c9cefa2a443