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