# HG changeset patch # User kvn # Date 1304539962 25200 # Node ID bad7ecd0b6ed33c0ef2f99027f2b8aca08a76f80 # Parent 0139aac70fb540cfbd0d6897762b6edc5c529614 5091921: Sign flip issues in loop optimizer Summary: Fix integer overflow problem in the code generated by loop optimizer. Reviewed-by: never diff -r 0139aac70fb5 -r bad7ecd0b6ed src/cpu/x86/vm/x86_32.ad --- a/src/cpu/x86/vm/x86_32.ad Wed May 04 03:42:58 2011 -0700 +++ b/src/cpu/x86/vm/x86_32.ad Wed May 04 13:12:42 2011 -0700 @@ -12989,6 +12989,53 @@ %} // ============================================================================ +// Counted Loop limit node which represents exact final iterator value. +// Note: the resulting value should fit into integer range since +// counted loops have limit check on overflow. +instruct loopLimit_eReg(eAXRegI limit, nadxRegI init, immI stride, eDXRegI limit_hi, nadxRegI tmp, eFlagsReg flags) %{ + match(Set limit (LoopLimit (Binary init limit) stride)); + effect(TEMP limit_hi, TEMP tmp, KILL flags); + ins_cost(300); + + format %{ "loopLimit $init,$limit,$stride # $limit = $init + $stride *( $limit - $init + $stride -1)/ $stride, kills $limit_hi" %} + ins_encode %{ + int strd = (int)$stride$$constant; + assert(strd != 1 && strd != -1, "sanity"); + int m1 = (strd > 0) ? 1 : -1; + // Convert limit to long (EAX:EDX) + __ cdql(); + // Convert init to long (init:tmp) + __ movl($tmp$$Register, $init$$Register); + __ sarl($tmp$$Register, 31); + // $limit - $init + __ subl($limit$$Register, $init$$Register); + __ sbbl($limit_hi$$Register, $tmp$$Register); + // + ($stride - 1) + if (strd > 0) { + __ addl($limit$$Register, (strd - 1)); + __ adcl($limit_hi$$Register, 0); + __ movl($tmp$$Register, strd); + } else { + __ addl($limit$$Register, (strd + 1)); + __ adcl($limit_hi$$Register, -1); + __ lneg($limit_hi$$Register, $limit$$Register); + __ movl($tmp$$Register, -strd); + } + // signed devision: (EAX:EDX) / pos_stride + __ idivl($tmp$$Register); + if (strd < 0) { + // restore sign + __ negl($tmp$$Register); + } + // (EAX) * stride + __ mull($tmp$$Register); + // + init (ignore upper bits) + __ addl($limit$$Register, $init$$Register); + %} + ins_pipe( pipe_slow ); +%} + +// ============================================================================ // Branch Instructions // Jump Table instruct jumpXtnd(eRegI switch_val) %{ diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/oops/methodDataOop.hpp --- a/src/share/vm/oops/methodDataOop.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/oops/methodDataOop.hpp Wed May 04 13:12:42 2011 -0700 @@ -1194,7 +1194,7 @@ // Whole-method sticky bits and flags public: enum { - _trap_hist_limit = 16, // decoupled from Deoptimization::Reason_LIMIT + _trap_hist_limit = 17, // decoupled from Deoptimization::Reason_LIMIT _trap_hist_mask = max_jubyte, _extra_data_count = 4 // extra DataLayout headers, for trap history }; // Public flag values diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/bytecodeInfo.cpp --- a/src/share/vm/opto/bytecodeInfo.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/bytecodeInfo.cpp Wed May 04 13:12:42 2011 -0700 @@ -373,7 +373,6 @@ return true; } -#ifndef PRODUCT //------------------------------print_inlining--------------------------------- // Really, the failure_msg can be a success message also. void InlineTree::print_inlining(ciMethod* callee_method, int caller_bci, const char* failure_msg) const { @@ -385,7 +384,6 @@ tty->print(" bcs: %d+%d invoked: %d", top->count_inline_bcs(), callee_method->code_size(), callee_method->interpreter_invocation_count()); } } -#endif //------------------------------ok_to_inline----------------------------------- WarmCallInfo* InlineTree::ok_to_inline(ciMethod* callee_method, JVMState* jvms, ciCallProfile& profile, WarmCallInfo* initial_wci) { diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/c2_globals.hpp --- a/src/share/vm/opto/c2_globals.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/c2_globals.hpp Wed May 04 13:12:42 2011 -0700 @@ -183,6 +183,21 @@ develop(bool, TraceLoopOpts, false, \ "Trace executed loop optimizations") \ \ + diagnostic(bool, LoopLimitCheck, true, \ + "Generate a loop limits check for overflow") \ + \ + develop(bool, TraceLoopLimitCheck, false, \ + "Trace generation of loop limits checks") \ + \ + diagnostic(bool, RangeLimitCheck, true, \ + "Additional overflow checks during range check elimination") \ + \ + develop(bool, TraceRangeLimitCheck, false, \ + "Trace additional overflow checks in RCE") \ + \ + diagnostic(bool, UnrollLimitCheck, true, \ + "Additional overflow checks during loop unroll") \ + \ product(bool, OptimizeFill, false, \ "convert fill/copy loops into intrinsic") \ \ diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/cfgnode.cpp --- a/src/share/vm/opto/cfgnode.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/cfgnode.cpp Wed May 04 13:12:42 2011 -0700 @@ -1373,7 +1373,7 @@ // Clone loop predicates if (predicate_proj != NULL) { - newn = igvn->clone_loop_predicates(predicate_proj, newn); + newn = igvn->clone_loop_predicates(predicate_proj, newn, !n->is_CountedLoop()); } // Now I can point to the new node. diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/classes.hpp --- a/src/share/vm/opto/classes.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/classes.hpp Wed May 04 13:12:42 2011 -0700 @@ -156,6 +156,7 @@ macro(LogD) macro(Log10D) macro(Loop) +macro(LoopLimit) macro(Mach) macro(MachProj) macro(MaxI) diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/graphKit.cpp --- a/src/share/vm/opto/graphKit.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/graphKit.cpp Wed May 04 13:12:42 2011 -0700 @@ -3378,6 +3378,10 @@ if (UseLoopPredicate) { add_predicate_impl(Deoptimization::Reason_predicate, nargs); } + // loop's limit check predicate should be near the loop. + if (LoopLimitCheck) { + add_predicate_impl(Deoptimization::Reason_loop_limit_check, nargs); + } } //----------------------------- store barriers ---------------------------- diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/ifnode.cpp --- a/src/share/vm/opto/ifnode.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/ifnode.cpp Wed May 04 13:12:42 2011 -0700 @@ -236,6 +236,7 @@ } Node* predicate_c = NULL; Node* predicate_x = NULL; + bool counted_loop = r->is_CountedLoop(); Node *region_c = new (igvn->C, req_c + 1) RegionNode(req_c + 1); Node *phi_c = con1; @@ -294,16 +295,16 @@ if (predicate_c != NULL) { assert(predicate_x == NULL, "only one predicate entry expected"); // Clone loop predicates to each path - iff_c_t = igvn->clone_loop_predicates(predicate_c, iff_c_t); - iff_c_f = igvn->clone_loop_predicates(predicate_c, iff_c_f); + iff_c_t = igvn->clone_loop_predicates(predicate_c, iff_c_t, !counted_loop); + iff_c_f = igvn->clone_loop_predicates(predicate_c, iff_c_f, !counted_loop); } Node *iff_x_t = phase->transform(new (igvn->C, 1) IfTrueNode (iff_x)); Node *iff_x_f = phase->transform(new (igvn->C, 1) IfFalseNode(iff_x)); if (predicate_x != NULL) { assert(predicate_c == NULL, "only one predicate entry expected"); // Clone loop predicates to each path - iff_x_t = igvn->clone_loop_predicates(predicate_x, iff_x_t); - iff_x_f = igvn->clone_loop_predicates(predicate_x, iff_x_f); + iff_x_t = igvn->clone_loop_predicates(predicate_x, iff_x_t, !counted_loop); + iff_x_f = igvn->clone_loop_predicates(predicate_x, iff_x_f, !counted_loop); } // Merge the TRUE paths diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/loopPredicate.cpp --- a/src/share/vm/opto/loopPredicate.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/loopPredicate.cpp Wed May 04 13:12:42 2011 -0700 @@ -341,7 +341,7 @@ // 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); @@ -384,24 +384,25 @@ //--------------------------clone_loop_predicates----------------------- // Interface from IGVN -Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry) { - return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, false, NULL, this); +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, clone_limit_check, NULL, this); } -Node* PhaseIterGVN::move_loop_predicates(Node* old_entry, Node* new_entry) { - return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, true, NULL, this); +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, clone_limit_check, NULL, this); } // Interface from PhaseIdealLoop -Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry) { - return clone_loop_predicates(old_entry, new_entry, false, this, &this->_igvn); +Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { + 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) { - return clone_loop_predicates(old_entry, new_entry, true, this, &this->_igvn); +Node* PhaseIdealLoop::move_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { + 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 @@ -413,10 +414,16 @@ #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, @@ -435,11 +442,37 @@ } } } + 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 @@ -456,10 +489,15 @@ // 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(); @@ -491,10 +529,15 @@ // 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; } } @@ -658,7 +701,7 @@ 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 @@ -696,7 +739,7 @@ // 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) { @@ -709,9 +752,19 @@ 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); - register_new_node(max_idx_expr, ctrl); - if (TraceLoopPredicate) predString->print("(limit - stride) "); + 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, 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 "); } @@ -752,29 +805,36 @@ // 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()) { - cl = loop->_head->as_CountedLoop(); + if (head->is_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 = lpn->in(LoopNode::EntryControl); + Node* entry = head->in(LoopNode::EntryControl); + ProjNode *predicate_proj = NULL; + // Loop limit check predicate should be near the loop. + 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); + } - ProjNode *predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); + 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; @@ -788,7 +848,6 @@ // 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 ? @@ -862,8 +921,8 @@ 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; @@ -892,14 +951,14 @@ } // 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); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/loopTransform.cpp --- a/src/share/vm/opto/loopTransform.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/loopTransform.cpp Wed May 04 13:12:42 2011 -0700 @@ -83,7 +83,7 @@ #ifdef ASSERT BoolTest::mask bt = cl->loopexit()->test_trip(); assert(bt == BoolTest::lt || bt == BoolTest::gt || - bt == BoolTest::ne, "canonical test is expected"); + (bt == BoolTest::ne && !LoopLimitCheck), "canonical test is expected"); #endif Node* init_n = cl->init_trip(); @@ -510,7 +510,7 @@ // the pre-loop with only 1 user (the new peeled iteration), but the // peeled-loop backedge has 2 users. Node* new_exit_value = old_new[head->in(LoopNode::LoopBackControl)->_idx]; - new_exit_value = move_loop_predicates(entry, new_exit_value); + new_exit_value = move_loop_predicates(entry, new_exit_value, !counted_loop); _igvn.hash_delete(head); head->set_req(LoopNode::EntryControl, new_exit_value); for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) { @@ -593,6 +593,12 @@ return false; } + // Fully unroll a loop with few iterations regardless next + // conditions since following loop optimizations will split + // such loop anyway (pre-main-post). + if (trip_count <= 3) + return true; + // Take into account that after unroll conjoined heads and tails will fold, // otherwise policy_unroll() may allow more unrolling than max unrolling. uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count; @@ -605,15 +611,6 @@ return false; } - // Currently we don't have policy to optimize one iteration loops. - // Maximally unrolling transformation is used for that: - // it is peeled and the original loop become non reachable (dead). - // Also fully unroll a loop with few iterations regardless next - // conditions since following loop optimizations will split - // such loop anyway (pre-main-post). - if (trip_count <= 3) - return true; - // Do not unroll a loop with String intrinsics code. // String intrinsics are large and have loops. for (uint k = 0; k < _body.size(); k++) { @@ -645,8 +642,9 @@ if (!cl->is_valid_counted_loop()) return false; // Malformed counted loop - // protect against over-unrolling - if (cl->trip_count() <= 1) return false; + // Protect against over-unrolling. + // After split at least one iteration will be executed in pre-loop. + if (cl->trip_count() <= (uint)(cl->is_normal_loop() ? 2 : 1)) return false; int future_unroll_ct = cl->unrolled_count() * 2; if (future_unroll_ct > MAX_UNROLL) return false; @@ -678,6 +676,7 @@ Node *init_n = cl->init_trip(); Node *limit_n = cl->limit(); + int stride_con = cl->stride_con(); // Non-constant bounds. // Protect against over-unrolling when init or/and limit are not constant // (so that trip_count's init value is maxint) but iv range is known. @@ -687,7 +686,7 @@ if (phi != NULL) { assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi."); const TypeInt* iv_type = phase->_igvn.type(phi)->is_int(); - int next_stride = cl->stride_con() * 2; // stride after this unroll + int next_stride = stride_con * 2; // stride after this unroll if (next_stride > 0) { if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow iv_type->_lo + next_stride > iv_type->_hi) { @@ -702,15 +701,19 @@ } } + // After unroll limit will be adjusted: new_limit = limit-stride. + // Bailout if adjustment overflow. + const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int(); + if (stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi) || + stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo)) + return false; // overflow + // Adjust body_size to determine if we unroll or not uint body_size = _body.size(); - // Key test to unroll CaffeineMark's Logic test - int xors_in_loop = 0; // Also count ModL, DivL and MulL which expand mightly for (uint k = 0; k < _body.size(); k++) { Node* n = _body.at(k); switch (n->Opcode()) { - case Op_XorI: xors_in_loop++; break; // CaffeineMark's Logic test case Op_ModL: body_size += 30; break; case Op_DivL: body_size += 30; break; case Op_MulL: body_size += 10; break; @@ -727,8 +730,7 @@ // Check for being too big if (body_size > (uint)LoopUnrollLimit) { - if (xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true; - // Normal case: loop too big + // Normal case: loop too big return false; } @@ -750,28 +752,31 @@ // Return TRUE or FALSE if the loop should be range-check-eliminated. // Actually we do iteration-splitting, a more powerful form of RCE. bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const { - if( !RangeCheckElimination ) return false; + if (!RangeCheckElimination) return false; CountedLoopNode *cl = _head->as_CountedLoop(); // If we unrolled with no intention of doing RCE and we later // changed our minds, we got no pre-loop. Either we need to // make a new pre-loop, or we gotta disallow RCE. - if( cl->is_main_no_pre_loop() ) return false; // Disallowed for now. + if (cl->is_main_no_pre_loop()) return false; // Disallowed for now. Node *trip_counter = cl->phi(); // Check loop body for tests of trip-counter plus loop-invariant vs // loop-invariant. - for( uint i = 0; i < _body.size(); i++ ) { + for (uint i = 0; i < _body.size(); i++) { Node *iff = _body[i]; - if( iff->Opcode() == Op_If ) { // Test? + if (iff->Opcode() == Op_If) { // Test? // Comparing trip+off vs limit Node *bol = iff->in(1); - if( bol->req() != 2 ) continue; // dead constant test + if (bol->req() != 2) continue; // dead constant test if (!bol->is_Bool()) { assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only"); continue; } + if (bol->as_Bool()->_test._test == BoolTest::ne) + continue; // not RC + Node *cmp = bol->in(1); Node *rc_exp = cmp->in(1); @@ -1067,6 +1072,7 @@ // negative stride use > if (pre_end->in(CountedLoopEndNode::TestValue)->as_Bool()->_test._test == BoolTest::ne) { + assert(!LoopLimitCheck, "only canonical tests (lt or gt) are expected"); BoolTest::mask new_test = (main_end->stride_con() > 0) ? BoolTest::lt : BoolTest::gt; // Modify pre loop end condition @@ -1093,6 +1099,9 @@ main_head->set_main_loop(); if( peel_only ) main_head->set_main_no_pre_loop(); + // Subtract a trip count for the pre-loop. + main_head->set_trip_count(main_head->trip_count() - 1); + // It's difficult to be precise about the trip-counts // for the pre/post loops. They are usually very short, // so guess that 4 trips is a reasonable value. @@ -1126,9 +1135,9 @@ loop->dump_head(); } else if (TraceLoopOpts) { if (loop_head->trip_count() < (uint)LoopUnrollLimit) { - tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count()); + tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count()); } else { - tty->print("Unroll %d ", loop_head->unrolled_count()*2); + tty->print("Unroll %d ", loop_head->unrolled_count()*2); } loop->dump_head(); } @@ -1144,7 +1153,8 @@ Node *stride = loop_head->stride(); Node *opaq = NULL; - if( adjust_min_trip ) { // If not maximally unrolling, need adjustment + if (adjust_min_trip) { // If not maximally unrolling, need adjustment + // Search for zero-trip guard. assert( loop_head->is_main_loop(), "" ); assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" ); Node *iff = ctrl->in(0); @@ -1154,63 +1164,202 @@ Node *cmp = bol->in(1); assert( cmp->Opcode() == Op_CmpI, "" ); opaq = cmp->in(2); - // Occasionally it's possible for a pre-loop Opaque1 node to be + // Occasionally it's possible for a zero-trip guard Opaque1 node to be // optimized away and then another round of loop opts attempted. // We can not optimize this particular loop in that case. - if( opaq->Opcode() != Op_Opaque1 ) - return; // Cannot find pre-loop! Bail out! + if (opaq->Opcode() != Op_Opaque1) + return; // Cannot find zero-trip guard! Bail out! + // Zero-trip test uses an 'opaque' node which is not shared. + assert(opaq->outcnt() == 1 && opaq->in(1) == limit, ""); } C->set_major_progress(); - // Adjust max trip count. The trip count is intentionally rounded - // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll, - // the main, unrolled, part of the loop will never execute as it is protected - // by the min-trip test. See bug 4834191 for a case where we over-unrolled - // and later determined that part of the unrolled loop was dead. - loop_head->set_trip_count(loop_head->trip_count() / 2); + Node* new_limit = NULL; + if (UnrollLimitCheck) { + int stride_con = stride->get_int(); + int stride_p = (stride_con > 0) ? stride_con : -stride_con; + uint old_trip_count = loop_head->trip_count(); + // Verify that unroll policy result is still valid. + assert(old_trip_count > 1 && + (!adjust_min_trip || stride_p <= (1<<3)*loop_head->unrolled_count()), "sanity"); - // Double the count of original iterations in the unrolled loop body. - loop_head->double_unrolled_count(); + // Adjust loop limit to keep valid iterations number after unroll. + // Use (limit - stride) instead of (((limit - init)/stride) & (-2))*stride + // which may overflow. + if (!adjust_min_trip) { + assert(old_trip_count > 1 && (old_trip_count & 1) == 0, + "odd trip count for maximally unroll"); + // Don't need to adjust limit for maximally unroll since trip count is even. + } else if (loop_head->has_exact_trip_count() && init->is_Con()) { + // Loop's limit is constant. Loop's init could be constant when pre-loop + // become peeled iteration. + long init_con = init->get_int(); + // We can keep old loop limit if iterations count stays the same: + // old_trip_count == new_trip_count * 2 + // Note: since old_trip_count >= 2 then new_trip_count >= 1 + // so we also don't need to adjust zero trip test. + long limit_con = limit->get_int(); + // (stride_con*2) not overflow since stride_con <= 8. + int new_stride_con = stride_con * 2; + int stride_m = new_stride_con - (stride_con > 0 ? 1 : -1); + long trip_count = (limit_con - init_con + stride_m)/new_stride_con; + // New trip count should satisfy next conditions. + assert(trip_count > 0 && (julong)trip_count < (julong)max_juint/2, "sanity"); + uint new_trip_count = (uint)trip_count; + adjust_min_trip = (old_trip_count != new_trip_count*2); + } + + if (adjust_min_trip) { + // Step 2: Adjust the trip limit if it is called for. + // The adjustment amount is -stride. Need to make sure if the + // adjustment underflows or overflows, then the main loop is skipped. + Node* cmp = loop_end->cmp_node(); + assert(cmp->in(2) == limit, "sanity"); + assert(opaq != NULL && opaq->in(1) == limit, "sanity"); + + // Verify that policy_unroll result is still valid. + const TypeInt* limit_type = _igvn.type(limit)->is_int(); + assert(stride_con > 0 && ((limit_type->_hi - stride_con) < limit_type->_hi) || + stride_con < 0 && ((limit_type->_lo - stride_con) > limit_type->_lo), "sanity"); - // ----------- - // Step 2: Cut back the trip counter for an unroll amount of 2. - // Loop will normally trip (limit - init)/stride_con. Since it's a - // CountedLoop this is exact (stride divides limit-init exactly). - // We are going to double the loop body, so we want to knock off any - // odd iteration: (trip_cnt & ~1). Then back compute a new limit. - Node *span = new (C, 3) SubINode( limit, init ); - register_new_node( span, ctrl ); - Node *trip = new (C, 3) DivINode( 0, span, stride ); - register_new_node( trip, ctrl ); - Node *mtwo = _igvn.intcon(-2); - set_ctrl(mtwo, C->root()); - Node *rond = new (C, 3) AndINode( trip, mtwo ); - register_new_node( rond, ctrl ); - Node *spn2 = new (C, 3) MulINode( rond, stride ); - register_new_node( spn2, ctrl ); - Node *lim2 = new (C, 3) AddINode( spn2, init ); - register_new_node( lim2, ctrl ); + if (limit->is_Con()) { + // The check in policy_unroll and the assert above guarantee + // no underflow if limit is constant. + new_limit = _igvn.intcon(limit->get_int() - stride_con); + set_ctrl(new_limit, C->root()); + } else { + if (stride_con > 0 && ((limit_type->_lo - stride_con) < limit_type->_lo) || + stride_con < 0 && ((limit_type->_hi - stride_con) > limit_type->_hi)) { + // No underflow. + new_limit = new (C, 3) SubINode(limit, stride); + } else { + // (limit - stride) may underflow. + // Clamp the adjustment value with MININT or MAXINT: + // + // new_limit = limit-stride + // if (stride > 0) + // new_limit = (limit < new_limit) ? MININT : new_limit; + // else + // new_limit = (limit > new_limit) ? MAXINT : new_limit; + // + BoolTest::mask bt = loop_end->test_trip(); + assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected"); + Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint); + set_ctrl(adj_max, C->root()); + Node* old_limit = NULL; + Node* adj_limit = NULL; + Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL; + if (loop_head->unrolled_count() > 1 && + limit->is_CMove() && limit->Opcode() == Op_CMoveI && + limit->in(CMoveNode::IfTrue) == adj_max && + bol->as_Bool()->_test._test == bt && + bol->in(1)->Opcode() == Op_CmpI && + bol->in(1)->in(2) == limit->in(CMoveNode::IfFalse)) { + // Loop was unrolled before. + // Optimize the limit to avoid nested CMove: + // use original limit as old limit. + old_limit = bol->in(1)->in(1); + // Adjust previous adjusted limit. + adj_limit = limit->in(CMoveNode::IfFalse); + adj_limit = new (C, 3) SubINode(adj_limit, stride); + } else { + old_limit = limit; + adj_limit = new (C, 3) SubINode(limit, stride); + } + assert(old_limit != NULL && adj_limit != NULL, ""); + register_new_node( adj_limit, ctrl ); // adjust amount + Node* adj_cmp = new (C, 3) CmpINode(old_limit, adj_limit); + register_new_node( adj_cmp, ctrl ); + Node* adj_bool = new (C, 2) BoolNode(adj_cmp, bt); + register_new_node( adj_bool, ctrl ); + new_limit = new (C, 4) CMoveINode(adj_bool, adj_limit, adj_max, TypeInt::INT); + } + register_new_node(new_limit, ctrl); + } + assert(new_limit != NULL, ""); + if (limit->outcnt() == 2) { + // Replace old limit if it is used only in loop tests. + _igvn.replace_node(limit, new_limit); + } else { + // Replace in loop test. + _igvn.hash_delete(cmp); + cmp->set_req(2, new_limit); + + // Step 3: Find the min-trip test guaranteed before a 'main' loop. + // Make it a 1-trip test (means at least 2 trips). - // Hammer in the new limit - Node *ctrl2 = loop_end->in(0); - Node *cmp2 = new (C, 3) CmpINode( loop_head->incr(), lim2 ); - register_new_node( cmp2, ctrl2 ); - Node *bol2 = new (C, 2) BoolNode( cmp2, loop_end->test_trip() ); - register_new_node( bol2, ctrl2 ); - _igvn.hash_delete(loop_end); - loop_end->set_req(CountedLoopEndNode::TestValue, bol2); + // Guard test uses an 'opaque' node which is not shared. Hence I + // can edit it's inputs directly. Hammer in the new limit for the + // minimum-trip guard. + assert(opaq->outcnt() == 1, ""); + _igvn.hash_delete(opaq); + opaq->set_req(1, new_limit); + } + } + + // Adjust max trip count. The trip count is intentionally rounded + // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll, + // the main, unrolled, part of the loop will never execute as it is protected + // by the min-trip test. See bug 4834191 for a case where we over-unrolled + // and later determined that part of the unrolled loop was dead. + loop_head->set_trip_count(old_trip_count / 2); + + // Double the count of original iterations in the unrolled loop body. + loop_head->double_unrolled_count(); + + } else { // LoopLimitCheck + + // Adjust max trip count. The trip count is intentionally rounded + // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll, + // the main, unrolled, part of the loop will never execute as it is protected + // by the min-trip test. See bug 4834191 for a case where we over-unrolled + // and later determined that part of the unrolled loop was dead. + loop_head->set_trip_count(loop_head->trip_count() / 2); + + // Double the count of original iterations in the unrolled loop body. + loop_head->double_unrolled_count(); - // Step 3: Find the min-trip test guaranteed before a 'main' loop. - // Make it a 1-trip test (means at least 2 trips). - if( adjust_min_trip ) { - // Guard test uses an 'opaque' node which is not shared. Hence I - // can edit it's inputs directly. Hammer in the new limit for the - // minimum-trip guard. - assert( opaq->outcnt() == 1, "" ); - _igvn.hash_delete(opaq); - opaq->set_req(1, lim2); - } + // ----------- + // Step 2: Cut back the trip counter for an unroll amount of 2. + // Loop will normally trip (limit - init)/stride_con. Since it's a + // CountedLoop this is exact (stride divides limit-init exactly). + // We are going to double the loop body, so we want to knock off any + // odd iteration: (trip_cnt & ~1). Then back compute a new limit. + Node *span = new (C, 3) SubINode( limit, init ); + register_new_node( span, ctrl ); + Node *trip = new (C, 3) DivINode( 0, span, stride ); + register_new_node( trip, ctrl ); + Node *mtwo = _igvn.intcon(-2); + set_ctrl(mtwo, C->root()); + Node *rond = new (C, 3) AndINode( trip, mtwo ); + register_new_node( rond, ctrl ); + Node *spn2 = new (C, 3) MulINode( rond, stride ); + register_new_node( spn2, ctrl ); + new_limit = new (C, 3) AddINode( spn2, init ); + register_new_node( new_limit, ctrl ); + + // Hammer in the new limit + Node *ctrl2 = loop_end->in(0); + Node *cmp2 = new (C, 3) CmpINode( loop_head->incr(), new_limit ); + register_new_node( cmp2, ctrl2 ); + Node *bol2 = new (C, 2) BoolNode( cmp2, loop_end->test_trip() ); + register_new_node( bol2, ctrl2 ); + _igvn.hash_delete(loop_end); + loop_end->set_req(CountedLoopEndNode::TestValue, bol2); + + // Step 3: Find the min-trip test guaranteed before a 'main' loop. + // Make it a 1-trip test (means at least 2 trips). + if( adjust_min_trip ) { + assert( new_limit != NULL, "" ); + // Guard test uses an 'opaque' node which is not shared. Hence I + // can edit it's inputs directly. Hammer in the new limit for the + // minimum-trip guard. + assert( opaq->outcnt() == 1, "" ); + _igvn.hash_delete(opaq); + opaq->set_req(1, new_limit); + } + } // LoopLimitCheck // --------- // Step 4: Clone the loop body. Move it inside the loop. This loop body @@ -1266,6 +1415,7 @@ void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) { CountedLoopNode *cl = loop->_head->as_CountedLoop(); + assert(cl->has_exact_trip_count(), "trip count is not exact"); assert(cl->trip_count() > 0, ""); #ifndef PRODUCT if (TraceLoopOpts) { @@ -1282,6 +1432,7 @@ // Now its tripping an even number of times remaining. Double loop body. // Do not adjust pre-guards; they are not needed and do not exist. if (cl->trip_count() > 0) { + assert((cl->trip_count() & 1) == 0, "missed peeling"); do_unroll(loop, old_new, false); } } @@ -1295,22 +1446,13 @@ } //------------------------------add_constraint--------------------------------- -// Constrain the main loop iterations so the condition: -// scale_con * I + offset < limit +// Constrain the main loop iterations so the conditions: +// low_limit <= scale_con * I + offset < upper_limit // always holds true. That is, either increase the number of iterations in // the pre-loop or the post-loop until the condition holds true in the main // loop. Stride, scale, offset and limit are all loop invariant. Further, // stride and scale are constants (offset and limit often are). -void PhaseIdealLoop::add_constraint( int stride_con, int scale_con, Node *offset, Node *limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ) { - - // Compute "I :: (limit-offset)/scale_con" - Node *con = new (C, 3) SubINode( limit, offset ); - register_new_node( con, pre_ctrl ); - Node *scale = _igvn.intcon(scale_con); - set_ctrl(scale, C->root()); - Node *X = new (C, 3) DivINode( 0, con, scale ); - register_new_node( X, pre_ctrl ); - +void PhaseIdealLoop::add_constraint( int stride_con, int scale_con, Node *offset, Node *low_limit, Node *upper_limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ) { // For positive stride, the pre-loop limit always uses a MAX function // and the main loop a MIN function. For negative stride these are // reversed. @@ -1319,48 +1461,143 @@ // pre-loop must check for underflow and the post-loop for overflow. // Negative stride*scale reverses this; pre-loop checks for overflow and // post-loop for underflow. - if( stride_con*scale_con > 0 ) { - // Compute I < (limit-offset)/scale_con - // Adjust main-loop last iteration to be MIN/MAX(main_loop,X) - *main_limit = (stride_con > 0) - ? (Node*)(new (C, 3) MinINode( *main_limit, X )) - : (Node*)(new (C, 3) MaxINode( *main_limit, X )); - register_new_node( *main_limit, pre_ctrl ); + if (stride_con*scale_con > 0) { + // The overflow limit: scale*I+offset < upper_limit + // For main-loop compute + // ( if (scale > 0) /* and stride > 0 */ + // I < (upper_limit-offset)/scale + // else /* scale < 0 and stride < 0 */ + // I > (upper_limit-offset)/scale + // ) + // + // (upper_limit-offset) may overflow when offset < 0. + // But it is fine since main loop will either have + // less iterations or will be skipped in such case. + Node *con = new (C, 3) SubINode(upper_limit, offset); + register_new_node(con, pre_ctrl); + Node *scale = _igvn.intcon(scale_con); + set_ctrl(scale, C->root()); + Node *X = new (C, 3) DivINode(0, con, scale); + register_new_node(X, pre_ctrl); + + // Adjust main-loop last iteration + Node *loop_limit = *main_limit; + loop_limit = (stride_con > 0) // scale > 0 + ? (Node*)(new (C, 3) MinINode(loop_limit, X)) + : (Node*)(new (C, 3) MaxINode(loop_limit, X)); + register_new_node(loop_limit, pre_ctrl); + *main_limit = loop_limit; - } else { - // Compute (limit-offset)/scale_con + SGN(-scale_con) <= I - // Add the negation of the main-loop constraint to the pre-loop. - // See footnote [++] below for a derivation of the limit expression. - Node *incr = _igvn.intcon(scale_con > 0 ? -1 : 1); - set_ctrl(incr, C->root()); - Node *adj = new (C, 3) AddINode( X, incr ); - register_new_node( adj, pre_ctrl ); - *pre_limit = (scale_con > 0) - ? (Node*)new (C, 3) MinINode( *pre_limit, adj ) - : (Node*)new (C, 3) MaxINode( *pre_limit, adj ); - register_new_node( *pre_limit, pre_ctrl ); + // The underflow limit: low_limit <= scale*I+offset. + // For pre-loop compute + // NOT(scale*I+offset >= low_limit) + // scale*I+offset < low_limit + // ( if (scale > 0) /* and stride > 0 */ + // I < (low_limit-offset)/scale + // else /* scale < 0 and stride < 0 */ + // I > (low_limit-offset)/scale + // ) + + if (low_limit->get_int() == -max_jint) { + if (!RangeLimitCheck) return; + // We need this guard when scale*pre_limit+offset >= limit + // due to underflow so we need execute pre-loop until + // scale*I+offset >= min_int. But (low_limit-offset) will + // underflow when offset > 0 and X will be > original_limit. + // To avoid it we replace offset = offset > 0 ? 0 : offset + // and add min(pre_limit, original_limit). + Node* shift = _igvn.intcon(31); + set_ctrl(shift, C->root()); + Node *neg_off = new (C, 3) RShiftINode(offset, shift); + register_new_node(neg_off, pre_ctrl); + offset = new (C, 3) AndINode(offset, neg_off); + register_new_node(offset, pre_ctrl); + } else { + assert(low_limit->get_int() == 0, "wrong low limit for range check"); + // The only problem we have here when offset == min_int + // since (0-min_int) == min_int. It may be fine for scale > 0 + // but for scale < 0 X will be < original_limit. + } + con = new (C, 3) SubINode(low_limit, offset); + register_new_node(con, pre_ctrl); + scale = _igvn.intcon(scale_con); + set_ctrl(scale, C->root()); + X = new (C, 3) DivINode(0, con, scale); + register_new_node(X, pre_ctrl); -// [++] Here's the algebra that justifies the pre-loop limit expression: -// -// NOT( scale_con * I + offset < limit ) -// == -// scale_con * I + offset >= limit -// == -// SGN(scale_con) * I >= (limit-offset)/|scale_con| -// == -// (limit-offset)/|scale_con| <= I * SGN(scale_con) -// == -// (limit-offset)/|scale_con|-1 < I * SGN(scale_con) -// == -// ( if (scale_con > 0) /*common case*/ -// (limit-offset)/scale_con - 1 < I -// else -// (limit-offset)/scale_con + 1 > I -// ) -// ( if (scale_con > 0) /*common case*/ -// (limit-offset)/scale_con + SGN(-scale_con) < I -// else -// (limit-offset)/scale_con + SGN(-scale_con) > I + // Adjust pre-loop last iteration + loop_limit = *pre_limit; + loop_limit = (stride_con > 0) // scale > 0 + ? (Node*)(new (C, 3) MaxINode(loop_limit, X)) + : (Node*)(new (C, 3) MinINode(loop_limit, X)); + register_new_node( loop_limit, pre_ctrl ); + *pre_limit = loop_limit; + + } else { // stride_con*scale_con < 0 + // For negative stride*scale pre-loop checks for overflow and + // post-loop for underflow. + // + // The underflow limit: low_limit <= scale*I+offset. + // For main-loop compute + // scale*I+offset+1 > low_limit + // ( if (scale < 0) /* and stride > 0 */ + // I < (low_limit-(offset+1))/scale + // else /* scale < 0 and stride < 0 */ + // I > (low_limit-(offset+1))/scale + // ) + + if (low_limit->get_int() == -max_jint) { + if (!RangeLimitCheck) return; + } else { + assert(low_limit->get_int() == 0, "wrong low limit for range check"); + } + + Node *one = _igvn.intcon(1); + set_ctrl(one, C->root()); + Node *plus_one = new (C, 3) AddINode(offset, one); + register_new_node( plus_one, pre_ctrl ); + Node *con = new (C, 3) SubINode(low_limit, plus_one); + register_new_node(con, pre_ctrl); + Node *scale = _igvn.intcon(scale_con); + set_ctrl(scale, C->root()); + Node *X = new (C, 3) DivINode(0, con, scale); + register_new_node(X, pre_ctrl); + + // Adjust main-loop last iteration + Node *loop_limit = *main_limit; + loop_limit = (stride_con > 0) // scale < 0 + ? (Node*)(new (C, 3) MinINode(loop_limit, X)) + : (Node*)(new (C, 3) MaxINode(loop_limit, X)); + register_new_node(loop_limit, pre_ctrl); + *main_limit = loop_limit; + + // The overflow limit: scale*I+offset < upper_limit + // For pre-loop compute + // NOT(scale*I+offset < upper_limit) + // scale*I+offset >= upper_limit + // scale*I+offset+1 > upper_limit + // ( if (scale < 0) /* and stride > 0 */ + // I < (upper_limit-(offset+1))/scale + // else /* scale < 0 and stride < 0 */ + // I > (upper_limit-(offset+1))/scale + // ) + plus_one = new (C, 3) AddINode(offset, one); + register_new_node( plus_one, pre_ctrl ); + con = new (C, 3) SubINode(upper_limit, plus_one); + register_new_node(con, pre_ctrl); + scale = _igvn.intcon(scale_con); + set_ctrl(scale, C->root()); + X = new (C, 3) DivINode(0, con, scale); + register_new_node(X, pre_ctrl); + + // Adjust pre-loop last iteration + loop_limit = *pre_limit; + loop_limit = (stride_con > 0) // scale < 0 + ? (Node*)(new (C, 3) MaxINode(loop_limit, X)) + : (Node*)(new (C, 3) MinINode(loop_limit, X)); + register_new_node( loop_limit, pre_ctrl ); + *pre_limit = loop_limit; + } } @@ -1491,7 +1728,7 @@ Node *cmpzm = bolzm->in(1); assert(cmpzm->is_Cmp(), ""); Node *opqzm = cmpzm->in(2); - // Can not optimize a loop if pre-loop Opaque1 node is optimized + // Can not optimize a loop if zero-trip Opaque1 node is optimized // away and then another round of loop opts attempted. if (opqzm->Opcode() != Op_Opaque1) return; @@ -1526,8 +1763,11 @@ int stride_con = cl->stride_con(); Node *zero = _igvn.intcon(0); Node *one = _igvn.intcon(1); + // Use symmetrical int range [-max_jint,max_jint] + Node *mini = _igvn.intcon(-max_jint); set_ctrl(zero, C->root()); set_ctrl(one, C->root()); + set_ctrl(mini, C->root()); // Range checks that do not dominate the loop backedge (ie. // conditionally executed) can lengthen the pre loop limit beyond @@ -1602,7 +1842,12 @@ if( offset_c == ctrl ) { 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:" : ":"); + bol->dump(2); + } +#endif // At this point we have the expression as: // scale_con * trip_counter + offset :: limit // where scale_con, offset and limit are loop invariant. Trip_counter @@ -1613,17 +1858,16 @@ // Adjust pre and main loop limits to guard the correct iteration set if( cmp->Opcode() == Op_CmpU ) {// Unsigned compare is really 2 tests if( b_test._test == BoolTest::lt ) { // Range checks always use lt - // The overflow limit: scale*I+offset < limit - add_constraint( stride_con, scale_con, offset, limit, pre_ctrl, &pre_limit, &main_limit ); - // The underflow limit: 0 <= scale*I+offset. - // Some math yields: -scale*I-(offset+1) < 0 - Node *plus_one = new (C, 3) AddINode( offset, one ); - register_new_node( plus_one, pre_ctrl ); - Node *neg_offset = new (C, 3) SubINode( zero, plus_one ); - register_new_node( neg_offset, pre_ctrl ); - add_constraint( stride_con, -scale_con, neg_offset, zero, pre_ctrl, &pre_limit, &main_limit ); + // 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 ); if (!conditional_rc) { conditional_rc = !loop->dominates_backedge(iff); + // It is also needed if offset->_lo == min_int since + // (0-min_int) == min_int. It may be fine for stride > 0 + // but for stride < 0 pre_limit will be < original_limit. + const TypeInt* offset_t = _igvn.type(offset)->is_int(); + conditional_rc |= RangeLimitCheck && (offset_t->_lo == min_jint) && + (scale_con<0) && (stride_con<0); } } else { #ifndef PRODUCT @@ -1634,21 +1878,35 @@ } } else { // Otherwise work on normal compares switch( b_test._test ) { - case BoolTest::ge: // Convert X >= Y to -X <= -Y + case BoolTest::gt: + // Fall into GE case + case BoolTest::ge: + // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit scale_con = -scale_con; offset = new (C, 3) SubINode( zero, offset ); register_new_node( offset, pre_ctrl ); limit = new (C, 3) SubINode( zero, limit ); register_new_node( limit, pre_ctrl ); // Fall into LE case - case BoolTest::le: // Convert X <= Y to X < Y+1 - limit = new (C, 3) AddINode( limit, one ); - register_new_node( limit, pre_ctrl ); + case BoolTest::le: + if (b_test._test != BoolTest::gt) { + // Convert X <= Y to X < Y+1 + limit = new (C, 3) AddINode( limit, one ); + register_new_node( limit, pre_ctrl ); + } // Fall into LT case case BoolTest::lt: - add_constraint( stride_con, scale_con, offset, limit, pre_ctrl, &pre_limit, &main_limit ); + // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit + add_constraint( stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit ); if (!conditional_rc) { conditional_rc = !loop->dominates_backedge(iff); + // It is also needed if scale*pre_limit+offset >= limit + // due to underflow so we need execute pre-loop until + // scale*I+offset >= min_int. But (low_limit-offset) will + // underflow when offset > 0 and X will be > original_limit. + const TypeInt* offset_t = _igvn.type(offset)->is_int(); + conditional_rc |= RangeLimitCheck && (offset_t->_hi > 0) && + (scale_con>0) && (stride_con>0); } break; default: @@ -1699,7 +1957,8 @@ // Note:: we are making the main loop limit no longer precise; // need to round up based on stride. - if( stride_con != 1 && stride_con != -1 ) { // Cutout for common case + cl->set_nonexact_trip_count(); + if (!LoopLimitCheck && stride_con != 1 && stride_con != -1) { // Cutout for common case // "Standard" round-up logic: ([main_limit-init+(y-1)]/y)*y+init // Hopefully, compiler will optimize for powers of 2. Node *ctrl = get_ctrl(main_limit); @@ -1879,7 +2138,19 @@ // iteration. Then the CountedLoopEnd will collapse (backedge never // taken) and all loop-invariant uses of the exit values will be correct. Node *phi = cl->phi(); - Node *final = new (phase->C, 3) SubINode( cl->limit(), cl->stride() ); + Node *exact_limit = phase->exact_limit(this); + if (exact_limit != cl->limit()) { + // We also need to replace the original limit to collapse loop exit. + Node* cmp = cl->loopexit()->cmp_node(); + assert(cl->limit() == cmp->in(2), "sanity"); + phase->_igvn._worklist.push(cmp->in(2)); // put limit on worklist + phase->_igvn.hash_delete(cmp); + cmp->set_req(2, exact_limit); + phase->_igvn._worklist.push(cmp); // put cmp on worklist + } + // Note: the final value after increment should not overflow since + // counted loop has limit check predicate. + Node *final = new (phase->C, 3) SubINode( exact_limit, cl->stride() ); phase->register_new_node(final,cl->in(LoopNode::EntryControl)); phase->_igvn.replace_node(phi,final); phase->C->set_major_progress(); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/loopUnswitch.cpp --- a/src/share/vm/opto/loopUnswitch.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/loopUnswitch.cpp Wed May 04 13:12:42 2011 -0700 @@ -130,6 +130,11 @@ Node* uniqc = proj_true->unique_ctrl_out(); Node* entry = head->in(LoopNode::EntryControl); Node* predicate = find_predicate(entry); + if (predicate != NULL && LoopLimitCheck && UseLoopPredicate) { + // We may have two predicates, find first. + entry = find_predicate(entry->in(0)->in(0)); + if (entry != NULL) predicate = entry; + } if (predicate != NULL) predicate = predicate->in(0); assert(proj_true->is_IfTrue() && (predicate == NULL && uniqc == head || @@ -217,6 +222,7 @@ ProjNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop, Node_List &old_new) { LoopNode* head = loop->_head->as_Loop(); + bool counted_loop = head->is_CountedLoop(); Node* entry = head->in(LoopNode::EntryControl); _igvn.hash_delete(entry); _igvn._worklist.push(entry); @@ -242,14 +248,14 @@ assert(old_new[head->_idx]->is_Loop(), "" ); // Fast (true) control - Node* iffast_pred = clone_loop_predicates(entry, iffast); + Node* iffast_pred = clone_loop_predicates(entry, iffast, !counted_loop); _igvn.hash_delete(head); head->set_req(LoopNode::EntryControl, iffast_pred); set_idom(head, iffast_pred, dom_depth(head)); _igvn._worklist.push(head); // Slow (false) control - Node* ifslow_pred = move_loop_predicates(entry, ifslow); + Node* ifslow_pred = move_loop_predicates(entry, ifslow, !counted_loop); LoopNode* slow_head = old_new[head->_idx]->as_Loop(); _igvn.hash_delete(slow_head); slow_head->set_req(LoopNode::EntryControl, ifslow_pred); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/loopnode.cpp --- a/src/share/vm/opto/loopnode.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/loopnode.cpp Wed May 04 13:12:42 2011 -0700 @@ -206,7 +206,7 @@ // Get backedge compare Node *cmp = test->in(1); int cmp_op = cmp->Opcode(); - if( cmp_op != Op_CmpI ) + if (cmp_op != Op_CmpI) return false; // Avoid pointer & float compares // Find the trip-counter increment & limit. Limit must be loop invariant. @@ -259,7 +259,8 @@ } // Stride must be constant int stride_con = stride->get_int(); - assert(stride_con != 0, "missed some peephole opt"); + if (stride_con == 0) + return false; // missed some peephole opt if (!xphi->is_Phi()) return false; // Too much math on the trip counter @@ -319,7 +320,7 @@ // Count down loop rolls through MAXINT (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 || // Count up loop rolls through MININT - (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0 ) { + (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) { return false; // Bail out } @@ -341,12 +342,137 @@ // assert(x->Opcode() == Op_Loop, "regular loops only"); C->print_method("Before CountedLoop", 3); + + Node *hook = new (C, 6) Node(6); + + if (LoopLimitCheck) { + + // =================================================== + // Generate loop limit check to avoid integer overflow + // in cases like next (cyclic loops): + // + // for (i=0; i <= max_jint; i++) {} + // for (i=0; i < max_jint; i+=2) {} + // + // + // Limit check predicate depends on the loop test: + // + // for(;i != limit; i++) --> limit <= (max_jint) + // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1) + // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride ) + // + + // Check if limit is excluded to do more precise int overflow check. + bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge); + int stride_m = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1)); + + // If compare points directly to the phi we need to adjust + // the compare so that it points to the incr. Limit have + // to be adjusted to keep trip count the same and the + // adjusted limit should be checked for int overflow. + if (phi_incr != NULL) { + stride_m += stride_con; + } + + if (limit->is_Con()) { + int limit_con = limit->get_int(); + if ((stride_con > 0 && limit_con > (max_jint - stride_m)) || + (stride_con < 0 && limit_con < (min_jint - stride_m))) { + // Bailout: it could be integer overflow. + return false; + } + } else if ((stride_con > 0 && limit_t->_hi <= (max_jint - stride_m)) || + (stride_con < 0 && limit_t->_lo >= (min_jint - stride_m))) { + // Limit's type may satisfy the condition, for example, + // when it is an array length. + } else { + // Generate loop's limit check. + // Loop limit check predicate should be near the loop. + ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check); + if (!limit_check_proj) { + // The limit check predicate is not generated if this method trapped here before. +#ifdef ASSERT + if (TraceLoopLimitCheck) { + tty->print("missing loop limit check:"); + loop->dump_head(); + x->dump(1); + } +#endif + return false; + } + + IfNode* check_iff = limit_check_proj->in(0)->as_If(); + Node* cmp_limit; + Node* bol; + + if (stride_con > 0) { + cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(max_jint - stride_m)); + bol = new (C, 2) BoolNode(cmp_limit, BoolTest::le); + } else { + cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(min_jint - stride_m)); + bol = new (C, 2) BoolNode(cmp_limit, BoolTest::ge); + } + cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit); + bol = _igvn.register_new_node_with_optimizer(bol); + set_subtree_ctrl(bol); + + // Replace condition in original predicate but preserve Opaque node + // so that previous predicates could be found. + assert(check_iff->in(1)->Opcode() == Op_Conv2B && + check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, ""); + Node* opq = check_iff->in(1)->in(1); + _igvn.hash_delete(opq); + opq->set_req(1, bol); + // Update ctrl. + set_ctrl(opq, check_iff->in(0)); + set_ctrl(check_iff->in(1), check_iff->in(0)); + #ifndef PRODUCT - if (TraceLoopOpts) { - tty->print("Counted "); - loop->dump_head(); + // report that the loop predication has been actually performed + // for this loop + if (TraceLoopLimitCheck) { + tty->print_cr("Counted Loop Limit Check generated:"); + debug_only( bol->dump(2); ) + } +#endif + } + + if (phi_incr != NULL) { + // If compare points directly to the phi we need to adjust + // the compare so that it points to the incr. Limit have + // to be adjusted to keep trip count the same and we + // should avoid int overflow. + // + // i = init; do {} while(i++ < limit); + // is converted to + // i = init; do {} while(++i < limit+1); + // + limit = gvn->transform(new (C, 3) AddINode(limit, stride)); } -#endif + + // Now we need to canonicalize loop condition. + if (bt == BoolTest::ne) { + assert(stride_con == 1 || stride_con == -1, "simple increment only"); + bt = (stride_con > 0) ? BoolTest::lt : BoolTest::gt; + } + + if (incl_limit) { + // The limit check guaranties that 'limit <= (max_jint - stride)' so + // we can convert 'i <= limit' to 'i < limit+1' since stride != 0. + // + Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1); + limit = gvn->transform(new (C, 3) AddINode(limit, one)); + if (bt == BoolTest::le) + bt = BoolTest::lt; + else if (bt == BoolTest::ge) + bt = BoolTest::gt; + else + ShouldNotReachHere(); + } + set_subtree_ctrl( limit ); + + } else { // LoopLimitCheck + // If compare points to incr, we are ok. Otherwise the compare // can directly point to the phi; in this case adjust the compare so that // it points to the incr by adjusting the limit. @@ -359,7 +485,6 @@ Node *one_m = gvn->intcon(-1); Node *trip_count = NULL; - Node *hook = new (C, 6) Node(6); switch( bt ) { case BoolTest::eq: ShouldNotReachHere(); @@ -441,6 +566,8 @@ limit = gvn->transform(new (C, 3) AddINode(span,init_trip)); set_subtree_ctrl( limit ); + } // LoopLimitCheck + // Check for SafePoint on backedge and remove Node *sfpt = x->in(LoopNode::LoopBackControl); if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) { @@ -531,7 +658,7 @@ // Check for immediately preceding SafePoint and remove Node *sfpt2 = le->in(0); - if( sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) + if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control)); // Free up intermediate goo @@ -541,12 +668,56 @@ assert(l->is_valid_counted_loop(), "counted loop shape is messed up"); assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" ); #endif +#ifndef PRODUCT + if (TraceLoopOpts) { + tty->print("Counted "); + loop->dump_head(); + } +#endif C->print_method("After CountedLoop", 3); return true; } +//----------------------exact_limit------------------------------------------- +Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) { + assert(loop->_head->is_CountedLoop(), ""); + CountedLoopNode *cl = loop->_head->as_CountedLoop(); + + if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 || + cl->limit()->Opcode() == Op_LoopLimit) { + // Old code has exact limit (it could be incorrect in case of int overflow). + // Loop limit is exact with stride == 1. And loop may already have exact limit. + return cl->limit(); + } + Node *limit = NULL; +#ifdef ASSERT + BoolTest::mask bt = cl->loopexit()->test_trip(); + assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected"); +#endif + if (cl->has_exact_trip_count()) { + // Simple case: loop has constant boundaries. + // Use longs to avoid integer overflow. + int stride_con = cl->stride_con(); + long init_con = cl->init_trip()->get_int(); + long limit_con = cl->limit()->get_int(); + julong trip_cnt = cl->trip_count(); + long final_con = init_con + trip_cnt*stride_con; + final_con -= stride_con; + int final_int = (int)final_con; + // The final value should be in integer range since the loop + // is counted and the limit was checked for overflow. + assert(final_con == (long)final_int, "final value should be integer"); + limit = _igvn.intcon(final_int); + } else { + // Create new LoopLimit node to get exact limit (final iv value). + limit = new (C, 4) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride()); + register_new_node(limit, cl->in(LoopNode::EntryControl)); + } + assert(limit != NULL, "sanity"); + return limit; +} //------------------------------Ideal------------------------------------------ // Return a node which is more "ideal" than the current node. @@ -572,14 +743,12 @@ #ifndef PRODUCT void CountedLoopNode::dump_spec(outputStream *st) const { LoopNode::dump_spec(st); - if( stride_is_con() ) { + if (stride_is_con()) { st->print("stride: %d ",stride_con()); - } else { - st->print("stride: not constant "); } - if( is_pre_loop () ) st->print("pre of N%d" , _main_idx ); - if( is_main_loop() ) st->print("main of N%d", _idx ); - if( is_post_loop() ) st->print("post of N%d", _main_idx ); + if (is_pre_loop ()) st->print("pre of N%d" , _main_idx); + if (is_main_loop()) st->print("main of N%d", _idx); + if (is_post_loop()) st->print("post of N%d", _main_idx); } #endif @@ -588,7 +757,130 @@ return stride()->bottom_type()->is_int()->get_con(); } - +//============================================================================= +//------------------------------Value----------------------------------------- +const Type *LoopLimitNode::Value( PhaseTransform *phase ) const { + const Type* init_t = phase->type(in(Init)); + const Type* limit_t = phase->type(in(Limit)); + const Type* stride_t = phase->type(in(Stride)); + // Either input is TOP ==> the result is TOP + if (init_t == Type::TOP) return Type::TOP; + if (limit_t == Type::TOP) return Type::TOP; + if (stride_t == Type::TOP) return Type::TOP; + + int stride_con = stride_t->is_int()->get_con(); + if (stride_con == 1) + return NULL; // Identity + + if (init_t->is_int()->is_con() && limit_t->is_int()->is_con()) { + // Use longs to avoid integer overflow. + long init_con = init_t->is_int()->get_con(); + long limit_con = limit_t->is_int()->get_con(); + int stride_m = stride_con - (stride_con > 0 ? 1 : -1); + long trip_count = (limit_con - init_con + stride_m)/stride_con; + long final_con = init_con + stride_con*trip_count; + int final_int = (int)final_con; + // The final value should be in integer range since the loop + // is counted and the limit was checked for overflow. + assert(final_con == (long)final_int, "final value should be integer"); + return TypeInt::make(final_int); + } + + return bottom_type(); // TypeInt::INT +} + +//------------------------------Ideal------------------------------------------ +// Return a node which is more "ideal" than the current node. +Node *LoopLimitNode::Ideal(PhaseGVN *phase, bool can_reshape) { + if (phase->type(in(Init)) == Type::TOP || + phase->type(in(Limit)) == Type::TOP || + phase->type(in(Stride)) == Type::TOP) + return NULL; // Dead + + int stride_con = phase->type(in(Stride))->is_int()->get_con(); + if (stride_con == 1) + return NULL; // Identity + + if (in(Init)->is_Con() && in(Limit)->is_Con()) + return NULL; // Value + + // Delay following optimizations until all loop optimizations + // done to keep Ideal graph simple. + if (!can_reshape || phase->C->major_progress()) + return NULL; + + const TypeInt* init_t = phase->type(in(Init) )->is_int(); + const TypeInt* limit_t = phase->type(in(Limit))->is_int(); + int stride_p; + long lim, ini; + julong max; + if (stride_con > 0) { + stride_p = stride_con; + lim = limit_t->_hi; + ini = init_t->_lo; + max = (julong)max_jint; + } else { + stride_p = -stride_con; + lim = init_t->_hi; + ini = limit_t->_lo; + max = (julong)min_jint; + } + julong range = lim - ini + stride_p; + if (range <= max) { + // Convert to integer expression if it is not overflow. + Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1)); + Node *range = phase->transform(new (phase->C, 3) SubINode(in(Limit), in(Init))); + Node *bias = phase->transform(new (phase->C, 3) AddINode(range, stride_m)); + Node *trip = phase->transform(new (phase->C, 3) DivINode(0, bias, in(Stride))); + Node *span = phase->transform(new (phase->C, 3) MulINode(trip, in(Stride))); + return new (phase->C, 3) AddINode(span, in(Init)); // exact limit + } + + if (is_power_of_2(stride_p) || // divisor is 2^n + !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node? + // Convert to long expression to avoid integer overflow + // and let igvn optimizer convert this division. + // + Node* init = phase->transform( new (phase->C, 2) ConvI2LNode(in(Init))); + Node* limit = phase->transform( new (phase->C, 2) ConvI2LNode(in(Limit))); + Node* stride = phase->longcon(stride_con); + Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1)); + + Node *range = phase->transform(new (phase->C, 3) SubLNode(limit, init)); + Node *bias = phase->transform(new (phase->C, 3) AddLNode(range, stride_m)); + Node *span; + if (stride_con > 0 && is_power_of_2(stride_p)) { + // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride) + // and avoid generating rounding for division. Zero trip guard should + // guarantee that init < limit but sometimes the guard is missing and + // we can get situation when init > limit. Note, for the empty loop + // optimization zero trip guard is generated explicitly which leaves + // only RCE predicate where exact limit is used and the predicate + // will simply fail forcing recompilation. + Node* neg_stride = phase->longcon(-stride_con); + span = phase->transform(new (phase->C, 3) AndLNode(bias, neg_stride)); + } else { + Node *trip = phase->transform(new (phase->C, 3) DivLNode(0, bias, stride)); + span = phase->transform(new (phase->C, 3) MulLNode(trip, stride)); + } + // Convert back to int + Node *span_int = phase->transform(new (phase->C, 2) ConvL2INode(span)); + return new (phase->C, 3) AddINode(span_int, in(Init)); // exact limit + } + + return NULL; // No progress +} + +//------------------------------Identity--------------------------------------- +// If stride == 1 return limit node. +Node *LoopLimitNode::Identity( PhaseTransform *phase ) { + int stride_con = phase->type(in(Stride))->is_int()->get_con(); + if (stride_con == 1 || stride_con == -1) + return in(Limit); + return this; +} + +//============================================================================= //----------------------match_incr_with_optional_truncation-------------------- // Match increment with optional truncation: // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16 @@ -870,7 +1162,7 @@ outer = igvn.register_new_node_with_optimizer(outer, _head); phase->set_created_loop_node(); - Node* pred = phase->clone_loop_predicates(ctl, outer); + Node* pred = phase->clone_loop_predicates(ctl, outer, true); // Outermost loop falls into '_head' loop _head->set_req(LoopNode::EntryControl, pred); _head->del_req(outer_idx); @@ -1440,9 +1732,16 @@ tty->print(" "); tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx); if (_irreducible) tty->print(" IRREDUCIBLE"); + Node* entry = _head->in(LoopNode::EntryControl); + if (LoopLimitCheck) { + Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); + if (predicate != NULL ) { + tty->print(" limit_check"); + entry = entry->in(0)->in(0); + } + } if (UseLoopPredicate) { - Node* entry = PhaseIdealLoop::find_predicate_insertion_point(_head->in(LoopNode::EntryControl), - Deoptimization::Reason_predicate); + entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); if (entry != NULL) { tty->print(" predicated"); } @@ -1528,10 +1827,15 @@ !loop->tail()->is_top()) { LoopNode* lpn = loop->_head->as_Loop(); Node* entry = lpn->in(LoopNode::EntryControl); - Node* predicate_proj = find_predicate(entry); + Node* predicate_proj = find_predicate(entry); // loop_limit_check first 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"); useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one + entry = entry->in(0)->in(0); + } + predicate_proj = find_predicate(entry); // Predicate + if (predicate_proj != NULL ) { + useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one } } @@ -1542,6 +1846,8 @@ //------------------------eliminate_useless_predicates----------------------------- // Eliminate all inserted predicates if they could not be used by loop predication. +// Note: it will also eliminates loop limits check predicate since it also uses +// Opaque1 node (see Parse::add_predicate()). void PhaseIdealLoop::eliminate_useless_predicates() { if (C->predicate_count() == 0) return; // no predicate left @@ -1731,7 +2037,7 @@ // Some parser-inserted loop predicates could never be used by loop // predication or they were moved away from loop during some optimizations. // For example, peeling. Eliminate them before next loop optimizations. - if (UseLoopPredicate) { + if (UseLoopPredicate || LoopLimitCheck) { eliminate_useless_predicates(); } diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/loopnode.hpp --- a/src/share/vm/opto/loopnode.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/loopnode.hpp Wed May 04 13:12:42 2011 -0700 @@ -289,6 +289,28 @@ inline Node *CountedLoopNode::incr() const { return loopexit() ? loopexit()->incr() : NULL; } inline Node *CountedLoopNode::phi() const { return loopexit() ? loopexit()->phi() : NULL; } +//------------------------------LoopLimitNode----------------------------- +// Counted Loop limit node which represents exact final iterator value: +// trip_count = (limit - init_trip + stride - 1)/stride +// final_value= trip_count * stride + init_trip. +// Use HW instructions to calculate it when it can overflow in integer. +// Note, final_value should fit into integer since counted loop has +// limit check: limit <= max_int-stride. +class LoopLimitNode : public Node { + enum { Init=1, Limit=2, Stride=3 }; + public: + LoopLimitNode( Compile* C, Node *init, Node *limit, Node *stride ) : Node(0,init,limit,stride) { + // Put it on the Macro nodes list to optimize during macro nodes expansion. + init_flags(Flag_is_macro); + C->add_macro_node(this); + } + virtual int Opcode() const; + virtual const Type *bottom_type() const { return TypeInt::INT; } + virtual uint ideal_reg() const { return Op_RegI; } + virtual const Type *Value( PhaseTransform *phase ) const; + virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); + virtual Node *Identity( PhaseTransform *phase ); +}; // -----------------------------IdealLoopTree---------------------------------- class IdealLoopTree : public ResourceObj { @@ -775,6 +797,8 @@ bool is_counted_loop( Node *x, IdealLoopTree *loop ); + Node* exact_limit( IdealLoopTree *loop ); + // Return a post-walked LoopNode IdealLoopTree *get_loop( Node *n ) const { // Dead nodes have no loop, so return the top level loop instead @@ -837,7 +861,6 @@ bool is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth = 0); // Return true if proj is for "proj->[region->..]call_uct" - // Return true if proj is for "proj->[region->..]call_uct" static bool is_uncommon_trap_proj(ProjNode* proj, Deoptimization::DeoptReason reason); // Return true for "if(test)-> proj -> ... // | @@ -860,10 +883,11 @@ PhaseIterGVN* igvn); static Node* clone_loop_predicates(Node* old_entry, Node* new_entry, bool move_predicates, + bool clone_limit_check, PhaseIdealLoop* loop_phase, PhaseIterGVN* igvn); - Node* clone_loop_predicates(Node* old_entry, Node* new_entry); - Node* move_loop_predicates(Node* old_entry, Node* new_entry); + Node* clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check); + Node* move_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check); void eliminate_loop_predicates(Node* entry); static Node* skip_loop_predicates(Node* entry); @@ -873,7 +897,7 @@ // Find a predicate static Node* find_predicate(Node* entry); // Construct a range check for a predicate if - BoolNode* rc_predicate(Node* ctrl, + BoolNode* rc_predicate(IdealLoopTree *loop, Node* ctrl, int scale, Node* offset, Node* init, Node* limit, Node* stride, Node* range, bool upper); @@ -903,11 +927,11 @@ // Range Check Elimination uses this function! // Constrain the main loop iterations so the affine function: - // scale_con * I + offset < limit + // low_limit <= scale_con * I + offset < upper_limit // always holds true. That is, either increase the number of iterations in // the pre-loop or the post-loop until the condition holds true in the main // loop. Scale_con, offset and limit are all loop invariant. - void add_constraint( int stride_con, int scale_con, Node *offset, Node *limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ); + void add_constraint( int stride_con, int scale_con, Node *offset, Node *low_limit, Node *upper_limit, Node *pre_ctrl, Node **pre_limit, Node **main_limit ); // Partially peel loop up through last_peel node. bool partial_peel( IdealLoopTree *loop, Node_List &old_new ); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/macro.cpp --- a/src/share/vm/opto/macro.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/macro.cpp Wed May 04 13:12:42 2011 -0700 @@ -2154,6 +2154,11 @@ debug_only(int old_macro_count = C->macro_count();); if (n->is_AbstractLock()) { success = eliminate_locking_node(n->as_AbstractLock()); + } else if (n->Opcode() == Op_LoopLimit) { + // Remove it from macro list and put on IGVN worklist to optimize. + C->remove_macro_node(n); + _igvn._worklist.push(n); + success = true; } else if (n->Opcode() == Op_Opaque1 || n->Opcode() == Op_Opaque2) { _igvn.replace_node(n, n->in(1)); success = true; diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/matcher.cpp --- a/src/share/vm/opto/matcher.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/matcher.cpp Wed May 04 13:12:42 2011 -0700 @@ -2086,6 +2086,13 @@ n->del_req(3); break; } + case Op_LoopLimit: { + Node *pair1 = new (C, 3) BinaryNode(n->in(1),n->in(2)); + n->set_req(1,pair1); + n->set_req(2,n->in(3)); + n->del_req(3); + break; + } case Op_StrEquals: { Node *pair1 = new (C, 3) BinaryNode(n->in(2),n->in(3)); n->set_req(2,pair1); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/parse.hpp --- a/src/share/vm/opto/parse.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/parse.hpp Wed May 04 13:12:42 2011 -0700 @@ -70,7 +70,7 @@ const char* try_to_inline(ciMethod* callee_method, ciMethod* caller_method, int caller_bci, ciCallProfile& profile, WarmCallInfo* wci_result); const char* shouldInline(ciMethod* callee_method, ciMethod* caller_method, int caller_bci, ciCallProfile& profile, WarmCallInfo* wci_result) const; const char* shouldNotInline(ciMethod* callee_method, ciMethod* caller_method, WarmCallInfo* wci_result) const; - void print_inlining(ciMethod *callee_method, int caller_bci, const char *failure_msg) const PRODUCT_RETURN; + void print_inlining(ciMethod *callee_method, int caller_bci, const char *failure_msg) const; InlineTree *caller_tree() const { return _caller_tree; } InlineTree* callee_at(int bci, ciMethod* m) const; diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/parse1.cpp --- a/src/share/vm/opto/parse1.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/parse1.cpp Wed May 04 13:12:42 2011 -0700 @@ -638,7 +638,7 @@ ensure_phis_everywhere(); if (block->is_SEL_head() && - UseLoopPredicate) { + (UseLoopPredicate || LoopLimitCheck)) { // Add predicate to single entry (not irreducible) loop head. assert(!block->has_merged_backedge(), "only entry paths should be merged for now"); // Need correct bci for predicate. diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/opto/phaseX.hpp --- a/src/share/vm/opto/phaseX.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/opto/phaseX.hpp Wed May 04 13:12:42 2011 -0700 @@ -472,8 +472,8 @@ } // Clone loop predicates. Defined in loopTransform.cpp. - Node* clone_loop_predicates(Node* old_entry, Node* new_entry); - Node* move_loop_predicates(Node* old_entry, Node* new_entry); + Node* clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check); + Node* move_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check); // Create a new if below new_entry for the predicate to be cloned ProjNode* create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry, Deoptimization::DeoptReason reason); diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/runtime/deoptimization.cpp --- a/src/share/vm/runtime/deoptimization.cpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/runtime/deoptimization.cpp Wed May 04 13:12:42 2011 -0700 @@ -1773,7 +1773,8 @@ "constraint", "div0_check", "age", - "predicate" + "predicate", + "loop_limit_check" }; const char* Deoptimization::_trap_action_name[Action_LIMIT] = { // Note: Keep this in sync. with enum DeoptAction. diff -r 0139aac70fb5 -r bad7ecd0b6ed src/share/vm/runtime/deoptimization.hpp --- a/src/share/vm/runtime/deoptimization.hpp Wed May 04 03:42:58 2011 -0700 +++ b/src/share/vm/runtime/deoptimization.hpp Wed May 04 13:12:42 2011 -0700 @@ -56,6 +56,7 @@ Reason_div0_check, // a null_check due to division by zero Reason_age, // nmethod too old; tier threshold reached Reason_predicate, // compiler generated predicate failed + Reason_loop_limit_check, // compiler generated loop limits check failed Reason_LIMIT, // Note: Keep this enum in sync. with _trap_reason_name. Reason_RECORDED_LIMIT = Reason_bimorphic // some are not recorded per bc @@ -78,7 +79,7 @@ enum { _action_bits = 3, - _reason_bits = 4, + _reason_bits = 5, _action_shift = 0, _reason_shift = _action_shift+_action_bits, BC_CASE_LIMIT = PRODUCT_ONLY(1) NOT_PRODUCT(4) // for _deoptimization_hist diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test5091921.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test5091921.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,309 @@ +/* + * Copyright (c) 2011 Hewlett-Packard Company. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 5091921 + * @summary Sign flip issues in loop optimizer + * + * @run main/othervm -Xcomp -XX:CompileOnly=Test5091921 -XX:MaxInlineSize=1 Test5091921 + */ + +public class Test5091921 { + private static int result = 0; + + + /* Test for the bug of transforming indx >= MININT to indx > MININT-1 */ + public static int test_ge1(int limit) { + int indx; + int sum = 0; + for (indx = 500; indx >= limit; indx -= 2) { + sum += 2000 / indx; + result = sum; + } + return sum; + } + + /* Test for the bug of transforming indx <= MAXINT to indx < MAXINT+1 */ + public static int test_le1(int limit) { + int indx; + int sum = 0; + for (indx = -500; indx <= limit; indx += 2) + { + sum += 3000 / indx; + result = sum; + } + return sum; + } + + /* Run with -Xcomp -XX:CompileOnly=wrap1.test1 -XX:MaxInlineSize=1 */ + /* limit reset to ((limit-init+stride-1)/stride)*stride+init */ + /* Calculation may overflow */ + public static volatile int c = 1; + public static int test_wrap1(int limit) + { + int indx; + int sum = 0; + for (indx = 0xffffffff; indx < limit; indx += 0x20000000) + { + sum += c; + } + return sum; + } + + /* Test for range check elimination with bit flip issue for + scale*i+offset 0x80000000) + { + // this test is not issued in pre-loop but issued in main loop + // trick rce into thinking expression is false when indx >= 0 + // in fact it is false when indx==0x80000001 + if (indx - 9 < -9) + { + sum += indx; + result = sum; + sum ^= b[indx & 7]; + result = sum; + } + else + break; + } + else + { + sum += b[indx & 3]; + result = sum; + } + } + return sum; + } + + /* Test for range check elimination with bit flip issue for + scale*i 1 */ + static int[] box6 = {1,2,3,4,5,6,7,8,9}; + public static int test_rce6(int[] b, int limit) + { + int indx; + int sum = b[1]; + result = sum; + for (indx = 0x80000000; indx < limit; ++indx) + { + if (indx > 0x80000000) + { + // harmless rce target + if (indx < 0) + { + sum += result; + result = sum; + } + else + break; + // this test is not issued in pre-loop but issued in main loop + // trick rce into thinking expression is false when indx >= 0 + // in fact it is false when indx==0x80000001 + // In compilers that transform mulI to shiftI may mask this issue. + if (indx * 28 + 1 < 0) + { + sum += indx; + result = sum; + sum ^= b[indx & 7]; + result = sum; + } + else + break; + } + else + { + sum += b[indx & 3]; + result = sum; + } + } + return sum; + } + + /* Test for range check elimination with i <= limit */ + static int[] box7 = {1,2,3,4,5,6,7,8,9,0x7fffffff}; + public static int test_rce7(int[] b) + { + int indx; + int max = b[9]; + int sum = b[7]; + result = sum; + for (indx = 0; indx < b.length; ++indx) + { + if (indx <= max) + { + sum += (indx ^ 15) + ((result != 0) ? 0 : sum); + result = sum; + } + else + throw new RuntimeException(); + } + for (indx = -7; indx < b.length; ++indx) + { + if (indx <= 9) + { + sum += (sum ^ 15) + ((result != 0) ? 0 : sum); + result = sum; + } + else + throw new RuntimeException(); + } + return sum; + } + + /* Test for range check elimination with i >= limit */ + static int[] box8 = {-1,0,1,2,3,4,5,6,7,8,0x80000000}; + public static int test_rce8(int[] b) + { + int indx; + int sum = b[5]; + int min = b[10]; + result = sum; + for (indx = b.length-1; indx >= 0; --indx) + { + if (indx >= min) + { + sum += (sum ^ 9) + ((result != 0) ? 0 :sum); + result = sum; + } + else + throw new RuntimeException(); + } + return sum; + } + + public static void main(String[] args) + { + result=1; + int r = 0; + try { + r = test_ge1(0x80000000); + System.out.println(result); + System.out.println("test_ge1 FAILED"); + System.exit(1); + } + catch (ArithmeticException e1) { + System.out.println("test_ge1: Expected exception caught"); + if (result != 5986) { + System.out.println(result); + System.out.println("test_ge1 FAILED"); + System.exit(97); + } + } + System.out.println("test_ge1 WORKED"); + + result=0; + try + { + r = test_le1(0x7fffffff); + System.out.println(result); + System.out.println("test_le1 FAILED"); + System.exit(1); + } + catch (ArithmeticException e1) + { + System.out.println("test_le1: Expected exception caught"); + if (result != -9039) + { + System.out.println(result); + System.out.println("test_le1 FAILED"); + System.exit(97); + } + } + System.out.println("test_le1 WORKED"); + + result=0; + r = test_wrap1(0x7fffffff); + if (r != 4) + { + System.out.println(result); + System.out.println("test_wrap1 FAILED"); + System.exit(97); + } + else + { + System.out.println("test_wrap1 WORKED"); + } + + result=0; + r = test_rce5(box5,0x80000100); + if (result != 3) + { + System.out.println(result); + System.out.println("test_rce5 FAILED"); + System.exit(97); + } + else + { + System.out.println("test_rce5 WORKED"); + } + + result=0; + r = test_rce6(box6,0x80000100); + if (result != 6) + { + System.out.println(result); + System.out.println("test_rce6 FAILED"); + System.exit(97); + } + else + { + System.out.println("test_rce6 WORKED"); + } + + result=0; + r = test_rce7(box7); + if (result != 14680079) + { + System.out.println(result); + System.out.println("test_rce7 FAILED"); + System.exit(97); + } + else + { + System.out.println("test_rce7 WORKED"); + } + + result=0; + r = test_rce8(box8); + if (result != 16393) + { + System.out.println(result); + System.out.println("test_rce8 FAILED"); + System.exit(97); + } + else + { + System.out.println("test_rce8 WORKED"); + } + } +} diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6186134.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6186134.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6186134 + * @summary Server virtual machine produces/exeutes incorrect code. + * + * @run main Test6186134 100000 + */ +import java.util.ArrayList; + +public class Test6186134 { + + int num = 0; + + public Test6186134(int n) { + num = n; + } + + public boolean more() { + return num-- > 0; + } + + public ArrayList test1() { + ArrayList res = new ArrayList(); + int maxResults = Integer.MAX_VALUE; + int n = 0; + boolean more = more(); + while ((n++ < maxResults) && more) { + res.add(new Object()); + more = more(); + } + return res; + } + + public static void main(String[] pars) { + int n = Integer.parseInt(pars[0]); + for (int i=0; i= 0) { + i1++; + if (i1 > i2) { + System.out.println("E R R O R: " + i1); + System.exit(97); + } + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6357214.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6357214.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,179 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6357214 + * @summary Hotspot server compiler gets integer comparison wrong + * + * @run main/othervm/timeout=60 -DshowAll=ffo -DeventID=444 Test6357214 + */ + +// The test hangs after few iterations before the fix. So it fails if timeout. +class MyResult { + public boolean next() { + return true; + } + + public String getString(String in) { + if (in.equals("id")) + return "idFoo"; + if (in.equals("contentKey")) + return "ckFoo"; + return "Foo"; + } + + public int getInt(String in) { + if (in.equals("processingComplete")) + return 0; + return 1; + } + + public byte[] getBytes(String in) { + byte[] arr = null; + if (in.equals("content")) { + arr = new byte[65536]; + byte j = 32; + for (int i=0; i<65536; i++) { + arr[i] = j; + if (++j == 127) + j=32; + } + } + return arr; + } +} + +public class Test6357214 { + public static volatile boolean bollocks = true; + public String create(String context) throws Exception { + + // + // Extract HTTP parameters + // + + boolean showAll = System.getProperty("showAll") != null; + String eventID = System.getProperty("eventID"); + String eventContentKey = System.getProperty("cKey"); + // + // Build ContentStaging query based on eventID or eventContentKey + // + + String sql = "select id, processingComplete, contentKey, content " + + "from ContentStaging cs, ContentStagingKey csk " + + "where cs.eventContentKey = csk.eventContentKey "; + + if (eventID != null) { + sql += "and id = " + eventID; + } + else if (eventContentKey != null) { + sql += "and cs.eventContentKey = '" + + eventContentKey + + "' having id = max(id)"; + } + else { + throw new Exception("Need eventID or eventContentKey"); + } + + // + // This factory builds a static panel, there is no JSP + // + + StringBuffer html = new StringBuffer(); + + try { + + MyResult result = new MyResult(); + if (result.next()) { + + eventID = result.getString("id"); + int processingComplete = result.getInt("processingComplete"); + String contentKey = result.getString("contentKey"); + byte[] bytes = result.getBytes("content"); + + // + // Print content status and associated controls + // + + html.append("
"); + html.append("Status: "); + switch (processingComplete) { + case 0 : + case 1 : html.append("PENDING"); break; + case 2 : html.append(contentKey); break; + case 3 : html.append(eventID); break; + default : html.append("UNKNONW"); + } + html.append("
"); + + // + // Print at most 20Kb of content unless "showAll" is set + // + + int limit = showAll ? Integer.MAX_VALUE : 1024 * 20; + System.out.println(limit); + html.append("
");
+                for (int i = 0; bytes != null && i < bytes.length; i++) {
+                    char c = (char) bytes[i];
+                    switch (c) {
+                        case '<' : html.append("<");  break;
+                        case '>' : html.append(">");  break;
+                        case '&' : html.append("&"); break;
+                        default  : html.append(c);
+                    }
+
+                    if (i > limit) {
+                        while (bollocks);
+                        // System.out.println("i is " + i);
+                        // System.out.println("limit is " + limit);
+                        html.append("...\n
"); + html.append(eventID); + html.append("
");
+                        break;
+                    }
+                }
+                html.append("
"); + } + } + catch (Exception exception) { + throw exception; + } + finally { + html.append("Oof!!"); + } + String ret = html.toString(); + System.out.println("Returning string length = "+ ret.length()); + return ret; + } + + public static void main(String[] args) throws Exception { + int length=0; + + for (int i = 0; i < 100; i++) { + length = new Test6357214().create("boo").length(); + System.out.println(length); + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6559156.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6559156.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,81 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6559156 + * @summary Server compiler generates bad code for "<= Integer.MAX_VALUE" expression + * + * @run main Test6559156 + */ + +public class Test6559156 { + + static final int N_TESTS = 1000000; + + public static void main(String[] args) throws Exception { + + /* + * If MAX_VALUE is changed to MAX_VALUE - 1 below, the test passes + * because (apparently) bad code is only generated when comparing + * <= MAX_VALUE in the doTest method. + */ + Test6559156 test = new Test6559156(); + for (int i = 0; i < N_TESTS; i += 1) { + test.doTest1(10, Integer.MAX_VALUE, i); + test.doTest2(10, Integer.MAX_VALUE, i); + } + System.out.println("No failure"); + } + + void doTest1(int expected, int max, int i) { + int counted; + for (counted = 0; + (counted <= max) && (counted < expected); + counted += 1) { + } + if (counted != expected) { + throw new RuntimeException("Failed test1 iteration=" + i + + " max=" + max + + " counted=" + counted + + " expected=" + expected); + } + } + + void doTest2(int expected, int max, int i) { + int counted; + for (counted = 0; + // change test sequence. + (counted < expected) && (counted <= max); + counted += 1) { + } + if (counted != expected) { + throw new RuntimeException("Failed test1 iteration=" + i + + " max=" + max + + " counted=" + counted + + " expected=" + expected); + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6753639.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6753639.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6753639 + * @summary Strange optimisation in for loop with cyclic integer condition + * + * @run main/othervm -Xbatch Test6753639 + */ + +public class Test6753639 { + public static void main(String[] args) throws InterruptedException { + int END = Integer.MAX_VALUE; + int count = 0; + for(int i = Integer.MAX_VALUE - 5; i <= END; i++) { + count++; + if (count > 100000) { + System.out.println("Passed"); + System.exit(95); + } + } + System.out.println("broken " + count); + System.out.println("FAILED"); + System.exit(97); + } +} + + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6850611.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6850611.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6850611 + * @summary int / long arithmetic seems to be broken in 1.6.0_14 HotSpot Server VM (Win XP) + * + * @run main Test6850611 + */ + +public class Test6850611 { + + public static void main(String[] args) { + test(); + } + + private static void test() { + for (int j = 0; j < 5; ++j) { + long x = 0; + for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; ++i) { + x += i; + } + System.out.println("sum: " + x); + if (x != -4294967295l) { + System.out.println("FAILED"); + System.exit(97); + } + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6890943.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6890943.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,189 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6890943 + * @summary JVM mysteriously gives wrong result on 64-bit 1.6 VMs in hotspot mode. + * + * @run shell Test6890943.sh + */ +import java.util.*; +import java.io.*; +import java.util.regex.*; + +public class Test6890943 { + public static final boolean AIR = true, ROCK = false; + public static void main(String[] args) { + new Test6890943().go(); + } + + int r, c, f, t; + boolean[][] grid; + + public void go() { + Scanner s = new Scanner(System.in); + s.useDelimiter("\\s+"); + int T = s.nextInt(); + for (t = 0 ; t < T ; t++) { + r = s.nextInt(); c = s.nextInt(); f = s.nextInt(); + grid = new boolean[r][c]; + for (int x = 0 ; x < r ; x++) { + String line = s.next(); + for (int y = 0 ; y < c ; y++) grid[x][y] = line.charAt(y) == '.'; + } + int digs = solve(); + String res = digs == -1 ? "No" : "Yes " + digs; + System.out.printf("Case #%d: %s\n", t+1, res); + } + } + + Map M = new HashMap(); + + private int solve() { + M = new HashMap(); + M.put(calcWalkingRange(0, 0), 0); + for (int digDown = 0 ; digDown < r ; digDown++) { + Map tries = new HashMap(); + for (Map.Entry m : M.entrySet()) { + int q = m.getKey(); + if (depth(q) != (digDown)) continue; + if (stuck(q)) continue; + tries.put(q, m.getValue()); + } + + for (Map.Entry m : tries.entrySet()) { + int q = m.getKey(); + int fallLeftDelta = 0, fallRightDelta = 0; + //fall left + int fallLeft = fall(digDown, start(q)); + if (fallLeft > 0) { + fallLeftDelta = 1; + if (fallLeft <= f) addToM(calcWalkingRange(digDown+fallLeft, start(q)), m.getValue()); + } + + //fall right + int fallRight = fall(digDown, end(q)); + if (fallRight > 0) { + fallRightDelta = 1; + + if (fallRight <= f) addToM(calcWalkingRange(digDown+fallRight, end(q)), m.getValue()); + } + + for (int p = start(q) + fallLeftDelta ; p <= end(q) - fallRightDelta ; p++) { + //goLeft + for (int digSpot = p ; digSpot > start(q) +fallLeftDelta ; digSpot--) { + int fallDown = 1+fall(digDown+1, digSpot); + if (fallDown <= f) { + if (fallDown == 1) { + addToM(calcWalkingRange(digDown + 1, digSpot, digSpot, p), m.getValue() + Math.abs(digSpot-p)+1); + } else { + addToM(calcWalkingRange(digDown + fallDown, digSpot), m.getValue() + Math.abs(digSpot-p)+1); + } + } + } + + //goRight + for (int digSpot = p ; digSpot < end(q)-fallRightDelta ;digSpot++) { + int fallDown = 1+fall(digDown+1, digSpot); + if (fallDown <= f) { + if (fallDown == 1) { + addToM(calcWalkingRange(digDown + 1, digSpot, p, digSpot), m.getValue() + Math.abs(digSpot-p)+1); + } else { + addToM(calcWalkingRange(digDown + fallDown, digSpot), m.getValue() + Math.abs(digSpot-p)+1); + } + } + } + } + } + } + + int result = Integer.MAX_VALUE; + for (Map.Entry m : M.entrySet()) { + if (depth(m.getKey()) == r-1) result = Math.min(m.getValue(), result); + } + + if (result == Integer.MAX_VALUE) return -1; + return result; + } + + private void addToM(int q, int i) { + Integer original = M.get(q); + if ( original == null ) M.put(q, i); + else M.put(q, Math.min(original, i)); + } + + private int fall(int row, int column) { + int res = 0; + for ( int p = row+1 ; p < r ; p++) { + if (grid[p][column] == AIR) res++; + else break; + } + return res; + } + + private boolean stuck(int q) { + return start(q) == end(q); + } + + private int depth(int q) { + return q % 50; + } + + private int start(int q) { + return q / (50*50); + } + + private int end(int q) { + return (q / 50) % 50; + } + + private int calcWalkingRange(int depth, int pos) { + return calcWalkingRange(depth, pos, Integer.MAX_VALUE, Integer.MIN_VALUE); + } + + private int calcWalkingRange(int depth, int pos, int airOverrideStart, int airOverrideEnd) { + int left = pos, right = pos; + if (depth >= r) return (c-1)*50 + depth; + + while (left > 0) { + if (grid[depth][left-1] == ROCK && (left-1 < airOverrideStart || left-1 > airOverrideEnd)) break; + if (depth < r-1 && grid[depth+1][left-1] == AIR) { + left--; + break; + } + left--; + } + while (right < c-1) { + if (grid[depth][right+1] == ROCK && (right+1 < airOverrideStart || right+1 > airOverrideEnd)) break; + if (depth < r-1 && grid[depth+1][right+1] == AIR) { + right++; + break; + } + right++; + } + + return left *50*50 + right*50 + depth; + } +} diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6890943.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6890943.sh Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,67 @@ +#!/bin/sh +# +# Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. +# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. +# +# This code is free software; you can redistribute it and/or modify it +# under the terms of the GNU General Public License version 2 only, as +# published by the Free Software Foundation. +# +# This code is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +# version 2 for more details (a copy is included in the LICENSE file that +# accompanied this code). +# +# You should have received a copy of the GNU General Public License version +# 2 along with this work; if not, write to the Free Software Foundation, +# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. +# +# Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA +# or visit www.oracle.com if you need additional information or have any +# questions. +# +# + +if [ "${TESTSRC}" = "" ] +then + echo "TESTSRC not set. Test cannot execute. Failed." + exit 1 +fi +echo "TESTSRC=${TESTSRC}" +if [ "${TESTJAVA}" = "" ] +then + echo "TESTJAVA not set. Test cannot execute. Failed." + exit 1 +fi +echo "TESTJAVA=${TESTJAVA}" +if [ "${TESTCLASSES}" = "" ] +then + echo "TESTCLASSES not set. Test cannot execute. Failed." + exit 1 +fi +echo "TESTCLASSES=${TESTCLASSES}" +echo "CLASSPATH=${CLASSPATH}" + +set -x + +cp ${TESTSRC}/Test6890943.java . +cp ${TESTSRC}/input6890943.txt . +cp ${TESTSRC}/output6890943.txt . +cp ${TESTSRC}/Test6890943.sh . + +${TESTJAVA}/bin/javac -d . Test6890943.java + +${TESTJAVA}/bin/java ${TESTVMOPTS} Test6890943 < input6890943.txt > test.out 2>&1 + +diff output6890943.txt test.out + +result=$? +if [ $result -eq 0 ] +then + echo "Passed" + exit 0 +else + echo "Failed" + exit 1 +fi diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6897150.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6897150.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6897150 + * @summary Hotspot optimises away a valid loop + * + * @run main Test6897150 + */ + +// Should be compiled with javac from JDK1.3 to get bytecode which shows the problem. +public class Test6897150 { + public static void main(String[] args) { + // This works + loopAndPrint(Integer.MAX_VALUE -1); + // This doesn't + loopAndPrint(Integer.MAX_VALUE); + } + + static void verify(int max, int a) { + if ( a != (max - 1)) { + System.out.println("Expected: " + (max - 1)); + System.out.println("Actual : " + a); + System.exit(97); + } + } + static void loopAndPrint(int max) { + int a = -1; + int i = 1; + for (; i < max; i++) { + a = i; + } + verify(max, a); + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6905845.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6905845.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,76 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6905845 + * @summary Server VM improperly optimizing away loop. + * + * @run main Test6905845 + */ + +public class Test6905845 { + + public static void main(String[] args){ + for (int asdf = 0; asdf < 5; asdf++){ + //test block + { + StringBuilder strBuf1 = new StringBuilder(65); + long start = System.currentTimeMillis(); + int count = 0; + + for (int i = Integer.MIN_VALUE; i < (Integer.MAX_VALUE - 80); i += 79){ + strBuf1.append(i); + count++; + strBuf1.delete(0, 65); + } + + System.out.println(count); + if (count != 54366674) { + System.out.println("wrong count: " + count +", should be 54366674"); + System.exit(97); + } + } + //test block + { + StringBuilder strBuf1 = new StringBuilder(65); + long start = System.currentTimeMillis(); + int count = 0; + + for (int i = Integer.MIN_VALUE; i < (Integer.MAX_VALUE - 80); i += 79){ + strBuf1.append(i); + count++; + strBuf1.delete(0, 65); + } + + System.out.println(count); + if (count != 54366674) { + System.out.println("wrong count: " + count +", should be 54366674"); + System.exit(97); + } + } + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6931567.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6931567.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,62 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6931567 + * @summary JIT Error (on class file compiled with eclipse) on JVM x64 (but not on x32!). + * + * @run main Test6931567 + */ + +// Should be compiled with javac from JDK1.3 to get bytecode which shows the problem. +public class Test6931567 { + + public static void main(final String[] args) { + booleanInvert(Integer.MAX_VALUE); + booleanInvert(Integer.MAX_VALUE - 1); + } + + private static void booleanInvert(final int max) { + boolean test1 = false; + boolean test2 = false; + + for (int i = 0; i < max; i++) { + test1 = !test1; + } + + for (int i = 0; i < max; i++) { + test2 ^= true; + } + + if (test1 != test2) { + System.out.println("ERROR: Boolean invert\n\ttest1=" + test1 + + "\n\ttest2=" + test2); + System.exit(97); + } else { + System.out.println("Passed!"); + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6935022.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6935022.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,74 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6935022 + * @summary Server VM incorrectly breaks out of while loop + * + * @run main Test6935022 + */ + +public class Test6935022 { + public static final void main(String[] args) throws Exception { + Test6935022 test = new Test6935022(); + + int cnt = 0; + + while (cnt < 10000) { + try { + ++cnt; + if ((cnt&1023) == 0) + System.out.println("Thread="+Thread.currentThread().getName() + " iteration: " + cnt); + test.loop(2147483647, (cnt&1023)); + } + + catch (Exception e) { + System.out.println("Caught on iteration " + cnt); + e.printStackTrace(); + System.exit(97); + } + } + } + + private void loop(int endingRow, int mask) throws Exception { + int rows = 1; + boolean next = true; + + while(rows <= endingRow && next) { + rows++; + if (rows == mask) + System.out.println("Rows="+rows+", end="+endingRow+", next="+next); + next = next(rows); + } + + if (next) + throw new Exception("Ended on rows(no rs): " + rows); + } + + private boolean next(int rows) { + return rows < 12; + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6959129.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6959129.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,90 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6959129 + * @summary COMPARISON WITH INTEGER.MAX_INT DOES NOT WORK CORRECTLY IN THE CLIENT VM. + * + * @run main/othervm -ea Test6959129 + */ + +public class Test6959129 { + + public static void main(String[] args) { + long start = System.currentTimeMillis(); + int min = Integer.MAX_VALUE-30000; + int max = Integer.MAX_VALUE; + long maxmoves = 0; + try { + maxmoves = maxMoves(min, max); + } catch (AssertionError e) { + System.out.println("Passed"); + System.exit(95); + } + System.out.println("maxMove:" + maxmoves); + System.out.println("FAILED"); + System.exit(97); + } + /** + * Imperative implementation that returns the length hailstone moves + * for a given number. + */ + public static long hailstoneLengthImp(long n) { + long moves = 0; + while (n != 1) { + assert n > 1; + if (isEven(n)) { + n = n / 2; + } else { + n = 3 * n + 1; + } + ++moves; + } + return moves; + } + + private static boolean isEven(long n) { + return n % 2 == 0; + } + + /** + * Returns the maximum length of the hailstone sequence for numbers + * between min to max. + * + * For rec1 - Assume that min is bigger than max. + */ + public static long maxMoves(int min, int max) { + long maxmoves = 0; + for (int n = min; n <= max; n++) { + if ((n & 1023) == 0) System.out.println(n); + long moves = hailstoneLengthImp(n); + if (moves > maxmoves) { + maxmoves = moves; + } + } + return maxmoves; + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6985295.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6985295.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6985295 + * @summary JVM fails to evaluate condition randomly + * + * @run main/othervm -Xbatch Test6985295 + */ + +public class Test6985295 { + + public static void main(String[] args) { + int min = Integer.MAX_VALUE-50000; + int max = Integer.MAX_VALUE; + System.out.println("max = " + max); + long counter = 0; + int i; + for(i = min; i <= max; i++) { + counter++; + if (counter > 1000000) { + System.out.println("Passed"); + System.exit(95); + } + } + System.out.println("iteration went " + counter + " times (" + i + ")"); + System.out.println("FAILED"); + System.exit(97); + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test6992759.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test6992759.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 6992759 + * @summary Bad code generated for integer <= comparison, fails for Integer.MAX_VALUE + * + * @run main Test6992759 + */ + +public class Test6992759 { + + static final int N_TESTS = 1000000000; + + public static void main(String[] args) throws Exception { + + /* + * If MAX_VALUE is changed to MAX_VALUE - 1 below, the test passes + * because (apparently) bad code is only generated when comparing + * <= MAX_VALUE in the doTest method. + */ + Test6992759 test = new Test6992759(); + for (int i = 0; i < N_TESTS; i += 1) { + test.doTest(10, Integer.MAX_VALUE, i); + //test.doTest(10, Integer.MAX_VALUE - 1, i); + } + System.out.println("No failure"); + } + + void doTest(int expected, int max, int i) { + int counted; + for (counted = 0; + (counted <= max) && (counted < expected); + counted += 1) { + } + if (counted != expected) { + throw new RuntimeException("Failed test iteration=" + i + + " max=" + max + + " counted=" + counted + + " expected=" + expected); + } + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test7005594.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test7005594.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 7005594 + * @summary Array overflow not handled correctly with loop optimzations + * + * @run main/othervm -Xms2048m -Xcomp -XX:CompileOnly=Test7005594.test Test7005594 + */ + +public class Test7005594 { + + static int test(byte a[]){ + int result=0; + for( int i=0; i>1)+1) ){ + result += a[i]; + } + return result; + } + + public static void main(String [] args){ + byte a[]=new byte[(0x7fffffff>>1)+2]; + int result = 0; + try { + result = test(a); + } catch (ArrayIndexOutOfBoundsException e) { + e.printStackTrace(System.out); + System.out.println("Passed"); + System.exit(95); + } + System.out.println(result); + System.out.println("FAILED"); + System.exit(97); + } + +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/Test7020614.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/Test7020614.java Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +/** + * @test + * @bug 7020614 + * @summary "-server" mode optimizer makes code hang + * + * @run main/othervm/timeout=30 -Xbatch Test7020614 + */ + +public class Test7020614 { + + private static final int ITERATIONS = 1000; + private static int doNotOptimizeOut = 0; + + public static long bitCountShort() { + long t0 = System.currentTimeMillis(); + int sum = 0; + for (int it = 0; it < ITERATIONS; ++it) { + short value = 0; + do { + sum += Integer.bitCount(value); + } while (++value != 0); + } + doNotOptimizeOut += sum; + return System.currentTimeMillis() - t0; + } + + public static void main(String[] args) { + for (int i = 0; i < 4; ++i) { + System.out.println((i + 1) + ": " + bitCountShort()); + } + System.out.println("doNotOptimizeOut value: " + doNotOptimizeOut); + } +} + diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/input6890943.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/input6890943.txt Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,1543 @@ +50 +4 5 1 +..... +##### +..### +.#... +4 5 1 +..... +##### +###.. +...#. +5 4 2 +.... +#### +..## +.### +.#.# +6 10 5 +.......... +####.##### +####.##### +####.##### +####.##### +####.##### +6 10 4 +.......... +#....##### +#....##### +#....##### +#....##### +#....##### +6 10 1 +.......... +####.##### +####.##### +####.##### +####.##### +####.##### +6 10 2 +.......... +####.##### +####.##### +####.##### +####.##### +####.##### +6 11 2 +.....###### +########### +###.......# +###.#.#...# +###.#.##..# +###.#.###.# +6 11 1 +.....###### +########### +###.......# +###.#.#...# +###.#.##..# +###.#.###.# +6 11 2 +.......#### +########### +###.......# +###.#.#...# +###.#.##..# +###.#.###.# +7 11 1 +..#........ +##.#....... +###.#...... +####.#..... +#####.#.... +######.#... +#########.. +13 16 2 +................ +#.#.#.#.#.#.#.#. +................ +.#.#.#.#.#.#.#.# +................ +#.#.#.#.#.#.#.#. +................ +.#.#.#.#.#.#.#.# +................ +#.#.#.#.#.#.#.#. +................ +.#.#.#.#.#.#.#.# +................ +4 16 3 +................ +#.#.#.#.#.#.#.#. +.#.#.#.#.#.#.#.# +................ +50 50 1 +.................................................. +################################################.# +.#............#....#.......................#....## +..#.....#......#....#.....................#....#.. +...#.......#....#....#...................#....#... +#...#....#.......#....#.................#....#.... +##...#.......#....#....#...............#....#..... +###...#....#.......#....#.............#....#...... +####...#.......#....#....#...........#....#....... +.####...#....#.......#....#.........#....#........ +..####...#.......#....#....#.......#....#......... +...####...#....#.......#....#.....#....#.......... +....####...#.......#....#....#...#....#...###..... +.....####...#....#.......#....#.#....#..##..###... +......####...#.......#....#....#.............##... +.......####...#....#.......#...............##..... +........####...#.......#....#............##....... +.........####...#....#.......#.........#######.... +..###.....####...#.......#....#................... +.#..###....####...#....#.......#.........####..... +##...###....####...#.......#....#.......##..##.... +##...........####...#....#.......#......##..##.... +##..####......####...#.......#....##....##..##.... +##....##.......####...#....#......##....##..##.... +.###.##.........####.............##.....##..##.... +..###............#######........##.......####..... +.........###......######.......##................. +.......##..##..........#......##.........####..... +......##....##........#......##.........##..##.... +......##.............#......##..........##..##.... +......##............#......##...........##..##.... +......##....#......#......##............##..##.... +.......##..##.....#....########.........##..##.... +........####.....#.....###.#...#.........####..... +.#####..........#.....#..##.#...#................. +...##..........#.....#....##.#...#.........####... +...##.........#.....#..#...##.#...#.......##..##.. +...##........#.....#..##....##.#...#......##..##.. +...##.......#.....#....##....##.#...#.....##..##.. +##.##......#.....#...###......##.#...#.....#####.. +.###......#.....#..##..........##.#...#.......##.. +.........#.....#...##..####.....##.#...#.....##... +........#.....#...###..#.##......##.#...#...##.... +.......#.....#....##.....###......##.#...#........ +......#.....#..#.##...###..........##.#...#....... +.....#.....#...##..#..#..##.##.#....##.#...#...... +....#.....#........###.....##........##.#...#..... +...#.....#.......##...####..###.......##.#...#.... +..#.....#......##.#.#..#.#..##.........##.#...#... +.#..............#.#.#.#.#.#.#...........##.#...#.. +50 50 13 +.................................................. +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +################################################## +20 49 5 +................................................. +################################################# +################################################# +##################################.############## +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +############################.#################### +################################################# +######.########################################## +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +49 49 48 +................................................. +################################################# +################################################. +################################################# +####################################.############ +################################################# +##########.###################################### +#######.######################################### +################################################# +################################################# +################################################# +#######################################.######### +################################################# +################################################# +################################################# +################################################# +################################################# +###########################################.##### +################################################# +################################################# +###.############################################# +###############.################################# +################################################# +##.############################################## +################################################# +################################################# +################################################# +################################################# +################################################# +#####################################.########### +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +#####.########################################### +#####################.########################### +################################################# +###.############################################# +################################################# +################################################# +################################################# +#############.###########.####################### +###.##############.####.######################### +#########################################.####### +################################################# +########################################.######## +40 49 10 +................................................. +################################################# +..#..............#............................... +.......................#.......................#. +..#....#...................#.................#... +..........#...............................#...... +............#..................#.......#......... +........#............#............#.............. +...................#.....#....................... +....#..........#........................#........ +....#.................................#......#... +...........#..................................... +....................#............................ +.##........#................#.................... +..............#.................................. +........#......................................#. +.................................#....#........#. +................................................. +.............................#..##............... +...........................................#.#... +........#..........#........#.............#.....# +..........#.#.................................... +.............................#............#...... +.......#.......................#.........#....... +..............................#.................. +......#.......................................... +.............#................#.................. +......#.............................#............ +#.................#..................#......#.... +..............#.................................. +...........#...........................#.....#... +............#............#...#................... +.......................#.......................#. +............................#.................... +..........................#...................... +...........................#.............#...#... +.#............................................... +..................#.............................. +...#..............................#.............. +.....#..................#........................ +49 49 20 +.........................................##..#..# +########################################.##...#.# +#.##..#....#####..####...#..#.##.###.#..#..#..... +..#...#.##...##.#....#...##..#.#..###...###...... +..#..##.#.###......#.....##.....#.......##.#.#.#. +..##......###.#.##.....##.#..#.##.###..##.#.##### +#.#.##....#..#..#.....#.#.##.#.#.##.#.....###.#.# +..###.#..#..###...###..#.#.....#..######.#.#....# +..#...#...##.#..##.#.#.#..###.#..#..#...#....##.. +.#..#.#..##.#...##........##.##..#..........#.#.. +#.#.###.####...#.#...#..###..#.##....#........... +#..#.#######.#....#.#.##...#.#.............##.... +###..###....#..#....#.#.###...#..##.#.#..##.##### +....####...#.#...........##.#.#.#..#.#.#.##.#.#.. +##.#...##..#..#...#..##..####.##.#...#.....#...#. +...###.##.#..##.....#.#.##..#..###.#.###.#.#..#.# +###....##...#.#.##.##..#.#...#...##....#.###..... +##..#....###..#.....#..#....#.#.#.##.......##.### +.#.#....#.....####..##....##...##...#.##..##.#... +##....#....#.#.###.##...#..##.##...##....#.###### +..#....#..##.....##.##.#.........##..##...#.#.... +#..#..#.#....##.#.#...#.###..#...#..#.##.#.#....# +.....#..#...###.....##...###....###.##.....#...#. +#..#.#...###..#....#..####....#.#......#..##....# +.....#.#...###...###.#..#.#.#.........#.#.#..#.## +.#..##..##..#..#.#....##.........#..#.##.#..##... +##.#.#.....##.##..###...#.#.#..#.#.####.#.###.#.. +..#.#.......#.#.#...#####..#.##.#....#...#.#..... +..########.####.....#..#.........#..#####.##.#... +.#......##.####..###..#.####........#....#....#.# +#.....#....#...#...#..###......#.##..#..#...#.### +...#..###.....#....#..#..#......#.....#.#.#.#..## +....#.##..####.#..###...#...#...#######..#..#.... +.#..#...##...#...#......##...#####.##...#..##.... +..#.#.#######.#....#.#.###....#.##...#..#.##..#.. +#..#.##.#.#.##..###....#.##.#..#..#...##....##..# +.###.#.#..##.###...#..##.#.#...#.#.####....#..### +#.#......#...##.##...#.#.....##..#..##....#.##... +#.#...#.#.##...##.###.#..##..##..####..##.#.#...# +....#....#..####.##.....#.#....#..##..##....#..#. +....#...###.....##..#..###....#........###..##..# +.###....##...........#....#........####.#.####..# +.#........##...#.###..###.#...##.##..###..###..## +#.#######.#....###...#..##..#...#....##....#....# +#....#..#......#..#...##.....##.#.#.#..#......##. +#.##.##.#.#.##..#..##..######.##.###.#.#..#....#. +.###.##.....#.##.#..###....###..##....#.#..#..... +#####..#.#....#.#......##..##.#...........####.#. +..#..#.#..#...##....###.##.#.#...#..#..#....#..## +49 49 5 +.........................................#....### +#########################################..#..... +.....#.###...#...#...........##...#...#....#...#. +....#.....#..#....#....##...#..###.#...#..##.#.## +....#...###.##...........#.#.##.......#.#.#.#..#. +...........#..###..#..##.....#.........#.....#... +.....#......#.##.#..##.###.....#...###.#....#...# +.#......##.#.......##...##.....###..#......#.##.. +#.....#.#..#.#...#####...#.###.##.....#..#....... +........##....#....#....#.#.#....####....#.##.### +....#.#......#.##.....#..........##.............# +#..##....#.#....#..#.....#.#.#....#.#.#....##...# +...#..##..#...#....#.#....#..#....#..#..#.......# +......#...##.#.####.....####.###.#..#........#### +##..........#...........#..#.##......##......#.## +....###....##...#.####.....#............#..#..... +...#....#....##.....##.....#.#.....#..#.#..#..#.. +...........#...#.##..##..##.#......#..#.#..##.... +.#........##......#.........##..#..........#.#... +#....##.#.##..#.....#.....##.....##....#......... +.#.......###.......#..#.....#.....#..##.##...#..# +###......##.....##...##..#.#....#...####.##...... +....#..#....##...#.##.##.#.#...#...#.#..#.##.#..# +..........#.#..#####..####....##..#.#.#.........# +........##.#.###..###....#...#........##.#......# +...........##.##..#.....#.#.#..#....#.###..#.###. +#.#....#.#...##............#.#.....#....#...#.#.. +..###.#.##...#....#..##.##...#........#.......... +...........#...##...#..#..##.....#..#.......#..#. +#.#.#......##.#.....#...#.#.#.#...#..#######.#.## +...##..#.......###..#..#.##....#......####.#..... +....##......#.#......#....##..#...##.......#..#.. +#..###.##....##..##.#..#.###.##.....#...#........ +#......#....####....#.........#.........#.##.##.. +.#.#..###......#...##.#.##..#.#.....#...#.#...... +......#.#...##.#....#..#.#.......#.#.....#.#.###. +###..#.....#....#.#...##..#.#.....#.#.....#.#.#.. +..........#........#....#...#..#...#...#.#.#.#... +#..##..#...###....#.#..#....##....#...#..##....#. +.#.#.#....#..##.#...#.....#.##..#....##........#. +..#.##....###...#...#..#..#.....#..#..###..#...#. +##....#........#..#..#..#......#...#.##....#.#.## +....#.............#..#...#...#.#.#...##....#..#.# +...#.........#....###.....#.#..#..#...#..#...#... +.#.#.###..###..##.#.##...#...#..#................ +.#......#..#..#.#.#...#.....................#..#. +..#.....#.......#..##.......#...#...##.#.....#.#. +#..####.#....#......#.........#.#...###...#....#. +#.#.#.#....#......#..#.#........###..#....##..... +31 47 7 +.........................#.#..##.#..#...#.#...# +#########################.#.#...#...#.#........ +...#...........#...#...#...##...#..#.#.#...#.## +.#........#.......#.#.....#......#........#.... +#.#....###...#...#....#....#......##...#....... +#.#......##..##...#.....#.##.#.........#....... +.......#.....##........#..#.......#.##...#..... +..#.......##.#...#.#..#.#..#....#......#......# +#.##.........#####..###.......#........#......# +.#..#.#.#...#....####...#...........#....#..... +##..##..#..###..###....##......#....#..##...#.# +#......#........##...#.#.#..#..#....#..#...##.# +.#.#.##..........#.#..#...##.##................ +##.##.#...#....#.............#.#.....###...#.#. +..#..#.#..#..#.#....#....#............#.##..#.. +......###......#..##..#.#...##.........#.#.###. +..#.##.#..#......##....#.#........#....##..#..# +.........#.#.#.....##...#.#...#.##.....##.##... +.#........#...#.###.........#.#.#.............. +....##........#.....#....###....###.#..#....##. +..#..#....#....#.#.......#.#.#..........###.... +.#..###.#...#.###...##...#....#...#............ +##.....#..##.#.##.##.......#.##.....###...##.#. +.###.......#...#.....#.....###.........#...#... +#.....#..####.....##...#........####..........# +#..#...........##.#.#.#..............#....##... +..#.#..........#..##.#.##...##..##.#.#..##..#.. +#..........................###......#....##.... +.....#..........#..#......#...#.#..#....#...#.. +#......#....##.........#..#.......#..#.......#. +.#......#...###...##....##.#..........#...#..#. +44 35 13 +...........................##..#### +############################.....## +..###.#.##.#...#.##.####.###.###.## +#.##.#.#.#.#..###.#..#...###.##..## +.#.##.#.##..#.###.###.##.#.#...#.#. +##....##.#..#####.#.####..##.##...# +####.##..##.###.##.#.#...#.##.###.# +#.#######.#.#.#..#.#..#..#...###.#. +##.###.#..#.####.##.#.#########.##. +#.##.#######..#.#.####.#..#..###### +.#.##..########...##.###..#..##.##. +#.#######.###...##.#...#.####.#..#. +.###..###....#.#.##.###..##.##.##.# +...#.###.#.##.#.####.##.####.#.#... +#..#......##....#.##.#.#.###.#..#.. +...##.###.###.#.####..#.#.#..###.#. +.#####.#..#..##.#.#...##.#.#.##...# +..##..#.#....##.#.#.###.##.##...#.. +###.#..###....#######..#.#.###.##.# +##.##.#.#.##..#.#.#.#.#..##.####... +##.###...#.###.#.#.#..#####.###.#.. +...#.#...##......#.##..##.##.#.#.## +##..#..####..###...###.#........### +##..#....#..#.#..##.#####..###.#... +##...#.#####.###.##....###...####.. +#.####.#..#.##.#.#...#.###.#...##.. +####.#####.###.#.##...##...#...#.## +#..##.##....###..#..####.##..#.#.## +..#.###.##....####.##.#..###.#....# +#.#.###.#..#.##.##...###.##..###### +##.#.##.###.#..#...###.####..##.### +.########.#....#..#........#..##..# +####..#.##.#.##.####..#.###...##### +#..##..#..##.###....####.#.#...#.#. +.#...##.##.###.###...##..##..###... +###.##...#.##...####.#.#.##..#.#### +##.###..##.#....#.###..##.#...###.# +##..##.###..#..#.####.#.....##.#### +.#....##...#####.....####...#.##.#. +##.#.#.....##...#..#...#....#....## +#..#.#..#####.##..###.#.########### +.#.###.#..###.##.###.#.###.##.#.### +.###..####.#..##......#..##.######. +...##..###.#.....##.#.#..##......#. +6 10 2 +.......#.. +########## +##.#...#.. +.#..###... +#.##.##### +.####..#.# +7 9 4 +......##. +######### +.#.###.## +..#...#.. +.....##.# +####...## +.#..#.#.# +10 9 2 +......... +######### +..###.### +#..###.## +.....#.#. +..##..... +###.#.... +.##..#... +##...#..# +#..##..## +10 7 1 +....#.. +####..# +####..# +..#.#.. +...##.# +#....## +..#..## +#.#.... +.##.#.. +###...# +6 10 2 +.......#.. +#######.#. +..##.#.##. +..#..#.... +.#.#....## +..#....#.. +40 40 5 +........................................ +###############################..####### +#..##############.....################## +........................................ +...........................##########... +#####...################..############## +##################.##################### +.............................#####...... +#.............................########## +...............................####..... +.........#################.............. +..........................###........... +........................................ +....................#####............... +##########....................########## +.......##################............... +########........###############..####### +........................................ +..........#########################..... +#####................................... +.........................####........... +......................#####...######.... +######..................################ +........#########....................... +############.........................### +........####################............ +......................################## +....................######......#....... +............################............ +........................................ +......................#########......... +#######............##################### +........###############................. +........................................ +.........###################............ +.............................#.......... +######................................## +........................#############... +......##................................ +........................................ +30 20 11 +.................... +#################### +......##.##......... +#.....####....###### +...##............... +........#######.###. +.......##........... +....#####..##....... +........##.#........ +.....###...........# +..##########.....##. +..#........#.#...... +......##...##....... +....##...###..###... +.####...#####...#### +###................. +.......##........... +..........###..####. +..####..#####.#####. +..###....#.......##. +......##....##...... +....##.###.......... +.##.....#####..#.... +.................... +......###........... +####..###.#########. +.......#######...... +....###............. +.........###.#####.. +................#### +50 20 17 +.................... +###################. +#..##............... +.................... +............####.... +........#####....... +..............#..#.. +.........####...#### +.............####... +.....#....###....... +####...............# +.................... +.....######......... +......#............. +.####......#####.... +.............##..... +#####....#####...... +..#####............. +##..####....###..### +.................... +.................... +........######.###.. +....####....#####... +....########........ +...#####............ +.###................ +...............###.. +.......#########.... +..................## +.......####......... +..#####............. +...####............. +.##..........#####.. +.................... +...#.##.......###... +######.....##......# +......####.......... +......#............. +.................... +.................... +.................... +.....#.............. +.....####....###.... +......#.........#### +.......######...###. +.................... +.................... +##...........###...# +.###................ +......#######....... +45 25 10 +......................... +######################### +#...................#..## +....................#.... +......................... +......................... +...................#####. +##.....................## +.#.....................#. +##.....................## +......................... +.....####................ +.....##.#................ +.....##.#................ +.....##.#............#### +.....##.#.......###..#### +.....##.#.......#.#...... +.....##.######..#.#...... +.....####....#..#.#..###. +........#....#..#.#..###. +...##...#....#..#.#...... +...##...#....#..#.#...... +...##...#....#..#.#...... +...##...#....#..#.#...... +...########..#..###...... +##.##...#....#........### +.#.##...######..#####.#.. +.#.##...........#...#.#.. +.#.##...........#...#.#.. +.#..............#...#.#.. +.#..............#...#.#.. +.#.####.........#...#.#.. +.#.#..#.........#...#.#.. +.#.#..#.........#####.#.. +##.#.##########.......### +...#.####.....#.......... +..#####.#.....#..####.... +..#####.#.....#..#..#.... +..#..#..#.....#..#..#.... +..#..#..#.....#..#..#.... +#.#..#..#.....#..#..#..## +#.#..#..#######..#..#..#. +#.####.......#####..#..#. +#............#..##..#..#. +#............########..#. +25 45 5 +............................................. +############################################# +..........#...###################.#...#...... +#########.#....############################## +#########.#.............##################... +####################....##################### +#########..........#........################# +####################........################# +..................####################.....#. +####..............#...........############### +######################################.###### +#########################.....#...########### +###.###################.......#.....######### +#####.#.........#.....#.....################# +############################################# +###.#############...####............######### +......############################...#....#.. +....#########....................#...######.. +##########.##..............################## +#####################......################## +############################################# +############################################# +#######################################...### +############################################# +##########....############################### +40 40 5 +...............................######### +######################################## +######################################## +######################################## +#########....########################### +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +..#######.######################........ +######################################## +######################################## +######################################## +...........#####################........ +####.................################### +######################################## +######################################## +######################################## +######################################## +#####................################### +###################...........########## +######################################## +######################################## +.......##############################... +######################################## +######################################## +######################################## +##############..............############ +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +######################################## +30 20 2 +.................... +#################### +#############.....## +##...############### +#################### +#################### +#################### +....##.....#...#.... +#################### +##########.######### +###....############# +#########....####### +###....############# +#################### +....#######.....###. +#################### +########.########### +#################### +#############.....## +....#####..######### +#################### +##..########.##.#### +########.########### +#########..######### +#........########### +#########..######.## +###.################ +#################### +#################### +##############...### +50 20 7 +...................# +#################### +#####...############ +#################### +#################### +#################### +#################### +#################### +#################### +.....##############. +#################### +#################### +.........########... +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#########.########## +#################### +#################### +#################### +....###########..... +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +##........########## +#################### +#################### +#################### +#################### +#################### +#################### +#################### +#################### +....##########...... +#################### +49 49 3 +................................................. +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +................................................. +................................................. +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +################################################# +........##########............................... +################################################# +###########..................#################### +################################################# +################################################# +################################################# +################################################# +................................................. +################################################# +################################################# +################################################# +################################################# +################################################# +.......#####..................................... +................................................. +################################################# +................................################. +..................................###########.... +################################################# +################################################# +################################################# +################################################# +45 25 4 +......................... +######################### +########............##### +######################### +......................... +###############.#######.# +###############.#######.# +############....#######.# +......................... +############.#.########## +############...########## +######################### +.................######.. +################.######.# +......................... +....................##... +......................... +######################### +######################### +######################### +######################### +######################### +######################### +..........####........... +##....................... +##....................... +#########.####.########## +..........####........... +######################### +######################### +######################### +######################### +######################### +######################### +......................... +##################.###### +##################.###### +##################.###### +......................... +######################### +######################### +######################### +......................... +......................... +......................... +25 45 5 +............................................. +############################################# +####################################.######## +###########.################################# +###########.################################# +###########.################################# +############################################# +############################################# +############################################# +############################################# +############################################# +############################################# +############################################# +############################################# +############################################# +#############################...############# +#############################.#.############# +#############################...############# +############################################# +############################################# +############################################# +###..######################################## +###..######################################## +#########################################.... +####################################.####.##. +50 50 18 +.................................................. +################################################## +..##..##..##..##..##..##..##..##..##..##..##..##.. +.###.###.###.###.###.###.###.###.###.###.###.###.# +....####....####....####....####....####....####.. +.#.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +..######..######..######..######..######..######.. +.#######.#######.#######.#######.#######.#######.# +........########........########........########.. +.#.#.#.#########.#.#.#.#########.#.#.#.#########.# +..##..##########..##..##########..##..##########.. +.###.###########.###.###########.###.###########.# +....############....############....############.. +.#.#############.#.#############.#.#############.# +..##############..##############..##############.. +.###############.###############.###############.# +................################................## +.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.#.### +..##..##..##..##################..##..##..##..#### +.###.###.###.###################.###.###.###.##### +....####....####################....####....###### +.#.#####.#.#####################.#.#####.#.####### +..######..######################..######..######## +.#######.#######################.#######.######### +........########################........########## +.#.#.#.#########################.#.#.#.########### +..##..##########################..##..############ +.###.###########################.###.############# +....############################....############## +.#.#############################.#.############### +..##############################..################ +.###############################.################# +................................################## +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################### +..##..##..##..##..##..##..##..#################### +.###.###.###.###.###.###.###.##################### +....####....####....####....###################### +.#.#####.#.#####.#.#####.#.####################### +..######..######..######..######################## +.#######.#######.#######.######################### +........########........########################## +.#.#.#.#########.#.#.#.########################### +..##..##########..##..############################ +.###.###########.###.############################# +....############....############################## +.#.#############.#.############################### +..##############..################################ +.###############.################################# +................################################## +.#.#.#.#.#.#.#.################################### +50 50 19 +.................................................. +################################################## +..##..##..##..##..##..##..##..##..##..##..##..##.. +.###.###.###.###.###.###.###.###.###.###.###.###.# +....####....####....####....####....####....####.. +.#.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +..######..######..######..######..######..######.. +.#######.#######.#######.#######.#######.#######.# +........########........########........########.. +.#.#.#.#########.#.#.#.#########.#.#.#.#########.# +..##..##########..##..##########..##..##########.. +.###.###########.###.###########.###.###########.# +....############....############....############.. +.#.#############.#.#############.#.#############.# +..##############..##############..##############.. +.###############.###############.###############.# +................################................## +.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.#.### +..##..##..##..##################..##..##..##..#### +.###.###.###.###################.###.###.###.##### +....####....####################....####....###### +.#.#####.#.#####################.#.#####.#.####### +..######..######################..######..######## +.#######.#######################.#######.######### +........########################........########## +.#.#.#.#########################.#.#.#.########### +..##..##########################..##..############ +.###.###########################.###.############# +....############################....############## +.#.#############################.#.############### +..##############################..################ +.###############################.################# +................................################## +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################### +..##..##..##..##..##..##..##..#################### +.###.###.###.###.###.###.###.##################### +....####....####....####....###################### +.#.#####.#.#####.#.#####.#.####################### +..######..######..######..######################## +.#######.#######.#######.######################### +........########........########################## +.#.#.#.#########.#.#.#.########################### +..##..##########..##..############################ +.###.###########.###.############################# +....############....############################## +.#.#############.#.############################### +..##############..################################ +.###############.################################# +................################################## +.#.#.#.#.#.#.#.################################### +50 50 20 +.................................................. +################################################## +..##..##..##..##..##..##..##..##..##..##..##..##.. +.###.###.###.###.###.###.###.###.###.###.###.###.# +....####....####....####....####....####....####.. +.#.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +..######..######..######..######..######..######.. +.#######.#######.#######.#######.#######.#######.# +........########........########........########.. +.#.#.#.#########.#.#.#.#########.#.#.#.#########.# +..##..##########..##..##########..##..##########.. +.###.###########.###.###########.###.###########.# +....############....############....############.. +.#.#############.#.#############.#.#############.# +..##############..##############..##############.. +.###############.###############.###############.# +................################................## +.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.#.### +..##..##..##..##################..##..##..##..#### +.###.###.###.###################.###.###.###.##### +....####....####################....####....###### +.#.#####.#.#####################.#.#####.#.####### +..######..######################..######..######## +.#######.#######################.#######.######### +........########################........########## +.#.#.#.#########################.#.#.#.########### +..##..##########################..##..############ +.###.###########################.###.############# +....############################....############## +.#.#############################.#.############### +..##############################..################ +.###############################.################# +................................################## +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################### +..##..##..##..##..##..##..##..#################### +.###.###.###.###.###.###.###.##################### +....####....####....####....###################### +.#.#####.#.#####.#.#####.#.####################### +..######..######..######..######################## +.#######.#######.#######.######################### +........########........########################## +.#.#.#.#########.#.#.#.########################### +..##..##########..##..############################ +.###.###########.###.############################# +....############....############################## +.#.#############.#.############################### +..##############..################################ +.###############.################################# +................################################## +.#.#.#.#.#.#.#.################################### +49 48 5 +................................................ +################################################ +################################.############### +###############################..##############. +##############################.#.#############.# +#############################....############... +############################.###.###########.### +###########################..##..##########..##. +##########################.#.#.#.#########.#.#.# +#########################........########....... +########################.#######.#######.####### +#######################..######..######..######. +######################.#.#####.#.#####.#.#####.# +#####################....####....####....####... +####################.###.###.###.###.###.###.### +###################..##..##..##..##..##..##..##. +##################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +#################............................... +################.############################### +###############..##############################. +##############.#.#############################.# +#############....############################... +############.###.###########################.### +###########..##..##########################..##. +##########.#.#.#.#########################.#.#.# +#########........########################....... +########.#######.#######################.####### +#######..######..######################..######. +######.#.#####.#.#####################.#.#####.# +#####....####....####################....####... +####.###.###.###.###################.###.###.### +###..##..##..##..##################..##..##..##. +##.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.# +#................################............... +.###############.###############.############### +.##############..##############..##############. +.#############.#.#############.#.#############.# +.############....############....############... +.###########.###.###########.###.###########.### +.##########..##..##########..##..##########..##. +.#########.#.#.#.#########.#.#.#.#########.#.#.# +.########........########........########....... +.#######.#######.#######.#######.#######.####### +.######..######..######..######..######..######. +.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +.####....####....####....####....####....####... +.###.###.###.###.###.###.###.###.###.###.###.### +.##..##..##..##..##..##..##..##..##..##..##..##. +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +49 48 11 +................................................ +################################################ +################################.############### +###############################..##############. +##############################.#.#############.# +#############################....############... +############################.###.###########.### +###########################..##..##########..##. +##########################.#.#.#.#########.#.#.# +#########################........########....... +########################.#######.#######.####### +#######################..######..######..######. +######################.#.#####.#.#####.#.#####.# +#####################....####....####....####... +####################.###.###.###.###.###.###.### +###################..##..##..##..##..##..##..##. +##################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +#################............................... +################.############################### +###############..##############################. +##############.#.#############################.# +#############....############################... +############.###.###########################.### +###########..##..##########################..##. +##########.#.#.#.#########################.#.#.# +#########........########################....... +########.#######.#######################.####### +#######..######..######################..######. +######.#.#####.#.#####################.#.#####.# +#####....####....####################....####... +####.###.###.###.###################.###.###.### +###..##..##..##..##################..##..##..##. +##.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.# +#................################............... +.###############.###############.############### +.##############..##############..##############. +.#############.#.#############.#.#############.# +.############....############....############... +.###########.###.###########.###.###########.### +.##########..##..##########..##..##########..##. +.#########.#.#.#.#########.#.#.#.#########.#.#.# +.########........########........########....... +.#######.#######.#######.#######.#######.####### +.######..######..######..######..######..######. +.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +.####....####....####....####....####....####... +.###.###.###.###.###.###.###.###.###.###.###.### +.##..##..##..##..##..##..##..##..##..##..##..##. +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +49 48 30 +................................................ +################################################ +################################.############### +###############################..##############. +##############################.#.#############.# +#############################....############... +############################.###.###########.### +###########################..##..##########..##. +##########################.#.#.#.#########.#.#.# +#########################........########....... +########################.#######.#######.####### +#######################..######..######..######. +######################.#.#####.#.#####.#.#####.# +#####################....####....####....####... +####################.###.###.###.###.###.###.### +###################..##..##..##..##..##..##..##. +##################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +#################............................... +################.############################### +###############..##############################. +##############.#.#############################.# +#############....############################... +############.###.###########################.### +###########..##..##########################..##. +##########.#.#.#.#########################.#.#.# +#########........########################....... +########.#######.#######################.####### +#######..######..######################..######. +######.#.#####.#.#####################.#.#####.# +#####....####....####################....####... +####.###.###.###.###################.###.###.### +###..##..##..##..##################..##..##..##. +##.#.#.#.#.#.#.#.#################.#.#.#.#.#.#.# +#................################............... +.###############.###############.############### +.##############..##############..##############. +.#############.#.#############.#.#############.# +.############....############....############... +.###########.###.###########.###.###########.### +.##########..##..##########..##..##########..##. +.#########.#.#.#.#########.#.#.#.#########.#.#.# +.########........########........########....... +.#######.#######.#######.#######.#######.####### +.######..######..######..######..######..######. +.#####.#.#####.#.#####.#.#####.#.#####.#.#####.# +.####....####....####....####....####....####... +.###.###.###.###.###.###.###.###.###.###.###.### +.##..##..##..##..##..##..##..##..##..##..##..##. +.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# +50 10 4 +.......... +#####..... +#####..... +.####..... +#.###..... +##.##..... +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +#####..... +.####..... +#.###..... +##.##..... +.......... +#####..... +#......... +.#........ +..#....... +...#...... +.......... +....#..... +...#...... +..#....... +.#........ +.......... +#####..... +#####..... +.####..... +#.###..... +##.##..... +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +#####..... +#####..... +#####..... +#####..... +.......... +#####..... +#####..... +50 10 5 +.......... +#####..... +...##..... +.......... +.......... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +#......... +.#........ +..#....... +...#...... +.......... +....#..... +...#...... +..#....... +.#........ +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +#####..... +.####..... +#.###..... +##.##..... +.......... +#####..... +#......... +.#........ +..#....... +...#...... +.......... +....#..... +...#...... +..#....... +.#........ +.......... +50 10 4 +.......... +#####..... +#......... +.#........ +..#....... +...#...... +.......... +....#..... +...#...... +..#....... +.#........ +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +#####..... +#####..... +#####..... +#####..... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +#####..... +#####..... +#####..... +#####..... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +50 10 5 +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +#####..... +#####..... +#####..... +#####..... +.......... +#####..... +##........ +.......... +.......... +.......... +#####..... +#####..... +.####..... +#.###..... +##.##..... +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +...##..... +.......... +.......... +.......... +#####..... +#####..... +#####..... +#####..... +#####..... +.......... +#####..... +#####..... +####...... +###.#..... +##.##..... +.......... +#####..... +#......... +.#........ +..#....... +35 41 11 +........................................# +######################################### +##.......####.#..######.##.###...#####.## +.##.#.#...#.###...##...#..#.#..##..###### +.#...##....#.###...##.#.##.#.###...####.. +.###...##.##..####..##.#.#####.#...#.#... +..#...#.##..#...##..###..##...###...#.#.. +.#.####.##.##.###.....#..#..##.###..#.##. +##..##..#...##.###.#...####...#..##....#. +#....#..##.#.#.#......####.#.....#...#.#. +#.##.#####......####......###.###..###.#. +##..######...######.##.#.##.......#...#.. +.#.....###......#####...#..#.#.###...##.# +...##.##.##..##...####.#.###...#..#.##..# +....###.#.#..#...###..###.###..#####...## +....##.##..#.#.#.#.#####...##..######.... +#.#.##.##.#...#####....##.#.#...#.##.#..# +#.##.##.##.#...#.#.####...#..#.......##.# +.##.#..###..####.#..###...#...###.##.##.. +.####.#.#######.#......##....#######..##. +.#..#...#.#.####..#.######.#.#..##.#.#### +...#.###..#.##.#.###.#.#....#.###.#.#...# +..#.#.####....###...#..##..#####.#.###### +#......####.#..##.....#####.##...###..... +##..##..####......#.#.##..##...###.#..... +#.#.####.####.......##......####.###..### +##...###.#...#.####.##.#........##..#.### +....#..#####.#....#.##...###..#####.#.### +####.#.###.........####..###.#..######.## +.#..########..###..#####.######.###.#...# +.##..#.##..#....####...#.###.....##.#...# +##.#..##.##..##.##...##.##.##.#.##.###### +..#..#..####..##...###.#...#.....###..#.. +####.#..####.###...##..#.#.###.#..#..#### +#...#..#..#.#...#...#.#.##.##.#...###.#.# +31 41 12 +......................................... +#################################.....#.. +.#..........#.......#....##....#...#..... +.........#......#.#...#...#..#........#.. +#......#.#......#...#.........#.........# +.................#....#...#...##......... +.......#.#..#.....#..#.....##........#..# +.....#..#..#......................#..#... +..............#....##....#...#..#..#....# +...#.#.#........##.#..#..........#......# +...#......#..#......#....#....#....#..... +......##.#...#.##..........#............. +.......##.#.#..#...#.....#.#..#.......... +.........#..........#.................#.. +.#....#..#......#.......#.#..#..####.##.. +#...#................##...#..........#... +..........#...#.#..#..###..#...#......... +........##.......#.....##.#......#...#.#. +.#.....#.#..#.....#.#..##.#.#...........# +.......####...#.#.........#...#.#........ +.##.................#.#.#................ +.....###.#...#..#.#..............#....... +.....#...#.....#........#....##.......#.. +.........#...........##.#..#.....##...... +...#....#.........#...#...#.#............ +.....#..............#..............#....# +#.##...#.............#....#.#..#......#.. +........#...#...##.............#.#....... +.......#.......#..............#.......... +.....#.........#.........#..#...#..#....# +####..#...#.#.....##...........#.#.#.#.#. diff -r 0139aac70fb5 -r bad7ecd0b6ed test/compiler/5091921/output6890943.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/5091921/output6890943.txt Wed May 04 13:12:42 2011 -0700 @@ -0,0 +1,50 @@ +Case #1: Yes 2 +Case #2: Yes 2 +Case #3: Yes 1 +Case #4: Yes 0 +Case #5: No +Case #6: No +Case #7: Yes 6 +Case #8: Yes 6 +Case #9: No +Case #10: Yes 1 +Case #11: Yes 6 +Case #12: Yes 0 +Case #13: No +Case #14: Yes 22 +Case #15: Yes 1225 +Case #16: Yes 178 +Case #17: No +Case #18: Yes 1 +Case #19: Yes 7 +Case #20: Yes 2 +Case #21: Yes 1 +Case #22: No +Case #23: Yes 3 +Case #24: Yes 1 +Case #25: Yes 7 +Case #26: No +Case #27: Yes 2 +Case #28: Yes 4 +Case #29: Yes 2 +Case #30: Yes 1 +Case #31: Yes 2 +Case #32: Yes 20 +Case #33: Yes 161 +Case #34: Yes 48 +Case #35: No +Case #36: Yes 218 +Case #37: Yes 51 +Case #38: Yes 247 +Case #39: Yes 32 +Case #40: Yes 31 +Case #41: Yes 31 +Case #42: Yes 25 +Case #43: Yes 17 +Case #44: Yes 2 +Case #45: Yes 61 +Case #46: Yes 25 +Case #47: No +Case #48: No +Case #49: Yes 8 +Case #50: Yes 0