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