Mercurial > hg > truffle
annotate src/share/vm/opto/superword.cpp @ 452:00b023ae2d78
6722113: CMS: Incorrect overflow handling during precleaning of Reference lists
Summary: When we encounter marking stack overflow during precleaning of Reference lists, we were using the overflow list mechanism, which can cause problems on account of mutating the mark word of the header because of conflicts with mutator accesses and updates of that field. Instead we should use the usual mechanism for overflow handling in concurrent phases, namely dirtying of the card on which the overflowed object lies. Since precleaning effectively does a form of discovered list processing, albeit with discovery enabled, we needed to adjust some code to be correct in the face of interleaved processing and discovery.
Reviewed-by: apetrusenko, jcoomes
author | ysr |
---|---|
date | Thu, 20 Nov 2008 12:27:41 -0800 |
parents | b0fe4deeb9fb |
children | 3b5ac9e7e6ea |
rev | line source |
---|---|
0 | 1 /* |
196 | 2 * Copyright 2007-2008 Sun Microsystems, Inc. All Rights Reserved. |
0 | 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 */ | |
23 | |
24 #include "incls/_precompiled.incl" | |
25 #include "incls/_superword.cpp.incl" | |
26 | |
27 // | |
28 // S U P E R W O R D T R A N S F O R M | |
29 //============================================================================= | |
30 | |
31 //------------------------------SuperWord--------------------------- | |
32 SuperWord::SuperWord(PhaseIdealLoop* phase) : | |
33 _phase(phase), | |
34 _igvn(phase->_igvn), | |
35 _arena(phase->C->comp_arena()), | |
36 _packset(arena(), 8, 0, NULL), // packs for the current block | |
37 _bb_idx(arena(), (int)(1.10 * phase->C->unique()), 0, 0), // node idx to index in bb | |
38 _block(arena(), 8, 0, NULL), // nodes in current block | |
39 _data_entry(arena(), 8, 0, NULL), // nodes with all inputs from outside | |
40 _mem_slice_head(arena(), 8, 0, NULL), // memory slice heads | |
41 _mem_slice_tail(arena(), 8, 0, NULL), // memory slice tails | |
42 _node_info(arena(), 8, 0, SWNodeInfo::initial), // info needed per node | |
43 _align_to_ref(NULL), // memory reference to align vectors to | |
44 _disjoint_ptrs(arena(), 8, 0, OrderedPair::initial), // runtime disambiguated pointer pairs | |
45 _dg(_arena), // dependence graph | |
46 _visited(arena()), // visited node set | |
47 _post_visited(arena()), // post visited node set | |
48 _n_idx_list(arena(), 8), // scratch list of (node,index) pairs | |
49 _stk(arena(), 8, 0, NULL), // scratch stack of nodes | |
50 _nlist(arena(), 8, 0, NULL), // scratch list of nodes | |
51 _lpt(NULL), // loop tree node | |
52 _lp(NULL), // LoopNode | |
53 _bb(NULL), // basic block | |
54 _iv(NULL) // induction var | |
55 {} | |
56 | |
57 //------------------------------transform_loop--------------------------- | |
58 void SuperWord::transform_loop(IdealLoopTree* lpt) { | |
59 assert(lpt->_head->is_CountedLoop(), "must be"); | |
60 CountedLoopNode *cl = lpt->_head->as_CountedLoop(); | |
61 | |
62 if (!cl->is_main_loop() ) return; // skip normal, pre, and post loops | |
63 | |
64 // Check for no control flow in body (other than exit) | |
65 Node *cl_exit = cl->loopexit(); | |
66 if (cl_exit->in(0) != lpt->_head) return; | |
67 | |
105
a7d0f95410bd
6646020: assert(in_bb(n),"must be in block") in -Xcomp mode
never
parents:
72
diff
changeset
|
68 // Make sure the are no extra control users of the loop backedge |
a7d0f95410bd
6646020: assert(in_bb(n),"must be in block") in -Xcomp mode
never
parents:
72
diff
changeset
|
69 if (cl->back_control()->outcnt() != 1) { |
a7d0f95410bd
6646020: assert(in_bb(n),"must be in block") in -Xcomp mode
never
parents:
72
diff
changeset
|
70 return; |
a7d0f95410bd
6646020: assert(in_bb(n),"must be in block") in -Xcomp mode
never
parents:
72
diff
changeset
|
71 } |
a7d0f95410bd
6646020: assert(in_bb(n),"must be in block") in -Xcomp mode
never
parents:
72
diff
changeset
|
72 |
0 | 73 // Check for pre-loop ending with CountedLoopEnd(Bool(Cmp(x,Opaque1(limit)))) |
74 CountedLoopEndNode* pre_end = get_pre_loop_end(cl); | |
75 if (pre_end == NULL) return; | |
76 Node *pre_opaq1 = pre_end->limit(); | |
77 if (pre_opaq1->Opcode() != Op_Opaque1) return; | |
78 | |
79 // Do vectors exist on this architecture? | |
80 if (vector_width_in_bytes() == 0) return; | |
81 | |
82 init(); // initialize data structures | |
83 | |
84 set_lpt(lpt); | |
85 set_lp(cl); | |
86 | |
87 // For now, define one block which is the entire loop body | |
88 set_bb(cl); | |
89 | |
90 assert(_packset.length() == 0, "packset must be empty"); | |
91 SLP_extract(); | |
92 } | |
93 | |
94 //------------------------------SLP_extract--------------------------- | |
95 // Extract the superword level parallelism | |
96 // | |
97 // 1) A reverse post-order of nodes in the block is constructed. By scanning | |
98 // this list from first to last, all definitions are visited before their uses. | |
99 // | |
100 // 2) A point-to-point dependence graph is constructed between memory references. | |
101 // This simplies the upcoming "independence" checker. | |
102 // | |
103 // 3) The maximum depth in the node graph from the beginning of the block | |
104 // to each node is computed. This is used to prune the graph search | |
105 // in the independence checker. | |
106 // | |
107 // 4) For integer types, the necessary bit width is propagated backwards | |
108 // from stores to allow packed operations on byte, char, and short | |
109 // integers. This reverses the promotion to type "int" that javac | |
110 // did for operations like: char c1,c2,c3; c1 = c2 + c3. | |
111 // | |
112 // 5) One of the memory references is picked to be an aligned vector reference. | |
113 // The pre-loop trip count is adjusted to align this reference in the | |
114 // unrolled body. | |
115 // | |
116 // 6) The initial set of pack pairs is seeded with memory references. | |
117 // | |
118 // 7) The set of pack pairs is extended by following use->def and def->use links. | |
119 // | |
120 // 8) The pairs are combined into vector sized packs. | |
121 // | |
122 // 9) Reorder the memory slices to co-locate members of the memory packs. | |
123 // | |
124 // 10) Generate ideal vector nodes for the final set of packs and where necessary, | |
125 // inserting scalar promotion, vector creation from multiple scalars, and | |
126 // extraction of scalar values from vectors. | |
127 // | |
128 void SuperWord::SLP_extract() { | |
129 | |
130 // Ready the block | |
131 | |
132 construct_bb(); | |
133 | |
134 dependence_graph(); | |
135 | |
136 compute_max_depth(); | |
137 | |
138 compute_vector_element_type(); | |
139 | |
140 // Attempt vectorization | |
141 | |
142 find_adjacent_refs(); | |
143 | |
144 extend_packlist(); | |
145 | |
146 combine_packs(); | |
147 | |
148 construct_my_pack_map(); | |
149 | |
150 filter_packs(); | |
151 | |
152 schedule(); | |
153 | |
154 output(); | |
155 } | |
156 | |
157 //------------------------------find_adjacent_refs--------------------------- | |
158 // Find the adjacent memory references and create pack pairs for them. | |
159 // This is the initial set of packs that will then be extended by | |
160 // following use->def and def->use links. The align positions are | |
161 // assigned relative to the reference "align_to_ref" | |
162 void SuperWord::find_adjacent_refs() { | |
163 // Get list of memory operations | |
164 Node_List memops; | |
165 for (int i = 0; i < _block.length(); i++) { | |
166 Node* n = _block.at(i); | |
29
d5fc211aea19
6633953: type2aelembytes{T_ADDRESS} should be 8 bytes in 64 bit VM
kvn
parents:
0
diff
changeset
|
167 if (n->is_Mem() && in_bb(n) && |
d5fc211aea19
6633953: type2aelembytes{T_ADDRESS} should be 8 bytes in 64 bit VM
kvn
parents:
0
diff
changeset
|
168 is_java_primitive(n->as_Mem()->memory_type())) { |
0 | 169 int align = memory_alignment(n->as_Mem(), 0); |
170 if (align != bottom_align) { | |
171 memops.push(n); | |
172 } | |
173 } | |
174 } | |
175 if (memops.size() == 0) return; | |
176 | |
177 // Find a memory reference to align to. The pre-loop trip count | |
178 // is modified to align this reference to a vector-aligned address | |
179 find_align_to_ref(memops); | |
180 if (align_to_ref() == NULL) return; | |
181 | |
182 SWPointer align_to_ref_p(align_to_ref(), this); | |
183 int offset = align_to_ref_p.offset_in_bytes(); | |
184 int scale = align_to_ref_p.scale_in_bytes(); | |
185 int vw = vector_width_in_bytes(); | |
186 int stride_sign = (scale * iv_stride()) > 0 ? 1 : -1; | |
187 int iv_adjustment = (stride_sign * vw - (offset % vw)) % vw; | |
188 | |
189 #ifndef PRODUCT | |
190 if (TraceSuperWord) | |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
191 tty->print_cr("\noffset = %d iv_adjustment = %d elt_align = %d scale = %d iv_stride = %d", |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
192 offset, iv_adjustment, align_to_ref_p.memory_size(), align_to_ref_p.scale_in_bytes(), iv_stride()); |
0 | 193 #endif |
194 | |
195 // Set alignment relative to "align_to_ref" | |
196 for (int i = memops.size() - 1; i >= 0; i--) { | |
197 MemNode* s = memops.at(i)->as_Mem(); | |
198 SWPointer p2(s, this); | |
199 if (p2.comparable(align_to_ref_p)) { | |
200 int align = memory_alignment(s, iv_adjustment); | |
201 set_alignment(s, align); | |
202 } else { | |
203 memops.remove(i); | |
204 } | |
205 } | |
206 | |
207 // Create initial pack pairs of memory operations | |
208 for (uint i = 0; i < memops.size(); i++) { | |
209 Node* s1 = memops.at(i); | |
210 for (uint j = 0; j < memops.size(); j++) { | |
211 Node* s2 = memops.at(j); | |
212 if (s1 != s2 && are_adjacent_refs(s1, s2)) { | |
213 int align = alignment(s1); | |
214 if (stmts_can_pack(s1, s2, align)) { | |
215 Node_List* pair = new Node_List(); | |
216 pair->push(s1); | |
217 pair->push(s2); | |
218 _packset.append(pair); | |
219 } | |
220 } | |
221 } | |
222 } | |
223 | |
224 #ifndef PRODUCT | |
225 if (TraceSuperWord) { | |
226 tty->print_cr("\nAfter find_adjacent_refs"); | |
227 print_packset(); | |
228 } | |
229 #endif | |
230 } | |
231 | |
232 //------------------------------find_align_to_ref--------------------------- | |
233 // Find a memory reference to align the loop induction variable to. | |
234 // Looks first at stores then at loads, looking for a memory reference | |
235 // with the largest number of references similar to it. | |
236 void SuperWord::find_align_to_ref(Node_List &memops) { | |
237 GrowableArray<int> cmp_ct(arena(), memops.size(), memops.size(), 0); | |
238 | |
239 // Count number of comparable memory ops | |
240 for (uint i = 0; i < memops.size(); i++) { | |
241 MemNode* s1 = memops.at(i)->as_Mem(); | |
242 SWPointer p1(s1, this); | |
243 // Discard if pre loop can't align this reference | |
244 if (!ref_is_alignable(p1)) { | |
245 *cmp_ct.adr_at(i) = 0; | |
246 continue; | |
247 } | |
248 for (uint j = i+1; j < memops.size(); j++) { | |
249 MemNode* s2 = memops.at(j)->as_Mem(); | |
250 if (isomorphic(s1, s2)) { | |
251 SWPointer p2(s2, this); | |
252 if (p1.comparable(p2)) { | |
253 (*cmp_ct.adr_at(i))++; | |
254 (*cmp_ct.adr_at(j))++; | |
255 } | |
256 } | |
257 } | |
258 } | |
259 | |
260 // Find Store (or Load) with the greatest number of "comparable" references | |
261 int max_ct = 0; | |
262 int max_idx = -1; | |
263 int min_size = max_jint; | |
264 int min_iv_offset = max_jint; | |
265 for (uint j = 0; j < memops.size(); j++) { | |
266 MemNode* s = memops.at(j)->as_Mem(); | |
267 if (s->is_Store()) { | |
268 SWPointer p(s, this); | |
269 if (cmp_ct.at(j) > max_ct || | |
270 cmp_ct.at(j) == max_ct && (data_size(s) < min_size || | |
271 data_size(s) == min_size && | |
272 p.offset_in_bytes() < min_iv_offset)) { | |
273 max_ct = cmp_ct.at(j); | |
274 max_idx = j; | |
275 min_size = data_size(s); | |
276 min_iv_offset = p.offset_in_bytes(); | |
277 } | |
278 } | |
279 } | |
280 // If no stores, look at loads | |
281 if (max_ct == 0) { | |
282 for (uint j = 0; j < memops.size(); j++) { | |
283 MemNode* s = memops.at(j)->as_Mem(); | |
284 if (s->is_Load()) { | |
285 SWPointer p(s, this); | |
286 if (cmp_ct.at(j) > max_ct || | |
287 cmp_ct.at(j) == max_ct && (data_size(s) < min_size || | |
288 data_size(s) == min_size && | |
289 p.offset_in_bytes() < min_iv_offset)) { | |
290 max_ct = cmp_ct.at(j); | |
291 max_idx = j; | |
292 min_size = data_size(s); | |
293 min_iv_offset = p.offset_in_bytes(); | |
294 } | |
295 } | |
296 } | |
297 } | |
298 | |
299 if (max_ct > 0) | |
300 set_align_to_ref(memops.at(max_idx)->as_Mem()); | |
301 | |
302 #ifndef PRODUCT | |
303 if (TraceSuperWord && Verbose) { | |
304 tty->print_cr("\nVector memops after find_align_to_refs"); | |
305 for (uint i = 0; i < memops.size(); i++) { | |
306 MemNode* s = memops.at(i)->as_Mem(); | |
307 s->dump(); | |
308 } | |
309 } | |
310 #endif | |
311 } | |
312 | |
313 //------------------------------ref_is_alignable--------------------------- | |
314 // Can the preloop align the reference to position zero in the vector? | |
315 bool SuperWord::ref_is_alignable(SWPointer& p) { | |
316 if (!p.has_iv()) { | |
317 return true; // no induction variable | |
318 } | |
319 CountedLoopEndNode* pre_end = get_pre_loop_end(lp()->as_CountedLoop()); | |
320 assert(pre_end->stride_is_con(), "pre loop stride is constant"); | |
321 int preloop_stride = pre_end->stride_con(); | |
322 | |
323 int span = preloop_stride * p.scale_in_bytes(); | |
324 | |
325 // Stride one accesses are alignable. | |
326 if (ABS(span) == p.memory_size()) | |
327 return true; | |
328 | |
329 // If initial offset from start of object is computable, | |
330 // compute alignment within the vector. | |
331 int vw = vector_width_in_bytes(); | |
332 if (vw % span == 0) { | |
333 Node* init_nd = pre_end->init_trip(); | |
334 if (init_nd->is_Con() && p.invar() == NULL) { | |
335 int init = init_nd->bottom_type()->is_int()->get_con(); | |
336 | |
337 int init_offset = init * p.scale_in_bytes() + p.offset_in_bytes(); | |
338 assert(init_offset >= 0, "positive offset from object start"); | |
339 | |
340 if (span > 0) { | |
341 return (vw - (init_offset % vw)) % span == 0; | |
342 } else { | |
343 assert(span < 0, "nonzero stride * scale"); | |
344 return (init_offset % vw) % -span == 0; | |
345 } | |
346 } | |
347 } | |
348 return false; | |
349 } | |
350 | |
351 //---------------------------dependence_graph--------------------------- | |
352 // Construct dependency graph. | |
353 // Add dependence edges to load/store nodes for memory dependence | |
354 // A.out()->DependNode.in(1) and DependNode.out()->B.prec(x) | |
355 void SuperWord::dependence_graph() { | |
356 // First, assign a dependence node to each memory node | |
357 for (int i = 0; i < _block.length(); i++ ) { | |
358 Node *n = _block.at(i); | |
359 if (n->is_Mem() || n->is_Phi() && n->bottom_type() == Type::MEMORY) { | |
360 _dg.make_node(n); | |
361 } | |
362 } | |
363 | |
364 // For each memory slice, create the dependences | |
365 for (int i = 0; i < _mem_slice_head.length(); i++) { | |
366 Node* n = _mem_slice_head.at(i); | |
367 Node* n_tail = _mem_slice_tail.at(i); | |
368 | |
369 // Get slice in predecessor order (last is first) | |
370 mem_slice_preds(n_tail, n, _nlist); | |
371 | |
372 // Make the slice dependent on the root | |
373 DepMem* slice = _dg.dep(n); | |
374 _dg.make_edge(_dg.root(), slice); | |
375 | |
376 // Create a sink for the slice | |
377 DepMem* slice_sink = _dg.make_node(NULL); | |
378 _dg.make_edge(slice_sink, _dg.tail()); | |
379 | |
380 // Now visit each pair of memory ops, creating the edges | |
381 for (int j = _nlist.length() - 1; j >= 0 ; j--) { | |
382 Node* s1 = _nlist.at(j); | |
383 | |
384 // If no dependency yet, use slice | |
385 if (_dg.dep(s1)->in_cnt() == 0) { | |
386 _dg.make_edge(slice, s1); | |
387 } | |
388 SWPointer p1(s1->as_Mem(), this); | |
389 bool sink_dependent = true; | |
390 for (int k = j - 1; k >= 0; k--) { | |
391 Node* s2 = _nlist.at(k); | |
392 if (s1->is_Load() && s2->is_Load()) | |
393 continue; | |
394 SWPointer p2(s2->as_Mem(), this); | |
395 | |
396 int cmp = p1.cmp(p2); | |
397 if (SuperWordRTDepCheck && | |
398 p1.base() != p2.base() && p1.valid() && p2.valid()) { | |
399 // Create a runtime check to disambiguate | |
400 OrderedPair pp(p1.base(), p2.base()); | |
401 _disjoint_ptrs.append_if_missing(pp); | |
402 } else if (!SWPointer::not_equal(cmp)) { | |
403 // Possibly same address | |
404 _dg.make_edge(s1, s2); | |
405 sink_dependent = false; | |
406 } | |
407 } | |
408 if (sink_dependent) { | |
409 _dg.make_edge(s1, slice_sink); | |
410 } | |
411 } | |
412 #ifndef PRODUCT | |
413 if (TraceSuperWord) { | |
414 tty->print_cr("\nDependence graph for slice: %d", n->_idx); | |
415 for (int q = 0; q < _nlist.length(); q++) { | |
416 _dg.print(_nlist.at(q)); | |
417 } | |
418 tty->cr(); | |
419 } | |
420 #endif | |
421 _nlist.clear(); | |
422 } | |
423 | |
424 #ifndef PRODUCT | |
425 if (TraceSuperWord) { | |
426 tty->print_cr("\ndisjoint_ptrs: %s", _disjoint_ptrs.length() > 0 ? "" : "NONE"); | |
427 for (int r = 0; r < _disjoint_ptrs.length(); r++) { | |
428 _disjoint_ptrs.at(r).print(); | |
429 tty->cr(); | |
430 } | |
431 tty->cr(); | |
432 } | |
433 #endif | |
434 } | |
435 | |
436 //---------------------------mem_slice_preds--------------------------- | |
437 // Return a memory slice (node list) in predecessor order starting at "start" | |
438 void SuperWord::mem_slice_preds(Node* start, Node* stop, GrowableArray<Node*> &preds) { | |
439 assert(preds.length() == 0, "start empty"); | |
440 Node* n = start; | |
441 Node* prev = NULL; | |
442 while (true) { | |
443 assert(in_bb(n), "must be in block"); | |
444 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
445 Node* out = n->fast_out(i); | |
446 if (out->is_Load()) { | |
447 if (in_bb(out)) { | |
448 preds.push(out); | |
449 } | |
450 } else { | |
451 // FIXME | |
452 if (out->is_MergeMem() && !in_bb(out)) { | |
453 // Either unrolling is causing a memory edge not to disappear, | |
454 // or need to run igvn.optimize() again before SLP | |
455 } else if (out->is_Phi() && out->bottom_type() == Type::MEMORY && !in_bb(out)) { | |
456 // Ditto. Not sure what else to check further. | |
457 } else if (out->Opcode() == Op_StoreCM && out->in(4) == n) { | |
458 // StoreCM has an input edge used as a precedence edge. | |
459 // Maybe an issue when oop stores are vectorized. | |
460 } else { | |
461 assert(out == prev || prev == NULL, "no branches off of store slice"); | |
462 } | |
463 } | |
464 } | |
465 if (n == stop) break; | |
466 preds.push(n); | |
467 prev = n; | |
468 n = n->in(MemNode::Memory); | |
469 } | |
470 } | |
471 | |
472 //------------------------------stmts_can_pack--------------------------- | |
473 // Can s1 and s2 be in a pack with s1 immediately preceeding s2 and | |
474 // s1 aligned at "align" | |
475 bool SuperWord::stmts_can_pack(Node* s1, Node* s2, int align) { | |
476 if (isomorphic(s1, s2)) { | |
477 if (independent(s1, s2)) { | |
478 if (!exists_at(s1, 0) && !exists_at(s2, 1)) { | |
479 if (!s1->is_Mem() || are_adjacent_refs(s1, s2)) { | |
480 int s1_align = alignment(s1); | |
481 int s2_align = alignment(s2); | |
482 if (s1_align == top_align || s1_align == align) { | |
483 if (s2_align == top_align || s2_align == align + data_size(s1)) { | |
484 return true; | |
485 } | |
486 } | |
487 } | |
488 } | |
489 } | |
490 } | |
491 return false; | |
492 } | |
493 | |
494 //------------------------------exists_at--------------------------- | |
495 // Does s exist in a pack at position pos? | |
496 bool SuperWord::exists_at(Node* s, uint pos) { | |
497 for (int i = 0; i < _packset.length(); i++) { | |
498 Node_List* p = _packset.at(i); | |
499 if (p->at(pos) == s) { | |
500 return true; | |
501 } | |
502 } | |
503 return false; | |
504 } | |
505 | |
506 //------------------------------are_adjacent_refs--------------------------- | |
507 // Is s1 immediately before s2 in memory? | |
508 bool SuperWord::are_adjacent_refs(Node* s1, Node* s2) { | |
509 if (!s1->is_Mem() || !s2->is_Mem()) return false; | |
510 if (!in_bb(s1) || !in_bb(s2)) return false; | |
511 // FIXME - co_locate_pack fails on Stores in different mem-slices, so | |
512 // only pack memops that are in the same alias set until that's fixed. | |
513 if (_phase->C->get_alias_index(s1->as_Mem()->adr_type()) != | |
514 _phase->C->get_alias_index(s2->as_Mem()->adr_type())) | |
515 return false; | |
516 SWPointer p1(s1->as_Mem(), this); | |
517 SWPointer p2(s2->as_Mem(), this); | |
518 if (p1.base() != p2.base() || !p1.comparable(p2)) return false; | |
519 int diff = p2.offset_in_bytes() - p1.offset_in_bytes(); | |
520 return diff == data_size(s1); | |
521 } | |
522 | |
523 //------------------------------isomorphic--------------------------- | |
524 // Are s1 and s2 similar? | |
525 bool SuperWord::isomorphic(Node* s1, Node* s2) { | |
526 if (s1->Opcode() != s2->Opcode()) return false; | |
527 if (s1->req() != s2->req()) return false; | |
528 if (s1->in(0) != s2->in(0)) return false; | |
529 if (velt_type(s1) != velt_type(s2)) return false; | |
530 return true; | |
531 } | |
532 | |
533 //------------------------------independent--------------------------- | |
534 // Is there no data path from s1 to s2 or s2 to s1? | |
535 bool SuperWord::independent(Node* s1, Node* s2) { | |
536 // assert(s1->Opcode() == s2->Opcode(), "check isomorphic first"); | |
537 int d1 = depth(s1); | |
538 int d2 = depth(s2); | |
539 if (d1 == d2) return s1 != s2; | |
540 Node* deep = d1 > d2 ? s1 : s2; | |
541 Node* shallow = d1 > d2 ? s2 : s1; | |
542 | |
543 visited_clear(); | |
544 | |
545 return independent_path(shallow, deep); | |
546 } | |
547 | |
548 //------------------------------independent_path------------------------------ | |
549 // Helper for independent | |
550 bool SuperWord::independent_path(Node* shallow, Node* deep, uint dp) { | |
551 if (dp >= 1000) return false; // stop deep recursion | |
552 visited_set(deep); | |
553 int shal_depth = depth(shallow); | |
554 assert(shal_depth <= depth(deep), "must be"); | |
555 for (DepPreds preds(deep, _dg); !preds.done(); preds.next()) { | |
556 Node* pred = preds.current(); | |
557 if (in_bb(pred) && !visited_test(pred)) { | |
558 if (shallow == pred) { | |
559 return false; | |
560 } | |
561 if (shal_depth < depth(pred) && !independent_path(shallow, pred, dp+1)) { | |
562 return false; | |
563 } | |
564 } | |
565 } | |
566 return true; | |
567 } | |
568 | |
569 //------------------------------set_alignment--------------------------- | |
570 void SuperWord::set_alignment(Node* s1, Node* s2, int align) { | |
571 set_alignment(s1, align); | |
572 set_alignment(s2, align + data_size(s1)); | |
573 } | |
574 | |
575 //------------------------------data_size--------------------------- | |
576 int SuperWord::data_size(Node* s) { | |
577 const Type* t = velt_type(s); | |
578 BasicType bt = t->array_element_basic_type(); | |
29
d5fc211aea19
6633953: type2aelembytes{T_ADDRESS} should be 8 bytes in 64 bit VM
kvn
parents:
0
diff
changeset
|
579 int bsize = type2aelembytes(bt); |
0 | 580 assert(bsize != 0, "valid size"); |
581 return bsize; | |
582 } | |
583 | |
584 //------------------------------extend_packlist--------------------------- | |
585 // Extend packset by following use->def and def->use links from pack members. | |
586 void SuperWord::extend_packlist() { | |
587 bool changed; | |
588 do { | |
589 changed = false; | |
590 for (int i = 0; i < _packset.length(); i++) { | |
591 Node_List* p = _packset.at(i); | |
592 changed |= follow_use_defs(p); | |
593 changed |= follow_def_uses(p); | |
594 } | |
595 } while (changed); | |
596 | |
597 #ifndef PRODUCT | |
598 if (TraceSuperWord) { | |
599 tty->print_cr("\nAfter extend_packlist"); | |
600 print_packset(); | |
601 } | |
602 #endif | |
603 } | |
604 | |
605 //------------------------------follow_use_defs--------------------------- | |
606 // Extend the packset by visiting operand definitions of nodes in pack p | |
607 bool SuperWord::follow_use_defs(Node_List* p) { | |
608 Node* s1 = p->at(0); | |
609 Node* s2 = p->at(1); | |
610 assert(p->size() == 2, "just checking"); | |
611 assert(s1->req() == s2->req(), "just checking"); | |
612 assert(alignment(s1) + data_size(s1) == alignment(s2), "just checking"); | |
613 | |
614 if (s1->is_Load()) return false; | |
615 | |
616 int align = alignment(s1); | |
617 bool changed = false; | |
618 int start = s1->is_Store() ? MemNode::ValueIn : 1; | |
619 int end = s1->is_Store() ? MemNode::ValueIn+1 : s1->req(); | |
620 for (int j = start; j < end; j++) { | |
621 Node* t1 = s1->in(j); | |
622 Node* t2 = s2->in(j); | |
623 if (!in_bb(t1) || !in_bb(t2)) | |
624 continue; | |
625 if (stmts_can_pack(t1, t2, align)) { | |
626 if (est_savings(t1, t2) >= 0) { | |
627 Node_List* pair = new Node_List(); | |
628 pair->push(t1); | |
629 pair->push(t2); | |
630 _packset.append(pair); | |
631 set_alignment(t1, t2, align); | |
632 changed = true; | |
633 } | |
634 } | |
635 } | |
636 return changed; | |
637 } | |
638 | |
639 //------------------------------follow_def_uses--------------------------- | |
640 // Extend the packset by visiting uses of nodes in pack p | |
641 bool SuperWord::follow_def_uses(Node_List* p) { | |
642 bool changed = false; | |
643 Node* s1 = p->at(0); | |
644 Node* s2 = p->at(1); | |
645 assert(p->size() == 2, "just checking"); | |
646 assert(s1->req() == s2->req(), "just checking"); | |
647 assert(alignment(s1) + data_size(s1) == alignment(s2), "just checking"); | |
648 | |
649 if (s1->is_Store()) return false; | |
650 | |
651 int align = alignment(s1); | |
652 int savings = -1; | |
653 Node* u1 = NULL; | |
654 Node* u2 = NULL; | |
655 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) { | |
656 Node* t1 = s1->fast_out(i); | |
657 if (!in_bb(t1)) continue; | |
658 for (DUIterator_Fast jmax, j = s2->fast_outs(jmax); j < jmax; j++) { | |
659 Node* t2 = s2->fast_out(j); | |
660 if (!in_bb(t2)) continue; | |
661 if (!opnd_positions_match(s1, t1, s2, t2)) | |
662 continue; | |
663 if (stmts_can_pack(t1, t2, align)) { | |
664 int my_savings = est_savings(t1, t2); | |
665 if (my_savings > savings) { | |
666 savings = my_savings; | |
667 u1 = t1; | |
668 u2 = t2; | |
669 } | |
670 } | |
671 } | |
672 } | |
673 if (savings >= 0) { | |
674 Node_List* pair = new Node_List(); | |
675 pair->push(u1); | |
676 pair->push(u2); | |
677 _packset.append(pair); | |
678 set_alignment(u1, u2, align); | |
679 changed = true; | |
680 } | |
681 return changed; | |
682 } | |
683 | |
684 //---------------------------opnd_positions_match------------------------- | |
685 // Is the use of d1 in u1 at the same operand position as d2 in u2? | |
686 bool SuperWord::opnd_positions_match(Node* d1, Node* u1, Node* d2, Node* u2) { | |
687 uint ct = u1->req(); | |
688 if (ct != u2->req()) return false; | |
689 uint i1 = 0; | |
690 uint i2 = 0; | |
691 do { | |
692 for (i1++; i1 < ct; i1++) if (u1->in(i1) == d1) break; | |
693 for (i2++; i2 < ct; i2++) if (u2->in(i2) == d2) break; | |
694 if (i1 != i2) { | |
695 return false; | |
696 } | |
697 } while (i1 < ct); | |
698 return true; | |
699 } | |
700 | |
701 //------------------------------est_savings--------------------------- | |
702 // Estimate the savings from executing s1 and s2 as a pack | |
703 int SuperWord::est_savings(Node* s1, Node* s2) { | |
704 int save = 2 - 1; // 2 operations per instruction in packed form | |
705 | |
706 // inputs | |
707 for (uint i = 1; i < s1->req(); i++) { | |
708 Node* x1 = s1->in(i); | |
709 Node* x2 = s2->in(i); | |
710 if (x1 != x2) { | |
711 if (are_adjacent_refs(x1, x2)) { | |
712 save += adjacent_profit(x1, x2); | |
713 } else if (!in_packset(x1, x2)) { | |
714 save -= pack_cost(2); | |
715 } else { | |
716 save += unpack_cost(2); | |
717 } | |
718 } | |
719 } | |
720 | |
721 // uses of result | |
722 uint ct = 0; | |
723 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) { | |
724 Node* s1_use = s1->fast_out(i); | |
725 for (int j = 0; j < _packset.length(); j++) { | |
726 Node_List* p = _packset.at(j); | |
727 if (p->at(0) == s1_use) { | |
728 for (DUIterator_Fast kmax, k = s2->fast_outs(kmax); k < kmax; k++) { | |
729 Node* s2_use = s2->fast_out(k); | |
730 if (p->at(p->size()-1) == s2_use) { | |
731 ct++; | |
732 if (are_adjacent_refs(s1_use, s2_use)) { | |
733 save += adjacent_profit(s1_use, s2_use); | |
734 } | |
735 } | |
736 } | |
737 } | |
738 } | |
739 } | |
740 | |
741 if (ct < s1->outcnt()) save += unpack_cost(1); | |
742 if (ct < s2->outcnt()) save += unpack_cost(1); | |
743 | |
744 return save; | |
745 } | |
746 | |
747 //------------------------------costs--------------------------- | |
748 int SuperWord::adjacent_profit(Node* s1, Node* s2) { return 2; } | |
749 int SuperWord::pack_cost(int ct) { return ct; } | |
750 int SuperWord::unpack_cost(int ct) { return ct; } | |
751 | |
752 //------------------------------combine_packs--------------------------- | |
753 // Combine packs A and B with A.last == B.first into A.first..,A.last,B.second,..B.last | |
754 void SuperWord::combine_packs() { | |
755 bool changed; | |
756 do { | |
757 changed = false; | |
758 for (int i = 0; i < _packset.length(); i++) { | |
759 Node_List* p1 = _packset.at(i); | |
760 if (p1 == NULL) continue; | |
761 for (int j = 0; j < _packset.length(); j++) { | |
762 Node_List* p2 = _packset.at(j); | |
763 if (p2 == NULL) continue; | |
764 if (p1->at(p1->size()-1) == p2->at(0)) { | |
765 for (uint k = 1; k < p2->size(); k++) { | |
766 p1->push(p2->at(k)); | |
767 } | |
768 _packset.at_put(j, NULL); | |
769 changed = true; | |
770 } | |
771 } | |
772 } | |
773 } while (changed); | |
774 | |
775 for (int i = _packset.length() - 1; i >= 0; i--) { | |
776 Node_List* p1 = _packset.at(i); | |
777 if (p1 == NULL) { | |
778 _packset.remove_at(i); | |
779 } | |
780 } | |
781 | |
782 #ifndef PRODUCT | |
783 if (TraceSuperWord) { | |
784 tty->print_cr("\nAfter combine_packs"); | |
785 print_packset(); | |
786 } | |
787 #endif | |
788 } | |
789 | |
790 //-----------------------------construct_my_pack_map-------------------------- | |
791 // Construct the map from nodes to packs. Only valid after the | |
792 // point where a node is only in one pack (after combine_packs). | |
793 void SuperWord::construct_my_pack_map() { | |
794 Node_List* rslt = NULL; | |
795 for (int i = 0; i < _packset.length(); i++) { | |
796 Node_List* p = _packset.at(i); | |
797 for (uint j = 0; j < p->size(); j++) { | |
798 Node* s = p->at(j); | |
799 assert(my_pack(s) == NULL, "only in one pack"); | |
800 set_my_pack(s, p); | |
801 } | |
802 } | |
803 } | |
804 | |
805 //------------------------------filter_packs--------------------------- | |
806 // Remove packs that are not implemented or not profitable. | |
807 void SuperWord::filter_packs() { | |
808 | |
809 // Remove packs that are not implemented | |
810 for (int i = _packset.length() - 1; i >= 0; i--) { | |
811 Node_List* pk = _packset.at(i); | |
812 bool impl = implemented(pk); | |
813 if (!impl) { | |
814 #ifndef PRODUCT | |
815 if (TraceSuperWord && Verbose) { | |
816 tty->print_cr("Unimplemented"); | |
817 pk->at(0)->dump(); | |
818 } | |
819 #endif | |
820 remove_pack_at(i); | |
821 } | |
822 } | |
823 | |
824 // Remove packs that are not profitable | |
825 bool changed; | |
826 do { | |
827 changed = false; | |
828 for (int i = _packset.length() - 1; i >= 0; i--) { | |
829 Node_List* pk = _packset.at(i); | |
830 bool prof = profitable(pk); | |
831 if (!prof) { | |
832 #ifndef PRODUCT | |
833 if (TraceSuperWord && Verbose) { | |
834 tty->print_cr("Unprofitable"); | |
835 pk->at(0)->dump(); | |
836 } | |
837 #endif | |
838 remove_pack_at(i); | |
839 changed = true; | |
840 } | |
841 } | |
842 } while (changed); | |
843 | |
844 #ifndef PRODUCT | |
845 if (TraceSuperWord) { | |
846 tty->print_cr("\nAfter filter_packs"); | |
847 print_packset(); | |
848 tty->cr(); | |
849 } | |
850 #endif | |
851 } | |
852 | |
853 //------------------------------implemented--------------------------- | |
854 // Can code be generated for pack p? | |
855 bool SuperWord::implemented(Node_List* p) { | |
856 Node* p0 = p->at(0); | |
857 int vopc = VectorNode::opcode(p0->Opcode(), p->size(), velt_type(p0)); | |
858 return vopc > 0 && Matcher::has_match_rule(vopc); | |
859 } | |
860 | |
861 //------------------------------profitable--------------------------- | |
862 // For pack p, are all operands and all uses (with in the block) vector? | |
863 bool SuperWord::profitable(Node_List* p) { | |
864 Node* p0 = p->at(0); | |
865 uint start, end; | |
866 vector_opd_range(p0, &start, &end); | |
867 | |
868 // Return false if some input is not vector and inside block | |
869 for (uint i = start; i < end; i++) { | |
870 if (!is_vector_use(p0, i)) { | |
871 // For now, return false if not scalar promotion case (inputs are the same.) | |
872 // Later, implement PackNode and allow differring, non-vector inputs | |
873 // (maybe just the ones from outside the block.) | |
874 Node* p0_def = p0->in(i); | |
875 for (uint j = 1; j < p->size(); j++) { | |
876 Node* use = p->at(j); | |
877 Node* def = use->in(i); | |
878 if (p0_def != def) | |
879 return false; | |
880 } | |
881 } | |
882 } | |
883 if (!p0->is_Store()) { | |
884 // For now, return false if not all uses are vector. | |
885 // Later, implement ExtractNode and allow non-vector uses (maybe | |
886 // just the ones outside the block.) | |
887 for (uint i = 0; i < p->size(); i++) { | |
888 Node* def = p->at(i); | |
889 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) { | |
890 Node* use = def->fast_out(j); | |
891 for (uint k = 0; k < use->req(); k++) { | |
892 Node* n = use->in(k); | |
893 if (def == n) { | |
894 if (!is_vector_use(use, k)) { | |
895 return false; | |
896 } | |
897 } | |
898 } | |
899 } | |
900 } | |
901 } | |
902 return true; | |
903 } | |
904 | |
905 //------------------------------schedule--------------------------- | |
906 // Adjust the memory graph for the packed operations | |
907 void SuperWord::schedule() { | |
908 | |
909 // Co-locate in the memory graph the members of each memory pack | |
910 for (int i = 0; i < _packset.length(); i++) { | |
911 co_locate_pack(_packset.at(i)); | |
912 } | |
913 } | |
914 | |
915 //------------------------------co_locate_pack--------------------------- | |
916 // Within a pack, move stores down to the last executed store, | |
917 // and move loads up to the first executed load. | |
918 void SuperWord::co_locate_pack(Node_List* pk) { | |
919 if (pk->at(0)->is_Store()) { | |
920 // Push Stores down towards last executed pack member | |
921 MemNode* first = executed_first(pk)->as_Mem(); | |
922 MemNode* last = executed_last(pk)->as_Mem(); | |
923 MemNode* insert_pt = last; | |
924 MemNode* current = last->in(MemNode::Memory)->as_Mem(); | |
925 while (true) { | |
926 assert(in_bb(current), "stay in block"); | |
927 Node* my_mem = current->in(MemNode::Memory); | |
928 if (in_pack(current, pk)) { | |
929 // Forward users of my memory state to my input memory state | |
930 _igvn.hash_delete(current); | |
931 _igvn.hash_delete(my_mem); | |
932 for (DUIterator i = current->outs(); current->has_out(i); i++) { | |
933 Node* use = current->out(i); | |
934 if (use->is_Mem()) { | |
935 assert(use->in(MemNode::Memory) == current, "must be"); | |
936 _igvn.hash_delete(use); | |
937 use->set_req(MemNode::Memory, my_mem); | |
938 _igvn._worklist.push(use); | |
939 --i; // deleted this edge; rescan position | |
940 } | |
941 } | |
942 // put current immediately before insert_pt | |
943 current->set_req(MemNode::Memory, insert_pt->in(MemNode::Memory)); | |
944 _igvn.hash_delete(insert_pt); | |
945 insert_pt->set_req(MemNode::Memory, current); | |
946 _igvn._worklist.push(insert_pt); | |
947 _igvn._worklist.push(current); | |
948 insert_pt = current; | |
949 } | |
950 if (current == first) break; | |
951 current = my_mem->as_Mem(); | |
952 } | |
953 } else if (pk->at(0)->is_Load()) { | |
954 // Pull Loads up towards first executed pack member | |
955 LoadNode* first = executed_first(pk)->as_Load(); | |
956 Node* first_mem = first->in(MemNode::Memory); | |
957 _igvn.hash_delete(first_mem); | |
958 // Give each load same memory state as first | |
959 for (uint i = 0; i < pk->size(); i++) { | |
960 LoadNode* ld = pk->at(i)->as_Load(); | |
961 _igvn.hash_delete(ld); | |
962 ld->set_req(MemNode::Memory, first_mem); | |
963 _igvn._worklist.push(ld); | |
964 } | |
965 } | |
966 } | |
967 | |
968 //------------------------------output--------------------------- | |
969 // Convert packs into vector node operations | |
970 void SuperWord::output() { | |
971 if (_packset.length() == 0) return; | |
972 | |
973 // MUST ENSURE main loop's initial value is properly aligned: | |
974 // (iv_initial_value + min_iv_offset) % vector_width_in_bytes() == 0 | |
975 | |
976 align_initial_loop_index(align_to_ref()); | |
977 | |
978 // Insert extract (unpack) operations for scalar uses | |
979 for (int i = 0; i < _packset.length(); i++) { | |
980 insert_extracts(_packset.at(i)); | |
981 } | |
982 | |
983 for (int i = 0; i < _block.length(); i++) { | |
984 Node* n = _block.at(i); | |
985 Node_List* p = my_pack(n); | |
986 if (p && n == executed_last(p)) { | |
987 uint vlen = p->size(); | |
988 Node* vn = NULL; | |
989 Node* low_adr = p->at(0); | |
990 Node* first = executed_first(p); | |
991 if (n->is_Load()) { | |
992 int opc = n->Opcode(); | |
993 Node* ctl = n->in(MemNode::Control); | |
994 Node* mem = first->in(MemNode::Memory); | |
995 Node* adr = low_adr->in(MemNode::Address); | |
996 const TypePtr* atyp = n->adr_type(); | |
997 vn = VectorLoadNode::make(_phase->C, opc, ctl, mem, adr, atyp, vlen); | |
998 | |
999 } else if (n->is_Store()) { | |
1000 // Promote value to be stored to vector | |
1001 VectorNode* val = vector_opd(p, MemNode::ValueIn); | |
1002 | |
1003 int opc = n->Opcode(); | |
1004 Node* ctl = n->in(MemNode::Control); | |
1005 Node* mem = first->in(MemNode::Memory); | |
1006 Node* adr = low_adr->in(MemNode::Address); | |
1007 const TypePtr* atyp = n->adr_type(); | |
1008 vn = VectorStoreNode::make(_phase->C, opc, ctl, mem, adr, atyp, val, vlen); | |
1009 | |
1010 } else if (n->req() == 3) { | |
1011 // Promote operands to vector | |
1012 Node* in1 = vector_opd(p, 1); | |
1013 Node* in2 = vector_opd(p, 2); | |
1014 vn = VectorNode::make(_phase->C, n->Opcode(), in1, in2, vlen, velt_type(n)); | |
1015 | |
1016 } else { | |
1017 ShouldNotReachHere(); | |
1018 } | |
1019 | |
1020 _phase->_igvn.register_new_node_with_optimizer(vn); | |
1021 _phase->set_ctrl(vn, _phase->get_ctrl(p->at(0))); | |
1022 for (uint j = 0; j < p->size(); j++) { | |
1023 Node* pm = p->at(j); | |
1024 _igvn.hash_delete(pm); | |
1025 _igvn.subsume_node(pm, vn); | |
1026 } | |
1027 _igvn._worklist.push(vn); | |
1028 } | |
1029 } | |
1030 } | |
1031 | |
1032 //------------------------------vector_opd--------------------------- | |
1033 // Create a vector operand for the nodes in pack p for operand: in(opd_idx) | |
1034 VectorNode* SuperWord::vector_opd(Node_List* p, int opd_idx) { | |
1035 Node* p0 = p->at(0); | |
1036 uint vlen = p->size(); | |
1037 Node* opd = p0->in(opd_idx); | |
1038 | |
1039 bool same_opd = true; | |
1040 for (uint i = 1; i < vlen; i++) { | |
1041 Node* pi = p->at(i); | |
1042 Node* in = pi->in(opd_idx); | |
1043 if (opd != in) { | |
1044 same_opd = false; | |
1045 break; | |
1046 } | |
1047 } | |
1048 | |
1049 if (same_opd) { | |
1050 if (opd->is_Vector()) { | |
1051 return (VectorNode*)opd; // input is matching vector | |
1052 } | |
1053 // Convert scalar input to vector. Use p0's type because it's container | |
1054 // maybe smaller than the operand's container. | |
1055 const Type* opd_t = velt_type(!in_bb(opd) ? p0 : opd); | |
1056 const Type* p0_t = velt_type(p0); | |
1057 if (p0_t->higher_equal(opd_t)) opd_t = p0_t; | |
1058 VectorNode* vn = VectorNode::scalar2vector(_phase->C, opd, vlen, opd_t); | |
1059 | |
1060 _phase->_igvn.register_new_node_with_optimizer(vn); | |
1061 _phase->set_ctrl(vn, _phase->get_ctrl(opd)); | |
1062 return vn; | |
1063 } | |
1064 | |
1065 // Insert pack operation | |
1066 const Type* opd_t = velt_type(!in_bb(opd) ? p0 : opd); | |
1067 PackNode* pk = PackNode::make(_phase->C, opd, opd_t); | |
1068 | |
1069 for (uint i = 1; i < vlen; i++) { | |
1070 Node* pi = p->at(i); | |
1071 Node* in = pi->in(opd_idx); | |
1072 assert(my_pack(in) == NULL, "Should already have been unpacked"); | |
1073 assert(opd_t == velt_type(!in_bb(in) ? pi : in), "all same type"); | |
1074 pk->add_opd(in); | |
1075 } | |
1076 _phase->_igvn.register_new_node_with_optimizer(pk); | |
1077 _phase->set_ctrl(pk, _phase->get_ctrl(opd)); | |
1078 return pk; | |
1079 } | |
1080 | |
1081 //------------------------------insert_extracts--------------------------- | |
1082 // If a use of pack p is not a vector use, then replace the | |
1083 // use with an extract operation. | |
1084 void SuperWord::insert_extracts(Node_List* p) { | |
1085 if (p->at(0)->is_Store()) return; | |
1086 assert(_n_idx_list.is_empty(), "empty (node,index) list"); | |
1087 | |
1088 // Inspect each use of each pack member. For each use that is | |
1089 // not a vector use, replace the use with an extract operation. | |
1090 | |
1091 for (uint i = 0; i < p->size(); i++) { | |
1092 Node* def = p->at(i); | |
1093 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) { | |
1094 Node* use = def->fast_out(j); | |
1095 for (uint k = 0; k < use->req(); k++) { | |
1096 Node* n = use->in(k); | |
1097 if (def == n) { | |
1098 if (!is_vector_use(use, k)) { | |
1099 _n_idx_list.push(use, k); | |
1100 } | |
1101 } | |
1102 } | |
1103 } | |
1104 } | |
1105 | |
1106 while (_n_idx_list.is_nonempty()) { | |
1107 Node* use = _n_idx_list.node(); | |
1108 int idx = _n_idx_list.index(); | |
1109 _n_idx_list.pop(); | |
1110 Node* def = use->in(idx); | |
1111 | |
1112 // Insert extract operation | |
1113 _igvn.hash_delete(def); | |
1114 _igvn.hash_delete(use); | |
1115 int def_pos = alignment(def) / data_size(def); | |
1116 const Type* def_t = velt_type(def); | |
1117 | |
1118 Node* ex = ExtractNode::make(_phase->C, def, def_pos, def_t); | |
1119 _phase->_igvn.register_new_node_with_optimizer(ex); | |
1120 _phase->set_ctrl(ex, _phase->get_ctrl(def)); | |
1121 use->set_req(idx, ex); | |
1122 _igvn._worklist.push(def); | |
1123 _igvn._worklist.push(use); | |
1124 | |
1125 bb_insert_after(ex, bb_idx(def)); | |
1126 set_velt_type(ex, def_t); | |
1127 } | |
1128 } | |
1129 | |
1130 //------------------------------is_vector_use--------------------------- | |
1131 // Is use->in(u_idx) a vector use? | |
1132 bool SuperWord::is_vector_use(Node* use, int u_idx) { | |
1133 Node_List* u_pk = my_pack(use); | |
1134 if (u_pk == NULL) return false; | |
1135 Node* def = use->in(u_idx); | |
1136 Node_List* d_pk = my_pack(def); | |
1137 if (d_pk == NULL) { | |
1138 // check for scalar promotion | |
1139 Node* n = u_pk->at(0)->in(u_idx); | |
1140 for (uint i = 1; i < u_pk->size(); i++) { | |
1141 if (u_pk->at(i)->in(u_idx) != n) return false; | |
1142 } | |
1143 return true; | |
1144 } | |
1145 if (u_pk->size() != d_pk->size()) | |
1146 return false; | |
1147 for (uint i = 0; i < u_pk->size(); i++) { | |
1148 Node* ui = u_pk->at(i); | |
1149 Node* di = d_pk->at(i); | |
1150 if (ui->in(u_idx) != di || alignment(ui) != alignment(di)) | |
1151 return false; | |
1152 } | |
1153 return true; | |
1154 } | |
1155 | |
1156 //------------------------------construct_bb--------------------------- | |
1157 // Construct reverse postorder list of block members | |
1158 void SuperWord::construct_bb() { | |
1159 Node* entry = bb(); | |
1160 | |
1161 assert(_stk.length() == 0, "stk is empty"); | |
1162 assert(_block.length() == 0, "block is empty"); | |
1163 assert(_data_entry.length() == 0, "data_entry is empty"); | |
1164 assert(_mem_slice_head.length() == 0, "mem_slice_head is empty"); | |
1165 assert(_mem_slice_tail.length() == 0, "mem_slice_tail is empty"); | |
1166 | |
1167 // Find non-control nodes with no inputs from within block, | |
1168 // create a temporary map from node _idx to bb_idx for use | |
1169 // by the visited and post_visited sets, | |
1170 // and count number of nodes in block. | |
1171 int bb_ct = 0; | |
1172 for (uint i = 0; i < lpt()->_body.size(); i++ ) { | |
1173 Node *n = lpt()->_body.at(i); | |
1174 set_bb_idx(n, i); // Create a temporary map | |
1175 if (in_bb(n)) { | |
1176 bb_ct++; | |
1177 if (!n->is_CFG()) { | |
1178 bool found = false; | |
1179 for (uint j = 0; j < n->req(); j++) { | |
1180 Node* def = n->in(j); | |
1181 if (def && in_bb(def)) { | |
1182 found = true; | |
1183 break; | |
1184 } | |
1185 } | |
1186 if (!found) { | |
1187 assert(n != entry, "can't be entry"); | |
1188 _data_entry.push(n); | |
1189 } | |
1190 } | |
1191 } | |
1192 } | |
1193 | |
1194 // Find memory slices (head and tail) | |
1195 for (DUIterator_Fast imax, i = lp()->fast_outs(imax); i < imax; i++) { | |
1196 Node *n = lp()->fast_out(i); | |
1197 if (in_bb(n) && (n->is_Phi() && n->bottom_type() == Type::MEMORY)) { | |
1198 Node* n_tail = n->in(LoopNode::LoopBackControl); | |
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
235
diff
changeset
|
1199 if (n_tail != n->in(LoopNode::EntryControl)) { |
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
235
diff
changeset
|
1200 _mem_slice_head.push(n); |
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
235
diff
changeset
|
1201 _mem_slice_tail.push(n_tail); |
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
235
diff
changeset
|
1202 } |
0 | 1203 } |
1204 } | |
1205 | |
1206 // Create an RPO list of nodes in block | |
1207 | |
1208 visited_clear(); | |
1209 post_visited_clear(); | |
1210 | |
1211 // Push all non-control nodes with no inputs from within block, then control entry | |
1212 for (int j = 0; j < _data_entry.length(); j++) { | |
1213 Node* n = _data_entry.at(j); | |
1214 visited_set(n); | |
1215 _stk.push(n); | |
1216 } | |
1217 visited_set(entry); | |
1218 _stk.push(entry); | |
1219 | |
1220 // Do a depth first walk over out edges | |
1221 int rpo_idx = bb_ct - 1; | |
1222 int size; | |
1223 while ((size = _stk.length()) > 0) { | |
1224 Node* n = _stk.top(); // Leave node on stack | |
1225 if (!visited_test_set(n)) { | |
1226 // forward arc in graph | |
1227 } else if (!post_visited_test(n)) { | |
1228 // cross or back arc | |
1229 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
1230 Node *use = n->fast_out(i); | |
1231 if (in_bb(use) && !visited_test(use) && | |
1232 // Don't go around backedge | |
1233 (!use->is_Phi() || n == entry)) { | |
1234 _stk.push(use); | |
1235 } | |
1236 } | |
1237 if (_stk.length() == size) { | |
1238 // There were no additional uses, post visit node now | |
1239 _stk.pop(); // Remove node from stack | |
1240 assert(rpo_idx >= 0, ""); | |
1241 _block.at_put_grow(rpo_idx, n); | |
1242 rpo_idx--; | |
1243 post_visited_set(n); | |
1244 assert(rpo_idx >= 0 || _stk.is_empty(), ""); | |
1245 } | |
1246 } else { | |
1247 _stk.pop(); // Remove post-visited node from stack | |
1248 } | |
1249 } | |
1250 | |
1251 // Create real map of block indices for nodes | |
1252 for (int j = 0; j < _block.length(); j++) { | |
1253 Node* n = _block.at(j); | |
1254 set_bb_idx(n, j); | |
1255 } | |
1256 | |
1257 initialize_bb(); // Ensure extra info is allocated. | |
1258 | |
1259 #ifndef PRODUCT | |
1260 if (TraceSuperWord) { | |
1261 print_bb(); | |
1262 tty->print_cr("\ndata entry nodes: %s", _data_entry.length() > 0 ? "" : "NONE"); | |
1263 for (int m = 0; m < _data_entry.length(); m++) { | |
1264 tty->print("%3d ", m); | |
1265 _data_entry.at(m)->dump(); | |
1266 } | |
1267 tty->print_cr("\nmemory slices: %s", _mem_slice_head.length() > 0 ? "" : "NONE"); | |
1268 for (int m = 0; m < _mem_slice_head.length(); m++) { | |
1269 tty->print("%3d ", m); _mem_slice_head.at(m)->dump(); | |
1270 tty->print(" "); _mem_slice_tail.at(m)->dump(); | |
1271 } | |
1272 } | |
1273 #endif | |
1274 assert(rpo_idx == -1 && bb_ct == _block.length(), "all block members found"); | |
1275 } | |
1276 | |
1277 //------------------------------initialize_bb--------------------------- | |
1278 // Initialize per node info | |
1279 void SuperWord::initialize_bb() { | |
1280 Node* last = _block.at(_block.length() - 1); | |
1281 grow_node_info(bb_idx(last)); | |
1282 } | |
1283 | |
1284 //------------------------------bb_insert_after--------------------------- | |
1285 // Insert n into block after pos | |
1286 void SuperWord::bb_insert_after(Node* n, int pos) { | |
1287 int n_pos = pos + 1; | |
1288 // Make room | |
1289 for (int i = _block.length() - 1; i >= n_pos; i--) { | |
1290 _block.at_put_grow(i+1, _block.at(i)); | |
1291 } | |
1292 for (int j = _node_info.length() - 1; j >= n_pos; j--) { | |
1293 _node_info.at_put_grow(j+1, _node_info.at(j)); | |
1294 } | |
1295 // Set value | |
1296 _block.at_put_grow(n_pos, n); | |
1297 _node_info.at_put_grow(n_pos, SWNodeInfo::initial); | |
1298 // Adjust map from node->_idx to _block index | |
1299 for (int i = n_pos; i < _block.length(); i++) { | |
1300 set_bb_idx(_block.at(i), i); | |
1301 } | |
1302 } | |
1303 | |
1304 //------------------------------compute_max_depth--------------------------- | |
1305 // Compute max depth for expressions from beginning of block | |
1306 // Use to prune search paths during test for independence. | |
1307 void SuperWord::compute_max_depth() { | |
1308 int ct = 0; | |
1309 bool again; | |
1310 do { | |
1311 again = false; | |
1312 for (int i = 0; i < _block.length(); i++) { | |
1313 Node* n = _block.at(i); | |
1314 if (!n->is_Phi()) { | |
1315 int d_orig = depth(n); | |
1316 int d_in = 0; | |
1317 for (DepPreds preds(n, _dg); !preds.done(); preds.next()) { | |
1318 Node* pred = preds.current(); | |
1319 if (in_bb(pred)) { | |
1320 d_in = MAX2(d_in, depth(pred)); | |
1321 } | |
1322 } | |
1323 if (d_in + 1 != d_orig) { | |
1324 set_depth(n, d_in + 1); | |
1325 again = true; | |
1326 } | |
1327 } | |
1328 } | |
1329 ct++; | |
1330 } while (again); | |
1331 #ifndef PRODUCT | |
1332 if (TraceSuperWord && Verbose) | |
1333 tty->print_cr("compute_max_depth iterated: %d times", ct); | |
1334 #endif | |
1335 } | |
1336 | |
1337 //-------------------------compute_vector_element_type----------------------- | |
1338 // Compute necessary vector element type for expressions | |
1339 // This propagates backwards a narrower integer type when the | |
1340 // upper bits of the value are not needed. | |
1341 // Example: char a,b,c; a = b + c; | |
1342 // Normally the type of the add is integer, but for packed character | |
1343 // operations the type of the add needs to be char. | |
1344 void SuperWord::compute_vector_element_type() { | |
1345 #ifndef PRODUCT | |
1346 if (TraceSuperWord && Verbose) | |
1347 tty->print_cr("\ncompute_velt_type:"); | |
1348 #endif | |
1349 | |
1350 // Initial type | |
1351 for (int i = 0; i < _block.length(); i++) { | |
1352 Node* n = _block.at(i); | |
1353 const Type* t = n->is_Mem() ? Type::get_const_basic_type(n->as_Mem()->memory_type()) | |
1354 : _igvn.type(n); | |
1355 const Type* vt = container_type(t); | |
1356 set_velt_type(n, vt); | |
1357 } | |
1358 | |
1359 // Propagate narrowed type backwards through operations | |
1360 // that don't depend on higher order bits | |
1361 for (int i = _block.length() - 1; i >= 0; i--) { | |
1362 Node* n = _block.at(i); | |
1363 // Only integer types need be examined | |
1364 if (n->bottom_type()->isa_int()) { | |
1365 uint start, end; | |
1366 vector_opd_range(n, &start, &end); | |
1367 const Type* vt = velt_type(n); | |
1368 | |
1369 for (uint j = start; j < end; j++) { | |
1370 Node* in = n->in(j); | |
1371 // Don't propagate through a type conversion | |
1372 if (n->bottom_type() != in->bottom_type()) | |
1373 continue; | |
1374 switch(in->Opcode()) { | |
1375 case Op_AddI: case Op_AddL: | |
1376 case Op_SubI: case Op_SubL: | |
1377 case Op_MulI: case Op_MulL: | |
1378 case Op_AndI: case Op_AndL: | |
1379 case Op_OrI: case Op_OrL: | |
1380 case Op_XorI: case Op_XorL: | |
1381 case Op_LShiftI: case Op_LShiftL: | |
1382 case Op_CMoveI: case Op_CMoveL: | |
1383 if (in_bb(in)) { | |
1384 bool same_type = true; | |
1385 for (DUIterator_Fast kmax, k = in->fast_outs(kmax); k < kmax; k++) { | |
1386 Node *use = in->fast_out(k); | |
1387 if (!in_bb(use) || velt_type(use) != vt) { | |
1388 same_type = false; | |
1389 break; | |
1390 } | |
1391 } | |
1392 if (same_type) { | |
1393 set_velt_type(in, vt); | |
1394 } | |
1395 } | |
1396 } | |
1397 } | |
1398 } | |
1399 } | |
1400 #ifndef PRODUCT | |
1401 if (TraceSuperWord && Verbose) { | |
1402 for (int i = 0; i < _block.length(); i++) { | |
1403 Node* n = _block.at(i); | |
1404 velt_type(n)->dump(); | |
1405 tty->print("\t"); | |
1406 n->dump(); | |
1407 } | |
1408 } | |
1409 #endif | |
1410 } | |
1411 | |
1412 //------------------------------memory_alignment--------------------------- | |
1413 // Alignment within a vector memory reference | |
1414 int SuperWord::memory_alignment(MemNode* s, int iv_adjust_in_bytes) { | |
1415 SWPointer p(s, this); | |
1416 if (!p.valid()) { | |
1417 return bottom_align; | |
1418 } | |
1419 int offset = p.offset_in_bytes(); | |
1420 offset += iv_adjust_in_bytes; | |
1421 int off_rem = offset % vector_width_in_bytes(); | |
1422 int off_mod = off_rem >= 0 ? off_rem : off_rem + vector_width_in_bytes(); | |
1423 return off_mod; | |
1424 } | |
1425 | |
1426 //---------------------------container_type--------------------------- | |
1427 // Smallest type containing range of values | |
1428 const Type* SuperWord::container_type(const Type* t) { | |
221
1e026f8da827
6710487: More than half of JDI Regression tests hang with COOPs in -Xcomp mode
kvn
parents:
113
diff
changeset
|
1429 const Type* tp = t->make_ptr(); |
1e026f8da827
6710487: More than half of JDI Regression tests hang with COOPs in -Xcomp mode
kvn
parents:
113
diff
changeset
|
1430 if (tp && tp->isa_aryptr()) { |
1e026f8da827
6710487: More than half of JDI Regression tests hang with COOPs in -Xcomp mode
kvn
parents:
113
diff
changeset
|
1431 t = tp->is_aryptr()->elem(); |
0 | 1432 } |
1433 if (t->basic_type() == T_INT) { | |
1434 if (t->higher_equal(TypeInt::BOOL)) return TypeInt::BOOL; | |
1435 if (t->higher_equal(TypeInt::BYTE)) return TypeInt::BYTE; | |
1436 if (t->higher_equal(TypeInt::CHAR)) return TypeInt::CHAR; | |
1437 if (t->higher_equal(TypeInt::SHORT)) return TypeInt::SHORT; | |
1438 return TypeInt::INT; | |
1439 } | |
1440 return t; | |
1441 } | |
1442 | |
1443 //-------------------------vector_opd_range----------------------- | |
1444 // (Start, end] half-open range defining which operands are vector | |
1445 void SuperWord::vector_opd_range(Node* n, uint* start, uint* end) { | |
1446 switch (n->Opcode()) { | |
1447 case Op_LoadB: case Op_LoadC: | |
1448 case Op_LoadI: case Op_LoadL: | |
1449 case Op_LoadF: case Op_LoadD: | |
1450 case Op_LoadP: | |
1451 *start = 0; | |
1452 *end = 0; | |
1453 return; | |
1454 case Op_StoreB: case Op_StoreC: | |
1455 case Op_StoreI: case Op_StoreL: | |
1456 case Op_StoreF: case Op_StoreD: | |
1457 case Op_StoreP: | |
1458 *start = MemNode::ValueIn; | |
1459 *end = *start + 1; | |
1460 return; | |
1461 case Op_LShiftI: case Op_LShiftL: | |
1462 *start = 1; | |
1463 *end = 2; | |
1464 return; | |
1465 case Op_CMoveI: case Op_CMoveL: case Op_CMoveF: case Op_CMoveD: | |
1466 *start = 2; | |
1467 *end = n->req(); | |
1468 return; | |
1469 } | |
1470 *start = 1; | |
1471 *end = n->req(); // default is all operands | |
1472 } | |
1473 | |
1474 //------------------------------in_packset--------------------------- | |
1475 // Are s1 and s2 in a pack pair and ordered as s1,s2? | |
1476 bool SuperWord::in_packset(Node* s1, Node* s2) { | |
1477 for (int i = 0; i < _packset.length(); i++) { | |
1478 Node_List* p = _packset.at(i); | |
1479 assert(p->size() == 2, "must be"); | |
1480 if (p->at(0) == s1 && p->at(p->size()-1) == s2) { | |
1481 return true; | |
1482 } | |
1483 } | |
1484 return false; | |
1485 } | |
1486 | |
1487 //------------------------------in_pack--------------------------- | |
1488 // Is s in pack p? | |
1489 Node_List* SuperWord::in_pack(Node* s, Node_List* p) { | |
1490 for (uint i = 0; i < p->size(); i++) { | |
1491 if (p->at(i) == s) { | |
1492 return p; | |
1493 } | |
1494 } | |
1495 return NULL; | |
1496 } | |
1497 | |
1498 //------------------------------remove_pack_at--------------------------- | |
1499 // Remove the pack at position pos in the packset | |
1500 void SuperWord::remove_pack_at(int pos) { | |
1501 Node_List* p = _packset.at(pos); | |
1502 for (uint i = 0; i < p->size(); i++) { | |
1503 Node* s = p->at(i); | |
1504 set_my_pack(s, NULL); | |
1505 } | |
1506 _packset.remove_at(pos); | |
1507 } | |
1508 | |
1509 //------------------------------executed_first--------------------------- | |
1510 // Return the node executed first in pack p. Uses the RPO block list | |
1511 // to determine order. | |
1512 Node* SuperWord::executed_first(Node_List* p) { | |
1513 Node* n = p->at(0); | |
1514 int n_rpo = bb_idx(n); | |
1515 for (uint i = 1; i < p->size(); i++) { | |
1516 Node* s = p->at(i); | |
1517 int s_rpo = bb_idx(s); | |
1518 if (s_rpo < n_rpo) { | |
1519 n = s; | |
1520 n_rpo = s_rpo; | |
1521 } | |
1522 } | |
1523 return n; | |
1524 } | |
1525 | |
1526 //------------------------------executed_last--------------------------- | |
1527 // Return the node executed last in pack p. | |
1528 Node* SuperWord::executed_last(Node_List* p) { | |
1529 Node* n = p->at(0); | |
1530 int n_rpo = bb_idx(n); | |
1531 for (uint i = 1; i < p->size(); i++) { | |
1532 Node* s = p->at(i); | |
1533 int s_rpo = bb_idx(s); | |
1534 if (s_rpo > n_rpo) { | |
1535 n = s; | |
1536 n_rpo = s_rpo; | |
1537 } | |
1538 } | |
1539 return n; | |
1540 } | |
1541 | |
1542 //----------------------------align_initial_loop_index--------------------------- | |
1543 // Adjust pre-loop limit so that in main loop, a load/store reference | |
1544 // to align_to_ref will be a position zero in the vector. | |
1545 // (iv + k) mod vector_align == 0 | |
1546 void SuperWord::align_initial_loop_index(MemNode* align_to_ref) { | |
1547 CountedLoopNode *main_head = lp()->as_CountedLoop(); | |
1548 assert(main_head->is_main_loop(), ""); | |
1549 CountedLoopEndNode* pre_end = get_pre_loop_end(main_head); | |
1550 assert(pre_end != NULL, ""); | |
1551 Node *pre_opaq1 = pre_end->limit(); | |
1552 assert(pre_opaq1->Opcode() == Op_Opaque1, ""); | |
1553 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1; | |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1554 Node *lim0 = pre_opaq->in(1); |
0 | 1555 |
1556 // Where we put new limit calculations | |
1557 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl); | |
1558 | |
1559 // Ensure the original loop limit is available from the | |
1560 // pre-loop Opaque1 node. | |
1561 Node *orig_limit = pre_opaq->original_loop_limit(); | |
1562 assert(orig_limit != NULL && _igvn.type(orig_limit) != Type::TOP, ""); | |
1563 | |
1564 SWPointer align_to_ref_p(align_to_ref, this); | |
1565 | |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1566 // Given: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1567 // lim0 == original pre loop limit |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1568 // V == v_align (power of 2) |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1569 // invar == extra invariant piece of the address expression |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1570 // e == k [ +/- invar ] |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1571 // |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1572 // When reassociating expressions involving '%' the basic rules are: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1573 // (a - b) % k == 0 => a % k == b % k |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1574 // and: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1575 // (a + b) % k == 0 => a % k == (k - b) % k |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1576 // |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1577 // For stride > 0 && scale > 0, |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1578 // Derive the new pre-loop limit "lim" such that the two constraints: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1579 // (1) lim = lim0 + N (where N is some positive integer < V) |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1580 // (2) (e + lim) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1581 // are true. |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1582 // |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1583 // Substituting (1) into (2), |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1584 // (e + lim0 + N) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1585 // solve for N: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1586 // N = (V - (e + lim0)) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1587 // substitute back into (1), so that new limit |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1588 // lim = lim0 + (V - (e + lim0)) % V |
0 | 1589 // |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1590 // For stride > 0 && scale < 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1591 // Constraints: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1592 // lim = lim0 + N |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1593 // (e - lim) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1594 // Solving for lim: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1595 // (e - lim0 - N) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1596 // N = (e - lim0) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1597 // lim = lim0 + (e - lim0) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1598 // |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1599 // For stride < 0 && scale > 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1600 // Constraints: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1601 // lim = lim0 - N |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1602 // (e + lim) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1603 // Solving for lim: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1604 // (e + lim0 - N) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1605 // N = (e + lim0) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1606 // lim = lim0 - (e + lim0) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1607 // |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1608 // For stride < 0 && scale < 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1609 // Constraints: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1610 // lim = lim0 - N |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1611 // (e - lim) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1612 // Solving for lim: |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1613 // (e - lim0 + N) % V == 0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1614 // N = (V - (e - lim0)) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1615 // lim = lim0 - (V - (e - lim0)) % V |
0 | 1616 |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1617 int stride = iv_stride(); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1618 int scale = align_to_ref_p.scale_in_bytes(); |
0 | 1619 int elt_size = align_to_ref_p.memory_size(); |
1620 int v_align = vector_width_in_bytes() / elt_size; | |
1621 int k = align_to_ref_p.offset_in_bytes() / elt_size; | |
1622 | |
1623 Node *kn = _igvn.intcon(k); | |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1624 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1625 Node *e = kn; |
0 | 1626 if (align_to_ref_p.invar() != NULL) { |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1627 // incorporate any extra invariant piece producing k +/- invar >>> log2(elt) |
0 | 1628 Node* log2_elt = _igvn.intcon(exact_log2(elt_size)); |
1629 Node* aref = new (_phase->C, 3) URShiftINode(align_to_ref_p.invar(), log2_elt); | |
1630 _phase->_igvn.register_new_node_with_optimizer(aref); | |
1631 _phase->set_ctrl(aref, pre_ctrl); | |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1632 if (align_to_ref_p.negate_invar()) { |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1633 e = new (_phase->C, 3) SubINode(e, aref); |
0 | 1634 } else { |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1635 e = new (_phase->C, 3) AddINode(e, aref); |
0 | 1636 } |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1637 _phase->_igvn.register_new_node_with_optimizer(e); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1638 _phase->set_ctrl(e, pre_ctrl); |
0 | 1639 } |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1640 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1641 // compute e +/- lim0 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1642 if (scale < 0) { |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1643 e = new (_phase->C, 3) SubINode(e, lim0); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1644 } else { |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1645 e = new (_phase->C, 3) AddINode(e, lim0); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1646 } |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1647 _phase->_igvn.register_new_node_with_optimizer(e); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1648 _phase->set_ctrl(e, pre_ctrl); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1649 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1650 if (stride * scale > 0) { |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1651 // compute V - (e +/- lim0) |
0 | 1652 Node* va = _igvn.intcon(v_align); |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1653 e = new (_phase->C, 3) SubINode(va, e); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1654 _phase->_igvn.register_new_node_with_optimizer(e); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1655 _phase->set_ctrl(e, pre_ctrl); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1656 } |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1657 // compute N = (exp) % V |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1658 Node* va_msk = _igvn.intcon(v_align - 1); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1659 Node* N = new (_phase->C, 3) AndINode(e, va_msk); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1660 _phase->_igvn.register_new_node_with_optimizer(N); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1661 _phase->set_ctrl(N, pre_ctrl); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1662 |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1663 // substitute back into (1), so that new limit |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1664 // lim = lim0 + N |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1665 Node* lim; |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1666 if (stride < 0) { |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1667 lim = new (_phase->C, 3) SubINode(lim0, N); |
0 | 1668 } else { |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1669 lim = new (_phase->C, 3) AddINode(lim0, N); |
0 | 1670 } |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1671 _phase->_igvn.register_new_node_with_optimizer(lim); |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1672 _phase->set_ctrl(lim, pre_ctrl); |
0 | 1673 Node* constrained = |
72
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1674 (stride > 0) ? (Node*) new (_phase->C,3) MinINode(lim, orig_limit) |
f705f25597eb
6663621: JVM crashes while trying to execute api/java_security/Signature/SignatureTests.html#initSign tests.
never
parents:
29
diff
changeset
|
1675 : (Node*) new (_phase->C,3) MaxINode(lim, orig_limit); |
0 | 1676 _phase->_igvn.register_new_node_with_optimizer(constrained); |
1677 _phase->set_ctrl(constrained, pre_ctrl); | |
1678 _igvn.hash_delete(pre_opaq); | |
1679 pre_opaq->set_req(1, constrained); | |
1680 } | |
1681 | |
1682 //----------------------------get_pre_loop_end--------------------------- | |
1683 // Find pre loop end from main loop. Returns null if none. | |
1684 CountedLoopEndNode* SuperWord::get_pre_loop_end(CountedLoopNode *cl) { | |
1685 Node *ctrl = cl->in(LoopNode::EntryControl); | |
1686 if (!ctrl->is_IfTrue() && !ctrl->is_IfFalse()) return NULL; | |
1687 Node *iffm = ctrl->in(0); | |
1688 if (!iffm->is_If()) return NULL; | |
1689 Node *p_f = iffm->in(0); | |
1690 if (!p_f->is_IfFalse()) return NULL; | |
1691 if (!p_f->in(0)->is_CountedLoopEnd()) return NULL; | |
1692 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd(); | |
1693 if (!pre_end->loopnode()->is_pre_loop()) return NULL; | |
1694 return pre_end; | |
1695 } | |
1696 | |
1697 | |
1698 //------------------------------init--------------------------- | |
1699 void SuperWord::init() { | |
1700 _dg.init(); | |
1701 _packset.clear(); | |
1702 _disjoint_ptrs.clear(); | |
1703 _block.clear(); | |
1704 _data_entry.clear(); | |
1705 _mem_slice_head.clear(); | |
1706 _mem_slice_tail.clear(); | |
1707 _node_info.clear(); | |
1708 _align_to_ref = NULL; | |
1709 _lpt = NULL; | |
1710 _lp = NULL; | |
1711 _bb = NULL; | |
1712 _iv = NULL; | |
1713 } | |
1714 | |
1715 //------------------------------print_packset--------------------------- | |
1716 void SuperWord::print_packset() { | |
1717 #ifndef PRODUCT | |
1718 tty->print_cr("packset"); | |
1719 for (int i = 0; i < _packset.length(); i++) { | |
1720 tty->print_cr("Pack: %d", i); | |
1721 Node_List* p = _packset.at(i); | |
1722 print_pack(p); | |
1723 } | |
1724 #endif | |
1725 } | |
1726 | |
1727 //------------------------------print_pack--------------------------- | |
1728 void SuperWord::print_pack(Node_List* p) { | |
1729 for (uint i = 0; i < p->size(); i++) { | |
1730 print_stmt(p->at(i)); | |
1731 } | |
1732 } | |
1733 | |
1734 //------------------------------print_bb--------------------------- | |
1735 void SuperWord::print_bb() { | |
1736 #ifndef PRODUCT | |
1737 tty->print_cr("\nBlock"); | |
1738 for (int i = 0; i < _block.length(); i++) { | |
1739 Node* n = _block.at(i); | |
1740 tty->print("%d ", i); | |
1741 if (n) { | |
1742 n->dump(); | |
1743 } | |
1744 } | |
1745 #endif | |
1746 } | |
1747 | |
1748 //------------------------------print_stmt--------------------------- | |
1749 void SuperWord::print_stmt(Node* s) { | |
1750 #ifndef PRODUCT | |
1751 tty->print(" align: %d \t", alignment(s)); | |
1752 s->dump(); | |
1753 #endif | |
1754 } | |
1755 | |
1756 //------------------------------blank--------------------------- | |
1757 char* SuperWord::blank(uint depth) { | |
1758 static char blanks[101]; | |
1759 assert(depth < 101, "too deep"); | |
1760 for (uint i = 0; i < depth; i++) blanks[i] = ' '; | |
1761 blanks[depth] = '\0'; | |
1762 return blanks; | |
1763 } | |
1764 | |
1765 | |
1766 //==============================SWPointer=========================== | |
1767 | |
1768 //----------------------------SWPointer------------------------ | |
1769 SWPointer::SWPointer(MemNode* mem, SuperWord* slp) : | |
1770 _mem(mem), _slp(slp), _base(NULL), _adr(NULL), | |
1771 _scale(0), _offset(0), _invar(NULL), _negate_invar(false) { | |
1772 | |
1773 Node* adr = mem->in(MemNode::Address); | |
1774 if (!adr->is_AddP()) { | |
1775 assert(!valid(), "too complex"); | |
1776 return; | |
1777 } | |
1778 // Match AddP(base, AddP(ptr, k*iv [+ invariant]), constant) | |
1779 Node* base = adr->in(AddPNode::Base); | |
1780 for (int i = 0; i < 3; i++) { | |
1781 if (!scaled_iv_plus_offset(adr->in(AddPNode::Offset))) { | |
1782 assert(!valid(), "too complex"); | |
1783 return; | |
1784 } | |
1785 adr = adr->in(AddPNode::Address); | |
1786 if (base == adr || !adr->is_AddP()) { | |
1787 break; // stop looking at addp's | |
1788 } | |
1789 } | |
1790 _base = base; | |
1791 _adr = adr; | |
1792 assert(valid(), "Usable"); | |
1793 } | |
1794 | |
1795 // Following is used to create a temporary object during | |
1796 // the pattern match of an address expression. | |
1797 SWPointer::SWPointer(SWPointer* p) : | |
1798 _mem(p->_mem), _slp(p->_slp), _base(NULL), _adr(NULL), | |
1799 _scale(0), _offset(0), _invar(NULL), _negate_invar(false) {} | |
1800 | |
1801 //------------------------scaled_iv_plus_offset-------------------- | |
1802 // Match: k*iv + offset | |
1803 // where: k is a constant that maybe zero, and | |
1804 // offset is (k2 [+/- invariant]) where k2 maybe zero and invariant is optional | |
1805 bool SWPointer::scaled_iv_plus_offset(Node* n) { | |
1806 if (scaled_iv(n)) { | |
1807 return true; | |
1808 } | |
1809 if (offset_plus_k(n)) { | |
1810 return true; | |
1811 } | |
1812 int opc = n->Opcode(); | |
1813 if (opc == Op_AddI) { | |
1814 if (scaled_iv(n->in(1)) && offset_plus_k(n->in(2))) { | |
1815 return true; | |
1816 } | |
1817 if (scaled_iv(n->in(2)) && offset_plus_k(n->in(1))) { | |
1818 return true; | |
1819 } | |
1820 } else if (opc == Op_SubI) { | |
1821 if (scaled_iv(n->in(1)) && offset_plus_k(n->in(2), true)) { | |
1822 return true; | |
1823 } | |
1824 if (scaled_iv(n->in(2)) && offset_plus_k(n->in(1))) { | |
1825 _scale *= -1; | |
1826 return true; | |
1827 } | |
1828 } | |
1829 return false; | |
1830 } | |
1831 | |
1832 //----------------------------scaled_iv------------------------ | |
1833 // Match: k*iv where k is a constant that's not zero | |
1834 bool SWPointer::scaled_iv(Node* n) { | |
1835 if (_scale != 0) { | |
1836 return false; // already found a scale | |
1837 } | |
1838 if (n == iv()) { | |
1839 _scale = 1; | |
1840 return true; | |
1841 } | |
1842 int opc = n->Opcode(); | |
1843 if (opc == Op_MulI) { | |
1844 if (n->in(1) == iv() && n->in(2)->is_Con()) { | |
1845 _scale = n->in(2)->get_int(); | |
1846 return true; | |
1847 } else if (n->in(2) == iv() && n->in(1)->is_Con()) { | |
1848 _scale = n->in(1)->get_int(); | |
1849 return true; | |
1850 } | |
1851 } else if (opc == Op_LShiftI) { | |
1852 if (n->in(1) == iv() && n->in(2)->is_Con()) { | |
1853 _scale = 1 << n->in(2)->get_int(); | |
1854 return true; | |
1855 } | |
1856 } else if (opc == Op_ConvI2L) { | |
1857 if (scaled_iv_plus_offset(n->in(1))) { | |
1858 return true; | |
1859 } | |
1860 } else if (opc == Op_LShiftL) { | |
1861 if (!has_iv() && _invar == NULL) { | |
1862 // Need to preserve the current _offset value, so | |
1863 // create a temporary object for this expression subtree. | |
1864 // Hacky, so should re-engineer the address pattern match. | |
1865 SWPointer tmp(this); | |
1866 if (tmp.scaled_iv_plus_offset(n->in(1))) { | |
1867 if (tmp._invar == NULL) { | |
1868 int mult = 1 << n->in(2)->get_int(); | |
1869 _scale = tmp._scale * mult; | |
1870 _offset += tmp._offset * mult; | |
1871 return true; | |
1872 } | |
1873 } | |
1874 } | |
1875 } | |
1876 return false; | |
1877 } | |
1878 | |
1879 //----------------------------offset_plus_k------------------------ | |
1880 // Match: offset is (k [+/- invariant]) | |
1881 // where k maybe zero and invariant is optional, but not both. | |
1882 bool SWPointer::offset_plus_k(Node* n, bool negate) { | |
1883 int opc = n->Opcode(); | |
1884 if (opc == Op_ConI) { | |
1885 _offset += negate ? -(n->get_int()) : n->get_int(); | |
1886 return true; | |
1887 } else if (opc == Op_ConL) { | |
1888 // Okay if value fits into an int | |
1889 const TypeLong* t = n->find_long_type(); | |
1890 if (t->higher_equal(TypeLong::INT)) { | |
1891 jlong loff = n->get_long(); | |
1892 jint off = (jint)loff; | |
1893 _offset += negate ? -off : loff; | |
1894 return true; | |
1895 } | |
1896 return false; | |
1897 } | |
1898 if (_invar != NULL) return false; // already have an invariant | |
1899 if (opc == Op_AddI) { | |
1900 if (n->in(2)->is_Con() && invariant(n->in(1))) { | |
1901 _negate_invar = negate; | |
1902 _invar = n->in(1); | |
1903 _offset += negate ? -(n->in(2)->get_int()) : n->in(2)->get_int(); | |
1904 return true; | |
1905 } else if (n->in(1)->is_Con() && invariant(n->in(2))) { | |
1906 _offset += negate ? -(n->in(1)->get_int()) : n->in(1)->get_int(); | |
1907 _negate_invar = negate; | |
1908 _invar = n->in(2); | |
1909 return true; | |
1910 } | |
1911 } | |
1912 if (opc == Op_SubI) { | |
1913 if (n->in(2)->is_Con() && invariant(n->in(1))) { | |
1914 _negate_invar = negate; | |
1915 _invar = n->in(1); | |
1916 _offset += !negate ? -(n->in(2)->get_int()) : n->in(2)->get_int(); | |
1917 return true; | |
1918 } else if (n->in(1)->is_Con() && invariant(n->in(2))) { | |
1919 _offset += negate ? -(n->in(1)->get_int()) : n->in(1)->get_int(); | |
1920 _negate_invar = !negate; | |
1921 _invar = n->in(2); | |
1922 return true; | |
1923 } | |
1924 } | |
1925 if (invariant(n)) { | |
1926 _negate_invar = negate; | |
1927 _invar = n; | |
1928 return true; | |
1929 } | |
1930 return false; | |
1931 } | |
1932 | |
1933 //----------------------------print------------------------ | |
1934 void SWPointer::print() { | |
1935 #ifndef PRODUCT | |
1936 tty->print("base: %d adr: %d scale: %d offset: %d invar: %c%d\n", | |
1937 _base != NULL ? _base->_idx : 0, | |
1938 _adr != NULL ? _adr->_idx : 0, | |
1939 _scale, _offset, | |
1940 _negate_invar?'-':'+', | |
1941 _invar != NULL ? _invar->_idx : 0); | |
1942 #endif | |
1943 } | |
1944 | |
1945 // ========================= OrderedPair ===================== | |
1946 | |
1947 const OrderedPair OrderedPair::initial; | |
1948 | |
1949 // ========================= SWNodeInfo ===================== | |
1950 | |
1951 const SWNodeInfo SWNodeInfo::initial; | |
1952 | |
1953 | |
1954 // ============================ DepGraph =========================== | |
1955 | |
1956 //------------------------------make_node--------------------------- | |
1957 // Make a new dependence graph node for an ideal node. | |
1958 DepMem* DepGraph::make_node(Node* node) { | |
1959 DepMem* m = new (_arena) DepMem(node); | |
1960 if (node != NULL) { | |
1961 assert(_map.at_grow(node->_idx) == NULL, "one init only"); | |
1962 _map.at_put_grow(node->_idx, m); | |
1963 } | |
1964 return m; | |
1965 } | |
1966 | |
1967 //------------------------------make_edge--------------------------- | |
1968 // Make a new dependence graph edge from dpred -> dsucc | |
1969 DepEdge* DepGraph::make_edge(DepMem* dpred, DepMem* dsucc) { | |
1970 DepEdge* e = new (_arena) DepEdge(dpred, dsucc, dsucc->in_head(), dpred->out_head()); | |
1971 dpred->set_out_head(e); | |
1972 dsucc->set_in_head(e); | |
1973 return e; | |
1974 } | |
1975 | |
1976 // ========================== DepMem ======================== | |
1977 | |
1978 //------------------------------in_cnt--------------------------- | |
1979 int DepMem::in_cnt() { | |
1980 int ct = 0; | |
1981 for (DepEdge* e = _in_head; e != NULL; e = e->next_in()) ct++; | |
1982 return ct; | |
1983 } | |
1984 | |
1985 //------------------------------out_cnt--------------------------- | |
1986 int DepMem::out_cnt() { | |
1987 int ct = 0; | |
1988 for (DepEdge* e = _out_head; e != NULL; e = e->next_out()) ct++; | |
1989 return ct; | |
1990 } | |
1991 | |
1992 //------------------------------print----------------------------- | |
1993 void DepMem::print() { | |
1994 #ifndef PRODUCT | |
1995 tty->print(" DepNode %d (", _node->_idx); | |
1996 for (DepEdge* p = _in_head; p != NULL; p = p->next_in()) { | |
1997 Node* pred = p->pred()->node(); | |
1998 tty->print(" %d", pred != NULL ? pred->_idx : 0); | |
1999 } | |
2000 tty->print(") ["); | |
2001 for (DepEdge* s = _out_head; s != NULL; s = s->next_out()) { | |
2002 Node* succ = s->succ()->node(); | |
2003 tty->print(" %d", succ != NULL ? succ->_idx : 0); | |
2004 } | |
2005 tty->print_cr(" ]"); | |
2006 #endif | |
2007 } | |
2008 | |
2009 // =========================== DepEdge ========================= | |
2010 | |
2011 //------------------------------DepPreds--------------------------- | |
2012 void DepEdge::print() { | |
2013 #ifndef PRODUCT | |
2014 tty->print_cr("DepEdge: %d [ %d ]", _pred->node()->_idx, _succ->node()->_idx); | |
2015 #endif | |
2016 } | |
2017 | |
2018 // =========================== DepPreds ========================= | |
2019 // Iterator over predecessor edges in the dependence graph. | |
2020 | |
2021 //------------------------------DepPreds--------------------------- | |
2022 DepPreds::DepPreds(Node* n, DepGraph& dg) { | |
2023 _n = n; | |
2024 _done = false; | |
2025 if (_n->is_Store() || _n->is_Load()) { | |
2026 _next_idx = MemNode::Address; | |
2027 _end_idx = n->req(); | |
2028 _dep_next = dg.dep(_n)->in_head(); | |
2029 } else if (_n->is_Mem()) { | |
2030 _next_idx = 0; | |
2031 _end_idx = 0; | |
2032 _dep_next = dg.dep(_n)->in_head(); | |
2033 } else { | |
2034 _next_idx = 1; | |
2035 _end_idx = _n->req(); | |
2036 _dep_next = NULL; | |
2037 } | |
2038 next(); | |
2039 } | |
2040 | |
2041 //------------------------------next--------------------------- | |
2042 void DepPreds::next() { | |
2043 if (_dep_next != NULL) { | |
2044 _current = _dep_next->pred()->node(); | |
2045 _dep_next = _dep_next->next_in(); | |
2046 } else if (_next_idx < _end_idx) { | |
2047 _current = _n->in(_next_idx++); | |
2048 } else { | |
2049 _done = true; | |
2050 } | |
2051 } | |
2052 | |
2053 // =========================== DepSuccs ========================= | |
2054 // Iterator over successor edges in the dependence graph. | |
2055 | |
2056 //------------------------------DepSuccs--------------------------- | |
2057 DepSuccs::DepSuccs(Node* n, DepGraph& dg) { | |
2058 _n = n; | |
2059 _done = false; | |
2060 if (_n->is_Load()) { | |
2061 _next_idx = 0; | |
2062 _end_idx = _n->outcnt(); | |
2063 _dep_next = dg.dep(_n)->out_head(); | |
2064 } else if (_n->is_Mem() || _n->is_Phi() && _n->bottom_type() == Type::MEMORY) { | |
2065 _next_idx = 0; | |
2066 _end_idx = 0; | |
2067 _dep_next = dg.dep(_n)->out_head(); | |
2068 } else { | |
2069 _next_idx = 0; | |
2070 _end_idx = _n->outcnt(); | |
2071 _dep_next = NULL; | |
2072 } | |
2073 next(); | |
2074 } | |
2075 | |
2076 //-------------------------------next--------------------------- | |
2077 void DepSuccs::next() { | |
2078 if (_dep_next != NULL) { | |
2079 _current = _dep_next->succ()->node(); | |
2080 _dep_next = _dep_next->next_out(); | |
2081 } else if (_next_idx < _end_idx) { | |
2082 _current = _n->raw_out(_next_idx++); | |
2083 } else { | |
2084 _done = true; | |
2085 } | |
2086 } |