1 /*
   2  * Copyright (c) 2006, 2018, 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 "memory/allocation.inline.hpp"
  27 #include "opto/connode.hpp"
  28 #include "opto/convertnode.hpp"
  29 #include "opto/loopnode.hpp"
  30 #include "opto/opaquenode.hpp"
  31 #include "opto/rootnode.hpp"
  32 #include "utilities/macros.hpp"
  33 #if INCLUDE_SHENANDOAHGC
  34 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  35 #endif
  36 
  37 //================= Loop Unswitching =====================
  38 //
  39 // orig:                       transformed:
  40 //                               if (invariant-test) then
  41 //  predicate                      predicate
  42 //  loop                           loop
  43 //    stmt1                          stmt1
  44 //    if (invariant-test) then       stmt2
  45 //      stmt2                        stmt4
  46 //    else                         endloop
  47 //      stmt3                    else
  48 //    endif                        predicate [clone]
  49 //    stmt4                        loop [clone]
  50 //  endloop                          stmt1 [clone]
  51 //                                   stmt3
  52 //                                   stmt4 [clone]
  53 //                                 endloop
  54 //                               endif
  55 //
  56 // Note: the "else" clause may be empty
  57 
  58 //------------------------------policy_unswitching-----------------------------
  59 // Return TRUE or FALSE if the loop should be unswitched
  60 // (ie. clone loop with an invariant test that does not exit the loop)
  61 bool IdealLoopTree::policy_unswitching(PhaseIdealLoop *phase, bool shenandoah_opts) const {
  62   if( !LoopUnswitching ) {
  63     return false;
  64   }
  65   if (!_head->is_Loop()) {
  66     return false;
  67   }
  68 
  69   // check for vectorized loops, any unswitching was already applied
  70   if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) {
  71     return false;
  72   }
  73 
  74   int nodes_left = phase->C->max_node_limit() - phase->C->live_nodes();
  75   if ((int)(2 * _body.size()) > nodes_left) {
  76     return false; // Too speculative if running low on nodes.
  77   }
  78   LoopNode* head = _head->as_Loop();
  79   if (head->unswitch_count() + 1 > head->unswitch_max()) {
  80     return false;
  81   }
  82   return phase->find_unswitching_candidate(this, shenandoah_opts) != NULL;
  83 }
  84 
  85 //------------------------------find_unswitching_candidate-----------------------------
  86 // Find candidate "if" for unswitching
  87 IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop, bool shenandoah_opts) const {
  88 
  89   // Find first invariant test that doesn't exit the loop
  90   LoopNode *head = loop->_head->as_Loop();
  91   IfNode* unswitch_iff = NULL;
  92   Node* n = head->in(LoopNode::LoopBackControl);
  93   int loop_has_sfpts = -1;
  94   while (n != head) {
  95     Node* n_dom = idom(n);
  96     if (n->is_Region()) {
  97       if (n_dom->is_If()) {
  98         IfNode* iff = n_dom->as_If();
  99         if (iff->in(1)->is_Bool()) {
 100           BoolNode* bol = iff->in(1)->as_Bool();
 101           if (bol->in(1)->is_Cmp()) {
 102             // If condition is invariant and not a loop exit,
 103             // then found reason to unswitch.
 104             if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
 105               unswitch_iff = iff;
 106             }
 107 #if INCLUDE_SHENANDOAHGC
 108             else if (shenandoah_opts &&
 109                        (ShenandoahWriteBarrierNode::is_heap_stable_test(iff)) &&
 110                        (loop_has_sfpts == -1 || loop_has_sfpts == 0)) {
 111               assert(UseShenandoahGC, "shenandoah only");
 112               assert(!loop->is_loop_exit(iff), "both branches should be in the loop");
 113               if (loop_has_sfpts == -1) {
 114                 for(uint i = 0; i < loop->_body.size(); i++) {
 115                   Node *m = loop->_body[i];
 116                   if (m->is_SafePoint() && !m->is_CallLeaf()) {
 117                     loop_has_sfpts = 1;
 118                     break;
 119                   }
 120                 }
 121                 if (loop_has_sfpts == -1) {
 122                   loop_has_sfpts = 0;
 123                 }
 124               }
 125               if (!loop_has_sfpts) {
 126                 unswitch_iff = iff;
 127               }
 128             }
 129 #endif
 130           }
 131         }
 132       }
 133     }
 134     n = n_dom;
 135   }
 136   return unswitch_iff;
 137 }
 138 
 139 //------------------------------do_unswitching-----------------------------
 140 // Clone loop with an invariant test (that does not exit) and
 141 // insert a clone of the test that selects which version to
 142 // execute.
 143 void PhaseIdealLoop::do_unswitching(IdealLoopTree *loop, Node_List &old_new, bool shenandoah_opts) {
 144 
 145   // Find first invariant test that doesn't exit the loop
 146   LoopNode *head = loop->_head->as_Loop();
 147 
 148   IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop, shenandoah_opts);
 149 
 150 #if INCLUDE_SHENANDOAHGC
 151   if (ShenandoahWriteBarrierNode::is_heap_stable_test(unswitch_iff)) {
 152     ShenandoahWriteBarrierNode::move_heap_stable_test_out_of_loop(unswitch_iff, this);
 153   }
 154 #endif
 155 
 156   assert(unswitch_iff != NULL, "should be at least one");
 157 
 158 #ifndef PRODUCT
 159   if (TraceLoopOpts) {
 160     tty->print("Unswitch   %d ", head->unswitch_count()+1);
 161     loop->dump_head();
 162   }
 163 #endif
 164 
 165   // Need to revert back to normal loop
 166   if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) {
 167     head->as_CountedLoop()->set_normal_loop();
 168   }
 169 
 170   ProjNode* proj_true = create_slow_version_of_loop(loop, old_new, unswitch_iff->Opcode(), CloneIncludesStripMined);
 171 
 172 #ifdef ASSERT
 173   Node* uniqc = proj_true->unique_ctrl_out();
 174   Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
 175   Node* predicate = find_predicate(entry);
 176   if (predicate != NULL) {
 177     entry = skip_loop_predicates(entry);
 178   }
 179   if (predicate != NULL && UseLoopPredicate) {
 180     // We may have two predicates, find first.
 181     Node* n = find_predicate(entry);
 182     if (n != NULL) {
 183       predicate = n;
 184       entry = skip_loop_predicates(entry);
 185     }
 186   }
 187   if (predicate != NULL && UseProfiledLoopPredicate) {
 188     entry = find_predicate(entry);
 189     if (entry != NULL) predicate = entry;
 190   }
 191   if (predicate != NULL) predicate = predicate->in(0);
 192   assert(proj_true->is_IfTrue() &&
 193          (predicate == NULL && uniqc == head && !head->is_strip_mined() ||
 194           predicate == NULL && uniqc == head->in(LoopNode::EntryControl) && head->is_strip_mined() ||
 195           predicate != NULL && uniqc == predicate), "by construction");
 196 #endif
 197   // Increment unswitch count
 198   LoopNode* head_clone = old_new[head->_idx]->as_Loop();
 199   int nct = head->unswitch_count() + 1;
 200   head->set_unswitch_count(nct);
 201   head_clone->set_unswitch_count(nct);
 202 
 203   // Add test to new "if" outside of loop
 204   IfNode* invar_iff   = proj_true->in(0)->as_If();
 205   Node* invar_iff_c   = invar_iff->in(0);
 206   BoolNode* bol       = unswitch_iff->in(1)->as_Bool();
 207   invar_iff->set_req(1, bol);
 208   invar_iff->_prob    = unswitch_iff->_prob;
 209 
 210   ProjNode* proj_false = invar_iff->proj_out(0)->as_Proj();
 211 
 212   // Hoist invariant casts out of each loop to the appropriate
 213   // control projection.
 214 
 215   Node_List worklist;
 216 
 217   for (DUIterator_Fast imax, i = unswitch_iff->fast_outs(imax); i < imax; i++) {
 218     ProjNode* proj= unswitch_iff->fast_out(i)->as_Proj();
 219     // Copy to a worklist for easier manipulation
 220     for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
 221       Node* use = proj->fast_out(j);
 222       if (use->Opcode() == Op_CheckCastPP && loop->is_invariant(use->in(1))) {
 223         worklist.push(use);
 224       }
 225     }
 226     ProjNode* invar_proj = invar_iff->proj_out(proj->_con)->as_Proj();
 227     while (worklist.size() > 0) {
 228       Node* use = worklist.pop();
 229       Node* nuse = use->clone();
 230       nuse->set_req(0, invar_proj);
 231       _igvn.replace_input_of(use, 1, nuse);
 232       register_new_node(nuse, invar_proj);
 233       // Same for the clone
 234       Node* use_clone = old_new[use->_idx];
 235       _igvn.replace_input_of(use_clone, 1, nuse);
 236     }
 237   }
 238 
 239   // Hardwire the control paths in the loops into if(true) and if(false)
 240   _igvn.rehash_node_delayed(unswitch_iff);
 241   short_circuit_if(unswitch_iff, proj_true);
 242 
 243   IfNode* unswitch_iff_clone = old_new[unswitch_iff->_idx]->as_If();
 244   _igvn.rehash_node_delayed(unswitch_iff_clone);
 245   short_circuit_if(unswitch_iff_clone, proj_false);
 246 
 247   // Reoptimize loops
 248   loop->record_for_igvn();
 249   for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
 250     Node *n = loop->_body[i];
 251     Node *n_clone = old_new[n->_idx];
 252     _igvn._worklist.push(n_clone);
 253   }
 254 
 255 #ifndef PRODUCT
 256   if (TraceLoopUnswitching) {
 257     tty->print_cr("Loop unswitching orig: %d @ %d  new: %d @ %d",
 258                   head->_idx,                unswitch_iff->_idx,
 259                   old_new[head->_idx]->_idx, unswitch_iff_clone->_idx);
 260   }
 261 #endif
 262 
 263   C->set_major_progress();
 264 }
 265 
 266 //-------------------------create_slow_version_of_loop------------------------
 267 // Create a slow version of the loop by cloning the loop
 268 // and inserting an if to select fast-slow versions.
 269 // Return control projection of the entry to the fast version.
 270 ProjNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop,
 271                                                       Node_List &old_new,
 272                                                       int opcode,
 273                                                       CloneLoopMode mode) {
 274   LoopNode* head  = loop->_head->as_Loop();
 275   bool counted_loop = head->is_CountedLoop();
 276   Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
 277   _igvn.rehash_node_delayed(entry);
 278   IdealLoopTree* outer_loop = loop->_parent;
 279 
 280   head->verify_strip_mined(1);
 281 
 282   Node *cont      = _igvn.intcon(1);
 283   set_ctrl(cont, C->root());
 284   Node* opq       = new Opaque1Node(C, cont);
 285   register_node(opq, outer_loop, entry, dom_depth(entry));
 286   Node *bol       = new Conv2BNode(opq);
 287   register_node(bol, outer_loop, entry, dom_depth(entry));
 288   IfNode* iff = (opcode == Op_RangeCheck) ? new RangeCheckNode(entry, bol, PROB_MAX, COUNT_UNKNOWN) :
 289     new IfNode(entry, bol, PROB_MAX, COUNT_UNKNOWN);
 290   register_node(iff, outer_loop, entry, dom_depth(entry));
 291   ProjNode* iffast = new IfTrueNode(iff);
 292   register_node(iffast, outer_loop, iff, dom_depth(iff));
 293   ProjNode* ifslow = new IfFalseNode(iff);
 294   register_node(ifslow, outer_loop, iff, dom_depth(iff));
 295 
 296   // Clone the loop body.  The clone becomes the fast loop.  The
 297   // original pre-header will (illegally) have 3 control users
 298   // (old & new loops & new if).
 299   clone_loop(loop, old_new, dom_depth(head->skip_strip_mined()), mode, iff);
 300   assert(old_new[head->_idx]->is_Loop(), "" );
 301 
 302   // Fast (true) control
 303   Node* iffast_pred = clone_loop_predicates(entry, iffast, !counted_loop);
 304 
 305   // Slow (false) control
 306   Node* ifslow_pred = clone_loop_predicates(entry, ifslow, !counted_loop);
 307 
 308   Node* l = head->skip_strip_mined();
 309   _igvn.replace_input_of(l, LoopNode::EntryControl, iffast_pred);
 310   set_idom(l, iffast_pred, dom_depth(l));
 311   LoopNode* slow_l = old_new[head->_idx]->as_Loop()->skip_strip_mined();
 312   _igvn.replace_input_of(slow_l, LoopNode::EntryControl, ifslow_pred);
 313   set_idom(slow_l, ifslow_pred, dom_depth(l));
 314 
 315   recompute_dom_depth();
 316 
 317   return iffast;
 318 }
 319 
 320 LoopNode* PhaseIdealLoop::create_reserve_version_of_loop(IdealLoopTree *loop, CountedLoopReserveKit* lk) {
 321   Node_List old_new;
 322   LoopNode* head  = loop->_head->as_Loop();
 323   bool counted_loop = head->is_CountedLoop();
 324   Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
 325   _igvn.rehash_node_delayed(entry);
 326   IdealLoopTree* outer_loop = head->is_strip_mined() ? loop->_parent->_parent : loop->_parent;
 327 
 328   ConINode* const_1 = _igvn.intcon(1);
 329   set_ctrl(const_1, C->root());
 330   IfNode* iff = new IfNode(entry, const_1, PROB_MAX, COUNT_UNKNOWN);
 331   register_node(iff, outer_loop, entry, dom_depth(entry));
 332   ProjNode* iffast = new IfTrueNode(iff);
 333   register_node(iffast, outer_loop, iff, dom_depth(iff));
 334   ProjNode* ifslow = new IfFalseNode(iff);
 335   register_node(ifslow, outer_loop, iff, dom_depth(iff));
 336 
 337   // Clone the loop body.  The clone becomes the fast loop.  The
 338   // original pre-header will (illegally) have 3 control users
 339   // (old & new loops & new if).
 340   clone_loop(loop, old_new, dom_depth(head), CloneIncludesStripMined, iff);
 341   assert(old_new[head->_idx]->is_Loop(), "" );
 342 
 343   LoopNode* slow_head = old_new[head->_idx]->as_Loop();
 344 
 345 #ifndef PRODUCT
 346   if (TraceLoopOpts) {
 347     tty->print_cr("PhaseIdealLoop::create_reserve_version_of_loop:");
 348     tty->print("\t iff = %d, ", iff->_idx); iff->dump();
 349     tty->print("\t iffast = %d, ", iffast->_idx); iffast->dump();
 350     tty->print("\t ifslow = %d, ", ifslow->_idx); ifslow->dump();
 351     tty->print("\t before replace_input_of: head = %d, ", head->_idx); head->dump();
 352     tty->print("\t before replace_input_of: slow_head = %d, ", slow_head->_idx); slow_head->dump();
 353   }
 354 #endif
 355 
 356   // Fast (true) control
 357   _igvn.replace_input_of(head->skip_strip_mined(), LoopNode::EntryControl, iffast);
 358   // Slow (false) control
 359   _igvn.replace_input_of(slow_head->skip_strip_mined(), LoopNode::EntryControl, ifslow);
 360 
 361   recompute_dom_depth();
 362 
 363   lk->set_iff(iff);
 364 
 365 #ifndef PRODUCT
 366   if (TraceLoopOpts ) {
 367     tty->print("\t after  replace_input_of: head = %d, ", head->_idx); head->dump();
 368     tty->print("\t after  replace_input_of: slow_head = %d, ", slow_head->_idx); slow_head->dump();
 369   }
 370 #endif
 371 
 372   return slow_head->as_Loop();
 373 }
 374 
 375 CountedLoopReserveKit::CountedLoopReserveKit(PhaseIdealLoop* phase, IdealLoopTree *loop, bool active = true) :
 376   _phase(phase),
 377   _lpt(loop),
 378   _lp(NULL),
 379   _iff(NULL),
 380   _lp_reserved(NULL),
 381   _has_reserved(false),
 382   _use_new(false),
 383   _active(active)
 384   {
 385     create_reserve();
 386   };
 387 
 388 CountedLoopReserveKit::~CountedLoopReserveKit() {
 389   if (!_active) {
 390     return;
 391   }
 392 
 393   if (_has_reserved && !_use_new) {
 394     // intcon(0)->iff-node reverts CF to the reserved copy
 395     ConINode* const_0 = _phase->_igvn.intcon(0);
 396     _phase->set_ctrl(const_0, _phase->C->root());
 397     _iff->set_req(1, const_0);
 398 
 399     #ifndef PRODUCT
 400       if (TraceLoopOpts) {
 401         tty->print_cr("CountedLoopReserveKit::~CountedLoopReserveKit()");
 402         tty->print("\t discard loop %d and revert to the reserved loop clone %d: ", _lp->_idx, _lp_reserved->_idx);
 403         _lp_reserved->dump();
 404       }
 405     #endif
 406   }
 407 }
 408 
 409 bool CountedLoopReserveKit::create_reserve() {
 410   if (!_active) {
 411     return false;
 412   }
 413 
 414   if(!_lpt->_head->is_CountedLoop()) {
 415     if (TraceLoopOpts) {
 416       tty->print_cr("CountedLoopReserveKit::create_reserve: %d not counted loop", _lpt->_head->_idx);
 417     }
 418     return false;
 419   }
 420   CountedLoopNode *cl = _lpt->_head->as_CountedLoop();
 421   if (!cl->is_valid_counted_loop()) {
 422     if (TraceLoopOpts) {
 423       tty->print_cr("CountedLoopReserveKit::create_reserve: %d not valid counted loop", cl->_idx);
 424     }
 425     return false; // skip malformed counted loop
 426   }
 427   if (!cl->is_main_loop()) {
 428     bool loop_not_canonical = true;
 429     if (cl->is_post_loop() && (cl->slp_max_unroll() > 0)) {
 430       loop_not_canonical = false;
 431     }
 432     // only reject some loop forms
 433     if (loop_not_canonical) {
 434       if (TraceLoopOpts) {
 435         tty->print_cr("CountedLoopReserveKit::create_reserve: %d not canonical loop", cl->_idx);
 436       }
 437       return false; // skip normal, pre, and post (conditionally) loops
 438     }
 439   }
 440 
 441   _lp = _lpt->_head->as_Loop();
 442   _lp_reserved = _phase->create_reserve_version_of_loop(_lpt, this);
 443 
 444   if (!_lp_reserved->is_CountedLoop()) {
 445     return false;
 446   }
 447 
 448   Node* ifslow_pred = _lp_reserved->skip_strip_mined()->in(LoopNode::EntryControl);
 449 
 450   if (!ifslow_pred->is_IfFalse()) {
 451     return false;
 452   }
 453 
 454   Node* iff = ifslow_pred->in(0);
 455   if (!iff->is_If() || iff != _iff) {
 456     return false;
 457   }
 458 
 459   if (iff->in(1)->Opcode() != Op_ConI) {
 460     return false;
 461   }
 462 
 463   return _has_reserved = true;
 464 }