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