1 /*
   2  * Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "compiler/compileLog.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "opto/addnode.hpp"
  29 #include "opto/callnode.hpp"
  30 #include "opto/castnode.hpp"
  31 #include "opto/connode.hpp"
  32 #include "opto/convertnode.hpp"
  33 #include "opto/divnode.hpp"
  34 #include "opto/loopnode.hpp"
  35 #include "opto/mulnode.hpp"
  36 #include "opto/movenode.hpp"
  37 #include "opto/opaquenode.hpp"
  38 #include "opto/rootnode.hpp"
  39 #include "opto/runtime.hpp"
  40 #include "opto/subnode.hpp"
  41 #include "opto/superword.hpp"
  42 #include "opto/vectornode.hpp"
  43 
  44 //------------------------------is_loop_exit-----------------------------------
  45 // Given an IfNode, return the loop-exiting projection or NULL if both
  46 // arms remain in the loop.
  47 Node *IdealLoopTree::is_loop_exit(Node *iff) const {
  48   if (iff->outcnt() != 2) return NULL;  // Ignore partially dead tests
  49   PhaseIdealLoop *phase = _phase;
  50   // Test is an IfNode, has 2 projections.  If BOTH are in the loop
  51   // we need loop unswitching instead of peeling.
  52   if (!is_member(phase->get_loop(iff->raw_out(0))))
  53     return iff->raw_out(0);
  54   if (!is_member(phase->get_loop(iff->raw_out(1))))
  55     return iff->raw_out(1);
  56   return NULL;
  57 }
  58 
  59 
  60 //=============================================================================
  61 
  62 
  63 //------------------------------record_for_igvn----------------------------
  64 // Put loop body on igvn work list
  65 void IdealLoopTree::record_for_igvn() {
  66   for (uint i = 0; i < _body.size(); i++) {
  67     Node *n = _body.at(i);
  68     _phase->_igvn._worklist.push(n);
  69   }
  70   // put body of outer strip mined loop on igvn work list as well
  71   if (_head->is_CountedLoop() && _head->as_Loop()->is_strip_mined()) {
  72     CountedLoopNode* l = _head->as_CountedLoop();
  73     Node* outer_loop = l->outer_loop();
  74     assert(outer_loop != NULL, "missing piece of strip mined loop");
  75     _phase->_igvn._worklist.push(outer_loop);
  76     Node* outer_loop_tail = l->outer_loop_tail();
  77     assert(outer_loop_tail != NULL, "missing piece of strip mined loop");
  78     _phase->_igvn._worklist.push(outer_loop_tail);
  79     Node* outer_loop_end = l->outer_loop_end();
  80     assert(outer_loop_end != NULL, "missing piece of strip mined loop");
  81     _phase->_igvn._worklist.push(outer_loop_end);
  82     Node* outer_safepoint = l->outer_safepoint();
  83     assert(outer_safepoint != NULL, "missing piece of strip mined loop");
  84     _phase->_igvn._worklist.push(outer_safepoint);
  85     Node* cle_out = _head->as_CountedLoop()->loopexit()->proj_out(false);
  86     assert(cle_out != NULL, "missing piece of strip mined loop");
  87     _phase->_igvn._worklist.push(cle_out);
  88   }
  89 }
  90 
  91 //------------------------------compute_exact_trip_count-----------------------
  92 // Compute loop trip count if possible. Do not recalculate trip count for
  93 // split loops (pre-main-post) which have their limits and inits behind Opaque node.
  94 void IdealLoopTree::compute_trip_count(PhaseIdealLoop* phase) {
  95   if (!_head->as_Loop()->is_valid_counted_loop()) {
  96     return;
  97   }
  98   CountedLoopNode* cl = _head->as_CountedLoop();
  99   // Trip count may become nonexact for iteration split loops since
 100   // RCE modifies limits. Note, _trip_count value is not reset since
 101   // it is used to limit unrolling of main loop.
 102   cl->set_nonexact_trip_count();
 103 
 104   // Loop's test should be part of loop.
 105   if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
 106     return; // Infinite loop
 107 
 108 #ifdef ASSERT
 109   BoolTest::mask bt = cl->loopexit()->test_trip();
 110   assert(bt == BoolTest::lt || bt == BoolTest::gt ||
 111          bt == BoolTest::ne, "canonical test is expected");
 112 #endif
 113 
 114   Node* init_n = cl->init_trip();
 115   Node* limit_n = cl->limit();
 116   if (init_n != NULL && limit_n != NULL) {
 117     // Use longs to avoid integer overflow.
 118     int stride_con = cl->stride_con();
 119     const TypeInt* init_type = phase->_igvn.type(init_n)->is_int();
 120     const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
 121     jlong init_con = (stride_con > 0) ? init_type->_lo : init_type->_hi;
 122     jlong limit_con = (stride_con > 0) ? limit_type->_hi : limit_type->_lo;
 123     int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
 124     jlong trip_count = (limit_con - init_con + stride_m)/stride_con;
 125     if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {
 126       if (init_n->is_Con() && limit_n->is_Con()) {
 127         // Set exact trip count.
 128         cl->set_exact_trip_count((uint)trip_count);
 129       } else if (cl->unrolled_count() == 1) {
 130         // Set maximum trip count before unrolling.
 131         cl->set_trip_count((uint)trip_count);
 132       }
 133     }
 134   }
 135 }
 136 
 137 //------------------------------compute_profile_trip_cnt----------------------------
 138 // Compute loop trip count from profile data as
 139 //    (backedge_count + loop_exit_count) / loop_exit_count
 140 
 141 float IdealLoopTree::compute_profile_trip_cnt_helper(Node* n) {
 142   if (n->is_If()) {
 143     IfNode *iff = n->as_If();
 144     if (iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN) {
 145       Node *exit = is_loop_exit(iff);
 146       if (exit) {
 147         float exit_prob = iff->_prob;
 148         if (exit->Opcode() == Op_IfFalse) {
 149           exit_prob = 1.0 - exit_prob;
 150         }
 151         if (exit_prob > PROB_MIN) {
 152           float exit_cnt = iff->_fcnt * exit_prob;
 153           return exit_cnt;
 154         }
 155       }
 156     }
 157   }
 158   if (n->is_Jump()) {
 159     JumpNode *jmp = n->as_Jump();
 160     if (jmp->_fcnt != COUNT_UNKNOWN) {
 161       float* probs = jmp->_probs;
 162       float exit_prob = 0;
 163       PhaseIdealLoop *phase = _phase;
 164       for (DUIterator_Fast imax, i = jmp->fast_outs(imax); i < imax; i++) {
 165         JumpProjNode* u = jmp->fast_out(i)->as_JumpProj();
 166         if (!is_member(_phase->get_loop(u))) {
 167           exit_prob += probs[u->_con];
 168         }
 169       }
 170       return exit_prob * jmp->_fcnt;
 171     }
 172   }
 173   return 0;
 174 }
 175 
 176 void IdealLoopTree::compute_profile_trip_cnt(PhaseIdealLoop *phase) {
 177   if (!_head->is_Loop()) {
 178     return;
 179   }
 180   LoopNode* head = _head->as_Loop();
 181   if (head->profile_trip_cnt() != COUNT_UNKNOWN) {
 182     return; // Already computed
 183   }
 184   float trip_cnt = (float)max_jint; // default is big
 185 
 186   Node* back = head->in(LoopNode::LoopBackControl);
 187   while (back != head) {
 188     if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 189         back->in(0) &&
 190         back->in(0)->is_If() &&
 191         back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&
 192         back->in(0)->as_If()->_prob != PROB_UNKNOWN &&
 193         (back->Opcode() == Op_IfTrue ? 1-back->in(0)->as_If()->_prob : back->in(0)->as_If()->_prob) > PROB_MIN) {
 194       break;
 195     }
 196     back = phase->idom(back);
 197   }
 198   if (back != head) {
 199     assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&
 200            back->in(0), "if-projection exists");
 201     IfNode* back_if = back->in(0)->as_If();
 202     float loop_back_cnt = back_if->_fcnt * (back->Opcode() == Op_IfTrue ? back_if->_prob : (1 - back_if->_prob));
 203 
 204     // Now compute a loop exit count
 205     float loop_exit_cnt = 0.0f;
 206     if (_child == NULL) {
 207       for (uint i = 0; i < _body.size(); i++) {
 208         Node *n = _body[i];
 209         loop_exit_cnt += compute_profile_trip_cnt_helper(n);
 210       }
 211     } else {
 212       ResourceMark rm;
 213       Unique_Node_List wq;
 214       wq.push(back);
 215       for (uint i = 0; i < wq.size(); i++) {
 216         Node *n = wq.at(i);
 217         assert(n->is_CFG(), "only control nodes");
 218         if (n != head) {
 219           if (n->is_Region()) {
 220             for (uint j = 1; j < n->req(); j++) {
 221               wq.push(n->in(j));
 222             }
 223           } else {
 224             loop_exit_cnt += compute_profile_trip_cnt_helper(n);
 225             wq.push(n->in(0));
 226           }
 227         }
 228       }
 229 
 230     }
 231     if (loop_exit_cnt > 0.0f) {
 232       trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;
 233     } else {
 234       // No exit count so use
 235       trip_cnt = loop_back_cnt;
 236     }
 237   } else {
 238     head->mark_profile_trip_failed();
 239   }
 240 #ifndef PRODUCT
 241   if (TraceProfileTripCount) {
 242     tty->print_cr("compute_profile_trip_cnt  lp: %d cnt: %f\n", head->_idx, trip_cnt);
 243   }
 244 #endif
 245   head->set_profile_trip_cnt(trip_cnt);
 246 }
 247 
 248 //---------------------is_invariant_addition-----------------------------
 249 // Return nonzero index of invariant operand for an Add or Sub
 250 // of (nonconstant) invariant and variant values. Helper for reassociate_invariants.
 251 int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {
 252   int op = n->Opcode();
 253   if (op == Op_AddI || op == Op_SubI) {
 254     bool in1_invar = this->is_invariant(n->in(1));
 255     bool in2_invar = this->is_invariant(n->in(2));
 256     if (in1_invar && !in2_invar) return 1;
 257     if (!in1_invar && in2_invar) return 2;
 258   }
 259   return 0;
 260 }
 261 
 262 //---------------------reassociate_add_sub-----------------------------
 263 // Reassociate invariant add and subtract expressions:
 264 //
 265 // inv1 + (x + inv2)  =>  ( inv1 + inv2) + x
 266 // (x + inv2) + inv1  =>  ( inv1 + inv2) + x
 267 // inv1 + (x - inv2)  =>  ( inv1 - inv2) + x
 268 // inv1 - (inv2 - x)  =>  ( inv1 - inv2) + x
 269 // (x + inv2) - inv1  =>  (-inv1 + inv2) + x
 270 // (x - inv2) + inv1  =>  ( inv1 - inv2) + x
 271 // (x - inv2) - inv1  =>  (-inv1 - inv2) + x
 272 // inv1 + (inv2 - x)  =>  ( inv1 + inv2) - x
 273 // inv1 - (x - inv2)  =>  ( inv1 + inv2) - x
 274 // (inv2 - x) + inv1  =>  ( inv1 + inv2) - x
 275 // (inv2 - x) - inv1  =>  (-inv1 + inv2) - x
 276 // inv1 - (x + inv2)  =>  ( inv1 - inv2) - x
 277 //
 278 Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {
 279   if ((!n1->is_Add() && !n1->is_Sub()) || n1->outcnt() == 0) return NULL;
 280   if (is_invariant(n1)) return NULL;
 281   int inv1_idx = is_invariant_addition(n1, phase);
 282   if (!inv1_idx) return NULL;
 283   // Don't mess with add of constant (igvn moves them to expression tree root.)
 284   if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;
 285   Node* inv1 = n1->in(inv1_idx);
 286   Node* n2 = n1->in(3 - inv1_idx);
 287   int inv2_idx = is_invariant_addition(n2, phase);
 288   if (!inv2_idx) return NULL;
 289   Node* x    = n2->in(3 - inv2_idx);
 290   Node* inv2 = n2->in(inv2_idx);
 291 
 292   bool neg_x    = n2->is_Sub() && inv2_idx == 1;
 293   bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;
 294   bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;
 295   if (n1->is_Sub() && inv1_idx == 1) {
 296     neg_x    = !neg_x;
 297     neg_inv2 = !neg_inv2;
 298   }
 299   Node* inv1_c = phase->get_ctrl(inv1);
 300   Node* inv2_c = phase->get_ctrl(inv2);
 301   Node* n_inv1;
 302   if (neg_inv1) {
 303     Node *zero = phase->_igvn.intcon(0);
 304     phase->set_ctrl(zero, phase->C->root());
 305     n_inv1 = new SubINode(zero, inv1);
 306     phase->register_new_node(n_inv1, inv1_c);
 307   } else {
 308     n_inv1 = inv1;
 309   }
 310   Node* inv;
 311   if (neg_inv2) {
 312     inv = new SubINode(n_inv1, inv2);
 313   } else {
 314     inv = new AddINode(n_inv1, inv2);
 315   }
 316   phase->register_new_node(inv, phase->get_early_ctrl(inv));
 317 
 318   Node* addx;
 319   if (neg_x) {
 320     addx = new SubINode(inv, x);
 321   } else {
 322     addx = new AddINode(x, inv);
 323   }
 324   phase->register_new_node(addx, phase->get_ctrl(x));
 325   phase->_igvn.replace_node(n1, addx);
 326   assert(phase->get_loop(phase->get_ctrl(n1)) == this, "");
 327   _body.yank(n1);
 328   return addx;
 329 }
 330 
 331 //---------------------reassociate_invariants-----------------------------
 332 // Reassociate invariant expressions:
 333 void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {
 334   for (int i = _body.size() - 1; i >= 0; i--) {
 335     Node *n = _body.at(i);
 336     for (int j = 0; j < 5; j++) {
 337       Node* nn = reassociate_add_sub(n, phase);
 338       if (nn == NULL) break;
 339       n = nn; // again
 340     };
 341   }
 342 }
 343 
 344 //------------------------------policy_peeling---------------------------------
 345 // Return TRUE or FALSE if the loop should be peeled or not.  Peel if we can
 346 // make some loop-invariant test (usually a null-check) happen before the loop.
 347 bool IdealLoopTree::policy_peeling(PhaseIdealLoop *phase) const {
 348   IdealLoopTree *loop = (IdealLoopTree*)this;
 349 
 350   // If nodes are depleted, some transform has miscalculated its needs.
 351   assert(!phase->exceeding_node_budget(), "sanity");
 352 
 353   uint body_size = loop->_body.size();
 354   // Peeling does loop cloning which can result in O(N^2) node construction
 355   if (body_size > 255) {
 356     return false;   // Prevent overflow for large body size
 357   }
 358   uint estimate = body_size * body_size;
 359   if (phase->exceeding_node_budget(estimate)) {
 360     return false;   // Too large to safely clone
 361   }
 362 
 363   // check for vectorized loops, any peeling done was already applied
 364   if (_head->is_CountedLoop()) {
 365     CountedLoopNode* cl = _head->as_CountedLoop();
 366     if (cl->is_unroll_only() || cl->trip_count() == 1) {
 367       return false;
 368     }
 369   }
 370 
 371   Node* test = loop->tail();
 372 
 373   while (test != _head) {       // Scan till run off top of loop
 374     if (test->is_If()) {        // Test?
 375       Node *ctrl = phase->get_ctrl(test->in(1));
 376       if (ctrl->is_top()) {
 377         return false;           // Found dead test on live IF?  No peeling!
 378       }
 379       // Standard IF only has one input value to check for loop invariance
 380       assert(test->Opcode() == Op_If ||
 381              test->Opcode() == Op_CountedLoopEnd ||
 382              test->Opcode() == Op_RangeCheck,
 383              "Check this code when new subtype is added");
 384       // Condition is not a member of this loop?
 385       if (!is_member(phase->get_loop(ctrl)) && is_loop_exit(test)) {
 386         // Found reason to peel!
 387         return phase->may_require_nodes(estimate);
 388       }
 389     }
 390     // Walk up dominators to loop _head looking for test which is
 391     // executed on every path thru loop.
 392     test = phase->idom(test);
 393   }
 394   return false;
 395 }
 396 
 397 //------------------------------peeled_dom_test_elim---------------------------
 398 // If we got the effect of peeling, either by actually peeling or by making
 399 // a pre-loop which must execute at least once, we can remove all
 400 // loop-invariant dominated tests in the main body.
 401 void PhaseIdealLoop::peeled_dom_test_elim(IdealLoopTree *loop, Node_List &old_new) {
 402   bool progress = true;
 403   while (progress) {
 404     progress = false;           // Reset for next iteration
 405     Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();
 406     Node *test = prev->in(0);
 407     while (test != loop->_head) { // Scan till run off top of loop
 408 
 409       int p_op = prev->Opcode();
 410       if ((p_op == Op_IfFalse || p_op == Op_IfTrue) &&
 411           test->is_If() &&      // Test?
 412           !test->in(1)->is_Con() && // And not already obvious?
 413           // Condition is not a member of this loop?
 414           !loop->is_member(get_loop(get_ctrl(test->in(1))))){
 415         // Walk loop body looking for instances of this test
 416         for (uint i = 0; i < loop->_body.size(); i++) {
 417           Node *n = loop->_body.at(i);
 418           if (n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/) {
 419             // IfNode was dominated by version in peeled loop body
 420             progress = true;
 421             dominated_by(old_new[prev->_idx], n);
 422           }
 423         }
 424       }
 425       prev = test;
 426       test = idom(test);
 427     } // End of scan tests in loop
 428 
 429   } // End of while (progress)
 430 }
 431 
 432 //------------------------------do_peeling-------------------------------------
 433 // Peel the first iteration of the given loop.
 434 // Step 1: Clone the loop body.  The clone becomes the peeled iteration.
 435 //         The pre-loop illegally has 2 control users (old & new loops).
 436 // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
 437 //         Do this by making the old-loop fall-in edges act as if they came
 438 //         around the loopback from the prior iteration (follow the old-loop
 439 //         backedges) and then map to the new peeled iteration.  This leaves
 440 //         the pre-loop with only 1 user (the new peeled iteration), but the
 441 //         peeled-loop backedge has 2 users.
 442 // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
 443 //         extra backedge user.
 444 //
 445 //                   orig
 446 //
 447 //                  stmt1
 448 //                    |
 449 //                    v
 450 //              loop predicate
 451 //                    |
 452 //                    v
 453 //                   loop<----+
 454 //                     |      |
 455 //                   stmt2    |
 456 //                     |      |
 457 //                     v      |
 458 //                    if      ^
 459 //                   / \      |
 460 //                  /   \     |
 461 //                 v     v    |
 462 //               false true   |
 463 //               /       \    |
 464 //              /         ----+
 465 //             |
 466 //             v
 467 //           exit
 468 //
 469 //
 470 //            after clone loop
 471 //
 472 //                   stmt1
 473 //                     |
 474 //                     v
 475 //               loop predicate
 476 //                 /       \
 477 //        clone   /         \   orig
 478 //               /           \
 479 //              /             \
 480 //             v               v
 481 //   +---->loop clone          loop<----+
 482 //   |      |                    |      |
 483 //   |    stmt2 clone          stmt2    |
 484 //   |      |                    |      |
 485 //   |      v                    v      |
 486 //   ^      if clone            If      ^
 487 //   |      / \                / \      |
 488 //   |     /   \              /   \     |
 489 //   |    v     v            v     v    |
 490 //   |    true  false      false true   |
 491 //   |    /         \      /       \    |
 492 //   +----           \    /         ----+
 493 //                    \  /
 494 //                    1v v2
 495 //                  region
 496 //                     |
 497 //                     v
 498 //                   exit
 499 //
 500 //
 501 //         after peel and predicate move
 502 //
 503 //                   stmt1
 504 //                    /
 505 //                   /
 506 //        clone     /            orig
 507 //                 /
 508 //                /              +----------+
 509 //               /               |          |
 510 //              /          loop predicate   |
 511 //             /                 |          |
 512 //            v                  v          |
 513 //   TOP-->loop clone          loop<----+   |
 514 //          |                    |      |   |
 515 //        stmt2 clone          stmt2    |   |
 516 //          |                    |      |   ^
 517 //          v                    v      |   |
 518 //          if clone            If      ^   |
 519 //          / \                / \      |   |
 520 //         /   \              /   \     |   |
 521 //        v     v            v     v    |   |
 522 //      true   false      false  true   |   |
 523 //        |         \      /       \    |   |
 524 //        |          \    /         ----+   ^
 525 //        |           \  /                  |
 526 //        |           1v v2                 |
 527 //        v         region                  |
 528 //        |            |                    |
 529 //        |            v                    |
 530 //        |          exit                   |
 531 //        |                                 |
 532 //        +--------------->-----------------+
 533 //
 534 //
 535 //              final graph
 536 //
 537 //                  stmt1
 538 //                    |
 539 //                    v
 540 //                  stmt2 clone
 541 //                    |
 542 //                    v
 543 //                   if clone
 544 //                  / |
 545 //                 /  |
 546 //                v   v
 547 //            false  true
 548 //             |      |
 549 //             |      v
 550 //             | loop predicate
 551 //             |      |
 552 //             |      v
 553 //             |     loop<----+
 554 //             |      |       |
 555 //             |    stmt2     |
 556 //             |      |       |
 557 //             |      v       |
 558 //             v      if      ^
 559 //             |     /  \     |
 560 //             |    /    \    |
 561 //             |   v     v    |
 562 //             | false  true  |
 563 //             |  |        \  |
 564 //             v  v         --+
 565 //            region
 566 //              |
 567 //              v
 568 //             exit
 569 //
 570 void PhaseIdealLoop::do_peeling(IdealLoopTree *loop, Node_List &old_new) {
 571 
 572   C->set_major_progress();
 573   // Peeling a 'main' loop in a pre/main/post situation obfuscates the
 574   // 'pre' loop from the main and the 'pre' can no longer have its
 575   // iterations adjusted.  Therefore, we need to declare this loop as
 576   // no longer a 'main' loop; it will need new pre and post loops before
 577   // we can do further RCE.
 578 #ifndef PRODUCT
 579   if (TraceLoopOpts) {
 580     tty->print("Peel         ");
 581     loop->dump_head();
 582   }
 583 #endif
 584   LoopNode* head = loop->_head->as_Loop();
 585   bool counted_loop = head->is_CountedLoop();
 586   if (counted_loop) {
 587     CountedLoopNode *cl = head->as_CountedLoop();
 588     assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
 589     cl->set_trip_count(cl->trip_count() - 1);
 590     if (cl->is_main_loop()) {
 591       cl->set_normal_loop();
 592 #ifndef PRODUCT
 593       if (PrintOpto && VerifyLoopOptimizations) {
 594         tty->print("Peeling a 'main' loop; resetting to 'normal' ");
 595         loop->dump_head();
 596       }
 597 #endif
 598     }
 599   }
 600   Node* entry = head->in(LoopNode::EntryControl);
 601 
 602   // Step 1: Clone the loop body.  The clone becomes the peeled iteration.
 603   //         The pre-loop illegally has 2 control users (old & new loops).
 604   clone_loop(loop, old_new, dom_depth(head->skip_strip_mined()), ControlAroundStripMined);
 605 
 606   // Step 2: Make the old-loop fall-in edges point to the peeled iteration.
 607   //         Do this by making the old-loop fall-in edges act as if they came
 608   //         around the loopback from the prior iteration (follow the old-loop
 609   //         backedges) and then map to the new peeled iteration.  This leaves
 610   //         the pre-loop with only 1 user (the new peeled iteration), but the
 611   //         peeled-loop backedge has 2 users.
 612   Node* new_entry = old_new[head->in(LoopNode::LoopBackControl)->_idx];
 613   _igvn.hash_delete(head->skip_strip_mined());
 614   head->skip_strip_mined()->set_req(LoopNode::EntryControl, new_entry);
 615   for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) {
 616     Node* old = head->fast_out(j);
 617     if (old->in(0) == loop->_head && old->req() == 3 && old->is_Phi()) {
 618       Node* new_exit_value = old_new[old->in(LoopNode::LoopBackControl)->_idx];
 619       if (!new_exit_value)     // Backedge value is ALSO loop invariant?
 620         // Then loop body backedge value remains the same.
 621         new_exit_value = old->in(LoopNode::LoopBackControl);
 622       _igvn.hash_delete(old);
 623       old->set_req(LoopNode::EntryControl, new_exit_value);
 624     }
 625   }
 626 
 627 
 628   // Step 3: Cut the backedge on the clone (so its not a loop) and remove the
 629   //         extra backedge user.
 630   Node* new_head = old_new[head->_idx];
 631   _igvn.hash_delete(new_head);
 632   new_head->set_req(LoopNode::LoopBackControl, C->top());
 633   for (DUIterator_Fast j2max, j2 = new_head->fast_outs(j2max); j2 < j2max; j2++) {
 634     Node* use = new_head->fast_out(j2);
 635     if (use->in(0) == new_head && use->req() == 3 && use->is_Phi()) {
 636       _igvn.hash_delete(use);
 637       use->set_req(LoopNode::LoopBackControl, C->top());
 638     }
 639   }
 640 
 641 
 642   // Step 4: Correct dom-depth info.  Set to loop-head depth.
 643   int dd = dom_depth(head);
 644   set_idom(head, head->in(1), dd);
 645   for (uint j3 = 0; j3 < loop->_body.size(); j3++) {
 646     Node *old = loop->_body.at(j3);
 647     Node *nnn = old_new[old->_idx];
 648     if (!has_ctrl(nnn)) {
 649       set_idom(nnn, idom(nnn), dd-1);
 650     }
 651   }
 652 
 653   // Now force out all loop-invariant dominating tests.  The optimizer
 654   // finds some, but we _know_ they are all useless.
 655   peeled_dom_test_elim(loop,old_new);
 656 
 657   loop->record_for_igvn();
 658 }
 659 
 660 #define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop
 661 
 662 //------------------------------policy_maximally_unroll------------------------
 663 // Calculate exact loop trip count and return true if loop can be maximally
 664 // unrolled.
 665 bool IdealLoopTree::policy_maximally_unroll(PhaseIdealLoop *phase) const {
 666   CountedLoopNode *cl = _head->as_CountedLoop();
 667   assert(cl->is_normal_loop(), "");
 668   if (!cl->is_valid_counted_loop()) {
 669     return false; // Malformed counted loop
 670   }
 671   if (!cl->has_exact_trip_count()) {
 672     // Trip count is not exact.
 673     return false;
 674   }
 675 
 676   uint trip_count = cl->trip_count();
 677   // Note, max_juint is used to indicate unknown trip count.
 678   assert(trip_count > 1, "one iteration loop should be optimized out already");
 679   assert(trip_count < max_juint, "exact trip_count should be less than max_uint.");
 680 
 681   // If nodes are depleted, some transform has miscalculated its needs.
 682   assert(!phase->exceeding_node_budget(), "sanity");
 683 
 684   // Real policy: if we maximally unroll, does it get too big?
 685   // Allow the unrolled mess to get larger than standard loop
 686   // size.  After all, it will no longer be a loop.
 687   uint body_size    = _body.size();
 688   uint unroll_limit = (uint)LoopUnrollLimit * 4;
 689   assert((intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
 690   if (trip_count > unroll_limit || body_size > unroll_limit) {
 691     return false;
 692   }
 693 
 694   // Take into account that after unroll conjoined heads and tails will fold,
 695   // otherwise policy_unroll() may allow more unrolling than max unrolling.
 696   uint new_body_size = est_loop_clone_sz(trip_count, body_size - EMPTY_LOOP_SIZE);
 697 
 698   if (new_body_size == UINT_MAX) { // Check for bad estimate (overflow).
 699     return false;
 700   }
 701 
 702   // Fully unroll a loop with few iterations regardless next conditions since
 703   // following loop optimizations will split such loop anyway (pre-main-post).
 704   if (trip_count <= 3) {
 705     return phase->may_require_nodes(new_body_size);
 706   }
 707 
 708   if (new_body_size > unroll_limit ||
 709       // Unrolling can result in a large amount of node construction
 710       phase->exceeding_node_budget(new_body_size)) {
 711     return false;
 712   }
 713 
 714   // Do not unroll a loop with String intrinsics code.
 715   // String intrinsics are large and have loops.
 716   for (uint k = 0; k < _body.size(); k++) {
 717     Node* n = _body.at(k);
 718     switch (n->Opcode()) {
 719       case Op_StrComp:
 720       case Op_StrEquals:
 721       case Op_StrIndexOf:
 722       case Op_StrIndexOfChar:
 723       case Op_EncodeISOArray:
 724       case Op_AryEq:
 725       case Op_HasNegatives: {
 726         return false;
 727       }
 728 #if INCLUDE_RTM_OPT
 729       case Op_FastLock:
 730       case Op_FastUnlock: {
 731         // Don't unroll RTM locking code because it is large.
 732         if (UseRTMLocking) {
 733           return false;
 734         }
 735       }
 736 #endif
 737     } // switch
 738   }
 739 
 740   return phase->may_require_nodes(new_body_size);
 741 }
 742 
 743 
 744 //------------------------------policy_unroll----------------------------------
 745 // Return TRUE or FALSE if the loop should be unrolled or not.  Unroll if the
 746 // loop is a CountedLoop and the body is small enough.
 747 bool IdealLoopTree::policy_unroll(PhaseIdealLoop *phase) {
 748 
 749   CountedLoopNode *cl = _head->as_CountedLoop();
 750   assert(cl->is_normal_loop() || cl->is_main_loop(), "");
 751 
 752   if (!cl->is_valid_counted_loop()) {
 753     return false; // Malformed counted loop
 754   }
 755 
 756   // If nodes are depleted, some transform has miscalculated its needs.
 757   assert(!phase->exceeding_node_budget(), "sanity");
 758 
 759   // Protect against over-unrolling.
 760   // After split at least one iteration will be executed in pre-loop.
 761   if (cl->trip_count() <= (cl->is_normal_loop() ? 2u : 1u)) {
 762     return false;
 763   }
 764   _local_loop_unroll_limit  = LoopUnrollLimit;
 765   _local_loop_unroll_factor = 4;
 766   int future_unroll_cnt = cl->unrolled_count() * 2;
 767   if (!cl->is_vectorized_loop()) {
 768     if (future_unroll_cnt > LoopMaxUnroll) return false;
 769   } else {
 770     // obey user constraints on vector mapped loops with additional unrolling applied
 771     int unroll_constraint = (cl->slp_max_unroll()) ? cl->slp_max_unroll() : 1;
 772     if ((future_unroll_cnt / unroll_constraint) > LoopMaxUnroll) return false;
 773   }
 774 
 775   // Check for initial stride being a small enough constant
 776   if (abs(cl->stride_con()) > (1<<2)*future_unroll_cnt) return false;
 777 
 778   // Don't unroll if the next round of unrolling would push us
 779   // over the expected trip count of the loop.  One is subtracted
 780   // from the expected trip count because the pre-loop normally
 781   // executes 1 iteration.
 782   if (UnrollLimitForProfileCheck > 0 &&
 783       cl->profile_trip_cnt() != COUNT_UNKNOWN &&
 784       future_unroll_cnt        > UnrollLimitForProfileCheck &&
 785       (float)future_unroll_cnt > cl->profile_trip_cnt() - 1.0) {
 786     return false;
 787   }
 788 
 789   // When unroll count is greater than LoopUnrollMin, don't unroll if:
 790   //   the residual iterations are more than 10% of the trip count
 791   //   and rounds of "unroll,optimize" are not making significant progress
 792   //   Progress defined as current size less than 20% larger than previous size.
 793   if (UseSuperWord && cl->node_count_before_unroll() > 0 &&
 794       future_unroll_cnt > LoopUnrollMin &&
 795       (future_unroll_cnt - 1) * (100 / LoopPercentProfileLimit) > cl->profile_trip_cnt() &&
 796       1.2 * cl->node_count_before_unroll() < (double)_body.size()) {
 797     return false;
 798   }
 799 
 800   Node *init_n = cl->init_trip();
 801   Node *limit_n = cl->limit();
 802   int stride_con = cl->stride_con();
 803   if (limit_n == NULL) return false; // We will dereference it below.
 804 
 805   // Non-constant bounds.
 806   // Protect against over-unrolling when init or/and limit are not constant
 807   // (so that trip_count's init value is maxint) but iv range is known.
 808   if (init_n == NULL || !init_n->is_Con() || !limit_n->is_Con()) {
 809     Node* phi = cl->phi();
 810     if (phi != NULL) {
 811       assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
 812       const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();
 813       int next_stride = stride_con * 2; // stride after this unroll
 814       if (next_stride > 0) {
 815         if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow
 816             iv_type->_lo + next_stride >  iv_type->_hi) {
 817           return false;  // over-unrolling
 818         }
 819       } else if (next_stride < 0) {
 820         if (iv_type->_hi + next_stride >= iv_type->_hi || // overflow
 821             iv_type->_hi + next_stride <  iv_type->_lo) {
 822           return false;  // over-unrolling
 823         }
 824       }
 825     }
 826   }
 827 
 828   // After unroll limit will be adjusted: new_limit = limit-stride.
 829   // Bailout if adjustment overflow.
 830   const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
 831   if ((stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi)) ||
 832       (stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo)))
 833     return false;  // overflow
 834 
 835   // Adjust body_size to determine if we unroll or not
 836   uint body_size = _body.size();
 837   // Key test to unroll loop in CRC32 java code
 838   int xors_in_loop = 0;
 839   // Also count ModL, DivL and MulL which expand mightly
 840   for (uint k = 0; k < _body.size(); k++) {
 841     Node* n = _body.at(k);
 842     switch (n->Opcode()) {
 843       case Op_XorI: xors_in_loop++; break; // CRC32 java code
 844       case Op_ModL: body_size += 30; break;
 845       case Op_DivL: body_size += 30; break;
 846       case Op_MulL: body_size += 10; break;
 847       case Op_StrComp:
 848       case Op_StrEquals:
 849       case Op_StrIndexOf:
 850       case Op_StrIndexOfChar:
 851       case Op_EncodeISOArray:
 852       case Op_AryEq:
 853       case Op_HasNegatives: {
 854         // Do not unroll a loop with String intrinsics code.
 855         // String intrinsics are large and have loops.
 856         return false;
 857       }
 858 #if INCLUDE_RTM_OPT
 859       case Op_FastLock:
 860       case Op_FastUnlock: {
 861         // Don't unroll RTM locking code because it is large.
 862         if (UseRTMLocking) {
 863           return false;
 864         }
 865       }
 866 #endif
 867     } // switch
 868   }
 869 
 870   if (UseSuperWord) {
 871     if (!cl->is_reduction_loop()) {
 872       phase->mark_reductions(this);
 873     }
 874 
 875     // Only attempt slp analysis when user controls do not prohibit it
 876     if (LoopMaxUnroll > _local_loop_unroll_factor) {
 877       // Once policy_slp_analysis succeeds, mark the loop with the
 878       // maximal unroll factor so that we minimize analysis passes
 879       if (future_unroll_cnt >= _local_loop_unroll_factor) {
 880         policy_unroll_slp_analysis(cl, phase, future_unroll_cnt);
 881       }
 882     }
 883   }
 884 
 885   int slp_max_unroll_factor = cl->slp_max_unroll();
 886   if ((LoopMaxUnroll < slp_max_unroll_factor) && FLAG_IS_DEFAULT(LoopMaxUnroll) && UseSubwordForMaxVector) {
 887     LoopMaxUnroll = slp_max_unroll_factor;
 888   }
 889 
 890   uint estimate = est_loop_clone_sz(2, body_size);
 891 
 892   if (cl->has_passed_slp()) {
 893     if (slp_max_unroll_factor >= future_unroll_cnt) {
 894       return phase->may_require_nodes(estimate);
 895     }
 896     return false; // Loop too big.
 897   }
 898 
 899   // Check for being too big
 900   if (body_size > (uint)_local_loop_unroll_limit) {
 901     if ((cl->is_subword_loop() || xors_in_loop >= 4) && body_size < 4u * LoopUnrollLimit) {
 902       return phase->may_require_nodes(estimate);
 903     }
 904     return false; // Loop too big.
 905   }
 906 
 907   if (cl->is_unroll_only()) {
 908     if (TraceSuperWordLoopUnrollAnalysis) {
 909       tty->print_cr("policy_unroll passed vector loop(vlen=%d, factor=%d)\n",
 910                     slp_max_unroll_factor, future_unroll_cnt);
 911     }
 912   }
 913 
 914   // Unroll once!  (Each trip will soon do double iterations)
 915   return phase->may_require_nodes(estimate);
 916 }
 917 
 918 void IdealLoopTree::policy_unroll_slp_analysis(CountedLoopNode *cl, PhaseIdealLoop *phase, int future_unroll_cnt) {
 919 
 920   // If nodes are depleted, some transform has miscalculated its needs.
 921   assert(!phase->exceeding_node_budget(), "sanity");
 922 
 923   // Enable this functionality target by target as needed
 924   if (SuperWordLoopUnrollAnalysis) {
 925     if (!cl->was_slp_analyzed()) {
 926       SuperWord sw(phase);
 927       sw.transform_loop(this, false);
 928 
 929       // If the loop is slp canonical analyze it
 930       if (sw.early_return() == false) {
 931         sw.unrolling_analysis(_local_loop_unroll_factor);
 932       }
 933     }
 934 
 935     if (cl->has_passed_slp()) {
 936       int slp_max_unroll_factor = cl->slp_max_unroll();
 937       if (slp_max_unroll_factor >= future_unroll_cnt) {
 938         int new_limit = cl->node_count_before_unroll() * slp_max_unroll_factor;
 939         if (new_limit > LoopUnrollLimit) {
 940           if (TraceSuperWordLoopUnrollAnalysis) {
 941             tty->print_cr("slp analysis unroll=%d, default limit=%d\n", new_limit, _local_loop_unroll_limit);
 942           }
 943           _local_loop_unroll_limit = new_limit;
 944         }
 945       }
 946     }
 947   }
 948 }
 949 
 950 //------------------------------policy_align-----------------------------------
 951 // Return TRUE or FALSE if the loop should be cache-line aligned.  Gather the
 952 // expression that does the alignment.  Note that only one array base can be
 953 // aligned in a loop (unless the VM guarantees mutual alignment).  Note that
 954 // if we vectorize short memory ops into longer memory ops, we may want to
 955 // increase alignment.
 956 bool IdealLoopTree::policy_align(PhaseIdealLoop *phase) const {
 957   return false;
 958 }
 959 
 960 //------------------------------policy_range_check-----------------------------
 961 // Return TRUE or FALSE if the loop should be range-check-eliminated.
 962 // Actually we do iteration-splitting, a more powerful form of RCE.
 963 bool IdealLoopTree::policy_range_check(PhaseIdealLoop *phase) const {
 964   if (!RangeCheckElimination) return false;
 965 
 966   // If nodes are depleted, some transform has miscalculated its needs.
 967   assert(!phase->exceeding_node_budget(), "sanity");
 968 
 969   CountedLoopNode *cl = _head->as_CountedLoop();
 970   // If we unrolled with no intention of doing RCE and we later
 971   // changed our minds, we got no pre-loop.  Either we need to
 972   // make a new pre-loop, or we gotta disallow RCE.
 973   if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
 974   Node *trip_counter = cl->phi();
 975 
 976   // check for vectorized loops, some opts are no longer needed
 977   if (cl->is_unroll_only()) return false;
 978 
 979   // Check loop body for tests of trip-counter plus loop-invariant vs
 980   // loop-invariant.
 981   for (uint i = 0; i < _body.size(); i++) {
 982     Node *iff = _body[i];
 983     if (iff->Opcode() == Op_If ||
 984         iff->Opcode() == Op_RangeCheck) { // Test?
 985 
 986       // Comparing trip+off vs limit
 987       Node *bol = iff->in(1);
 988       if (bol->req() != 2) {
 989         continue; // dead constant test
 990       }
 991       if (!bol->is_Bool()) {
 992         assert(bol->Opcode() == Op_Conv2B, "predicate check only");
 993         continue;
 994       }
 995       if (bol->as_Bool()->_test._test == BoolTest::ne) {
 996         continue; // not RC
 997       }
 998       Node *cmp = bol->in(1);
 999       Node *rc_exp = cmp->in(1);
1000       Node *limit = cmp->in(2);
1001 
1002       Node *limit_c = phase->get_ctrl(limit);
1003       if (limit_c == phase->C->top()) {
1004         return false;           // Found dead test on live IF?  No RCE!
1005       }
1006       if (is_member(phase->get_loop(limit_c))) {
1007         // Compare might have operands swapped; commute them
1008         rc_exp = cmp->in(2);
1009         limit  = cmp->in(1);
1010         limit_c = phase->get_ctrl(limit);
1011         if (is_member(phase->get_loop(limit_c))) {
1012           continue;             // Both inputs are loop varying; cannot RCE
1013         }
1014       }
1015 
1016       if (!phase->is_scaled_iv_plus_offset(rc_exp, trip_counter, NULL, NULL)) {
1017         continue;
1018       }
1019       // Found a test like 'trip+off vs  limit'.  Test is an IfNode, has two
1020       // (2) projections.  If BOTH are in  the loop we need loop unswitching
1021       // instead of iteration splitting.
1022       if (is_loop_exit(iff)) {
1023         // Found valid reason to split iterations (if there is room).
1024         // NOTE: Usually a gross overestimate.
1025         return phase->may_require_nodes(est_loop_clone_sz(2, _body.size()));
1026       }
1027     } // End of is IF
1028   }
1029 
1030   return false;
1031 }
1032 
1033 //------------------------------policy_peel_only-------------------------------
1034 // Return TRUE or FALSE if the loop should NEVER be RCE'd or aligned.  Useful
1035 // for unrolling loops with NO array accesses.
1036 bool IdealLoopTree::policy_peel_only(PhaseIdealLoop *phase) const {
1037 
1038   // If nodes are depleted, some transform has miscalculated its needs.
1039   assert(!phase->exceeding_node_budget(), "sanity");
1040 
1041   // check for vectorized loops, any peeling done was already applied
1042   if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
1043     return false;
1044   }
1045 
1046   for (uint i = 0; i < _body.size(); i++) {
1047     if (_body[i]->is_Mem()) {
1048       return false;
1049     }
1050   }
1051   // No memory accesses at all!
1052   return true;
1053 }
1054 
1055 //------------------------------clone_up_backedge_goo--------------------------
1056 // If Node n lives in the back_ctrl block and cannot float, we clone a private
1057 // version of n in preheader_ctrl block and return that, otherwise return n.
1058 Node *PhaseIdealLoop::clone_up_backedge_goo(Node *back_ctrl, Node *preheader_ctrl, Node *n, VectorSet &visited, Node_Stack &clones) {
1059   if (get_ctrl(n) != back_ctrl) return n;
1060 
1061   // Only visit once
1062   if (visited.test_set(n->_idx)) {
1063     Node *x = clones.find(n->_idx);
1064     return (x != NULL) ? x : n;
1065   }
1066 
1067   Node *x = NULL;               // If required, a clone of 'n'
1068   // Check for 'n' being pinned in the backedge.
1069   if (n->in(0) && n->in(0) == back_ctrl) {
1070     assert(clones.find(n->_idx) == NULL, "dead loop");
1071     x = n->clone();             // Clone a copy of 'n' to preheader
1072     clones.push(x, n->_idx);
1073     x->set_req(0, preheader_ctrl); // Fix x's control input to preheader
1074   }
1075 
1076   // Recursive fixup any other input edges into x.
1077   // If there are no changes we can just return 'n', otherwise
1078   // we need to clone a private copy and change it.
1079   for (uint i = 1; i < n->req(); i++) {
1080     Node *g = clone_up_backedge_goo(back_ctrl, preheader_ctrl, n->in(i), visited, clones);
1081     if (g != n->in(i)) {
1082       if (!x) {
1083         assert(clones.find(n->_idx) == NULL, "dead loop");
1084         x = n->clone();
1085         clones.push(x, n->_idx);
1086       }
1087       x->set_req(i, g);
1088     }
1089   }
1090   if (x) {                     // x can legally float to pre-header location
1091     register_new_node(x, preheader_ctrl);
1092     return x;
1093   } else {                      // raise n to cover LCA of uses
1094     set_ctrl(n, find_non_split_ctrl(back_ctrl->in(0)));
1095   }
1096   return n;
1097 }
1098 
1099 Node* PhaseIdealLoop::cast_incr_before_loop(Node* incr, Node* ctrl, Node* loop) {
1100   Node* castii = new CastIINode(incr, TypeInt::INT, true);
1101   castii->set_req(0, ctrl);
1102   register_new_node(castii, ctrl);
1103   for (DUIterator_Fast imax, i = incr->fast_outs(imax); i < imax; i++) {
1104     Node* n = incr->fast_out(i);
1105     if (n->is_Phi() && n->in(0) == loop) {
1106       int nrep = n->replace_edge(incr, castii);
1107       return castii;
1108     }
1109   }
1110   return NULL;
1111 }
1112 
1113 // Make a copy of the skeleton range check predicates before the main
1114 // loop and set the initial value of loop as input. After unrolling,
1115 // the range of values for the induction variable in the main loop can
1116 // fall outside the allowed range of values by the array access (main
1117 // loop is never executed). When that happens, range check
1118 // CastII/ConvI2L nodes cause some data paths to die. For consistency,
1119 // the control paths must die too but the range checks were removed by
1120 // predication. The range checks that we add here guarantee that they do.
1121 void PhaseIdealLoop::duplicate_predicates_helper(Node* predicate, Node* start, Node* end,
1122                                                  IdealLoopTree* outer_loop, LoopNode* outer_main_head,
1123                                                  uint dd_main_head) {
1124   if (predicate != NULL) {
1125     IfNode* iff = predicate->in(0)->as_If();
1126     ProjNode* uncommon_proj = iff->proj_out(1 - predicate->as_Proj()->_con);
1127     Node* rgn = uncommon_proj->unique_ctrl_out();
1128     assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct");
1129     assert(iff->in(1)->in(1)->Opcode() == Op_Opaque1, "unexpected predicate shape");
1130     predicate = iff->in(0);
1131     Node* current_proj = outer_main_head->in(LoopNode::EntryControl);
1132     Node* prev_proj = current_proj;
1133     while (predicate != NULL && predicate->is_Proj() && predicate->in(0)->is_If()) {
1134       iff = predicate->in(0)->as_If();
1135       uncommon_proj = iff->proj_out(1 - predicate->as_Proj()->_con);
1136       if (uncommon_proj->unique_ctrl_out() != rgn)
1137         break;
1138       if (iff->in(1)->Opcode() == Op_Opaque4) {
1139         assert(skeleton_predicate_has_opaque(iff), "unexpected");
1140         // Clone the predicate twice and initialize one with the initial
1141         // value of the loop induction variable. Leave the other predicate
1142         // to be initialized when increasing the stride during loop unrolling.
1143         prev_proj = clone_skeleton_predicate(iff, start, predicate, uncommon_proj, current_proj, outer_loop, prev_proj);
1144         assert(skeleton_predicate_has_opaque(prev_proj->in(0)->as_If()) == (start->Opcode() == Op_Opaque1), "");
1145         prev_proj = clone_skeleton_predicate(iff, end, predicate, uncommon_proj, current_proj, outer_loop, prev_proj);
1146         assert(skeleton_predicate_has_opaque(prev_proj->in(0)->as_If()) == (end->Opcode() == Op_Opaque1), "");
1147         // Remove the skeleton predicate from the pre-loop
1148         _igvn.replace_input_of(iff, 1, _igvn.intcon(1));
1149       }
1150       predicate = predicate->in(0)->in(0);
1151     }
1152     _igvn.replace_input_of(outer_main_head, LoopNode::EntryControl, prev_proj);
1153     set_idom(outer_main_head, prev_proj, dd_main_head);
1154   }
1155 }
1156 
1157 static bool skeleton_follow_inputs(Node* n, int op) {
1158   return (n->is_Bool() ||
1159           n->is_Cmp() ||
1160           op == Op_AndL ||
1161           op == Op_OrL ||
1162           op == Op_RShiftL ||
1163           op == Op_LShiftL ||
1164           op == Op_AddL ||
1165           op == Op_AddI ||
1166           op == Op_MulL ||
1167           op == Op_MulI ||
1168           op == Op_SubL ||
1169           op == Op_SubI ||
1170           op == Op_ConvI2L);
1171 }
1172 
1173 bool PhaseIdealLoop::skeleton_predicate_has_opaque(IfNode* iff) {
1174   ResourceMark rm;
1175   Unique_Node_List wq;
1176   wq.push(iff->in(1)->in(1));
1177   for (uint i = 0; i < wq.size(); i++) {
1178     Node* n = wq.at(i);
1179     int op = n->Opcode();
1180     if (skeleton_follow_inputs(n, op)) {
1181       for (uint j = 1; j < n->req(); j++) {
1182         Node* m = n->in(j);
1183         if (m != NULL) {
1184           wq.push(m);
1185         }
1186       }
1187       continue;
1188     }
1189     if (op == Op_Opaque1) {
1190       return true;
1191     }
1192   }
1193   return false;
1194 }
1195 
1196 Node* PhaseIdealLoop::clone_skeleton_predicate(Node* iff, Node* value, Node* predicate, Node* uncommon_proj,
1197                                                Node* current_proj, IdealLoopTree* outer_loop, Node* prev_proj) {
1198   Node_Stack to_clone(2);
1199   to_clone.push(iff->in(1), 1);
1200   uint current = C->unique();
1201   Node* result = NULL;
1202   // Look for the opaque node to replace with the new value
1203   // and clone everything in between. We keep the Opaque4 node
1204   // so the duplicated predicates are eliminated once loop
1205   // opts are over: they are here only to keep the IR graph
1206   // consistent.
1207   do {
1208     Node* n = to_clone.node();
1209     uint i = to_clone.index();
1210     Node* m = n->in(i);
1211     int op = m->Opcode();
1212     if (skeleton_follow_inputs(m, op)) {
1213         to_clone.push(m, 1);
1214         continue;
1215     }
1216     if (op == Op_Opaque1) {
1217       if (n->_idx < current) {
1218         n = n->clone();
1219       }
1220       n->set_req(i, value);
1221       register_new_node(n, current_proj);
1222       to_clone.set_node(n);
1223     }
1224     for (;;) {
1225       Node* cur = to_clone.node();
1226       uint j = to_clone.index();
1227       if (j+1 < cur->req()) {
1228         to_clone.set_index(j+1);
1229         break;
1230       }
1231       to_clone.pop();
1232       if (to_clone.size() == 0) {
1233         result = cur;
1234         break;
1235       }
1236       Node* next = to_clone.node();
1237       j = to_clone.index();
1238       if (next->in(j) != cur) {
1239         assert(cur->_idx >= current || next->in(j)->Opcode() == Op_Opaque1, "new node or Opaque1 being replaced");
1240         if (next->_idx < current) {
1241           next = next->clone();
1242           register_new_node(next, current_proj);
1243           to_clone.set_node(next);
1244         }
1245         next->set_req(j, cur);
1246       }
1247     }
1248   } while (result == NULL);
1249   assert(result->_idx >= current, "new node expected");
1250 
1251   Node* proj = predicate->clone();
1252   Node* other_proj = uncommon_proj->clone();
1253   Node* new_iff = iff->clone();
1254   new_iff->set_req(1, result);
1255   proj->set_req(0, new_iff);
1256   other_proj->set_req(0, new_iff);
1257   Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
1258   register_new_node(frame, C->start());
1259   // It's impossible for the predicate to fail at runtime. Use an Halt node.
1260   Node* halt = new HaltNode(other_proj, frame);
1261   C->root()->add_req(halt);
1262   new_iff->set_req(0, prev_proj);
1263 
1264   register_control(new_iff, outer_loop->_parent, prev_proj);
1265   register_control(proj, outer_loop->_parent, new_iff);
1266   register_control(other_proj, _ltree_root, new_iff);
1267   register_control(halt, _ltree_root, other_proj);
1268   return proj;
1269 }
1270 
1271 void PhaseIdealLoop::duplicate_predicates(CountedLoopNode* pre_head, Node* start, Node* end,
1272                                           IdealLoopTree* outer_loop, LoopNode* outer_main_head,
1273                                           uint dd_main_head) {
1274   if (UseLoopPredicate) {
1275     Node* entry = pre_head->in(LoopNode::EntryControl);
1276     Node* predicate = NULL;
1277     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
1278     if (predicate != NULL) {
1279       entry = skip_loop_predicates(entry);
1280     }
1281     Node* profile_predicate = NULL;
1282     if (UseProfiledLoopPredicate) {
1283       profile_predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
1284       if (profile_predicate != NULL) {
1285         entry = skip_loop_predicates(entry);
1286       }
1287     }
1288     predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
1289     duplicate_predicates_helper(predicate, start, end, outer_loop, outer_main_head, dd_main_head);
1290     duplicate_predicates_helper(profile_predicate, start, end, outer_loop, outer_main_head, dd_main_head);
1291   }
1292 }
1293 
1294 //------------------------------insert_pre_post_loops--------------------------
1295 // Insert pre and post loops.  If peel_only is set, the pre-loop can not have
1296 // more iterations added.  It acts as a 'peel' only, no lower-bound RCE, no
1297 // alignment.  Useful to unroll loops that do no array accesses.
1298 void PhaseIdealLoop::insert_pre_post_loops(IdealLoopTree *loop, Node_List &old_new, bool peel_only) {
1299 
1300 #ifndef PRODUCT
1301   if (TraceLoopOpts) {
1302     if (peel_only)
1303       tty->print("PeelMainPost ");
1304     else
1305       tty->print("PreMainPost  ");
1306     loop->dump_head();
1307   }
1308 #endif
1309   C->set_major_progress();
1310 
1311   // Find common pieces of the loop being guarded with pre & post loops
1312   CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1313   assert(main_head->is_normal_loop(), "");
1314   CountedLoopEndNode *main_end = main_head->loopexit();
1315   assert(main_end->outcnt() == 2, "1 true, 1 false path only");
1316 
1317   Node *pre_header= main_head->in(LoopNode::EntryControl);
1318   Node *init      = main_head->init_trip();
1319   Node *incr      = main_end ->incr();
1320   Node *limit     = main_end ->limit();
1321   Node *stride    = main_end ->stride();
1322   Node *cmp       = main_end ->cmp_node();
1323   BoolTest::mask b_test = main_end->test_trip();
1324 
1325   // Need only 1 user of 'bol' because I will be hacking the loop bounds.
1326   Node *bol = main_end->in(CountedLoopEndNode::TestValue);
1327   if (bol->outcnt() != 1) {
1328     bol = bol->clone();
1329     register_new_node(bol,main_end->in(CountedLoopEndNode::TestControl));
1330     _igvn.replace_input_of(main_end, CountedLoopEndNode::TestValue, bol);
1331   }
1332   // Need only 1 user of 'cmp' because I will be hacking the loop bounds.
1333   if (cmp->outcnt() != 1) {
1334     cmp = cmp->clone();
1335     register_new_node(cmp,main_end->in(CountedLoopEndNode::TestControl));
1336     _igvn.replace_input_of(bol, 1, cmp);
1337   }
1338 
1339   // Add the post loop
1340   CountedLoopNode *post_head = NULL;
1341   Node *main_exit = insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1342 
1343   //------------------------------
1344   // Step B: Create Pre-Loop.
1345 
1346   // Step B1: Clone the loop body.  The clone becomes the pre-loop.  The main
1347   // loop pre-header illegally has 2 control users (old & new loops).
1348   LoopNode* outer_main_head = main_head;
1349   IdealLoopTree* outer_loop = loop;
1350   if (main_head->is_strip_mined()) {
1351     main_head->verify_strip_mined(1);
1352     outer_main_head = main_head->outer_loop();
1353     outer_loop = loop->_parent;
1354     assert(outer_loop->_head == outer_main_head, "broken loop tree");
1355   }
1356   uint dd_main_head = dom_depth(outer_main_head);
1357   clone_loop(loop, old_new, dd_main_head, ControlAroundStripMined);
1358   CountedLoopNode*    pre_head = old_new[main_head->_idx]->as_CountedLoop();
1359   CountedLoopEndNode* pre_end  = old_new[main_end ->_idx]->as_CountedLoopEnd();
1360   pre_head->set_pre_loop(main_head);
1361   Node *pre_incr = old_new[incr->_idx];
1362 
1363   // Reduce the pre-loop trip count.
1364   pre_end->_prob = PROB_FAIR;
1365 
1366   // Find the pre-loop normal exit.
1367   Node* pre_exit = pre_end->proj_out(false);
1368   assert(pre_exit->Opcode() == Op_IfFalse, "");
1369   IfFalseNode *new_pre_exit = new IfFalseNode(pre_end);
1370   _igvn.register_new_node_with_optimizer(new_pre_exit);
1371   set_idom(new_pre_exit, pre_end, dd_main_head);
1372   set_loop(new_pre_exit, outer_loop->_parent);
1373 
1374   // Step B2: Build a zero-trip guard for the main-loop.  After leaving the
1375   // pre-loop, the main-loop may not execute at all.  Later in life this
1376   // zero-trip guard will become the minimum-trip guard when we unroll
1377   // the main-loop.
1378   Node *min_opaq = new Opaque1Node(C, limit);
1379   Node *min_cmp  = new CmpINode(pre_incr, min_opaq);
1380   Node *min_bol  = new BoolNode(min_cmp, b_test);
1381   register_new_node(min_opaq, new_pre_exit);
1382   register_new_node(min_cmp , new_pre_exit);
1383   register_new_node(min_bol , new_pre_exit);
1384 
1385   // Build the IfNode (assume the main-loop is executed always).
1386   IfNode *min_iff = new IfNode(new_pre_exit, min_bol, PROB_ALWAYS, COUNT_UNKNOWN);
1387   _igvn.register_new_node_with_optimizer(min_iff);
1388   set_idom(min_iff, new_pre_exit, dd_main_head);
1389   set_loop(min_iff, outer_loop->_parent);
1390 
1391   // Plug in the false-path, taken if we need to skip main-loop
1392   _igvn.hash_delete(pre_exit);
1393   pre_exit->set_req(0, min_iff);
1394   set_idom(pre_exit, min_iff, dd_main_head);
1395   set_idom(pre_exit->unique_ctrl_out(), min_iff, dd_main_head);
1396   // Make the true-path, must enter the main loop
1397   Node *min_taken = new IfTrueNode(min_iff);
1398   _igvn.register_new_node_with_optimizer(min_taken);
1399   set_idom(min_taken, min_iff, dd_main_head);
1400   set_loop(min_taken, outer_loop->_parent);
1401   // Plug in the true path
1402   _igvn.hash_delete(outer_main_head);
1403   outer_main_head->set_req(LoopNode::EntryControl, min_taken);
1404   set_idom(outer_main_head, min_taken, dd_main_head);
1405 
1406   Arena *a = Thread::current()->resource_area();
1407   VectorSet visited(a);
1408   Node_Stack clones(a, main_head->back_control()->outcnt());
1409   // Step B3: Make the fall-in values to the main-loop come from the
1410   // fall-out values of the pre-loop.
1411   for (DUIterator_Fast i2max, i2 = main_head->fast_outs(i2max); i2 < i2max; i2++) {
1412     Node* main_phi = main_head->fast_out(i2);
1413     if (main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0) {
1414       Node *pre_phi = old_new[main_phi->_idx];
1415       Node *fallpre  = clone_up_backedge_goo(pre_head->back_control(),
1416                                              main_head->skip_strip_mined()->in(LoopNode::EntryControl),
1417                                              pre_phi->in(LoopNode::LoopBackControl),
1418                                              visited, clones);
1419       _igvn.hash_delete(main_phi);
1420       main_phi->set_req(LoopNode::EntryControl, fallpre);
1421     }
1422   }
1423 
1424   // Nodes inside the loop may be control dependent on a predicate
1425   // that was moved before the preloop. If the back branch of the main
1426   // or post loops becomes dead, those nodes won't be dependent on the
1427   // test that guards that loop nest anymore which could lead to an
1428   // incorrect array access because it executes independently of the
1429   // test that was guarding the loop nest. We add a special CastII on
1430   // the if branch that enters the loop, between the input induction
1431   // variable value and the induction variable Phi to preserve correct
1432   // dependencies.
1433 
1434   // CastII for the main loop:
1435   Node* castii = cast_incr_before_loop(pre_incr, min_taken, main_head);
1436   assert(castii != NULL, "no castII inserted");
1437   Node* opaque_castii = new Opaque1Node(C, castii);
1438   register_new_node(opaque_castii, outer_main_head->in(LoopNode::EntryControl));
1439   duplicate_predicates(pre_head, castii, opaque_castii, outer_loop, outer_main_head, dd_main_head);
1440 
1441   // Step B4: Shorten the pre-loop to run only 1 iteration (for now).
1442   // RCE and alignment may change this later.
1443   Node *cmp_end = pre_end->cmp_node();
1444   assert(cmp_end->in(2) == limit, "");
1445   Node *pre_limit = new AddINode(init, stride);
1446 
1447   // Save the original loop limit in this Opaque1 node for
1448   // use by range check elimination.
1449   Node *pre_opaq  = new Opaque1Node(C, pre_limit, limit);
1450 
1451   register_new_node(pre_limit, pre_head->in(0));
1452   register_new_node(pre_opaq , pre_head->in(0));
1453 
1454   // Since no other users of pre-loop compare, I can hack limit directly
1455   assert(cmp_end->outcnt() == 1, "no other users");
1456   _igvn.hash_delete(cmp_end);
1457   cmp_end->set_req(2, peel_only ? pre_limit : pre_opaq);
1458 
1459   // Special case for not-equal loop bounds:
1460   // Change pre loop test, main loop test, and the
1461   // main loop guard test to use lt or gt depending on stride
1462   // direction:
1463   // positive stride use <
1464   // negative stride use >
1465   //
1466   // not-equal test is kept for post loop to handle case
1467   // when init > limit when stride > 0 (and reverse).
1468 
1469   if (pre_end->in(CountedLoopEndNode::TestValue)->as_Bool()->_test._test == BoolTest::ne) {
1470 
1471     BoolTest::mask new_test = (main_end->stride_con() > 0) ? BoolTest::lt : BoolTest::gt;
1472     // Modify pre loop end condition
1473     Node* pre_bol = pre_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1474     BoolNode* new_bol0 = new BoolNode(pre_bol->in(1), new_test);
1475     register_new_node(new_bol0, pre_head->in(0));
1476     _igvn.replace_input_of(pre_end, CountedLoopEndNode::TestValue, new_bol0);
1477     // Modify main loop guard condition
1478     assert(min_iff->in(CountedLoopEndNode::TestValue) == min_bol, "guard okay");
1479     BoolNode* new_bol1 = new BoolNode(min_bol->in(1), new_test);
1480     register_new_node(new_bol1, new_pre_exit);
1481     _igvn.hash_delete(min_iff);
1482     min_iff->set_req(CountedLoopEndNode::TestValue, new_bol1);
1483     // Modify main loop end condition
1484     BoolNode* main_bol = main_end->in(CountedLoopEndNode::TestValue)->as_Bool();
1485     BoolNode* new_bol2 = new BoolNode(main_bol->in(1), new_test);
1486     register_new_node(new_bol2, main_end->in(CountedLoopEndNode::TestControl));
1487     _igvn.replace_input_of(main_end, CountedLoopEndNode::TestValue, new_bol2);
1488   }
1489 
1490   // Flag main loop
1491   main_head->set_main_loop();
1492   if (peel_only) {
1493     main_head->set_main_no_pre_loop();
1494   }
1495 
1496   // Subtract a trip count for the pre-loop.
1497   main_head->set_trip_count(main_head->trip_count() - 1);
1498 
1499   // It's difficult to be precise about the trip-counts
1500   // for the pre/post loops.  They are usually very short,
1501   // so guess that 4 trips is a reasonable value.
1502   post_head->set_profile_trip_cnt(4.0);
1503   pre_head->set_profile_trip_cnt(4.0);
1504 
1505   // Now force out all loop-invariant dominating tests.  The optimizer
1506   // finds some, but we _know_ they are all useless.
1507   peeled_dom_test_elim(loop,old_new);
1508   loop->record_for_igvn();
1509 }
1510 
1511 //------------------------------insert_vector_post_loop------------------------
1512 // Insert a copy of the atomic unrolled vectorized main loop as a post loop,
1513 // unroll_policy has  already informed  us that more  unrolling is  about to
1514 // happen  to the  main  loop.  The  resultant  post loop  will  serve as  a
1515 // vectorized drain loop.
1516 void PhaseIdealLoop::insert_vector_post_loop(IdealLoopTree *loop, Node_List &old_new) {
1517   if (!loop->_head->is_CountedLoop()) return;
1518 
1519   CountedLoopNode *cl = loop->_head->as_CountedLoop();
1520 
1521   // only process vectorized main loops
1522   if (!cl->is_vectorized_loop() || !cl->is_main_loop()) return;
1523 
1524   if (!may_require_nodes(est_loop_clone_sz(2, loop->_body.size()))) {
1525     return;
1526   }
1527   int slp_max_unroll_factor = cl->slp_max_unroll();
1528   int cur_unroll = cl->unrolled_count();
1529 
1530   if (slp_max_unroll_factor == 0) return;
1531 
1532   // only process atomic unroll vector loops (not super unrolled after vectorization)
1533   if (cur_unroll != slp_max_unroll_factor) return;
1534 
1535   // we only ever process this one time
1536   if (cl->has_atomic_post_loop()) return;
1537 
1538 #ifndef PRODUCT
1539   if (TraceLoopOpts) {
1540     tty->print("PostVector  ");
1541     loop->dump_head();
1542   }
1543 #endif
1544   C->set_major_progress();
1545 
1546   // Find common pieces of the loop being guarded with pre & post loops
1547   CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1548   CountedLoopEndNode *main_end = main_head->loopexit();
1549   // diagnostic to show loop end is not properly formed
1550   assert(main_end->outcnt() == 2, "1 true, 1 false path only");
1551 
1552   // mark this loop as processed
1553   main_head->mark_has_atomic_post_loop();
1554 
1555   Node *incr = main_end->incr();
1556   Node *limit = main_end->limit();
1557 
1558   // In this case we throw away the result as we are not using it to connect anything else.
1559   CountedLoopNode *post_head = NULL;
1560   insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1561 
1562   // It's difficult to be precise about the trip-counts
1563   // for post loops.  They are usually very short,
1564   // so guess that unit vector trips is a reasonable value.
1565   post_head->set_profile_trip_cnt(cur_unroll);
1566 
1567   // Now force out all loop-invariant dominating tests.  The optimizer
1568   // finds some, but we _know_ they are all useless.
1569   peeled_dom_test_elim(loop, old_new);
1570   loop->record_for_igvn();
1571 }
1572 
1573 
1574 //-------------------------insert_scalar_rced_post_loop------------------------
1575 // Insert a copy of the rce'd main loop as a post loop,
1576 // We have not unrolled the main loop, so this is the right time to inject this.
1577 // Later we will examine the partner of this post loop pair which still has range checks
1578 // to see inject code which tests at runtime if the range checks are applicable.
1579 void PhaseIdealLoop::insert_scalar_rced_post_loop(IdealLoopTree *loop, Node_List &old_new) {
1580   if (!loop->_head->is_CountedLoop()) return;
1581 
1582   CountedLoopNode *cl = loop->_head->as_CountedLoop();
1583 
1584   // only process RCE'd main loops
1585   if (!cl->is_main_loop() || cl->range_checks_present()) return;
1586 
1587 #ifndef PRODUCT
1588   if (TraceLoopOpts) {
1589     tty->print("PostScalarRce  ");
1590     loop->dump_head();
1591   }
1592 #endif
1593   C->set_major_progress();
1594 
1595   // Find common pieces of the loop being guarded with pre & post loops
1596   CountedLoopNode *main_head = loop->_head->as_CountedLoop();
1597   CountedLoopEndNode *main_end = main_head->loopexit();
1598   // diagnostic to show loop end is not properly formed
1599   assert(main_end->outcnt() == 2, "1 true, 1 false path only");
1600 
1601   Node *incr = main_end->incr();
1602   Node *limit = main_end->limit();
1603 
1604   // In this case we throw away the result as we are not using it to connect anything else.
1605   CountedLoopNode *post_head = NULL;
1606   insert_post_loop(loop, old_new, main_head, main_end, incr, limit, post_head);
1607 
1608   // It's difficult to be precise about the trip-counts
1609   // for post loops.  They are usually very short,
1610   // so guess that unit vector trips is a reasonable value.
1611   post_head->set_profile_trip_cnt(4.0);
1612   post_head->set_is_rce_post_loop();
1613 
1614   // Now force out all loop-invariant dominating tests.  The optimizer
1615   // finds some, but we _know_ they are all useless.
1616   peeled_dom_test_elim(loop, old_new);
1617   loop->record_for_igvn();
1618 }
1619 
1620 
1621 //------------------------------insert_post_loop-------------------------------
1622 // Insert post loops.  Add a post loop to the given loop passed.
1623 Node *PhaseIdealLoop::insert_post_loop(IdealLoopTree *loop, Node_List &old_new,
1624                                        CountedLoopNode *main_head, CountedLoopEndNode *main_end,
1625                                        Node *incr, Node *limit, CountedLoopNode *&post_head) {
1626   IfNode* outer_main_end = main_end;
1627   IdealLoopTree* outer_loop = loop;
1628   if (main_head->is_strip_mined()) {
1629     main_head->verify_strip_mined(1);
1630     outer_main_end = main_head->outer_loop_end();
1631     outer_loop = loop->_parent;
1632     assert(outer_loop->_head == main_head->in(LoopNode::EntryControl), "broken loop tree");
1633   }
1634 
1635   //------------------------------
1636   // Step A: Create a new post-Loop.
1637   Node* main_exit = outer_main_end->proj_out(false);
1638   assert(main_exit->Opcode() == Op_IfFalse, "");
1639   int dd_main_exit = dom_depth(main_exit);
1640 
1641   // Step A1: Clone the loop body of main. The clone becomes the post-loop.
1642   // The main loop pre-header illegally has 2 control users (old & new loops).
1643   clone_loop(loop, old_new, dd_main_exit, ControlAroundStripMined);
1644   assert(old_new[main_end->_idx]->Opcode() == Op_CountedLoopEnd, "");
1645   post_head = old_new[main_head->_idx]->as_CountedLoop();
1646   post_head->set_normal_loop();
1647   post_head->set_post_loop(main_head);
1648 
1649   // Reduce the post-loop trip count.
1650   CountedLoopEndNode* post_end = old_new[main_end->_idx]->as_CountedLoopEnd();
1651   post_end->_prob = PROB_FAIR;
1652 
1653   // Build the main-loop normal exit.
1654   IfFalseNode *new_main_exit = new IfFalseNode(outer_main_end);
1655   _igvn.register_new_node_with_optimizer(new_main_exit);
1656   set_idom(new_main_exit, outer_main_end, dd_main_exit);
1657   set_loop(new_main_exit, outer_loop->_parent);
1658 
1659   // Step A2: Build a zero-trip guard for the post-loop.  After leaving the
1660   // main-loop, the post-loop may not execute at all.  We 'opaque' the incr
1661   // (the previous loop trip-counter exit value) because we will be changing
1662   // the exit value (via additional unrolling) so we cannot constant-fold away the zero
1663   // trip guard until all unrolling is done.
1664   Node *zer_opaq = new Opaque1Node(C, incr);
1665   Node *zer_cmp = new CmpINode(zer_opaq, limit);
1666   Node *zer_bol = new BoolNode(zer_cmp, main_end->test_trip());
1667   register_new_node(zer_opaq, new_main_exit);
1668   register_new_node(zer_cmp, new_main_exit);
1669   register_new_node(zer_bol, new_main_exit);
1670 
1671   // Build the IfNode
1672   IfNode *zer_iff = new IfNode(new_main_exit, zer_bol, PROB_FAIR, COUNT_UNKNOWN);
1673   _igvn.register_new_node_with_optimizer(zer_iff);
1674   set_idom(zer_iff, new_main_exit, dd_main_exit);
1675   set_loop(zer_iff, outer_loop->_parent);
1676 
1677   // Plug in the false-path, taken if we need to skip this post-loop
1678   _igvn.replace_input_of(main_exit, 0, zer_iff);
1679   set_idom(main_exit, zer_iff, dd_main_exit);
1680   set_idom(main_exit->unique_out(), zer_iff, dd_main_exit);
1681   // Make the true-path, must enter this post loop
1682   Node *zer_taken = new IfTrueNode(zer_iff);
1683   _igvn.register_new_node_with_optimizer(zer_taken);
1684   set_idom(zer_taken, zer_iff, dd_main_exit);
1685   set_loop(zer_taken, outer_loop->_parent);
1686   // Plug in the true path
1687   _igvn.hash_delete(post_head);
1688   post_head->set_req(LoopNode::EntryControl, zer_taken);
1689   set_idom(post_head, zer_taken, dd_main_exit);
1690 
1691   Arena *a = Thread::current()->resource_area();
1692   VectorSet visited(a);
1693   Node_Stack clones(a, main_head->back_control()->outcnt());
1694   // Step A3: Make the fall-in values to the post-loop come from the
1695   // fall-out values of the main-loop.
1696   for (DUIterator_Fast imax, i = main_head->fast_outs(imax); i < imax; i++) {
1697     Node* main_phi = main_head->fast_out(i);
1698     if (main_phi->is_Phi() && main_phi->in(0) == main_head && main_phi->outcnt() > 0) {
1699       Node *cur_phi = old_new[main_phi->_idx];
1700       Node *fallnew = clone_up_backedge_goo(main_head->back_control(),
1701                                             post_head->init_control(),
1702                                             main_phi->in(LoopNode::LoopBackControl),
1703                                             visited, clones);
1704       _igvn.hash_delete(cur_phi);
1705       cur_phi->set_req(LoopNode::EntryControl, fallnew);
1706     }
1707   }
1708 
1709   // CastII for the new post loop:
1710   Node* castii = cast_incr_before_loop(zer_opaq->in(1), zer_taken, post_head);
1711   assert(castii != NULL, "no castII inserted");
1712 
1713   return new_main_exit;
1714 }
1715 
1716 //------------------------------is_invariant-----------------------------
1717 // Return true if n is invariant
1718 bool IdealLoopTree::is_invariant(Node* n) const {
1719   Node *n_c = _phase->has_ctrl(n) ? _phase->get_ctrl(n) : n;
1720   if (n_c->is_top()) return false;
1721   return !is_member(_phase->get_loop(n_c));
1722 }
1723 
1724 void PhaseIdealLoop::update_skeleton_predicates(Node* ctrl, CountedLoopNode* loop_head, Node* init, int stride_con) {
1725   // Search for skeleton predicates and update them according to the new stride
1726   Node* entry = ctrl;
1727   Node* prev_proj = ctrl;
1728   LoopNode* outer_loop_head = loop_head->skip_strip_mined();
1729   IdealLoopTree* outer_loop = get_loop(outer_loop_head);
1730   while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) {
1731     IfNode* iff = entry->in(0)->as_If();
1732     ProjNode* proj = iff->proj_out(1 - entry->as_Proj()->_con);
1733     if (proj->unique_ctrl_out()->Opcode() != Op_Halt) {
1734       break;
1735     }
1736     if (iff->in(1)->Opcode() == Op_Opaque4) {
1737       // Look for predicate with an Opaque1 node that can be used as a template
1738       if (!skeleton_predicate_has_opaque(iff)) {
1739         // No Opaque1 node? It's either the check for the first value
1740         // of the first iteration or the check for the last value of
1741         // the first iteration of an unrolled loop. We can't
1742         // tell. Kill it in any case.
1743         _igvn.replace_input_of(iff, 1, iff->in(1)->in(2));
1744       } else {
1745         // Add back the predicate for the value at the beginning of the first entry
1746         prev_proj = clone_skeleton_predicate(iff, init, entry, proj, ctrl, outer_loop, prev_proj);
1747         assert(!skeleton_predicate_has_opaque(prev_proj->in(0)->as_If()), "unexpected");
1748         // Compute the value of the loop induction variable at the end of the
1749         // first iteration of the unrolled loop: init + new_stride_con - init_inc
1750         int init_inc = stride_con/loop_head->unrolled_count();
1751         assert(init_inc != 0, "invalid loop increment");
1752         int new_stride_con = stride_con * 2;
1753         Node* max_value = _igvn.intcon(new_stride_con - init_inc);
1754         max_value = new AddINode(init, max_value);
1755         register_new_node(max_value, get_ctrl(iff->in(1)));
1756         prev_proj = clone_skeleton_predicate(iff, max_value, entry, proj, ctrl, outer_loop, prev_proj);
1757         assert(!skeleton_predicate_has_opaque(prev_proj->in(0)->as_If()), "unexpected");
1758       }
1759     }
1760     entry = entry->in(0)->in(0);
1761   }
1762   if (prev_proj != ctrl) {
1763     _igvn.replace_input_of(outer_loop_head, LoopNode::EntryControl, prev_proj);
1764     set_idom(outer_loop_head, prev_proj, dom_depth(outer_loop_head));
1765   }
1766 }
1767 
1768 //------------------------------do_unroll--------------------------------------
1769 // Unroll the loop body one step - make each trip do 2 iterations.
1770 void PhaseIdealLoop::do_unroll(IdealLoopTree *loop, Node_List &old_new, bool adjust_min_trip) {
1771   assert(LoopUnrollLimit, "");
1772   CountedLoopNode *loop_head = loop->_head->as_CountedLoop();
1773   CountedLoopEndNode *loop_end = loop_head->loopexit();
1774 #ifndef PRODUCT
1775   if (PrintOpto && VerifyLoopOptimizations) {
1776     tty->print("Unrolling ");
1777     loop->dump_head();
1778   } else if (TraceLoopOpts) {
1779     if (loop_head->trip_count() < (uint)LoopUnrollLimit) {
1780       tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count());
1781     } else {
1782       tty->print("Unroll %d     ", loop_head->unrolled_count()*2);
1783     }
1784     loop->dump_head();
1785   }
1786 
1787   if (C->do_vector_loop() && (PrintOpto && (VerifyLoopOptimizations || TraceLoopOpts))) {
1788     Arena* arena = Thread::current()->resource_area();
1789     Node_Stack stack(arena, C->live_nodes() >> 2);
1790     Node_List rpo_list;
1791     VectorSet visited(arena);
1792     visited.set(loop_head->_idx);
1793     rpo(loop_head, stack, visited, rpo_list);
1794     dump(loop, rpo_list.size(), rpo_list);
1795   }
1796 #endif
1797 
1798   // Remember loop node count before unrolling to detect
1799   // if rounds of unroll,optimize are making progress
1800   loop_head->set_node_count_before_unroll(loop->_body.size());
1801 
1802   Node *ctrl  = loop_head->skip_strip_mined()->in(LoopNode::EntryControl);
1803   Node *limit = loop_head->limit();
1804   Node *init  = loop_head->init_trip();
1805   Node *stride = loop_head->stride();
1806 
1807   Node *opaq = NULL;
1808   if (adjust_min_trip) {       // If not maximally unrolling, need adjustment
1809     // Search for zero-trip guard.
1810 
1811     // Check the shape of the graph at the loop entry. If an inappropriate
1812     // graph shape is encountered, the compiler bails out loop unrolling;
1813     // compilation of the method will still succeed.
1814     if (!is_canonical_loop_entry(loop_head)) {
1815       return;
1816     }
1817     opaq = loop_head->skip_predicates()->in(0)->in(1)->in(1)->in(2);
1818     // Zero-trip test uses an 'opaque' node which is not shared.
1819     assert(opaq->outcnt() == 1 && opaq->in(1) == limit, "");
1820   }
1821 
1822   C->set_major_progress();
1823 
1824   Node* new_limit = NULL;
1825   int stride_con = stride->get_int();
1826   int stride_p = (stride_con > 0) ? stride_con : -stride_con;
1827   uint old_trip_count = loop_head->trip_count();
1828   // Verify that unroll policy result is still valid.
1829   assert(old_trip_count > 1 &&
1830       (!adjust_min_trip || stride_p <= (1<<3)*loop_head->unrolled_count()), "sanity");
1831 
1832   update_skeleton_predicates(ctrl, loop_head, init, stride_con);
1833 
1834   // Adjust loop limit to keep valid iterations number after unroll.
1835   // Use (limit - stride) instead of (((limit - init)/stride) & (-2))*stride
1836   // which may overflow.
1837   if (!adjust_min_trip) {
1838     assert(old_trip_count > 1 && (old_trip_count & 1) == 0,
1839         "odd trip count for maximally unroll");
1840     // Don't need to adjust limit for maximally unroll since trip count is even.
1841   } else if (loop_head->has_exact_trip_count() && init->is_Con()) {
1842     // Loop's limit is constant. Loop's init could be constant when pre-loop
1843     // become peeled iteration.
1844     jlong init_con = init->get_int();
1845     // We can keep old loop limit if iterations count stays the same:
1846     //   old_trip_count == new_trip_count * 2
1847     // Note: since old_trip_count >= 2 then new_trip_count >= 1
1848     // so we also don't need to adjust zero trip test.
1849     jlong limit_con  = limit->get_int();
1850     // (stride_con*2) not overflow since stride_con <= 8.
1851     int new_stride_con = stride_con * 2;
1852     int stride_m    = new_stride_con - (stride_con > 0 ? 1 : -1);
1853     jlong trip_count = (limit_con - init_con + stride_m)/new_stride_con;
1854     // New trip count should satisfy next conditions.
1855     assert(trip_count > 0 && (julong)trip_count < (julong)max_juint/2, "sanity");
1856     uint new_trip_count = (uint)trip_count;
1857     adjust_min_trip = (old_trip_count != new_trip_count*2);
1858   }
1859 
1860   if (adjust_min_trip) {
1861     // Step 2: Adjust the trip limit if it is called for.
1862     // The adjustment amount is -stride. Need to make sure if the
1863     // adjustment underflows or overflows, then the main loop is skipped.
1864     Node* cmp = loop_end->cmp_node();
1865     assert(cmp->in(2) == limit, "sanity");
1866     assert(opaq != NULL && opaq->in(1) == limit, "sanity");
1867 
1868     // Verify that policy_unroll result is still valid.
1869     const TypeInt* limit_type = _igvn.type(limit)->is_int();
1870     assert(stride_con > 0 && ((limit_type->_hi - stride_con) < limit_type->_hi) ||
1871            stride_con < 0 && ((limit_type->_lo - stride_con) > limit_type->_lo),
1872            "sanity");
1873 
1874     if (limit->is_Con()) {
1875       // The check in policy_unroll and the assert above guarantee
1876       // no underflow if limit is constant.
1877       new_limit = _igvn.intcon(limit->get_int() - stride_con);
1878       set_ctrl(new_limit, C->root());
1879     } else {
1880       // Limit is not constant.
1881       if (loop_head->unrolled_count() == 1) { // only for first unroll
1882         // Separate limit by Opaque node in case it is an incremented
1883         // variable from previous loop to avoid using pre-incremented
1884         // value which could increase register pressure.
1885         // Otherwise reorg_offsets() optimization will create a separate
1886         // Opaque node for each use of trip-counter and as result
1887         // zero trip guard limit will be different from loop limit.
1888         assert(has_ctrl(opaq), "should have it");
1889         Node* opaq_ctrl = get_ctrl(opaq);
1890         limit = new Opaque2Node(C, limit);
1891         register_new_node(limit, opaq_ctrl);
1892       }
1893       if ((stride_con > 0 && (java_subtract(limit_type->_lo, stride_con) < limit_type->_lo)) ||
1894           (stride_con < 0 && (java_subtract(limit_type->_hi, stride_con) > limit_type->_hi))) {
1895         // No underflow.
1896         new_limit = new SubINode(limit, stride);
1897       } else {
1898         // (limit - stride) may underflow.
1899         // Clamp the adjustment value with MININT or MAXINT:
1900         //
1901         //   new_limit = limit-stride
1902         //   if (stride > 0)
1903         //     new_limit = (limit < new_limit) ? MININT : new_limit;
1904         //   else
1905         //     new_limit = (limit > new_limit) ? MAXINT : new_limit;
1906         //
1907         BoolTest::mask bt = loop_end->test_trip();
1908         assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
1909         Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint);
1910         set_ctrl(adj_max, C->root());
1911         Node* old_limit = NULL;
1912         Node* adj_limit = NULL;
1913         Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL;
1914         if (loop_head->unrolled_count() > 1 &&
1915             limit->is_CMove() && limit->Opcode() == Op_CMoveI &&
1916             limit->in(CMoveNode::IfTrue) == adj_max &&
1917             bol->as_Bool()->_test._test == bt &&
1918             bol->in(1)->Opcode() == Op_CmpI &&
1919             bol->in(1)->in(2) == limit->in(CMoveNode::IfFalse)) {
1920           // Loop was unrolled before.
1921           // Optimize the limit to avoid nested CMove:
1922           // use original limit as old limit.
1923           old_limit = bol->in(1)->in(1);
1924           // Adjust previous adjusted limit.
1925           adj_limit = limit->in(CMoveNode::IfFalse);
1926           adj_limit = new SubINode(adj_limit, stride);
1927         } else {
1928           old_limit = limit;
1929           adj_limit = new SubINode(limit, stride);
1930         }
1931         assert(old_limit != NULL && adj_limit != NULL, "");
1932         register_new_node(adj_limit, ctrl); // adjust amount
1933         Node* adj_cmp = new CmpINode(old_limit, adj_limit);
1934         register_new_node(adj_cmp, ctrl);
1935         Node* adj_bool = new BoolNode(adj_cmp, bt);
1936         register_new_node(adj_bool, ctrl);
1937         new_limit = new CMoveINode(adj_bool, adj_limit, adj_max, TypeInt::INT);
1938       }
1939       register_new_node(new_limit, ctrl);
1940     }
1941 
1942     assert(new_limit != NULL, "");
1943     // Replace in loop test.
1944     assert(loop_end->in(1)->in(1) == cmp, "sanity");
1945     if (cmp->outcnt() == 1 && loop_end->in(1)->outcnt() == 1) {
1946       // Don't need to create new test since only one user.
1947       _igvn.hash_delete(cmp);
1948       cmp->set_req(2, new_limit);
1949     } else {
1950       // Create new test since it is shared.
1951       Node* ctrl2 = loop_end->in(0);
1952       Node* cmp2  = cmp->clone();
1953       cmp2->set_req(2, new_limit);
1954       register_new_node(cmp2, ctrl2);
1955       Node* bol2 = loop_end->in(1)->clone();
1956       bol2->set_req(1, cmp2);
1957       register_new_node(bol2, ctrl2);
1958       _igvn.replace_input_of(loop_end, 1, bol2);
1959     }
1960     // Step 3: Find the min-trip test guaranteed before a 'main' loop.
1961     // Make it a 1-trip test (means at least 2 trips).
1962 
1963     // Guard test uses an 'opaque' node which is not shared.  Hence I
1964     // can edit it's inputs directly.  Hammer in the new limit for the
1965     // minimum-trip guard.
1966     assert(opaq->outcnt() == 1, "");
1967     _igvn.replace_input_of(opaq, 1, new_limit);
1968   }
1969 
1970   // Adjust max trip count. The trip count is intentionally rounded
1971   // down here (e.g. 15-> 7-> 3-> 1) because if we unwittingly over-unroll,
1972   // the main, unrolled, part of the loop will never execute as it is protected
1973   // by the min-trip test.  See bug 4834191 for a case where we over-unrolled
1974   // and later determined that part of the unrolled loop was dead.
1975   loop_head->set_trip_count(old_trip_count / 2);
1976 
1977   // Double the count of original iterations in the unrolled loop body.
1978   loop_head->double_unrolled_count();
1979 
1980   // ---------
1981   // Step 4: Clone the loop body.  Move it inside the loop.  This loop body
1982   // represents the odd iterations; since the loop trips an even number of
1983   // times its backedge is never taken.  Kill the backedge.
1984   uint dd = dom_depth(loop_head);
1985   clone_loop(loop, old_new, dd, IgnoreStripMined);
1986 
1987   // Make backedges of the clone equal to backedges of the original.
1988   // Make the fall-in from the original come from the fall-out of the clone.
1989   for (DUIterator_Fast jmax, j = loop_head->fast_outs(jmax); j < jmax; j++) {
1990     Node* phi = loop_head->fast_out(j);
1991     if (phi->is_Phi() && phi->in(0) == loop_head && phi->outcnt() > 0) {
1992       Node *newphi = old_new[phi->_idx];
1993       _igvn.hash_delete(phi);
1994       _igvn.hash_delete(newphi);
1995 
1996       phi   ->set_req(LoopNode::   EntryControl, newphi->in(LoopNode::LoopBackControl));
1997       newphi->set_req(LoopNode::LoopBackControl, phi   ->in(LoopNode::LoopBackControl));
1998       phi   ->set_req(LoopNode::LoopBackControl, C->top());
1999     }
2000   }
2001   Node *clone_head = old_new[loop_head->_idx];
2002   _igvn.hash_delete(clone_head);
2003   loop_head ->set_req(LoopNode::   EntryControl, clone_head->in(LoopNode::LoopBackControl));
2004   clone_head->set_req(LoopNode::LoopBackControl, loop_head ->in(LoopNode::LoopBackControl));
2005   loop_head ->set_req(LoopNode::LoopBackControl, C->top());
2006   loop->_head = clone_head;     // New loop header
2007 
2008   set_idom(loop_head,  loop_head ->in(LoopNode::EntryControl), dd);
2009   set_idom(clone_head, clone_head->in(LoopNode::EntryControl), dd);
2010 
2011   // Kill the clone's backedge
2012   Node *newcle = old_new[loop_end->_idx];
2013   _igvn.hash_delete(newcle);
2014   Node *one = _igvn.intcon(1);
2015   set_ctrl(one, C->root());
2016   newcle->set_req(1, one);
2017   // Force clone into same loop body
2018   uint max = loop->_body.size();
2019   for (uint k = 0; k < max; k++) {
2020     Node *old = loop->_body.at(k);
2021     Node *nnn = old_new[old->_idx];
2022     loop->_body.push(nnn);
2023     if (!has_ctrl(old)) {
2024       set_loop(nnn, loop);
2025     }
2026   }
2027 
2028   loop->record_for_igvn();
2029   loop_head->clear_strip_mined();
2030 
2031 #ifndef PRODUCT
2032   if (C->do_vector_loop() && (PrintOpto && (VerifyLoopOptimizations || TraceLoopOpts))) {
2033     tty->print("\nnew loop after unroll\n");       loop->dump_head();
2034     for (uint i = 0; i < loop->_body.size(); i++) {
2035       loop->_body.at(i)->dump();
2036     }
2037     if (C->clone_map().is_debug()) {
2038       tty->print("\nCloneMap\n");
2039       Dict* dict = C->clone_map().dict();
2040       DictI i(dict);
2041       tty->print_cr("Dict@%p[%d] = ", dict, dict->Size());
2042       for (int ii = 0; i.test(); ++i, ++ii) {
2043         NodeCloneInfo cl((uint64_t)dict->operator[]((void*)i._key));
2044         tty->print("%d->%d:%d,", (int)(intptr_t)i._key, cl.idx(), cl.gen());
2045         if (ii % 10 == 9) {
2046           tty->print_cr(" ");
2047         }
2048       }
2049       tty->print_cr(" ");
2050     }
2051   }
2052 #endif
2053 }
2054 
2055 //------------------------------do_maximally_unroll----------------------------
2056 
2057 void PhaseIdealLoop::do_maximally_unroll(IdealLoopTree *loop, Node_List &old_new) {
2058   CountedLoopNode *cl = loop->_head->as_CountedLoop();
2059   assert(cl->has_exact_trip_count(), "trip count is not exact");
2060   assert(cl->trip_count() > 0, "");
2061 #ifndef PRODUCT
2062   if (TraceLoopOpts) {
2063     tty->print("MaxUnroll  %d ", cl->trip_count());
2064     loop->dump_head();
2065   }
2066 #endif
2067 
2068   // If loop is tripping an odd number of times, peel odd iteration
2069   if ((cl->trip_count() & 1) == 1) {
2070     do_peeling(loop, old_new);
2071   }
2072 
2073   // Now its tripping an even number of times remaining.  Double loop body.
2074   // Do not adjust pre-guards; they are not needed and do not exist.
2075   if (cl->trip_count() > 0) {
2076     assert((cl->trip_count() & 1) == 0, "missed peeling");
2077     do_unroll(loop, old_new, false);
2078   }
2079 }
2080 
2081 void PhaseIdealLoop::mark_reductions(IdealLoopTree *loop) {
2082   if (SuperWordReductions == false) return;
2083 
2084   CountedLoopNode* loop_head = loop->_head->as_CountedLoop();
2085   if (loop_head->unrolled_count() > 1) {
2086     return;
2087   }
2088 
2089   Node* trip_phi = loop_head->phi();
2090   for (DUIterator_Fast imax, i = loop_head->fast_outs(imax); i < imax; i++) {
2091     Node* phi = loop_head->fast_out(i);
2092     if (phi->is_Phi() && phi->outcnt() > 0 && phi != trip_phi) {
2093       // For definitions which are loop inclusive and not tripcounts.
2094       Node* def_node = phi->in(LoopNode::LoopBackControl);
2095 
2096       if (def_node != NULL) {
2097         Node* n_ctrl = get_ctrl(def_node);
2098         if (n_ctrl != NULL && loop->is_member(get_loop(n_ctrl))) {
2099           // Now test it to see if it fits the standard pattern for a reduction operator.
2100           int opc = def_node->Opcode();
2101           if (opc != ReductionNode::opcode(opc, def_node->bottom_type()->basic_type())
2102               || opc == Op_MinD || opc == Op_MinF || opc == Op_MaxD || opc == Op_MaxF) {
2103             if (!def_node->is_reduction()) { // Not marked yet
2104               // To be a reduction, the arithmetic node must have the phi as input and provide a def to it
2105               bool ok = false;
2106               for (unsigned j = 1; j < def_node->req(); j++) {
2107                 Node* in = def_node->in(j);
2108                 if (in == phi) {
2109                   ok = true;
2110                   break;
2111                 }
2112               }
2113 
2114               // do nothing if we did not match the initial criteria
2115               if (ok == false) {
2116                 continue;
2117               }
2118 
2119               // The result of the reduction must not be used in the loop
2120               for (DUIterator_Fast imax, i = def_node->fast_outs(imax); i < imax && ok; i++) {
2121                 Node* u = def_node->fast_out(i);
2122                 if (!loop->is_member(get_loop(ctrl_or_self(u)))) {
2123                   continue;
2124                 }
2125                 if (u == phi) {
2126                   continue;
2127                 }
2128                 ok = false;
2129               }
2130 
2131               // iff the uses conform
2132               if (ok) {
2133                 def_node->add_flag(Node::Flag_is_reduction);
2134                 loop_head->mark_has_reductions();
2135               }
2136             }
2137           }
2138         }
2139       }
2140     }
2141   }
2142 }
2143 
2144 //------------------------------adjust_limit-----------------------------------
2145 // Helper function for add_constraint().
2146 Node* PhaseIdealLoop::adjust_limit(int stride_con, Node * scale, Node *offset, Node *rc_limit, Node *loop_limit, Node *pre_ctrl, bool round_up) {
2147   // Compute "I :: (limit-offset)/scale"
2148   Node *con = new SubINode(rc_limit, offset);
2149   register_new_node(con, pre_ctrl);
2150   Node *X = new DivINode(0, con, scale);
2151   register_new_node(X, pre_ctrl);
2152 
2153   // When the absolute value of scale is greater than one, the integer
2154   // division may round limit down so add one to the limit.
2155   if (round_up) {
2156     X = new AddINode(X, _igvn.intcon(1));
2157     register_new_node(X, pre_ctrl);
2158   }
2159 
2160   // Adjust loop limit
2161   loop_limit = (stride_con > 0)
2162                ? (Node*)(new MinINode(loop_limit, X))
2163                : (Node*)(new MaxINode(loop_limit, X));
2164   register_new_node(loop_limit, pre_ctrl);
2165   return loop_limit;
2166 }
2167 
2168 //------------------------------add_constraint---------------------------------
2169 // Constrain the main loop iterations so the conditions:
2170 //    low_limit <= scale_con * I + offset  <  upper_limit
2171 // always holds true.  That is, either increase the number of iterations in
2172 // the pre-loop or the post-loop until the condition holds true in the main
2173 // loop.  Stride, scale, offset and limit are all loop invariant.  Further,
2174 // stride and scale are constants (offset and limit often are).
2175 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) {
2176   // For positive stride, the pre-loop limit always uses a MAX function
2177   // and the main loop a MIN function.  For negative stride these are
2178   // reversed.
2179 
2180   // Also for positive stride*scale the affine function is increasing, so the
2181   // pre-loop must check for underflow and the post-loop for overflow.
2182   // Negative stride*scale reverses this; pre-loop checks for overflow and
2183   // post-loop for underflow.
2184 
2185   Node *scale = _igvn.intcon(scale_con);
2186   set_ctrl(scale, C->root());
2187 
2188   if ((stride_con^scale_con) >= 0) { // Use XOR to avoid overflow
2189     // The overflow limit: scale*I+offset < upper_limit
2190     // For main-loop compute
2191     //   ( if (scale > 0) /* and stride > 0 */
2192     //       I < (upper_limit-offset)/scale
2193     //     else /* scale < 0 and stride < 0 */
2194     //       I > (upper_limit-offset)/scale
2195     //   )
2196     //
2197     // (upper_limit-offset) may overflow or underflow.
2198     // But it is fine since main loop will either have
2199     // less iterations or will be skipped in such case.
2200     *main_limit = adjust_limit(stride_con, scale, offset, upper_limit, *main_limit, pre_ctrl, false);
2201 
2202     // The underflow limit: low_limit <= scale*I+offset.
2203     // For pre-loop compute
2204     //   NOT(scale*I+offset >= low_limit)
2205     //   scale*I+offset < low_limit
2206     //   ( if (scale > 0) /* and stride > 0 */
2207     //       I < (low_limit-offset)/scale
2208     //     else /* scale < 0 and stride < 0 */
2209     //       I > (low_limit-offset)/scale
2210     //   )
2211 
2212     if (low_limit->get_int() == -max_jint) {
2213       // We need this guard when scale*pre_limit+offset >= limit
2214       // due to underflow. So we need execute pre-loop until
2215       // scale*I+offset >= min_int. But (min_int-offset) will
2216       // underflow when offset > 0 and X will be > original_limit
2217       // when stride > 0. To avoid it we replace positive offset with 0.
2218       //
2219       // Also (min_int+1 == -max_int) is used instead of min_int here
2220       // to avoid problem with scale == -1 (min_int/(-1) == min_int).
2221       Node* shift = _igvn.intcon(31);
2222       set_ctrl(shift, C->root());
2223       Node* sign = new RShiftINode(offset, shift);
2224       register_new_node(sign, pre_ctrl);
2225       offset = new AndINode(offset, sign);
2226       register_new_node(offset, pre_ctrl);
2227     } else {
2228       assert(low_limit->get_int() == 0, "wrong low limit for range check");
2229       // The only problem we have here when offset == min_int
2230       // since (0-min_int) == min_int. It may be fine for stride > 0
2231       // but for stride < 0 X will be < original_limit. To avoid it
2232       // max(pre_limit, original_limit) is used in do_range_check().
2233     }
2234     // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
2235     *pre_limit = adjust_limit((-stride_con), scale, offset, low_limit, *pre_limit, pre_ctrl,
2236                               scale_con > 1 && stride_con > 0);
2237 
2238   } else { // stride_con*scale_con < 0
2239     // For negative stride*scale pre-loop checks for overflow and
2240     // post-loop for underflow.
2241     //
2242     // The overflow limit: scale*I+offset < upper_limit
2243     // For pre-loop compute
2244     //   NOT(scale*I+offset < upper_limit)
2245     //   scale*I+offset >= upper_limit
2246     //   scale*I+offset+1 > upper_limit
2247     //   ( if (scale < 0) /* and stride > 0 */
2248     //       I < (upper_limit-(offset+1))/scale
2249     //     else /* scale > 0 and stride < 0 */
2250     //       I > (upper_limit-(offset+1))/scale
2251     //   )
2252     //
2253     // (upper_limit-offset-1) may underflow or overflow.
2254     // To avoid it min(pre_limit, original_limit) is used
2255     // in do_range_check() for stride > 0 and max() for < 0.
2256     Node *one  = _igvn.intcon(1);
2257     set_ctrl(one, C->root());
2258 
2259     Node *plus_one = new AddINode(offset, one);
2260     register_new_node(plus_one, pre_ctrl);
2261     // Pass (-stride) to indicate pre_loop_cond = NOT(main_loop_cond);
2262     *pre_limit = adjust_limit((-stride_con), scale, plus_one, upper_limit, *pre_limit, pre_ctrl,
2263                               scale_con < -1 && stride_con > 0);
2264 
2265     if (low_limit->get_int() == -max_jint) {
2266       // We need this guard when scale*main_limit+offset >= limit
2267       // due to underflow. So we need execute main-loop while
2268       // scale*I+offset+1 > min_int. But (min_int-offset-1) will
2269       // underflow when (offset+1) > 0 and X will be < main_limit
2270       // when scale < 0 (and stride > 0). To avoid it we replace
2271       // positive (offset+1) with 0.
2272       //
2273       // Also (min_int+1 == -max_int) is used instead of min_int here
2274       // to avoid problem with scale == -1 (min_int/(-1) == min_int).
2275       Node* shift = _igvn.intcon(31);
2276       set_ctrl(shift, C->root());
2277       Node* sign = new RShiftINode(plus_one, shift);
2278       register_new_node(sign, pre_ctrl);
2279       plus_one = new AndINode(plus_one, sign);
2280       register_new_node(plus_one, pre_ctrl);
2281     } else {
2282       assert(low_limit->get_int() == 0, "wrong low limit for range check");
2283       // The only problem we have here when offset == max_int
2284       // since (max_int+1) == min_int and (0-min_int) == min_int.
2285       // But it is fine since main loop will either have
2286       // less iterations or will be skipped in such case.
2287     }
2288     // The underflow limit: low_limit <= scale*I+offset.
2289     // For main-loop compute
2290     //   scale*I+offset+1 > low_limit
2291     //   ( if (scale < 0) /* and stride > 0 */
2292     //       I < (low_limit-(offset+1))/scale
2293     //     else /* scale > 0 and stride < 0 */
2294     //       I > (low_limit-(offset+1))/scale
2295     //   )
2296 
2297     *main_limit = adjust_limit(stride_con, scale, plus_one, low_limit, *main_limit, pre_ctrl,
2298                                false);
2299   }
2300 }
2301 
2302 
2303 //------------------------------is_scaled_iv---------------------------------
2304 // Return true if exp is a constant times an induction var
2305 bool PhaseIdealLoop::is_scaled_iv(Node* exp, Node* iv, int* p_scale) {
2306   if (exp == iv) {
2307     if (p_scale != NULL) {
2308       *p_scale = 1;
2309     }
2310     return true;
2311   }
2312   int opc = exp->Opcode();
2313   if (opc == Op_MulI) {
2314     if (exp->in(1) == iv && exp->in(2)->is_Con()) {
2315       if (p_scale != NULL) {
2316         *p_scale = exp->in(2)->get_int();
2317       }
2318       return true;
2319     }
2320     if (exp->in(2) == iv && exp->in(1)->is_Con()) {
2321       if (p_scale != NULL) {
2322         *p_scale = exp->in(1)->get_int();
2323       }
2324       return true;
2325     }
2326   } else if (opc == Op_LShiftI) {
2327     if (exp->in(1) == iv && exp->in(2)->is_Con()) {
2328       if (p_scale != NULL) {
2329         *p_scale = 1 << exp->in(2)->get_int();
2330       }
2331       return true;
2332     }
2333   }
2334   return false;
2335 }
2336 
2337 //-----------------------------is_scaled_iv_plus_offset------------------------------
2338 // Return true if exp is a simple induction variable expression: k1*iv + (invar + k2)
2339 bool PhaseIdealLoop::is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth) {
2340   if (is_scaled_iv(exp, iv, p_scale)) {
2341     if (p_offset != NULL) {
2342       Node *zero = _igvn.intcon(0);
2343       set_ctrl(zero, C->root());
2344       *p_offset = zero;
2345     }
2346     return true;
2347   }
2348   int opc = exp->Opcode();
2349   if (opc == Op_AddI) {
2350     if (is_scaled_iv(exp->in(1), iv, p_scale)) {
2351       if (p_offset != NULL) {
2352         *p_offset = exp->in(2);
2353       }
2354       return true;
2355     }
2356     if (is_scaled_iv(exp->in(2), iv, p_scale)) {
2357       if (p_offset != NULL) {
2358         *p_offset = exp->in(1);
2359       }
2360       return true;
2361     }
2362     if (exp->in(2)->is_Con()) {
2363       Node* offset2 = NULL;
2364       if (depth < 2 &&
2365           is_scaled_iv_plus_offset(exp->in(1), iv, p_scale,
2366                                    p_offset != NULL ? &offset2 : NULL, depth+1)) {
2367         if (p_offset != NULL) {
2368           Node *ctrl_off2 = get_ctrl(offset2);
2369           Node* offset = new AddINode(offset2, exp->in(2));
2370           register_new_node(offset, ctrl_off2);
2371           *p_offset = offset;
2372         }
2373         return true;
2374       }
2375     }
2376   } else if (opc == Op_SubI) {
2377     if (is_scaled_iv(exp->in(1), iv, p_scale)) {
2378       if (p_offset != NULL) {
2379         Node *zero = _igvn.intcon(0);
2380         set_ctrl(zero, C->root());
2381         Node *ctrl_off = get_ctrl(exp->in(2));
2382         Node* offset = new SubINode(zero, exp->in(2));
2383         register_new_node(offset, ctrl_off);
2384         *p_offset = offset;
2385       }
2386       return true;
2387     }
2388     if (is_scaled_iv(exp->in(2), iv, p_scale)) {
2389       if (p_offset != NULL) {
2390         *p_scale *= -1;
2391         *p_offset = exp->in(1);
2392       }
2393       return true;
2394     }
2395   }
2396   return false;
2397 }
2398 
2399 // Same as PhaseIdealLoop::duplicate_predicates() but for range checks
2400 // eliminated by iteration splitting.
2401 Node* PhaseIdealLoop::add_range_check_predicate(IdealLoopTree* loop, CountedLoopNode* cl,
2402                                                 Node* predicate_proj, int scale_con, Node* offset,
2403                                                 Node* limit, jint stride_con, Node* value) {
2404   bool overflow = false;
2405   BoolNode* bol = rc_predicate(loop, predicate_proj, scale_con, offset, value, NULL, stride_con, limit, (stride_con > 0) != (scale_con > 0), overflow);
2406   Node* opaque_bol = new Opaque4Node(C, bol, _igvn.intcon(1));
2407   register_new_node(opaque_bol, predicate_proj);
2408   IfNode* new_iff = NULL;
2409   if (overflow) {
2410     new_iff = new IfNode(predicate_proj, opaque_bol, PROB_MAX, COUNT_UNKNOWN);
2411   } else {
2412     new_iff = new RangeCheckNode(predicate_proj, opaque_bol, PROB_MAX, COUNT_UNKNOWN);
2413   }
2414   register_control(new_iff, loop->_parent, predicate_proj);
2415   Node* iffalse = new IfFalseNode(new_iff);
2416   register_control(iffalse, _ltree_root, new_iff);
2417   ProjNode* iftrue = new IfTrueNode(new_iff);
2418   register_control(iftrue, loop->_parent, new_iff);
2419   Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
2420   register_new_node(frame, C->start());
2421   Node* halt = new HaltNode(iffalse, frame);
2422   register_control(halt, _ltree_root, iffalse);
2423   C->root()->add_req(halt);
2424   return iftrue;
2425 }
2426 
2427 //------------------------------do_range_check---------------------------------
2428 // Eliminate range-checks and other trip-counter vs loop-invariant tests.
2429 int PhaseIdealLoop::do_range_check(IdealLoopTree *loop, Node_List &old_new) {
2430 #ifndef PRODUCT
2431   if (PrintOpto && VerifyLoopOptimizations) {
2432     tty->print("Range Check Elimination ");
2433     loop->dump_head();
2434   } else if (TraceLoopOpts) {
2435     tty->print("RangeCheck   ");
2436     loop->dump_head();
2437   }
2438 #endif
2439 
2440   assert(RangeCheckElimination, "");
2441   CountedLoopNode *cl = loop->_head->as_CountedLoop();
2442   // If we fail before trying to eliminate range checks, set multiversion state
2443   int closed_range_checks = 1;
2444 
2445   // protect against stride not being a constant
2446   if (!cl->stride_is_con()) {
2447     return closed_range_checks;
2448   }
2449   // Find the trip counter; we are iteration splitting based on it
2450   Node *trip_counter = cl->phi();
2451   // Find the main loop limit; we will trim it's iterations
2452   // to not ever trip end tests
2453   Node *main_limit = cl->limit();
2454 
2455   // Check graph shape. Cannot optimize a loop if zero-trip
2456   // Opaque1 node is optimized away and then another round
2457   // of loop opts attempted.
2458   if (!is_canonical_loop_entry(cl)) {
2459     return closed_range_checks;
2460   }
2461 
2462   // Need to find the main-loop zero-trip guard
2463   Node *ctrl = cl->skip_predicates();
2464   Node *iffm = ctrl->in(0);
2465   Node *opqzm = iffm->in(1)->in(1)->in(2);
2466   assert(opqzm->in(1) == main_limit, "do not understand situation");
2467 
2468   // Find the pre-loop limit; we will expand its iterations to
2469   // not ever trip low tests.
2470   Node *p_f = iffm->in(0);
2471   // pre loop may have been optimized out
2472   if (p_f->Opcode() != Op_IfFalse) {
2473     return closed_range_checks;
2474   }
2475   CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2476   assert(pre_end->loopnode()->is_pre_loop(), "");
2477   Node *pre_opaq1 = pre_end->limit();
2478   // Occasionally it's possible for a pre-loop Opaque1 node to be
2479   // optimized away and then another round of loop opts attempted.
2480   // We can not optimize this particular loop in that case.
2481   if (pre_opaq1->Opcode() != Op_Opaque1) {
2482     return closed_range_checks;
2483   }
2484   Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
2485   Node *pre_limit = pre_opaq->in(1);
2486 
2487   // Where do we put new limit calculations
2488   Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
2489 
2490   // Ensure the original loop limit is available from the
2491   // pre-loop Opaque1 node.
2492   Node *orig_limit = pre_opaq->original_loop_limit();
2493   if (orig_limit == NULL || _igvn.type(orig_limit) == Type::TOP) {
2494     return closed_range_checks;
2495   }
2496   // Must know if its a count-up or count-down loop
2497 
2498   int stride_con = cl->stride_con();
2499   Node *zero = _igvn.intcon(0);
2500   Node *one  = _igvn.intcon(1);
2501   // Use symmetrical int range [-max_jint,max_jint]
2502   Node *mini = _igvn.intcon(-max_jint);
2503   set_ctrl(zero, C->root());
2504   set_ctrl(one,  C->root());
2505   set_ctrl(mini, C->root());
2506 
2507   // Range checks that do not dominate the loop backedge (ie.
2508   // conditionally executed) can lengthen the pre loop limit beyond
2509   // the original loop limit. To prevent this, the pre limit is
2510   // (for stride > 0) MINed with the original loop limit (MAXed
2511   // stride < 0) when some range_check (rc) is conditionally
2512   // executed.
2513   bool conditional_rc = false;
2514 
2515   // Count number of range checks and reduce by load range limits, if zero,
2516   // the loop is in canonical form to multiversion.
2517   closed_range_checks = 0;
2518 
2519   Node* predicate_proj = cl->skip_strip_mined()->in(LoopNode::EntryControl);
2520   assert(predicate_proj->is_Proj() && predicate_proj->in(0)->is_If(), "if projection only");
2521 
2522   // Check loop body for tests of trip-counter plus loop-invariant vs loop-variant.
2523   for (uint i = 0; i < loop->_body.size(); i++) {
2524     Node *iff = loop->_body[i];
2525     if (iff->Opcode() == Op_If ||
2526         iff->Opcode() == Op_RangeCheck) { // Test?
2527       // Test is an IfNode, has 2 projections.  If BOTH are in the loop
2528       // we need loop unswitching instead of iteration splitting.
2529       closed_range_checks++;
2530       Node *exit = loop->is_loop_exit(iff);
2531       if (!exit) continue;
2532       int flip = (exit->Opcode() == Op_IfTrue) ? 1 : 0;
2533 
2534       // Get boolean condition to test
2535       Node *i1 = iff->in(1);
2536       if (!i1->is_Bool()) continue;
2537       BoolNode *bol = i1->as_Bool();
2538       BoolTest b_test = bol->_test;
2539       // Flip sense of test if exit condition is flipped
2540       if (flip) {
2541         b_test = b_test.negate();
2542       }
2543       // Get compare
2544       Node *cmp = bol->in(1);
2545 
2546       // Look for trip_counter + offset vs limit
2547       Node *rc_exp = cmp->in(1);
2548       Node *limit  = cmp->in(2);
2549       int scale_con= 1;        // Assume trip counter not scaled
2550 
2551       Node *limit_c = get_ctrl(limit);
2552       if (loop->is_member(get_loop(limit_c))) {
2553         // Compare might have operands swapped; commute them
2554         b_test = b_test.commute();
2555         rc_exp = cmp->in(2);
2556         limit  = cmp->in(1);
2557         limit_c = get_ctrl(limit);
2558         if (loop->is_member(get_loop(limit_c))) {
2559           continue;             // Both inputs are loop varying; cannot RCE
2560         }
2561       }
2562       // Here we know 'limit' is loop invariant
2563 
2564       // 'limit' maybe pinned below the zero trip test (probably from a
2565       // previous round of rce), in which case, it can't be used in the
2566       // zero trip test expression which must occur before the zero test's if.
2567       if (is_dominator(ctrl, limit_c)) {
2568         continue;  // Don't rce this check but continue looking for other candidates.
2569       }
2570 
2571       // Check for scaled induction variable plus an offset
2572       Node *offset = NULL;
2573 
2574       if (!is_scaled_iv_plus_offset(rc_exp, trip_counter, &scale_con, &offset)) {
2575         continue;
2576       }
2577 
2578       Node *offset_c = get_ctrl(offset);
2579       if (loop->is_member(get_loop(offset_c))) {
2580         continue;               // Offset is not really loop invariant
2581       }
2582       // Here we know 'offset' is loop invariant.
2583 
2584       // As above for the 'limit', the 'offset' maybe pinned below the
2585       // zero trip test.
2586       if (is_dominator(ctrl, offset_c)) {
2587         continue; // Don't rce this check but continue looking for other candidates.
2588       }
2589 #ifdef ASSERT
2590       if (TraceRangeLimitCheck) {
2591         tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
2592         bol->dump(2);
2593       }
2594 #endif
2595       // At this point we have the expression as:
2596       //   scale_con * trip_counter + offset :: limit
2597       // where scale_con, offset and limit are loop invariant.  Trip_counter
2598       // monotonically increases by stride_con, a constant.  Both (or either)
2599       // stride_con and scale_con can be negative which will flip about the
2600       // sense of the test.
2601 
2602       // Adjust pre and main loop limits to guard the correct iteration set
2603       if (cmp->Opcode() == Op_CmpU) { // Unsigned compare is really 2 tests
2604         if (b_test._test == BoolTest::lt) { // Range checks always use lt
2605           // The underflow and overflow limits: 0 <= scale*I+offset < limit
2606           add_constraint(stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit);
2607           // (0-offset)/scale could be outside of loop iterations range.
2608           conditional_rc = true;
2609           Node* init = cl->init_trip();
2610           Node* opaque_init = new Opaque1Node(C, init);
2611           register_new_node(opaque_init, predicate_proj);
2612           // template predicate so it can be updated on next unrolling
2613           predicate_proj = add_range_check_predicate(loop, cl, predicate_proj, scale_con, offset, limit, stride_con, opaque_init);
2614           assert(skeleton_predicate_has_opaque(predicate_proj->in(0)->as_If()), "unexpected");
2615           // predicate on first value of first iteration
2616           predicate_proj = add_range_check_predicate(loop, cl, predicate_proj, scale_con, offset, limit, stride_con, init);
2617           assert(!skeleton_predicate_has_opaque(predicate_proj->in(0)->as_If()), "unexpected");
2618           int init_inc = stride_con/cl->unrolled_count();
2619           assert(init_inc != 0, "invalid loop increment");
2620           Node* max_value = _igvn.intcon(stride_con - init_inc);
2621           max_value = new AddINode(init, max_value);
2622           register_new_node(max_value, predicate_proj);
2623           // predicate on last value of first iteration (in case unrolling has already happened)
2624           predicate_proj = add_range_check_predicate(loop, cl, predicate_proj, scale_con, offset, limit, stride_con, max_value);
2625           assert(!skeleton_predicate_has_opaque(predicate_proj->in(0)->as_If()), "unexpected");
2626         } else {
2627           if (PrintOpto) {
2628             tty->print_cr("missed RCE opportunity");
2629           }
2630           continue;             // In release mode, ignore it
2631         }
2632       } else {                  // Otherwise work on normal compares
2633         switch(b_test._test) {
2634         case BoolTest::gt:
2635           // Fall into GE case
2636         case BoolTest::ge:
2637           // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit
2638           scale_con = -scale_con;
2639           offset = new SubINode(zero, offset);
2640           register_new_node(offset, pre_ctrl);
2641           limit  = new SubINode(zero, limit);
2642           register_new_node(limit, pre_ctrl);
2643           // Fall into LE case
2644         case BoolTest::le:
2645           if (b_test._test != BoolTest::gt) {
2646             // Convert X <= Y to X < Y+1
2647             limit = new AddINode(limit, one);
2648             register_new_node(limit, pre_ctrl);
2649           }
2650           // Fall into LT case
2651         case BoolTest::lt:
2652           // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit
2653           // Note: (MIN_INT+1 == -MAX_INT) is used instead of MIN_INT here
2654           // to avoid problem with scale == -1: MIN_INT/(-1) == MIN_INT.
2655           add_constraint(stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit);
2656           // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
2657           // Note: negative offset is replaced with 0 but (MIN_INT+1)/scale could
2658           // still be outside of loop range.
2659           conditional_rc = true;
2660           break;
2661         default:
2662           if (PrintOpto) {
2663             tty->print_cr("missed RCE opportunity");
2664           }
2665           continue;             // Unhandled case
2666         }
2667       }
2668 
2669       // Kill the eliminated test
2670       C->set_major_progress();
2671       Node *kill_con = _igvn.intcon(1-flip);
2672       set_ctrl(kill_con, C->root());
2673       _igvn.replace_input_of(iff, 1, kill_con);
2674       // Find surviving projection
2675       assert(iff->is_If(), "");
2676       ProjNode* dp = ((IfNode*)iff)->proj_out(1-flip);
2677       // Find loads off the surviving projection; remove their control edge
2678       for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
2679         Node* cd = dp->fast_out(i); // Control-dependent node
2680         if (cd->is_Load() && cd->depends_only_on_test()) {   // Loads can now float around in the loop
2681           // Allow the load to float around in the loop, or before it
2682           // but NOT before the pre-loop.
2683           _igvn.replace_input_of(cd, 0, ctrl); // ctrl, not NULL
2684           --i;
2685           --imax;
2686         }
2687       }
2688       if (limit->Opcode() == Op_LoadRange) {
2689         closed_range_checks--;
2690       }
2691     } // End of is IF
2692   }
2693   if (predicate_proj != cl->skip_strip_mined()->in(LoopNode::EntryControl)) {
2694     _igvn.replace_input_of(cl->skip_strip_mined(), LoopNode::EntryControl, predicate_proj);
2695     set_idom(cl->skip_strip_mined(), predicate_proj, dom_depth(cl->skip_strip_mined()));
2696   }
2697 
2698   // Update loop limits
2699   if (conditional_rc) {
2700     pre_limit = (stride_con > 0) ? (Node*)new MinINode(pre_limit, orig_limit)
2701                                  : (Node*)new MaxINode(pre_limit, orig_limit);
2702     register_new_node(pre_limit, pre_ctrl);
2703   }
2704   _igvn.replace_input_of(pre_opaq, 1, pre_limit);
2705 
2706   // Note:: we are making the main loop limit no longer precise;
2707   // need to round up based on stride.
2708   cl->set_nonexact_trip_count();
2709   Node *main_cle = cl->loopexit();
2710   Node *main_bol = main_cle->in(1);
2711   // Hacking loop bounds; need private copies of exit test
2712   if (main_bol->outcnt() > 1) {     // BoolNode shared?
2713     main_bol = main_bol->clone();   // Clone a private BoolNode
2714     register_new_node(main_bol, main_cle->in(0));
2715     _igvn.replace_input_of(main_cle, 1, main_bol);
2716   }
2717   Node *main_cmp = main_bol->in(1);
2718   if (main_cmp->outcnt() > 1) {     // CmpNode shared?
2719     main_cmp = main_cmp->clone();   // Clone a private CmpNode
2720     register_new_node(main_cmp, main_cle->in(0));
2721     _igvn.replace_input_of(main_bol, 1, main_cmp);
2722   }
2723   // Hack the now-private loop bounds
2724   _igvn.replace_input_of(main_cmp, 2, main_limit);
2725   // The OpaqueNode is unshared by design
2726   assert(opqzm->outcnt() == 1, "cannot hack shared node");
2727   _igvn.replace_input_of(opqzm, 1, main_limit);
2728 
2729   return closed_range_checks;
2730 }
2731 
2732 //------------------------------has_range_checks-------------------------------
2733 // Check to see if RCE cleaned the current loop of range-checks.
2734 void PhaseIdealLoop::has_range_checks(IdealLoopTree *loop) {
2735   assert(RangeCheckElimination, "");
2736 
2737   // skip if not a counted loop
2738   if (!loop->is_counted()) return;
2739 
2740   CountedLoopNode *cl = loop->_head->as_CountedLoop();
2741 
2742   // skip this loop if it is already checked
2743   if (cl->has_been_range_checked()) return;
2744 
2745   // Now check for existence of range checks
2746   for (uint i = 0; i < loop->_body.size(); i++) {
2747     Node *iff = loop->_body[i];
2748     int iff_opc = iff->Opcode();
2749     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2750       cl->mark_has_range_checks();
2751       break;
2752     }
2753   }
2754   cl->set_has_been_range_checked();
2755 }
2756 
2757 //-------------------------multi_version_post_loops----------------------------
2758 // Check the range checks that remain, if simple, use the bounds to guard
2759 // which version to a post loop we execute, one with range checks or one without
2760 bool PhaseIdealLoop::multi_version_post_loops(IdealLoopTree *rce_loop, IdealLoopTree *legacy_loop) {
2761   bool multi_version_succeeded = false;
2762   assert(RangeCheckElimination, "");
2763   CountedLoopNode *legacy_cl = legacy_loop->_head->as_CountedLoop();
2764   assert(legacy_cl->is_post_loop(), "");
2765 
2766   // Check for existence of range checks using the unique instance to make a guard with
2767   Unique_Node_List worklist;
2768   for (uint i = 0; i < legacy_loop->_body.size(); i++) {
2769     Node *iff = legacy_loop->_body[i];
2770     int iff_opc = iff->Opcode();
2771     if (iff_opc == Op_If || iff_opc == Op_RangeCheck) {
2772       worklist.push(iff);
2773     }
2774   }
2775 
2776   // Find RCE'd post loop so that we can stage its guard.
2777   if (!is_canonical_loop_entry(legacy_cl)) return multi_version_succeeded;
2778   Node* ctrl = legacy_cl->in(LoopNode::EntryControl);
2779   Node* iffm = ctrl->in(0);
2780 
2781   // Now we test that both the post loops are connected
2782   Node* post_loop_region = iffm->in(0);
2783   if (post_loop_region == NULL) return multi_version_succeeded;
2784   if (!post_loop_region->is_Region()) return multi_version_succeeded;
2785   Node* covering_region = post_loop_region->in(RegionNode::Control+1);
2786   if (covering_region == NULL) return multi_version_succeeded;
2787   if (!covering_region->is_Region()) return multi_version_succeeded;
2788   Node* p_f = covering_region->in(RegionNode::Control);
2789   if (p_f == NULL) return multi_version_succeeded;
2790   if (!p_f->is_IfFalse()) return multi_version_succeeded;
2791   if (!p_f->in(0)->is_CountedLoopEnd()) return multi_version_succeeded;
2792   CountedLoopEndNode* rce_loop_end = p_f->in(0)->as_CountedLoopEnd();
2793   if (rce_loop_end == NULL) return multi_version_succeeded;
2794   CountedLoopNode* rce_cl = rce_loop_end->loopnode();
2795   if (rce_cl == NULL || !rce_cl->is_post_loop()) return multi_version_succeeded;
2796   CountedLoopNode *known_rce_cl = rce_loop->_head->as_CountedLoop();
2797   if (rce_cl != known_rce_cl) return multi_version_succeeded;
2798 
2799   // Then we fetch the cover entry test
2800   ctrl = rce_cl->in(LoopNode::EntryControl);
2801   if (!ctrl->is_IfTrue() && !ctrl->is_IfFalse()) return multi_version_succeeded;
2802 
2803 #ifndef PRODUCT
2804   if (TraceLoopOpts) {
2805     tty->print("PostMultiVersion\n");
2806     rce_loop->dump_head();
2807     legacy_loop->dump_head();
2808   }
2809 #endif
2810 
2811   // Now fetch the limit we want to compare against
2812   Node *limit = rce_cl->limit();
2813   bool first_time = true;
2814 
2815   // If we got this far, we identified the post loop which has been RCE'd and
2816   // we have a work list.  Now we will try to transform the if guard to cause
2817   // the loop pair to be multi version executed with the determination left to runtime
2818   // or the optimizer if full information is known about the given arrays at compile time.
2819   Node *last_min = NULL;
2820   multi_version_succeeded = true;
2821   while (worklist.size()) {
2822     Node* rc_iffm = worklist.pop();
2823     if (rc_iffm->is_If()) {
2824       Node *rc_bolzm = rc_iffm->in(1);
2825       if (rc_bolzm->is_Bool()) {
2826         Node *rc_cmpzm = rc_bolzm->in(1);
2827         if (rc_cmpzm->is_Cmp()) {
2828           Node *rc_left = rc_cmpzm->in(2);
2829           if (rc_left->Opcode() != Op_LoadRange) {
2830             multi_version_succeeded = false;
2831             break;
2832           }
2833           if (first_time) {
2834             last_min = rc_left;
2835             first_time = false;
2836           } else {
2837             Node *cur_min = new MinINode(last_min, rc_left);
2838             last_min = cur_min;
2839             _igvn.register_new_node_with_optimizer(last_min);
2840           }
2841         }
2842       }
2843     }
2844   }
2845 
2846   // All we have to do is update the limit of the rce loop
2847   // with the min of our expression and the current limit.
2848   // We will use this expression to replace the current limit.
2849   if (last_min && multi_version_succeeded) {
2850     Node *cur_min = new MinINode(last_min, limit);
2851     _igvn.register_new_node_with_optimizer(cur_min);
2852     Node *cmp_node = rce_loop_end->cmp_node();
2853     _igvn.replace_input_of(cmp_node, 2, cur_min);
2854     set_ctrl(cur_min, ctrl);
2855     set_loop(cur_min, rce_loop->_parent);
2856 
2857     legacy_cl->mark_is_multiversioned();
2858     rce_cl->mark_is_multiversioned();
2859     multi_version_succeeded = true;
2860 
2861     C->set_major_progress();
2862   }
2863 
2864   return multi_version_succeeded;
2865 }
2866 
2867 //-------------------------poison_rce_post_loop--------------------------------
2868 // Causes the rce'd post loop to be optimized away if multiversioning fails
2869 void PhaseIdealLoop::poison_rce_post_loop(IdealLoopTree *rce_loop) {
2870   CountedLoopNode *rce_cl = rce_loop->_head->as_CountedLoop();
2871   Node* ctrl = rce_cl->in(LoopNode::EntryControl);
2872   if (ctrl->is_IfTrue() || ctrl->is_IfFalse()) {
2873     Node* iffm = ctrl->in(0);
2874     if (iffm->is_If()) {
2875       Node* cur_bool = iffm->in(1);
2876       if (cur_bool->is_Bool()) {
2877         Node* cur_cmp = cur_bool->in(1);
2878         if (cur_cmp->is_Cmp()) {
2879           BoolTest::mask new_test = BoolTest::gt;
2880           BoolNode *new_bool = new BoolNode(cur_cmp, new_test);
2881           _igvn.replace_node(cur_bool, new_bool);
2882           _igvn._worklist.push(new_bool);
2883           Node* left_op = cur_cmp->in(1);
2884           _igvn.replace_input_of(cur_cmp, 2, left_op);
2885           C->set_major_progress();
2886         }
2887       }
2888     }
2889   }
2890 }
2891 
2892 //------------------------------DCE_loop_body----------------------------------
2893 // Remove simplistic dead code from loop body
2894 void IdealLoopTree::DCE_loop_body() {
2895   for (uint i = 0; i < _body.size(); i++) {
2896     if (_body.at(i)->outcnt() == 0) {
2897       _body.map(i, _body.pop());
2898       i--; // Ensure we revisit the updated index.
2899     }
2900   }
2901 }
2902 
2903 
2904 //------------------------------adjust_loop_exit_prob--------------------------
2905 // Look for loop-exit tests with the 50/50 (or worse) guesses from the parsing stage.
2906 // Replace with a 1-in-10 exit guess.
2907 void IdealLoopTree::adjust_loop_exit_prob(PhaseIdealLoop *phase) {
2908   Node *test = tail();
2909   while (test != _head) {
2910     uint top = test->Opcode();
2911     if (top == Op_IfTrue || top == Op_IfFalse) {
2912       int test_con = ((ProjNode*)test)->_con;
2913       assert(top == (uint)(test_con? Op_IfTrue: Op_IfFalse), "sanity");
2914       IfNode *iff = test->in(0)->as_If();
2915       if (iff->outcnt() == 2) {         // Ignore dead tests
2916         Node *bol = iff->in(1);
2917         if (bol && bol->req() > 1 && bol->in(1) &&
2918             ((bol->in(1)->Opcode() == Op_StorePConditional) ||
2919              (bol->in(1)->Opcode() == Op_StoreIConditional) ||
2920              (bol->in(1)->Opcode() == Op_StoreLConditional) ||
2921              (bol->in(1)->Opcode() == Op_CompareAndExchangeB) ||
2922              (bol->in(1)->Opcode() == Op_CompareAndExchangeS) ||
2923              (bol->in(1)->Opcode() == Op_CompareAndExchangeI) ||
2924              (bol->in(1)->Opcode() == Op_CompareAndExchangeL) ||
2925              (bol->in(1)->Opcode() == Op_CompareAndExchangeP) ||
2926              (bol->in(1)->Opcode() == Op_CompareAndExchangeN) ||
2927              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapB) ||
2928              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapS) ||
2929              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapI) ||
2930              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapL) ||
2931              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapP) ||
2932              (bol->in(1)->Opcode() == Op_WeakCompareAndSwapN) ||
2933              (bol->in(1)->Opcode() == Op_CompareAndSwapB) ||
2934              (bol->in(1)->Opcode() == Op_CompareAndSwapS) ||
2935              (bol->in(1)->Opcode() == Op_CompareAndSwapI) ||
2936              (bol->in(1)->Opcode() == Op_CompareAndSwapL) ||
2937              (bol->in(1)->Opcode() == Op_CompareAndSwapP) ||
2938              (bol->in(1)->Opcode() == Op_CompareAndSwapN) ||
2939              (bol->in(1)->Opcode() == Op_ShenandoahCompareAndExchangeP) ||
2940              (bol->in(1)->Opcode() == Op_ShenandoahCompareAndExchangeN) ||
2941              (bol->in(1)->Opcode() == Op_ShenandoahWeakCompareAndSwapP) ||
2942              (bol->in(1)->Opcode() == Op_ShenandoahWeakCompareAndSwapN) ||
2943              (bol->in(1)->Opcode() == Op_ShenandoahCompareAndSwapP) ||
2944              (bol->in(1)->Opcode() == Op_ShenandoahCompareAndSwapN)))
2945           return;               // Allocation loops RARELY take backedge
2946         // Find the OTHER exit path from the IF
2947         Node* ex = iff->proj_out(1-test_con);
2948         float p = iff->_prob;
2949         if (!phase->is_member(this, ex) && iff->_fcnt == COUNT_UNKNOWN) {
2950           if (top == Op_IfTrue) {
2951             if (p < (PROB_FAIR + PROB_UNLIKELY_MAG(3))) {
2952               iff->_prob = PROB_STATIC_FREQUENT;
2953             }
2954           } else {
2955             if (p > (PROB_FAIR - PROB_UNLIKELY_MAG(3))) {
2956               iff->_prob = PROB_STATIC_INFREQUENT;
2957             }
2958           }
2959         }
2960       }
2961     }
2962     test = phase->idom(test);
2963   }
2964 }
2965 
2966 #ifdef ASSERT
2967 static CountedLoopNode* locate_pre_from_main(CountedLoopNode *cl) {
2968   Node *ctrl  = cl->skip_predicates();
2969   assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
2970   Node *iffm = ctrl->in(0);
2971   assert(iffm->Opcode() == Op_If, "");
2972   Node *p_f = iffm->in(0);
2973   assert(p_f->Opcode() == Op_IfFalse, "");
2974   CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2975   assert(pre_end->loopnode()->is_pre_loop(), "");
2976   return pre_end->loopnode();
2977 }
2978 #endif
2979 
2980 // Remove the main and post loops and make the pre loop execute all
2981 // iterations. Useful when the pre loop is found empty.
2982 void IdealLoopTree::remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase) {
2983   CountedLoopEndNode* pre_end = cl->loopexit();
2984   Node* pre_cmp = pre_end->cmp_node();
2985   if (pre_cmp->in(2)->Opcode() != Op_Opaque1) {
2986     // Only safe to remove the main loop if the compiler optimized it
2987     // out based on an unknown number of iterations
2988     return;
2989   }
2990 
2991   // Can we find the main loop?
2992   if (_next == NULL) {
2993     return;
2994   }
2995 
2996   Node* next_head = _next->_head;
2997   if (!next_head->is_CountedLoop()) {
2998     return;
2999   }
3000 
3001   CountedLoopNode* main_head = next_head->as_CountedLoop();
3002   if (!main_head->is_main_loop()) {
3003     return;
3004   }
3005 
3006   assert(locate_pre_from_main(main_head) == cl, "bad main loop");
3007   Node* main_iff = main_head->skip_predicates()->in(0);
3008 
3009   // Remove the Opaque1Node of the pre loop and make it execute all iterations
3010   phase->_igvn.replace_input_of(pre_cmp, 2, pre_cmp->in(2)->in(2));
3011   // Remove the Opaque1Node of the main loop so it can be optimized out
3012   Node* main_cmp = main_iff->in(1)->in(1);
3013   assert(main_cmp->in(2)->Opcode() == Op_Opaque1, "main loop has no opaque node?");
3014   phase->_igvn.replace_input_of(main_cmp, 2, main_cmp->in(2)->in(1));
3015 }
3016 
3017 //------------------------------do_remove_empty_loop---------------------------
3018 // We always attempt remove empty loops.   The approach is to replace the trip
3019 // counter with the value it will have on the last iteration.  This will break
3020 // the loop.
3021 bool IdealLoopTree::do_remove_empty_loop(PhaseIdealLoop *phase) {
3022   // Minimum size must be empty loop
3023   if (_body.size() > EMPTY_LOOP_SIZE) {
3024     return false;
3025   }
3026   if (!_head->is_CountedLoop()) {
3027     return false;   // Dead loop
3028   }
3029   CountedLoopNode *cl = _head->as_CountedLoop();
3030   if (!cl->is_valid_counted_loop()) {
3031     return false;   // Malformed loop
3032   }
3033   if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue)))) {
3034     return false;   // Infinite loop
3035   }
3036   if (cl->is_pre_loop()) {
3037     // If the loop we are removing is a pre-loop then the main and post loop
3038     // can be removed as well.
3039     remove_main_post_loops(cl, phase);
3040   }
3041 
3042 #ifdef ASSERT
3043   // Ensure only one phi which is the iv.
3044   Node* iv = NULL;
3045   for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
3046     Node* n = cl->fast_out(i);
3047     if (n->Opcode() == Op_Phi) {
3048       assert(iv == NULL, "Too many phis");
3049       iv = n;
3050     }
3051   }
3052   assert(iv == cl->phi(), "Wrong phi");
3053 #endif
3054 
3055   // main and post loops have explicitly created zero trip guard
3056   bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
3057   if (needs_guard) {
3058     // Skip guard if values not overlap.
3059     const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
3060     const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
3061     int  stride_con = cl->stride_con();
3062     if (stride_con > 0) {
3063       needs_guard = (init_t->_hi >= limit_t->_lo);
3064     } else {
3065       needs_guard = (init_t->_lo <= limit_t->_hi);
3066     }
3067   }
3068   if (needs_guard) {
3069     // Check for an obvious zero trip guard.
3070     Node* inctrl = PhaseIdealLoop::skip_all_loop_predicates(cl->skip_predicates());
3071     if (inctrl->Opcode() == Op_IfTrue || inctrl->Opcode() == Op_IfFalse) {
3072       bool maybe_swapped = (inctrl->Opcode() == Op_IfFalse);
3073       // The test should look like just the backedge of a CountedLoop
3074       Node* iff = inctrl->in(0);
3075       if (iff->is_If()) {
3076         Node* bol = iff->in(1);
3077         if (bol->is_Bool()) {
3078           BoolTest test = bol->as_Bool()->_test;
3079           if (maybe_swapped) {
3080             test._test = test.commute();
3081             test._test = test.negate();
3082           }
3083           if (test._test == cl->loopexit()->test_trip()) {
3084             Node* cmp = bol->in(1);
3085             int init_idx = maybe_swapped ? 2 : 1;
3086             int limit_idx = maybe_swapped ? 1 : 2;
3087             if (cmp->is_Cmp() && cmp->in(init_idx) == cl->init_trip() && cmp->in(limit_idx) == cl->limit()) {
3088               needs_guard = false;
3089             }
3090           }
3091         }
3092       }
3093     }
3094   }
3095 
3096 #ifndef PRODUCT
3097   if (PrintOpto) {
3098     tty->print("Removing empty loop with%s zero trip guard", needs_guard ? "out" : "");
3099     this->dump_head();
3100   } else if (TraceLoopOpts) {
3101     tty->print("Empty with%s zero trip guard   ", needs_guard ? "out" : "");
3102     this->dump_head();
3103   }
3104 #endif
3105 
3106   if (needs_guard) {
3107     // Peel the loop to ensure there's a zero trip guard
3108     Node_List old_new;
3109     phase->do_peeling(this, old_new);
3110   }
3111 
3112   // Replace the phi at loop head with the final value of the last
3113   // iteration.  Then the CountedLoopEnd will collapse (backedge never
3114   // taken) and all loop-invariant uses of the exit values will be correct.
3115   Node *phi = cl->phi();
3116   Node *exact_limit = phase->exact_limit(this);
3117   if (exact_limit != cl->limit()) {
3118     // We also need to replace the original limit to collapse loop exit.
3119     Node* cmp = cl->loopexit()->cmp_node();
3120     assert(cl->limit() == cmp->in(2), "sanity");
3121     phase->_igvn._worklist.push(cmp->in(2)); // put limit on worklist
3122     phase->_igvn.replace_input_of(cmp, 2, exact_limit); // put cmp on worklist
3123   }
3124   // Note: the final value after increment should not overflow since
3125   // counted loop has limit check predicate.
3126   Node *final = new SubINode(exact_limit, cl->stride());
3127   phase->register_new_node(final,cl->in(LoopNode::EntryControl));
3128   phase->_igvn.replace_node(phi,final);
3129   phase->C->set_major_progress();
3130   return true;
3131 }
3132 
3133 //------------------------------do_one_iteration_loop--------------------------
3134 // Convert one iteration loop into normal code.
3135 bool IdealLoopTree::do_one_iteration_loop(PhaseIdealLoop *phase) {
3136   if (!_head->as_Loop()->is_valid_counted_loop()) {
3137     return false; // Only for counted loop
3138   }
3139   CountedLoopNode *cl = _head->as_CountedLoop();
3140   if (!cl->has_exact_trip_count() || cl->trip_count() != 1) {
3141     return false;
3142   }
3143 
3144 #ifndef PRODUCT
3145   if (TraceLoopOpts) {
3146     tty->print("OneIteration ");
3147     this->dump_head();
3148   }
3149 #endif
3150 
3151   Node *init_n = cl->init_trip();
3152 #ifdef ASSERT
3153   // Loop boundaries should be constant since trip count is exact.
3154   assert(init_n->get_int() + cl->stride_con() >= cl->limit()->get_int(), "should be one iteration");
3155 #endif
3156   // Replace the phi at loop head with the value of the init_trip.
3157   // Then the CountedLoopEnd will collapse (backedge will not be taken)
3158   // and all loop-invariant uses of the exit values will be correct.
3159   phase->_igvn.replace_node(cl->phi(), cl->init_trip());
3160   phase->C->set_major_progress();
3161   return true;
3162 }
3163 
3164 //=============================================================================
3165 //------------------------------iteration_split_impl---------------------------
3166 bool IdealLoopTree::iteration_split_impl(PhaseIdealLoop *phase, Node_List &old_new) {
3167   // Compute loop trip count if possible.
3168   compute_trip_count(phase);
3169 
3170   // Convert one iteration loop into normal code.
3171   if (do_one_iteration_loop(phase)) {
3172     return true;
3173   }
3174   // Check and remove empty loops (spam micro-benchmarks)
3175   if (do_remove_empty_loop(phase)) {
3176     return true;  // Here we removed an empty loop
3177   }
3178 
3179   AutoNodeBudget node_budget(phase);
3180 
3181   bool should_peel     = policy_peeling(phase);
3182   bool should_unswitch = policy_unswitching(phase);
3183 
3184   // Non-counted loops may be peeled; exactly 1 iteration is peeled.
3185   // This removes loop-invariant tests (usually null checks).
3186   if (!_head->is_CountedLoop()) { // Non-counted loop
3187     if (PartialPeelLoop && phase->partial_peel(this, old_new)) {
3188       // Partial peel succeeded so terminate this round of loop opts
3189       return false;
3190     }
3191     if (should_peel) {            // Should we peel?
3192       if (PrintOpto) { tty->print_cr("should_peel"); }
3193       phase->do_peeling(this,old_new);
3194     } else if (should_unswitch) {
3195       phase->do_unswitching(this, old_new);
3196     }
3197     return true;
3198   }
3199   CountedLoopNode *cl = _head->as_CountedLoop();
3200 
3201   if (!cl->is_valid_counted_loop()) return true; // Ignore various kinds of broken loops
3202 
3203   // Do nothing special to pre- and post- loops
3204   if (cl->is_pre_loop() || cl->is_post_loop()) return true;
3205 
3206   // Compute loop trip count from profile data
3207   compute_profile_trip_cnt(phase);
3208 
3209   // Before attempting fancy unrolling, RCE or alignment, see if we want
3210   // to completely unroll this loop or do loop unswitching.
3211   if (cl->is_normal_loop()) {
3212     if (should_unswitch) {
3213       phase->do_unswitching(this, old_new);
3214       return true;
3215     }
3216     bool should_maximally_unroll = policy_maximally_unroll(phase);
3217     if (should_maximally_unroll) {
3218       // Here we did some unrolling and peeling.  Eventually we will
3219       // completely unroll this loop and it will no longer be a loop.
3220       phase->do_maximally_unroll(this, old_new);
3221       return true;
3222     }
3223   }
3224 
3225   // Counted loops may be peeled, may need some iterations run up
3226   // front for RCE, and may want to align loop refs to a cache
3227   // line.  Thus we clone a full loop up front whose trip count is
3228   // at least 1 (if peeling), but may be several more.
3229 
3230   // The main loop will start cache-line aligned with at least 1
3231   // iteration of the unrolled body (zero-trip test required) and
3232   // will have some range checks removed.
3233 
3234   // A post-loop will finish any odd iterations (leftover after
3235   // unrolling), plus any needed for RCE purposes.
3236 
3237   bool should_unroll = policy_unroll(phase);
3238   bool should_rce    = policy_range_check(phase);
3239   // TODO: Remove align -- not used.
3240   bool should_align  = policy_align(phase);
3241 
3242   // If not RCE'ing  (iteration splitting) or Aligning, then we  do not need a
3243   // pre-loop.  We may still need to peel an initial iteration but we will not
3244   // be needing an unknown number of pre-iterations.
3245   //
3246   // Basically, if may_rce_align reports FALSE first time through, we will not
3247   // be able to later do RCE or Aligning on this loop.
3248   bool may_rce_align = !policy_peel_only(phase) || should_rce || should_align;
3249 
3250   // If we have any of these conditions (RCE, alignment, unrolling) met, then
3251   // we switch to the pre-/main-/post-loop model.  This model also covers
3252   // peeling.
3253   if (should_rce || should_align || should_unroll) {
3254     if (cl->is_normal_loop()) { // Convert to 'pre/main/post' loops
3255       if (!phase->may_require_nodes(est_loop_clone_sz(3, _body.size()))) {
3256         return false;
3257       }
3258       phase->insert_pre_post_loops(this,old_new, !may_rce_align);
3259     }
3260     // Adjust the pre- and main-loop limits to let the pre and post loops run
3261     // with full checks, but the main-loop with no checks.  Remove said
3262     // checks from the main body.
3263     if (should_rce) {
3264       if (phase->do_range_check(this, old_new) != 0) {
3265         cl->mark_has_range_checks();
3266       }
3267     } else if (PostLoopMultiversioning) {
3268       phase->has_range_checks(this);
3269     }
3270 
3271     if (should_unroll && !should_peel && PostLoopMultiversioning) {
3272       // Try to setup multiversioning on main loops before they are unrolled
3273       if (cl->is_main_loop() && (cl->unrolled_count() == 1)) {
3274         phase->insert_scalar_rced_post_loop(this, old_new);
3275       }
3276     }
3277 
3278     // Double loop body for unrolling.  Adjust the minimum-trip test (will do
3279     // twice as many iterations as before) and the main body limit (only do
3280     // an even number of trips).  If we are peeling, we might enable some RCE
3281     // and we'd rather unroll the post-RCE'd loop SO... do not unroll if
3282     // peeling.
3283     if (should_unroll && !should_peel) {
3284       if (SuperWordLoopUnrollAnalysis) {
3285         phase->insert_vector_post_loop(this, old_new);
3286       }
3287       phase->do_unroll(this, old_new, true);
3288     }
3289 
3290     // Adjust the pre-loop limits to align the main body iterations.
3291     if (should_align) {
3292       Unimplemented();
3293     }
3294   } else {                      // Else we have an unchanged counted loop
3295     if (should_peel) {          // Might want to peel but do nothing else
3296       phase->do_peeling(this,old_new);
3297     }
3298   }
3299   return true;
3300 }
3301 
3302 
3303 //=============================================================================
3304 //------------------------------iteration_split--------------------------------
3305 bool IdealLoopTree::iteration_split(PhaseIdealLoop* phase, Node_List &old_new) {
3306   // Recursively iteration split nested loops
3307   if (_child && !_child->iteration_split(phase, old_new)) {
3308     return false;
3309   }
3310 
3311   // Clean out prior deadwood
3312   DCE_loop_body();
3313 
3314   // Look for loop-exit tests with my 50/50 guesses from the Parsing stage.
3315   // Replace with a 1-in-10 exit guess.
3316   if (!is_root() && is_loop()) {
3317     adjust_loop_exit_prob(phase);
3318   }
3319 
3320   // Unrolling, RCE and peeling efforts, iff innermost loop.
3321   if (_allow_optimizations && is_innermost()) {
3322     if (!_has_call) {
3323       if (!iteration_split_impl(phase, old_new)) {
3324         return false;
3325       }
3326     } else {
3327       AutoNodeBudget node_budget(phase);
3328       if (policy_unswitching(phase)) {
3329         phase->do_unswitching(this, old_new);
3330       }
3331     }
3332   }
3333 
3334   // Minor offset re-organization to remove loop-fallout uses of
3335   // trip counter when there was no major reshaping.
3336   phase->reorg_offsets(this);
3337 
3338   if (_next && !_next->iteration_split(phase, old_new)) {
3339     return false;
3340   }
3341   return true;
3342 }
3343 
3344 
3345 //=============================================================================
3346 // Process all the loops in the loop tree and replace any fill
3347 // patterns with an intrinsic version.
3348 bool PhaseIdealLoop::do_intrinsify_fill() {
3349   bool changed = false;
3350   for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
3351     IdealLoopTree* lpt = iter.current();
3352     changed |= intrinsify_fill(lpt);
3353   }
3354   return changed;
3355 }
3356 
3357 
3358 // Examine an inner loop looking for a a single store of an invariant
3359 // value in a unit stride loop,
3360 bool PhaseIdealLoop::match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
3361                                      Node*& shift, Node*& con) {
3362   const char* msg = NULL;
3363   Node* msg_node = NULL;
3364 
3365   store_value = NULL;
3366   con = NULL;
3367   shift = NULL;
3368 
3369   // Process the loop looking for stores.  If there are multiple
3370   // stores or extra control flow give at this point.
3371   CountedLoopNode* head = lpt->_head->as_CountedLoop();
3372   for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3373     Node* n = lpt->_body.at(i);
3374     if (n->outcnt() == 0) continue; // Ignore dead
3375     if (n->is_Store()) {
3376       if (store != NULL) {
3377         msg = "multiple stores";
3378         break;
3379       }
3380       int opc = n->Opcode();
3381       if (opc == Op_StoreP || opc == Op_StoreN || opc == Op_StoreNKlass || opc == Op_StoreCM) {
3382         msg = "oop fills not handled";
3383         break;
3384       }
3385       Node* value = n->in(MemNode::ValueIn);
3386       if (!lpt->is_invariant(value)) {
3387         msg  = "variant store value";
3388       } else if (!_igvn.type(n->in(MemNode::Address))->isa_aryptr()) {
3389         msg = "not array address";
3390       }
3391       store = n;
3392       store_value = value;
3393     } else if (n->is_If() && n != head->loopexit_or_null()) {
3394       msg = "extra control flow";
3395       msg_node = n;
3396     }
3397   }
3398 
3399   if (store == NULL) {
3400     // No store in loop
3401     return false;
3402   }
3403 
3404   if (msg == NULL && head->stride_con() != 1) {
3405     // could handle negative strides too
3406     if (head->stride_con() < 0) {
3407       msg = "negative stride";
3408     } else {
3409       msg = "non-unit stride";
3410     }
3411   }
3412 
3413   if (msg == NULL && !store->in(MemNode::Address)->is_AddP()) {
3414     msg = "can't handle store address";
3415     msg_node = store->in(MemNode::Address);
3416   }
3417 
3418   if (msg == NULL &&
3419       (!store->in(MemNode::Memory)->is_Phi() ||
3420        store->in(MemNode::Memory)->in(LoopNode::LoopBackControl) != store)) {
3421     msg = "store memory isn't proper phi";
3422     msg_node = store->in(MemNode::Memory);
3423   }
3424 
3425   // Make sure there is an appropriate fill routine
3426   BasicType t = store->as_Mem()->memory_type();
3427   const char* fill_name;
3428   if (msg == NULL &&
3429       StubRoutines::select_fill_function(t, false, fill_name) == NULL) {
3430     msg = "unsupported store";
3431     msg_node = store;
3432   }
3433 
3434   if (msg != NULL) {
3435 #ifndef PRODUCT
3436     if (TraceOptimizeFill) {
3437       tty->print_cr("not fill intrinsic candidate: %s", msg);
3438       if (msg_node != NULL) msg_node->dump();
3439     }
3440 #endif
3441     return false;
3442   }
3443 
3444   // Make sure the address expression can be handled.  It should be
3445   // head->phi * elsize + con.  head->phi might have a ConvI2L(CastII()).
3446   Node* elements[4];
3447   Node* cast = NULL;
3448   Node* conv = NULL;
3449   bool found_index = false;
3450   int count = store->in(MemNode::Address)->as_AddP()->unpack_offsets(elements, ARRAY_SIZE(elements));
3451   for (int e = 0; e < count; e++) {
3452     Node* n = elements[e];
3453     if (n->is_Con() && con == NULL) {
3454       con = n;
3455     } else if (n->Opcode() == Op_LShiftX && shift == NULL) {
3456       Node* value = n->in(1);
3457 #ifdef _LP64
3458       if (value->Opcode() == Op_ConvI2L) {
3459         conv = value;
3460         value = value->in(1);
3461       }
3462       if (value->Opcode() == Op_CastII &&
3463           value->as_CastII()->has_range_check()) {
3464         // Skip range check dependent CastII nodes
3465         cast = value;
3466         value = value->in(1);
3467       }
3468 #endif
3469       if (value != head->phi()) {
3470         msg = "unhandled shift in address";
3471       } else {
3472         if (type2aelembytes(store->as_Mem()->memory_type(), true) != (1 << n->in(2)->get_int())) {
3473           msg = "scale doesn't match";
3474         } else {
3475           found_index = true;
3476           shift = n;
3477         }
3478       }
3479     } else if (n->Opcode() == Op_ConvI2L && conv == NULL) {
3480       conv = n;
3481       n = n->in(1);
3482       if (n->Opcode() == Op_CastII &&
3483           n->as_CastII()->has_range_check()) {
3484         // Skip range check dependent CastII nodes
3485         cast = n;
3486         n = n->in(1);
3487       }
3488       if (n == head->phi()) {
3489         found_index = true;
3490       } else {
3491         msg = "unhandled input to ConvI2L";
3492       }
3493     } else if (n == head->phi()) {
3494       // no shift, check below for allowed cases
3495       found_index = true;
3496     } else {
3497       msg = "unhandled node in address";
3498       msg_node = n;
3499     }
3500   }
3501 
3502   if (count == -1) {
3503     msg = "malformed address expression";
3504     msg_node = store;
3505   }
3506 
3507   if (!found_index) {
3508     msg = "missing use of index";
3509   }
3510 
3511   // byte sized items won't have a shift
3512   if (msg == NULL && shift == NULL && t != T_BYTE && t != T_BOOLEAN) {
3513     msg = "can't find shift";
3514     msg_node = store;
3515   }
3516 
3517   if (msg != NULL) {
3518 #ifndef PRODUCT
3519     if (TraceOptimizeFill) {
3520       tty->print_cr("not fill intrinsic: %s", msg);
3521       if (msg_node != NULL) msg_node->dump();
3522     }
3523 #endif
3524     return false;
3525   }
3526 
3527   // No make sure all the other nodes in the loop can be handled
3528   VectorSet ok(Thread::current()->resource_area());
3529 
3530   // store related values are ok
3531   ok.set(store->_idx);
3532   ok.set(store->in(MemNode::Memory)->_idx);
3533 
3534   CountedLoopEndNode* loop_exit = head->loopexit();
3535 
3536   // Loop structure is ok
3537   ok.set(head->_idx);
3538   ok.set(loop_exit->_idx);
3539   ok.set(head->phi()->_idx);
3540   ok.set(head->incr()->_idx);
3541   ok.set(loop_exit->cmp_node()->_idx);
3542   ok.set(loop_exit->in(1)->_idx);
3543 
3544   // Address elements are ok
3545   if (con)   ok.set(con->_idx);
3546   if (shift) ok.set(shift->_idx);
3547   if (cast)  ok.set(cast->_idx);
3548   if (conv)  ok.set(conv->_idx);
3549 
3550   for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3551     Node* n = lpt->_body.at(i);
3552     if (n->outcnt() == 0) continue; // Ignore dead
3553     if (ok.test(n->_idx)) continue;
3554     // Backedge projection is ok
3555     if (n->is_IfTrue() && n->in(0) == loop_exit) continue;
3556     if (!n->is_AddP()) {
3557       msg = "unhandled node";
3558       msg_node = n;
3559       break;
3560     }
3561   }
3562 
3563   // Make sure no unexpected values are used outside the loop
3564   for (uint i = 0; msg == NULL && i < lpt->_body.size(); i++) {
3565     Node* n = lpt->_body.at(i);
3566     // These values can be replaced with other nodes if they are used
3567     // outside the loop.
3568     if (n == store || n == loop_exit || n == head->incr() || n == store->in(MemNode::Memory)) continue;
3569     for (SimpleDUIterator iter(n); iter.has_next(); iter.next()) {
3570       Node* use = iter.get();
3571       if (!lpt->_body.contains(use)) {
3572         msg = "node is used outside loop";
3573         // lpt->_body.dump();
3574         msg_node = n;
3575         break;
3576       }
3577     }
3578   }
3579 
3580 #ifdef ASSERT
3581   if (TraceOptimizeFill) {
3582     if (msg != NULL) {
3583       tty->print_cr("no fill intrinsic: %s", msg);
3584       if (msg_node != NULL) msg_node->dump();
3585     } else {
3586       tty->print_cr("fill intrinsic for:");
3587     }
3588     store->dump();
3589     if (Verbose) {
3590       lpt->_body.dump();
3591     }
3592   }
3593 #endif
3594 
3595   return msg == NULL;
3596 }
3597 
3598 
3599 
3600 bool PhaseIdealLoop::intrinsify_fill(IdealLoopTree* lpt) {
3601   // Only for counted inner loops
3602   if (!lpt->is_counted() || !lpt->is_innermost()) {
3603     return false;
3604   }
3605 
3606   // Must have constant stride
3607   CountedLoopNode* head = lpt->_head->as_CountedLoop();
3608   if (!head->is_valid_counted_loop() || !head->is_normal_loop()) {
3609     return false;
3610   }
3611 
3612   head->verify_strip_mined(1);
3613 
3614   // Check that the body only contains a store of a loop invariant
3615   // value that is indexed by the loop phi.
3616   Node* store = NULL;
3617   Node* store_value = NULL;
3618   Node* shift = NULL;
3619   Node* offset = NULL;
3620   if (!match_fill_loop(lpt, store, store_value, shift, offset)) {
3621     return false;
3622   }
3623 
3624   Node* exit = head->loopexit()->proj_out_or_null(0);
3625   if (exit == NULL) {
3626     return false;
3627   }
3628 
3629 #ifndef PRODUCT
3630   if (TraceLoopOpts) {
3631     tty->print("ArrayFill    ");
3632     lpt->dump_head();
3633   }
3634 #endif
3635 
3636   // Now replace the whole loop body by a call to a fill routine that
3637   // covers the same region as the loop.
3638   Node* base = store->in(MemNode::Address)->as_AddP()->in(AddPNode::Base);
3639 
3640   // Build an expression for the beginning of the copy region
3641   Node* index = head->init_trip();
3642 #ifdef _LP64
3643   index = new ConvI2LNode(index);
3644   _igvn.register_new_node_with_optimizer(index);
3645 #endif
3646   if (shift != NULL) {
3647     // byte arrays don't require a shift but others do.
3648     index = new LShiftXNode(index, shift->in(2));
3649     _igvn.register_new_node_with_optimizer(index);
3650   }
3651   index = new AddPNode(base, base, index);
3652   _igvn.register_new_node_with_optimizer(index);
3653   Node* from = new AddPNode(base, index, offset);
3654   _igvn.register_new_node_with_optimizer(from);
3655   // Compute the number of elements to copy
3656   Node* len = new SubINode(head->limit(), head->init_trip());
3657   _igvn.register_new_node_with_optimizer(len);
3658 
3659   BasicType t = store->as_Mem()->memory_type();
3660   bool aligned = false;
3661   if (offset != NULL && head->init_trip()->is_Con()) {
3662     int element_size = type2aelembytes(t);
3663     aligned = (offset->find_intptr_t_type()->get_con() + head->init_trip()->get_int() * element_size) % HeapWordSize == 0;
3664   }
3665 
3666   // Build a call to the fill routine
3667   const char* fill_name;
3668   address fill = StubRoutines::select_fill_function(t, aligned, fill_name);
3669   assert(fill != NULL, "what?");
3670 
3671   // Convert float/double to int/long for fill routines
3672   if (t == T_FLOAT) {
3673     store_value = new MoveF2INode(store_value);
3674     _igvn.register_new_node_with_optimizer(store_value);
3675   } else if (t == T_DOUBLE) {
3676     store_value = new MoveD2LNode(store_value);
3677     _igvn.register_new_node_with_optimizer(store_value);
3678   }
3679 
3680   Node* mem_phi = store->in(MemNode::Memory);
3681   Node* result_ctrl;
3682   Node* result_mem;
3683   const TypeFunc* call_type = OptoRuntime::array_fill_Type();
3684   CallLeafNode *call = new CallLeafNoFPNode(call_type, fill,
3685                                             fill_name, TypeAryPtr::get_array_body_type(t));
3686   uint cnt = 0;
3687   call->init_req(TypeFunc::Parms + cnt++, from);
3688   call->init_req(TypeFunc::Parms + cnt++, store_value);
3689 #ifdef _LP64
3690   len = new ConvI2LNode(len);
3691   _igvn.register_new_node_with_optimizer(len);
3692 #endif
3693   call->init_req(TypeFunc::Parms + cnt++, len);
3694 #ifdef _LP64
3695   call->init_req(TypeFunc::Parms + cnt++, C->top());
3696 #endif
3697   call->init_req(TypeFunc::Control,   head->init_control());
3698   call->init_req(TypeFunc::I_O,       C->top());       // Does no I/O.
3699   call->init_req(TypeFunc::Memory,    mem_phi->in(LoopNode::EntryControl));
3700   call->init_req(TypeFunc::ReturnAdr, C->start()->proj_out_or_null(TypeFunc::ReturnAdr));
3701   call->init_req(TypeFunc::FramePtr,  C->start()->proj_out_or_null(TypeFunc::FramePtr));
3702   _igvn.register_new_node_with_optimizer(call);
3703   result_ctrl = new ProjNode(call,TypeFunc::Control);
3704   _igvn.register_new_node_with_optimizer(result_ctrl);
3705   result_mem = new ProjNode(call,TypeFunc::Memory);
3706   _igvn.register_new_node_with_optimizer(result_mem);
3707 
3708 /* Disable following optimization until proper fix (add missing checks).
3709 
3710   // If this fill is tightly coupled to an allocation and overwrites
3711   // the whole body, allow it to take over the zeroing.
3712   AllocateNode* alloc = AllocateNode::Ideal_allocation(base, this);
3713   if (alloc != NULL && alloc->is_AllocateArray()) {
3714     Node* length = alloc->as_AllocateArray()->Ideal_length();
3715     if (head->limit() == length &&
3716         head->init_trip() == _igvn.intcon(0)) {
3717       if (TraceOptimizeFill) {
3718         tty->print_cr("Eliminated zeroing in allocation");
3719       }
3720       alloc->maybe_set_complete(&_igvn);
3721     } else {
3722 #ifdef ASSERT
3723       if (TraceOptimizeFill) {
3724         tty->print_cr("filling array but bounds don't match");
3725         alloc->dump();
3726         head->init_trip()->dump();
3727         head->limit()->dump();
3728         length->dump();
3729       }
3730 #endif
3731     }
3732   }
3733 */
3734 
3735   if (head->is_strip_mined()) {
3736     // Inner strip mined loop goes away so get rid of outer strip
3737     // mined loop
3738     Node* outer_sfpt = head->outer_safepoint();
3739     Node* in = outer_sfpt->in(0);
3740     Node* outer_out = head->outer_loop_exit();
3741     lazy_replace(outer_out, in);
3742     _igvn.replace_input_of(outer_sfpt, 0, C->top());
3743   }
3744 
3745   // Redirect the old control and memory edges that are outside the loop.
3746   // Sometimes the memory phi of the head is used as the outgoing
3747   // state of the loop.  It's safe in this case to replace it with the
3748   // result_mem.
3749   _igvn.replace_node(store->in(MemNode::Memory), result_mem);
3750   lazy_replace(exit, result_ctrl);
3751   _igvn.replace_node(store, result_mem);
3752   // Any uses the increment outside of the loop become the loop limit.
3753   _igvn.replace_node(head->incr(), head->limit());
3754 
3755   // Disconnect the head from the loop.
3756   for (uint i = 0; i < lpt->_body.size(); i++) {
3757     Node* n = lpt->_body.at(i);
3758     _igvn.replace_node(n, C->top());
3759   }
3760 
3761   return true;
3762 }