1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/loopTransform.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,2796 @@
1.4 +/*
1.5 + * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "compiler/compileLog.hpp"
1.30 +#include "memory/allocation.inline.hpp"
1.31 +#include "opto/addnode.hpp"
1.32 +#include "opto/callnode.hpp"
1.33 +#include "opto/connode.hpp"
1.34 +#include "opto/divnode.hpp"
1.35 +#include "opto/loopnode.hpp"
1.36 +#include "opto/mulnode.hpp"
1.37 +#include "opto/rootnode.hpp"
1.38 +#include "opto/runtime.hpp"
1.39 +#include "opto/subnode.hpp"
1.40 +
1.41 +//------------------------------is_loop_exit-----------------------------------
1.42 +// Given an IfNode, return the loop-exiting projection or NULL if both
1.43 +// arms remain in the loop.
1.44 +Node *IdealLoopTree::is_loop_exit(Node *iff) const {
1.45 + if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests
1.46 + PhaseIdealLoop *phase = _phase;
1.47 + // Test is an IfNode, has 2 projections. If BOTH are in the loop
1.48 + // we need loop unswitching instead of peeling.
1.49 + if( !is_member(phase->get_loop( iff->raw_out(0) )) )
1.50 + return iff->raw_out(0);
1.51 + if( !is_member(phase->get_loop( iff->raw_out(1) )) )
1.52 + return iff->raw_out(1);
1.53 + return NULL;
1.54 +}
1.55 +
1.56 +
1.57 +//=============================================================================
1.58 +
1.59 +
1.60 +//------------------------------record_for_igvn----------------------------
1.61 +// Put loop body on igvn work list
1.62 +void IdealLoopTree::record_for_igvn() {
1.63 + for( uint i = 0; i < _body.size(); i++ ) {
1.64 + Node *n = _body.at(i);
1.65 + _phase->_igvn._worklist.push(n);
1.66 + }
1.67 +}
1.68 +
1.69 +//------------------------------compute_exact_trip_count-----------------------
1.70 +// Compute loop exact trip count if possible. Do not recalculate trip count for
1.71 +// split loops (pre-main-post) which have their limits and inits behind Opaque node.
1.72 +void IdealLoopTree::compute_exact_trip_count( PhaseIdealLoop *phase ) {
1.73 + if (!_head->as_Loop()->is_valid_counted_loop()) {
1.74 + return;
1.75 + }
1.76 + CountedLoopNode* cl = _head->as_CountedLoop();
1.77 + // Trip count may become nonexact for iteration split loops since
1.78 + // RCE modifies limits. Note, _trip_count value is not reset since
1.79 + // it is used to limit unrolling of main loop.
1.80 + cl->set_nonexact_trip_count();
1.81 +
1.82 + // Loop's test should be part of loop.
1.83 + if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
1.84 + return; // Infinite loop
1.85 +
1.86 +#ifdef ASSERT
1.87 + BoolTest::mask bt = cl->loopexit()->test_trip();
1.88 + assert(bt == BoolTest::lt || bt == BoolTest::gt ||
1.89 + bt == BoolTest::ne, "canonical test is expected");
1.90 +#endif
1.91 +
1.92 + Node* init_n = cl->init_trip();
1.93 + Node* limit_n = cl->limit();
1.94 + if (init_n != NULL && init_n->is_Con() &&
1.95 + limit_n != NULL && limit_n->is_Con()) {
1.96 + // Use longs to avoid integer overflow.
1.97 + int stride_con = cl->stride_con();
1.98 + jlong init_con = cl->init_trip()->get_int();
1.99 + jlong limit_con = cl->limit()->get_int();
1.100 + int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
1.101 + jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
1.102 + if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
1.103 + // Set exact trip count.
1.104 + cl->set_exact_trip_count((uint)trip_count);
1.105 + }
1.106 + }
1.107 +}
1.108 +
1.109 +//------------------------------compute_profile_trip_cnt----------------------------
1.110 +// Compute loop trip count from profile data as
1.111 +// (backedge_count + loop_exit_count) / loop_exit_count
1.112 +void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {
1.113 + if (!_head->is_CountedLoop()) {
1.114 + return;
1.115 + }
1.116 + CountedLoopNode* head = _head->as_CountedLoop();
1.117 + if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
1.118 + return; // Already computed
1.119 + }
1.120 + float trip_cnt = (float)max_jint; // default is big
1.121 +
1.122 + Node* back = head->in(LoopNode::LoopBackControl);
1.123 + while (back != head) {
1.124 + if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
1.125 + back->in(0) &&
1.126 + back->in(0)->is_If() &&
1.127 + back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&
1.128 + back->in(0)->as_If()->_prob != PROB_UNKNOWN) {
1.129 + break;
1.130 + }
1.131 + back = phase->idom(back);
1.132 + }
1.133 + if (back != head) {
1.134 + assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
1.135 + back->in(0), "if-projection exists");
1.136 + IfNode* back_if = back->in(0)->as_If();
1.137 + float loop_back_cnt = back_if->_fcnt * back_if->_prob;
1.138 +
1.139 + // Now compute a loop exit count
1.140 + float loop_exit_cnt = 0.0f;
1.141 + for( uint i = 0; i < _body.size(); i++ ) {
1.142 + Node *n = _body[i];
1.143 + if( n->is_If() ) {
1.144 + IfNode *iff = n->as_If();
1.145 + if( iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN ) {
1.146 + Node *exit = is_loop_exit(iff);
1.147 + if( exit ) {
1.148 + float exit_prob = iff->_prob;
1.149 + if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;
1.150 + if (exit_prob > PROB_MIN) {
1.151 + float exit_cnt = iff->_fcnt * exit_prob;
1.152 + loop_exit_cnt += exit_cnt;
1.153 + }
1.154 + }
1.155 + }
1.156 + }
1.157 + }
1.158 + if (loop_exit_cnt > 0.0f) {
1.159 + trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;
1.160 + } else {
1.161 + // No exit count so use
1.162 + trip_cnt = loop_back_cnt;
1.163 + }
1.164 + }
1.165 +#ifndef PRODUCT
1.166 + if (TraceProfileTripCount) {
1.167 + tty->print_cr("compute_profile_trip_cnt lp: %d cnt: %f\n", head->_idx, trip_cnt);
1.168 + }
1.169 +#endif
1.170 + head->set_profile_trip_cnt(trip_cnt);
1.171 +}
1.172 +
1.173 +//---------------------is_invariant_addition-----------------------------
1.174 +// Return nonzero index of invariant operand for an Add or Sub
1.175 +// of (nonconstant) invariant and variant values. Helper for reassociate_invariants.
1.176 +int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {
1.177 + int op = n->Opcode();
1.178 + if (op == Op_AddI || op == Op_SubI) {
1.179 + bool in1_invar = this->is_invariant(n->in(1));
1.180 + bool in2_invar = this->is_invariant(n->in(2));
1.181 + if (in1_invar && !in2_invar) return 1;
1.182 + if (!in1_invar && in2_invar) return 2;
1.183 + }
1.184 + return 0;
1.185 +}
1.186 +
1.187 +//---------------------reassociate_add_sub-----------------------------
1.188 +// Reassociate invariant add and subtract expressions:
1.189 +//
1.190 +// inv1 + (x + inv2) => ( inv1 + inv2) + x
1.191 +// (x + inv2) + inv1 => ( inv1 + inv2) + x
1.192 +// inv1 + (x - inv2) => ( inv1 - inv2) + x
1.193 +// inv1 - (inv2 - x) => ( inv1 - inv2) + x
1.194 +// (x + inv2) - inv1 => (-inv1 + inv2) + x
1.195 +// (x - inv2) + inv1 => ( inv1 - inv2) + x
1.196 +// (x - inv2) - inv1 => (-inv1 - inv2) + x
1.197 +// inv1 + (inv2 - x) => ( inv1 + inv2) - x
1.198 +// inv1 - (x - inv2) => ( inv1 + inv2) - x
1.199 +// (inv2 - x) + inv1 => ( inv1 + inv2) - x
1.200 +// (inv2 - x) - inv1 => (-inv1 + inv2) - x
1.201 +// inv1 - (x + inv2) => ( inv1 - inv2) - x
1.202 +//
1.203 +Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {
1.204 + if (!n1->is_Add() && !n1->is_Sub() || n1->outcnt() == 0) return NULL;
1.205 + if (is_invariant(n1)) return NULL;
1.206 + int inv1_idx = is_invariant_addition(n1, phase);
1.207 + if (!inv1_idx) return NULL;
1.208 + // Don't mess with add of constant (igvn moves them to expression tree root.)
1.209 + if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;
1.210 + Node* inv1 = n1->in(inv1_idx);
1.211 + Node* n2 = n1->in(3 - inv1_idx);
1.212 + int inv2_idx = is_invariant_addition(n2, phase);
1.213 + if (!inv2_idx) return NULL;
1.214 + Node* x = n2->in(3 - inv2_idx);
1.215 + Node* inv2 = n2->in(inv2_idx);
1.216 +
1.217 + bool neg_x = n2->is_Sub() && inv2_idx == 1;
1.218 + bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;
1.219 + bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;
1.220 + if (n1->is_Sub() && inv1_idx == 1) {
1.221 + neg_x = !neg_x;
1.222 + neg_inv2 = !neg_inv2;
1.223 + }
1.224 + Node* inv1_c = phase->get_ctrl(inv1);
1.225 + Node* inv2_c = phase->get_ctrl(inv2);
1.226 + Node* n_inv1;
1.227 + if (neg_inv1) {
1.228 + Node *zero = phase->_igvn.intcon(0);
1.229 + phase->set_ctrl(zero, phase->C->root());
1.230 + n_inv1 = new (phase->C) SubINode(zero, inv1);
1.231 + phase->register_new_node(n_inv1, inv1_c);
1.232 + } else {
1.233 + n_inv1 = inv1;
1.234 + }
1.235 + Node* inv;
1.236 + if (neg_inv2) {
1.237 + inv = new (phase->C) SubINode(n_inv1, inv2);
1.238 + } else {
1.239 + inv = new (phase->C) AddINode(n_inv1, inv2);
1.240 + }
1.241 + phase->register_new_node(inv, phase->get_early_ctrl(inv));
1.242 +
1.243 + Node* addx;
1.244 + if (neg_x) {
1.245 + addx = new (phase->C) SubINode(inv, x);
1.246 + } else {
1.247 + addx = new (phase->C) AddINode(x, inv);
1.248 + }
1.249 + phase->register_new_node(addx, phase->get_ctrl(x));
1.250 + phase->_igvn.replace_node(n1, addx);
1.251 + assert(phase->get_loop(phase->get_ctrl(n1)) == this, "");
1.252 + _body.yank(n1);
1.253 + return addx;
1.254 +}
1.255 +
1.256 +//---------------------reassociate_invariants-----------------------------
1.257 +// Reassociate invariant expressions:
1.258 +void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {
1.259 + for (int i = _body.size() - 1; i >= 0; i--) {
1.260 + Node *n = _body.at(i);
1.261 + for (int j = 0; j < 5; j++) {
1.262 + Node* nn = reassociate_add_sub(n, phase);
1.263 + if (nn == NULL) break;
1.264 + n = nn; // again
1.265 + };
1.266 + }
1.267 +}
1.268 +
1.269 +//------------------------------policy_peeling---------------------------------
1.270 +// Return TRUE or FALSE if the loop should be peeled or not. Peel if we can
1.271 +// make some loop-invariant test (usually a null-check) happen before the loop.
1.272 +bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {
1.273 + Node *test = ((IdealLoopTree*)this)->tail();
1.274 + int body_size = ((IdealLoopTree*)this)->_body.size();
1.275 + int live_node_count = phase->C->live_nodes();
1.276 + // Peeling does loop cloning which can result in O(N^2) node construction
1.277 + if( body_size > 255 /* Prevent overflow for large body_size */
1.278 + || (body_size * body_size + live_node_count > MaxNodeLimit) ) {
1.279 + return false; // too large to safely clone
1.280 + }
1.281 + while( test != _head ) { // Scan till run off top of loop
1.282 + if( test->is_If() ) { // Test?
1.283 + Node *ctrl = phase->get_ctrl(test->in(1));
1.284 + if (ctrl->is_top())
1.285 + return false; // Found dead test on live IF? No peeling!
1.286 + // Standard IF only has one input value to check for loop invariance
1.287 + assert( test->Opcode() == Op_If || test->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
1.288 + // Condition is not a member of this loop?
1.289 + if( !is_member(phase->get_loop(ctrl)) &&
1.290 + is_loop_exit(test) )
1.291 + return true; // Found reason to peel!
1.292 + }
1.293 + // Walk up dominators to loop _head looking for test which is
1.294 + // executed on every path thru loop.
1.295 + test = phase->idom(test);
1.296 + }
1.297 + return false;
1.298 +}
1.299 +
1.300 +//------------------------------peeled_dom_test_elim---------------------------
1.301 +// If we got the effect of peeling, either by actually peeling or by making
1.302 +// a pre-loop which must execute at least once, we can remove all
1.303 +// loop-invariant dominated tests in the main body.
1.304 +void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {
1.305 + bool progress = true;
1.306 + while( progress ) {
1.307 + progress = false; // Reset for next iteration
1.308 + Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();
1.309 + Node *test = prev->in(0);
1.310 + while( test != loop->_head ) { // Scan till run off top of loop
1.311 +
1.312 + int p_op = prev->Opcode();
1.313 + if( (p_op == Op_IfFalse || p_op == Op_IfTrue) &&
1.314 + test->is_If() && // Test?
1.315 + !test->in(1)->is_Con() && // And not already obvious?
1.316 + // Condition is not a member of this loop?
1.317 + !loop->is_member(get_loop(get_ctrl(test->in(1))))){
1.318 + // Walk loop body looking for instances of this test
1.319 + for( uint i = 0; i < loop->_body.size(); i++ ) {
1.320 + Node *n = loop->_body.at(i);
1.321 + if( n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/ ) {
1.322 + // IfNode was dominated by version in peeled loop body
1.323 + progress = true;
1.324 + dominated_by( old_new[prev->_idx], n );
1.325 + }
1.326 + }
1.327 + }
1.328 + prev = test;
1.329 + test = idom(test);
1.330 + } // End of scan tests in loop
1.331 +
1.332 + } // End of while( progress )
1.333 +}
1.334 +
1.335 +//------------------------------do_peeling-------------------------------------
1.336 +// Peel the first iteration of the given loop.
1.337 +// Step 1: Clone the loop body. The clone becomes the peeled iteration.
1.338 +// The pre-loop illegally has 2 control users (old & new loops).
1.339 +// Step 2: Make the old-loop fall-in edges point to the peeled iteration.
1.340 +// Do this by making the old-loop fall-in edges act as if they came
1.341 +// around the loopback from the prior iteration (follow the old-loop
1.342 +// backedges) and then map to the new peeled iteration. This leaves
1.343 +// the pre-loop with only 1 user (the new peeled iteration), but the
1.344 +// peeled-loop backedge has 2 users.
1.345 +// Step 3: Cut the backedge on the clone (so its not a loop) and remove the
1.346 +// extra backedge user.
1.347 +//
1.348 +// orig
1.349 +//
1.350 +// stmt1
1.351 +// |
1.352 +// v
1.353 +// loop predicate
1.354 +// |
1.355 +// v
1.356 +// loop<----+
1.357 +// | |
1.358 +// stmt2 |
1.359 +// | |
1.360 +// v |
1.361 +// if ^
1.362 +// / \ |
1.363 +// / \ |
1.364 +// v v |
1.365 +// false true |
1.366 +// / \ |
1.367 +// / ----+
1.368 +// |
1.369 +// v
1.370 +// exit
1.371 +//
1.372 +//
1.373 +// after clone loop
1.374 +//
1.375 +// stmt1
1.376 +// |
1.377 +// v
1.378 +// loop predicate
1.379 +// / \
1.380 +// clone / \ orig
1.381 +// / \
1.382 +// / \
1.383 +// v v
1.384 +// +---->loop clone loop<----+
1.385 +// | | | |
1.386 +// | stmt2 clone stmt2 |
1.387 +// | | | |
1.388 +// | v v |
1.389 +// ^ if clone If ^
1.390 +// | / \ / \ |
1.391 +// | / \ / \ |
1.392 +// | v v v v |
1.393 +// | true false false true |
1.394 +// | / \ / \ |
1.395 +// +---- \ / ----+
1.396 +// \ /
1.397 +// 1v v2
1.398 +// region
1.399 +// |
1.400 +// v
1.401 +// exit
1.402 +//
1.403 +//
1.404 +// after peel and predicate move
1.405 +//
1.406 +// stmt1
1.407 +// /
1.408 +// /
1.409 +// clone / orig
1.410 +// /
1.411 +// / +----------+
1.412 +// / | |
1.413 +// / loop predicate |
1.414 +// / | |
1.415 +// v v |
1.416 +// TOP-->loop clone loop<----+ |
1.417 +// | | | |
1.418 +// stmt2 clone stmt2 | |
1.419 +// | | | ^
1.420 +// v v | |
1.421 +// if clone If ^ |
1.422 +// / \ / \ | |
1.423 +// / \ / \ | |
1.424 +// v v v v | |
1.425 +// true false false true | |
1.426 +// | \ / \ | |
1.427 +// | \ / ----+ ^
1.428 +// | \ / |
1.429 +// | 1v v2 |
1.430 +// v region |
1.431 +// | | |
1.432 +// | v |
1.433 +// | exit |
1.434 +// | |
1.435 +// +--------------->-----------------+
1.436 +//
1.437 +//
1.438 +// final graph
1.439 +//
1.440 +// stmt1
1.441 +// |
1.442 +// v
1.443 +// stmt2 clone
1.444 +// |
1.445 +// v
1.446 +// if clone
1.447 +// / |
1.448 +// / |
1.449 +// v v
1.450 +// false true
1.451 +// | |
1.452 +// | v
1.453 +// | loop predicate
1.454 +// | |
1.455 +// | v
1.456 +// | loop<----+
1.457 +// | | |
1.458 +// | stmt2 |
1.459 +// | | |
1.460 +// | v |
1.461 +// v if ^
1.462 +// | / \ |
1.463 +// | / \ |
1.464 +// | v v |
1.465 +// | false true |
1.466 +// | | \ |
1.467 +// v v --+
1.468 +// region
1.469 +// |
1.470 +// v
1.471 +// exit
1.472 +//
1.473 +void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {
1.474 +
1.475 + C->set_major_progress();
1.476 + // Peeling a 'main' loop in a pre/main/post situation obfuscates the
1.477 + // 'pre' loop from the main and the 'pre' can no longer have it's
1.478 + // iterations adjusted. Therefore, we need to declare this loop as
1.479 + // no longer a 'main' loop; it will need new pre and post loops before
1.480 + // we can do further RCE.
1.481 +#ifndef PRODUCT
1.482 + if (TraceLoopOpts) {
1.483 + tty->print("Peel ");
1.484 + loop->dump_head();
1.485 + }
1.486 +#endif
1.487 + Node* head = loop->_head;
1.488 + bool counted_loop = head->is_CountedLoop();
1.489 + if (counted_loop) {
1.490 + CountedLoopNode *cl = head->as_CountedLoop();
1.491 + assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
1.492 + cl->set_trip_count(cl->trip_count() - 1);
1.493 + if (cl->is_main_loop()) {
1.494 + cl->set_normal_loop();
1.495 +#ifndef PRODUCT
1.496 + if (PrintOpto && VerifyLoopOptimizations) {
1.497 + tty->print("Peeling a 'main' loop; resetting to 'normal' ");
1.498 + loop->dump_head();
1.499 + }
1.500 +#endif
1.501 + }
1.502 + }
1.503 + Node* entry = head->in(LoopNode::EntryControl);
1.504 +
1.505 + // Step 1: Clone the loop body. The clone becomes the peeled iteration.
1.506 + // The pre-loop illegally has 2 control users (old & new loops).
1.507 + clone_loop( loop, old_new, dom_depth(head) );
1.508 +
1.509 + // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
1.510 + // Do this by making the old-loop fall-in edges act as if they came
1.511 + // around the loopback from the prior iteration (follow the old-loop
1.512 + // backedges) and then map to the new peeled iteration. This leaves
1.513 + // the pre-loop with only 1 user (the new peeled iteration), but the
1.514 + // peeled-loop backedge has 2 users.
1.515 + Node* new_entry = old_new[head->in(LoopNode::LoopBackControl)->_idx];
1.516 + _igvn.hash_delete(head);
1.517 + head->set_req(LoopNode::EntryControl, new_entry);
1.518 + for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) {
1.519 + Node* old = head->fast_out(j);
1.520 + if (old->in(0) == loop->_head && old->req() == 3 && old->is_Phi()) {
1.521 + Node* new_exit_value = old_new[old->in(LoopNode::LoopBackControl)->_idx];
1.522 + if (!new_exit_value ) // Backedge value is ALSO loop invariant?
1.523 + // Then loop body backedge value remains the same.
1.524 + new_exit_value = old->in(LoopNode::LoopBackControl);
1.525 + _igvn.hash_delete(old);
1.526 + old->set_req(LoopNode::EntryControl, new_exit_value);
1.527 + }
1.528 + }
1.529 +
1.530 +
1.531 + // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
1.532 + // extra backedge user.
1.533 + Node* new_head = old_new[head->_idx];
1.534 + _igvn.hash_delete(new_head);
1.535 + new_head->set_req(LoopNode::LoopBackControl, C->top());
1.536 + for (DUIterator_Fast j2max, j2 = new_head->fast_outs(j2max); j2 < j2max; j2++) {
1.537 + Node* use = new_head->fast_out(j2);
1.538 + if (use->in(0) == new_head && use->req() == 3 && use->is_Phi()) {
1.539 + _igvn.hash_delete(use);
1.540 + use->set_req(LoopNode::LoopBackControl, C->top());
1.541 + }
1.542 + }
1.543 +
1.544 +
1.545 + // Step 4: Correct dom-depth info. Set to loop-head depth.
1.546 + int dd = dom_depth(head);
1.547 + set_idom(head, head->in(1), dd);
1.548 + for (uint j3 = 0; j3 < loop->_body.size(); j3++) {
1.549 + Node *old = loop->_body.at(j3);
1.550 + Node *nnn = old_new[old->_idx];
1.551 + if (!has_ctrl(nnn))
1.552 + set_idom(nnn, idom(nnn), dd-1);
1.553 + }
1.554 +
1.555 + // Now force out all loop-invariant dominating tests. The optimizer
1.556 + // finds some, but we _know_ they are all useless.
1.557 + peeled_dom_test_elim(loop,old_new);
1.558 +
1.559 + loop->record_for_igvn();
1.560 +}
1.561 +
1.562 +#define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop
1.563 +
1.564 +//------------------------------policy_maximally_unroll------------------------
1.565 +// Calculate exact loop trip count and return true if loop can be maximally
1.566 +// unrolled.
1.567 +bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const {
1.568 + CountedLoopNode *cl = _head->as_CountedLoop();
1.569 + assert(cl->is_normal_loop(), "");
1.570 + if (!cl->is_valid_counted_loop())
1.571 + return false; // Malformed counted loop
1.572 +
1.573 + if (!cl->has_exact_trip_count()) {
1.574 + // Trip count is not exact.
1.575 + return false;
1.576 + }
1.577 +
1.578 + uint trip_count = cl->trip_count();
1.579 + // Note, max_juint is used to indicate unknown trip count.
1.580 + assert(trip_count > 1, "one iteration loop should be optimized out already");
1.581 + assert(trip_count < max_juint, "exact trip_count should be less than max_uint.");
1.582 +
1.583 + // Real policy: if we maximally unroll, does it get too big?
1.584 + // Allow the unrolled mess to get larger than standard loop
1.585 + // size. After all, it will no longer be a loop.
1.586 + uint body_size = _body.size();
1.587 + uint unroll_limit = (uint)LoopUnrollLimit * 4;
1.588 + assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
1.589 + if (trip_count > unroll_limit || body_size > unroll_limit) {
1.590 + return false;
1.591 + }
1.592 +
1.593 + // Fully unroll a loop with few iterations regardless next
1.594 + // conditions since following loop optimizations will split
1.595 + // such loop anyway (pre-main-post).
1.596 + if (trip_count <= 3)
1.597 + return true;
1.598 +
1.599 + // Take into account that after unroll conjoined heads and tails will fold,
1.600 + // otherwise policy_unroll() may allow more unrolling than max unrolling.
1.601 + uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count;
1.602 + uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE;
1.603 + if (body_size != tst_body_size) // Check for int overflow
1.604 + return false;
1.605 + if (new_body_size > unroll_limit ||
1.606 + // Unrolling can result in a large amount of node construction
1.607 + new_body_size >= MaxNodeLimit - (uint) phase->C->live_nodes()) {
1.608 + return false;
1.609 + }
1.610 +
1.611 + // Do not unroll a loop with String intrinsics code.
1.612 + // String intrinsics are large and have loops.
1.613 + for (uint k = 0; k < _body.size(); k++) {
1.614 + Node* n = _body.at(k);
1.615 + switch (n->Opcode()) {
1.616 + case Op_StrComp:
1.617 + case Op_StrEquals:
1.618 + case Op_StrIndexOf:
1.619 + case Op_EncodeISOArray:
1.620 + case Op_AryEq: {
1.621 + return false;
1.622 + }
1.623 +#if INCLUDE_RTM_OPT
1.624 + case Op_FastLock:
1.625 + case Op_FastUnlock: {
1.626 + // Don't unroll RTM locking code because it is large.
1.627 + if (UseRTMLocking) {
1.628 + return false;
1.629 + }
1.630 + }
1.631 +#endif
1.632 + } // switch
1.633 + }
1.634 +
1.635 + return true; // Do maximally unroll
1.636 +}
1.637 +
1.638 +
1.639 +//------------------------------policy_unroll----------------------------------
1.640 +// Return TRUE or FALSE if the loop should be unrolled or not. Unroll if
1.641 +// the loop is a CountedLoop and the body is small enough.
1.642 +bool IdealLoopTree::policy_unroll( PhaseIdealLoop *phase ) const {
1.643 +
1.644 + CountedLoopNode *cl = _head->as_CountedLoop();
1.645 + assert(cl->is_normal_loop() || cl->is_main_loop(), "");
1.646 +
1.647 + if (!cl->is_valid_counted_loop())
1.648 + return false; // Malformed counted loop
1.649 +
1.650 + // Protect against over-unrolling.
1.651 + // After split at least one iteration will be executed in pre-loop.
1.652 + if (cl->trip_count() <= (uint)(cl->is_normal_loop() ? 2 : 1)) return false;
1.653 +
1.654 + int future_unroll_ct = cl->unrolled_count() * 2;
1.655 + if (future_unroll_ct > LoopMaxUnroll) return false;
1.656 +
1.657 + // Check for initial stride being a small enough constant
1.658 + if (abs(cl->stride_con()) > (1<<2)*future_unroll_ct) return false;
1.659 +
1.660 + // Don't unroll if the next round of unrolling would push us
1.661 + // over the expected trip count of the loop. One is subtracted
1.662 + // from the expected trip count because the pre-loop normally
1.663 + // executes 1 iteration.
1.664 + if (UnrollLimitForProfileCheck > 0 &&
1.665 + cl->profile_trip_cnt() != COUNT_UNKNOWN &&
1.666 + future_unroll_ct > UnrollLimitForProfileCheck &&
1.667 + (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
1.668 + return false;
1.669 + }
1.670 +
1.671 + // When unroll count is greater than LoopUnrollMin, don't unroll if:
1.672 + // the residual iterations are more than 10% of the trip count
1.673 + // and rounds of "unroll,optimize" are not making significant progress
1.674 + // Progress defined as current size less than 20% larger than previous size.
1.675 + if (UseSuperWord && cl->node_count_before_unroll() > 0 &&
1.676 + future_unroll_ct > LoopUnrollMin &&
1.677 + (future_unroll_ct - 1) * 10.0 > cl->profile_trip_cnt() &&
1.678 + 1.2 * cl->node_count_before_unroll() < (double)_body.size()) {
1.679 + return false;
1.680 + }
1.681 +
1.682 + Node *init_n = cl->init_trip();
1.683 + Node *limit_n = cl->limit();
1.684 + int stride_con = cl->stride_con();
1.685 + // Non-constant bounds.
1.686 + // Protect against over-unrolling when init or/and limit are not constant
1.687 + // (so that trip_count's init value is maxint) but iv range is known.
1.688 + if (init_n == NULL || !init_n->is_Con() ||
1.689 + limit_n == NULL || !limit_n->is_Con()) {
1.690 + Node* phi = cl->phi();
1.691 + if (phi != NULL) {
1.692 + assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
1.693 + const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();
1.694 + int next_stride = stride_con * 2; // stride after this unroll
1.695 + if (next_stride > 0) {
1.696 + if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow
1.697 + iv_type->_lo + next_stride > iv_type->_hi) {
1.698 + return false; // over-unrolling
1.699 + }
1.700 + } else if (next_stride < 0) {
1.701 + if (iv_type->_hi + next_stride >= iv_type->_hi || // overflow
1.702 + iv_type->_hi + next_stride < iv_type->_lo) {
1.703 + return false; // over-unrolling
1.704 + }
1.705 + }
1.706 + }
1.707 + }
1.708 +
1.709 + // After unroll limit will be adjusted: new_limit = limit-stride.
1.710 + // Bailout if adjustment overflow.
1.711 + const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
1.712 + if (stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi) ||
1.713 + stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo))
1.714 + return false; // overflow
1.715 +
1.716 + // Adjust body_size to determine if we unroll or not
1.717 + uint body_size = _body.size();
1.718 + // Key test to unroll loop in CRC32 java code
1.719 + int xors_in_loop = 0;
1.720 + // Also count ModL, DivL and MulL which expand mightly
1.721 + for (uint k = 0; k < _body.size(); k++) {
1.722 + Node* n = _body.at(k);
1.723 + switch (n->Opcode()) {
1.724 + case Op_XorI: xors_in_loop++; break; // CRC32 java code
1.725 + case Op_ModL: body_size += 30; break;
1.726 + case Op_DivL: body_size += 30; break;
1.727 + case Op_MulL: body_size += 10; break;
1.728 + case Op_StrComp:
1.729 + case Op_StrEquals:
1.730 + case Op_StrIndexOf:
1.731 + case Op_EncodeISOArray:
1.732 + case Op_AryEq: {
1.733 + // Do not unroll a loop with String intrinsics code.
1.734 + // String intrinsics are large and have loops.
1.735 + return false;
1.736 + }
1.737 +#if INCLUDE_RTM_OPT
1.738 + case Op_FastLock:
1.739 + case Op_FastUnlock: {
1.740 + // Don't unroll RTM locking code because it is large.
1.741 + if (UseRTMLocking) {
1.742 + return false;
1.743 + }
1.744 + }
1.745 +#endif
1.746 + } // switch
1.747 + }
1.748 +
1.749 + // Check for being too big
1.750 + if (body_size > (uint)LoopUnrollLimit) {
1.751 + if (xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true;
1.752 + // Normal case: loop too big
1.753 + return false;
1.754 + }
1.755 +
1.756 + // Unroll once! (Each trip will soon do double iterations)
1.757 + return true;
1.758 +}
1.759 +
1.760 +//------------------------------policy_align-----------------------------------
1.761 +// Return TRUE or FALSE if the loop should be cache-line aligned. Gather the
1.762 +// expression that does the alignment. Note that only one array base can be
1.763 +// aligned in a loop (unless the VM guarantees mutual alignment). Note that
1.764 +// if we vectorize short memory ops into longer memory ops, we may want to
1.765 +// increase alignment.
1.766 +bool IdealLoopTree::policy_align( PhaseIdealLoop *phase ) const {
1.767 + return false;
1.768 +}
1.769 +
1.770 +//------------------------------policy_range_check-----------------------------
1.771 +// Return TRUE or FALSE if the loop should be range-check-eliminated.
1.772 +// Actually we do iteration-splitting, a more powerful form of RCE.
1.773 +bool IdealLoopTree::policy_range_check( PhaseIdealLoop *phase ) const {
1.774 + if (!RangeCheckElimination) return false;
1.775 +
1.776 + CountedLoopNode *cl = _head->as_CountedLoop();
1.777 + // If we unrolled with no intention of doing RCE and we later
1.778 + // changed our minds, we got no pre-loop. Either we need to
1.779 + // make a new pre-loop, or we gotta disallow RCE.
1.780 + if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
1.781 + Node *trip_counter = cl->phi();
1.782 +
1.783 + // Check loop body for tests of trip-counter plus loop-invariant vs
1.784 + // loop-invariant.
1.785 + for (uint i = 0; i < _body.size(); i++) {
1.786 + Node *iff = _body[i];
1.787 + if (iff->Opcode() == Op_If) { // Test?
1.788 +
1.789 + // Comparing trip+off vs limit
1.790 + Node *bol = iff->in(1);
1.791 + if (bol->req() != 2) continue; // dead constant test
1.792 + if (!bol->is_Bool()) {
1.793 + assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only");
1.794 + continue;
1.795 + }
1.796 + if (bol->as_Bool()->_test._test == BoolTest::ne)
1.797 + continue; // not RC
1.798 +
1.799 + Node *cmp = bol->in(1);
1.800 + Node *rc_exp = cmp->in(1);
1.801 + Node *limit = cmp->in(2);
1.802 +
1.803 + Node *limit_c = phase->get_ctrl(limit);
1.804 + if( limit_c == phase->C->top() )
1.805 + return false; // Found dead test on live IF? No RCE!
1.806 + if( is_member(phase->get_loop(limit_c) ) ) {
1.807 + // Compare might have operands swapped; commute them
1.808 + rc_exp = cmp->in(2);
1.809 + limit = cmp->in(1);
1.810 + limit_c = phase->get_ctrl(limit);
1.811 + if( is_member(phase->get_loop(limit_c) ) )
1.812 + continue; // Both inputs are loop varying; cannot RCE
1.813 + }
1.814 +
1.815 + if (!phase->is_scaled_iv_plus_offset(rc_exp, trip_counter, NULL, NULL)) {
1.816 + continue;
1.817 + }
1.818 + // Yeah! Found a test like 'trip+off vs limit'
1.819 + // Test is an IfNode, has 2 projections. If BOTH are in the loop
1.820 + // we need loop unswitching instead of iteration splitting.
1.821 + if( is_loop_exit(iff) )
1.822 + return true; // Found reason to split iterations
1.823 + } // End of is IF
1.824 + }
1.825 +
1.826 + return false;
1.827 +}
1.828 +
1.829 +//------------------------------policy_peel_only-------------------------------
1.830 +// Return TRUE or FALSE if the loop should NEVER be RCE'd or aligned. Useful
1.831 +// for unrolling loops with NO array accesses.
1.832 +bool IdealLoopTree::policy_peel_only( PhaseIdealLoop *phase ) const {
1.833 +
1.834 + for( uint i = 0; i < _body.size(); i++ )
1.835 + if( _body[i]->is_Mem() )
1.836 + return false;
1.837 +
1.838 + // No memory accesses at all!
1.839 + return true;
1.840 +}
1.841 +
1.842 +//------------------------------clone_up_backedge_goo--------------------------
1.843 +// If Node n lives in the back_ctrl block and cannot float, we clone a private
1.844 +// version of n in preheader_ctrl block and return that, otherwise return n.
1.845 +Node *PhaseIdealLoop::clone_up_backedge_goo( Node *back_ctrl, Node *preheader_ctrl, Node *n, VectorSet &visited, Node_Stack &clones ) {
1.846 + if( get_ctrl(n) != back_ctrl ) return n;
1.847 +
1.848 + // Only visit once
1.849 + if (visited.test_set(n->_idx)) {
1.850 + Node *x = clones.find(n->_idx);
1.851 + if (x != NULL)
1.852 + return x;
1.853 + return n;
1.854 + }
1.855 +
1.856 + Node *x = NULL; // If required, a clone of 'n'
1.857 + // Check for 'n' being pinned in the backedge.
1.858 + if( n->in(0) && n->in(0) == back_ctrl ) {
1.859 + assert(clones.find(n->_idx) == NULL, "dead loop");
1.860 + x = n->clone(); // Clone a copy of 'n' to preheader
1.861 + clones.push(x, n->_idx);
1.862 + x->set_req( 0, preheader_ctrl ); // Fix x's control input to preheader
1.863 + }
1.864 +
1.865 + // Recursive fixup any other input edges into x.
1.866 + // If there are no changes we can just return 'n', otherwise
1.867 + // we need to clone a private copy and change it.
1.868 + for( uint i = 1; i < n->req(); i++ ) {
1.869 + Node *g = clone_up_backedge_goo( back_ctrl, preheader_ctrl, n->in(i), visited, clones );
1.870 + if( g != n->in(i) ) {
1.871 + if( !x ) {
1.872 + assert(clones.find(n->_idx) == NULL, "dead loop");
1.873 + x = n->clone();
1.874 + clones.push(x, n->_idx);
1.875 + }
1.876 + x->set_req(i, g);
1.877 + }
1.878 + }
1.879 + if( x ) { // x can legally float to pre-header location
1.880 + register_new_node( x, preheader_ctrl );
1.881 + return x;
1.882 + } else { // raise n to cover LCA of uses
1.883 + set_ctrl( n, find_non_split_ctrl(back_ctrl->in(0)) );
1.884 + }
1.885 + return n;
1.886 +}
1.887 +
1.888 +//------------------------------insert_pre_post_loops--------------------------
1.889 +// Insert pre and post loops. If peel_only is set, the pre-loop can not have
1.890 +// more iterations added. It acts as a 'peel' only, no lower-bound RCE, no
1.891 +// alignment. Useful to unroll loops that do no array accesses.
1.892 +void PhaseIdealLoop::insert_pre_post_loops( IdealLoopTree *loop, Node_List &old_new, bool peel_only ) {
1.893 +
1.894 +#ifndef PRODUCT
1.895 + if (TraceLoopOpts) {
1.896 + if (peel_only)
1.897 + tty->print("PeelMainPost ");
1.898 + else
1.899 + tty->print("PreMainPost ");
1.900 + loop->dump_head();
1.901 + }
1.902 +#endif
1.903 + C->set_major_progress();
1.904 +
1.905 + // Find common pieces of the loop being guarded with pre & post loops
1.906 + CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1.907 + assert( main_head->is_normal_loop(), "" );
1.908 + CountedLoopEndNode *main_end = main_head->loopexit();
1.909 + guarantee(main_end != NULL, "no loop exit node");
1.910 + assert( main_end->outcnt() == 2, "1 true, 1 false path only" );
1.911 + uint dd_main_head = dom_depth(main_head);
1.912 + uint max = main_head->outcnt();
1.913 +
1.914 + Node *pre_header= main_head->in(LoopNode::EntryControl);
1.915 + Node *init = main_head->init_trip();
1.916 + Node *incr = main_end ->incr();
1.917 + Node *limit = main_end ->limit();
1.918 + Node *stride = main_end ->stride();
1.919 + Node *cmp = main_end ->cmp_node();
1.920 + BoolTest::mask b_test = main_end->test_trip();
1.921 +
1.922 + // Need only 1 user of 'bol' because I will be hacking the loop bounds.
1.923 + Node *bol = main_end->in(CountedLoopEndNode::TestValue);
1.924 + if( bol->outcnt() != 1 ) {
1.925 + bol = bol->clone();
1.926 + register_new_node(bol,main_end->in(CountedLoopEndNode::TestControl));
1.927 + _igvn.hash_delete(main_end);
1.928 + main_end->set_req(CountedLoopEndNode::TestValue, bol);
1.929 + }
1.930 + // Need only 1 user of 'cmp' because I will be hacking the loop bounds.
1.931 + if( cmp->outcnt() != 1 ) {
1.932 + cmp = cmp->clone();
1.933 + register_new_node(cmp,main_end->in(CountedLoopEndNode::TestControl));
1.934 + _igvn.hash_delete(bol);
1.935 + bol->set_req(1, cmp);
1.936 + }
1.937 +
1.938 + //------------------------------
1.939 + // Step A: Create Post-Loop.
1.940 + Node* main_exit = main_end->proj_out(false);
1.941 + assert( main_exit->Opcode() == Op_IfFalse, "" );
1.942 + int dd_main_exit = dom_depth(main_exit);
1.943 +
1.944 + // Step A1: Clone the loop body. The clone becomes the post-loop. The main
1.945 + // loop pre-header illegally has 2 control users (old & new loops).
1.946 + clone_loop( loop, old_new, dd_main_exit );
1.947 + assert( old_new[main_end ->_idx]->Opcode() == Op_CountedLoopEnd, "" );
1.948 + CountedLoopNode *post_head = old_new[main_head->_idx]->as_CountedLoop();
1.949 + post_head->set_post_loop(main_head);
1.950 +
1.951 + // Reduce the post-loop trip count.
1.952 + CountedLoopEndNode* post_end = old_new[main_end ->_idx]->as_CountedLoopEnd();
1.953 + post_end->_prob = PROB_FAIR;
1.954 +
1.955 + // Build the main-loop normal exit.
1.956 + IfFalseNode *new_main_exit = new (C) IfFalseNode(main_end);
1.957 + _igvn.register_new_node_with_optimizer( new_main_exit );
1.958 + set_idom(new_main_exit, main_end, dd_main_exit );
1.959 + set_loop(new_main_exit, loop->_parent);
1.960 +
1.961 + // Step A2: Build a zero-trip guard for the post-loop. After leaving the
1.962 + // main-loop, the post-loop may not execute at all. We 'opaque' the incr
1.963 + // (the main-loop trip-counter exit value) because we will be changing
1.964 + // the exit value (via unrolling) so we cannot constant-fold away the zero
1.965 + // trip guard until all unrolling is done.
1.966 + Node *zer_opaq = new (C) Opaque1Node(C, incr);
1.967 + Node *zer_cmp = new (C) CmpINode( zer_opaq, limit );
1.968 + Node *zer_bol = new (C) BoolNode( zer_cmp, b_test );
1.969 + register_new_node( zer_opaq, new_main_exit );
1.970 + register_new_node( zer_cmp , new_main_exit );
1.971 + register_new_node( zer_bol , new_main_exit );
1.972 +
1.973 + // Build the IfNode
1.974 + IfNode *zer_iff = new (C) IfNode( new_main_exit, zer_bol, PROB_FAIR, COUNT_UNKNOWN );
1.975 + _igvn.register_new_node_with_optimizer( zer_iff );
1.976 + set_idom(zer_iff, new_main_exit, dd_main_exit);
1.977 + set_loop(zer_iff, loop->_parent);
1.978 +
1.979 + // Plug in the false-path, taken if we need to skip post-loop
1.980 + _igvn.replace_input_of(main_exit, 0, zer_iff);
1.981 + set_idom(main_exit, zer_iff, dd_main_exit);
1.982 + set_idom(main_exit->unique_out(), zer_iff, dd_main_exit);
1.983 + // Make the true-path, must enter the post loop
1.984 + Node *zer_taken = new (C) IfTrueNode( zer_iff );
1.985 + _igvn.register_new_node_with_optimizer( zer_taken );
1.986 + set_idom(zer_taken, zer_iff, dd_main_exit);
1.987 + set_loop(zer_taken, loop->_parent);
1.988 + // Plug in the true path
1.989 + _igvn.hash_delete( post_head );
1.990 + post_head->set_req(LoopNode::EntryControl, zer_taken);
1.991 + set_idom(post_head, zer_taken, dd_main_exit);
1.992 +
1.993 + Arena *a = Thread::current()->resource_area();
1.994 + VectorSet visited(a);
1.995 + Node_Stack clones(a, main_head->back_control()->outcnt());
1.996 + // Step A3: Make the fall-in values to the post-loop come from the
1.997 + // fall-out values of the main-loop.
1.998 + for (DUIterator_Fast imax, i = main_head->fast_outs(imax); i < imax; i++) {
1.999 + Node* main_phi = main_head->fast_out(i);
1.1000 + if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() >0 ) {
1.1001 + Node *post_phi = old_new[main_phi->_idx];
1.1002 + Node *fallmain = clone_up_backedge_goo(main_head->back_control(),
1.1003 + post_head->init_control(),
1.1004 + main_phi->in(LoopNode::LoopBackControl),
1.1005 + visited, clones);
1.1006 + _igvn.hash_delete(post_phi);
1.1007 + post_phi->set_req( LoopNode::EntryControl, fallmain );
1.1008 + }
1.1009 + }
1.1010 +
1.1011 + // Update local caches for next stanza
1.1012 + main_exit = new_main_exit;
1.1013 +
1.1014 +
1.1015 + //------------------------------
1.1016 + // Step B: Create Pre-Loop.
1.1017 +
1.1018 + // Step B1: Clone the loop body. The clone becomes the pre-loop. The main
1.1019 + // loop pre-header illegally has 2 control users (old & new loops).
1.1020 + clone_loop( loop, old_new, dd_main_head );
1.1021 + CountedLoopNode* pre_head = old_new[main_head->_idx]->as_CountedLoop();
1.1022 + CountedLoopEndNode* pre_end = old_new[main_end ->_idx]->as_CountedLoopEnd();
1.1023 + pre_head->set_pre_loop(main_head);
1.1024 + Node *pre_incr = old_new[incr->_idx];
1.1025 +
1.1026 + // Reduce the pre-loop trip count.
1.1027 + pre_end->_prob = PROB_FAIR;
1.1028 +
1.1029 + // Find the pre-loop normal exit.
1.1030 + Node* pre_exit = pre_end->proj_out(false);
1.1031 + assert( pre_exit->Opcode() == Op_IfFalse, "" );
1.1032 + IfFalseNode *new_pre_exit = new (C) IfFalseNode(pre_end);
1.1033 + _igvn.register_new_node_with_optimizer( new_pre_exit );
1.1034 + set_idom(new_pre_exit, pre_end, dd_main_head);
1.1035 + set_loop(new_pre_exit, loop->_parent);
1.1036 +
1.1037 + // Step B2: Build a zero-trip guard for the main-loop. After leaving the
1.1038 + // pre-loop, the main-loop may not execute at all. Later in life this
1.1039 + // zero-trip guard will become the minimum-trip guard when we unroll
1.1040 + // the main-loop.
1.1041 + Node *min_opaq = new (C) Opaque1Node(C, limit);
1.1042 + Node *min_cmp = new (C) CmpINode( pre_incr, min_opaq );
1.1043 + Node *min_bol = new (C) BoolNode( min_cmp, b_test );
1.1044 + register_new_node( min_opaq, new_pre_exit );
1.1045 + register_new_node( min_cmp , new_pre_exit );
1.1046 + register_new_node( min_bol , new_pre_exit );
1.1047 +
1.1048 + // Build the IfNode (assume the main-loop is executed always).
1.1049 + IfNode *min_iff = new (C) IfNode( new_pre_exit, min_bol, PROB_ALWAYS, COUNT_UNKNOWN );
1.1050 + _igvn.register_new_node_with_optimizer( min_iff );
1.1051 + set_idom(min_iff, new_pre_exit, dd_main_head);
1.1052 + set_loop(min_iff, loop->_parent);
1.1053 +
1.1054 + // Plug in the false-path, taken if we need to skip main-loop
1.1055 + _igvn.hash_delete( pre_exit );
1.1056 + pre_exit->set_req(0, min_iff);
1.1057 + set_idom(pre_exit, min_iff, dd_main_head);
1.1058 + set_idom(pre_exit->unique_out(), min_iff, dd_main_head);
1.1059 + // Make the true-path, must enter the main loop
1.1060 + Node *min_taken = new (C) IfTrueNode( min_iff );
1.1061 + _igvn.register_new_node_with_optimizer( min_taken );
1.1062 + set_idom(min_taken, min_iff, dd_main_head);
1.1063 + set_loop(min_taken, loop->_parent);
1.1064 + // Plug in the true path
1.1065 + _igvn.hash_delete( main_head );
1.1066 + main_head->set_req(LoopNode::EntryControl, min_taken);
1.1067 + set_idom(main_head, min_taken, dd_main_head);
1.1068 +
1.1069 + visited.Clear();
1.1070 + clones.clear();
1.1071 + // Step B3: Make the fall-in values to the main-loop come from the
1.1072 + // fall-out values of the pre-loop.
1.1073 + for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {
1.1074 + Node* main_phi = main_head->fast_out(i2);
1.1075 + if( main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0 ) {
1.1076 + Node *pre_phi = old_new[main_phi->_idx];
1.1077 + Node *fallpre = clone_up_backedge_goo(pre_head->back_control(),
1.1078 + main_head->init_control(),
1.1079 + pre_phi->in(LoopNode::LoopBackControl),
1.1080 + visited, clones);
1.1081 + _igvn.hash_delete(main_phi);
1.1082 + main_phi->set_req( LoopNode::EntryControl, fallpre );
1.1083 + }
1.1084 + }
1.1085 +
1.1086 + // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1.1087 + // RCE and alignment may change this later.
1.1088 + Node *cmp_end = pre_end->cmp_node();
1.1089 + assert( cmp_end->in(2) == limit, "" );
1.1090 + Node *pre_limit = new (C) AddINode( init, stride );
1.1091 +
1.1092 + // Save the original loop limit in this Opaque1 node for
1.1093 + // use by range check elimination.
1.1094 + Node *pre_opaq = new (C) Opaque1Node(C, pre_limit, limit);
1.1095 +
1.1096 + register_new_node( pre_limit, pre_head->in(0) );
1.1097 + register_new_node( pre_opaq , pre_head->in(0) );
1.1098 +
1.1099 + // Since no other users of pre-loop compare, I can hack limit directly
1.1100 + assert( cmp_end->outcnt() == 1, "no other users" );
1.1101 + _igvn.hash_delete(cmp_end);
1.1102 + cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1.1103 +
1.1104 + // Special case for not-equal loop bounds:
1.1105 + // Change pre loop test, main loop test, and the
1.1106 + // main loop guard test to use lt or gt depending on stride
1.1107 + // direction:
1.1108 + // positive stride use <
1.1109 + // negative stride use >
1.1110 + //
1.1111 + // not-equal test is kept for post loop to handle case
1.1112 + // when init > limit when stride > 0 (and reverse).
1.1113 +
1.1114 + if (pre_end->in(CountedLoopEndNode::TestValue)->as_Bool()->_test._test == BoolTest::ne) {
1.1115 +
1.1116 + BoolTest::mask new_test = (main_end->stride_con() > 0) ? BoolTest::lt : BoolTest::gt;
1.1117 + // Modify pre loop end condition
1.1118 + Node* pre_bol = pre_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1.1119 + BoolNode* new_bol0 = new (C) BoolNode(pre_bol->in(1), new_test);
1.1120 + register_new_node( new_bol0, pre_head->in(0) );
1.1121 + _igvn.hash_delete(pre_end);
1.1122 + pre_end->set_req(CountedLoopEndNode::TestValue, new_bol0);
1.1123 + // Modify main loop guard condition
1.1124 + assert(min_iff->in(CountedLoopEndNode::TestValue) == min_bol, "guard okay");
1.1125 + BoolNode* new_bol1 = new (C) BoolNode(min_bol->in(1), new_test);
1.1126 + register_new_node( new_bol1, new_pre_exit );
1.1127 + _igvn.hash_delete(min_iff);
1.1128 + min_iff->set_req(CountedLoopEndNode::TestValue, new_bol1);
1.1129 + // Modify main loop end condition
1.1130 + BoolNode* main_bol = main_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1.1131 + BoolNode* new_bol2 = new (C) BoolNode(main_bol->in(1), new_test);
1.1132 + register_new_node( new_bol2, main_end->in(CountedLoopEndNode::TestControl) );
1.1133 + _igvn.hash_delete(main_end);
1.1134 + main_end->set_req(CountedLoopEndNode::TestValue, new_bol2);
1.1135 + }
1.1136 +
1.1137 + // Flag main loop
1.1138 + main_head->set_main_loop();
1.1139 + if( peel_only ) main_head->set_main_no_pre_loop();
1.1140 +
1.1141 + // Subtract a trip count for the pre-loop.
1.1142 + main_head->set_trip_count(main_head->trip_count() - 1);
1.1143 +
1.1144 + // It's difficult to be precise about the trip-counts
1.1145 + // for the pre/post loops. They are usually very short,
1.1146 + // so guess that 4 trips is a reasonable value.
1.1147 + post_head->set_profile_trip_cnt(4.0);
1.1148 + pre_head->set_profile_trip_cnt(4.0);
1.1149 +
1.1150 + // Now force out all loop-invariant dominating tests. The optimizer
1.1151 + // finds some, but we _know_ they are all useless.
1.1152 + peeled_dom_test_elim(loop,old_new);
1.1153 + loop->record_for_igvn();
1.1154 +}
1.1155 +
1.1156 +//------------------------------is_invariant-----------------------------
1.1157 +// Return true if n is invariant
1.1158 +bool IdealLoopTree::is_invariant(Node* n) const {
1.1159 + Node *n_c = _phase->has_ctrl(n) ? _phase->get_ctrl(n) : n;
1.1160 + if (n_c->is_top()) return false;
1.1161 + return !is_member(_phase->get_loop(n_c));
1.1162 +}
1.1163 +
1.1164 +
1.1165 +//------------------------------do_unroll--------------------------------------
1.1166 +// Unroll the loop body one step - make each trip do 2 iterations.
1.1167 +void PhaseIdealLoop::do_unroll( IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip ) {
1.1168 + assert(LoopUnrollLimit, "");
1.1169 + CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
1.1170 + CountedLoopEndNode *loop_end = loop_head->loopexit();
1.1171 + assert(loop_end, "");
1.1172 +#ifndef PRODUCT
1.1173 + if (PrintOpto && VerifyLoopOptimizations) {
1.1174 + tty->print("Unrolling ");
1.1175 + loop->dump_head();
1.1176 + } else if (TraceLoopOpts) {
1.1177 + if (loop_head->trip_count() < (uint)LoopUnrollLimit) {
1.1178 + tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count());
1.1179 + } else {
1.1180 + tty->print("Unroll %d ", loop_head->unrolled_count()*2);
1.1181 + }
1.1182 + loop->dump_head();
1.1183 + }
1.1184 +#endif
1.1185 +
1.1186 + // Remember loop node count before unrolling to detect
1.1187 + // if rounds of unroll,optimize are making progress
1.1188 + loop_head->set_node_count_before_unroll(loop->_body.size());
1.1189 +
1.1190 + Node *ctrl = loop_head->in(LoopNode::EntryControl);
1.1191 + Node *limit = loop_head->limit();
1.1192 + Node *init = loop_head->init_trip();
1.1193 + Node *stride = loop_head->stride();
1.1194 +
1.1195 + Node *opaq = NULL;
1.1196 + if (adjust_min_trip) { // If not maximally unrolling, need adjustment
1.1197 + // Search for zero-trip guard.
1.1198 + assert( loop_head->is_main_loop(), "" );
1.1199 + assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" );
1.1200 + Node *iff = ctrl->in(0);
1.1201 + assert( iff->Opcode() == Op_If, "" );
1.1202 + Node *bol = iff->in(1);
1.1203 + assert( bol->Opcode() == Op_Bool, "" );
1.1204 + Node *cmp = bol->in(1);
1.1205 + assert( cmp->Opcode() == Op_CmpI, "" );
1.1206 + opaq = cmp->in(2);
1.1207 + // Occasionally it's possible for a zero-trip guard Opaque1 node to be
1.1208 + // optimized away and then another round of loop opts attempted.
1.1209 + // We can not optimize this particular loop in that case.
1.1210 + if (opaq->Opcode() != Op_Opaque1)
1.1211 + return; // Cannot find zero-trip guard! Bail out!
1.1212 + // Zero-trip test uses an 'opaque' node which is not shared.
1.1213 + assert(opaq->outcnt() == 1 && opaq->in(1) == limit, "");
1.1214 + }
1.1215 +
1.1216 + C->set_major_progress();
1.1217 +
1.1218 + Node* new_limit = NULL;
1.1219 + if (UnrollLimitCheck) {
1.1220 + int stride_con = stride->get_int();
1.1221 + int stride_p = (stride_con > 0) ? stride_con : -stride_con;
1.1222 + uint old_trip_count = loop_head->trip_count();
1.1223 + // Verify that unroll policy result is still valid.
1.1224 + assert(old_trip_count > 1 &&
1.1225 + (!adjust_min_trip || stride_p <= (1<<3)*loop_head->unrolled_count()), "sanity");
1.1226 +
1.1227 + // Adjust loop limit to keep valid iterations number after unroll.
1.1228 + // Use (limit - stride) instead of (((limit - init)/stride) & (-2))*stride
1.1229 + // which may overflow.
1.1230 + if (!adjust_min_trip) {
1.1231 + assert(old_trip_count > 1 && (old_trip_count & 1) == 0,
1.1232 + "odd trip count for maximally unroll");
1.1233 + // Don't need to adjust limit for maximally unroll since trip count is even.
1.1234 + } else if (loop_head->has_exact_trip_count() && init->is_Con()) {
1.1235 + // Loop's limit is constant. Loop's init could be constant when pre-loop
1.1236 + // become peeled iteration.
1.1237 + jlong init_con = init->get_int();
1.1238 + // We can keep old loop limit if iterations count stays the same:
1.1239 + // old_trip_count == new_trip_count * 2
1.1240 + // Note: since old_trip_count >= 2 then new_trip_count >= 1
1.1241 + // so we also don't need to adjust zero trip test.
1.1242 + jlong limit_con = limit->get_int();
1.1243 + // (stride_con*2) not overflow since stride_con <= 8.
1.1244 + int new_stride_con = stride_con * 2;
1.1245 + int stride_m = new_stride_con - (stride_con > 0 ? 1 : -1);
1.1246 + jlong trip_count = (limit_con - init_con + stride_m)/new_stride_con;
1.1247 + // New trip count should satisfy next conditions.
1.1248 + assert(trip_count > 0 && (julong)trip_count < (julong)max_juint/2, "sanity");
1.1249 + uint new_trip_count = (uint)trip_count;
1.1250 + adjust_min_trip = (old_trip_count != new_trip_count*2);
1.1251 + }
1.1252 +
1.1253 + if (adjust_min_trip) {
1.1254 + // Step 2: Adjust the trip limit if it is called for.
1.1255 + // The adjustment amount is -stride. Need to make sure if the
1.1256 + // adjustment underflows or overflows, then the main loop is skipped.
1.1257 + Node* cmp = loop_end->cmp_node();
1.1258 + assert(cmp->in(2) == limit, "sanity");
1.1259 + assert(opaq != NULL && opaq->in(1) == limit, "sanity");
1.1260 +
1.1261 + // Verify that policy_unroll result is still valid.
1.1262 + const TypeInt* limit_type = _igvn.type(limit)->is_int();
1.1263 + assert(stride_con > 0 && ((limit_type->_hi - stride_con) < limit_type->_hi) ||
1.1264 + stride_con < 0 && ((limit_type->_lo - stride_con) > limit_type->_lo), "sanity");
1.1265 +
1.1266 + if (limit->is_Con()) {
1.1267 + // The check in policy_unroll and the assert above guarantee
1.1268 + // no underflow if limit is constant.
1.1269 + new_limit = _igvn.intcon(limit->get_int() - stride_con);
1.1270 + set_ctrl(new_limit, C->root());
1.1271 + } else {
1.1272 + // Limit is not constant.
1.1273 + if (loop_head->unrolled_count() == 1) { // only for first unroll
1.1274 + // Separate limit by Opaque node in case it is an incremented
1.1275 + // variable from previous loop to avoid using pre-incremented
1.1276 + // value which could increase register pressure.
1.1277 + // Otherwise reorg_offsets() optimization will create a separate
1.1278 + // Opaque node for each use of trip-counter and as result
1.1279 + // zero trip guard limit will be different from loop limit.
1.1280 + assert(has_ctrl(opaq), "should have it");
1.1281 + Node* opaq_ctrl = get_ctrl(opaq);
1.1282 + limit = new (C) Opaque2Node( C, limit );
1.1283 + register_new_node( limit, opaq_ctrl );
1.1284 + }
1.1285 + if (stride_con > 0 && ((limit_type->_lo - stride_con) < limit_type->_lo) ||
1.1286 + stride_con < 0 && ((limit_type->_hi - stride_con) > limit_type->_hi)) {
1.1287 + // No underflow.
1.1288 + new_limit = new (C) SubINode(limit, stride);
1.1289 + } else {
1.1290 + // (limit - stride) may underflow.
1.1291 + // Clamp the adjustment value with MININT or MAXINT:
1.1292 + //
1.1293 + // new_limit = limit-stride
1.1294 + // if (stride > 0)
1.1295 + // new_limit = (limit < new_limit) ? MININT : new_limit;
1.1296 + // else
1.1297 + // new_limit = (limit > new_limit) ? MAXINT : new_limit;
1.1298 + //
1.1299 + BoolTest::mask bt = loop_end->test_trip();
1.1300 + assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
1.1301 + Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint);
1.1302 + set_ctrl(adj_max, C->root());
1.1303 + Node* old_limit = NULL;
1.1304 + Node* adj_limit = NULL;
1.1305 + Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL;
1.1306 + if (loop_head->unrolled_count() > 1 &&
1.1307 + limit->is_CMove() && limit->Opcode() == Op_CMoveI &&
1.1308 + limit->in(CMoveNode::IfTrue) == adj_max &&
1.1309 + bol->as_Bool()->_test._test == bt &&
1.1310 + bol->in(1)->Opcode() == Op_CmpI &&
1.1311 + bol->in(1)->in(2) == limit->in(CMoveNode::IfFalse)) {
1.1312 + // Loop was unrolled before.
1.1313 + // Optimize the limit to avoid nested CMove:
1.1314 + // use original limit as old limit.
1.1315 + old_limit = bol->in(1)->in(1);
1.1316 + // Adjust previous adjusted limit.
1.1317 + adj_limit = limit->in(CMoveNode::IfFalse);
1.1318 + adj_limit = new (C) SubINode(adj_limit, stride);
1.1319 + } else {
1.1320 + old_limit = limit;
1.1321 + adj_limit = new (C) SubINode(limit, stride);
1.1322 + }
1.1323 + assert(old_limit != NULL && adj_limit != NULL, "");
1.1324 + register_new_node( adj_limit, ctrl ); // adjust amount
1.1325 + Node* adj_cmp = new (C) CmpINode(old_limit, adj_limit);
1.1326 + register_new_node( adj_cmp, ctrl );
1.1327 + Node* adj_bool = new (C) BoolNode(adj_cmp, bt);
1.1328 + register_new_node( adj_bool, ctrl );
1.1329 + new_limit = new (C) CMoveINode(adj_bool, adj_limit, adj_max, TypeInt::INT);
1.1330 + }
1.1331 + register_new_node(new_limit, ctrl);
1.1332 + }
1.1333 + assert(new_limit != NULL, "");
1.1334 + // Replace in loop test.
1.1335 + assert(loop_end->in(1)->in(1) == cmp, "sanity");
1.1336 + if (cmp->outcnt() == 1 && loop_end->in(1)->outcnt() == 1) {
1.1337 + // Don't need to create new test since only one user.
1.1338 + _igvn.hash_delete(cmp);
1.1339 + cmp->set_req(2, new_limit);
1.1340 + } else {
1.1341 + // Create new test since it is shared.
1.1342 + Node* ctrl2 = loop_end->in(0);
1.1343 + Node* cmp2 = cmp->clone();
1.1344 + cmp2->set_req(2, new_limit);
1.1345 + register_new_node(cmp2, ctrl2);
1.1346 + Node* bol2 = loop_end->in(1)->clone();
1.1347 + bol2->set_req(1, cmp2);
1.1348 + register_new_node(bol2, ctrl2);
1.1349 + _igvn.hash_delete(loop_end);
1.1350 + loop_end->set_req(1, bol2);
1.1351 + }
1.1352 + // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1.1353 + // Make it a 1-trip test (means at least 2 trips).
1.1354 +
1.1355 + // Guard test uses an 'opaque' node which is not shared. Hence I
1.1356 + // can edit it's inputs directly. Hammer in the new limit for the
1.1357 + // minimum-trip guard.
1.1358 + assert(opaq->outcnt() == 1, "");
1.1359 + _igvn.hash_delete(opaq);
1.1360 + opaq->set_req(1, new_limit);
1.1361 + }
1.1362 +
1.1363 + // Adjust max trip count. The trip count is intentionally rounded
1.1364 + // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll,
1.1365 + // the main, unrolled, part of the loop will never execute as it is protected
1.1366 + // by the min-trip test. See bug 4834191 for a case where we over-unrolled
1.1367 + // and later determined that part of the unrolled loop was dead.
1.1368 + loop_head->set_trip_count(old_trip_count / 2);
1.1369 +
1.1370 + // Double the count of original iterations in the unrolled loop body.
1.1371 + loop_head->double_unrolled_count();
1.1372 +
1.1373 + } else { // LoopLimitCheck
1.1374 +
1.1375 + // Adjust max trip count. The trip count is intentionally rounded
1.1376 + // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll,
1.1377 + // the main, unrolled, part of the loop will never execute as it is protected
1.1378 + // by the min-trip test. See bug 4834191 for a case where we over-unrolled
1.1379 + // and later determined that part of the unrolled loop was dead.
1.1380 + loop_head->set_trip_count(loop_head->trip_count() / 2);
1.1381 +
1.1382 + // Double the count of original iterations in the unrolled loop body.
1.1383 + loop_head->double_unrolled_count();
1.1384 +
1.1385 + // -----------
1.1386 + // Step 2: Cut back the trip counter for an unroll amount of 2.
1.1387 + // Loop will normally trip (limit - init)/stride_con. Since it's a
1.1388 + // CountedLoop this is exact (stride divides limit-init exactly).
1.1389 + // We are going to double the loop body, so we want to knock off any
1.1390 + // odd iteration: (trip_cnt & ~1). Then back compute a new limit.
1.1391 + Node *span = new (C) SubINode( limit, init );
1.1392 + register_new_node( span, ctrl );
1.1393 + Node *trip = new (C) DivINode( 0, span, stride );
1.1394 + register_new_node( trip, ctrl );
1.1395 + Node *mtwo = _igvn.intcon(-2);
1.1396 + set_ctrl(mtwo, C->root());
1.1397 + Node *rond = new (C) AndINode( trip, mtwo );
1.1398 + register_new_node( rond, ctrl );
1.1399 + Node *spn2 = new (C) MulINode( rond, stride );
1.1400 + register_new_node( spn2, ctrl );
1.1401 + new_limit = new (C) AddINode( spn2, init );
1.1402 + register_new_node( new_limit, ctrl );
1.1403 +
1.1404 + // Hammer in the new limit
1.1405 + Node *ctrl2 = loop_end->in(0);
1.1406 + Node *cmp2 = new (C) CmpINode( loop_head->incr(), new_limit );
1.1407 + register_new_node( cmp2, ctrl2 );
1.1408 + Node *bol2 = new (C) BoolNode( cmp2, loop_end->test_trip() );
1.1409 + register_new_node( bol2, ctrl2 );
1.1410 + _igvn.hash_delete(loop_end);
1.1411 + loop_end->set_req(CountedLoopEndNode::TestValue, bol2);
1.1412 +
1.1413 + // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1.1414 + // Make it a 1-trip test (means at least 2 trips).
1.1415 + if( adjust_min_trip ) {
1.1416 + assert( new_limit != NULL, "" );
1.1417 + // Guard test uses an 'opaque' node which is not shared. Hence I
1.1418 + // can edit it's inputs directly. Hammer in the new limit for the
1.1419 + // minimum-trip guard.
1.1420 + assert( opaq->outcnt() == 1, "" );
1.1421 + _igvn.hash_delete(opaq);
1.1422 + opaq->set_req(1, new_limit);
1.1423 + }
1.1424 + } // LoopLimitCheck
1.1425 +
1.1426 + // ---------
1.1427 + // Step 4: Clone the loop body. Move it inside the loop. This loop body
1.1428 + // represents the odd iterations; since the loop trips an even number of
1.1429 + // times its backedge is never taken. Kill the backedge.
1.1430 + uint dd = dom_depth(loop_head);
1.1431 + clone_loop( loop, old_new, dd );
1.1432 +
1.1433 + // Make backedges of the clone equal to backedges of the original.
1.1434 + // Make the fall-in from the original come from the fall-out of the clone.
1.1435 + for (DUIterator_Fast jmax, j = loop_head->fast_outs(jmax); j < jmax; j++) {
1.1436 + Node* phi = loop_head->fast_out(j);
1.1437 + if( phi->is_Phi() && phi->in(0) == loop_head && phi->outcnt() > 0 ) {
1.1438 + Node *newphi = old_new[phi->_idx];
1.1439 + _igvn.hash_delete( phi );
1.1440 + _igvn.hash_delete( newphi );
1.1441 +
1.1442 + phi ->set_req(LoopNode:: EntryControl, newphi->in(LoopNode::LoopBackControl));
1.1443 + newphi->set_req(LoopNode::LoopBackControl, phi ->in(LoopNode::LoopBackControl));
1.1444 + phi ->set_req(LoopNode::LoopBackControl, C->top());
1.1445 + }
1.1446 + }
1.1447 + Node *clone_head = old_new[loop_head->_idx];
1.1448 + _igvn.hash_delete( clone_head );
1.1449 + loop_head ->set_req(LoopNode:: EntryControl, clone_head->in(LoopNode::LoopBackControl));
1.1450 + clone_head->set_req(LoopNode::LoopBackControl, loop_head ->in(LoopNode::LoopBackControl));
1.1451 + loop_head ->set_req(LoopNode::LoopBackControl, C->top());
1.1452 + loop->_head = clone_head; // New loop header
1.1453 +
1.1454 + set_idom(loop_head, loop_head ->in(LoopNode::EntryControl), dd);
1.1455 + set_idom(clone_head, clone_head->in(LoopNode::EntryControl), dd);
1.1456 +
1.1457 + // Kill the clone's backedge
1.1458 + Node *newcle = old_new[loop_end->_idx];
1.1459 + _igvn.hash_delete( newcle );
1.1460 + Node *one = _igvn.intcon(1);
1.1461 + set_ctrl(one, C->root());
1.1462 + newcle->set_req(1, one);
1.1463 + // Force clone into same loop body
1.1464 + uint max = loop->_body.size();
1.1465 + for( uint k = 0; k < max; k++ ) {
1.1466 + Node *old = loop->_body.at(k);
1.1467 + Node *nnn = old_new[old->_idx];
1.1468 + loop->_body.push(nnn);
1.1469 + if (!has_ctrl(old))
1.1470 + set_loop(nnn, loop);
1.1471 + }
1.1472 +
1.1473 + loop->record_for_igvn();
1.1474 +}
1.1475 +
1.1476 +//------------------------------do_maximally_unroll----------------------------
1.1477 +
1.1478 +void PhaseIdealLoop::do_maximally_unroll( IdealLoopTree *loop, Node_List &old_new ) {
1.1479 + CountedLoopNode *cl = loop->_head->as_CountedLoop();
1.1480 + assert(cl->has_exact_trip_count(), "trip count is not exact");
1.1481 + assert(cl->trip_count() > 0, "");
1.1482 +#ifndef PRODUCT
1.1483 + if (TraceLoopOpts) {
1.1484 + tty->print("MaxUnroll %d ", cl->trip_count());
1.1485 + loop->dump_head();
1.1486 + }
1.1487 +#endif
1.1488 +
1.1489 + // If loop is tripping an odd number of times, peel odd iteration
1.1490 + if ((cl->trip_count() & 1) == 1) {
1.1491 + do_peeling(loop, old_new);
1.1492 + }
1.1493 +
1.1494 + // Now its tripping an even number of times remaining. Double loop body.
1.1495 + // Do not adjust pre-guards; they are not needed and do not exist.
1.1496 + if (cl->trip_count() > 0) {
1.1497 + assert((cl->trip_count() & 1) == 0, "missed peeling");
1.1498 + do_unroll(loop, old_new, false);
1.1499 + }
1.1500 +}
1.1501 +
1.1502 +//------------------------------dominates_backedge---------------------------------
1.1503 +// Returns true if ctrl is executed on every complete iteration
1.1504 +bool IdealLoopTree::dominates_backedge(Node* ctrl) {
1.1505 + assert(ctrl->is_CFG(), "must be control");
1.1506 + Node* backedge = _head->as_Loop()->in(LoopNode::LoopBackControl);
1.1507 + return _phase->dom_lca_internal(ctrl, backedge) == ctrl;
1.1508 +}
1.1509 +
1.1510 +//------------------------------adjust_limit-----------------------------------
1.1511 +// Helper function for add_constraint().
1.1512 +Node* PhaseIdealLoop::adjust_limit(int stride_con, Node * scale, Node *offset, Node *rc_limit, Node *loop_limit, Node *pre_ctrl) {
1.1513 + // Compute "I :: (limit-offset)/scale"
1.1514 + Node *con = new (C) SubINode(rc_limit, offset);
1.1515 + register_new_node(con, pre_ctrl);
1.1516 + Node *X = new (C) DivINode(0, con, scale);
1.1517 + register_new_node(X, pre_ctrl);
1.1518 +
1.1519 + // Adjust loop limit
1.1520 + loop_limit = (stride_con > 0)
1.1521 + ? (Node*)(new (C) MinINode(loop_limit, X))
1.1522 + : (Node*)(new (C) MaxINode(loop_limit, X));
1.1523 + register_new_node(loop_limit, pre_ctrl);
1.1524 + return loop_limit;
1.1525 +}
1.1526 +
1.1527 +//------------------------------add_constraint---------------------------------
1.1528 +// Constrain the main loop iterations so the conditions:
1.1529 +// low_limit <= scale_con * I + offset < upper_limit
1.1530 +// always holds true. That is, either increase the number of iterations in
1.1531 +// the pre-loop or the post-loop until the condition holds true in the main
1.1532 +// loop. Stride, scale, offset and limit are all loop invariant. Further,
1.1533 +// stride and scale are constants (offset and limit often are).
1.1534 +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 ) {
1.1535 + // For positive stride, the pre-loop limit always uses a MAX function
1.1536 + // and the main loop a MIN function. For negative stride these are
1.1537 + // reversed.
1.1538 +
1.1539 + // Also for positive stride*scale the affine function is increasing, so the
1.1540 + // pre-loop must check for underflow and the post-loop for overflow.
1.1541 + // Negative stride*scale reverses this; pre-loop checks for overflow and
1.1542 + // post-loop for underflow.
1.1543 +
1.1544 + Node *scale = _igvn.intcon(scale_con);
1.1545 + set_ctrl(scale, C->root());
1.1546 +
1.1547 + if ((stride_con^scale_con) >= 0) { // Use XOR to avoid overflow
1.1548 + // The overflow limit: scale*I+offset < upper_limit
1.1549 + // For main-loop compute
1.1550 + // ( if (scale > 0) /* and stride > 0 */
1.1551 + // I < (upper_limit-offset)/scale
1.1552 + // else /* scale < 0 and stride < 0 */
1.1553 + // I > (upper_limit-offset)/scale
1.1554 + // )
1.1555 + //
1.1556 + // (upper_limit-offset) may overflow or underflow.
1.1557 + // But it is fine since main loop will either have
1.1558 + // less iterations or will be skipped in such case.
1.1559 + *main_limit = adjust_limit(stride_con, scale, offset, upper_limit, *main_limit, pre_ctrl);
1.1560 +
1.1561 + // The underflow limit: low_limit <= scale*I+offset.
1.1562 + // For pre-loop compute
1.1563 + // NOT(scale*I+offset >= low_limit)
1.1564 + // scale*I+offset < low_limit
1.1565 + // ( if (scale > 0) /* and stride > 0 */
1.1566 + // I < (low_limit-offset)/scale
1.1567 + // else /* scale < 0 and stride < 0 */
1.1568 + // I > (low_limit-offset)/scale
1.1569 + // )
1.1570 +
1.1571 + if (low_limit->get_int() == -max_jint) {
1.1572 + if (!RangeLimitCheck) return;
1.1573 + // We need this guard when scale*pre_limit+offset >= limit
1.1574 + // due to underflow. So we need execute pre-loop until
1.1575 + // scale*I+offset >= min_int. But (min_int-offset) will
1.1576 + // underflow when offset > 0 and X will be > original_limit
1.1577 + // when stride > 0. To avoid it we replace positive offset with 0.
1.1578 + //
1.1579 + // Also (min_int+1 == -max_int) is used instead of min_int here
1.1580 + // to avoid problem with scale == -1 (min_int/(-1) == min_int).
1.1581 + Node* shift = _igvn.intcon(31);
1.1582 + set_ctrl(shift, C->root());
1.1583 + Node* sign = new (C) RShiftINode(offset, shift);
1.1584 + register_new_node(sign, pre_ctrl);
1.1585 + offset = new (C) AndINode(offset, sign);
1.1586 + register_new_node(offset, pre_ctrl);
1.1587 + } else {
1.1588 + assert(low_limit->get_int() == 0, "wrong low limit for range check");
1.1589 + // The only problem we have here when offset == min_int
1.1590 + // since (0-min_int) == min_int. It may be fine for stride > 0
1.1591 + // but for stride < 0 X will be < original_limit. To avoid it
1.1592 + // max(pre_limit, original_limit) is used in do_range_check().
1.1593 + }
1.1594 + // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
1.1595 + *pre_limit = adjust_limit((-stride_con), scale, offset, low_limit, *pre_limit, pre_ctrl);
1.1596 +
1.1597 + } else { // stride_con*scale_con < 0
1.1598 + // For negative stride*scale pre-loop checks for overflow and
1.1599 + // post-loop for underflow.
1.1600 + //
1.1601 + // The overflow limit: scale*I+offset < upper_limit
1.1602 + // For pre-loop compute
1.1603 + // NOT(scale*I+offset < upper_limit)
1.1604 + // scale*I+offset >= upper_limit
1.1605 + // scale*I+offset+1 > upper_limit
1.1606 + // ( if (scale < 0) /* and stride > 0 */
1.1607 + // I < (upper_limit-(offset+1))/scale
1.1608 + // else /* scale > 0 and stride < 0 */
1.1609 + // I > (upper_limit-(offset+1))/scale
1.1610 + // )
1.1611 + //
1.1612 + // (upper_limit-offset-1) may underflow or overflow.
1.1613 + // To avoid it min(pre_limit, original_limit) is used
1.1614 + // in do_range_check() for stride > 0 and max() for < 0.
1.1615 + Node *one = _igvn.intcon(1);
1.1616 + set_ctrl(one, C->root());
1.1617 +
1.1618 + Node *plus_one = new (C) AddINode(offset, one);
1.1619 + register_new_node( plus_one, pre_ctrl );
1.1620 + // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
1.1621 + *pre_limit = adjust_limit((-stride_con), scale, plus_one, upper_limit, *pre_limit, pre_ctrl);
1.1622 +
1.1623 + if (low_limit->get_int() == -max_jint) {
1.1624 + if (!RangeLimitCheck) return;
1.1625 + // We need this guard when scale*main_limit+offset >= limit
1.1626 + // due to underflow. So we need execute main-loop while
1.1627 + // scale*I+offset+1 > min_int. But (min_int-offset-1) will
1.1628 + // underflow when (offset+1) > 0 and X will be < main_limit
1.1629 + // when scale < 0 (and stride > 0). To avoid it we replace
1.1630 + // positive (offset+1) with 0.
1.1631 + //
1.1632 + // Also (min_int+1 == -max_int) is used instead of min_int here
1.1633 + // to avoid problem with scale == -1 (min_int/(-1) == min_int).
1.1634 + Node* shift = _igvn.intcon(31);
1.1635 + set_ctrl(shift, C->root());
1.1636 + Node* sign = new (C) RShiftINode(plus_one, shift);
1.1637 + register_new_node(sign, pre_ctrl);
1.1638 + plus_one = new (C) AndINode(plus_one, sign);
1.1639 + register_new_node(plus_one, pre_ctrl);
1.1640 + } else {
1.1641 + assert(low_limit->get_int() == 0, "wrong low limit for range check");
1.1642 + // The only problem we have here when offset == max_int
1.1643 + // since (max_int+1) == min_int and (0-min_int) == min_int.
1.1644 + // But it is fine since main loop will either have
1.1645 + // less iterations or will be skipped in such case.
1.1646 + }
1.1647 + // The underflow limit: low_limit <= scale*I+offset.
1.1648 + // For main-loop compute
1.1649 + // scale*I+offset+1 > low_limit
1.1650 + // ( if (scale < 0) /* and stride > 0 */
1.1651 + // I < (low_limit-(offset+1))/scale
1.1652 + // else /* scale > 0 and stride < 0 */
1.1653 + // I > (low_limit-(offset+1))/scale
1.1654 + // )
1.1655 +
1.1656 + *main_limit = adjust_limit(stride_con, scale, plus_one, low_limit, *main_limit, pre_ctrl);
1.1657 + }
1.1658 +}
1.1659 +
1.1660 +
1.1661 +//------------------------------is_scaled_iv---------------------------------
1.1662 +// Return true if exp is a constant times an induction var
1.1663 +bool PhaseIdealLoop::is_scaled_iv(Node* exp, Node* iv, int* p_scale) {
1.1664 + if (exp == iv) {
1.1665 + if (p_scale != NULL) {
1.1666 + *p_scale = 1;
1.1667 + }
1.1668 + return true;
1.1669 + }
1.1670 + int opc = exp->Opcode();
1.1671 + if (opc == Op_MulI) {
1.1672 + if (exp->in(1) == iv && exp->in(2)->is_Con()) {
1.1673 + if (p_scale != NULL) {
1.1674 + *p_scale = exp->in(2)->get_int();
1.1675 + }
1.1676 + return true;
1.1677 + }
1.1678 + if (exp->in(2) == iv && exp->in(1)->is_Con()) {
1.1679 + if (p_scale != NULL) {
1.1680 + *p_scale = exp->in(1)->get_int();
1.1681 + }
1.1682 + return true;
1.1683 + }
1.1684 + } else if (opc == Op_LShiftI) {
1.1685 + if (exp->in(1) == iv && exp->in(2)->is_Con()) {
1.1686 + if (p_scale != NULL) {
1.1687 + *p_scale = 1 << exp->in(2)->get_int();
1.1688 + }
1.1689 + return true;
1.1690 + }
1.1691 + }
1.1692 + return false;
1.1693 +}
1.1694 +
1.1695 +//-----------------------------is_scaled_iv_plus_offset------------------------------
1.1696 +// Return true if exp is a simple induction variable expression: k1*iv + (invar + k2)
1.1697 +bool PhaseIdealLoop::is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth) {
1.1698 + if (is_scaled_iv(exp, iv, p_scale)) {
1.1699 + if (p_offset != NULL) {
1.1700 + Node *zero = _igvn.intcon(0);
1.1701 + set_ctrl(zero, C->root());
1.1702 + *p_offset = zero;
1.1703 + }
1.1704 + return true;
1.1705 + }
1.1706 + int opc = exp->Opcode();
1.1707 + if (opc == Op_AddI) {
1.1708 + if (is_scaled_iv(exp->in(1), iv, p_scale)) {
1.1709 + if (p_offset != NULL) {
1.1710 + *p_offset = exp->in(2);
1.1711 + }
1.1712 + return true;
1.1713 + }
1.1714 + if (exp->in(2)->is_Con()) {
1.1715 + Node* offset2 = NULL;
1.1716 + if (depth < 2 &&
1.1717 + is_scaled_iv_plus_offset(exp->in(1), iv, p_scale,
1.1718 + p_offset != NULL ? &offset2 : NULL, depth+1)) {
1.1719 + if (p_offset != NULL) {
1.1720 + Node *ctrl_off2 = get_ctrl(offset2);
1.1721 + Node* offset = new (C) AddINode(offset2, exp->in(2));
1.1722 + register_new_node(offset, ctrl_off2);
1.1723 + *p_offset = offset;
1.1724 + }
1.1725 + return true;
1.1726 + }
1.1727 + }
1.1728 + } else if (opc == Op_SubI) {
1.1729 + if (is_scaled_iv(exp->in(1), iv, p_scale)) {
1.1730 + if (p_offset != NULL) {
1.1731 + Node *zero = _igvn.intcon(0);
1.1732 + set_ctrl(zero, C->root());
1.1733 + Node *ctrl_off = get_ctrl(exp->in(2));
1.1734 + Node* offset = new (C) SubINode(zero, exp->in(2));
1.1735 + register_new_node(offset, ctrl_off);
1.1736 + *p_offset = offset;
1.1737 + }
1.1738 + return true;
1.1739 + }
1.1740 + if (is_scaled_iv(exp->in(2), iv, p_scale)) {
1.1741 + if (p_offset != NULL) {
1.1742 + *p_scale *= -1;
1.1743 + *p_offset = exp->in(1);
1.1744 + }
1.1745 + return true;
1.1746 + }
1.1747 + }
1.1748 + return false;
1.1749 +}
1.1750 +
1.1751 +//------------------------------do_range_check---------------------------------
1.1752 +// Eliminate range-checks and other trip-counter vs loop-invariant tests.
1.1753 +void PhaseIdealLoop::do_range_check( IdealLoopTree *loop, Node_List &old_new ) {
1.1754 +#ifndef PRODUCT
1.1755 + if (PrintOpto && VerifyLoopOptimizations) {
1.1756 + tty->print("Range Check Elimination ");
1.1757 + loop->dump_head();
1.1758 + } else if (TraceLoopOpts) {
1.1759 + tty->print("RangeCheck ");
1.1760 + loop->dump_head();
1.1761 + }
1.1762 +#endif
1.1763 + assert(RangeCheckElimination, "");
1.1764 + CountedLoopNode *cl = loop->_head->as_CountedLoop();
1.1765 + assert(cl->is_main_loop(), "");
1.1766 +
1.1767 + // protect against stride not being a constant
1.1768 + if (!cl->stride_is_con())
1.1769 + return;
1.1770 +
1.1771 + // Find the trip counter; we are iteration splitting based on it
1.1772 + Node *trip_counter = cl->phi();
1.1773 + // Find the main loop limit; we will trim it's iterations
1.1774 + // to not ever trip end tests
1.1775 + Node *main_limit = cl->limit();
1.1776 +
1.1777 + // Need to find the main-loop zero-trip guard
1.1778 + Node *ctrl = cl->in(LoopNode::EntryControl);
1.1779 + assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
1.1780 + Node *iffm = ctrl->in(0);
1.1781 + assert(iffm->Opcode() == Op_If, "");
1.1782 + Node *bolzm = iffm->in(1);
1.1783 + assert(bolzm->Opcode() == Op_Bool, "");
1.1784 + Node *cmpzm = bolzm->in(1);
1.1785 + assert(cmpzm->is_Cmp(), "");
1.1786 + Node *opqzm = cmpzm->in(2);
1.1787 + // Can not optimize a loop if zero-trip Opaque1 node is optimized
1.1788 + // away and then another round of loop opts attempted.
1.1789 + if (opqzm->Opcode() != Op_Opaque1)
1.1790 + return;
1.1791 + assert(opqzm->in(1) == main_limit, "do not understand situation");
1.1792 +
1.1793 + // Find the pre-loop limit; we will expand it's iterations to
1.1794 + // not ever trip low tests.
1.1795 + Node *p_f = iffm->in(0);
1.1796 + assert(p_f->Opcode() == Op_IfFalse, "");
1.1797 + CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
1.1798 + assert(pre_end->loopnode()->is_pre_loop(), "");
1.1799 + Node *pre_opaq1 = pre_end->limit();
1.1800 + // Occasionally it's possible for a pre-loop Opaque1 node to be
1.1801 + // optimized away and then another round of loop opts attempted.
1.1802 + // We can not optimize this particular loop in that case.
1.1803 + if (pre_opaq1->Opcode() != Op_Opaque1)
1.1804 + return;
1.1805 + Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
1.1806 + Node *pre_limit = pre_opaq->in(1);
1.1807 +
1.1808 + // Where do we put new limit calculations
1.1809 + Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
1.1810 +
1.1811 + // Ensure the original loop limit is available from the
1.1812 + // pre-loop Opaque1 node.
1.1813 + Node *orig_limit = pre_opaq->original_loop_limit();
1.1814 + if (orig_limit == NULL || _igvn.type(orig_limit) == Type::TOP)
1.1815 + return;
1.1816 +
1.1817 + // Must know if its a count-up or count-down loop
1.1818 +
1.1819 + int stride_con = cl->stride_con();
1.1820 + Node *zero = _igvn.intcon(0);
1.1821 + Node *one = _igvn.intcon(1);
1.1822 + // Use symmetrical int range [-max_jint,max_jint]
1.1823 + Node *mini = _igvn.intcon(-max_jint);
1.1824 + set_ctrl(zero, C->root());
1.1825 + set_ctrl(one, C->root());
1.1826 + set_ctrl(mini, C->root());
1.1827 +
1.1828 + // Range checks that do not dominate the loop backedge (ie.
1.1829 + // conditionally executed) can lengthen the pre loop limit beyond
1.1830 + // the original loop limit. To prevent this, the pre limit is
1.1831 + // (for stride > 0) MINed with the original loop limit (MAXed
1.1832 + // stride < 0) when some range_check (rc) is conditionally
1.1833 + // executed.
1.1834 + bool conditional_rc = false;
1.1835 +
1.1836 + // Check loop body for tests of trip-counter plus loop-invariant vs
1.1837 + // loop-invariant.
1.1838 + for( uint i = 0; i < loop->_body.size(); i++ ) {
1.1839 + Node *iff = loop->_body[i];
1.1840 + if( iff->Opcode() == Op_If ) { // Test?
1.1841 +
1.1842 + // Test is an IfNode, has 2 projections. If BOTH are in the loop
1.1843 + // we need loop unswitching instead of iteration splitting.
1.1844 + Node *exit = loop->is_loop_exit(iff);
1.1845 + if( !exit ) continue;
1.1846 + int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
1.1847 +
1.1848 + // Get boolean condition to test
1.1849 + Node *i1 = iff->in(1);
1.1850 + if( !i1->is_Bool() ) continue;
1.1851 + BoolNode *bol = i1->as_Bool();
1.1852 + BoolTest b_test = bol->_test;
1.1853 + // Flip sense of test if exit condition is flipped
1.1854 + if( flip )
1.1855 + b_test = b_test.negate();
1.1856 +
1.1857 + // Get compare
1.1858 + Node *cmp = bol->in(1);
1.1859 +
1.1860 + // Look for trip_counter + offset vs limit
1.1861 + Node *rc_exp = cmp->in(1);
1.1862 + Node *limit = cmp->in(2);
1.1863 + jint scale_con= 1; // Assume trip counter not scaled
1.1864 +
1.1865 + Node *limit_c = get_ctrl(limit);
1.1866 + if( loop->is_member(get_loop(limit_c) ) ) {
1.1867 + // Compare might have operands swapped; commute them
1.1868 + b_test = b_test.commute();
1.1869 + rc_exp = cmp->in(2);
1.1870 + limit = cmp->in(1);
1.1871 + limit_c = get_ctrl(limit);
1.1872 + if( loop->is_member(get_loop(limit_c) ) )
1.1873 + continue; // Both inputs are loop varying; cannot RCE
1.1874 + }
1.1875 + // Here we know 'limit' is loop invariant
1.1876 +
1.1877 + // 'limit' maybe pinned below the zero trip test (probably from a
1.1878 + // previous round of rce), in which case, it can't be used in the
1.1879 + // zero trip test expression which must occur before the zero test's if.
1.1880 + if( limit_c == ctrl ) {
1.1881 + continue; // Don't rce this check but continue looking for other candidates.
1.1882 + }
1.1883 +
1.1884 + // Check for scaled induction variable plus an offset
1.1885 + Node *offset = NULL;
1.1886 +
1.1887 + if (!is_scaled_iv_plus_offset(rc_exp, trip_counter, &scale_con, &offset)) {
1.1888 + continue;
1.1889 + }
1.1890 +
1.1891 + Node *offset_c = get_ctrl(offset);
1.1892 + if( loop->is_member( get_loop(offset_c) ) )
1.1893 + continue; // Offset is not really loop invariant
1.1894 + // Here we know 'offset' is loop invariant.
1.1895 +
1.1896 + // As above for the 'limit', the 'offset' maybe pinned below the
1.1897 + // zero trip test.
1.1898 + if( offset_c == ctrl ) {
1.1899 + continue; // Don't rce this check but continue looking for other candidates.
1.1900 + }
1.1901 +#ifdef ASSERT
1.1902 + if (TraceRangeLimitCheck) {
1.1903 + tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
1.1904 + bol->dump(2);
1.1905 + }
1.1906 +#endif
1.1907 + // At this point we have the expression as:
1.1908 + // scale_con * trip_counter + offset :: limit
1.1909 + // where scale_con, offset and limit are loop invariant. Trip_counter
1.1910 + // monotonically increases by stride_con, a constant. Both (or either)
1.1911 + // stride_con and scale_con can be negative which will flip about the
1.1912 + // sense of the test.
1.1913 +
1.1914 + // Adjust pre and main loop limits to guard the correct iteration set
1.1915 + if( cmp->Opcode() == Op_CmpU ) {// Unsigned compare is really 2 tests
1.1916 + if( b_test._test == BoolTest::lt ) { // Range checks always use lt
1.1917 + // The underflow and overflow limits: 0 <= scale*I+offset < limit
1.1918 + add_constraint( stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit );
1.1919 + if (!conditional_rc) {
1.1920 + // (0-offset)/scale could be outside of loop iterations range.
1.1921 + conditional_rc = !loop->dominates_backedge(iff) || RangeLimitCheck;
1.1922 + }
1.1923 + } else {
1.1924 +#ifndef PRODUCT
1.1925 + if( PrintOpto )
1.1926 + tty->print_cr("missed RCE opportunity");
1.1927 +#endif
1.1928 + continue; // In release mode, ignore it
1.1929 + }
1.1930 + } else { // Otherwise work on normal compares
1.1931 + switch( b_test._test ) {
1.1932 + case BoolTest::gt:
1.1933 + // Fall into GE case
1.1934 + case BoolTest::ge:
1.1935 + // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit
1.1936 + scale_con = -scale_con;
1.1937 + offset = new (C) SubINode( zero, offset );
1.1938 + register_new_node( offset, pre_ctrl );
1.1939 + limit = new (C) SubINode( zero, limit );
1.1940 + register_new_node( limit, pre_ctrl );
1.1941 + // Fall into LE case
1.1942 + case BoolTest::le:
1.1943 + if (b_test._test != BoolTest::gt) {
1.1944 + // Convert X <= Y to X < Y+1
1.1945 + limit = new (C) AddINode( limit, one );
1.1946 + register_new_node( limit, pre_ctrl );
1.1947 + }
1.1948 + // Fall into LT case
1.1949 + case BoolTest::lt:
1.1950 + // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit
1.1951 + // Note: (MIN_INT+1 == -MAX_INT) is used instead of MIN_INT here
1.1952 + // to avoid problem with scale == -1: MIN_INT/(-1) == MIN_INT.
1.1953 + add_constraint( stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit );
1.1954 + if (!conditional_rc) {
1.1955 + // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
1.1956 + // Note: negative offset is replaced with 0 but (MIN_INT+1)/scale could
1.1957 + // still be outside of loop range.
1.1958 + conditional_rc = !loop->dominates_backedge(iff) || RangeLimitCheck;
1.1959 + }
1.1960 + break;
1.1961 + default:
1.1962 +#ifndef PRODUCT
1.1963 + if( PrintOpto )
1.1964 + tty->print_cr("missed RCE opportunity");
1.1965 +#endif
1.1966 + continue; // Unhandled case
1.1967 + }
1.1968 + }
1.1969 +
1.1970 + // Kill the eliminated test
1.1971 + C->set_major_progress();
1.1972 + Node *kill_con = _igvn.intcon( 1-flip );
1.1973 + set_ctrl(kill_con, C->root());
1.1974 + _igvn.replace_input_of(iff, 1, kill_con);
1.1975 + // Find surviving projection
1.1976 + assert(iff->is_If(), "");
1.1977 + ProjNode* dp = ((IfNode*)iff)->proj_out(1-flip);
1.1978 + // Find loads off the surviving projection; remove their control edge
1.1979 + for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
1.1980 + Node* cd = dp->fast_out(i); // Control-dependent node
1.1981 + if (cd->is_Load() && cd->depends_only_on_test()) { // Loads can now float around in the loop
1.1982 + // Allow the load to float around in the loop, or before it
1.1983 + // but NOT before the pre-loop.
1.1984 + _igvn.replace_input_of(cd, 0, ctrl); // ctrl, not NULL
1.1985 + --i;
1.1986 + --imax;
1.1987 + }
1.1988 + }
1.1989 +
1.1990 + } // End of is IF
1.1991 +
1.1992 + }
1.1993 +
1.1994 + // Update loop limits
1.1995 + if (conditional_rc) {
1.1996 + pre_limit = (stride_con > 0) ? (Node*)new (C) MinINode(pre_limit, orig_limit)
1.1997 + : (Node*)new (C) MaxINode(pre_limit, orig_limit);
1.1998 + register_new_node(pre_limit, pre_ctrl);
1.1999 + }
1.2000 + _igvn.hash_delete(pre_opaq);
1.2001 + pre_opaq->set_req(1, pre_limit);
1.2002 +
1.2003 + // Note:: we are making the main loop limit no longer precise;
1.2004 + // need to round up based on stride.
1.2005 + cl->set_nonexact_trip_count();
1.2006 + if (!LoopLimitCheck && stride_con != 1 && stride_con != -1) { // Cutout for common case
1.2007 + // "Standard" round-up logic: ([main_limit-init+(y-1)]/y)*y+init
1.2008 + // Hopefully, compiler will optimize for powers of 2.
1.2009 + Node *ctrl = get_ctrl(main_limit);
1.2010 + Node *stride = cl->stride();
1.2011 + Node *init = cl->init_trip();
1.2012 + Node *span = new (C) SubINode(main_limit,init);
1.2013 + register_new_node(span,ctrl);
1.2014 + Node *rndup = _igvn.intcon(stride_con + ((stride_con>0)?-1:1));
1.2015 + Node *add = new (C) AddINode(span,rndup);
1.2016 + register_new_node(add,ctrl);
1.2017 + Node *div = new (C) DivINode(0,add,stride);
1.2018 + register_new_node(div,ctrl);
1.2019 + Node *mul = new (C) MulINode(div,stride);
1.2020 + register_new_node(mul,ctrl);
1.2021 + Node *newlim = new (C) AddINode(mul,init);
1.2022 + register_new_node(newlim,ctrl);
1.2023 + main_limit = newlim;
1.2024 + }
1.2025 +
1.2026 + Node *main_cle = cl->loopexit();
1.2027 + Node *main_bol = main_cle->in(1);
1.2028 + // Hacking loop bounds; need private copies of exit test
1.2029 + if( main_bol->outcnt() > 1 ) {// BoolNode shared?
1.2030 + _igvn.hash_delete(main_cle);
1.2031 + main_bol = main_bol->clone();// Clone a private BoolNode
1.2032 + register_new_node( main_bol, main_cle->in(0) );
1.2033 + main_cle->set_req(1,main_bol);
1.2034 + }
1.2035 + Node *main_cmp = main_bol->in(1);
1.2036 + if( main_cmp->outcnt() > 1 ) { // CmpNode shared?
1.2037 + _igvn.hash_delete(main_bol);
1.2038 + main_cmp = main_cmp->clone();// Clone a private CmpNode
1.2039 + register_new_node( main_cmp, main_cle->in(0) );
1.2040 + main_bol->set_req(1,main_cmp);
1.2041 + }
1.2042 + // Hack the now-private loop bounds
1.2043 + _igvn.replace_input_of(main_cmp, 2, main_limit);
1.2044 + // The OpaqueNode is unshared by design
1.2045 + assert( opqzm->outcnt() == 1, "cannot hack shared node" );
1.2046 + _igvn.replace_input_of(opqzm, 1, main_limit);
1.2047 +}
1.2048 +
1.2049 +//------------------------------DCE_loop_body----------------------------------
1.2050 +// Remove simplistic dead code from loop body
1.2051 +void IdealLoopTree::DCE_loop_body() {
1.2052 + for( uint i = 0; i < _body.size(); i++ )
1.2053 + if( _body.at(i)->outcnt() == 0 )
1.2054 + _body.map( i--, _body.pop() );
1.2055 +}
1.2056 +
1.2057 +
1.2058 +//------------------------------adjust_loop_exit_prob--------------------------
1.2059 +// Look for loop-exit tests with the 50/50 (or worse) guesses from the parsing stage.
1.2060 +// Replace with a 1-in-10 exit guess.
1.2061 +void IdealLoopTree::adjust_loop_exit_prob( PhaseIdealLoop *phase ) {
1.2062 + Node *test = tail();
1.2063 + while( test != _head ) {
1.2064 + uint top = test->Opcode();
1.2065 + if( top == Op_IfTrue || top == Op_IfFalse ) {
1.2066 + int test_con = ((ProjNode*)test)->_con;
1.2067 + assert(top == (uint)(test_con? Op_IfTrue: Op_IfFalse), "sanity");
1.2068 + IfNode *iff = test->in(0)->as_If();
1.2069 + if( iff->outcnt() == 2 ) { // Ignore dead tests
1.2070 + Node *bol = iff->in(1);
1.2071 + if( bol && bol->req() > 1 && bol->in(1) &&
1.2072 + ((bol->in(1)->Opcode() == Op_StorePConditional ) ||
1.2073 + (bol->in(1)->Opcode() == Op_StoreIConditional ) ||
1.2074 + (bol->in(1)->Opcode() == Op_StoreLConditional ) ||
1.2075 + (bol->in(1)->Opcode() == Op_CompareAndSwapI ) ||
1.2076 + (bol->in(1)->Opcode() == Op_CompareAndSwapL ) ||
1.2077 + (bol->in(1)->Opcode() == Op_CompareAndSwapP ) ||
1.2078 + (bol->in(1)->Opcode() == Op_CompareAndSwapN )))
1.2079 + return; // Allocation loops RARELY take backedge
1.2080 + // Find the OTHER exit path from the IF
1.2081 + Node* ex = iff->proj_out(1-test_con);
1.2082 + float p = iff->_prob;
1.2083 + if( !phase->is_member( this, ex ) && iff->_fcnt == COUNT_UNKNOWN ) {
1.2084 + if( top == Op_IfTrue ) {
1.2085 + if( p < (PROB_FAIR + PROB_UNLIKELY_MAG(3))) {
1.2086 + iff->_prob = PROB_STATIC_FREQUENT;
1.2087 + }
1.2088 + } else {
1.2089 + if( p > (PROB_FAIR - PROB_UNLIKELY_MAG(3))) {
1.2090 + iff->_prob = PROB_STATIC_INFREQUENT;
1.2091 + }
1.2092 + }
1.2093 + }
1.2094 + }
1.2095 + }
1.2096 + test = phase->idom(test);
1.2097 + }
1.2098 +}
1.2099 +
1.2100 +
1.2101 +//------------------------------policy_do_remove_empty_loop--------------------
1.2102 +// Micro-benchmark spamming. Policy is to always remove empty loops.
1.2103 +// The 'DO' part is to replace the trip counter with the value it will
1.2104 +// have on the last iteration. This will break the loop.
1.2105 +bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
1.2106 + // Minimum size must be empty loop
1.2107 + if (_body.size() > EMPTY_LOOP_SIZE)
1.2108 + return false;
1.2109 +
1.2110 + if (!_head->is_CountedLoop())
1.2111 + return false; // Dead loop
1.2112 + CountedLoopNode *cl = _head->as_CountedLoop();
1.2113 + if (!cl->is_valid_counted_loop())
1.2114 + return false; // Malformed loop
1.2115 + if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
1.2116 + return false; // Infinite loop
1.2117 +
1.2118 +#ifdef ASSERT
1.2119 + // Ensure only one phi which is the iv.
1.2120 + Node* iv = NULL;
1.2121 + for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
1.2122 + Node* n = cl->fast_out(i);
1.2123 + if (n->Opcode() == Op_Phi) {
1.2124 + assert(iv == NULL, "Too many phis" );
1.2125 + iv = n;
1.2126 + }
1.2127 + }
1.2128 + assert(iv == cl->phi(), "Wrong phi" );
1.2129 +#endif
1.2130 +
1.2131 + // main and post loops have explicitly created zero trip guard
1.2132 + bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
1.2133 + if (needs_guard) {
1.2134 + // Skip guard if values not overlap.
1.2135 + const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
1.2136 + const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
1.2137 + int stride_con = cl->stride_con();
1.2138 + if (stride_con > 0) {
1.2139 + needs_guard = (init_t->_hi >= limit_t->_lo);
1.2140 + } else {
1.2141 + needs_guard = (init_t->_lo <= limit_t->_hi);
1.2142 + }
1.2143 + }
1.2144 + if (needs_guard) {
1.2145 + // Check for an obvious zero trip guard.
1.2146 + Node* inctrl = PhaseIdealLoop::skip_loop_predicates(cl->in(LoopNode::EntryControl));
1.2147 + if (inctrl->Opcode() == Op_IfTrue) {
1.2148 + // The test should look like just the backedge of a CountedLoop
1.2149 + Node* iff = inctrl->in(0);
1.2150 + if (iff->is_If()) {
1.2151 + Node* bol = iff->in(1);
1.2152 + if (bol->is_Bool() && bol->as_Bool()->_test._test == cl->loopexit()->test_trip()) {
1.2153 + Node* cmp = bol->in(1);
1.2154 + if (cmp->is_Cmp() && cmp->in(1) == cl->init_trip() && cmp->in(2) == cl->limit()) {
1.2155 + needs_guard = false;
1.2156 + }
1.2157 + }
1.2158 + }
1.2159 + }
1.2160 + }
1.2161 +
1.2162 +#ifndef PRODUCT
1.2163 + if (PrintOpto) {
1.2164 + tty->print("Removing empty loop with%s zero trip guard", needs_guard ? "out" : "");
1.2165 + this->dump_head();
1.2166 + } else if (TraceLoopOpts) {
1.2167 + tty->print("Empty with%s zero trip guard ", needs_guard ? "out" : "");
1.2168 + this->dump_head();
1.2169 + }
1.2170 +#endif
1.2171 +
1.2172 + if (needs_guard) {
1.2173 + // Peel the loop to ensure there's a zero trip guard
1.2174 + Node_List old_new;
1.2175 + phase->do_peeling(this, old_new);
1.2176 + }
1.2177 +
1.2178 + // Replace the phi at loop head with the final value of the last
1.2179 + // iteration. Then the CountedLoopEnd will collapse (backedge never
1.2180 + // taken) and all loop-invariant uses of the exit values will be correct.
1.2181 + Node *phi = cl->phi();
1.2182 + Node *exact_limit = phase->exact_limit(this);
1.2183 + if (exact_limit != cl->limit()) {
1.2184 + // We also need to replace the original limit to collapse loop exit.
1.2185 + Node* cmp = cl->loopexit()->cmp_node();
1.2186 + assert(cl->limit() == cmp->in(2), "sanity");
1.2187 + phase->_igvn._worklist.push(cmp->in(2)); // put limit on worklist
1.2188 + phase->_igvn.replace_input_of(cmp, 2, exact_limit); // put cmp on worklist
1.2189 + }
1.2190 + // Note: the final value after increment should not overflow since
1.2191 + // counted loop has limit check predicate.
1.2192 + Node *final = new (phase->C) SubINode( exact_limit, cl->stride() );
1.2193 + phase->register_new_node(final,cl->in(LoopNode::EntryControl));
1.2194 + phase->_igvn.replace_node(phi,final);
1.2195 + phase->C->set_major_progress();
1.2196 + return true;
1.2197 +}
1.2198 +
1.2199 +//------------------------------policy_do_one_iteration_loop-------------------
1.2200 +// Convert one iteration loop into normal code.
1.2201 +bool IdealLoopTree::policy_do_one_iteration_loop( PhaseIdealLoop *phase ) {
1.2202 + if (!_head->as_Loop()->is_valid_counted_loop())
1.2203 + return false; // Only for counted loop
1.2204 +
1.2205 + CountedLoopNode *cl = _head->as_CountedLoop();
1.2206 + if (!cl->has_exact_trip_count() || cl->trip_count() != 1) {
1.2207 + return false;
1.2208 + }
1.2209 +
1.2210 +#ifndef PRODUCT
1.2211 + if(TraceLoopOpts) {
1.2212 + tty->print("OneIteration ");
1.2213 + this->dump_head();
1.2214 + }
1.2215 +#endif
1.2216 +
1.2217 + Node *init_n = cl->init_trip();
1.2218 +#ifdef ASSERT
1.2219 + // Loop boundaries should be constant since trip count is exact.
1.2220 + assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
1.2221 +#endif
1.2222 + // Replace the phi at loop head with the value of the init_trip.
1.2223 + // Then the CountedLoopEnd will collapse (backedge will not be taken)
1.2224 + // and all loop-invariant uses of the exit values will be correct.
1.2225 + phase->_igvn.replace_node(cl->phi(), cl->init_trip());
1.2226 + phase->C->set_major_progress();
1.2227 + return true;
1.2228 +}
1.2229 +
1.2230 +//=============================================================================
1.2231 +//------------------------------iteration_split_impl---------------------------
1.2232 +bool IdealLoopTree::iteration_split_impl( PhaseIdealLoop *phase, Node_List &old_new ) {
1.2233 + // Compute exact loop trip count if possible.
1.2234 + compute_exact_trip_count(phase);
1.2235 +
1.2236 + // Convert one iteration loop into normal code.
1.2237 + if (policy_do_one_iteration_loop(phase))
1.2238 + return true;
1.2239 +
1.2240 + // Check and remove empty loops (spam micro-benchmarks)
1.2241 + if (policy_do_remove_empty_loop(phase))
1.2242 + return true; // Here we removed an empty loop
1.2243 +
1.2244 + bool should_peel = policy_peeling(phase); // Should we peel?
1.2245 +
1.2246 + bool should_unswitch = policy_unswitching(phase);
1.2247 +
1.2248 + // Non-counted loops may be peeled; exactly 1 iteration is peeled.
1.2249 + // This removes loop-invariant tests (usually null checks).
1.2250 + if (!_head->is_CountedLoop()) { // Non-counted loop
1.2251 + if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
1.2252 + // Partial peel succeeded so terminate this round of loop opts
1.2253 + return false;
1.2254 + }
1.2255 + if (should_peel) { // Should we peel?
1.2256 +#ifndef PRODUCT
1.2257 + if (PrintOpto) tty->print_cr("should_peel");
1.2258 +#endif
1.2259 + phase->do_peeling(this,old_new);
1.2260 + } else if (should_unswitch) {
1.2261 + phase->do_unswitching(this, old_new);
1.2262 + }
1.2263 + return true;
1.2264 + }
1.2265 + CountedLoopNode *cl = _head->as_CountedLoop();
1.2266 +
1.2267 + if (!cl->is_valid_counted_loop()) return true; // Ignore various kinds of broken loops
1.2268 +
1.2269 + // Do nothing special to pre- and post- loops
1.2270 + if (cl->is_pre_loop() || cl->is_post_loop()) return true;
1.2271 +
1.2272 + // Compute loop trip count from profile data
1.2273 + compute_profile_trip_cnt(phase);
1.2274 +
1.2275 + // Before attempting fancy unrolling, RCE or alignment, see if we want
1.2276 + // to completely unroll this loop or do loop unswitching.
1.2277 + if (cl->is_normal_loop()) {
1.2278 + if (should_unswitch) {
1.2279 + phase->do_unswitching(this, old_new);
1.2280 + return true;
1.2281 + }
1.2282 + bool should_maximally_unroll = policy_maximally_unroll(phase);
1.2283 + if (should_maximally_unroll) {
1.2284 + // Here we did some unrolling and peeling. Eventually we will
1.2285 + // completely unroll this loop and it will no longer be a loop.
1.2286 + phase->do_maximally_unroll(this,old_new);
1.2287 + return true;
1.2288 + }
1.2289 + }
1.2290 +
1.2291 + // Skip next optimizations if running low on nodes. Note that
1.2292 + // policy_unswitching and policy_maximally_unroll have this check.
1.2293 + uint nodes_left = MaxNodeLimit - (uint) phase->C->live_nodes();
1.2294 + if ((2 * _body.size()) > nodes_left) {
1.2295 + return true;
1.2296 + }
1.2297 +
1.2298 + // Counted loops may be peeled, may need some iterations run up
1.2299 + // front for RCE, and may want to align loop refs to a cache
1.2300 + // line. Thus we clone a full loop up front whose trip count is
1.2301 + // at least 1 (if peeling), but may be several more.
1.2302 +
1.2303 + // The main loop will start cache-line aligned with at least 1
1.2304 + // iteration of the unrolled body (zero-trip test required) and
1.2305 + // will have some range checks removed.
1.2306 +
1.2307 + // A post-loop will finish any odd iterations (leftover after
1.2308 + // unrolling), plus any needed for RCE purposes.
1.2309 +
1.2310 + bool should_unroll = policy_unroll(phase);
1.2311 +
1.2312 + bool should_rce = policy_range_check(phase);
1.2313 +
1.2314 + bool should_align = policy_align(phase);
1.2315 +
1.2316 + // If not RCE'ing (iteration splitting) or Aligning, then we do not
1.2317 + // need a pre-loop. We may still need to peel an initial iteration but
1.2318 + // we will not be needing an unknown number of pre-iterations.
1.2319 + //
1.2320 + // Basically, if may_rce_align reports FALSE first time through,
1.2321 + // we will not be able to later do RCE or Aligning on this loop.
1.2322 + bool may_rce_align = !policy_peel_only(phase) || should_rce || should_align;
1.2323 +
1.2324 + // If we have any of these conditions (RCE, alignment, unrolling) met, then
1.2325 + // we switch to the pre-/main-/post-loop model. This model also covers
1.2326 + // peeling.
1.2327 + if (should_rce || should_align || should_unroll) {
1.2328 + if (cl->is_normal_loop()) // Convert to 'pre/main/post' loops
1.2329 + phase->insert_pre_post_loops(this,old_new, !may_rce_align);
1.2330 +
1.2331 + // Adjust the pre- and main-loop limits to let the pre and post loops run
1.2332 + // with full checks, but the main-loop with no checks. Remove said
1.2333 + // checks from the main body.
1.2334 + if (should_rce)
1.2335 + phase->do_range_check(this,old_new);
1.2336 +
1.2337 + // Double loop body for unrolling. Adjust the minimum-trip test (will do
1.2338 + // twice as many iterations as before) and the main body limit (only do
1.2339 + // an even number of trips). If we are peeling, we might enable some RCE
1.2340 + // and we'd rather unroll the post-RCE'd loop SO... do not unroll if
1.2341 + // peeling.
1.2342 + if (should_unroll && !should_peel)
1.2343 + phase->do_unroll(this,old_new, true);
1.2344 +
1.2345 + // Adjust the pre-loop limits to align the main body
1.2346 + // iterations.
1.2347 + if (should_align)
1.2348 + Unimplemented();
1.2349 +
1.2350 + } else { // Else we have an unchanged counted loop
1.2351 + if (should_peel) // Might want to peel but do nothing else
1.2352 + phase->do_peeling(this,old_new);
1.2353 + }
1.2354 + return true;
1.2355 +}
1.2356 +
1.2357 +
1.2358 +//=============================================================================
1.2359 +//------------------------------iteration_split--------------------------------
1.2360 +bool IdealLoopTree::iteration_split( PhaseIdealLoop *phase, Node_List &old_new ) {
1.2361 + // Recursively iteration split nested loops
1.2362 + if (_child && !_child->iteration_split(phase, old_new))
1.2363 + return false;
1.2364 +
1.2365 + // Clean out prior deadwood
1.2366 + DCE_loop_body();
1.2367 +
1.2368 +
1.2369 + // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
1.2370 + // Replace with a 1-in-10 exit guess.
1.2371 + if (_parent /*not the root loop*/ &&
1.2372 + !_irreducible &&
1.2373 + // Also ignore the occasional dead backedge
1.2374 + !tail()->is_top()) {
1.2375 + adjust_loop_exit_prob(phase);
1.2376 + }
1.2377 +
1.2378 + // Gate unrolling, RCE and peeling efforts.
1.2379 + if (!_child && // If not an inner loop, do not split
1.2380 + !_irreducible &&
1.2381 + _allow_optimizations &&
1.2382 + !tail()->is_top()) { // Also ignore the occasional dead backedge
1.2383 + if (!_has_call) {
1.2384 + if (!iteration_split_impl(phase, old_new)) {
1.2385 + return false;
1.2386 + }
1.2387 + } else if (policy_unswitching(phase)) {
1.2388 + phase->do_unswitching(this, old_new);
1.2389 + }
1.2390 + }
1.2391 +
1.2392 + // Minor offset re-organization to remove loop-fallout uses of
1.2393 + // trip counter when there was no major reshaping.
1.2394 + phase->reorg_offsets(this);
1.2395 +
1.2396 + if (_next && !_next->iteration_split(phase, old_new))
1.2397 + return false;
1.2398 + return true;
1.2399 +}
1.2400 +
1.2401 +
1.2402 +//=============================================================================
1.2403 +// Process all the loops in the loop tree and replace any fill
1.2404 +// patterns with an intrisc version.
1.2405 +bool PhaseIdealLoop::do_intrinsify_fill() {
1.2406 + bool changed = false;
1.2407 + for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1.2408 + IdealLoopTree* lpt = iter.current();
1.2409 + changed |= intrinsify_fill(lpt);
1.2410 + }
1.2411 + return changed;
1.2412 +}
1.2413 +
1.2414 +
1.2415 +// Examine an inner loop looking for a a single store of an invariant
1.2416 +// value in a unit stride loop,
1.2417 +bool PhaseIdealLoop::match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1.2418 + Node*& shift, Node*& con) {
1.2419 + const char* msg = NULL;
1.2420 + Node* msg_node = NULL;
1.2421 +
1.2422 + store_value = NULL;
1.2423 + con = NULL;
1.2424 + shift = NULL;
1.2425 +
1.2426 + // Process the loop looking for stores. If there are multiple
1.2427 + // stores or extra control flow give at this point.
1.2428 + CountedLoopNode* head = lpt->_head->as_CountedLoop();
1.2429 + for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
1.2430 + Node* n = lpt->_body.at(i);
1.2431 + if (n->outcnt() == 0) continue; // Ignore dead
1.2432 + if (n->is_Store()) {
1.2433 + if (store != NULL) {
1.2434 + msg = "multiple stores";
1.2435 + break;
1.2436 + }
1.2437 + int opc = n->Opcode();
1.2438 + if (opc == Op_StoreP || opc == Op_StoreN || opc == Op_StoreNKlass || opc == Op_StoreCM) {
1.2439 + msg = "oop fills not handled";
1.2440 + break;
1.2441 + }
1.2442 + Node* value = n->in(MemNode::ValueIn);
1.2443 + if (!lpt->is_invariant(value)) {
1.2444 + msg = "variant store value";
1.2445 + } else if (!_igvn.type(n->in(MemNode::Address))->isa_aryptr()) {
1.2446 + msg = "not array address";
1.2447 + }
1.2448 + store = n;
1.2449 + store_value = value;
1.2450 + } else if (n->is_If() && n != head->loopexit()) {
1.2451 + msg = "extra control flow";
1.2452 + msg_node = n;
1.2453 + }
1.2454 + }
1.2455 +
1.2456 + if (store == NULL) {
1.2457 + // No store in loop
1.2458 + return false;
1.2459 + }
1.2460 +
1.2461 + if (msg == NULL && head->stride_con() != 1) {
1.2462 + // could handle negative strides too
1.2463 + if (head->stride_con() < 0) {
1.2464 + msg = "negative stride";
1.2465 + } else {
1.2466 + msg = "non-unit stride";
1.2467 + }
1.2468 + }
1.2469 +
1.2470 + if (msg == NULL && !store->in(MemNode::Address)->is_AddP()) {
1.2471 + msg = "can't handle store address";
1.2472 + msg_node = store->in(MemNode::Address);
1.2473 + }
1.2474 +
1.2475 + if (msg == NULL &&
1.2476 + (!store->in(MemNode::Memory)->is_Phi() ||
1.2477 + store->in(MemNode::Memory)->in(LoopNode::LoopBackControl) != store)) {
1.2478 + msg = "store memory isn't proper phi";
1.2479 + msg_node = store->in(MemNode::Memory);
1.2480 + }
1.2481 +
1.2482 + // Make sure there is an appropriate fill routine
1.2483 + BasicType t = store->as_Mem()->memory_type();
1.2484 + const char* fill_name;
1.2485 + if (msg == NULL &&
1.2486 + StubRoutines::select_fill_function(t, false, fill_name) == NULL) {
1.2487 + msg = "unsupported store";
1.2488 + msg_node = store;
1.2489 + }
1.2490 +
1.2491 + if (msg != NULL) {
1.2492 +#ifndef PRODUCT
1.2493 + if (TraceOptimizeFill) {
1.2494 + tty->print_cr("not fill intrinsic candidate: %s", msg);
1.2495 + if (msg_node != NULL) msg_node->dump();
1.2496 + }
1.2497 +#endif
1.2498 + return false;
1.2499 + }
1.2500 +
1.2501 + // Make sure the address expression can be handled. It should be
1.2502 + // head->phi * elsize + con. head->phi might have a ConvI2L.
1.2503 + Node* elements[4];
1.2504 + Node* conv = NULL;
1.2505 + bool found_index = false;
1.2506 + int count = store->in(MemNode::Address)->as_AddP()->unpack_offsets(elements, ARRAY_SIZE(elements));
1.2507 + for (int e = 0; e < count; e++) {
1.2508 + Node* n = elements[e];
1.2509 + if (n->is_Con() && con == NULL) {
1.2510 + con = n;
1.2511 + } else if (n->Opcode() == Op_LShiftX && shift == NULL) {
1.2512 + Node* value = n->in(1);
1.2513 +#ifdef _LP64
1.2514 + if (value->Opcode() == Op_ConvI2L) {
1.2515 + conv = value;
1.2516 + value = value->in(1);
1.2517 + }
1.2518 +#endif
1.2519 + if (value != head->phi()) {
1.2520 + msg = "unhandled shift in address";
1.2521 + } else {
1.2522 + if (type2aelembytes(store->as_Mem()->memory_type(), true) != (1 << n->in(2)->get_int())) {
1.2523 + msg = "scale doesn't match";
1.2524 + } else {
1.2525 + found_index = true;
1.2526 + shift = n;
1.2527 + }
1.2528 + }
1.2529 + } else if (n->Opcode() == Op_ConvI2L && conv == NULL) {
1.2530 + if (n->in(1) == head->phi()) {
1.2531 + found_index = true;
1.2532 + conv = n;
1.2533 + } else {
1.2534 + msg = "unhandled input to ConvI2L";
1.2535 + }
1.2536 + } else if (n == head->phi()) {
1.2537 + // no shift, check below for allowed cases
1.2538 + found_index = true;
1.2539 + } else {
1.2540 + msg = "unhandled node in address";
1.2541 + msg_node = n;
1.2542 + }
1.2543 + }
1.2544 +
1.2545 + if (count == -1) {
1.2546 + msg = "malformed address expression";
1.2547 + msg_node = store;
1.2548 + }
1.2549 +
1.2550 + if (!found_index) {
1.2551 + msg = "missing use of index";
1.2552 + }
1.2553 +
1.2554 + // byte sized items won't have a shift
1.2555 + if (msg == NULL && shift == NULL && t != T_BYTE && t != T_BOOLEAN) {
1.2556 + msg = "can't find shift";
1.2557 + msg_node = store;
1.2558 + }
1.2559 +
1.2560 + if (msg != NULL) {
1.2561 +#ifndef PRODUCT
1.2562 + if (TraceOptimizeFill) {
1.2563 + tty->print_cr("not fill intrinsic: %s", msg);
1.2564 + if (msg_node != NULL) msg_node->dump();
1.2565 + }
1.2566 +#endif
1.2567 + return false;
1.2568 + }
1.2569 +
1.2570 + // No make sure all the other nodes in the loop can be handled
1.2571 + VectorSet ok(Thread::current()->resource_area());
1.2572 +
1.2573 + // store related values are ok
1.2574 + ok.set(store->_idx);
1.2575 + ok.set(store->in(MemNode::Memory)->_idx);
1.2576 +
1.2577 + CountedLoopEndNode* loop_exit = head->loopexit();
1.2578 + guarantee(loop_exit != NULL, "no loop exit node");
1.2579 +
1.2580 + // Loop structure is ok
1.2581 + ok.set(head->_idx);
1.2582 + ok.set(loop_exit->_idx);
1.2583 + ok.set(head->phi()->_idx);
1.2584 + ok.set(head->incr()->_idx);
1.2585 + ok.set(loop_exit->cmp_node()->_idx);
1.2586 + ok.set(loop_exit->in(1)->_idx);
1.2587 +
1.2588 + // Address elements are ok
1.2589 + if (con) ok.set(con->_idx);
1.2590 + if (shift) ok.set(shift->_idx);
1.2591 + if (conv) ok.set(conv->_idx);
1.2592 +
1.2593 + for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
1.2594 + Node* n = lpt->_body.at(i);
1.2595 + if (n->outcnt() == 0) continue; // Ignore dead
1.2596 + if (ok.test(n->_idx)) continue;
1.2597 + // Backedge projection is ok
1.2598 + if (n->is_IfTrue() && n->in(0) == loop_exit) continue;
1.2599 + if (!n->is_AddP()) {
1.2600 + msg = "unhandled node";
1.2601 + msg_node = n;
1.2602 + break;
1.2603 + }
1.2604 + }
1.2605 +
1.2606 + // Make sure no unexpected values are used outside the loop
1.2607 + for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
1.2608 + Node* n = lpt->_body.at(i);
1.2609 + // These values can be replaced with other nodes if they are used
1.2610 + // outside the loop.
1.2611 + if (n == store || n == loop_exit || n == head->incr() || n == store->in(MemNode::Memory)) continue;
1.2612 + for (SimpleDUIterator iter(n); iter.has_next(); iter.next()) {
1.2613 + Node* use = iter.get();
1.2614 + if (!lpt->_body.contains(use)) {
1.2615 + msg = "node is used outside loop";
1.2616 + // lpt->_body.dump();
1.2617 + msg_node = n;
1.2618 + break;
1.2619 + }
1.2620 + }
1.2621 + }
1.2622 +
1.2623 +#ifdef ASSERT
1.2624 + if (TraceOptimizeFill) {
1.2625 + if (msg != NULL) {
1.2626 + tty->print_cr("no fill intrinsic: %s", msg);
1.2627 + if (msg_node != NULL) msg_node->dump();
1.2628 + } else {
1.2629 + tty->print_cr("fill intrinsic for:");
1.2630 + }
1.2631 + store->dump();
1.2632 + if (Verbose) {
1.2633 + lpt->_body.dump();
1.2634 + }
1.2635 + }
1.2636 +#endif
1.2637 +
1.2638 + return msg == NULL;
1.2639 +}
1.2640 +
1.2641 +
1.2642 +
1.2643 +bool PhaseIdealLoop::intrinsify_fill(IdealLoopTree* lpt) {
1.2644 + // Only for counted inner loops
1.2645 + if (!lpt->is_counted() || !lpt->is_inner()) {
1.2646 + return false;
1.2647 + }
1.2648 +
1.2649 + // Must have constant stride
1.2650 + CountedLoopNode* head = lpt->_head->as_CountedLoop();
1.2651 + if (!head->is_valid_counted_loop() || !head->is_normal_loop()) {
1.2652 + return false;
1.2653 + }
1.2654 +
1.2655 + // Check that the body only contains a store of a loop invariant
1.2656 + // value that is indexed by the loop phi.
1.2657 + Node* store = NULL;
1.2658 + Node* store_value = NULL;
1.2659 + Node* shift = NULL;
1.2660 + Node* offset = NULL;
1.2661 + if (!match_fill_loop(lpt, store, store_value, shift, offset)) {
1.2662 + return false;
1.2663 + }
1.2664 +
1.2665 +#ifndef PRODUCT
1.2666 + if (TraceLoopOpts) {
1.2667 + tty->print("ArrayFill ");
1.2668 + lpt->dump_head();
1.2669 + }
1.2670 +#endif
1.2671 +
1.2672 + // Now replace the whole loop body by a call to a fill routine that
1.2673 + // covers the same region as the loop.
1.2674 + Node* base = store->in(MemNode::Address)->as_AddP()->in(AddPNode::Base);
1.2675 +
1.2676 + // Build an expression for the beginning of the copy region
1.2677 + Node* index = head->init_trip();
1.2678 +#ifdef _LP64
1.2679 + index = new (C) ConvI2LNode(index);
1.2680 + _igvn.register_new_node_with_optimizer(index);
1.2681 +#endif
1.2682 + if (shift != NULL) {
1.2683 + // byte arrays don't require a shift but others do.
1.2684 + index = new (C) LShiftXNode(index, shift->in(2));
1.2685 + _igvn.register_new_node_with_optimizer(index);
1.2686 + }
1.2687 + index = new (C) AddPNode(base, base, index);
1.2688 + _igvn.register_new_node_with_optimizer(index);
1.2689 + Node* from = new (C) AddPNode(base, index, offset);
1.2690 + _igvn.register_new_node_with_optimizer(from);
1.2691 + // Compute the number of elements to copy
1.2692 + Node* len = new (C) SubINode(head->limit(), head->init_trip());
1.2693 + _igvn.register_new_node_with_optimizer(len);
1.2694 +
1.2695 + BasicType t = store->as_Mem()->memory_type();
1.2696 + bool aligned = false;
1.2697 + if (offset != NULL && head->init_trip()->is_Con()) {
1.2698 + int element_size = type2aelembytes(t);
1.2699 + aligned = (offset->find_intptr_t_type()->get_con() + head->init_trip()->get_int() * element_size) % HeapWordSize == 0;
1.2700 + }
1.2701 +
1.2702 + // Build a call to the fill routine
1.2703 + const char* fill_name;
1.2704 + address fill = StubRoutines::select_fill_function(t, aligned, fill_name);
1.2705 + assert(fill != NULL, "what?");
1.2706 +
1.2707 + // Convert float/double to int/long for fill routines
1.2708 + if (t == T_FLOAT) {
1.2709 + store_value = new (C) MoveF2INode(store_value);
1.2710 + _igvn.register_new_node_with_optimizer(store_value);
1.2711 + } else if (t == T_DOUBLE) {
1.2712 + store_value = new (C) MoveD2LNode(store_value);
1.2713 + _igvn.register_new_node_with_optimizer(store_value);
1.2714 + }
1.2715 +
1.2716 + if (CCallingConventionRequiresIntsAsLongs &&
1.2717 + // See StubRoutines::select_fill_function for types. FLOAT has been converted to INT.
1.2718 + (t == T_FLOAT || t == T_INT || is_subword_type(t))) {
1.2719 + store_value = new (C) ConvI2LNode(store_value);
1.2720 + _igvn.register_new_node_with_optimizer(store_value);
1.2721 + }
1.2722 +
1.2723 + Node* mem_phi = store->in(MemNode::Memory);
1.2724 + Node* result_ctrl;
1.2725 + Node* result_mem;
1.2726 + const TypeFunc* call_type = OptoRuntime::array_fill_Type();
1.2727 + CallLeafNode *call = new (C) CallLeafNoFPNode(call_type, fill,
1.2728 + fill_name, TypeAryPtr::get_array_body_type(t));
1.2729 + uint cnt = 0;
1.2730 + call->init_req(TypeFunc::Parms + cnt++, from);
1.2731 + call->init_req(TypeFunc::Parms + cnt++, store_value);
1.2732 + if (CCallingConventionRequiresIntsAsLongs) {
1.2733 + call->init_req(TypeFunc::Parms + cnt++, C->top());
1.2734 + }
1.2735 +#ifdef _LP64
1.2736 + len = new (C) ConvI2LNode(len);
1.2737 + _igvn.register_new_node_with_optimizer(len);
1.2738 +#endif
1.2739 + call->init_req(TypeFunc::Parms + cnt++, len);
1.2740 +#ifdef _LP64
1.2741 + call->init_req(TypeFunc::Parms + cnt++, C->top());
1.2742 +#endif
1.2743 + call->init_req(TypeFunc::Control, head->init_control());
1.2744 + call->init_req(TypeFunc::I_O, C->top()); // Does no I/O.
1.2745 + call->init_req(TypeFunc::Memory, mem_phi->in(LoopNode::EntryControl));
1.2746 + call->init_req(TypeFunc::ReturnAdr, C->start()->proj_out(TypeFunc::ReturnAdr));
1.2747 + call->init_req(TypeFunc::FramePtr, C->start()->proj_out(TypeFunc::FramePtr));
1.2748 + _igvn.register_new_node_with_optimizer(call);
1.2749 + result_ctrl = new (C) ProjNode(call,TypeFunc::Control);
1.2750 + _igvn.register_new_node_with_optimizer(result_ctrl);
1.2751 + result_mem = new (C) ProjNode(call,TypeFunc::Memory);
1.2752 + _igvn.register_new_node_with_optimizer(result_mem);
1.2753 +
1.2754 +/* Disable following optimization until proper fix (add missing checks).
1.2755 +
1.2756 + // If this fill is tightly coupled to an allocation and overwrites
1.2757 + // the whole body, allow it to take over the zeroing.
1.2758 + AllocateNode* alloc = AllocateNode::Ideal_allocation(base, this);
1.2759 + if (alloc != NULL && alloc->is_AllocateArray()) {
1.2760 + Node* length = alloc->as_AllocateArray()->Ideal_length();
1.2761 + if (head->limit() == length &&
1.2762 + head->init_trip() == _igvn.intcon(0)) {
1.2763 + if (TraceOptimizeFill) {
1.2764 + tty->print_cr("Eliminated zeroing in allocation");
1.2765 + }
1.2766 + alloc->maybe_set_complete(&_igvn);
1.2767 + } else {
1.2768 +#ifdef ASSERT
1.2769 + if (TraceOptimizeFill) {
1.2770 + tty->print_cr("filling array but bounds don't match");
1.2771 + alloc->dump();
1.2772 + head->init_trip()->dump();
1.2773 + head->limit()->dump();
1.2774 + length->dump();
1.2775 + }
1.2776 +#endif
1.2777 + }
1.2778 + }
1.2779 +*/
1.2780 +
1.2781 + // Redirect the old control and memory edges that are outside the loop.
1.2782 + Node* exit = head->loopexit()->proj_out(0);
1.2783 + // Sometimes the memory phi of the head is used as the outgoing
1.2784 + // state of the loop. It's safe in this case to replace it with the
1.2785 + // result_mem.
1.2786 + _igvn.replace_node(store->in(MemNode::Memory), result_mem);
1.2787 + _igvn.replace_node(exit, result_ctrl);
1.2788 + _igvn.replace_node(store, result_mem);
1.2789 + // Any uses the increment outside of the loop become the loop limit.
1.2790 + _igvn.replace_node(head->incr(), head->limit());
1.2791 +
1.2792 + // Disconnect the head from the loop.
1.2793 + for (uint i = 0; i < lpt->_body.size(); i++) {
1.2794 + Node* n = lpt->_body.at(i);
1.2795 + _igvn.replace_node(n, C->top());
1.2796 + }
1.2797 +
1.2798 + return true;
1.2799 +}
