< prev index next >

src/hotspot/share/opto/loopUnswitch.cpp

Print this page


   1 /*
   2  * Copyright (c) 2006, 2012, 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   // check for vectorized loops, any unswitching was already applied
  66   if (_head->is_CountedLoop() && _head->as_CountedLoop()->do_unroll_only()) {
  67     return false;
  68   }
  69 
  70   int nodes_left = phase->C->max_node_limit() - phase->C->live_nodes();
  71   if ((int)(2 * _body.size()) > nodes_left) {
  72     return false; // Too speculative if running low on nodes.
  73   }
  74   LoopNode* head = _head->as_Loop();
  75   if (head->unswitch_count() + 1 > head->unswitch_max()) {
  76     return false;
  77   }
  78   return phase->find_unswitching_candidate(this) != NULL;
  79 }
  80 
  81 //------------------------------find_unswitching_candidate-----------------------------
  82 // Find candidate "if" for unswitching
  83 IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop) const {
  84 
  85   // Find first invariant test that doesn't exit the loop
  86   LoopNode *head = loop->_head->as_Loop();
  87   IfNode* unswitch_iff = NULL;
  88   Node* n = head->in(LoopNode::LoopBackControl);

  89   while (n != head) {
  90     Node* n_dom = idom(n);
  91     if (n->is_Region()) {
  92       if (n_dom->is_If()) {
  93         IfNode* iff = n_dom->as_If();
  94         if (iff->in(1)->is_Bool()) {
  95           BoolNode* bol = iff->in(1)->as_Bool();
  96           if (bol->in(1)->is_Cmp()) {
  97             // If condition is invariant and not a loop exit,
  98             // then found reason to unswitch.
  99             if (loop->is_invariant(bol) && !loop->is_loop_exit(iff)) {
 100               unswitch_iff = iff;
 101             }























 102           }
 103         }
 104       }
 105     }
 106     n = n_dom;
 107   }
 108   return unswitch_iff;
 109 }
 110 
 111 //------------------------------do_unswitching-----------------------------
 112 // Clone loop with an invariant test (that does not exit) and
 113 // insert a clone of the test that selects which version to
 114 // execute.
 115 void PhaseIdealLoop::do_unswitching (IdealLoopTree *loop, Node_List &old_new) {
 116 
 117   // Find first invariant test that doesn't exit the loop
 118   LoopNode *head = loop->_head->as_Loop();
 119 
 120   IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop);







 121   assert(unswitch_iff != NULL, "should be at least one");
 122 
 123 #ifndef PRODUCT
 124   if (TraceLoopOpts) {
 125     tty->print("Unswitch   %d ", head->unswitch_count()+1);
 126     loop->dump_head();
 127   }
 128 #endif
 129 
 130   // Need to revert back to normal loop
 131   if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) {
 132     head->as_CountedLoop()->set_normal_loop();
 133   }
 134 
 135   ProjNode* proj_true = create_slow_version_of_loop(loop, old_new, unswitch_iff->Opcode(), CloneIncludesStripMined);
 136 
 137 #ifdef ASSERT
 138   Node* uniqc = proj_true->unique_ctrl_out();
 139   Node* entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
 140   Node* predicate = find_predicate(entry);


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


< prev index next >