< prev index next >

src/hotspot/share/opto/loopUnswitch.cpp

Print this page

  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();

  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/mulnode.hpp"
 28 #include "opto/addnode.hpp"
 29 #include "opto/connode.hpp"
 30 #include "opto/convertnode.hpp"
 31 #include "opto/loopnode.hpp"
 32 #include "opto/opaquenode.hpp"
 33 #include "opto/rootnode.hpp"
 34 
 35 //================= Loop Unswitching =====================
 36 //
 37 // orig:                       transformed:
 38 //                               if (invariant-test) then
 39 //  predicate                      predicate
 40 //  loop                           loop
 41 //    stmt1                          stmt1
 42 //    if (invariant-test) then       stmt2
 43 //      stmt2                        stmt4
 44 //    else                         endloop
 45 //      stmt3                    else
 46 //    endif                        predicate [clone]
 47 //    stmt4                        loop [clone]
 48 //  endloop                          stmt1 [clone]
 49 //                                   stmt3
 50 //                                   stmt4 [clone]
 51 //                                 endloop
 52 //                               endif
 53 //
 54 // Note: the "else" clause may be empty
 55 
 56 
 57 //------------------------------policy_unswitching-----------------------------
 58 // Return TRUE or FALSE if the loop should be unswitched
 59 // (ie. clone loop with an invariant test that does not exit the loop)
 60 bool IdealLoopTree::policy_unswitching( PhaseIdealLoop *phase ) const {
 61   if (!LoopUnswitching) {
 62     return false;
 63   }
 64   if (!_head->is_Loop()) {
 65     return false;
 66   }
 67 
 68   // If nodes are depleted, some transform has miscalculated its needs.
 69   assert(!phase->exceeding_node_budget(), "sanity");
 70 
 71   // check for vectorized loops, any unswitching was already applied
 72   if (_head->is_CountedLoop() && _head->as_CountedLoop()->is_unroll_only()) {
 73     return false;
 74   }
 75 
 76   LoopNode* head = _head->as_Loop();
 77   if (head->unswitch_count() + 1 > head->unswitch_max()) {
 78     return false;
 79   }
 80 
 81   if (head->is_flattened_arrays()) {
 82     return false;
 83   }
 84 
 85   Node_List unswitch_iffs;
 86   if (phase->find_unswitching_candidate(this, unswitch_iffs) == NULL) {
 87     return false;
 88   }
 89 
 90   // Too speculative if running low on nodes.
 91   return phase->may_require_nodes(est_loop_clone_sz(2));
 92 }
 93 
 94 //------------------------------find_unswitching_candidate-----------------------------
 95 // Find candidate "if" for unswitching
 96 IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop, Node_List& unswitch_iffs) const {
 97 
 98   // Find first invariant test that doesn't exit the loop
 99   LoopNode *head = loop->_head->as_Loop();
100   IfNode* unswitch_iff = NULL;
101   Node* n = head->in(LoopNode::LoopBackControl);
102   while (n != head) {
103     Node* n_dom = idom(n);
104     if (n->is_Region()) {
105       if (n_dom->is_If()) {
106         IfNode* iff = n_dom->as_If();
107         if (iff->in(1)->is_Bool()) {
108           BoolNode* bol = iff->in(1)->as_Bool();
109           if (bol->in(1)->is_Cmp()) {
110             // If condition is invariant and not a loop exit,
111             // then found reason to unswitch.
112             if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
113               unswitch_iff = iff;
114             }
115           }
116         }
117       }
118     }
119     n = n_dom;
120   }
121   if (unswitch_iff != NULL) {
122     unswitch_iffs.push(unswitch_iff);
123   }
124 
125   // Collect all non-flattened array checks for unswitching to create a fast loop
126   // without checks (only non-flattened array accesses) and a slow loop with checks.
127   if (unswitch_iff == NULL || unswitch_iff->is_flat_array_check(&_igvn)) {
128     for (uint i = 0; i < loop->_body.size(); i++) {
129       IfNode* n = loop->_body.at(i)->isa_If();
130       if (n != NULL && n != unswitch_iff && n->is_flat_array_check(&_igvn) &&
131           loop->is_invariant(n->in(1)) && !loop->is_loop_exit(n)) {
132         unswitch_iffs.push(n);
133         if (unswitch_iff == NULL) {
134           unswitch_iff = n;
135         }
136       }
137     }
138   }
139   return unswitch_iff;
140 }
141 
142 //------------------------------do_unswitching-----------------------------
143 // Clone loop with an invariant test (that does not exit) and
144 // insert a clone of the test that selects which version to
145 // execute.
146 void PhaseIdealLoop::do_unswitching(IdealLoopTree *loop, Node_List &old_new) {
147 
148   LoopNode *head = loop->_head->as_Loop();
149   Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
150   if (find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check) != NULL
151       || (UseProfiledLoopPredicate && find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate) != NULL)
152       || (UseLoopPredicate && find_predicate_insertion_point(entry, Deoptimization::Reason_predicate) != NULL)) {
153     assert(entry->is_IfProj(), "sanity - must be ifProj since there is at least one predicate");
154     if (entry->outcnt() > 1) {
155       // Bailout if there are loop predicates from which there are additional control dependencies (i.e. from
156       // loop entry 'entry') to previously partially peeled statements since this case is not handled and can lead
157       // to wrong execution. Remove this bailout, once this is fixed.
158       return;
159     }
160   }
161   // Find first invariant test that doesn't exit the loop
162   Node_List unswitch_iffs;
163   IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop, unswitch_iffs);
164   assert(unswitch_iff != NULL && unswitch_iff == unswitch_iffs.at(0), "should be at least one");
165   bool flat_array_checks = unswitch_iffs.size() > 1;
166 
167 #ifndef PRODUCT
168   if (TraceLoopOpts) {
169     tty->print("Unswitch   %d ", head->unswitch_count()+1);
170     loop->dump_head();
171     for (uint i = 0; i < unswitch_iffs.size(); i++) {
172       unswitch_iffs.at(i)->dump(3);
173       tty->cr();
174     }
175   }
176 #endif
177 
178   // Need to revert back to normal loop
179   if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) {
180     head->as_CountedLoop()->set_normal_loop();
181   }
182 
183   IfNode* invar_iff = create_slow_version_of_loop(loop, old_new, unswitch_iffs, CloneIncludesStripMined);
184   ProjNode* proj_true = invar_iff->proj_out(1);
185   ProjNode* proj_false = invar_iff->proj_out(0);
186 
187 #ifdef ASSERT
188   assert(proj_true->is_IfTrue(), "must be true projection");
189   entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
190   Node* predicate = find_predicate(entry);
191   if (predicate == NULL) {
192     // No empty predicate
193     Node* uniqc = proj_true->unique_ctrl_out();
194     assert((uniqc == head && !head->is_strip_mined()) || (uniqc == head->in(LoopNode::EntryControl)
195            && head->is_strip_mined()), "must hold by construction if no predicates");
196   } else {
197     // There is at least one empty predicate. When calling 'skip_loop_predicates' on each found empty predicate,
198     // we should end up at 'proj_true'.
199     Node* proj_before_first_empty_predicate = skip_loop_predicates(entry);
200     if (UseProfiledLoopPredicate) {
201       predicate = find_predicate(proj_before_first_empty_predicate);
202       if (predicate != NULL) {
203         proj_before_first_empty_predicate = skip_loop_predicates(predicate);
204       }
205     }
206     if (UseLoopPredicate) {
207       predicate = find_predicate(proj_before_first_empty_predicate);
208       if (predicate != NULL) {
209         proj_before_first_empty_predicate = skip_loop_predicates(predicate);
210       }
211     }
212     assert(proj_true == proj_before_first_empty_predicate, "must hold by construction if at least one predicate");
213   }
214 #endif
215   // Increment unswitch count
216   LoopNode* head_clone = old_new[head->_idx]->as_Loop();
217   int nct = head->unswitch_count() + 1;
218   head->set_unswitch_count(nct);
219   head_clone->set_unswitch_count(nct);
220 
221   // Hoist invariant casts out of each loop to the appropriate control projection.


