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