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 }
|