222   Node_List worklist;
223   for (uint i = 0; i < unswitch_iffs.size(); i++) {
224     IfNode* iff = unswitch_iffs.at(i)->as_If();
225     for (DUIterator_Fast imax, i = iff->fast_outs(imax); i < imax; i++) {
226       ProjNode* proj = iff->fast_out(i)->as_Proj();
227       // Copy to a worklist for easier manipulation
228       for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
229         Node* use = proj->fast_out(j);
230         if (use->Opcode() == Op_CheckCastPP && loop->is_invariant(use->in(1))) {
231           worklist.push(use);
232         }
233       }
234       ProjNode* invar_proj = invar_iff->proj_out(proj->_con)->as_Proj();
235       while (worklist.size() > 0) {
236         Node* use = worklist.pop();
237         Node* nuse = use->clone();
238         nuse->set_req(0, invar_proj);
239         _igvn.replace_input_of(use, 1, nuse);
240         register_new_node(nuse, invar_proj);
241         // Same for the clone if we are removing checks from the slow loop
242         if (!flat_array_checks) {
243           Node* use_clone = old_new[use->_idx];
244           _igvn.replace_input_of(use_clone, 1, nuse);
245         }
246       }











247     }
248   }
249 
250   // Hardwire the control paths in the loops into if(true) and if(false)
251   for (uint i = 0; i < unswitch_iffs.size(); i++) {
252     IfNode* iff = unswitch_iffs.at(i)->as_If();
253     _igvn.rehash_node_delayed(iff);
254     dominated_by(proj_true, iff);
255   }
256   IfNode* unswitch_iff_clone = old_new[unswitch_iff->_idx]->as_If();
257   if (!flat_array_checks) {
258     ProjNode* proj_false = invar_iff->proj_out(0)->as_Proj();
259     _igvn.rehash_node_delayed(unswitch_iff_clone);
260     dominated_by(proj_false, unswitch_iff_clone);
261   } else {
262     // Leave the flattened array checks in the slow loop and
263     // prevent it from being unswitched again based on these checks.
264     head_clone->mark_flattened_arrays();
265   }
266 
267   // Reoptimize loops
268   loop->record_for_igvn();
269   for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
270     Node *n = loop->_body[i];
271     Node *n_clone = old_new[n->_idx];
272     _igvn._worklist.push(n_clone);
273   }
274 
275 #ifndef PRODUCT
276   if (TraceLoopUnswitching) {
277     for (uint i = 0; i < unswitch_iffs.size(); i++) {
278       tty->print_cr("Loop unswitching orig: %d @ %d  new: %d @ %d",
279                     head->_idx,                unswitch_iffs.at(i)->_idx,
280                     old_new[head->_idx]->_idx, old_new[unswitch_iffs.at(i)->_idx]->_idx);
281     }
282   }
283 #endif
284 
285   C->set_major_progress();
286 }
287 
288 //-------------------------create_slow_version_of_loop------------------------
289 // Create a slow version of the loop by cloning the loop
290 // and inserting an if to select fast-slow versions.
291 // Return the inserted if.
292 IfNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop,
293                                                     Node_List &old_new,
294                                                     Node_List &unswitch_iffs,
295                                                     CloneLoopMode mode) {
296   LoopNode* head  = loop->_head->as_Loop();
297   bool counted_loop = head->is_CountedLoop();
298   Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
299   _igvn.rehash_node_delayed(entry);
300   IdealLoopTree* outer_loop = loop->_parent;
301 
302   head->verify_strip_mined(1);
303 
304   // Add test to new "if" outside of loop
305   IfNode* unswitch_iff = unswitch_iffs.at(0)->as_If();
306   BoolNode* bol = unswitch_iff->in(1)->as_Bool();
307   if (unswitch_iffs.size() > 1) {
308     // Flattened array checks are used on array access to switch between
309     // a legacy object array access and a flattened inline type array
310     // access. We want the performance impact on legacy accesses to be
311     // as small as possible so we make two copies of the loop: a fast
312     // one where all accesses are known to be legacy, a slow one where
313     // some accesses are to flattened arrays. Flattened array checks
314     // can be removed from the fast loop (true proj) but not from the
315     // slow loop (false proj) as it can have a mix of flattened/legacy accesses.
316     assert(bol->_test._test == BoolTest::ne, "IfTrue proj must point to flat array");
317     bol = bol->clone()->as_Bool();
318     register_new_node(bol, entry);
319     FlatArrayCheckNode* cmp = bol->in(1)->clone()->as_FlatArrayCheck();
320     register_new_node(cmp, entry);
321     bol->set_req(1, cmp);
322     // Combine all checks into a single one that fails if one array is flattened
323     assert(cmp->req() == 3, "unexpected number of inputs for FlatArrayCheck");
324     cmp->add_req_batch(C->top(), unswitch_iffs.size() - 1);
325     for (uint i = 0; i < unswitch_iffs.size(); i++) {
326       Node* array = unswitch_iffs.at(i)->in(1)->in(1)->in(FlatArrayCheckNode::Array);
327       cmp->set_req(FlatArrayCheckNode::Array + i, array);
328     }
329   }
330 
331   IfNode* iff = (unswitch_iff->Opcode() == Op_RangeCheck) ? new RangeCheckNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt) :
332       new IfNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt);
333   register_node(iff, outer_loop, entry, dom_depth(entry));
334   ProjNode* iffast = new IfTrueNode(iff);
335   register_node(iffast, outer_loop, iff, dom_depth(iff));
336   ProjNode* ifslow = new IfFalseNode(iff);
337   register_node(ifslow, outer_loop, iff, dom_depth(iff));
338 
339   // Clone the loop body.  The clone becomes the slow loop.  The
340   // original pre-header will (illegally) have 3 control users
341   // (old & new loops & new if).
342   clone_loop(loop, old_new, dom_depth(head->skip_strip_mined()), mode, iff);
343   assert(old_new[head->_idx]->is_Loop(), "" );
344 
345   // Fast (true) and Slow (false) control
346   ProjNode* iffast_pred = iffast;
347   ProjNode* ifslow_pred = ifslow;
348   clone_predicates_to_unswitched_loop(loop, old_new, iffast_pred, ifslow_pred);
349 
350   Node* l = head->skip_strip_mined();
351   _igvn.replace_input_of(l, LoopNode::EntryControl, iffast_pred);
352   set_idom(l, iffast_pred, dom_depth(l));
353   LoopNode* slow_l = old_new[head->_idx]->as_Loop()->skip_strip_mined();
354   _igvn.replace_input_of(slow_l, LoopNode::EntryControl, ifslow_pred);
355   set_idom(slow_l, ifslow_pred, dom_depth(l));
356 
357   recompute_dom_depth();
358 
359   return iff;
360 }
361 
362 LoopNode* PhaseIdealLoop::create_reserve_version_of_loop(IdealLoopTree *loop, CountedLoopReserveKit* lk) {
363   Node_List old_new;
364   LoopNode* head  = loop->_head->as_Loop();
365   bool counted_loop = head->is_CountedLoop();
366   Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
367   _igvn.rehash_node_delayed(entry);
368   IdealLoopTree* outer_loop = head->is_strip_mined() ? loop->_parent->_parent : loop->_parent;
369 
370   ConINode* const_1 = _igvn.intcon(1);
371   set_ctrl(const_1, C->root());
372   IfNode* iff = new IfNode(entry, const_1, PROB_MAX, COUNT_UNKNOWN);
373   register_node(iff, outer_loop, entry, dom_depth(entry));
374   ProjNode* iffast = new IfTrueNode(iff);
375   register_node(iffast, outer_loop, iff, dom_depth(iff));
376   ProjNode* ifslow = new IfFalseNode(iff);
377   register_node(ifslow, outer_loop, iff, dom_depth(iff));
378 
379   // Clone the loop body.  The clone becomes the slow loop.  The
380   // original pre-header will (illegally) have 3 control users
381   // (old & new loops & new if).
382   clone_loop(loop, old_new, dom_depth(head), CloneIncludesStripMined, iff);
383   assert(old_new[head->_idx]->is_Loop(), "" );
384 
385   LoopNode* slow_head = old_new[head->_idx]->as_Loop();
< prev index next >