< prev index next >

src/hotspot/share/opto/loopopts.cpp

Print this page


   1 /*
   2  * Copyright (c) 1999, 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  *


3012 //         :  |   |     |       |
3013 //         :  |   v    stmt2    |
3014 //         :  | exitB:  |       |
3015 //         :  | stmt4   v       |
3016 //         :  |       ifA orig  |
3017 //         :  |      /  \       |
3018 //         :  |     /    \      |
3019 //         :  |    v     v      |
3020 //         :  |  false  true    |
3021 //         :  |  /        \     |
3022 //         :  v  v         -----+
3023 //          RegionA
3024 //             |
3025 //             v
3026 //           exitA
3027 //
3028 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
3029 
3030   assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
3031   if (!loop->_head->is_Loop()) {
3032     return false;  }
3033 
3034   LoopNode *head  = loop->_head->as_Loop();
3035 
3036   if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
3037     return false;
3038   }
3039 
3040   // Check for complex exit control
3041   for(uint ii = 0; ii < loop->_body.size(); ii++ ) {
3042     Node *n = loop->_body.at(ii);
3043     int opc = n->Opcode();
3044     if (n->is_Call()        ||
3045         opc == Op_Catch     ||
3046         opc == Op_CatchProj ||
3047         opc == Op_Jump      ||
3048         opc == Op_JumpProj) {
3049 #ifndef PRODUCT
3050       if (TracePartialPeeling) {
3051         tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
3052       }
3053 #endif
3054       return false;
3055     }
3056   }
3057 
3058   int dd = dom_depth(head);
3059 
3060   // Step 1: find cut point
3061 
3062   // Walk up dominators to loop head looking for first loop exit
3063   // which is executed on every path thru loop.
3064   IfNode *peel_if = NULL;
3065   IfNode *peel_if_cmpu = NULL;
3066 
3067   Node *iff = loop->tail();
3068   while( iff != head ) {
3069     if( iff->is_If() ) {
3070       Node *ctrl = get_ctrl(iff->in(1));
3071       if (ctrl->is_top()) return false; // Dead test on live IF.
3072       // If loop-varying exit-test, check for induction variable
3073       if( loop->is_member(get_loop(ctrl)) &&
3074           loop->is_loop_exit(iff) &&
3075           is_possible_iv_test(iff)) {
3076         Node* cmp = iff->in(1)->in(1);
3077         if (cmp->Opcode() == Op_CmpI) {
3078           peel_if = iff->as_If();
3079         } else {
3080           assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU");
3081           peel_if_cmpu = iff->as_If();
3082         }
3083       }
3084     }
3085     iff = idom(iff);
3086   }

3087   // Prefer signed compare over unsigned compare.
3088   IfNode* new_peel_if = NULL;
3089   if (peel_if == NULL) {
3090     if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
3091       return false;   // No peel point found
3092     }
3093     new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
3094     if (new_peel_if == NULL) {
3095       return false;   // No peel point found
3096     }
3097     peel_if = new_peel_if;
3098   }
3099   Node* last_peel        = stay_in_loop(peel_if, loop);
3100   Node* first_not_peeled = stay_in_loop(last_peel, loop);
3101   if (first_not_peeled == NULL || first_not_peeled == head) {
3102     return false;
3103   }
3104 
3105 #ifndef PRODUCT
3106   if (TraceLoopOpts) {


3114     Node* t = head->in(2);
3115     while (true) {
3116       wl.push(t);
3117       if (t == head) break;
3118       t = idom(t);
3119     }
3120     while (wl.size() > 0) {
3121       Node* tt = wl.pop();
3122       tt->dump();
3123       if (tt == last_peel) tty->print_cr("-- cut --");
3124     }
3125   }
3126 #endif
3127   ResourceArea *area = Thread::current()->resource_area();
3128   VectorSet peel(area);
3129   VectorSet not_peel(area);
3130   Node_List peel_list(area);
3131   Node_List worklist(area);
3132   Node_List sink_list(area);
3133 
3134   if (!may_require_nodes(est_loop_clone_sz(2, loop->_body.size()))) {
3135     return false;
3136   }
3137 
3138   // Set of cfg nodes to peel are those that are executable from
3139   // the head through last_peel.
3140   assert(worklist.size() == 0, "should be empty");
3141   worklist.push(head);
3142   peel.set(head->_idx);
3143   while (worklist.size() > 0) {
3144     Node *n = worklist.pop();
3145     if (n != last_peel) {
3146       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
3147         Node* use = n->fast_out(j);
3148         if (use->is_CFG() &&
3149             loop->is_member(get_loop(use)) &&
3150             !peel.test_set(use->_idx)) {
3151           worklist.push(use);
3152         }
3153       }
3154     }


   1 /*
   2  * Copyright (c) 1999, 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  *


3012 //         :  |   |     |       |
3013 //         :  |   v    stmt2    |
3014 //         :  | exitB:  |       |
3015 //         :  | stmt4   v       |
3016 //         :  |       ifA orig  |
3017 //         :  |      /  \       |
3018 //         :  |     /    \      |
3019 //         :  |    v     v      |
3020 //         :  |  false  true    |
3021 //         :  |  /        \     |
3022 //         :  v  v         -----+
3023 //          RegionA
3024 //             |
3025 //             v
3026 //           exitA
3027 //
3028 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
3029 
3030   assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
3031   if (!loop->_head->is_Loop()) {
3032     return false;
3033   }
3034   LoopNode *head = loop->_head->as_Loop();
3035 
3036   if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
3037     return false;
3038   }
3039 
3040   // Check for complex exit control
3041   for (uint ii = 0; ii < loop->_body.size(); ii++) {
3042     Node *n = loop->_body.at(ii);
3043     int opc = n->Opcode();
3044     if (n->is_Call()        ||
3045         opc == Op_Catch     ||
3046         opc == Op_CatchProj ||
3047         opc == Op_Jump      ||
3048         opc == Op_JumpProj) {
3049 #ifndef PRODUCT
3050       if (TracePartialPeeling) {
3051         tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
3052       }
3053 #endif
3054       return false;
3055     }
3056   }
3057 
3058   int dd = dom_depth(head);
3059 
3060   // Step 1: find cut point
3061 
3062   // Walk up dominators to loop head looking for first loop exit
3063   // which is executed on every path thru loop.
3064   IfNode *peel_if = NULL;
3065   IfNode *peel_if_cmpu = NULL;
3066 
3067   Node *iff = loop->tail();
3068   while (iff != head) {
3069     if (iff->is_If()) {
3070       Node *ctrl = get_ctrl(iff->in(1));
3071       if (ctrl->is_top()) return false; // Dead test on live IF.
3072       // If loop-varying exit-test, check for induction variable
3073       if (loop->is_member(get_loop(ctrl)) &&
3074           loop->is_loop_exit(iff) &&
3075           is_possible_iv_test(iff)) {
3076         Node* cmp = iff->in(1)->in(1);
3077         if (cmp->Opcode() == Op_CmpI) {
3078           peel_if = iff->as_If();
3079         } else {
3080           assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU");
3081           peel_if_cmpu = iff->as_If();
3082         }
3083       }
3084     }
3085     iff = idom(iff);
3086   }
3087 
3088   // Prefer signed compare over unsigned compare.
3089   IfNode* new_peel_if = NULL;
3090   if (peel_if == NULL) {
3091     if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
3092       return false;   // No peel point found
3093     }
3094     new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
3095     if (new_peel_if == NULL) {
3096       return false;   // No peel point found
3097     }
3098     peel_if = new_peel_if;
3099   }
3100   Node* last_peel        = stay_in_loop(peel_if, loop);
3101   Node* first_not_peeled = stay_in_loop(last_peel, loop);
3102   if (first_not_peeled == NULL || first_not_peeled == head) {
3103     return false;
3104   }
3105 
3106 #ifndef PRODUCT
3107   if (TraceLoopOpts) {


3115     Node* t = head->in(2);
3116     while (true) {
3117       wl.push(t);
3118       if (t == head) break;
3119       t = idom(t);
3120     }
3121     while (wl.size() > 0) {
3122       Node* tt = wl.pop();
3123       tt->dump();
3124       if (tt == last_peel) tty->print_cr("-- cut --");
3125     }
3126   }
3127 #endif
3128   ResourceArea *area = Thread::current()->resource_area();
3129   VectorSet peel(area);
3130   VectorSet not_peel(area);
3131   Node_List peel_list(area);
3132   Node_List worklist(area);
3133   Node_List sink_list(area);
3134 
3135   if (!may_require_nodes(loop->est_loop_clone_sz(2))) {
3136     return false;
3137   }
3138 
3139   // Set of cfg nodes to peel are those that are executable from
3140   // the head through last_peel.
3141   assert(worklist.size() == 0, "should be empty");
3142   worklist.push(head);
3143   peel.set(head->_idx);
3144   while (worklist.size() > 0) {
3145     Node *n = worklist.pop();
3146     if (n != last_peel) {
3147       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
3148         Node* use = n->fast_out(j);
3149         if (use->is_CFG() &&
3150             loop->is_member(get_loop(use)) &&
3151             !peel.test_set(use->_idx)) {
3152           worklist.push(use);
3153         }
3154       }
3155     }


< prev index next >