Mon, 23 Jun 2014 13:33:23 +0200
8046289: compiler/6340864/TestLongVect.java timeout with
Reviewed-by: iveresov, vlivanov
kvn@2727 | 1 | /* |
drchase@6680 | 2 | * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. |
kvn@2727 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
kvn@2727 | 4 | * |
kvn@2727 | 5 | * This code is free software; you can redistribute it and/or modify it |
kvn@2727 | 6 | * under the terms of the GNU General Public License version 2 only, as |
kvn@2727 | 7 | * published by the Free Software Foundation. |
kvn@2727 | 8 | * |
kvn@2727 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
kvn@2727 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
kvn@2727 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
kvn@2727 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
kvn@2727 | 13 | * accompanied this code). |
kvn@2727 | 14 | * |
kvn@2727 | 15 | * You should have received a copy of the GNU General Public License version |
kvn@2727 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
kvn@2727 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
kvn@2727 | 18 | * |
kvn@2727 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
kvn@2727 | 20 | * or visit www.oracle.com if you need additional information or have any |
kvn@2727 | 21 | * questions. |
kvn@2727 | 22 | * |
kvn@2727 | 23 | */ |
kvn@2727 | 24 | |
kvn@2727 | 25 | #include "precompiled.hpp" |
kvn@2727 | 26 | #include "opto/loopnode.hpp" |
kvn@2727 | 27 | #include "opto/addnode.hpp" |
kvn@2727 | 28 | #include "opto/callnode.hpp" |
kvn@2727 | 29 | #include "opto/connode.hpp" |
kvn@2727 | 30 | #include "opto/loopnode.hpp" |
kvn@2727 | 31 | #include "opto/mulnode.hpp" |
kvn@2727 | 32 | #include "opto/rootnode.hpp" |
kvn@2727 | 33 | #include "opto/subnode.hpp" |
kvn@2727 | 34 | |
kvn@2727 | 35 | /* |
kvn@2727 | 36 | * The general idea of Loop Predication is to insert a predicate on the entry |
kvn@2727 | 37 | * path to a loop, and raise a uncommon trap if the check of the condition fails. |
kvn@2727 | 38 | * The condition checks are promoted from inside the loop body, and thus |
kvn@2727 | 39 | * the checks inside the loop could be eliminated. Currently, loop predication |
kvn@2727 | 40 | * optimization has been applied to remove array range check and loop invariant |
kvn@2727 | 41 | * checks (such as null checks). |
kvn@2727 | 42 | */ |
kvn@2727 | 43 | |
kvn@2727 | 44 | //-------------------------------register_control------------------------- |
kvn@2727 | 45 | void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) { |
kvn@2727 | 46 | assert(n->is_CFG(), "must be control node"); |
kvn@2727 | 47 | _igvn.register_new_node_with_optimizer(n); |
kvn@2727 | 48 | loop->_body.push(n); |
kvn@2727 | 49 | set_loop(n, loop); |
kvn@2727 | 50 | // When called from beautify_loops() idom is not constructed yet. |
kvn@2727 | 51 | if (_idom != NULL) { |
kvn@2727 | 52 | set_idom(n, pred, dom_depth(pred)); |
kvn@2727 | 53 | } |
kvn@2727 | 54 | } |
kvn@2727 | 55 | |
kvn@2727 | 56 | //------------------------------create_new_if_for_predicate------------------------ |
kvn@2727 | 57 | // create a new if above the uct_if_pattern for the predicate to be promoted. |
kvn@2727 | 58 | // |
kvn@2727 | 59 | // before after |
kvn@2727 | 60 | // ---------- ---------- |
kvn@2727 | 61 | // ctrl ctrl |
kvn@2727 | 62 | // | | |
kvn@2727 | 63 | // | | |
kvn@2727 | 64 | // v v |
kvn@2727 | 65 | // iff new_iff |
kvn@2727 | 66 | // / \ / \ |
kvn@2727 | 67 | // / \ / \ |
kvn@2727 | 68 | // v v v v |
kvn@2727 | 69 | // uncommon_proj cont_proj if_uct if_cont |
kvn@2727 | 70 | // \ | | | | |
kvn@2727 | 71 | // \ | | | | |
kvn@2727 | 72 | // v v v | v |
kvn@2727 | 73 | // rgn loop | iff |
kvn@2727 | 74 | // | | / \ |
kvn@2727 | 75 | // | | / \ |
kvn@2727 | 76 | // v | v v |
kvn@2727 | 77 | // uncommon_trap | uncommon_proj cont_proj |
kvn@2727 | 78 | // \ \ | | |
kvn@2727 | 79 | // \ \ | | |
kvn@2727 | 80 | // v v v v |
kvn@2727 | 81 | // rgn loop |
kvn@2727 | 82 | // | |
kvn@2727 | 83 | // | |
kvn@2727 | 84 | // v |
kvn@2727 | 85 | // uncommon_trap |
kvn@2727 | 86 | // |
kvn@2727 | 87 | // |
kvn@2727 | 88 | // We will create a region to guard the uct call if there is no one there. |
kvn@2727 | 89 | // The true projecttion (if_cont) of the new_iff is returned. |
kvn@2727 | 90 | // This code is also used to clone predicates to clonned loops. |
kvn@2727 | 91 | ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry, |
kvn@2727 | 92 | Deoptimization::DeoptReason reason) { |
roland@5981 | 93 | assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!"); |
kvn@2727 | 94 | IfNode* iff = cont_proj->in(0)->as_If(); |
kvn@2727 | 95 | |
kvn@2727 | 96 | ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); |
kvn@2727 | 97 | Node *rgn = uncommon_proj->unique_ctrl_out(); |
kvn@2727 | 98 | assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); |
kvn@2727 | 99 | |
kvn@2727 | 100 | uint proj_index = 1; // region's edge corresponding to uncommon_proj |
kvn@2727 | 101 | if (!rgn->is_Region()) { // create a region to guard the call |
kvn@2727 | 102 | assert(rgn->is_Call(), "must be call uct"); |
kvn@2727 | 103 | CallNode* call = rgn->as_Call(); |
kvn@2727 | 104 | IdealLoopTree* loop = get_loop(call); |
kvn@4115 | 105 | rgn = new (C) RegionNode(1); |
kvn@2727 | 106 | rgn->add_req(uncommon_proj); |
kvn@2727 | 107 | register_control(rgn, loop, uncommon_proj); |
kvn@2727 | 108 | _igvn.hash_delete(call); |
kvn@2727 | 109 | call->set_req(0, rgn); |
kvn@2727 | 110 | // When called from beautify_loops() idom is not constructed yet. |
kvn@2727 | 111 | if (_idom != NULL) { |
kvn@2727 | 112 | set_idom(call, rgn, dom_depth(rgn)); |
kvn@2727 | 113 | } |
kvn@2727 | 114 | } else { |
kvn@2727 | 115 | // Find region's edge corresponding to uncommon_proj |
kvn@2727 | 116 | for (; proj_index < rgn->req(); proj_index++) |
kvn@2727 | 117 | if (rgn->in(proj_index) == uncommon_proj) break; |
kvn@2727 | 118 | assert(proj_index < rgn->req(), "sanity"); |
kvn@2727 | 119 | } |
kvn@2727 | 120 | |
kvn@2727 | 121 | Node* entry = iff->in(0); |
kvn@2727 | 122 | if (new_entry != NULL) { |
kvn@2727 | 123 | // Clonning the predicate to new location. |
kvn@2727 | 124 | entry = new_entry; |
kvn@2727 | 125 | } |
kvn@2727 | 126 | // Create new_iff |
kvn@2727 | 127 | IdealLoopTree* lp = get_loop(entry); |
kvn@2727 | 128 | IfNode *new_iff = iff->clone()->as_If(); |
kvn@2727 | 129 | new_iff->set_req(0, entry); |
kvn@2727 | 130 | register_control(new_iff, lp, entry); |
kvn@4115 | 131 | Node *if_cont = new (C) IfTrueNode(new_iff); |
kvn@4115 | 132 | Node *if_uct = new (C) IfFalseNode(new_iff); |
kvn@2727 | 133 | if (cont_proj->is_IfFalse()) { |
kvn@2727 | 134 | // Swap |
kvn@2727 | 135 | Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; |
kvn@2727 | 136 | } |
kvn@2727 | 137 | register_control(if_cont, lp, new_iff); |
kvn@2727 | 138 | register_control(if_uct, get_loop(rgn), new_iff); |
kvn@2727 | 139 | |
kvn@2727 | 140 | // if_uct to rgn |
kvn@2727 | 141 | _igvn.hash_delete(rgn); |
kvn@2727 | 142 | rgn->add_req(if_uct); |
kvn@2727 | 143 | // When called from beautify_loops() idom is not constructed yet. |
kvn@2727 | 144 | if (_idom != NULL) { |
kvn@2727 | 145 | Node* ridom = idom(rgn); |
kvn@2727 | 146 | Node* nrdom = dom_lca(ridom, new_iff); |
kvn@2727 | 147 | set_idom(rgn, nrdom, dom_depth(rgn)); |
kvn@2727 | 148 | } |
kvn@2727 | 149 | |
kvn@2727 | 150 | // If rgn has phis add new edges which has the same |
kvn@2727 | 151 | // value as on original uncommon_proj pass. |
kvn@2727 | 152 | assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last"); |
kvn@2727 | 153 | bool has_phi = false; |
kvn@2727 | 154 | for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) { |
kvn@2727 | 155 | Node* use = rgn->fast_out(i); |
kvn@2727 | 156 | if (use->is_Phi() && use->outcnt() > 0) { |
kvn@2727 | 157 | assert(use->in(0) == rgn, ""); |
kvn@3847 | 158 | _igvn.rehash_node_delayed(use); |
kvn@2727 | 159 | use->add_req(use->in(proj_index)); |
kvn@2727 | 160 | has_phi = true; |
kvn@2727 | 161 | } |
kvn@2727 | 162 | } |
kvn@2727 | 163 | assert(!has_phi || rgn->req() > 3, "no phis when region is created"); |
kvn@2727 | 164 | |
kvn@2727 | 165 | if (new_entry == NULL) { |
kvn@2727 | 166 | // Attach if_cont to iff |
kvn@2727 | 167 | _igvn.hash_delete(iff); |
kvn@2727 | 168 | iff->set_req(0, if_cont); |
kvn@2727 | 169 | if (_idom != NULL) { |
kvn@2727 | 170 | set_idom(iff, if_cont, dom_depth(iff)); |
kvn@2727 | 171 | } |
kvn@2727 | 172 | } |
kvn@2727 | 173 | return if_cont->as_Proj(); |
kvn@2727 | 174 | } |
kvn@2727 | 175 | |
kvn@2727 | 176 | //------------------------------create_new_if_for_predicate------------------------ |
kvn@2727 | 177 | // Create a new if below new_entry for the predicate to be cloned (IGVN optimization) |
kvn@2727 | 178 | ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry, |
kvn@2727 | 179 | Deoptimization::DeoptReason reason) { |
kvn@2727 | 180 | assert(new_entry != 0, "only used for clone predicate"); |
roland@5981 | 181 | assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!"); |
kvn@2727 | 182 | IfNode* iff = cont_proj->in(0)->as_If(); |
kvn@2727 | 183 | |
kvn@2727 | 184 | ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); |
kvn@2727 | 185 | Node *rgn = uncommon_proj->unique_ctrl_out(); |
kvn@2727 | 186 | assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); |
kvn@2727 | 187 | |
kvn@2727 | 188 | uint proj_index = 1; // region's edge corresponding to uncommon_proj |
kvn@2727 | 189 | if (!rgn->is_Region()) { // create a region to guard the call |
kvn@2727 | 190 | assert(rgn->is_Call(), "must be call uct"); |
kvn@2727 | 191 | CallNode* call = rgn->as_Call(); |
kvn@4115 | 192 | rgn = new (C) RegionNode(1); |
kvn@2727 | 193 | register_new_node_with_optimizer(rgn); |
kvn@2727 | 194 | rgn->add_req(uncommon_proj); |
kvn@2727 | 195 | hash_delete(call); |
kvn@2727 | 196 | call->set_req(0, rgn); |
kvn@2727 | 197 | } else { |
kvn@2727 | 198 | // Find region's edge corresponding to uncommon_proj |
kvn@2727 | 199 | for (; proj_index < rgn->req(); proj_index++) |
kvn@2727 | 200 | if (rgn->in(proj_index) == uncommon_proj) break; |
kvn@2727 | 201 | assert(proj_index < rgn->req(), "sanity"); |
kvn@2727 | 202 | } |
kvn@2727 | 203 | |
kvn@2727 | 204 | // Create new_iff in new location. |
kvn@2727 | 205 | IfNode *new_iff = iff->clone()->as_If(); |
kvn@2727 | 206 | new_iff->set_req(0, new_entry); |
kvn@2727 | 207 | |
kvn@2727 | 208 | register_new_node_with_optimizer(new_iff); |
kvn@4115 | 209 | Node *if_cont = new (C) IfTrueNode(new_iff); |
kvn@4115 | 210 | Node *if_uct = new (C) IfFalseNode(new_iff); |
kvn@2727 | 211 | if (cont_proj->is_IfFalse()) { |
kvn@2727 | 212 | // Swap |
kvn@2727 | 213 | Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; |
kvn@2727 | 214 | } |
kvn@2727 | 215 | register_new_node_with_optimizer(if_cont); |
kvn@2727 | 216 | register_new_node_with_optimizer(if_uct); |
kvn@2727 | 217 | |
kvn@2727 | 218 | // if_uct to rgn |
kvn@2727 | 219 | hash_delete(rgn); |
kvn@2727 | 220 | rgn->add_req(if_uct); |
kvn@2727 | 221 | |
kvn@2727 | 222 | // If rgn has phis add corresponding new edges which has the same |
kvn@2727 | 223 | // value as on original uncommon_proj pass. |
kvn@2727 | 224 | assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last"); |
kvn@2727 | 225 | bool has_phi = false; |
kvn@2727 | 226 | for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) { |
kvn@2727 | 227 | Node* use = rgn->fast_out(i); |
kvn@2727 | 228 | if (use->is_Phi() && use->outcnt() > 0) { |
kvn@3847 | 229 | rehash_node_delayed(use); |
kvn@2727 | 230 | use->add_req(use->in(proj_index)); |
kvn@2727 | 231 | has_phi = true; |
kvn@2727 | 232 | } |
kvn@2727 | 233 | } |
kvn@2727 | 234 | assert(!has_phi || rgn->req() > 3, "no phis when region is created"); |
kvn@2727 | 235 | |
kvn@2727 | 236 | return if_cont->as_Proj(); |
kvn@2727 | 237 | } |
kvn@2727 | 238 | |
kvn@2727 | 239 | //--------------------------clone_predicate----------------------- |
kvn@2727 | 240 | ProjNode* PhaseIdealLoop::clone_predicate(ProjNode* predicate_proj, Node* new_entry, |
kvn@2727 | 241 | Deoptimization::DeoptReason reason, |
kvn@2727 | 242 | PhaseIdealLoop* loop_phase, |
kvn@2727 | 243 | PhaseIterGVN* igvn) { |
kvn@2727 | 244 | ProjNode* new_predicate_proj; |
kvn@2727 | 245 | if (loop_phase != NULL) { |
kvn@2727 | 246 | new_predicate_proj = loop_phase->create_new_if_for_predicate(predicate_proj, new_entry, reason); |
kvn@2727 | 247 | } else { |
kvn@2727 | 248 | new_predicate_proj = igvn->create_new_if_for_predicate(predicate_proj, new_entry, reason); |
kvn@2727 | 249 | } |
kvn@2727 | 250 | IfNode* iff = new_predicate_proj->in(0)->as_If(); |
kvn@2727 | 251 | Node* ctrl = iff->in(0); |
kvn@2727 | 252 | |
kvn@2727 | 253 | // Match original condition since predicate's projections could be swapped. |
kvn@2727 | 254 | assert(predicate_proj->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be"); |
kvn@4115 | 255 | Node* opq = new (igvn->C) Opaque1Node(igvn->C, predicate_proj->in(0)->in(1)->in(1)->in(1)); |
kvn@2727 | 256 | igvn->C->add_predicate_opaq(opq); |
kvn@2727 | 257 | |
kvn@4115 | 258 | Node* bol = new (igvn->C) Conv2BNode(opq); |
kvn@2727 | 259 | if (loop_phase != NULL) { |
kvn@2727 | 260 | loop_phase->register_new_node(opq, ctrl); |
kvn@2727 | 261 | loop_phase->register_new_node(bol, ctrl); |
kvn@2727 | 262 | } else { |
kvn@2727 | 263 | igvn->register_new_node_with_optimizer(opq); |
kvn@2727 | 264 | igvn->register_new_node_with_optimizer(bol); |
kvn@2727 | 265 | } |
kvn@2727 | 266 | igvn->hash_delete(iff); |
kvn@2727 | 267 | iff->set_req(1, bol); |
kvn@2727 | 268 | return new_predicate_proj; |
kvn@2727 | 269 | } |
kvn@2727 | 270 | |
kvn@2727 | 271 | |
kvn@2727 | 272 | //--------------------------clone_loop_predicates----------------------- |
kvn@2727 | 273 | // Interface from IGVN |
kvn@2877 | 274 | Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { |
kvn@3043 | 275 | return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, clone_limit_check, NULL, this); |
kvn@2727 | 276 | } |
kvn@2727 | 277 | |
kvn@2727 | 278 | // Interface from PhaseIdealLoop |
kvn@2877 | 279 | Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { |
kvn@3043 | 280 | return clone_loop_predicates(old_entry, new_entry, clone_limit_check, this, &this->_igvn); |
kvn@2727 | 281 | } |
kvn@2727 | 282 | |
kvn@2727 | 283 | // Clone loop predicates to cloned loops (peeled, unswitched, split_if). |
kvn@2727 | 284 | Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, |
kvn@2877 | 285 | bool clone_limit_check, |
kvn@2727 | 286 | PhaseIdealLoop* loop_phase, |
kvn@2727 | 287 | PhaseIterGVN* igvn) { |
kvn@2727 | 288 | #ifdef ASSERT |
kvn@2727 | 289 | if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) { |
kvn@2727 | 290 | if (new_entry != NULL) |
kvn@2727 | 291 | new_entry->dump(); |
kvn@2727 | 292 | assert(false, "not IfTrue, IfFalse, Region or SafePoint"); |
kvn@2727 | 293 | } |
kvn@2727 | 294 | #endif |
kvn@2727 | 295 | // Search original predicates |
kvn@2727 | 296 | Node* entry = old_entry; |
kvn@2877 | 297 | ProjNode* limit_check_proj = NULL; |
kvn@2877 | 298 | if (LoopLimitCheck) { |
kvn@2877 | 299 | limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); |
kvn@2877 | 300 | if (limit_check_proj != NULL) { |
kvn@2877 | 301 | entry = entry->in(0)->in(0); |
kvn@2877 | 302 | } |
kvn@2877 | 303 | } |
kvn@2727 | 304 | if (UseLoopPredicate) { |
kvn@2727 | 305 | ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); |
kvn@2727 | 306 | if (predicate_proj != NULL) { // right pattern that can be used by loop predication |
kvn@3043 | 307 | // clone predicate |
kvn@3043 | 308 | new_entry = clone_predicate(predicate_proj, new_entry, |
kvn@3043 | 309 | Deoptimization::Reason_predicate, |
kvn@3043 | 310 | loop_phase, igvn); |
kvn@3043 | 311 | assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate"); |
kvn@2727 | 312 | if (TraceLoopPredicate) { |
kvn@3043 | 313 | tty->print("Loop Predicate cloned: "); |
kvn@2727 | 314 | debug_only( new_entry->in(0)->dump(); ) |
kvn@2727 | 315 | } |
kvn@2727 | 316 | } |
kvn@2727 | 317 | } |
kvn@2877 | 318 | if (limit_check_proj != NULL && clone_limit_check) { |
kvn@2877 | 319 | // Clone loop limit check last to insert it before loop. |
kvn@2877 | 320 | // Don't clone a limit check which was already finalized |
kvn@2877 | 321 | // for this counted loop (only one limit check is needed). |
kvn@3043 | 322 | new_entry = clone_predicate(limit_check_proj, new_entry, |
kvn@3043 | 323 | Deoptimization::Reason_loop_limit_check, |
kvn@3043 | 324 | loop_phase, igvn); |
kvn@3043 | 325 | assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check"); |
kvn@2877 | 326 | if (TraceLoopLimitCheck) { |
kvn@3043 | 327 | tty->print("Loop Limit Check cloned: "); |
kvn@2877 | 328 | debug_only( new_entry->in(0)->dump(); ) |
kvn@2877 | 329 | } |
kvn@2877 | 330 | } |
kvn@2727 | 331 | return new_entry; |
kvn@2727 | 332 | } |
kvn@2727 | 333 | |
kvn@2727 | 334 | //--------------------------skip_loop_predicates------------------------------ |
kvn@2727 | 335 | // Skip related predicates. |
kvn@2727 | 336 | Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) { |
kvn@2727 | 337 | Node* predicate = NULL; |
kvn@2877 | 338 | if (LoopLimitCheck) { |
kvn@2877 | 339 | predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); |
kvn@2877 | 340 | if (predicate != NULL) { |
kvn@2877 | 341 | entry = entry->in(0)->in(0); |
kvn@2877 | 342 | } |
kvn@2877 | 343 | } |
kvn@2727 | 344 | if (UseLoopPredicate) { |
kvn@2727 | 345 | predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); |
kvn@2727 | 346 | if (predicate != NULL) { // right pattern that can be used by loop predication |
kvn@2727 | 347 | IfNode* iff = entry->in(0)->as_If(); |
kvn@2727 | 348 | ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con); |
kvn@2727 | 349 | Node* rgn = uncommon_proj->unique_ctrl_out(); |
kvn@2727 | 350 | assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); |
kvn@2727 | 351 | entry = entry->in(0)->in(0); |
kvn@2727 | 352 | while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) { |
kvn@2727 | 353 | uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con); |
kvn@2727 | 354 | if (uncommon_proj->unique_ctrl_out() != rgn) |
kvn@2727 | 355 | break; |
kvn@2727 | 356 | entry = entry->in(0)->in(0); |
kvn@2727 | 357 | } |
kvn@2727 | 358 | } |
kvn@2727 | 359 | } |
kvn@2727 | 360 | return entry; |
kvn@2727 | 361 | } |
kvn@2727 | 362 | |
kvn@2727 | 363 | //--------------------------find_predicate_insertion_point------------------- |
kvn@2727 | 364 | // Find a good location to insert a predicate |
kvn@2727 | 365 | ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) { |
kvn@2727 | 366 | if (start_c == NULL || !start_c->is_Proj()) |
kvn@2727 | 367 | return NULL; |
roland@5981 | 368 | if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) { |
kvn@2727 | 369 | return start_c->as_Proj(); |
kvn@2727 | 370 | } |
kvn@2727 | 371 | return NULL; |
kvn@2727 | 372 | } |
kvn@2727 | 373 | |
kvn@2727 | 374 | //--------------------------find_predicate------------------------------------ |
kvn@2727 | 375 | // Find a predicate |
kvn@2727 | 376 | Node* PhaseIdealLoop::find_predicate(Node* entry) { |
kvn@2727 | 377 | Node* predicate = NULL; |
kvn@2877 | 378 | if (LoopLimitCheck) { |
kvn@2877 | 379 | predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); |
kvn@2877 | 380 | if (predicate != NULL) { // right pattern that can be used by loop predication |
kvn@2877 | 381 | return entry; |
kvn@2877 | 382 | } |
kvn@2877 | 383 | } |
kvn@2727 | 384 | if (UseLoopPredicate) { |
kvn@2727 | 385 | predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); |
kvn@2727 | 386 | if (predicate != NULL) { // right pattern that can be used by loop predication |
kvn@2727 | 387 | return entry; |
kvn@2727 | 388 | } |
kvn@2727 | 389 | } |
kvn@2727 | 390 | return NULL; |
kvn@2727 | 391 | } |
kvn@2727 | 392 | |
kvn@2727 | 393 | //------------------------------Invariance----------------------------------- |
kvn@2727 | 394 | // Helper class for loop_predication_impl to compute invariance on the fly and |
kvn@2727 | 395 | // clone invariants. |
kvn@2727 | 396 | class Invariance : public StackObj { |
kvn@2727 | 397 | VectorSet _visited, _invariant; |
kvn@2727 | 398 | Node_Stack _stack; |
kvn@2727 | 399 | VectorSet _clone_visited; |
kvn@2727 | 400 | Node_List _old_new; // map of old to new (clone) |
kvn@2727 | 401 | IdealLoopTree* _lpt; |
kvn@2727 | 402 | PhaseIdealLoop* _phase; |
kvn@2727 | 403 | |
kvn@2727 | 404 | // Helper function to set up the invariance for invariance computation |
kvn@2727 | 405 | // If n is a known invariant, set up directly. Otherwise, look up the |
kvn@2727 | 406 | // the possibility to push n onto the stack for further processing. |
kvn@2727 | 407 | void visit(Node* use, Node* n) { |
kvn@2727 | 408 | if (_lpt->is_invariant(n)) { // known invariant |
kvn@2727 | 409 | _invariant.set(n->_idx); |
kvn@2727 | 410 | } else if (!n->is_CFG()) { |
kvn@2727 | 411 | Node *n_ctrl = _phase->ctrl_or_self(n); |
kvn@2727 | 412 | Node *u_ctrl = _phase->ctrl_or_self(use); // self if use is a CFG |
kvn@2727 | 413 | if (_phase->is_dominator(n_ctrl, u_ctrl)) { |
kvn@2727 | 414 | _stack.push(n, n->in(0) == NULL ? 1 : 0); |
kvn@2727 | 415 | } |
kvn@2727 | 416 | } |
kvn@2727 | 417 | } |
kvn@2727 | 418 | |
kvn@2727 | 419 | // Compute invariance for "the_node" and (possibly) all its inputs recursively |
kvn@2727 | 420 | // on the fly |
kvn@2727 | 421 | void compute_invariance(Node* n) { |
kvn@2727 | 422 | assert(_visited.test(n->_idx), "must be"); |
kvn@2727 | 423 | visit(n, n); |
kvn@2727 | 424 | while (_stack.is_nonempty()) { |
kvn@2727 | 425 | Node* n = _stack.node(); |
kvn@2727 | 426 | uint idx = _stack.index(); |
kvn@2727 | 427 | if (idx == n->req()) { // all inputs are processed |
kvn@2727 | 428 | _stack.pop(); |
kvn@2727 | 429 | // n is invariant if it's inputs are all invariant |
kvn@2727 | 430 | bool all_inputs_invariant = true; |
kvn@2727 | 431 | for (uint i = 0; i < n->req(); i++) { |
kvn@2727 | 432 | Node* in = n->in(i); |
kvn@2727 | 433 | if (in == NULL) continue; |
kvn@2727 | 434 | assert(_visited.test(in->_idx), "must have visited input"); |
kvn@2727 | 435 | if (!_invariant.test(in->_idx)) { // bad guy |
kvn@2727 | 436 | all_inputs_invariant = false; |
kvn@2727 | 437 | break; |
kvn@2727 | 438 | } |
kvn@2727 | 439 | } |
kvn@2727 | 440 | if (all_inputs_invariant) { |
kvn@2727 | 441 | _invariant.set(n->_idx); // I am a invariant too |
kvn@2727 | 442 | } |
kvn@2727 | 443 | } else { // process next input |
kvn@2727 | 444 | _stack.set_index(idx + 1); |
kvn@2727 | 445 | Node* m = n->in(idx); |
kvn@2727 | 446 | if (m != NULL && !_visited.test_set(m->_idx)) { |
kvn@2727 | 447 | visit(n, m); |
kvn@2727 | 448 | } |
kvn@2727 | 449 | } |
kvn@2727 | 450 | } |
kvn@2727 | 451 | } |
kvn@2727 | 452 | |
kvn@2727 | 453 | // Helper function to set up _old_new map for clone_nodes. |
kvn@2727 | 454 | // If n is a known invariant, set up directly ("clone" of n == n). |
kvn@2727 | 455 | // Otherwise, push n onto the stack for real cloning. |
kvn@2727 | 456 | void clone_visit(Node* n) { |
kvn@2727 | 457 | assert(_invariant.test(n->_idx), "must be invariant"); |
kvn@2727 | 458 | if (_lpt->is_invariant(n)) { // known invariant |
kvn@2727 | 459 | _old_new.map(n->_idx, n); |
kvn@2727 | 460 | } else { // to be cloned |
kvn@2727 | 461 | assert(!n->is_CFG(), "should not see CFG here"); |
kvn@2727 | 462 | _stack.push(n, n->in(0) == NULL ? 1 : 0); |
kvn@2727 | 463 | } |
kvn@2727 | 464 | } |
kvn@2727 | 465 | |
kvn@2727 | 466 | // Clone "n" and (possibly) all its inputs recursively |
kvn@2727 | 467 | void clone_nodes(Node* n, Node* ctrl) { |
kvn@2727 | 468 | clone_visit(n); |
kvn@2727 | 469 | while (_stack.is_nonempty()) { |
kvn@2727 | 470 | Node* n = _stack.node(); |
kvn@2727 | 471 | uint idx = _stack.index(); |
kvn@2727 | 472 | if (idx == n->req()) { // all inputs processed, clone n! |
kvn@2727 | 473 | _stack.pop(); |
kvn@2727 | 474 | // clone invariant node |
kvn@2727 | 475 | Node* n_cl = n->clone(); |
kvn@2727 | 476 | _old_new.map(n->_idx, n_cl); |
kvn@2727 | 477 | _phase->register_new_node(n_cl, ctrl); |
kvn@2727 | 478 | for (uint i = 0; i < n->req(); i++) { |
kvn@2727 | 479 | Node* in = n_cl->in(i); |
kvn@2727 | 480 | if (in == NULL) continue; |
kvn@2727 | 481 | n_cl->set_req(i, _old_new[in->_idx]); |
kvn@2727 | 482 | } |
kvn@2727 | 483 | } else { // process next input |
kvn@2727 | 484 | _stack.set_index(idx + 1); |
kvn@2727 | 485 | Node* m = n->in(idx); |
kvn@2727 | 486 | if (m != NULL && !_clone_visited.test_set(m->_idx)) { |
kvn@2727 | 487 | clone_visit(m); // visit the input |
kvn@2727 | 488 | } |
kvn@2727 | 489 | } |
kvn@2727 | 490 | } |
kvn@2727 | 491 | } |
kvn@2727 | 492 | |
kvn@2727 | 493 | public: |
kvn@2727 | 494 | Invariance(Arena* area, IdealLoopTree* lpt) : |
kvn@2727 | 495 | _lpt(lpt), _phase(lpt->_phase), |
kvn@2727 | 496 | _visited(area), _invariant(area), _stack(area, 10 /* guess */), |
kvn@2727 | 497 | _clone_visited(area), _old_new(area) |
kvn@2727 | 498 | {} |
kvn@2727 | 499 | |
kvn@2727 | 500 | // Map old to n for invariance computation and clone |
kvn@2727 | 501 | void map_ctrl(Node* old, Node* n) { |
kvn@2727 | 502 | assert(old->is_CFG() && n->is_CFG(), "must be"); |
kvn@2727 | 503 | _old_new.map(old->_idx, n); // "clone" of old is n |
kvn@2727 | 504 | _invariant.set(old->_idx); // old is invariant |
kvn@2727 | 505 | _clone_visited.set(old->_idx); |
kvn@2727 | 506 | } |
kvn@2727 | 507 | |
kvn@2727 | 508 | // Driver function to compute invariance |
kvn@2727 | 509 | bool is_invariant(Node* n) { |
kvn@2727 | 510 | if (!_visited.test_set(n->_idx)) |
kvn@2727 | 511 | compute_invariance(n); |
kvn@2727 | 512 | return (_invariant.test(n->_idx) != 0); |
kvn@2727 | 513 | } |
kvn@2727 | 514 | |
kvn@2727 | 515 | // Driver function to clone invariant |
kvn@2727 | 516 | Node* clone(Node* n, Node* ctrl) { |
kvn@2727 | 517 | assert(ctrl->is_CFG(), "must be"); |
kvn@2727 | 518 | assert(_invariant.test(n->_idx), "must be an invariant"); |
kvn@2727 | 519 | if (!_clone_visited.test(n->_idx)) |
kvn@2727 | 520 | clone_nodes(n, ctrl); |
kvn@2727 | 521 | return _old_new[n->_idx]; |
kvn@2727 | 522 | } |
kvn@2727 | 523 | }; |
kvn@2727 | 524 | |
kvn@2727 | 525 | //------------------------------is_range_check_if ----------------------------------- |
kvn@2727 | 526 | // Returns true if the predicate of iff is in "scale*iv + offset u< load_range(ptr)" format |
kvn@2727 | 527 | // Note: this function is particularly designed for loop predication. We require load_range |
kvn@2727 | 528 | // and offset to be loop invariant computed on the fly by "invar" |
kvn@2727 | 529 | bool IdealLoopTree::is_range_check_if(IfNode *iff, PhaseIdealLoop *phase, Invariance& invar) const { |
kvn@2727 | 530 | if (!is_loop_exit(iff)) { |
kvn@2727 | 531 | return false; |
kvn@2727 | 532 | } |
kvn@2727 | 533 | if (!iff->in(1)->is_Bool()) { |
kvn@2727 | 534 | return false; |
kvn@2727 | 535 | } |
kvn@2727 | 536 | const BoolNode *bol = iff->in(1)->as_Bool(); |
kvn@2727 | 537 | if (bol->_test._test != BoolTest::lt) { |
kvn@2727 | 538 | return false; |
kvn@2727 | 539 | } |
kvn@2727 | 540 | if (!bol->in(1)->is_Cmp()) { |
kvn@2727 | 541 | return false; |
kvn@2727 | 542 | } |
kvn@2727 | 543 | const CmpNode *cmp = bol->in(1)->as_Cmp(); |
kvn@2727 | 544 | if (cmp->Opcode() != Op_CmpU) { |
kvn@2727 | 545 | return false; |
kvn@2727 | 546 | } |
kvn@2727 | 547 | Node* range = cmp->in(2); |
kvn@2727 | 548 | if (range->Opcode() != Op_LoadRange) { |
kvn@2727 | 549 | const TypeInt* tint = phase->_igvn.type(range)->isa_int(); |
kvn@2877 | 550 | if (tint == NULL || tint->empty() || tint->_lo < 0) { |
kvn@2727 | 551 | // Allow predication on positive values that aren't LoadRanges. |
kvn@2727 | 552 | // This allows optimization of loops where the length of the |
kvn@2727 | 553 | // array is a known value and doesn't need to be loaded back |
kvn@2727 | 554 | // from the array. |
kvn@2727 | 555 | return false; |
kvn@2727 | 556 | } |
kvn@2727 | 557 | } |
kvn@2727 | 558 | if (!invar.is_invariant(range)) { |
kvn@2727 | 559 | return false; |
kvn@2727 | 560 | } |
kvn@2727 | 561 | Node *iv = _head->as_CountedLoop()->phi(); |
kvn@2727 | 562 | int scale = 0; |
kvn@2727 | 563 | Node *offset = NULL; |
kvn@2727 | 564 | if (!phase->is_scaled_iv_plus_offset(cmp->in(1), iv, &scale, &offset)) { |
kvn@2727 | 565 | return false; |
kvn@2727 | 566 | } |
kvn@2727 | 567 | if (offset && !invar.is_invariant(offset)) { // offset must be invariant |
kvn@2727 | 568 | return false; |
kvn@2727 | 569 | } |
kvn@2727 | 570 | return true; |
kvn@2727 | 571 | } |
kvn@2727 | 572 | |
kvn@2727 | 573 | //------------------------------rc_predicate----------------------------------- |
kvn@2727 | 574 | // Create a range check predicate |
kvn@2727 | 575 | // |
kvn@2727 | 576 | // for (i = init; i < limit; i += stride) { |
kvn@2727 | 577 | // a[scale*i+offset] |
kvn@2727 | 578 | // } |
kvn@2727 | 579 | // |
kvn@2727 | 580 | // Compute max(scale*i + offset) for init <= i < limit and build the predicate |
kvn@2727 | 581 | // as "max(scale*i + offset) u< a.length". |
kvn@2727 | 582 | // |
kvn@2727 | 583 | // There are two cases for max(scale*i + offset): |
kvn@2727 | 584 | // (1) stride*scale > 0 |
kvn@2727 | 585 | // max(scale*i + offset) = scale*(limit-stride) + offset |
kvn@2727 | 586 | // (2) stride*scale < 0 |
kvn@2727 | 587 | // max(scale*i + offset) = scale*init + offset |
kvn@2877 | 588 | BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl, |
kvn@2727 | 589 | int scale, Node* offset, |
kvn@2727 | 590 | Node* init, Node* limit, Node* stride, |
kvn@2727 | 591 | Node* range, bool upper) { |
never@2868 | 592 | stringStream* predString = NULL; |
never@2868 | 593 | if (TraceLoopPredicate) { |
never@2868 | 594 | predString = new stringStream(); |
never@2868 | 595 | predString->print("rc_predicate "); |
never@2868 | 596 | } |
kvn@2727 | 597 | |
kvn@2727 | 598 | Node* max_idx_expr = init; |
kvn@2727 | 599 | int stride_con = stride->get_int(); |
kvn@2727 | 600 | if ((stride_con > 0) == (scale > 0) == upper) { |
kvn@2877 | 601 | if (LoopLimitCheck) { |
kvn@2877 | 602 | // With LoopLimitCheck limit is not exact. |
kvn@2877 | 603 | // Calculate exact limit here. |
kvn@2877 | 604 | // Note, counted loop's test is '<' or '>'. |
kvn@2877 | 605 | limit = exact_limit(loop); |
kvn@4115 | 606 | max_idx_expr = new (C) SubINode(limit, stride); |
kvn@2877 | 607 | register_new_node(max_idx_expr, ctrl); |
kvn@2877 | 608 | if (TraceLoopPredicate) predString->print("(limit - stride) "); |
kvn@2877 | 609 | } else { |
kvn@4115 | 610 | max_idx_expr = new (C) SubINode(limit, stride); |
kvn@2877 | 611 | register_new_node(max_idx_expr, ctrl); |
kvn@2877 | 612 | if (TraceLoopPredicate) predString->print("(limit - stride) "); |
kvn@2877 | 613 | } |
kvn@2727 | 614 | } else { |
never@2868 | 615 | if (TraceLoopPredicate) predString->print("init "); |
kvn@2727 | 616 | } |
kvn@2727 | 617 | |
kvn@2727 | 618 | if (scale != 1) { |
kvn@2727 | 619 | ConNode* con_scale = _igvn.intcon(scale); |
kvn@4115 | 620 | max_idx_expr = new (C) MulINode(max_idx_expr, con_scale); |
kvn@2727 | 621 | register_new_node(max_idx_expr, ctrl); |
never@2868 | 622 | if (TraceLoopPredicate) predString->print("* %d ", scale); |
kvn@2727 | 623 | } |
kvn@2727 | 624 | |
kvn@2727 | 625 | if (offset && (!offset->is_Con() || offset->get_int() != 0)){ |
kvn@4115 | 626 | max_idx_expr = new (C) AddINode(max_idx_expr, offset); |
kvn@2727 | 627 | register_new_node(max_idx_expr, ctrl); |
kvn@2727 | 628 | if (TraceLoopPredicate) |
never@2868 | 629 | if (offset->is_Con()) predString->print("+ %d ", offset->get_int()); |
never@2868 | 630 | else predString->print("+ offset "); |
kvn@2727 | 631 | } |
kvn@2727 | 632 | |
kvn@4115 | 633 | CmpUNode* cmp = new (C) CmpUNode(max_idx_expr, range); |
kvn@2727 | 634 | register_new_node(cmp, ctrl); |
kvn@4115 | 635 | BoolNode* bol = new (C) BoolNode(cmp, BoolTest::lt); |
kvn@2727 | 636 | register_new_node(bol, ctrl); |
kvn@2727 | 637 | |
never@2868 | 638 | if (TraceLoopPredicate) { |
never@2868 | 639 | predString->print_cr("<u range"); |
drchase@6680 | 640 | tty->print("%s", predString->as_string()); |
never@2868 | 641 | } |
kvn@2727 | 642 | return bol; |
kvn@2727 | 643 | } |
kvn@2727 | 644 | |
kvn@2727 | 645 | //------------------------------ loop_predication_impl-------------------------- |
kvn@2727 | 646 | // Insert loop predicates for null checks and range checks |
kvn@2727 | 647 | bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) { |
kvn@2727 | 648 | if (!UseLoopPredicate) return false; |
kvn@2727 | 649 | |
kvn@2727 | 650 | if (!loop->_head->is_Loop()) { |
kvn@2727 | 651 | // Could be a simple region when irreducible loops are present. |
kvn@2727 | 652 | return false; |
kvn@2727 | 653 | } |
kvn@2877 | 654 | LoopNode* head = loop->_head->as_Loop(); |
kvn@2727 | 655 | |
kvn@2877 | 656 | if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) { |
kvn@2727 | 657 | // do nothing for infinite loops |
kvn@2727 | 658 | return false; |
kvn@2727 | 659 | } |
kvn@2727 | 660 | |
kvn@2727 | 661 | CountedLoopNode *cl = NULL; |
kvn@3048 | 662 | if (head->is_valid_counted_loop()) { |
kvn@2877 | 663 | cl = head->as_CountedLoop(); |
kvn@2727 | 664 | // do nothing for iteration-splitted loops |
kvn@2727 | 665 | if (!cl->is_normal_loop()) return false; |
kvn@3038 | 666 | // Avoid RCE if Counted loop's test is '!='. |
kvn@3038 | 667 | BoolTest::mask bt = cl->loopexit()->test_trip(); |
kvn@3038 | 668 | if (bt != BoolTest::lt && bt != BoolTest::gt) |
kvn@3038 | 669 | cl = NULL; |
kvn@2727 | 670 | } |
kvn@2727 | 671 | |
kvn@2877 | 672 | Node* entry = head->in(LoopNode::EntryControl); |
kvn@2877 | 673 | ProjNode *predicate_proj = NULL; |
kvn@2877 | 674 | // Loop limit check predicate should be near the loop. |
kvn@2877 | 675 | if (LoopLimitCheck) { |
kvn@2877 | 676 | predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); |
kvn@2877 | 677 | if (predicate_proj != NULL) |
kvn@2877 | 678 | entry = predicate_proj->in(0)->in(0); |
kvn@2877 | 679 | } |
kvn@2727 | 680 | |
kvn@2877 | 681 | predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); |
kvn@2727 | 682 | if (!predicate_proj) { |
kvn@2727 | 683 | #ifndef PRODUCT |
kvn@2727 | 684 | if (TraceLoopPredicate) { |
kvn@2727 | 685 | tty->print("missing predicate:"); |
kvn@2727 | 686 | loop->dump_head(); |
kvn@2877 | 687 | head->dump(1); |
kvn@2727 | 688 | } |
kvn@2727 | 689 | #endif |
kvn@2727 | 690 | return false; |
kvn@2727 | 691 | } |
kvn@2727 | 692 | ConNode* zero = _igvn.intcon(0); |
kvn@2727 | 693 | set_ctrl(zero, C->root()); |
kvn@2727 | 694 | |
kvn@2727 | 695 | ResourceArea *area = Thread::current()->resource_area(); |
kvn@2727 | 696 | Invariance invar(area, loop); |
kvn@2727 | 697 | |
kvn@2727 | 698 | // Create list of if-projs such that a newer proj dominates all older |
kvn@2727 | 699 | // projs in the list, and they all dominate loop->tail() |
kvn@2727 | 700 | Node_List if_proj_list(area); |
kvn@2727 | 701 | Node *current_proj = loop->tail(); //start from tail |
kvn@2727 | 702 | while (current_proj != head) { |
kvn@2727 | 703 | if (loop == get_loop(current_proj) && // still in the loop ? |
kvn@2727 | 704 | current_proj->is_Proj() && // is a projection ? |
kvn@2727 | 705 | current_proj->in(0)->Opcode() == Op_If) { // is a if projection ? |
kvn@2727 | 706 | if_proj_list.push(current_proj); |
kvn@2727 | 707 | } |
kvn@2727 | 708 | current_proj = idom(current_proj); |
kvn@2727 | 709 | } |
kvn@2727 | 710 | |
kvn@2727 | 711 | bool hoisted = false; // true if at least one proj is promoted |
kvn@2727 | 712 | while (if_proj_list.size() > 0) { |
kvn@2727 | 713 | // Following are changed to nonnull when a predicate can be hoisted |
kvn@2727 | 714 | ProjNode* new_predicate_proj = NULL; |
kvn@2727 | 715 | |
kvn@2727 | 716 | ProjNode* proj = if_proj_list.pop()->as_Proj(); |
kvn@2727 | 717 | IfNode* iff = proj->in(0)->as_If(); |
kvn@2727 | 718 | |
roland@5981 | 719 | if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) { |
kvn@2727 | 720 | if (loop->is_loop_exit(iff)) { |
kvn@2727 | 721 | // stop processing the remaining projs in the list because the execution of them |
kvn@2727 | 722 | // depends on the condition of "iff" (iff->in(1)). |
kvn@2727 | 723 | break; |
kvn@2727 | 724 | } else { |
kvn@2727 | 725 | // Both arms are inside the loop. There are two cases: |
kvn@2727 | 726 | // (1) there is one backward branch. In this case, any remaining proj |
kvn@2727 | 727 | // in the if_proj list post-dominates "iff". So, the condition of "iff" |
kvn@2727 | 728 | // does not determine the execution the remining projs directly, and we |
kvn@2727 | 729 | // can safely continue. |
kvn@2727 | 730 | // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj" |
kvn@2727 | 731 | // does not dominate loop->tail(), so it can not be in the if_proj list. |
kvn@2727 | 732 | continue; |
kvn@2727 | 733 | } |
kvn@2727 | 734 | } |
kvn@2727 | 735 | |
kvn@2727 | 736 | Node* test = iff->in(1); |
kvn@2727 | 737 | if (!test->is_Bool()){ //Conv2B, ... |
kvn@2727 | 738 | continue; |
kvn@2727 | 739 | } |
kvn@2727 | 740 | BoolNode* bol = test->as_Bool(); |
kvn@2727 | 741 | if (invar.is_invariant(bol)) { |
kvn@2727 | 742 | // Invariant test |
kvn@2727 | 743 | new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL, |
kvn@2727 | 744 | Deoptimization::Reason_predicate); |
kvn@2727 | 745 | Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0); |
kvn@2727 | 746 | BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool(); |
kvn@2727 | 747 | |
kvn@2727 | 748 | // Negate test if necessary |
kvn@2727 | 749 | bool negated = false; |
kvn@2727 | 750 | if (proj->_con != predicate_proj->_con) { |
kvn@4115 | 751 | new_predicate_bol = new (C) BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate()); |
kvn@2727 | 752 | register_new_node(new_predicate_bol, ctrl); |
kvn@2727 | 753 | negated = true; |
kvn@2727 | 754 | } |
kvn@2727 | 755 | IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If(); |
kvn@2727 | 756 | _igvn.hash_delete(new_predicate_iff); |
kvn@2727 | 757 | new_predicate_iff->set_req(1, new_predicate_bol); |
kvn@2727 | 758 | #ifndef PRODUCT |
kvn@2727 | 759 | if (TraceLoopPredicate) { |
kvn@2727 | 760 | tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx); |
kvn@2727 | 761 | loop->dump_head(); |
kvn@2727 | 762 | } else if (TraceLoopOpts) { |
kvn@2727 | 763 | tty->print("Predicate IC "); |
kvn@2727 | 764 | loop->dump_head(); |
kvn@2727 | 765 | } |
kvn@2727 | 766 | #endif |
kvn@5110 | 767 | } else if ((cl != NULL) && (proj->_con == predicate_proj->_con) && |
kvn@5110 | 768 | loop->is_range_check_if(iff, this, invar)) { |
kvn@2727 | 769 | |
kvn@2727 | 770 | // Range check for counted loops |
kvn@2727 | 771 | const Node* cmp = bol->in(1)->as_Cmp(); |
kvn@2727 | 772 | Node* idx = cmp->in(1); |
kvn@2727 | 773 | assert(!invar.is_invariant(idx), "index is variant"); |
kvn@2727 | 774 | Node* rng = cmp->in(2); |
kvn@2877 | 775 | assert(rng->Opcode() == Op_LoadRange || _igvn.type(rng)->is_int() >= 0, "must be"); |
kvn@2727 | 776 | assert(invar.is_invariant(rng), "range must be invariant"); |
kvn@2727 | 777 | int scale = 1; |
kvn@2727 | 778 | Node* offset = zero; |
kvn@2727 | 779 | bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset); |
kvn@2727 | 780 | assert(ok, "must be index expression"); |
kvn@2727 | 781 | |
kvn@2727 | 782 | Node* init = cl->init_trip(); |
kvn@2727 | 783 | Node* limit = cl->limit(); |
kvn@2727 | 784 | Node* stride = cl->stride(); |
kvn@2727 | 785 | |
kvn@2727 | 786 | // Build if's for the upper and lower bound tests. The |
kvn@2727 | 787 | // lower_bound test will dominate the upper bound test and all |
kvn@2727 | 788 | // cloned or created nodes will use the lower bound test as |
kvn@2727 | 789 | // their declared control. |
kvn@2727 | 790 | ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); |
kvn@2727 | 791 | ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); |
kvn@2727 | 792 | assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate"); |
kvn@2727 | 793 | Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0); |
kvn@2727 | 794 | |
kvn@2727 | 795 | // Perform cloning to keep Invariance state correct since the |
kvn@2727 | 796 | // late schedule will place invariant things in the loop. |
kvn@2727 | 797 | rng = invar.clone(rng, ctrl); |
kvn@2727 | 798 | if (offset && offset != zero) { |
kvn@2727 | 799 | assert(invar.is_invariant(offset), "offset must be loop invariant"); |
kvn@2727 | 800 | offset = invar.clone(offset, ctrl); |
kvn@2727 | 801 | } |
kvn@2727 | 802 | |
kvn@2727 | 803 | // Test the lower bound |
kvn@2877 | 804 | Node* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false); |
kvn@2727 | 805 | IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If(); |
kvn@2727 | 806 | _igvn.hash_delete(lower_bound_iff); |
kvn@2727 | 807 | lower_bound_iff->set_req(1, lower_bound_bol); |
kvn@2727 | 808 | if (TraceLoopPredicate) tty->print_cr("lower bound check if: %d", lower_bound_iff->_idx); |
kvn@2727 | 809 | |
kvn@2727 | 810 | // Test the upper bound |
kvn@3038 | 811 | Node* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true); |
kvn@2727 | 812 | IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If(); |
kvn@2727 | 813 | _igvn.hash_delete(upper_bound_iff); |
kvn@2727 | 814 | upper_bound_iff->set_req(1, upper_bound_bol); |
kvn@2727 | 815 | if (TraceLoopPredicate) tty->print_cr("upper bound check if: %d", lower_bound_iff->_idx); |
kvn@2727 | 816 | |
kvn@2727 | 817 | // Fall through into rest of the clean up code which will move |
kvn@2727 | 818 | // any dependent nodes onto the upper bound test. |
kvn@2727 | 819 | new_predicate_proj = upper_bound_proj; |
kvn@2727 | 820 | |
kvn@2727 | 821 | #ifndef PRODUCT |
kvn@2727 | 822 | if (TraceLoopOpts && !TraceLoopPredicate) { |
kvn@2727 | 823 | tty->print("Predicate RC "); |
kvn@2727 | 824 | loop->dump_head(); |
kvn@2727 | 825 | } |
kvn@2727 | 826 | #endif |
kvn@2727 | 827 | } else { |
kvn@2727 | 828 | // Loop variant check (for example, range check in non-counted loop) |
kvn@2727 | 829 | // with uncommon trap. |
kvn@2727 | 830 | continue; |
kvn@2727 | 831 | } |
kvn@2727 | 832 | assert(new_predicate_proj != NULL, "sanity"); |
kvn@2727 | 833 | // Success - attach condition (new_predicate_bol) to predicate if |
kvn@2727 | 834 | invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate |
kvn@2727 | 835 | |
kvn@2727 | 836 | // Eliminate the old If in the loop body |
kvn@2727 | 837 | dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con ); |
kvn@2727 | 838 | |
kvn@2727 | 839 | hoisted = true; |
kvn@2727 | 840 | C->set_major_progress(); |
kvn@2727 | 841 | } // end while |
kvn@2727 | 842 | |
kvn@2727 | 843 | #ifndef PRODUCT |
kvn@2727 | 844 | // report that the loop predication has been actually performed |
kvn@2727 | 845 | // for this loop |
kvn@2727 | 846 | if (TraceLoopPredicate && hoisted) { |
kvn@2727 | 847 | tty->print("Loop Predication Performed:"); |
kvn@2727 | 848 | loop->dump_head(); |
kvn@2727 | 849 | } |
kvn@2727 | 850 | #endif |
kvn@2727 | 851 | |
kvn@2727 | 852 | return hoisted; |
kvn@2727 | 853 | } |
kvn@2727 | 854 | |
kvn@2727 | 855 | //------------------------------loop_predication-------------------------------- |
kvn@2727 | 856 | // driver routine for loop predication optimization |
kvn@2727 | 857 | bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) { |
kvn@2727 | 858 | bool hoisted = false; |
kvn@2727 | 859 | // Recursively promote predicates |
kvn@2727 | 860 | if (_child) { |
kvn@2727 | 861 | hoisted = _child->loop_predication( phase); |
kvn@2727 | 862 | } |
kvn@2727 | 863 | |
kvn@2727 | 864 | // self |
kvn@2727 | 865 | if (!_irreducible && !tail()->is_top()) { |
kvn@2727 | 866 | hoisted |= phase->loop_predication_impl(this); |
kvn@2727 | 867 | } |
kvn@2727 | 868 | |
kvn@2727 | 869 | if (_next) { //sibling |
kvn@2727 | 870 | hoisted |= _next->loop_predication( phase); |
kvn@2727 | 871 | } |
kvn@2727 | 872 | |
kvn@2727 | 873 | return hoisted; |
kvn@2727 | 874 | } |