1.1 --- a/src/share/vm/opto/loopTransform.cpp Wed Mar 17 10:47:03 2010 -0700
1.2 +++ b/src/share/vm/opto/loopTransform.cpp Wed Mar 17 16:40:25 2010 -0700
1.3 @@ -1,5 +1,5 @@
1.4 /*
1.5 - * Copyright 2000-2009 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * Copyright 2000-2010 Sun Microsystems, Inc. All Rights Reserved.
1.7 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.8 *
1.9 * This code is free software; you can redistribute it and/or modify it
1.10 @@ -2088,29 +2088,41 @@
1.11 BoolNode* PhaseIdealLoop::rc_predicate(Node* ctrl,
1.12 int scale, Node* offset,
1.13 Node* init, Node* limit, Node* stride,
1.14 - Node* range) {
1.15 + Node* range, bool upper) {
1.16 + DEBUG_ONLY(ttyLocker ttyl);
1.17 + if (TraceLoopPredicate) tty->print("rc_predicate ");
1.18 +
1.19 Node* max_idx_expr = init;
1.20 int stride_con = stride->get_int();
1.21 - if ((stride_con > 0) == (scale > 0)) {
1.22 + if ((stride_con > 0) == (scale > 0) == upper) {
1.23 max_idx_expr = new (C, 3) SubINode(limit, stride);
1.24 register_new_node(max_idx_expr, ctrl);
1.25 + if (TraceLoopPredicate) tty->print("(limit - stride) ");
1.26 + } else {
1.27 + if (TraceLoopPredicate) tty->print("init ");
1.28 }
1.29
1.30 if (scale != 1) {
1.31 ConNode* con_scale = _igvn.intcon(scale);
1.32 max_idx_expr = new (C, 3) MulINode(max_idx_expr, con_scale);
1.33 register_new_node(max_idx_expr, ctrl);
1.34 + if (TraceLoopPredicate) tty->print("* %d ", scale);
1.35 }
1.36
1.37 if (offset && (!offset->is_Con() || offset->get_int() != 0)){
1.38 max_idx_expr = new (C, 3) AddINode(max_idx_expr, offset);
1.39 register_new_node(max_idx_expr, ctrl);
1.40 + if (TraceLoopPredicate)
1.41 + if (offset->is_Con()) tty->print("+ %d ", offset->get_int());
1.42 + else tty->print("+ offset ");
1.43 }
1.44
1.45 CmpUNode* cmp = new (C, 3) CmpUNode(max_idx_expr, range);
1.46 register_new_node(cmp, ctrl);
1.47 BoolNode* bol = new (C, 2) BoolNode(cmp, BoolTest::lt);
1.48 register_new_node(bol, ctrl);
1.49 +
1.50 + if (TraceLoopPredicate) tty->print_cr("<u range");
1.51 return bol;
1.52 }
1.53
1.54 @@ -2187,7 +2199,6 @@
1.55 while (if_proj_list.size() > 0) {
1.56 // Following are changed to nonnull when a predicate can be hoisted
1.57 ProjNode* new_predicate_proj = NULL;
1.58 - BoolNode* new_predicate_bol = NULL;
1.59
1.60 ProjNode* proj = if_proj_list.pop()->as_Proj();
1.61 IfNode* iff = proj->in(0)->as_If();
1.62 @@ -2218,93 +2229,120 @@
1.63 // Invariant test
1.64 new_predicate_proj = create_new_if_for_predicate(predicate_proj);
1.65 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0);
1.66 - new_predicate_bol = invar.clone(bol, ctrl)->as_Bool();
1.67 - if (TraceLoopPredicate) tty->print("invariant");
1.68 + BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool();
1.69 +
1.70 + // Negate test if necessary
1.71 + bool negated = false;
1.72 + if (proj->_con != predicate_proj->_con) {
1.73 + new_predicate_bol = new (C, 2) BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate());
1.74 + register_new_node(new_predicate_bol, ctrl);
1.75 + negated = true;
1.76 + }
1.77 + IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If();
1.78 + _igvn.hash_delete(new_predicate_iff);
1.79 + new_predicate_iff->set_req(1, new_predicate_bol);
1.80 + if (TraceLoopPredicate) tty->print_cr("invariant if%s: %d", negated ? " negated" : "", new_predicate_iff->_idx);
1.81 +
1.82 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) {
1.83 - // Range check (only for counted loops)
1.84 - new_predicate_proj = create_new_if_for_predicate(predicate_proj);
1.85 - Node *ctrl = new_predicate_proj->in(0)->as_If()->in(0);
1.86 + assert(proj->_con == predicate_proj->_con, "must match");
1.87 +
1.88 + // Range check for counted loops
1.89 const Node* cmp = bol->in(1)->as_Cmp();
1.90 Node* idx = cmp->in(1);
1.91 assert(!invar.is_invariant(idx), "index is variant");
1.92 assert(cmp->in(2)->Opcode() == Op_LoadRange, "must be");
1.93 - LoadRangeNode* ld_rng = (LoadRangeNode*)cmp->in(2); // LoadRangeNode
1.94 + Node* ld_rng = cmp->in(2); // LoadRangeNode
1.95 assert(invar.is_invariant(ld_rng), "load range must be invariant");
1.96 - ld_rng = (LoadRangeNode*)invar.clone(ld_rng, ctrl);
1.97 int scale = 1;
1.98 Node* offset = zero;
1.99 bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset);
1.100 assert(ok, "must be index expression");
1.101 +
1.102 + Node* init = cl->init_trip();
1.103 + Node* limit = cl->limit();
1.104 + Node* stride = cl->stride();
1.105 +
1.106 + // Build if's for the upper and lower bound tests. The
1.107 + // lower_bound test will dominate the upper bound test and all
1.108 + // cloned or created nodes will use the lower bound test as
1.109 + // their declared control.
1.110 + ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj);
1.111 + ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj);
1.112 + assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate");
1.113 + Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0);
1.114 +
1.115 + // Perform cloning to keep Invariance state correct since the
1.116 + // late schedule will place invariant things in the loop.
1.117 + ld_rng = invar.clone(ld_rng, ctrl);
1.118 if (offset && offset != zero) {
1.119 assert(invar.is_invariant(offset), "offset must be loop invariant");
1.120 offset = invar.clone(offset, ctrl);
1.121 }
1.122 - Node* init = cl->init_trip();
1.123 - Node* limit = cl->limit();
1.124 - Node* stride = cl->stride();
1.125 - new_predicate_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, ld_rng);
1.126 - if (TraceLoopPredicate) tty->print("range check");
1.127 - }
1.128
1.129 - if (new_predicate_proj == NULL) {
1.130 + // Test the lower bound
1.131 + Node* lower_bound_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, ld_rng, false);
1.132 + IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If();
1.133 + _igvn.hash_delete(lower_bound_iff);
1.134 + lower_bound_iff->set_req(1, lower_bound_bol);
1.135 + if (TraceLoopPredicate) tty->print_cr("lower bound check if: %d", lower_bound_iff->_idx);
1.136 +
1.137 + // Test the upper bound
1.138 + Node* upper_bound_bol = rc_predicate(ctrl, scale, offset, init, limit, stride, ld_rng, true);
1.139 + IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If();
1.140 + _igvn.hash_delete(upper_bound_iff);
1.141 + upper_bound_iff->set_req(1, upper_bound_bol);
1.142 + if (TraceLoopPredicate) tty->print_cr("upper bound check if: %d", lower_bound_iff->_idx);
1.143 +
1.144 + // Fall through into rest of the clean up code which will move
1.145 + // any dependent nodes onto the upper bound test.
1.146 + new_predicate_proj = upper_bound_proj;
1.147 + } else {
1.148 // The other proj of the "iff" is a uncommon trap projection, and we can assume
1.149 // the other proj will not be executed ("executed" means uct raised).
1.150 continue;
1.151 - } else {
1.152 - // Success - attach condition (new_predicate_bol) to predicate if
1.153 - invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate
1.154 - IfNode* new_iff = new_predicate_proj->in(0)->as_If();
1.155 + }
1.156
1.157 - // Negate test if necessary
1.158 - if (proj->_con != predicate_proj->_con) {
1.159 - new_predicate_bol = new (C, 2) BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate());
1.160 - register_new_node(new_predicate_bol, new_iff->in(0));
1.161 - if (TraceLoopPredicate) tty->print_cr(" if negated: %d", iff->_idx);
1.162 - } else {
1.163 - if (TraceLoopPredicate) tty->print_cr(" if: %d", iff->_idx);
1.164 + // Success - attach condition (new_predicate_bol) to predicate if
1.165 + invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate
1.166 +
1.167 + // Eliminate the old if in the loop body
1.168 + _igvn.hash_delete(iff);
1.169 + iff->set_req(1, proj->is_IfFalse() ? cond_false : cond_true);
1.170 +
1.171 + Node* ctrl = new_predicate_proj; // new control
1.172 + ProjNode* dp = proj; // old control
1.173 + assert(get_loop(dp) == loop, "guaranteed at the time of collecting proj");
1.174 + // Find nodes (depends only on the test) off the surviving projection;
1.175 + // move them outside the loop with the control of proj_clone
1.176 + for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
1.177 + Node* cd = dp->fast_out(i); // Control-dependent node
1.178 + if (cd->depends_only_on_test()) {
1.179 + assert(cd->in(0) == dp, "");
1.180 + _igvn.hash_delete(cd);
1.181 + cd->set_req(0, ctrl); // ctrl, not NULL
1.182 + set_early_ctrl(cd);
1.183 + _igvn._worklist.push(cd);
1.184 + IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
1.185 + if (new_loop != loop) {
1.186 + if (!loop->_child) loop->_body.yank(cd);
1.187 + if (!new_loop->_child ) new_loop->_body.push(cd);
1.188 + }
1.189 + --i;
1.190 + --imax;
1.191 }
1.192 + }
1.193
1.194 - _igvn.hash_delete(new_iff);
1.195 - new_iff->set_req(1, new_predicate_bol);
1.196 -
1.197 - _igvn.hash_delete(iff);
1.198 - iff->set_req(1, proj->is_IfFalse() ? cond_false : cond_true);
1.199 -
1.200 - Node* ctrl = new_predicate_proj; // new control
1.201 - ProjNode* dp = proj; // old control
1.202 - assert(get_loop(dp) == loop, "guarenteed at the time of collecting proj");
1.203 - // Find nodes (depends only on the test) off the surviving projection;
1.204 - // move them outside the loop with the control of proj_clone
1.205 - for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
1.206 - Node* cd = dp->fast_out(i); // Control-dependent node
1.207 - if (cd->depends_only_on_test()) {
1.208 - assert(cd->in(0) == dp, "");
1.209 - _igvn.hash_delete(cd);
1.210 - cd->set_req(0, ctrl); // ctrl, not NULL
1.211 - set_early_ctrl(cd);
1.212 - _igvn._worklist.push(cd);
1.213 - IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
1.214 - if (new_loop != loop) {
1.215 - if (!loop->_child) loop->_body.yank(cd);
1.216 - if (!new_loop->_child ) new_loop->_body.push(cd);
1.217 - }
1.218 - --i;
1.219 - --imax;
1.220 - }
1.221 - }
1.222 -
1.223 - hoisted = true;
1.224 - C->set_major_progress();
1.225 - }
1.226 + hoisted = true;
1.227 + C->set_major_progress();
1.228 } // end while
1.229
1.230 #ifndef PRODUCT
1.231 - // report that the loop predication has been actually performed
1.232 - // for this loop
1.233 - if (TraceLoopPredicate && hoisted) {
1.234 - tty->print("Loop Predication Performed:");
1.235 - loop->dump_head();
1.236 - }
1.237 + // report that the loop predication has been actually performed
1.238 + // for this loop
1.239 + if (TraceLoopPredicate && hoisted) {
1.240 + tty->print("Loop Predication Performed:");
1.241 + loop->dump_head();
1.242 + }
1.243 #endif
1.244
1.245 return hoisted;
