1 /*
2 * Copyright (c) 2007, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 #include "precompiled.hpp"
25 #include "compiler/compileLog.hpp"
26 #include "libadt/vectset.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/callnode.hpp"
30 #include "opto/castnode.hpp"
31 #include "opto/convertnode.hpp"
32 #include "opto/divnode.hpp"
33 #include "opto/matcher.hpp"
34 #include "opto/memnode.hpp"
35 #include "opto/mulnode.hpp"
36 #include "opto/opcodes.hpp"
37 #include "opto/opaquenode.hpp"
38 #include "opto/superword.hpp"
39 #include "opto/vectornode.hpp"
40
41 //
42 // S U P E R W O R D T R A N S F O R M
43 //=============================================================================
44
45 //------------------------------SuperWord---------------------------
46 SuperWord::SuperWord(PhaseIdealLoop* phase) :
47 _phase(phase),
48 _igvn(phase->_igvn),
49 _arena(phase->C->comp_arena()),
50 _packset(arena(), 8, 0, NULL), // packs for the current block
51 _bb_idx(arena(), (int)(1.10 * phase->C->unique()), 0, 0), // node idx to index in bb
52 _block(arena(), 8, 0, NULL), // nodes in current block
53 _data_entry(arena(), 8, 0, NULL), // nodes with all inputs from outside
54 _mem_slice_head(arena(), 8, 0, NULL), // memory slice heads
55 _mem_slice_tail(arena(), 8, 0, NULL), // memory slice tails
56 _node_info(arena(), 8, 0, SWNodeInfo::initial), // info needed per node
57 _clone_map(phase->C->clone_map()), // map of nodes created in cloning
58 _align_to_ref(NULL), // memory reference to align vectors to
59 _disjoint_ptrs(arena(), 8, 0, OrderedPair::initial), // runtime disambiguated pointer pairs
60 _dg(_arena), // dependence graph
61 _visited(arena()), // visited node set
62 _post_visited(arena()), // post visited node set
63 _n_idx_list(arena(), 8), // scratch list of (node,index) pairs
64 _stk(arena(), 8, 0, NULL), // scratch stack of nodes
65 _nlist(arena(), 8, 0, NULL), // scratch list of nodes
66 _lpt(NULL), // loop tree node
67 _lp(NULL), // LoopNode
68 _bb(NULL), // basic block
69 _iv(NULL), // induction var
70 _race_possible(false), // cases where SDMU is true
71 _early_return(true), // analysis evaluations routine
72 _num_work_vecs(0), // amount of vector work we have
73 _num_reductions(0), // amount of reduction work we have
74 _do_vector_loop(phase->C->do_vector_loop()), // whether to do vectorization/simd style
75 _ii_first(-1), // first loop generation index - only if do_vector_loop()
76 _ii_last(-1), // last loop generation index - only if do_vector_loop()
77 _ii_order(arena(), 8, 0, 0)
78 {
79 #ifndef PRODUCT
80 _vector_loop_debug = 0;
81 if (_phase->C->method() != NULL) {
82 _phase->C->method()->has_option_value("VectorizeDebug", _vector_loop_debug);
83 }
84 #endif
85 }
86
87 //------------------------------transform_loop---------------------------
88 void SuperWord::transform_loop(IdealLoopTree* lpt, bool do_optimization) {
89 assert(UseSuperWord, "should be");
90 // Do vectors exist on this architecture?
91 if (Matcher::vector_width_in_bytes(T_BYTE) < 2) return;
92
93 assert(lpt->_head->is_CountedLoop(), "must be");
94 CountedLoopNode *cl = lpt->_head->as_CountedLoop();
95
96 if (!cl->is_valid_counted_loop()) return; // skip malformed counted loop
97
98 if (!cl->is_main_loop() ) return; // skip normal, pre, and post loops
99 // Check for no control flow in body (other than exit)
100 Node *cl_exit = cl->loopexit();
101 if (cl_exit->in(0) != lpt->_head) return;
102
103 // Make sure the are no extra control users of the loop backedge
104 if (cl->back_control()->outcnt() != 1) {
105 return;
106 }
107
108 // We only re-enter slp when we vector mapped a queried loop and we want to
109 // continue unrolling, in this case, slp is not subsequently done.
110 if (cl->do_unroll_only()) return;
111
112 // Check for pre-loop ending with CountedLoopEnd(Bool(Cmp(x,Opaque1(limit))))
113 CountedLoopEndNode* pre_end = get_pre_loop_end(cl);
114 if (pre_end == NULL) return;
115 Node *pre_opaq1 = pre_end->limit();
116 if (pre_opaq1->Opcode() != Op_Opaque1) return;
117
118 init(); // initialize data structures
119
120 set_lpt(lpt);
121 set_lp(cl);
122
123 // For now, define one block which is the entire loop body
124 set_bb(cl);
125
126 if (do_optimization) {
127 assert(_packset.length() == 0, "packset must be empty");
128 SLP_extract();
129 }
130 }
131
132 //------------------------------early unrolling analysis------------------------------
133 void SuperWord::unrolling_analysis(int &local_loop_unroll_factor) {
134 bool is_slp = true;
135 ResourceMark rm;
136 size_t ignored_size = lpt()->_body.size();
137 int *ignored_loop_nodes = NEW_RESOURCE_ARRAY(int, ignored_size);
138 Node_Stack nstack((int)ignored_size);
139 CountedLoopNode *cl = lpt()->_head->as_CountedLoop();
140 Node *cl_exit = cl->loopexit();
141
142 // First clear the entries
143 for (uint i = 0; i < lpt()->_body.size(); i++) {
144 ignored_loop_nodes[i] = -1;
145 }
146
147 int max_vector = Matcher::max_vector_size(T_INT);
148
149 // Process the loop, some/all of the stack entries will not be in order, ergo
150 // need to preprocess the ignored initial state before we process the loop
151 for (uint i = 0; i < lpt()->_body.size(); i++) {
152 Node* n = lpt()->_body.at(i);
153 if (n == cl->incr() ||
154 n->is_reduction() ||
155 n->is_AddP() ||
156 n->is_Cmp() ||
157 n->is_IfTrue() ||
158 n->is_CountedLoop() ||
159 (n == cl_exit)) {
160 ignored_loop_nodes[i] = n->_idx;
161 continue;
162 }
163
164 if (n->is_If()) {
165 IfNode *iff = n->as_If();
166 if (iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN) {
167 if (lpt()->is_loop_exit(iff)) {
168 ignored_loop_nodes[i] = n->_idx;
169 continue;
170 }
171 }
172 }
173
174 if (n->is_Phi() && (n->bottom_type() == Type::MEMORY)) {
175 Node* n_tail = n->in(LoopNode::LoopBackControl);
176 if (n_tail != n->in(LoopNode::EntryControl)) {
177 if (!n_tail->is_Mem()) {
178 is_slp = false;
179 break;
180 }
181 }
182 }
183
184 // This must happen after check of phi/if
185 if (n->is_Phi() || n->is_If()) {
186 ignored_loop_nodes[i] = n->_idx;
187 continue;
188 }
189
190 if (n->is_LoadStore() || n->is_MergeMem() ||
191 (n->is_Proj() && !n->as_Proj()->is_CFG())) {
192 is_slp = false;
193 break;
194 }
195
196 // Ignore nodes with non-primitive type.
197 BasicType bt;
198 if (n->is_Mem()) {
199 bt = n->as_Mem()->memory_type();
200 } else {
201 bt = n->bottom_type()->basic_type();
202 }
203 if (is_java_primitive(bt) == false) {
204 ignored_loop_nodes[i] = n->_idx;
205 continue;
206 }
207
208 if (n->is_Mem()) {
209 MemNode* current = n->as_Mem();
210 Node* adr = n->in(MemNode::Address);
211 Node* n_ctrl = _phase->get_ctrl(adr);
212
213 // save a queue of post process nodes
214 if (n_ctrl != NULL && lpt()->is_member(_phase->get_loop(n_ctrl))) {
215 // Process the memory expression
216 int stack_idx = 0;
217 bool have_side_effects = true;
218 if (adr->is_AddP() == false) {
219 nstack.push(adr, stack_idx++);
220 } else {
221 // Mark the components of the memory operation in nstack
222 SWPointer p1(current, this, &nstack, true);
223 have_side_effects = p1.node_stack()->is_nonempty();
224 }
225
226 // Process the pointer stack
227 while (have_side_effects) {
228 Node* pointer_node = nstack.node();
229 for (uint j = 0; j < lpt()->_body.size(); j++) {
230 Node* cur_node = lpt()->_body.at(j);
231 if (cur_node == pointer_node) {
232 ignored_loop_nodes[j] = cur_node->_idx;
233 break;
234 }
235 }
236 nstack.pop();
237 have_side_effects = nstack.is_nonempty();
238 }
239 }
240 }
241 }
242
243 if (is_slp) {
244 // Now we try to find the maximum supported consistent vector which the machine
245 // description can use
246 for (uint i = 0; i < lpt()->_body.size(); i++) {
247 if (ignored_loop_nodes[i] != -1) continue;
248
249 BasicType bt;
250 Node* n = lpt()->_body.at(i);
251 if (n->is_Mem()) {
252 bt = n->as_Mem()->memory_type();
253 } else {
254 bt = n->bottom_type()->basic_type();
255 }
256 if (is_java_primitive(bt) == false) continue;
257
258 int cur_max_vector = Matcher::max_vector_size(bt);
259
260 // If a max vector exists which is not larger than _local_loop_unroll_factor
261 // stop looking, we already have the max vector to map to.
262 if (cur_max_vector < local_loop_unroll_factor) {
263 is_slp = false;
264 NOT_PRODUCT(if (TraceSuperWordLoopUnrollAnalysis) tty->print_cr("slp analysis fails: unroll limit greater than max vector\n"));
265 break;
266 }
267
268 // Map the maximal common vector
269 if (VectorNode::implemented(n->Opcode(), cur_max_vector, bt)) {
270 if (cur_max_vector < max_vector) {
271 max_vector = cur_max_vector;
272 }
273 }
274 }
275 if (is_slp) {
276 local_loop_unroll_factor = max_vector;
277 cl->mark_passed_slp();
278 }
279 cl->mark_was_slp();
280 cl->set_slp_max_unroll(local_loop_unroll_factor);
281 }
282 }
283
284 //------------------------------SLP_extract---------------------------
285 // Extract the superword level parallelism
286 //
287 // 1) A reverse post-order of nodes in the block is constructed. By scanning
288 // this list from first to last, all definitions are visited before their uses.
289 //
290 // 2) A point-to-point dependence graph is constructed between memory references.
291 // This simplies the upcoming "independence" checker.
292 //
293 // 3) The maximum depth in the node graph from the beginning of the block
294 // to each node is computed. This is used to prune the graph search
295 // in the independence checker.
296 //
297 // 4) For integer types, the necessary bit width is propagated backwards
298 // from stores to allow packed operations on byte, char, and short
299 // integers. This reverses the promotion to type "int" that javac
300 // did for operations like: char c1,c2,c3; c1 = c2 + c3.
301 //
302 // 5) One of the memory references is picked to be an aligned vector reference.
303 // The pre-loop trip count is adjusted to align this reference in the
304 // unrolled body.
305 //
306 // 6) The initial set of pack pairs is seeded with memory references.
307 //
308 // 7) The set of pack pairs is extended by following use->def and def->use links.
309 //
310 // 8) The pairs are combined into vector sized packs.
311 //
312 // 9) Reorder the memory slices to co-locate members of the memory packs.
313 //
314 // 10) Generate ideal vector nodes for the final set of packs and where necessary,
315 // inserting scalar promotion, vector creation from multiple scalars, and
316 // extraction of scalar values from vectors.
317 //
318 void SuperWord::SLP_extract() {
319
320 #ifndef PRODUCT
321 if (_do_vector_loop && TraceSuperWord) {
322 tty->print("SuperWord::SLP_extract\n");
323 tty->print("input loop\n");
324 _lpt->dump_head();
325 _lpt->dump();
326 for (uint i = 0; i < _lpt->_body.size(); i++) {
327 _lpt->_body.at(i)->dump();
328 }
329 }
330 #endif
331 // Ready the block
332 if (!construct_bb()) {
333 return; // Exit if no interesting nodes or complex graph.
334 }
335 // build _dg, _disjoint_ptrs
336 dependence_graph();
337
338 // compute function depth(Node*)
339 compute_max_depth();
340
341 if (_do_vector_loop) {
342 if (mark_generations() != -1) {
343 hoist_loads_in_graph(); // this only rebuild the graph; all basic structs need rebuild explicitly
344
345 if (!construct_bb()) {
346 return; // Exit if no interesting nodes or complex graph.
347 }
348 dependence_graph();
349 compute_max_depth();
350 }
351
352 #ifndef PRODUCT
353 if (TraceSuperWord) {
354 tty->print_cr("\nSuperWord::_do_vector_loop: graph after hoist_loads_in_graph");
355 _lpt->dump_head();
356 for (int j = 0; j < _block.length(); j++) {
357 Node* n = _block.at(j);
358 int d = depth(n);
359 for (int i = 0; i < d; i++) tty->print("%s", " ");
360 tty->print("%d :", d);
361 n->dump();
362 }
363 }
364 #endif
365 }
366
367 compute_vector_element_type();
368
369 // Attempt vectorization
370
371 find_adjacent_refs();
372
373 extend_packlist();
374
375 if (_do_vector_loop) {
376 if (_packset.length() == 0) {
377 #ifndef PRODUCT
378 if (TraceSuperWord) {
379 tty->print_cr("\nSuperWord::_do_vector_loop DFA could not build packset, now trying to build anyway");
380 }
381 #endif
382 pack_parallel();
383 }
384 }
385
386 combine_packs();
387
388 construct_my_pack_map();
389
390 filter_packs();
391
392 schedule();
393
394 output();
395 }
396
397 //------------------------------find_adjacent_refs---------------------------
398 // Find the adjacent memory references and create pack pairs for them.
399 // This is the initial set of packs that will then be extended by
400 // following use->def and def->use links. The align positions are
401 // assigned relative to the reference "align_to_ref"
402 void SuperWord::find_adjacent_refs() {
403 // Get list of memory operations
404 Node_List memops;
405 for (int i = 0; i < _block.length(); i++) {
406 Node* n = _block.at(i);
407 if (n->is_Mem() && !n->is_LoadStore() && in_bb(n) &&
408 is_java_primitive(n->as_Mem()->memory_type())) {
409 int align = memory_alignment(n->as_Mem(), 0);
410 if (align != bottom_align) {
411 memops.push(n);
412 }
413 }
414 }
415
416 Node_List align_to_refs;
417 int best_iv_adjustment = 0;
418 MemNode* best_align_to_mem_ref = NULL;
419
420 while (memops.size() != 0) {
421 // Find a memory reference to align to.
422 MemNode* mem_ref = find_align_to_ref(memops);
423 if (mem_ref == NULL) break;
424 align_to_refs.push(mem_ref);
425 int iv_adjustment = get_iv_adjustment(mem_ref);
426
427 if (best_align_to_mem_ref == NULL) {
428 // Set memory reference which is the best from all memory operations
429 // to be used for alignment. The pre-loop trip count is modified to align
430 // this reference to a vector-aligned address.
431 best_align_to_mem_ref = mem_ref;
432 best_iv_adjustment = iv_adjustment;
433 NOT_PRODUCT(find_adjacent_refs_trace_1(best_align_to_mem_ref, best_iv_adjustment);)
434 }
435
436 SWPointer align_to_ref_p(mem_ref, this, NULL, false);
437 // Set alignment relative to "align_to_ref" for all related memory operations.
438 for (int i = memops.size() - 1; i >= 0; i--) {
439 MemNode* s = memops.at(i)->as_Mem();
440 if (isomorphic(s, mem_ref) &&
441 (!_do_vector_loop || same_origin_idx(s, mem_ref))) {
442 SWPointer p2(s, this, NULL, false);
443 if (p2.comparable(align_to_ref_p)) {
444 int align = memory_alignment(s, iv_adjustment);
445 set_alignment(s, align);
446 }
447 }
448 }
449
450 // Create initial pack pairs of memory operations for which
451 // alignment is set and vectors will be aligned.
452 bool create_pack = true;
453 if (memory_alignment(mem_ref, best_iv_adjustment) == 0 || _do_vector_loop) {
454 if (!Matcher::misaligned_vectors_ok()) {
455 int vw = vector_width(mem_ref);
456 int vw_best = vector_width(best_align_to_mem_ref);
457 if (vw > vw_best) {
458 // Do not vectorize a memory access with more elements per vector
459 // if unaligned memory access is not allowed because number of
460 // iterations in pre-loop will be not enough to align it.
461 create_pack = false;
462 } else {
463 SWPointer p2(best_align_to_mem_ref, this, NULL, false);
464 if (align_to_ref_p.invar() != p2.invar()) {
465 // Do not vectorize memory accesses with different invariants
466 // if unaligned memory accesses are not allowed.
467 create_pack = false;
468 }
469 }
470 }
471 } else {
472 if (same_velt_type(mem_ref, best_align_to_mem_ref)) {
473 // Can't allow vectorization of unaligned memory accesses with the
474 // same type since it could be overlapped accesses to the same array.
475 create_pack = false;
476 } else {
477 // Allow independent (different type) unaligned memory operations
478 // if HW supports them.
479 if (!Matcher::misaligned_vectors_ok()) {
480 create_pack = false;
481 } else {
482 // Check if packs of the same memory type but
483 // with a different alignment were created before.
484 for (uint i = 0; i < align_to_refs.size(); i++) {
485 MemNode* mr = align_to_refs.at(i)->as_Mem();
486 if (same_velt_type(mr, mem_ref) &&
487 memory_alignment(mr, iv_adjustment) != 0)
488 create_pack = false;
489 }
490 }
491 }
492 }
493 if (create_pack) {
494 for (uint i = 0; i < memops.size(); i++) {
495 Node* s1 = memops.at(i);
496 int align = alignment(s1);
497 if (align == top_align) continue;
498 for (uint j = 0; j < memops.size(); j++) {
499 Node* s2 = memops.at(j);
500 if (alignment(s2) == top_align) continue;
501 if (s1 != s2 && are_adjacent_refs(s1, s2)) {
502 if (stmts_can_pack(s1, s2, align)) {
503 Node_List* pair = new Node_List();
504 pair->push(s1);
505 pair->push(s2);
506 if (!_do_vector_loop || same_origin_idx(s1, s2)) {
507 _packset.append(pair);
508 }
509 }
510 }
511 }
512 }
513 } else { // Don't create unaligned pack
514 // First, remove remaining memory ops of the same type from the list.
515 for (int i = memops.size() - 1; i >= 0; i--) {
516 MemNode* s = memops.at(i)->as_Mem();
517 if (same_velt_type(s, mem_ref)) {
518 memops.remove(i);
519 }
520 }
521
522 // Second, remove already constructed packs of the same type.
523 for (int i = _packset.length() - 1; i >= 0; i--) {
524 Node_List* p = _packset.at(i);
525 MemNode* s = p->at(0)->as_Mem();
526 if (same_velt_type(s, mem_ref)) {
527 remove_pack_at(i);
528 }
529 }
530
531 // If needed find the best memory reference for loop alignment again.
532 if (same_velt_type(mem_ref, best_align_to_mem_ref)) {
533 // Put memory ops from remaining packs back on memops list for
534 // the best alignment search.
535 uint orig_msize = memops.size();
536 for (int i = 0; i < _packset.length(); i++) {
537 Node_List* p = _packset.at(i);
538 MemNode* s = p->at(0)->as_Mem();
539 assert(!same_velt_type(s, mem_ref), "sanity");
540 memops.push(s);
541 }
542 MemNode* best_align_to_mem_ref = find_align_to_ref(memops);
543 if (best_align_to_mem_ref == NULL) {
544 NOT_PRODUCT(if (TraceSuperWord) tty->print_cr("SuperWord::find_adjacent_refs(): best_align_to_mem_ref == NULL");)
545 break;
546 }
547 best_iv_adjustment = get_iv_adjustment(best_align_to_mem_ref);
548 NOT_PRODUCT(find_adjacent_refs_trace_1(best_align_to_mem_ref, best_iv_adjustment);)
549 // Restore list.
550 while (memops.size() > orig_msize)
551 (void)memops.pop();
552 }
553 } // unaligned memory accesses
554
555 // Remove used mem nodes.
556 for (int i = memops.size() - 1; i >= 0; i--) {
557 MemNode* m = memops.at(i)->as_Mem();
558 if (alignment(m) != top_align) {
559 memops.remove(i);
560 }
561 }
562
563 } // while (memops.size() != 0
564 set_align_to_ref(best_align_to_mem_ref);
565
566 #ifndef PRODUCT
567 if (TraceSuperWord) {
568 tty->print_cr("\nAfter find_adjacent_refs");
569 print_packset();
570 }
571 #endif
572 }
573
574 #ifndef PRODUCT
575 void SuperWord::find_adjacent_refs_trace_1(Node* best_align_to_mem_ref, int best_iv_adjustment) {
576 if (is_trace_adjacent()) {
577 tty->print("SuperWord::find_adjacent_refs best_align_to_mem_ref = %d, best_iv_adjustment = %d",
578 best_align_to_mem_ref->_idx, best_iv_adjustment);
579 best_align_to_mem_ref->dump();
580 }
581 }
582 #endif
583
584 //------------------------------find_align_to_ref---------------------------
585 // Find a memory reference to align the loop induction variable to.
586 // Looks first at stores then at loads, looking for a memory reference
587 // with the largest number of references similar to it.
588 MemNode* SuperWord::find_align_to_ref(Node_List &memops) {
589 GrowableArray<int> cmp_ct(arena(), memops.size(), memops.size(), 0);
590
591 // Count number of comparable memory ops
592 for (uint i = 0; i < memops.size(); i++) {
593 MemNode* s1 = memops.at(i)->as_Mem();
594 SWPointer p1(s1, this, NULL, false);
595 // Discard if pre loop can't align this reference
596 if (!ref_is_alignable(p1)) {
597 *cmp_ct.adr_at(i) = 0;
598 continue;
599 }
600 for (uint j = i+1; j < memops.size(); j++) {
601 MemNode* s2 = memops.at(j)->as_Mem();
602 if (isomorphic(s1, s2)) {
603 SWPointer p2(s2, this, NULL, false);
604 if (p1.comparable(p2)) {
605 (*cmp_ct.adr_at(i))++;
606 (*cmp_ct.adr_at(j))++;
607 }
608 }
609 }
610 }
611
612 // Find Store (or Load) with the greatest number of "comparable" references,
613 // biggest vector size, smallest data size and smallest iv offset.
614 int max_ct = 0;
615 int max_vw = 0;
616 int max_idx = -1;
617 int min_size = max_jint;
618 int min_iv_offset = max_jint;
619 for (uint j = 0; j < memops.size(); j++) {
620 MemNode* s = memops.at(j)->as_Mem();
621 if (s->is_Store()) {
622 int vw = vector_width_in_bytes(s);
623 assert(vw > 1, "sanity");
624 SWPointer p(s, this, NULL, false);
625 if (cmp_ct.at(j) > max_ct ||
626 cmp_ct.at(j) == max_ct &&
627 (vw > max_vw ||
628 vw == max_vw &&
629 (data_size(s) < min_size ||
630 data_size(s) == min_size &&
631 (p.offset_in_bytes() < min_iv_offset)))) {
632 max_ct = cmp_ct.at(j);
633 max_vw = vw;
634 max_idx = j;
635 min_size = data_size(s);
636 min_iv_offset = p.offset_in_bytes();
637 }
638 }
639 }
640 // If no stores, look at loads
641 if (max_ct == 0) {
642 for (uint j = 0; j < memops.size(); j++) {
643 MemNode* s = memops.at(j)->as_Mem();
644 if (s->is_Load()) {
645 int vw = vector_width_in_bytes(s);
646 assert(vw > 1, "sanity");
647 SWPointer p(s, this, NULL, false);
648 if (cmp_ct.at(j) > max_ct ||
649 cmp_ct.at(j) == max_ct &&
650 (vw > max_vw ||
651 vw == max_vw &&
652 (data_size(s) < min_size ||
653 data_size(s) == min_size &&
654 (p.offset_in_bytes() < min_iv_offset)))) {
655 max_ct = cmp_ct.at(j);
656 max_vw = vw;
657 max_idx = j;
658 min_size = data_size(s);
659 min_iv_offset = p.offset_in_bytes();
660 }
661 }
662 }
663 }
664
665 #ifdef ASSERT
666 if (TraceSuperWord && Verbose) {
667 tty->print_cr("\nVector memops after find_align_to_ref");
668 for (uint i = 0; i < memops.size(); i++) {
669 MemNode* s = memops.at(i)->as_Mem();
670 s->dump();
671 }
672 }
673 #endif
674
675 if (max_ct > 0) {
676 #ifdef ASSERT
677 if (TraceSuperWord) {
678 tty->print("\nVector align to node: ");
679 memops.at(max_idx)->as_Mem()->dump();
680 }
681 #endif
682 return memops.at(max_idx)->as_Mem();
683 }
684 return NULL;
685 }
686
687 //------------------------------ref_is_alignable---------------------------
688 // Can the preloop align the reference to position zero in the vector?
689 bool SuperWord::ref_is_alignable(SWPointer& p) {
690 if (!p.has_iv()) {
691 return true; // no induction variable
692 }
693 CountedLoopEndNode* pre_end = get_pre_loop_end(lp()->as_CountedLoop());
694 assert(pre_end != NULL, "we must have a correct pre-loop");
695 assert(pre_end->stride_is_con(), "pre loop stride is constant");
696 int preloop_stride = pre_end->stride_con();
697
698 int span = preloop_stride * p.scale_in_bytes();
699 int mem_size = p.memory_size();
700 int offset = p.offset_in_bytes();
701 // Stride one accesses are alignable if offset is aligned to memory operation size.
702 // Offset can be unaligned when UseUnalignedAccesses is used.
703 if (ABS(span) == mem_size && (ABS(offset) % mem_size) == 0) {
704 return true;
705 }
706 // If the initial offset from start of the object is computable,
707 // check if the pre-loop can align the final offset accordingly.
708 //
709 // In other words: Can we find an i such that the offset
710 // after i pre-loop iterations is aligned to vw?
711 // (init_offset + pre_loop) % vw == 0 (1)
712 // where
713 // pre_loop = i * span
714 // is the number of bytes added to the offset by i pre-loop iterations.
715 //
716 // For this to hold we need pre_loop to increase init_offset by
717 // pre_loop = vw - (init_offset % vw)
718 //
719 // This is only possible if pre_loop is divisible by span because each
720 // pre-loop iteration increases the initial offset by 'span' bytes:
721 // (vw - (init_offset % vw)) % span == 0
722 //
723 int vw = vector_width_in_bytes(p.mem());
724 assert(vw > 1, "sanity");
725 Node* init_nd = pre_end->init_trip();
726 if (init_nd->is_Con() && p.invar() == NULL) {
727 int init = init_nd->bottom_type()->is_int()->get_con();
728 int init_offset = init * p.scale_in_bytes() + offset;
729 assert(init_offset >= 0, "positive offset from object start");
730 if (vw % span == 0) {
731 // If vm is a multiple of span, we use formula (1).
732 if (span > 0) {
733 return (vw - (init_offset % vw)) % span == 0;
734 } else {
735 assert(span < 0, "nonzero stride * scale");
736 return (init_offset % vw) % -span == 0;
737 }
738 } else if (span % vw == 0) {
739 // If span is a multiple of vw, we can simplify formula (1) to:
740 // (init_offset + i * span) % vw == 0
741 // =>
742 // (init_offset % vw) + ((i * span) % vw) == 0
743 // =>
744 // init_offset % vw == 0
745 //
746 // Because we add a multiple of vw to the initial offset, the final
747 // offset is a multiple of vw if and only if init_offset is a multiple.
748 //
749 return (init_offset % vw) == 0;
750 }
751 }
752 return false;
753 }
754
755 //---------------------------get_iv_adjustment---------------------------
756 // Calculate loop's iv adjustment for this memory ops.
757 int SuperWord::get_iv_adjustment(MemNode* mem_ref) {
758 SWPointer align_to_ref_p(mem_ref, this, NULL, false);
759 int offset = align_to_ref_p.offset_in_bytes();
760 int scale = align_to_ref_p.scale_in_bytes();
761 int elt_size = align_to_ref_p.memory_size();
762 int vw = vector_width_in_bytes(mem_ref);
763 assert(vw > 1, "sanity");
764 int iv_adjustment;
765 if (scale != 0) {
766 int stride_sign = (scale * iv_stride()) > 0 ? 1 : -1;
767 // At least one iteration is executed in pre-loop by default. As result
768 // several iterations are needed to align memory operations in main-loop even
769 // if offset is 0.
770 int iv_adjustment_in_bytes = (stride_sign * vw - (offset % vw));
771 assert(((ABS(iv_adjustment_in_bytes) % elt_size) == 0),
772 "(%d) should be divisible by (%d)", iv_adjustment_in_bytes, elt_size);
773 iv_adjustment = iv_adjustment_in_bytes/elt_size;
774 } else {
775 // This memory op is not dependent on iv (scale == 0)
776 iv_adjustment = 0;
777 }
778
779 #ifndef PRODUCT
780 if (TraceSuperWord) {
781 tty->print("SuperWord::get_iv_adjustment: n = %d, noffset = %d iv_adjust = %d elt_size = %d scale = %d iv_stride = %d vect_size %d: ",
782 mem_ref->_idx, offset, iv_adjustment, elt_size, scale, iv_stride(), vw);
783 mem_ref->dump();
784 }
785 #endif
786 return iv_adjustment;
787 }
788
789 //---------------------------dependence_graph---------------------------
790 // Construct dependency graph.
791 // Add dependence edges to load/store nodes for memory dependence
792 // A.out()->DependNode.in(1) and DependNode.out()->B.prec(x)
793 void SuperWord::dependence_graph() {
794 // First, assign a dependence node to each memory node
795 for (int i = 0; i < _block.length(); i++ ) {
796 Node *n = _block.at(i);
797 if (n->is_Mem() || n->is_Phi() && n->bottom_type() == Type::MEMORY) {
798 _dg.make_node(n);
799 }
800 }
801
802 // For each memory slice, create the dependences
803 for (int i = 0; i < _mem_slice_head.length(); i++) {
804 Node* n = _mem_slice_head.at(i);
805 Node* n_tail = _mem_slice_tail.at(i);
806
807 // Get slice in predecessor order (last is first)
808 mem_slice_preds(n_tail, n, _nlist);
809
810 #ifndef PRODUCT
811 if(TraceSuperWord && Verbose) {
812 tty->print_cr("SuperWord::dependence_graph: built a new mem slice");
813 for (int j = _nlist.length() - 1; j >= 0 ; j--) {
814 _nlist.at(j)->dump();
815 }
816 }
817 #endif
818 // Make the slice dependent on the root
819 DepMem* slice = _dg.dep(n);
820 _dg.make_edge(_dg.root(), slice);
821
822 // Create a sink for the slice
823 DepMem* slice_sink = _dg.make_node(NULL);
824 _dg.make_edge(slice_sink, _dg.tail());
825
826 // Now visit each pair of memory ops, creating the edges
827 for (int j = _nlist.length() - 1; j >= 0 ; j--) {
828 Node* s1 = _nlist.at(j);
829
830 // If no dependency yet, use slice
831 if (_dg.dep(s1)->in_cnt() == 0) {
832 _dg.make_edge(slice, s1);
833 }
834 SWPointer p1(s1->as_Mem(), this, NULL, false);
835 bool sink_dependent = true;
836 for (int k = j - 1; k >= 0; k--) {
837 Node* s2 = _nlist.at(k);
838 if (s1->is_Load() && s2->is_Load())
839 continue;
840 SWPointer p2(s2->as_Mem(), this, NULL, false);
841
842 int cmp = p1.cmp(p2);
843 if (SuperWordRTDepCheck &&
844 p1.base() != p2.base() && p1.valid() && p2.valid()) {
845 // Create a runtime check to disambiguate
846 OrderedPair pp(p1.base(), p2.base());
847 _disjoint_ptrs.append_if_missing(pp);
848 } else if (!SWPointer::not_equal(cmp)) {
849 // Possibly same address
850 _dg.make_edge(s1, s2);
851 sink_dependent = false;
852 }
853 }
854 if (sink_dependent) {
855 _dg.make_edge(s1, slice_sink);
856 }
857 }
858 #ifndef PRODUCT
859 if (TraceSuperWord) {
860 tty->print_cr("\nDependence graph for slice: %d", n->_idx);
861 for (int q = 0; q < _nlist.length(); q++) {
862 _dg.print(_nlist.at(q));
863 }
864 tty->cr();
865 }
866 #endif
867 _nlist.clear();
868 }
869
870 #ifndef PRODUCT
871 if (TraceSuperWord) {
872 tty->print_cr("\ndisjoint_ptrs: %s", _disjoint_ptrs.length() > 0 ? "" : "NONE");
873 for (int r = 0; r < _disjoint_ptrs.length(); r++) {
874 _disjoint_ptrs.at(r).print();
875 tty->cr();
876 }
877 tty->cr();
878 }
879 #endif
880 }
881
882 //---------------------------mem_slice_preds---------------------------
883 // Return a memory slice (node list) in predecessor order starting at "start"
884 void SuperWord::mem_slice_preds(Node* start, Node* stop, GrowableArray<Node*> &preds) {
885 assert(preds.length() == 0, "start empty");
886 Node* n = start;
887 Node* prev = NULL;
888 while (true) {
889 NOT_PRODUCT( if(is_trace_mem_slice()) tty->print_cr("SuperWord::mem_slice_preds: n %d", n->_idx);)
890 assert(in_bb(n), "must be in block");
891 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
892 Node* out = n->fast_out(i);
893 if (out->is_Load()) {
894 if (in_bb(out)) {
895 preds.push(out);
896 NOT_PRODUCT(if (TraceSuperWord && Verbose) tty->print_cr("SuperWord::mem_slice_preds: added pred(%d)", out->_idx);)
897 }
898 } else {
899 // FIXME
900 if (out->is_MergeMem() && !in_bb(out)) {
901 // Either unrolling is causing a memory edge not to disappear,
902 // or need to run igvn.optimize() again before SLP
903 } else if (out->is_Phi() && out->bottom_type() == Type::MEMORY && !in_bb(out)) {
904 // Ditto. Not sure what else to check further.
905 } else if (out->Opcode() == Op_StoreCM && out->in(MemNode::OopStore) == n) {
906 // StoreCM has an input edge used as a precedence edge.
907 // Maybe an issue when oop stores are vectorized.
908 } else {
909 assert(out == prev || prev == NULL, "no branches off of store slice");
910 }
911 }//else
912 }//for
913 if (n == stop) break;
914 preds.push(n);
915 NOT_PRODUCT(if (TraceSuperWord && Verbose) tty->print_cr("SuperWord::mem_slice_preds: added pred(%d)", n->_idx);)
916 prev = n;
917 assert(n->is_Mem(), "unexpected node %s", n->Name());
918 n = n->in(MemNode::Memory);
919 }
920 }
921
922 //------------------------------stmts_can_pack---------------------------
923 // Can s1 and s2 be in a pack with s1 immediately preceding s2 and
924 // s1 aligned at "align"
925 bool SuperWord::stmts_can_pack(Node* s1, Node* s2, int align) {
926
927 // Do not use superword for non-primitives
928 BasicType bt1 = velt_basic_type(s1);
929 BasicType bt2 = velt_basic_type(s2);
930 if(!is_java_primitive(bt1) || !is_java_primitive(bt2))
931 return false;
932 if (Matcher::max_vector_size(bt1) < 2) {
933 return false; // No vectors for this type
934 }
935
936 if (isomorphic(s1, s2)) {
937 if (independent(s1, s2) || reduction(s1, s2)) {
938 if (!exists_at(s1, 0) && !exists_at(s2, 1)) {
939 if (!s1->is_Mem() || are_adjacent_refs(s1, s2)) {
940 int s1_align = alignment(s1);
941 int s2_align = alignment(s2);
942 if (s1_align == top_align || s1_align == align) {
943 if (s2_align == top_align || s2_align == align + data_size(s1)) {
944 return true;
945 }
946 }
947 }
948 }
949 }
950 }
951 return false;
952 }
953
954 //------------------------------exists_at---------------------------
955 // Does s exist in a pack at position pos?
956 bool SuperWord::exists_at(Node* s, uint pos) {
957 for (int i = 0; i < _packset.length(); i++) {
958 Node_List* p = _packset.at(i);
959 if (p->at(pos) == s) {
960 return true;
961 }
962 }
963 return false;
964 }
965
966 //------------------------------are_adjacent_refs---------------------------
967 // Is s1 immediately before s2 in memory?
968 bool SuperWord::are_adjacent_refs(Node* s1, Node* s2) {
969 if (!s1->is_Mem() || !s2->is_Mem()) return false;
970 if (!in_bb(s1) || !in_bb(s2)) return false;
971
972 // Do not use superword for non-primitives
973 if (!is_java_primitive(s1->as_Mem()->memory_type()) ||
974 !is_java_primitive(s2->as_Mem()->memory_type())) {
975 return false;
976 }
977
978 // FIXME - co_locate_pack fails on Stores in different mem-slices, so
979 // only pack memops that are in the same alias set until that's fixed.
980 if (_phase->C->get_alias_index(s1->as_Mem()->adr_type()) !=
981 _phase->C->get_alias_index(s2->as_Mem()->adr_type()))
982 return false;
983 SWPointer p1(s1->as_Mem(), this, NULL, false);
984 SWPointer p2(s2->as_Mem(), this, NULL, false);
985 if (p1.base() != p2.base() || !p1.comparable(p2)) return false;
986 int diff = p2.offset_in_bytes() - p1.offset_in_bytes();
987 return diff == data_size(s1);
988 }
989
990 //------------------------------isomorphic---------------------------
991 // Are s1 and s2 similar?
992 bool SuperWord::isomorphic(Node* s1, Node* s2) {
993 if (s1->Opcode() != s2->Opcode()) return false;
994 if (s1->req() != s2->req()) return false;
995 if (s1->in(0) != s2->in(0)) return false;
996 if (!same_velt_type(s1, s2)) return false;
997 return true;
998 }
999
1000 //------------------------------independent---------------------------
1001 // Is there no data path from s1 to s2 or s2 to s1?
1002 bool SuperWord::independent(Node* s1, Node* s2) {
1003 // assert(s1->Opcode() == s2->Opcode(), "check isomorphic first");
1004 int d1 = depth(s1);
1005 int d2 = depth(s2);
1006 if (d1 == d2) return s1 != s2;
1007 Node* deep = d1 > d2 ? s1 : s2;
1008 Node* shallow = d1 > d2 ? s2 : s1;
1009
1010 visited_clear();
1011
1012 return independent_path(shallow, deep);
1013 }
1014
1015 //------------------------------reduction---------------------------
1016 // Is there a data path between s1 and s2 and the nodes reductions?
1017 bool SuperWord::reduction(Node* s1, Node* s2) {
1018 bool retValue = false;
1019 int d1 = depth(s1);
1020 int d2 = depth(s2);
1021 if (d1 + 1 == d2) {
1022 if (s1->is_reduction() && s2->is_reduction()) {
1023 // This is an ordered set, so s1 should define s2
1024 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) {
1025 Node* t1 = s1->fast_out(i);
1026 if (t1 == s2) {
1027 // both nodes are reductions and connected
1028 retValue = true;
1029 }
1030 }
1031 }
1032 }
1033
1034 return retValue;
1035 }
1036
1037 //------------------------------independent_path------------------------------
1038 // Helper for independent
1039 bool SuperWord::independent_path(Node* shallow, Node* deep, uint dp) {
1040 if (dp >= 1000) return false; // stop deep recursion
1041 visited_set(deep);
1042 int shal_depth = depth(shallow);
1043 assert(shal_depth <= depth(deep), "must be");
1044 for (DepPreds preds(deep, _dg); !preds.done(); preds.next()) {
1045 Node* pred = preds.current();
1046 if (in_bb(pred) && !visited_test(pred)) {
1047 if (shallow == pred) {
1048 return false;
1049 }
1050 if (shal_depth < depth(pred) && !independent_path(shallow, pred, dp+1)) {
1051 return false;
1052 }
1053 }
1054 }
1055 return true;
1056 }
1057
1058 //------------------------------set_alignment---------------------------
1059 void SuperWord::set_alignment(Node* s1, Node* s2, int align) {
1060 set_alignment(s1, align);
1061 if (align == top_align || align == bottom_align) {
1062 set_alignment(s2, align);
1063 } else {
1064 set_alignment(s2, align + data_size(s1));
1065 }
1066 }
1067
1068 //------------------------------data_size---------------------------
1069 int SuperWord::data_size(Node* s) {
1070 int bsize = type2aelembytes(velt_basic_type(s));
1071 assert(bsize != 0, "valid size");
1072 return bsize;
1073 }
1074
1075 //------------------------------extend_packlist---------------------------
1076 // Extend packset by following use->def and def->use links from pack members.
1077 void SuperWord::extend_packlist() {
1078 bool changed;
1079 do {
1080 packset_sort(_packset.length());
1081 changed = false;
1082 for (int i = 0; i < _packset.length(); i++) {
1083 Node_List* p = _packset.at(i);
1084 changed |= follow_use_defs(p);
1085 changed |= follow_def_uses(p);
1086 }
1087 } while (changed);
1088
1089 if (_race_possible) {
1090 for (int i = 0; i < _packset.length(); i++) {
1091 Node_List* p = _packset.at(i);
1092 order_def_uses(p);
1093 }
1094 }
1095
1096 #ifndef PRODUCT
1097 if (TraceSuperWord) {
1098 tty->print_cr("\nAfter extend_packlist");
1099 print_packset();
1100 }
1101 #endif
1102 }
1103
1104 //------------------------------follow_use_defs---------------------------
1105 // Extend the packset by visiting operand definitions of nodes in pack p
1106 bool SuperWord::follow_use_defs(Node_List* p) {
1107 assert(p->size() == 2, "just checking");
1108 Node* s1 = p->at(0);
1109 Node* s2 = p->at(1);
1110 assert(s1->req() == s2->req(), "just checking");
1111 assert(alignment(s1) + data_size(s1) == alignment(s2), "just checking");
1112
1113 if (s1->is_Load()) return false;
1114
1115 int align = alignment(s1);
1116 bool changed = false;
1117 int start = s1->is_Store() ? MemNode::ValueIn : 1;
1118 int end = s1->is_Store() ? MemNode::ValueIn+1 : s1->req();
1119 for (int j = start; j < end; j++) {
1120 Node* t1 = s1->in(j);
1121 Node* t2 = s2->in(j);
1122 if (!in_bb(t1) || !in_bb(t2))
1123 continue;
1124 if (stmts_can_pack(t1, t2, align)) {
1125 if (est_savings(t1, t2) >= 0) {
1126 Node_List* pair = new Node_List();
1127 pair->push(t1);
1128 pair->push(t2);
1129 _packset.append(pair);
1130 set_alignment(t1, t2, align);
1131 changed = true;
1132 }
1133 }
1134 }
1135 return changed;
1136 }
1137
1138 //------------------------------follow_def_uses---------------------------
1139 // Extend the packset by visiting uses of nodes in pack p
1140 bool SuperWord::follow_def_uses(Node_List* p) {
1141 bool changed = false;
1142 Node* s1 = p->at(0);
1143 Node* s2 = p->at(1);
1144 assert(p->size() == 2, "just checking");
1145 assert(s1->req() == s2->req(), "just checking");
1146 assert(alignment(s1) + data_size(s1) == alignment(s2), "just checking");
1147
1148 if (s1->is_Store()) return false;
1149
1150 int align = alignment(s1);
1151 int savings = -1;
1152 int num_s1_uses = 0;
1153 Node* u1 = NULL;
1154 Node* u2 = NULL;
1155 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) {
1156 Node* t1 = s1->fast_out(i);
1157 num_s1_uses++;
1158 if (!in_bb(t1)) continue;
1159 for (DUIterator_Fast jmax, j = s2->fast_outs(jmax); j < jmax; j++) {
1160 Node* t2 = s2->fast_out(j);
1161 if (!in_bb(t2)) continue;
1162 if (!opnd_positions_match(s1, t1, s2, t2))
1163 continue;
1164 if (stmts_can_pack(t1, t2, align)) {
1165 int my_savings = est_savings(t1, t2);
1166 if (my_savings > savings) {
1167 savings = my_savings;
1168 u1 = t1;
1169 u2 = t2;
1170 }
1171 }
1172 }
1173 }
1174 if (num_s1_uses > 1) {
1175 _race_possible = true;
1176 }
1177 if (savings >= 0) {
1178 Node_List* pair = new Node_List();
1179 pair->push(u1);
1180 pair->push(u2);
1181 _packset.append(pair);
1182 set_alignment(u1, u2, align);
1183 changed = true;
1184 }
1185 return changed;
1186 }
1187
1188 //------------------------------order_def_uses---------------------------
1189 // For extended packsets, ordinally arrange uses packset by major component
1190 void SuperWord::order_def_uses(Node_List* p) {
1191 Node* s1 = p->at(0);
1192
1193 if (s1->is_Store()) return;
1194
1195 // reductions are always managed beforehand
1196 if (s1->is_reduction()) return;
1197
1198 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) {
1199 Node* t1 = s1->fast_out(i);
1200
1201 // Only allow operand swap on commuting operations
1202 if (!t1->is_Add() && !t1->is_Mul()) {
1203 break;
1204 }
1205
1206 // Now find t1's packset
1207 Node_List* p2 = NULL;
1208 for (int j = 0; j < _packset.length(); j++) {
1209 p2 = _packset.at(j);
1210 Node* first = p2->at(0);
1211 if (t1 == first) {
1212 break;
1213 }
1214 p2 = NULL;
1215 }
1216 // Arrange all sub components by the major component
1217 if (p2 != NULL) {
1218 for (uint j = 1; j < p->size(); j++) {
1219 Node* d1 = p->at(j);
1220 Node* u1 = p2->at(j);
1221 opnd_positions_match(s1, t1, d1, u1);
1222 }
1223 }
1224 }
1225 }
1226
1227 //---------------------------opnd_positions_match-------------------------
1228 // Is the use of d1 in u1 at the same operand position as d2 in u2?
1229 bool SuperWord::opnd_positions_match(Node* d1, Node* u1, Node* d2, Node* u2) {
1230 // check reductions to see if they are marshalled to represent the reduction
1231 // operator in a specified opnd
1232 if (u1->is_reduction() && u2->is_reduction()) {
1233 // ensure reductions have phis and reduction definitions feeding the 1st operand
1234 Node* first = u1->in(2);
1235 if (first->is_Phi() || first->is_reduction()) {
1236 u1->swap_edges(1, 2);
1237 }
1238 // ensure reductions have phis and reduction definitions feeding the 1st operand
1239 first = u2->in(2);
1240 if (first->is_Phi() || first->is_reduction()) {
1241 u2->swap_edges(1, 2);
1242 }
1243 return true;
1244 }
1245
1246 uint ct = u1->req();
1247 if (ct != u2->req()) return false;
1248 uint i1 = 0;
1249 uint i2 = 0;
1250 do {
1251 for (i1++; i1 < ct; i1++) if (u1->in(i1) == d1) break;
1252 for (i2++; i2 < ct; i2++) if (u2->in(i2) == d2) break;
1253 if (i1 != i2) {
1254 if ((i1 == (3-i2)) && (u2->is_Add() || u2->is_Mul())) {
1255 // Further analysis relies on operands position matching.
1256 u2->swap_edges(i1, i2);
1257 } else {
1258 return false;
1259 }
1260 }
1261 } while (i1 < ct);
1262 return true;
1263 }
1264
1265 //------------------------------est_savings---------------------------
1266 // Estimate the savings from executing s1 and s2 as a pack
1267 int SuperWord::est_savings(Node* s1, Node* s2) {
1268 int save_in = 2 - 1; // 2 operations per instruction in packed form
1269
1270 // inputs
1271 for (uint i = 1; i < s1->req(); i++) {
1272 Node* x1 = s1->in(i);
1273 Node* x2 = s2->in(i);
1274 if (x1 != x2) {
1275 if (are_adjacent_refs(x1, x2)) {
1276 save_in += adjacent_profit(x1, x2);
1277 } else if (!in_packset(x1, x2)) {
1278 save_in -= pack_cost(2);
1279 } else {
1280 save_in += unpack_cost(2);
1281 }
1282 }
1283 }
1284
1285 // uses of result
1286 uint ct = 0;
1287 int save_use = 0;
1288 for (DUIterator_Fast imax, i = s1->fast_outs(imax); i < imax; i++) {
1289 Node* s1_use = s1->fast_out(i);
1290 for (int j = 0; j < _packset.length(); j++) {
1291 Node_List* p = _packset.at(j);
1292 if (p->at(0) == s1_use) {
1293 for (DUIterator_Fast kmax, k = s2->fast_outs(kmax); k < kmax; k++) {
1294 Node* s2_use = s2->fast_out(k);
1295 if (p->at(p->size()-1) == s2_use) {
1296 ct++;
1297 if (are_adjacent_refs(s1_use, s2_use)) {
1298 save_use += adjacent_profit(s1_use, s2_use);
1299 }
1300 }
1301 }
1302 }
1303 }
1304 }
1305
1306 if (ct < s1->outcnt()) save_use += unpack_cost(1);
1307 if (ct < s2->outcnt()) save_use += unpack_cost(1);
1308
1309 return MAX2(save_in, save_use);
1310 }
1311
1312 //------------------------------costs---------------------------
1313 int SuperWord::adjacent_profit(Node* s1, Node* s2) { return 2; }
1314 int SuperWord::pack_cost(int ct) { return ct; }
1315 int SuperWord::unpack_cost(int ct) { return ct; }
1316
1317 //------------------------------combine_packs---------------------------
1318 // Combine packs A and B with A.last == B.first into A.first..,A.last,B.second,..B.last
1319 void SuperWord::combine_packs() {
1320 bool changed = true;
1321 // Combine packs regardless max vector size.
1322 while (changed) {
1323 changed = false;
1324 for (int i = 0; i < _packset.length(); i++) {
1325 Node_List* p1 = _packset.at(i);
1326 if (p1 == NULL) continue;
1327 // Because of sorting we can start at i + 1
1328 for (int j = i + 1; j < _packset.length(); j++) {
1329 Node_List* p2 = _packset.at(j);
1330 if (p2 == NULL) continue;
1331 if (i == j) continue;
1332 if (p1->at(p1->size()-1) == p2->at(0)) {
1333 for (uint k = 1; k < p2->size(); k++) {
1334 p1->push(p2->at(k));
1335 }
1336 _packset.at_put(j, NULL);
1337 changed = true;
1338 }
1339 }
1340 }
1341 }
1342
1343 // Split packs which have size greater then max vector size.
1344 for (int i = 0; i < _packset.length(); i++) {
1345 Node_List* p1 = _packset.at(i);
1346 if (p1 != NULL) {
1347 BasicType bt = velt_basic_type(p1->at(0));
1348 uint max_vlen = Matcher::max_vector_size(bt); // Max elements in vector
1349 assert(is_power_of_2(max_vlen), "sanity");
1350 uint psize = p1->size();
1351 if (!is_power_of_2(psize)) {
1352 // Skip pack which can't be vector.
1353 // case1: for(...) { a[i] = i; } elements values are different (i+x)
1354 // case2: for(...) { a[i] = b[i+1]; } can't align both, load and store
1355 _packset.at_put(i, NULL);
1356 continue;
1357 }
1358 if (psize > max_vlen) {
1359 Node_List* pack = new Node_List();
1360 for (uint j = 0; j < psize; j++) {
1361 pack->push(p1->at(j));
1362 if (pack->size() >= max_vlen) {
1363 assert(is_power_of_2(pack->size()), "sanity");
1364 _packset.append(pack);
1365 pack = new Node_List();
1366 }
1367 }
1368 _packset.at_put(i, NULL);
1369 }
1370 }
1371 }
1372
1373 // Compress list.
1374 for (int i = _packset.length() - 1; i >= 0; i--) {
1375 Node_List* p1 = _packset.at(i);
1376 if (p1 == NULL) {
1377 _packset.remove_at(i);
1378 }
1379 }
1380
1381 #ifndef PRODUCT
1382 if (TraceSuperWord) {
1383 tty->print_cr("\nAfter combine_packs");
1384 print_packset();
1385 }
1386 #endif
1387 }
1388
1389 //-----------------------------construct_my_pack_map--------------------------
1390 // Construct the map from nodes to packs. Only valid after the
1391 // point where a node is only in one pack (after combine_packs).
1392 void SuperWord::construct_my_pack_map() {
1393 Node_List* rslt = NULL;
1394 for (int i = 0; i < _packset.length(); i++) {
1395 Node_List* p = _packset.at(i);
1396 for (uint j = 0; j < p->size(); j++) {
1397 Node* s = p->at(j);
1398 assert(my_pack(s) == NULL, "only in one pack");
1399 set_my_pack(s, p);
1400 }
1401 }
1402 }
1403
1404 //------------------------------filter_packs---------------------------
1405 // Remove packs that are not implemented or not profitable.
1406 void SuperWord::filter_packs() {
1407 // Remove packs that are not implemented
1408 for (int i = _packset.length() - 1; i >= 0; i--) {
1409 Node_List* pk = _packset.at(i);
1410 bool impl = implemented(pk);
1411 if (!impl) {
1412 #ifndef PRODUCT
1413 if (TraceSuperWord && Verbose) {
1414 tty->print_cr("Unimplemented");
1415 pk->at(0)->dump();
1416 }
1417 #endif
1418 remove_pack_at(i);
1419 }
1420 Node *n = pk->at(0);
1421 if (n->is_reduction()) {
1422 _num_reductions++;
1423 } else {
1424 _num_work_vecs++;
1425 }
1426 }
1427
1428 // Remove packs that are not profitable
1429 bool changed;
1430 do {
1431 changed = false;
1432 for (int i = _packset.length() - 1; i >= 0; i--) {
1433 Node_List* pk = _packset.at(i);
1434 bool prof = profitable(pk);
1435 if (!prof) {
1436 #ifndef PRODUCT
1437 if (TraceSuperWord && Verbose) {
1438 tty->print_cr("Unprofitable");
1439 pk->at(0)->dump();
1440 }
1441 #endif
1442 remove_pack_at(i);
1443 changed = true;
1444 }
1445 }
1446 } while (changed);
1447
1448 #ifndef PRODUCT
1449 if (TraceSuperWord) {
1450 tty->print_cr("\nAfter filter_packs");
1451 print_packset();
1452 tty->cr();
1453 }
1454 #endif
1455 }
1456
1457 //------------------------------implemented---------------------------
1458 // Can code be generated for pack p?
1459 bool SuperWord::implemented(Node_List* p) {
1460 bool retValue = false;
1461 Node* p0 = p->at(0);
1462 if (p0 != NULL) {
1463 int opc = p0->Opcode();
1464 uint size = p->size();
1465 if (p0->is_reduction()) {
1466 const Type *arith_type = p0->bottom_type();
1467 // Length 2 reductions of INT/LONG do not offer performance benefits
1468 if (((arith_type->basic_type() == T_INT) || (arith_type->basic_type() == T_LONG)) && (size == 2)) {
1469 retValue = false;
1470 } else {
1471 retValue = ReductionNode::implemented(opc, size, arith_type->basic_type());
1472 }
1473 } else {
1474 retValue = VectorNode::implemented(opc, size, velt_basic_type(p0));
1475 }
1476 }
1477 return retValue;
1478 }
1479
1480 //------------------------------same_inputs--------------------------
1481 // For pack p, are all idx operands the same?
1482 static bool same_inputs(Node_List* p, int idx) {
1483 Node* p0 = p->at(0);
1484 uint vlen = p->size();
1485 Node* p0_def = p0->in(idx);
1486 for (uint i = 1; i < vlen; i++) {
1487 Node* pi = p->at(i);
1488 Node* pi_def = pi->in(idx);
1489 if (p0_def != pi_def)
1490 return false;
1491 }
1492 return true;
1493 }
1494
1495 //------------------------------profitable---------------------------
1496 // For pack p, are all operands and all uses (with in the block) vector?
1497 bool SuperWord::profitable(Node_List* p) {
1498 Node* p0 = p->at(0);
1499 uint start, end;
1500 VectorNode::vector_operands(p0, &start, &end);
1501
1502 // Return false if some inputs are not vectors or vectors with different
1503 // size or alignment.
1504 // Also, for now, return false if not scalar promotion case when inputs are
1505 // the same. Later, implement PackNode and allow differing, non-vector inputs
1506 // (maybe just the ones from outside the block.)
1507 for (uint i = start; i < end; i++) {
1508 if (!is_vector_use(p0, i))
1509 return false;
1510 }
1511 // Check if reductions are connected
1512 if (p0->is_reduction()) {
1513 Node* second_in = p0->in(2);
1514 Node_List* second_pk = my_pack(second_in);
1515 if ((second_pk == NULL) || (_num_work_vecs == _num_reductions)) {
1516 // Remove reduction flag if no parent pack or if not enough work
1517 // to cover reduction expansion overhead
1518 p0->remove_flag(Node::Flag_is_reduction);
1519 return false;
1520 } else if (second_pk->size() != p->size()) {
1521 return false;
1522 }
1523 }
1524 if (VectorNode::is_shift(p0)) {
1525 // For now, return false if shift count is vector or not scalar promotion
1526 // case (different shift counts) because it is not supported yet.
1527 Node* cnt = p0->in(2);
1528 Node_List* cnt_pk = my_pack(cnt);
1529 if (cnt_pk != NULL)
1530 return false;
1531 if (!same_inputs(p, 2))
1532 return false;
1533 }
1534 if (!p0->is_Store()) {
1535 // For now, return false if not all uses are vector.
1536 // Later, implement ExtractNode and allow non-vector uses (maybe
1537 // just the ones outside the block.)
1538 for (uint i = 0; i < p->size(); i++) {
1539 Node* def = p->at(i);
1540 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
1541 Node* use = def->fast_out(j);
1542 for (uint k = 0; k < use->req(); k++) {
1543 Node* n = use->in(k);
1544 if (def == n) {
1545 // reductions can be loop carried dependences
1546 if (def->is_reduction() && use->is_Phi())
1547 continue;
1548 if (!is_vector_use(use, k)) {
1549 return false;
1550 }
1551 }
1552 }
1553 }
1554 }
1555 }
1556 return true;
1557 }
1558
1559 //------------------------------schedule---------------------------
1560 // Adjust the memory graph for the packed operations
1561 void SuperWord::schedule() {
1562
1563 // Co-locate in the memory graph the members of each memory pack
1564 for (int i = 0; i < _packset.length(); i++) {
1565 co_locate_pack(_packset.at(i));
1566 }
1567 }
1568
1569 //-------------------------------remove_and_insert-------------------
1570 // Remove "current" from its current position in the memory graph and insert
1571 // it after the appropriate insertion point (lip or uip).
1572 void SuperWord::remove_and_insert(MemNode *current, MemNode *prev, MemNode *lip,
1573 Node *uip, Unique_Node_List &sched_before) {
1574 Node* my_mem = current->in(MemNode::Memory);
1575 bool sched_up = sched_before.member(current);
1576
1577 // remove current_store from its current position in the memmory graph
1578 for (DUIterator i = current->outs(); current->has_out(i); i++) {
1579 Node* use = current->out(i);
1580 if (use->is_Mem()) {
1581 assert(use->in(MemNode::Memory) == current, "must be");
1582 if (use == prev) { // connect prev to my_mem
1583 _igvn.replace_input_of(use, MemNode::Memory, my_mem);
1584 --i; //deleted this edge; rescan position
1585 } else if (sched_before.member(use)) {
1586 if (!sched_up) { // Will be moved together with current
1587 _igvn.replace_input_of(use, MemNode::Memory, uip);
1588 --i; //deleted this edge; rescan position
1589 }
1590 } else {
1591 if (sched_up) { // Will be moved together with current
1592 _igvn.replace_input_of(use, MemNode::Memory, lip);
1593 --i; //deleted this edge; rescan position
1594 }
1595 }
1596 }
1597 }
1598
1599 Node *insert_pt = sched_up ? uip : lip;
1600
1601 // all uses of insert_pt's memory state should use current's instead
1602 for (DUIterator i = insert_pt->outs(); insert_pt->has_out(i); i++) {
1603 Node* use = insert_pt->out(i);
1604 if (use->is_Mem()) {
1605 assert(use->in(MemNode::Memory) == insert_pt, "must be");
1606 _igvn.replace_input_of(use, MemNode::Memory, current);
1607 --i; //deleted this edge; rescan position
1608 } else if (!sched_up && use->is_Phi() && use->bottom_type() == Type::MEMORY) {
1609 uint pos; //lip (lower insert point) must be the last one in the memory slice
1610 for (pos=1; pos < use->req(); pos++) {
1611 if (use->in(pos) == insert_pt) break;
1612 }
1613 _igvn.replace_input_of(use, pos, current);
1614 --i;
1615 }
1616 }
1617
1618 //connect current to insert_pt
1619 _igvn.replace_input_of(current, MemNode::Memory, insert_pt);
1620 }
1621
1622 //------------------------------co_locate_pack----------------------------------
1623 // To schedule a store pack, we need to move any sandwiched memory ops either before
1624 // or after the pack, based upon dependence information:
1625 // (1) If any store in the pack depends on the sandwiched memory op, the
1626 // sandwiched memory op must be scheduled BEFORE the pack;
1627 // (2) If a sandwiched memory op depends on any store in the pack, the
1628 // sandwiched memory op must be scheduled AFTER the pack;
1629 // (3) If a sandwiched memory op (say, memA) depends on another sandwiched
1630 // memory op (say memB), memB must be scheduled before memA. So, if memA is
1631 // scheduled before the pack, memB must also be scheduled before the pack;
1632 // (4) If there is no dependence restriction for a sandwiched memory op, we simply
1633 // schedule this store AFTER the pack
1634 // (5) We know there is no dependence cycle, so there in no other case;
1635 // (6) Finally, all memory ops in another single pack should be moved in the same direction.
1636 //
1637 // To schedule a load pack, we use the memory state of either the first or the last load in
1638 // the pack, based on the dependence constraint.
1639 void SuperWord::co_locate_pack(Node_List* pk) {
1640 if (pk->at(0)->is_Store()) {
1641 MemNode* first = executed_first(pk)->as_Mem();
1642 MemNode* last = executed_last(pk)->as_Mem();
1643 Unique_Node_List schedule_before_pack;
1644 Unique_Node_List memops;
1645
1646 MemNode* current = last->in(MemNode::Memory)->as_Mem();
1647 MemNode* previous = last;
1648 while (true) {
1649 assert(in_bb(current), "stay in block");
1650 memops.push(previous);
1651 for (DUIterator i = current->outs(); current->has_out(i); i++) {
1652 Node* use = current->out(i);
1653 if (use->is_Mem() && use != previous)
1654 memops.push(use);
1655 }
1656 if (current == first) break;
1657 previous = current;
1658 current = current->in(MemNode::Memory)->as_Mem();
1659 }
1660
1661 // determine which memory operations should be scheduled before the pack
1662 for (uint i = 1; i < memops.size(); i++) {
1663 Node *s1 = memops.at(i);
1664 if (!in_pack(s1, pk) && !schedule_before_pack.member(s1)) {
1665 for (uint j = 0; j< i; j++) {
1666 Node *s2 = memops.at(j);
1667 if (!independent(s1, s2)) {
1668 if (in_pack(s2, pk) || schedule_before_pack.member(s2)) {
1669 schedule_before_pack.push(s1); // s1 must be scheduled before
1670 Node_List* mem_pk = my_pack(s1);
1671 if (mem_pk != NULL) {
1672 for (uint ii = 0; ii < mem_pk->size(); ii++) {
1673 Node* s = mem_pk->at(ii); // follow partner
1674 if (memops.member(s) && !schedule_before_pack.member(s))
1675 schedule_before_pack.push(s);
1676 }
1677 }
1678 break;
1679 }
1680 }
1681 }
1682 }
1683 }
1684
1685 Node* upper_insert_pt = first->in(MemNode::Memory);
1686 // Following code moves loads connected to upper_insert_pt below aliased stores.
1687 // Collect such loads here and reconnect them back to upper_insert_pt later.
1688 memops.clear();
1689 for (DUIterator i = upper_insert_pt->outs(); upper_insert_pt->has_out(i); i++) {
1690 Node* use = upper_insert_pt->out(i);
1691 if (use->is_Mem() && !use->is_Store()) {
1692 memops.push(use);
1693 }
1694 }
1695
1696 MemNode* lower_insert_pt = last;
1697 previous = last; //previous store in pk
1698 current = last->in(MemNode::Memory)->as_Mem();
1699
1700 // start scheduling from "last" to "first"
1701 while (true) {
1702 assert(in_bb(current), "stay in block");
1703 assert(in_pack(previous, pk), "previous stays in pack");
1704 Node* my_mem = current->in(MemNode::Memory);
1705
1706 if (in_pack(current, pk)) {
1707 // Forward users of my memory state (except "previous) to my input memory state
1708 for (DUIterator i = current->outs(); current->has_out(i); i++) {
1709 Node* use = current->out(i);
1710 if (use->is_Mem() && use != previous) {
1711 assert(use->in(MemNode::Memory) == current, "must be");
1712 if (schedule_before_pack.member(use)) {
1713 _igvn.replace_input_of(use, MemNode::Memory, upper_insert_pt);
1714 } else {
1715 _igvn.replace_input_of(use, MemNode::Memory, lower_insert_pt);
1716 }
1717 --i; // deleted this edge; rescan position
1718 }
1719 }
1720 previous = current;
1721 } else { // !in_pack(current, pk) ==> a sandwiched store
1722 remove_and_insert(current, previous, lower_insert_pt, upper_insert_pt, schedule_before_pack);
1723 }
1724
1725 if (current == first) break;
1726 current = my_mem->as_Mem();
1727 } // end while
1728
1729 // Reconnect loads back to upper_insert_pt.
1730 for (uint i = 0; i < memops.size(); i++) {
1731 Node *ld = memops.at(i);
1732 if (ld->in(MemNode::Memory) != upper_insert_pt) {
1733 _igvn.replace_input_of(ld, MemNode::Memory, upper_insert_pt);
1734 }
1735 }
1736 } else if (pk->at(0)->is_Load()) { //load
1737 // all loads in the pack should have the same memory state. By default,
1738 // we use the memory state of the last load. However, if any load could
1739 // not be moved down due to the dependence constraint, we use the memory
1740 // state of the first load.
1741 Node* last_mem = executed_last(pk)->in(MemNode::Memory);
1742 Node* first_mem = executed_first(pk)->in(MemNode::Memory);
1743 bool schedule_last = true;
1744 for (uint i = 0; i < pk->size(); i++) {
1745 Node* ld = pk->at(i);
1746 for (Node* current = last_mem; current != ld->in(MemNode::Memory);
1747 current=current->in(MemNode::Memory)) {
1748 assert(current != first_mem, "corrupted memory graph");
1749 if(current->is_Mem() && !independent(current, ld)){
1750 schedule_last = false; // a later store depends on this load
1751 break;
1752 }
1753 }
1754 }
1755
1756 Node* mem_input = schedule_last ? last_mem : first_mem;
1757 _igvn.hash_delete(mem_input);
1758 // Give each load the same memory state
1759 for (uint i = 0; i < pk->size(); i++) {
1760 LoadNode* ld = pk->at(i)->as_Load();
1761 _igvn.replace_input_of(ld, MemNode::Memory, mem_input);
1762 }
1763 }
1764 }
1765
1766 //------------------------------output---------------------------
1767 // Convert packs into vector node operations
1768 void SuperWord::output() {
1769 if (_packset.length() == 0) return;
1770
1771 #ifndef PRODUCT
1772 if (TraceLoopOpts) {
1773 tty->print("SuperWord ");
1774 lpt()->dump_head();
1775 }
1776 #endif
1777
1778 // MUST ENSURE main loop's initial value is properly aligned:
1779 // (iv_initial_value + min_iv_offset) % vector_width_in_bytes() == 0
1780
1781 align_initial_loop_index(align_to_ref());
1782
1783 // Insert extract (unpack) operations for scalar uses
1784 for (int i = 0; i < _packset.length(); i++) {
1785 insert_extracts(_packset.at(i));
1786 }
1787
1788 Compile* C = _phase->C;
1789 CountedLoopNode *cl = lpt()->_head->as_CountedLoop();
1790 uint max_vlen_in_bytes = 0;
1791 uint max_vlen = 0;
1792 for (int i = 0; i < _block.length(); i++) {
1793 Node* n = _block.at(i);
1794 Node_List* p = my_pack(n);
1795 if (p && n == executed_last(p)) {
1796 uint vlen = p->size();
1797 uint vlen_in_bytes = 0;
1798 Node* vn = NULL;
1799 Node* low_adr = p->at(0);
1800 Node* first = executed_first(p);
1801 int opc = n->Opcode();
1802 if (n->is_Load()) {
1803 Node* ctl = n->in(MemNode::Control);
1804 Node* mem = first->in(MemNode::Memory);
1805 SWPointer p1(n->as_Mem(), this, NULL, false);
1806 // Identify the memory dependency for the new loadVector node by
1807 // walking up through memory chain.
1808 // This is done to give flexibility to the new loadVector node so that
1809 // it can move above independent storeVector nodes.
1810 while (mem->is_StoreVector()) {
1811 SWPointer p2(mem->as_Mem(), this, NULL, false);
1812 int cmp = p1.cmp(p2);
1813 if (SWPointer::not_equal(cmp) || !SWPointer::comparable(cmp)) {
1814 mem = mem->in(MemNode::Memory);
1815 } else {
1816 break; // dependent memory
1817 }
1818 }
1819 Node* adr = low_adr->in(MemNode::Address);
1820 const TypePtr* atyp = n->adr_type();
1821 vn = LoadVectorNode::make(opc, ctl, mem, adr, atyp, vlen, velt_basic_type(n), control_dependency(p));
1822 vlen_in_bytes = vn->as_LoadVector()->memory_size();
1823 } else if (n->is_Store()) {
1824 // Promote value to be stored to vector
1825 Node* val = vector_opd(p, MemNode::ValueIn);
1826 Node* ctl = n->in(MemNode::Control);
1827 Node* mem = first->in(MemNode::Memory);
1828 Node* adr = low_adr->in(MemNode::Address);
1829 const TypePtr* atyp = n->adr_type();
1830 vn = StoreVectorNode::make(opc, ctl, mem, adr, atyp, val, vlen);
1831 vlen_in_bytes = vn->as_StoreVector()->memory_size();
1832 } else if (n->req() == 3) {
1833 // Promote operands to vector
1834 Node* in1 = NULL;
1835 bool node_isa_reduction = n->is_reduction();
1836 if (node_isa_reduction) {
1837 // the input to the first reduction operation is retained
1838 in1 = low_adr->in(1);
1839 } else {
1840 in1 = vector_opd(p, 1);
1841 }
1842 Node* in2 = vector_opd(p, 2);
1843 if (VectorNode::is_invariant_vector(in1) && (node_isa_reduction == false) && (n->is_Add() || n->is_Mul())) {
1844 // Move invariant vector input into second position to avoid register spilling.
1845 Node* tmp = in1;
1846 in1 = in2;
1847 in2 = tmp;
1848 }
1849 if (node_isa_reduction) {
1850 const Type *arith_type = n->bottom_type();
1851 vn = ReductionNode::make(opc, NULL, in1, in2, arith_type->basic_type());
1852 if (in2->is_Load()) {
1853 vlen_in_bytes = in2->as_LoadVector()->memory_size();
1854 } else {
1855 vlen_in_bytes = in2->as_Vector()->length_in_bytes();
1856 }
1857 } else {
1858 vn = VectorNode::make(opc, in1, in2, vlen, velt_basic_type(n));
1859 vlen_in_bytes = vn->as_Vector()->length_in_bytes();
1860 }
1861 } else {
1862 ShouldNotReachHere();
1863 }
1864 assert(vn != NULL, "sanity");
1865 _igvn.register_new_node_with_optimizer(vn);
1866 _phase->set_ctrl(vn, _phase->get_ctrl(p->at(0)));
1867 for (uint j = 0; j < p->size(); j++) {
1868 Node* pm = p->at(j);
1869 _igvn.replace_node(pm, vn);
1870 }
1871 _igvn._worklist.push(vn);
1872
1873 if (vlen_in_bytes > max_vlen_in_bytes) {
1874 max_vlen = vlen;
1875 max_vlen_in_bytes = vlen_in_bytes;
1876 }
1877 #ifdef ASSERT
1878 if (TraceNewVectors) {
1879 tty->print("new Vector node: ");
1880 vn->dump();
1881 }
1882 #endif
1883 }
1884 }
1885 C->set_max_vector_size(max_vlen_in_bytes);
1886 if (SuperWordLoopUnrollAnalysis) {
1887 if (cl->has_passed_slp()) {
1888 uint slp_max_unroll_factor = cl->slp_max_unroll();
1889 if (slp_max_unroll_factor == max_vlen) {
1890 NOT_PRODUCT(if (TraceSuperWordLoopUnrollAnalysis) tty->print_cr("vector loop(unroll=%d, len=%d)\n", max_vlen, max_vlen_in_bytes*BitsPerByte));
1891 // For atomic unrolled loops which are vector mapped, instigate more unrolling.
1892 cl->set_notpassed_slp();
1893 C->set_major_progress();
1894 cl->mark_do_unroll_only();
1895 }
1896 }
1897 }
1898 }
1899
1900 //------------------------------vector_opd---------------------------
1901 // Create a vector operand for the nodes in pack p for operand: in(opd_idx)
1902 Node* SuperWord::vector_opd(Node_List* p, int opd_idx) {
1903 Node* p0 = p->at(0);
1904 uint vlen = p->size();
1905 Node* opd = p0->in(opd_idx);
1906
1907 if (same_inputs(p, opd_idx)) {
1908 if (opd->is_Vector() || opd->is_LoadVector()) {
1909 assert(((opd_idx != 2) || !VectorNode::is_shift(p0)), "shift's count can't be vector");
1910 return opd; // input is matching vector
1911 }
1912 if ((opd_idx == 2) && VectorNode::is_shift(p0)) {
1913 Compile* C = _phase->C;
1914 Node* cnt = opd;
1915 // Vector instructions do not mask shift count, do it here.
1916 juint mask = (p0->bottom_type() == TypeInt::INT) ? (BitsPerInt - 1) : (BitsPerLong - 1);
1917 const TypeInt* t = opd->find_int_type();
1918 if (t != NULL && t->is_con()) {
1919 juint shift = t->get_con();
1920 if (shift > mask) { // Unsigned cmp
1921 cnt = ConNode::make(TypeInt::make(shift & mask));
1922 }
1923 } else {
1924 if (t == NULL || t->_lo < 0 || t->_hi > (int)mask) {
1925 cnt = ConNode::make(TypeInt::make(mask));
1926 _igvn.register_new_node_with_optimizer(cnt);
1927 cnt = new AndINode(opd, cnt);
1928 _igvn.register_new_node_with_optimizer(cnt);
1929 _phase->set_ctrl(cnt, _phase->get_ctrl(opd));
1930 }
1931 assert(opd->bottom_type()->isa_int(), "int type only");
1932 // Move non constant shift count into vector register.
1933 cnt = VectorNode::shift_count(p0, cnt, vlen, velt_basic_type(p0));
1934 }
1935 if (cnt != opd) {
1936 _igvn.register_new_node_with_optimizer(cnt);
1937 _phase->set_ctrl(cnt, _phase->get_ctrl(opd));
1938 }
1939 return cnt;
1940 }
1941 assert(!opd->is_StoreVector(), "such vector is not expected here");
1942 // Convert scalar input to vector with the same number of elements as
1943 // p0's vector. Use p0's type because size of operand's container in
1944 // vector should match p0's size regardless operand's size.
1945 const Type* p0_t = velt_type(p0);
1946 VectorNode* vn = VectorNode::scalar2vector(opd, vlen, p0_t);
1947
1948 _igvn.register_new_node_with_optimizer(vn);
1949 _phase->set_ctrl(vn, _phase->get_ctrl(opd));
1950 #ifdef ASSERT
1951 if (TraceNewVectors) {
1952 tty->print("new Vector node: ");
1953 vn->dump();
1954 }
1955 #endif
1956 return vn;
1957 }
1958
1959 // Insert pack operation
1960 BasicType bt = velt_basic_type(p0);
1961 PackNode* pk = PackNode::make(opd, vlen, bt);
1962 DEBUG_ONLY( const BasicType opd_bt = opd->bottom_type()->basic_type(); )
1963
1964 for (uint i = 1; i < vlen; i++) {
1965 Node* pi = p->at(i);
1966 Node* in = pi->in(opd_idx);
1967 assert(my_pack(in) == NULL, "Should already have been unpacked");
1968 assert(opd_bt == in->bottom_type()->basic_type(), "all same type");
1969 pk->add_opd(in);
1970 }
1971 _igvn.register_new_node_with_optimizer(pk);
1972 _phase->set_ctrl(pk, _phase->get_ctrl(opd));
1973 #ifdef ASSERT
1974 if (TraceNewVectors) {
1975 tty->print("new Vector node: ");
1976 pk->dump();
1977 }
1978 #endif
1979 return pk;
1980 }
1981
1982 //------------------------------insert_extracts---------------------------
1983 // If a use of pack p is not a vector use, then replace the
1984 // use with an extract operation.
1985 void SuperWord::insert_extracts(Node_List* p) {
1986 if (p->at(0)->is_Store()) return;
1987 assert(_n_idx_list.is_empty(), "empty (node,index) list");
1988
1989 // Inspect each use of each pack member. For each use that is
1990 // not a vector use, replace the use with an extract operation.
1991
1992 for (uint i = 0; i < p->size(); i++) {
1993 Node* def = p->at(i);
1994 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
1995 Node* use = def->fast_out(j);
1996 for (uint k = 0; k < use->req(); k++) {
1997 Node* n = use->in(k);
1998 if (def == n) {
1999 if (!is_vector_use(use, k)) {
2000 _n_idx_list.push(use, k);
2001 }
2002 }
2003 }
2004 }
2005 }
2006
2007 while (_n_idx_list.is_nonempty()) {
2008 Node* use = _n_idx_list.node();
2009 int idx = _n_idx_list.index();
2010 _n_idx_list.pop();
2011 Node* def = use->in(idx);
2012
2013 if (def->is_reduction()) continue;
2014
2015 // Insert extract operation
2016 _igvn.hash_delete(def);
2017 int def_pos = alignment(def) / data_size(def);
2018
2019 Node* ex = ExtractNode::make(def, def_pos, velt_basic_type(def));
2020 _igvn.register_new_node_with_optimizer(ex);
2021 _phase->set_ctrl(ex, _phase->get_ctrl(def));
2022 _igvn.replace_input_of(use, idx, ex);
2023 _igvn._worklist.push(def);
2024
2025 bb_insert_after(ex, bb_idx(def));
2026 set_velt_type(ex, velt_type(def));
2027 }
2028 }
2029
2030 //------------------------------is_vector_use---------------------------
2031 // Is use->in(u_idx) a vector use?
2032 bool SuperWord::is_vector_use(Node* use, int u_idx) {
2033 Node_List* u_pk = my_pack(use);
2034 if (u_pk == NULL) return false;
2035 if (use->is_reduction()) return true;
2036 Node* def = use->in(u_idx);
2037 Node_List* d_pk = my_pack(def);
2038 if (d_pk == NULL) {
2039 // check for scalar promotion
2040 Node* n = u_pk->at(0)->in(u_idx);
2041 for (uint i = 1; i < u_pk->size(); i++) {
2042 if (u_pk->at(i)->in(u_idx) != n) return false;
2043 }
2044 return true;
2045 }
2046 if (u_pk->size() != d_pk->size())
2047 return false;
2048 for (uint i = 0; i < u_pk->size(); i++) {
2049 Node* ui = u_pk->at(i);
2050 Node* di = d_pk->at(i);
2051 if (ui->in(u_idx) != di || alignment(ui) != alignment(di))
2052 return false;
2053 }
2054 return true;
2055 }
2056
2057 //------------------------------construct_bb---------------------------
2058 // Construct reverse postorder list of block members
2059 bool SuperWord::construct_bb() {
2060 Node* entry = bb();
2061
2062 assert(_stk.length() == 0, "stk is empty");
2063 assert(_block.length() == 0, "block is empty");
2064 assert(_data_entry.length() == 0, "data_entry is empty");
2065 assert(_mem_slice_head.length() == 0, "mem_slice_head is empty");
2066 assert(_mem_slice_tail.length() == 0, "mem_slice_tail is empty");
2067
2068 // Find non-control nodes with no inputs from within block,
2069 // create a temporary map from node _idx to bb_idx for use
2070 // by the visited and post_visited sets,
2071 // and count number of nodes in block.
2072 int bb_ct = 0;
2073 for (uint i = 0; i < lpt()->_body.size(); i++) {
2074 Node *n = lpt()->_body.at(i);
2075 set_bb_idx(n, i); // Create a temporary map
2076 if (in_bb(n)) {
2077 if (n->is_LoadStore() || n->is_MergeMem() ||
2078 (n->is_Proj() && !n->as_Proj()->is_CFG())) {
2079 // Bailout if the loop has LoadStore, MergeMem or data Proj
2080 // nodes. Superword optimization does not work with them.
2081 return false;
2082 }
2083 bb_ct++;
2084 if (!n->is_CFG()) {
2085 bool found = false;
2086 for (uint j = 0; j < n->req(); j++) {
2087 Node* def = n->in(j);
2088 if (def && in_bb(def)) {
2089 found = true;
2090 break;
2091 }
2092 }
2093 if (!found) {
2094 assert(n != entry, "can't be entry");
2095 _data_entry.push(n);
2096 }
2097 }
2098 }
2099 }
2100
2101 // Find memory slices (head and tail)
2102 for (DUIterator_Fast imax, i = lp()->fast_outs(imax); i < imax; i++) {
2103 Node *n = lp()->fast_out(i);
2104 if (in_bb(n) && (n->is_Phi() && n->bottom_type() == Type::MEMORY)) {
2105 Node* n_tail = n->in(LoopNode::LoopBackControl);
2106 if (n_tail != n->in(LoopNode::EntryControl)) {
2107 if (!n_tail->is_Mem()) {
2108 assert(n_tail->is_Mem(), "unexpected node for memory slice: %s", n_tail->Name());
2109 return false; // Bailout
2110 }
2111 _mem_slice_head.push(n);
2112 _mem_slice_tail.push(n_tail);
2113 }
2114 }
2115 }
2116
2117 // Create an RPO list of nodes in block
2118
2119 visited_clear();
2120 post_visited_clear();
2121
2122 // Push all non-control nodes with no inputs from within block, then control entry
2123 for (int j = 0; j < _data_entry.length(); j++) {
2124 Node* n = _data_entry.at(j);
2125 visited_set(n);
2126 _stk.push(n);
2127 }
2128 visited_set(entry);
2129 _stk.push(entry);
2130
2131 // Do a depth first walk over out edges
2132 int rpo_idx = bb_ct - 1;
2133 int size;
2134 int reduction_uses = 0;
2135 while ((size = _stk.length()) > 0) {
2136 Node* n = _stk.top(); // Leave node on stack
2137 if (!visited_test_set(n)) {
2138 // forward arc in graph
2139 } else if (!post_visited_test(n)) {
2140 // cross or back arc
2141 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2142 Node *use = n->fast_out(i);
2143 if (in_bb(use) && !visited_test(use) &&
2144 // Don't go around backedge
2145 (!use->is_Phi() || n == entry)) {
2146 if (use->is_reduction()) {
2147 // First see if we can map the reduction on the given system we are on, then
2148 // make a data entry operation for each reduction we see.
2149 BasicType bt = use->bottom_type()->basic_type();
2150 if (ReductionNode::implemented(use->Opcode(), Matcher::min_vector_size(bt), bt)) {
2151 reduction_uses++;
2152 }
2153 }
2154 _stk.push(use);
2155 }
2156 }
2157 if (_stk.length() == size) {
2158 // There were no additional uses, post visit node now
2159 _stk.pop(); // Remove node from stack
2160 assert(rpo_idx >= 0, "");
2161 _block.at_put_grow(rpo_idx, n);
2162 rpo_idx--;
2163 post_visited_set(n);
2164 assert(rpo_idx >= 0 || _stk.is_empty(), "");
2165 }
2166 } else {
2167 _stk.pop(); // Remove post-visited node from stack
2168 }
2169 }//while
2170
2171 int ii_current = -1;
2172 unsigned int load_idx = (unsigned int)-1;
2173 _ii_order.clear();
2174 // Create real map of block indices for nodes
2175 for (int j = 0; j < _block.length(); j++) {
2176 Node* n = _block.at(j);
2177 set_bb_idx(n, j);
2178 if (_do_vector_loop && n->is_Load()) {
2179 if (ii_current == -1) {
2180 ii_current = _clone_map.gen(n->_idx);
2181 _ii_order.push(ii_current);
2182 load_idx = _clone_map.idx(n->_idx);
2183 } else if (_clone_map.idx(n->_idx) == load_idx && _clone_map.gen(n->_idx) != ii_current) {
2184 ii_current = _clone_map.gen(n->_idx);
2185 _ii_order.push(ii_current);
2186 }
2187 }
2188 }//for
2189
2190 // Ensure extra info is allocated.
2191 initialize_bb();
2192
2193 #ifndef PRODUCT
2194 if (_vector_loop_debug && _ii_order.length() > 0) {
2195 tty->print("SuperWord::construct_bb: List of generations: ");
2196 for (int jj = 0; jj < _ii_order.length(); ++jj) {
2197 tty->print(" %d:%d", jj, _ii_order.at(jj));
2198 }
2199 tty->print_cr(" ");
2200 }
2201 if (TraceSuperWord) {
2202 print_bb();
2203 tty->print_cr("\ndata entry nodes: %s", _data_entry.length() > 0 ? "" : "NONE");
2204 for (int m = 0; m < _data_entry.length(); m++) {
2205 tty->print("%3d ", m);
2206 _data_entry.at(m)->dump();
2207 }
2208 tty->print_cr("\nmemory slices: %s", _mem_slice_head.length() > 0 ? "" : "NONE");
2209 for (int m = 0; m < _mem_slice_head.length(); m++) {
2210 tty->print("%3d ", m); _mem_slice_head.at(m)->dump();
2211 tty->print(" "); _mem_slice_tail.at(m)->dump();
2212 }
2213 }
2214 #endif
2215 assert(rpo_idx == -1 && bb_ct == _block.length(), "all block members found");
2216 return (_mem_slice_head.length() > 0) || (reduction_uses > 0) || (_data_entry.length() > 0);
2217 }
2218
2219 //------------------------------initialize_bb---------------------------
2220 // Initialize per node info
2221 void SuperWord::initialize_bb() {
2222 Node* last = _block.at(_block.length() - 1);
2223 grow_node_info(bb_idx(last));
2224 }
2225
2226 //------------------------------bb_insert_after---------------------------
2227 // Insert n into block after pos
2228 void SuperWord::bb_insert_after(Node* n, int pos) {
2229 int n_pos = pos + 1;
2230 // Make room
2231 for (int i = _block.length() - 1; i >= n_pos; i--) {
2232 _block.at_put_grow(i+1, _block.at(i));
2233 }
2234 for (int j = _node_info.length() - 1; j >= n_pos; j--) {
2235 _node_info.at_put_grow(j+1, _node_info.at(j));
2236 }
2237 // Set value
2238 _block.at_put_grow(n_pos, n);
2239 _node_info.at_put_grow(n_pos, SWNodeInfo::initial);
2240 // Adjust map from node->_idx to _block index
2241 for (int i = n_pos; i < _block.length(); i++) {
2242 set_bb_idx(_block.at(i), i);
2243 }
2244 }
2245
2246 //------------------------------compute_max_depth---------------------------
2247 // Compute max depth for expressions from beginning of block
2248 // Use to prune search paths during test for independence.
2249 void SuperWord::compute_max_depth() {
2250 int ct = 0;
2251 bool again;
2252 do {
2253 again = false;
2254 for (int i = 0; i < _block.length(); i++) {
2255 Node* n = _block.at(i);
2256 if (!n->is_Phi()) {
2257 int d_orig = depth(n);
2258 int d_in = 0;
2259 for (DepPreds preds(n, _dg); !preds.done(); preds.next()) {
2260 Node* pred = preds.current();
2261 if (in_bb(pred)) {
2262 d_in = MAX2(d_in, depth(pred));
2263 }
2264 }
2265 if (d_in + 1 != d_orig) {
2266 set_depth(n, d_in + 1);
2267 again = true;
2268 }
2269 }
2270 }
2271 ct++;
2272 } while (again);
2273 #ifndef PRODUCT
2274 if (TraceSuperWord && Verbose)
2275 tty->print_cr("compute_max_depth iterated: %d times", ct);
2276 #endif
2277 }
2278
2279 //-------------------------compute_vector_element_type-----------------------
2280 // Compute necessary vector element type for expressions
2281 // This propagates backwards a narrower integer type when the
2282 // upper bits of the value are not needed.
2283 // Example: char a,b,c; a = b + c;
2284 // Normally the type of the add is integer, but for packed character
2285 // operations the type of the add needs to be char.
2286 void SuperWord::compute_vector_element_type() {
2287 #ifndef PRODUCT
2288 if (TraceSuperWord && Verbose)
2289 tty->print_cr("\ncompute_velt_type:");
2290 #endif
2291
2292 // Initial type
2293 for (int i = 0; i < _block.length(); i++) {
2294 Node* n = _block.at(i);
2295 set_velt_type(n, container_type(n));
2296 }
2297
2298 // Propagate integer narrowed type backwards through operations
2299 // that don't depend on higher order bits
2300 for (int i = _block.length() - 1; i >= 0; i--) {
2301 Node* n = _block.at(i);
2302 // Only integer types need be examined
2303 const Type* vtn = velt_type(n);
2304 if (vtn->basic_type() == T_INT) {
2305 uint start, end;
2306 VectorNode::vector_operands(n, &start, &end);
2307
2308 for (uint j = start; j < end; j++) {
2309 Node* in = n->in(j);
2310 // Don't propagate through a memory
2311 if (!in->is_Mem() && in_bb(in) && velt_type(in)->basic_type() == T_INT &&
2312 data_size(n) < data_size(in)) {
2313 bool same_type = true;
2314 for (DUIterator_Fast kmax, k = in->fast_outs(kmax); k < kmax; k++) {
2315 Node *use = in->fast_out(k);
2316 if (!in_bb(use) || !same_velt_type(use, n)) {
2317 same_type = false;
2318 break;
2319 }
2320 }
2321 if (same_type) {
2322 // For right shifts of small integer types (bool, byte, char, short)
2323 // we need precise information about sign-ness. Only Load nodes have
2324 // this information because Store nodes are the same for signed and
2325 // unsigned values. And any arithmetic operation after a load may
2326 // expand a value to signed Int so such right shifts can't be used
2327 // because vector elements do not have upper bits of Int.
2328 const Type* vt = vtn;
2329 if (VectorNode::is_shift(in)) {
2330 Node* load = in->in(1);
2331 if (load->is_Load() && in_bb(load) && (velt_type(load)->basic_type() == T_INT)) {
2332 vt = velt_type(load);
2333 } else if (in->Opcode() != Op_LShiftI) {
2334 // Widen type to Int to avoid creation of right shift vector
2335 // (align + data_size(s1) check in stmts_can_pack() will fail).
2336 // Note, left shifts work regardless type.
2337 vt = TypeInt::INT;
2338 }
2339 }
2340 set_velt_type(in, vt);
2341 }
2342 }
2343 }
2344 }
2345 }
2346 #ifndef PRODUCT
2347 if (TraceSuperWord && Verbose) {
2348 for (int i = 0; i < _block.length(); i++) {
2349 Node* n = _block.at(i);
2350 velt_type(n)->dump();
2351 tty->print("\t");
2352 n->dump();
2353 }
2354 }
2355 #endif
2356 }
2357
2358 //------------------------------memory_alignment---------------------------
2359 // Alignment within a vector memory reference
2360 int SuperWord::memory_alignment(MemNode* s, int iv_adjust) {
2361 #ifndef PRODUCT
2362 if(TraceSuperWord && Verbose) {
2363 tty->print("SuperWord::memory_alignment within a vector memory reference for %d: ", s->_idx); s->dump();
2364 }
2365 #endif
2366 NOT_PRODUCT(SWPointer::Tracer::Depth ddd(0);)
2367 SWPointer p(s, this, NULL, false);
2368 if (!p.valid()) {
2369 NOT_PRODUCT(if(is_trace_alignment()) tty->print("SWPointer::memory_alignment: SWPointer p invalid, return bottom_align");)
2370 return bottom_align;
2371 }
2372 int vw = vector_width_in_bytes(s);
2373 if (vw < 2) {
2374 NOT_PRODUCT(if(is_trace_alignment()) tty->print_cr("SWPointer::memory_alignment: vector_width_in_bytes < 2, return bottom_align");)
2375 return bottom_align; // No vectors for this type
2376 }
2377 int offset = p.offset_in_bytes();
2378 offset += iv_adjust*p.memory_size();
2379 int off_rem = offset % vw;
2380 int off_mod = off_rem >= 0 ? off_rem : off_rem + vw;
2381 NOT_PRODUCT(if(TraceSuperWord && Verbose) tty->print_cr("SWPointer::memory_alignment: off_rem = %d, off_mod = %d", off_rem, off_mod);)
2382 return off_mod;
2383 }
2384
2385 //---------------------------container_type---------------------------
2386 // Smallest type containing range of values
2387 const Type* SuperWord::container_type(Node* n) {
2388 if (n->is_Mem()) {
2389 BasicType bt = n->as_Mem()->memory_type();
2390 if (n->is_Store() && (bt == T_CHAR)) {
2391 // Use T_SHORT type instead of T_CHAR for stored values because any
2392 // preceding arithmetic operation extends values to signed Int.
2393 bt = T_SHORT;
2394 }
2395 if (n->Opcode() == Op_LoadUB) {
2396 // Adjust type for unsigned byte loads, it is important for right shifts.
2397 // T_BOOLEAN is used because there is no basic type representing type
2398 // TypeInt::UBYTE. Use of T_BOOLEAN for vectors is fine because only
2399 // size (one byte) and sign is important.
2400 bt = T_BOOLEAN;
2401 }
2402 return Type::get_const_basic_type(bt);
2403 }
2404 const Type* t = _igvn.type(n);
2405 if (t->basic_type() == T_INT) {
2406 // A narrow type of arithmetic operations will be determined by
2407 // propagating the type of memory operations.
2408 return TypeInt::INT;
2409 }
2410 return t;
2411 }
2412
2413 bool SuperWord::same_velt_type(Node* n1, Node* n2) {
2414 const Type* vt1 = velt_type(n1);
2415 const Type* vt2 = velt_type(n2);
2416 if (vt1->basic_type() == T_INT && vt2->basic_type() == T_INT) {
2417 // Compare vectors element sizes for integer types.
2418 return data_size(n1) == data_size(n2);
2419 }
2420 return vt1 == vt2;
2421 }
2422
2423 //------------------------------in_packset---------------------------
2424 // Are s1 and s2 in a pack pair and ordered as s1,s2?
2425 bool SuperWord::in_packset(Node* s1, Node* s2) {
2426 for (int i = 0; i < _packset.length(); i++) {
2427 Node_List* p = _packset.at(i);
2428 assert(p->size() == 2, "must be");
2429 if (p->at(0) == s1 && p->at(p->size()-1) == s2) {
2430 return true;
2431 }
2432 }
2433 return false;
2434 }
2435
2436 //------------------------------in_pack---------------------------
2437 // Is s in pack p?
2438 Node_List* SuperWord::in_pack(Node* s, Node_List* p) {
2439 for (uint i = 0; i < p->size(); i++) {
2440 if (p->at(i) == s) {
2441 return p;
2442 }
2443 }
2444 return NULL;
2445 }
2446
2447 //------------------------------remove_pack_at---------------------------
2448 // Remove the pack at position pos in the packset
2449 void SuperWord::remove_pack_at(int pos) {
2450 Node_List* p = _packset.at(pos);
2451 for (uint i = 0; i < p->size(); i++) {
2452 Node* s = p->at(i);
2453 set_my_pack(s, NULL);
2454 }
2455 _packset.remove_at(pos);
2456 }
2457
2458 void SuperWord::packset_sort(int n) {
2459 // simple bubble sort so that we capitalize with O(n) when its already sorted
2460 while (n != 0) {
2461 bool swapped = false;
2462 for (int i = 1; i < n; i++) {
2463 Node_List* q_low = _packset.at(i-1);
2464 Node_List* q_i = _packset.at(i);
2465
2466 // only swap when we find something to swap
2467 if (alignment(q_low->at(0)) > alignment(q_i->at(0))) {
2468 Node_List* t = q_i;
2469 *(_packset.adr_at(i)) = q_low;
2470 *(_packset.adr_at(i-1)) = q_i;
2471 swapped = true;
2472 }
2473 }
2474 if (swapped == false) break;
2475 n--;
2476 }
2477 }
2478
2479 //------------------------------executed_first---------------------------
2480 // Return the node executed first in pack p. Uses the RPO block list
2481 // to determine order.
2482 Node* SuperWord::executed_first(Node_List* p) {
2483 Node* n = p->at(0);
2484 int n_rpo = bb_idx(n);
2485 for (uint i = 1; i < p->size(); i++) {
2486 Node* s = p->at(i);
2487 int s_rpo = bb_idx(s);
2488 if (s_rpo < n_rpo) {
2489 n = s;
2490 n_rpo = s_rpo;
2491 }
2492 }
2493 return n;
2494 }
2495
2496 //------------------------------executed_last---------------------------
2497 // Return the node executed last in pack p.
2498 Node* SuperWord::executed_last(Node_List* p) {
2499 Node* n = p->at(0);
2500 int n_rpo = bb_idx(n);
2501 for (uint i = 1; i < p->size(); i++) {
2502 Node* s = p->at(i);
2503 int s_rpo = bb_idx(s);
2504 if (s_rpo > n_rpo) {
2505 n = s;
2506 n_rpo = s_rpo;
2507 }
2508 }
2509 return n;
2510 }
2511
2512 LoadNode::ControlDependency SuperWord::control_dependency(Node_List* p) {
2513 LoadNode::ControlDependency dep = LoadNode::DependsOnlyOnTest;
2514 for (uint i = 0; i < p->size(); i++) {
2515 Node* n = p->at(i);
2516 assert(n->is_Load(), "only meaningful for loads");
2517 if (!n->depends_only_on_test()) {
2518 dep = LoadNode::Pinned;
2519 }
2520 }
2521 return dep;
2522 }
2523
2524
2525 //----------------------------align_initial_loop_index---------------------------
2526 // Adjust pre-loop limit so that in main loop, a load/store reference
2527 // to align_to_ref will be a position zero in the vector.
2528 // (iv + k) mod vector_align == 0
2529 void SuperWord::align_initial_loop_index(MemNode* align_to_ref) {
2530 CountedLoopNode *main_head = lp()->as_CountedLoop();
2531 assert(main_head->is_main_loop(), "");
2532 CountedLoopEndNode* pre_end = get_pre_loop_end(main_head);
2533 assert(pre_end != NULL, "we must have a correct pre-loop");
2534 Node *pre_opaq1 = pre_end->limit();
2535 assert(pre_opaq1->Opcode() == Op_Opaque1, "");
2536 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
2537 Node *lim0 = pre_opaq->in(1);
2538
2539 // Where we put new limit calculations
2540 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
2541
2542 // Ensure the original loop limit is available from the
2543 // pre-loop Opaque1 node.
2544 Node *orig_limit = pre_opaq->original_loop_limit();
2545 assert(orig_limit != NULL && _igvn.type(orig_limit) != Type::TOP, "");
2546
2547 SWPointer align_to_ref_p(align_to_ref, this, NULL, false);
2548 assert(align_to_ref_p.valid(), "sanity");
2549
2550 // Given:
2551 // lim0 == original pre loop limit
2552 // V == v_align (power of 2)
2553 // invar == extra invariant piece of the address expression
2554 // e == offset [ +/- invar ]
2555 //
2556 // When reassociating expressions involving '%' the basic rules are:
2557 // (a - b) % k == 0 => a % k == b % k
2558 // and:
2559 // (a + b) % k == 0 => a % k == (k - b) % k
2560 //
2561 // For stride > 0 && scale > 0,
2562 // Derive the new pre-loop limit "lim" such that the two constraints:
2563 // (1) lim = lim0 + N (where N is some positive integer < V)
2564 // (2) (e + lim) % V == 0
2565 // are true.
2566 //
2567 // Substituting (1) into (2),
2568 // (e + lim0 + N) % V == 0
2569 // solve for N:
2570 // N = (V - (e + lim0)) % V
2571 // substitute back into (1), so that new limit
2572 // lim = lim0 + (V - (e + lim0)) % V
2573 //
2574 // For stride > 0 && scale < 0
2575 // Constraints:
2576 // lim = lim0 + N
2577 // (e - lim) % V == 0
2578 // Solving for lim:
2579 // (e - lim0 - N) % V == 0
2580 // N = (e - lim0) % V
2581 // lim = lim0 + (e - lim0) % V
2582 //
2583 // For stride < 0 && scale > 0
2584 // Constraints:
2585 // lim = lim0 - N
2586 // (e + lim) % V == 0
2587 // Solving for lim:
2588 // (e + lim0 - N) % V == 0
2589 // N = (e + lim0) % V
2590 // lim = lim0 - (e + lim0) % V
2591 //
2592 // For stride < 0 && scale < 0
2593 // Constraints:
2594 // lim = lim0 - N
2595 // (e - lim) % V == 0
2596 // Solving for lim:
2597 // (e - lim0 + N) % V == 0
2598 // N = (V - (e - lim0)) % V
2599 // lim = lim0 - (V - (e - lim0)) % V
2600
2601 int vw = vector_width_in_bytes(align_to_ref);
2602 int stride = iv_stride();
2603 int scale = align_to_ref_p.scale_in_bytes();
2604 int elt_size = align_to_ref_p.memory_size();
2605 int v_align = vw / elt_size;
2606 assert(v_align > 1, "sanity");
2607 int offset = align_to_ref_p.offset_in_bytes() / elt_size;
2608 Node *offsn = _igvn.intcon(offset);
2609
2610 Node *e = offsn;
2611 if (align_to_ref_p.invar() != NULL) {
2612 // incorporate any extra invariant piece producing (offset +/- invar) >>> log2(elt)
2613 Node* log2_elt = _igvn.intcon(exact_log2(elt_size));
2614 Node* aref = new URShiftINode(align_to_ref_p.invar(), log2_elt);
2615 _igvn.register_new_node_with_optimizer(aref);
2616 _phase->set_ctrl(aref, pre_ctrl);
2617 if (align_to_ref_p.negate_invar()) {
2618 e = new SubINode(e, aref);
2619 } else {
2620 e = new AddINode(e, aref);
2621 }
2622 _igvn.register_new_node_with_optimizer(e);
2623 _phase->set_ctrl(e, pre_ctrl);
2624 }
2625 if (vw > ObjectAlignmentInBytes) {
2626 // incorporate base e +/- base && Mask >>> log2(elt)
2627 Node* xbase = new CastP2XNode(NULL, align_to_ref_p.base());
2628 _igvn.register_new_node_with_optimizer(xbase);
2629 #ifdef _LP64
2630 xbase = new ConvL2INode(xbase);
2631 _igvn.register_new_node_with_optimizer(xbase);
2632 #endif
2633 Node* mask = _igvn.intcon(vw-1);
2634 Node* masked_xbase = new AndINode(xbase, mask);
2635 _igvn.register_new_node_with_optimizer(masked_xbase);
2636 Node* log2_elt = _igvn.intcon(exact_log2(elt_size));
2637 Node* bref = new URShiftINode(masked_xbase, log2_elt);
2638 _igvn.register_new_node_with_optimizer(bref);
2639 _phase->set_ctrl(bref, pre_ctrl);
2640 e = new AddINode(e, bref);
2641 _igvn.register_new_node_with_optimizer(e);
2642 _phase->set_ctrl(e, pre_ctrl);
2643 }
2644
2645 // compute e +/- lim0
2646 if (scale < 0) {
2647 e = new SubINode(e, lim0);
2648 } else {
2649 e = new AddINode(e, lim0);
2650 }
2651 _igvn.register_new_node_with_optimizer(e);
2652 _phase->set_ctrl(e, pre_ctrl);
2653
2654 if (stride * scale > 0) {
2655 // compute V - (e +/- lim0)
2656 Node* va = _igvn.intcon(v_align);
2657 e = new SubINode(va, e);
2658 _igvn.register_new_node_with_optimizer(e);
2659 _phase->set_ctrl(e, pre_ctrl);
2660 }
2661 // compute N = (exp) % V
2662 Node* va_msk = _igvn.intcon(v_align - 1);
2663 Node* N = new AndINode(e, va_msk);
2664 _igvn.register_new_node_with_optimizer(N);
2665 _phase->set_ctrl(N, pre_ctrl);
2666
2667 // substitute back into (1), so that new limit
2668 // lim = lim0 + N
2669 Node* lim;
2670 if (stride < 0) {
2671 lim = new SubINode(lim0, N);
2672 } else {
2673 lim = new AddINode(lim0, N);
2674 }
2675 _igvn.register_new_node_with_optimizer(lim);
2676 _phase->set_ctrl(lim, pre_ctrl);
2677 Node* constrained =
2678 (stride > 0) ? (Node*) new MinINode(lim, orig_limit)
2679 : (Node*) new MaxINode(lim, orig_limit);
2680 _igvn.register_new_node_with_optimizer(constrained);
2681 _phase->set_ctrl(constrained, pre_ctrl);
2682 _igvn.hash_delete(pre_opaq);
2683 pre_opaq->set_req(1, constrained);
2684 }
2685
2686 //----------------------------get_pre_loop_end---------------------------
2687 // Find pre loop end from main loop. Returns null if none.
2688 CountedLoopEndNode* SuperWord::get_pre_loop_end(CountedLoopNode *cl) {
2689 Node *ctrl = cl->in(LoopNode::EntryControl);
2690 if (!ctrl->is_IfTrue() && !ctrl->is_IfFalse()) return NULL;
2691 Node *iffm = ctrl->in(0);
2692 if (!iffm->is_If()) return NULL;
2693 Node *p_f = iffm->in(0);
2694 if (!p_f->is_IfFalse()) return NULL;
2695 if (!p_f->in(0)->is_CountedLoopEnd()) return NULL;
2696 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2697 CountedLoopNode* loop_node = pre_end->loopnode();
2698 if (loop_node == NULL || !loop_node->is_pre_loop()) return NULL;
2699 return pre_end;
2700 }
2701
2702
2703 //------------------------------init---------------------------
2704 void SuperWord::init() {
2705 _dg.init();
2706 _packset.clear();
2707 _disjoint_ptrs.clear();
2708 _block.clear();
2709 _data_entry.clear();
2710 _mem_slice_head.clear();
2711 _mem_slice_tail.clear();
2712 _iteration_first.clear();
2713 _iteration_last.clear();
2714 _node_info.clear();
2715 _align_to_ref = NULL;
2716 _lpt = NULL;
2717 _lp = NULL;
2718 _bb = NULL;
2719 _iv = NULL;
2720 _race_possible = 0;
2721 _early_return = false;
2722 _num_work_vecs = 0;
2723 _num_reductions = 0;
2724 }
2725
2726 //------------------------------restart---------------------------
2727 void SuperWord::restart() {
2728 _dg.init();
2729 _packset.clear();
2730 _disjoint_ptrs.clear();
2731 _block.clear();
2732 _data_entry.clear();
2733 _mem_slice_head.clear();
2734 _mem_slice_tail.clear();
2735 _node_info.clear();
2736 }
2737
2738 //------------------------------print_packset---------------------------
2739 void SuperWord::print_packset() {
2740 #ifndef PRODUCT
2741 tty->print_cr("packset");
2742 for (int i = 0; i < _packset.length(); i++) {
2743 tty->print_cr("Pack: %d", i);
2744 Node_List* p = _packset.at(i);
2745 print_pack(p);
2746 }
2747 #endif
2748 }
2749
2750 //------------------------------print_pack---------------------------
2751 void SuperWord::print_pack(Node_List* p) {
2752 for (uint i = 0; i < p->size(); i++) {
2753 print_stmt(p->at(i));
2754 }
2755 }
2756
2757 //------------------------------print_bb---------------------------
2758 void SuperWord::print_bb() {
2759 #ifndef PRODUCT
2760 tty->print_cr("\nBlock");
2761 for (int i = 0; i < _block.length(); i++) {
2762 Node* n = _block.at(i);
2763 tty->print("%d ", i);
2764 if (n) {
2765 n->dump();
2766 }
2767 }
2768 #endif
2769 }
2770
2771 //------------------------------print_stmt---------------------------
2772 void SuperWord::print_stmt(Node* s) {
2773 #ifndef PRODUCT
2774 tty->print(" align: %d \t", alignment(s));
2775 s->dump();
2776 #endif
2777 }
2778
2779 //------------------------------blank---------------------------
2780 char* SuperWord::blank(uint depth) {
2781 static char blanks[101];
2782 assert(depth < 101, "too deep");
2783 for (uint i = 0; i < depth; i++) blanks[i] = ' ';
2784 blanks[depth] = '\0';
2785 return blanks;
2786 }
2787
2788
2789 //==============================SWPointer===========================
2790 #ifndef PRODUCT
2791 int SWPointer::Tracer::_depth = 0;
2792 #endif
2793 //----------------------------SWPointer------------------------
2794 SWPointer::SWPointer(MemNode* mem, SuperWord* slp, Node_Stack *nstack, bool analyze_only) :
2795 _mem(mem), _slp(slp), _base(NULL), _adr(NULL),
2796 _scale(0), _offset(0), _invar(NULL), _negate_invar(false),
2797 _nstack(nstack), _analyze_only(analyze_only),
2798 _stack_idx(0)
2799 #ifndef PRODUCT
2800 , _tracer(slp)
2801 #endif
2802 {
2803 NOT_PRODUCT(_tracer.ctor_1(mem);)
2804
2805 Node* adr = mem->in(MemNode::Address);
2806 if (!adr->is_AddP()) {
2807 assert(!valid(), "too complex");
2808 return;
2809 }
2810 // Match AddP(base, AddP(ptr, k*iv [+ invariant]), constant)
2811 Node* base = adr->in(AddPNode::Base);
2812 // The base address should be loop invariant
2813 if (!invariant(base)) {
2814 assert(!valid(), "base address is loop variant");
2815 return;
2816 }
2817 //unsafe reference could not be aligned appropriately without runtime checking
2818 if (base == NULL || base->bottom_type() == Type::TOP) {
2819 assert(!valid(), "unsafe access");
2820 return;
2821 }
2822
2823 NOT_PRODUCT(if(_slp->is_trace_alignment()) _tracer.store_depth();)
2824 NOT_PRODUCT(_tracer.ctor_2(adr);)
2825
2826 int i;
2827 for (i = 0; i < 3; i++) {
2828 NOT_PRODUCT(_tracer.ctor_3(adr, i);)
2829
2830 if (!scaled_iv_plus_offset(adr->in(AddPNode::Offset))) {
2831 assert(!valid(), "too complex");
2832 return;
2833 }
2834 adr = adr->in(AddPNode::Address);
2835 NOT_PRODUCT(_tracer.ctor_4(adr, i);)
2836
2837 if (base == adr || !adr->is_AddP()) {
2838 NOT_PRODUCT(_tracer.ctor_5(adr, base, i);)
2839 break; // stop looking at addp's
2840 }
2841 }
2842 NOT_PRODUCT(if(_slp->is_trace_alignment()) _tracer.restore_depth();)
2843 NOT_PRODUCT(_tracer.ctor_6(mem);)
2844
2845 _base = base;
2846 _adr = adr;
2847 assert(valid(), "Usable");
2848 }
2849
2850 // Following is used to create a temporary object during
2851 // the pattern match of an address expression.
2852 SWPointer::SWPointer(SWPointer* p) :
2853 _mem(p->_mem), _slp(p->_slp), _base(NULL), _adr(NULL),
2854 _scale(0), _offset(0), _invar(NULL), _negate_invar(false),
2855 _nstack(p->_nstack), _analyze_only(p->_analyze_only),
2856 _stack_idx(p->_stack_idx)
2857 #ifndef PRODUCT
2858 , _tracer(p->_slp)
2859 #endif
2860 {}
2861
2862
2863 bool SWPointer::invariant(Node* n) {
2864 NOT_PRODUCT(Tracer::Depth dd;)
2865 Node *n_c = phase()->get_ctrl(n);
2866 NOT_PRODUCT(_tracer.invariant_1(n, n_c);)
2867 return !lpt()->is_member(phase()->get_loop(n_c));
2868 }
2869 //------------------------scaled_iv_plus_offset--------------------
2870 // Match: k*iv + offset
2871 // where: k is a constant that maybe zero, and
2872 // offset is (k2 [+/- invariant]) where k2 maybe zero and invariant is optional
2873 bool SWPointer::scaled_iv_plus_offset(Node* n) {
2874 NOT_PRODUCT(Tracer::Depth ddd;)
2875 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_1(n);)
2876
2877 if (scaled_iv(n)) {
2878 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_2(n);)
2879 return true;
2880 }
2881
2882 if (offset_plus_k(n)) {
2883 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_3(n);)
2884 return true;
2885 }
2886
2887 int opc = n->Opcode();
2888 if (opc == Op_AddI) {
2889 if (scaled_iv(n->in(1)) && offset_plus_k(n->in(2))) {
2890 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_4(n);)
2891 return true;
2892 }
2893 if (scaled_iv(n->in(2)) && offset_plus_k(n->in(1))) {
2894 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_5(n);)
2895 return true;
2896 }
2897 } else if (opc == Op_SubI) {
2898 if (scaled_iv(n->in(1)) && offset_plus_k(n->in(2), true)) {
2899 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_6(n);)
2900 return true;
2901 }
2902 if (scaled_iv(n->in(2)) && offset_plus_k(n->in(1))) {
2903 _scale *= -1;
2904 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_7(n);)
2905 return true;
2906 }
2907 }
2908
2909 NOT_PRODUCT(_tracer.scaled_iv_plus_offset_8(n);)
2910 return false;
2911 }
2912
2913 //----------------------------scaled_iv------------------------
2914 // Match: k*iv where k is a constant that's not zero
2915 bool SWPointer::scaled_iv(Node* n) {
2916 NOT_PRODUCT(Tracer::Depth ddd;)
2917 NOT_PRODUCT(_tracer.scaled_iv_1(n);)
2918
2919 if (_scale != 0) { // already found a scale
2920 NOT_PRODUCT(_tracer.scaled_iv_2(n, _scale);)
2921 return false;
2922 }
2923
2924 if (n == iv()) {
2925 _scale = 1;
2926 NOT_PRODUCT(_tracer.scaled_iv_3(n, _scale);)
2927 return true;
2928 }
2929 if (_analyze_only && (invariant(n) == false)) {
2930 _nstack->push(n, _stack_idx++);
2931 }
2932
2933 int opc = n->Opcode();
2934 if (opc == Op_MulI) {
2935 if (n->in(1) == iv() && n->in(2)->is_Con()) {
2936 _scale = n->in(2)->get_int();
2937 NOT_PRODUCT(_tracer.scaled_iv_4(n, _scale);)
2938 return true;
2939 } else if (n->in(2) == iv() && n->in(1)->is_Con()) {
2940 _scale = n->in(1)->get_int();
2941 NOT_PRODUCT(_tracer.scaled_iv_5(n, _scale);)
2942 return true;
2943 }
2944 } else if (opc == Op_LShiftI) {
2945 if (n->in(1) == iv() && n->in(2)->is_Con()) {
2946 _scale = 1 << n->in(2)->get_int();
2947 NOT_PRODUCT(_tracer.scaled_iv_6(n, _scale);)
2948 return true;
2949 }
2950 } else if (opc == Op_ConvI2L) {
2951 if (scaled_iv_plus_offset(n->in(1))) {
2952 NOT_PRODUCT(_tracer.scaled_iv_7(n);)
2953 return true;
2954 }
2955 } else if (opc == Op_LShiftL) {
2956 if (!has_iv() && _invar == NULL) {
2957 // Need to preserve the current _offset value, so
2958 // create a temporary object for this expression subtree.
2959 // Hacky, so should re-engineer the address pattern match.
2960 NOT_PRODUCT(Tracer::Depth dddd;)
2961 SWPointer tmp(this);
2962 NOT_PRODUCT(_tracer.scaled_iv_8(n, &tmp);)
2963
2964 if (tmp.scaled_iv_plus_offset(n->in(1))) {
2965 if (tmp._invar == NULL || _slp->do_vector_loop()) {
2966 int mult = 1 << n->in(2)->get_int();
2967 _scale = tmp._scale * mult;
2968 _offset += tmp._offset * mult;
2969 NOT_PRODUCT(_tracer.scaled_iv_9(n, _scale, _offset, mult);)
2970 return true;
2971 }
2972 }
2973 }
2974 }
2975 NOT_PRODUCT(_tracer.scaled_iv_10(n);)
2976 return false;
2977 }
2978
2979 //----------------------------offset_plus_k------------------------
2980 // Match: offset is (k [+/- invariant])
2981 // where k maybe zero and invariant is optional, but not both.
2982 bool SWPointer::offset_plus_k(Node* n, bool negate) {
2983 NOT_PRODUCT(Tracer::Depth ddd;)
2984 NOT_PRODUCT(_tracer.offset_plus_k_1(n);)
2985
2986 int opc = n->Opcode();
2987 if (opc == Op_ConI) {
2988 _offset += negate ? -(n->get_int()) : n->get_int();
2989 NOT_PRODUCT(_tracer.offset_plus_k_2(n, _offset);)
2990 return true;
2991 } else if (opc == Op_ConL) {
2992 // Okay if value fits into an int
2993 const TypeLong* t = n->find_long_type();
2994 if (t->higher_equal(TypeLong::INT)) {
2995 jlong loff = n->get_long();
2996 jint off = (jint)loff;
2997 _offset += negate ? -off : loff;
2998 NOT_PRODUCT(_tracer.offset_plus_k_3(n, _offset);)
2999 return true;
3000 }
3001 NOT_PRODUCT(_tracer.offset_plus_k_4(n);)
3002 return false;
3003 }
3004 if (_invar != NULL) { // already has an invariant
3005 NOT_PRODUCT(_tracer.offset_plus_k_5(n, _invar);)
3006 return false;
3007 }
3008
3009 if (_analyze_only && (invariant(n) == false)) {
3010 _nstack->push(n, _stack_idx++);
3011 }
3012 if (opc == Op_AddI) {
3013 if (n->in(2)->is_Con() && invariant(n->in(1))) {
3014 _negate_invar = negate;
3015 _invar = n->in(1);
3016 _offset += negate ? -(n->in(2)->get_int()) : n->in(2)->get_int();
3017 NOT_PRODUCT(_tracer.offset_plus_k_6(n, _invar, _negate_invar, _offset);)
3018 return true;
3019 } else if (n->in(1)->is_Con() && invariant(n->in(2))) {
3020 _offset += negate ? -(n->in(1)->get_int()) : n->in(1)->get_int();
3021 _negate_invar = negate;
3022 _invar = n->in(2);
3023 NOT_PRODUCT(_tracer.offset_plus_k_7(n, _invar, _negate_invar, _offset);)
3024 return true;
3025 }
3026 }
3027 if (opc == Op_SubI) {
3028 if (n->in(2)->is_Con() && invariant(n->in(1))) {
3029 _negate_invar = negate;
3030 _invar = n->in(1);
3031 _offset += !negate ? -(n->in(2)->get_int()) : n->in(2)->get_int();
3032 NOT_PRODUCT(_tracer.offset_plus_k_8(n, _invar, _negate_invar, _offset);)
3033 return true;
3034 } else if (n->in(1)->is_Con() && invariant(n->in(2))) {
3035 _offset += negate ? -(n->in(1)->get_int()) : n->in(1)->get_int();
3036 _negate_invar = !negate;
3037 _invar = n->in(2);
3038 NOT_PRODUCT(_tracer.offset_plus_k_9(n, _invar, _negate_invar, _offset);)
3039 return true;
3040 }
3041 }
3042 if (invariant(n)) {
3043 _negate_invar = negate;
3044 _invar = n;
3045 NOT_PRODUCT(_tracer.offset_plus_k_10(n, _invar, _negate_invar, _offset);)
3046 return true;
3047 }
3048
3049 NOT_PRODUCT(_tracer.offset_plus_k_11(n);)
3050 return false;
3051 }
3052
3053 //----------------------------print------------------------
3054 void SWPointer::print() {
3055 #ifndef PRODUCT
3056 tty->print("base: %d adr: %d scale: %d offset: %d invar: %c%d\n",
3057 _base != NULL ? _base->_idx : 0,
3058 _adr != NULL ? _adr->_idx : 0,
3059 _scale, _offset,
3060 _negate_invar?'-':'+',
3061 _invar != NULL ? _invar->_idx : 0);
3062 #endif
3063 }
3064
3065 //----------------------------tracing------------------------
3066 #ifndef PRODUCT
3067 void SWPointer::Tracer::print_depth() {
3068 for (int ii = 0; ii<_depth; ++ii) tty->print(" ");
3069 }
3070
3071 void SWPointer::Tracer::ctor_1 (Node* mem) {
3072 if(_slp->is_trace_alignment()) {
3073 print_depth(); tty->print(" %d SWPointer::SWPointer: start alignment analysis", mem->_idx); mem->dump();
3074 }
3075 }
3076
3077 void SWPointer::Tracer::ctor_2(Node* adr) {
3078 if(_slp->is_trace_alignment()) {
3079 //store_depth();
3080 inc_depth();
3081 print_depth(); tty->print(" %d (adr) SWPointer::SWPointer: ", adr->_idx); adr->dump();
3082 inc_depth();
3083 print_depth(); tty->print(" %d (base) SWPointer::SWPointer: ", adr->in(AddPNode::Base)->_idx); adr->in(AddPNode::Base)->dump();
3084 }
3085 }
3086
3087 void SWPointer::Tracer::ctor_3(Node* adr, int i) {
3088 if(_slp->is_trace_alignment()) {
3089 inc_depth();
3090 Node* offset = adr->in(AddPNode::Offset);
3091 print_depth(); tty->print(" %d (offset) SWPointer::SWPointer: i = %d: ", offset->_idx, i); offset->dump();
3092 }
3093 }
3094
3095 void SWPointer::Tracer::ctor_4(Node* adr, int i) {
3096 if(_slp->is_trace_alignment()) {
3097 inc_depth();
3098 print_depth(); tty->print(" %d (adr) SWPointer::SWPointer: i = %d: ", adr->_idx, i); adr->dump();
3099 }
3100 }
3101
3102 void SWPointer::Tracer::ctor_5(Node* adr, Node* base, int i) {
3103 if(_slp->is_trace_alignment()) {
3104 inc_depth();
3105 if (base == adr) {
3106 print_depth(); tty->print_cr(" \\ %d (adr) == %d (base) SWPointer::SWPointer: breaking analysis at i = %d", adr->_idx, base->_idx, i);
3107 } else if (!adr->is_AddP()) {
3108 print_depth(); tty->print_cr(" \\ %d (adr) is NOT Addp SWPointer::SWPointer: breaking analysis at i = %d", adr->_idx, i);
3109 }
3110 }
3111 }
3112
3113 void SWPointer::Tracer::ctor_6(Node* mem) {
3114 if(_slp->is_trace_alignment()) {
3115 //restore_depth();
3116 print_depth(); tty->print_cr(" %d (adr) SWPointer::SWPointer: stop analysis", mem->_idx);
3117 }
3118 }
3119
3120 void SWPointer::Tracer::invariant_1(Node *n, Node *n_c) {
3121 if (_slp->do_vector_loop() && _slp->is_debug() && _slp->_lpt->is_member(_slp->_phase->get_loop(n_c)) != (int)_slp->in_bb(n)) {
3122 int is_member = _slp->_lpt->is_member(_slp->_phase->get_loop(n_c));
3123 int in_bb = _slp->in_bb(n);
3124 print_depth(); tty->print(" \\ "); tty->print_cr(" %d SWPointer::invariant conditions differ: n_c %d", n->_idx, n_c->_idx);
3125 print_depth(); tty->print(" \\ "); tty->print_cr("is_member %d, in_bb %d", is_member, in_bb);
3126 print_depth(); tty->print(" \\ "); n->dump();
3127 print_depth(); tty->print(" \\ "); n_c->dump();
3128 }
3129 }
3130
3131 void SWPointer::Tracer::scaled_iv_plus_offset_1(Node* n) {
3132 if(_slp->is_trace_alignment()) {
3133 print_depth(); tty->print(" %d SWPointer::scaled_iv_plus_offset testing node: ", n->_idx);
3134 n->dump();
3135 }
3136 }
3137
3138 void SWPointer::Tracer::scaled_iv_plus_offset_2(Node* n) {
3139 if(_slp->is_trace_alignment()) {
3140 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: PASSED", n->_idx);
3141 }
3142 }
3143
3144 void SWPointer::Tracer::scaled_iv_plus_offset_3(Node* n) {
3145 if(_slp->is_trace_alignment()) {
3146 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: PASSED", n->_idx);
3147 }
3148 }
3149
3150 void SWPointer::Tracer::scaled_iv_plus_offset_4(Node* n) {
3151 if(_slp->is_trace_alignment()) {
3152 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: Op_AddI PASSED", n->_idx);
3153 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(1) is scaled_iv: ", n->in(1)->_idx); n->in(1)->dump();
3154 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(2) is offset_plus_k: ", n->in(2)->_idx); n->in(2)->dump();
3155 }
3156 }
3157
3158 void SWPointer::Tracer::scaled_iv_plus_offset_5(Node* n) {
3159 if(_slp->is_trace_alignment()) {
3160 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: Op_AddI PASSED", n->_idx);
3161 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(2) is scaled_iv: ", n->in(2)->_idx); n->in(2)->dump();
3162 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(1) is offset_plus_k: ", n->in(1)->_idx); n->in(1)->dump();
3163 }
3164 }
3165
3166 void SWPointer::Tracer::scaled_iv_plus_offset_6(Node* n) {
3167 if(_slp->is_trace_alignment()) {
3168 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: Op_SubI PASSED", n->_idx);
3169 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(1) is scaled_iv: ", n->in(1)->_idx); n->in(1)->dump();
3170 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(2) is offset_plus_k: ", n->in(2)->_idx); n->in(2)->dump();
3171 }
3172 }
3173
3174 void SWPointer::Tracer::scaled_iv_plus_offset_7(Node* n) {
3175 if(_slp->is_trace_alignment()) {
3176 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: Op_SubI PASSED", n->_idx);
3177 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(2) is scaled_iv: ", n->in(2)->_idx); n->in(2)->dump();
3178 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv_plus_offset: in(1) is offset_plus_k: ", n->in(1)->_idx); n->in(1)->dump();
3179 }
3180 }
3181
3182 void SWPointer::Tracer::scaled_iv_plus_offset_8(Node* n) {
3183 if(_slp->is_trace_alignment()) {
3184 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv_plus_offset: FAILED", n->_idx);
3185 }
3186 }
3187
3188 void SWPointer::Tracer::scaled_iv_1(Node* n) {
3189 if(_slp->is_trace_alignment()) {
3190 print_depth(); tty->print(" %d SWPointer::scaled_iv: testing node: ", n->_idx); n->dump();
3191 }
3192 }
3193
3194 void SWPointer::Tracer::scaled_iv_2(Node* n, int scale) {
3195 if(_slp->is_trace_alignment()) {
3196 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: FAILED since another _scale has been detected before", n->_idx);
3197 print_depth(); tty->print_cr(" \\ SWPointer::scaled_iv: _scale (%d) != 0", scale);
3198 }
3199 }
3200
3201 void SWPointer::Tracer::scaled_iv_3(Node* n, int scale) {
3202 if(_slp->is_trace_alignment()) {
3203 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: is iv, setting _scale = %d", n->_idx, scale);
3204 }
3205 }
3206
3207 void SWPointer::Tracer::scaled_iv_4(Node* n, int scale) {
3208 if(_slp->is_trace_alignment()) {
3209 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: Op_MulI PASSED, setting _scale = %d", n->_idx, scale);
3210 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(1) is iv: ", n->in(1)->_idx); n->in(1)->dump();
3211 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(2) is Con: ", n->in(2)->_idx); n->in(2)->dump();
3212 }
3213 }
3214
3215 void SWPointer::Tracer::scaled_iv_5(Node* n, int scale) {
3216 if(_slp->is_trace_alignment()) {
3217 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: Op_MulI PASSED, setting _scale = %d", n->_idx, scale);
3218 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(2) is iv: ", n->in(2)->_idx); n->in(2)->dump();
3219 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(1) is Con: ", n->in(1)->_idx); n->in(1)->dump();
3220 }
3221 }
3222
3223 void SWPointer::Tracer::scaled_iv_6(Node* n, int scale) {
3224 if(_slp->is_trace_alignment()) {
3225 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: Op_LShiftI PASSED, setting _scale = %d", n->_idx, scale);
3226 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(1) is iv: ", n->in(1)->_idx); n->in(1)->dump();
3227 print_depth(); tty->print(" \\ %d SWPointer::scaled_iv: in(2) is Con: ", n->in(2)->_idx); n->in(2)->dump();
3228 }
3229 }
3230
3231 void SWPointer::Tracer::scaled_iv_7(Node* n) {
3232 if(_slp->is_trace_alignment()) {
3233 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: Op_ConvI2L PASSED", n->_idx);
3234 print_depth(); tty->print_cr(" \\ SWPointer::scaled_iv: in(1) %d is scaled_iv_plus_offset: ", n->in(1)->_idx);
3235 inc_depth(); inc_depth();
3236 print_depth(); n->in(1)->dump();
3237 dec_depth(); dec_depth();
3238 }
3239 }
3240
3241 void SWPointer::Tracer::scaled_iv_8(Node* n, SWPointer* tmp) {
3242 if(_slp->is_trace_alignment()) {
3243 print_depth(); tty->print(" %d SWPointer::scaled_iv: Op_LShiftL, creating tmp SWPointer: ", n->_idx); tmp->print();
3244 }
3245 }
3246
3247 void SWPointer::Tracer::scaled_iv_9(Node* n, int scale, int _offset, int mult) {
3248 if(_slp->is_trace_alignment()) {
3249 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: Op_LShiftL PASSED, setting _scale = %d, _offset = %d", n->_idx, scale, _offset);
3250 print_depth(); tty->print_cr(" \\ SWPointer::scaled_iv: in(1) %d is scaled_iv_plus_offset, in(2) %d used to get mult = %d: _scale = %d, _offset = %d",
3251 n->in(1)->_idx, n->in(2)->_idx, mult, scale, _offset);
3252 inc_depth(); inc_depth();
3253 print_depth(); n->in(1)->dump();
3254 print_depth(); n->in(2)->dump();
3255 dec_depth(); dec_depth();
3256 }
3257 }
3258
3259 void SWPointer::Tracer::scaled_iv_10(Node* n) {
3260 if(_slp->is_trace_alignment()) {
3261 print_depth(); tty->print_cr(" %d SWPointer::scaled_iv: FAILED", n->_idx);
3262 }
3263 }
3264
3265 void SWPointer::Tracer::offset_plus_k_1(Node* n) {
3266 if(_slp->is_trace_alignment()) {
3267 print_depth(); tty->print(" %d SWPointer::offset_plus_k: testing node: ", n->_idx); n->dump();
3268 }
3269 }
3270
3271 void SWPointer::Tracer::offset_plus_k_2(Node* n, int _offset) {
3272 if(_slp->is_trace_alignment()) {
3273 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_ConI PASSED, setting _offset = %d", n->_idx, _offset);
3274 }
3275 }
3276
3277 void SWPointer::Tracer::offset_plus_k_3(Node* n, int _offset) {
3278 if(_slp->is_trace_alignment()) {
3279 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_ConL PASSED, setting _offset = %d", n->_idx, _offset);
3280 }
3281 }
3282
3283 void SWPointer::Tracer::offset_plus_k_4(Node* n) {
3284 if(_slp->is_trace_alignment()) {
3285 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: FAILED", n->_idx);
3286 print_depth(); tty->print_cr(" \\ " JLONG_FORMAT " SWPointer::offset_plus_k: Op_ConL FAILED, k is too big", n->get_long());
3287 }
3288 }
3289
3290 void SWPointer::Tracer::offset_plus_k_5(Node* n, Node* _invar) {
3291 if(_slp->is_trace_alignment()) {
3292 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: FAILED since another invariant has been detected before", n->_idx);
3293 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: _invar != NULL: ", _invar->_idx); _invar->dump();
3294 }
3295 }
3296
3297 void SWPointer::Tracer::offset_plus_k_6(Node* n, Node* _invar, bool _negate_invar, int _offset) {
3298 if(_slp->is_trace_alignment()) {
3299 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_AddI PASSED, setting _negate_invar = %d, _invar = %d, _offset = %d",
3300 n->_idx, _negate_invar, _invar->_idx, _offset);
3301 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(2) is Con: ", n->in(2)->_idx); n->in(2)->dump();
3302 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(1) is invariant: ", _invar->_idx); _invar->dump();
3303 }
3304 }
3305
3306 void SWPointer::Tracer::offset_plus_k_7(Node* n, Node* _invar, bool _negate_invar, int _offset) {
3307 if(_slp->is_trace_alignment()) {
3308 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_AddI PASSED, setting _negate_invar = %d, _invar = %d, _offset = %d",
3309 n->_idx, _negate_invar, _invar->_idx, _offset);
3310 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(1) is Con: ", n->in(1)->_idx); n->in(1)->dump();
3311 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(2) is invariant: ", _invar->_idx); _invar->dump();
3312 }
3313 }
3314
3315 void SWPointer::Tracer::offset_plus_k_8(Node* n, Node* _invar, bool _negate_invar, int _offset) {
3316 if(_slp->is_trace_alignment()) {
3317 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_SubI is PASSED, setting _negate_invar = %d, _invar = %d, _offset = %d",
3318 n->_idx, _negate_invar, _invar->_idx, _offset);
3319 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(2) is Con: ", n->in(2)->_idx); n->in(2)->dump();
3320 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(1) is invariant: ", _invar->_idx); _invar->dump();
3321 }
3322 }
3323
3324 void SWPointer::Tracer::offset_plus_k_9(Node* n, Node* _invar, bool _negate_invar, int _offset) {
3325 if(_slp->is_trace_alignment()) {
3326 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: Op_SubI PASSED, setting _negate_invar = %d, _invar = %d, _offset = %d", n->_idx, _negate_invar, _invar->_idx, _offset);
3327 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(1) is Con: ", n->in(1)->_idx); n->in(1)->dump();
3328 print_depth(); tty->print(" \\ %d SWPointer::offset_plus_k: in(2) is invariant: ", _invar->_idx); _invar->dump();
3329 }
3330 }
3331
3332 void SWPointer::Tracer::offset_plus_k_10(Node* n, Node* _invar, bool _negate_invar, int _offset) {
3333 if(_slp->is_trace_alignment()) {
3334 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: PASSED, setting _negate_invar = %d, _invar = %d, _offset = %d", n->_idx, _negate_invar, _invar->_idx, _offset);
3335 print_depth(); tty->print_cr(" \\ %d SWPointer::offset_plus_k: is invariant", n->_idx);
3336 }
3337 }
3338
3339 void SWPointer::Tracer::offset_plus_k_11(Node* n) {
3340 if(_slp->is_trace_alignment()) {
3341 print_depth(); tty->print_cr(" %d SWPointer::offset_plus_k: FAILED", n->_idx);
3342 }
3343 }
3344
3345 #endif
3346 // ========================= OrderedPair =====================
3347
3348 const OrderedPair OrderedPair::initial;
3349
3350 // ========================= SWNodeInfo =====================
3351
3352 const SWNodeInfo SWNodeInfo::initial;
3353
3354
3355 // ============================ DepGraph ===========================
3356
3357 //------------------------------make_node---------------------------
3358 // Make a new dependence graph node for an ideal node.
3359 DepMem* DepGraph::make_node(Node* node) {
3360 DepMem* m = new (_arena) DepMem(node);
3361 if (node != NULL) {
3362 assert(_map.at_grow(node->_idx) == NULL, "one init only");
3363 _map.at_put_grow(node->_idx, m);
3364 }
3365 return m;
3366 }
3367
3368 //------------------------------make_edge---------------------------
3369 // Make a new dependence graph edge from dpred -> dsucc
3370 DepEdge* DepGraph::make_edge(DepMem* dpred, DepMem* dsucc) {
3371 DepEdge* e = new (_arena) DepEdge(dpred, dsucc, dsucc->in_head(), dpred->out_head());
3372 dpred->set_out_head(e);
3373 dsucc->set_in_head(e);
3374 return e;
3375 }
3376
3377 // ========================== DepMem ========================
3378
3379 //------------------------------in_cnt---------------------------
3380 int DepMem::in_cnt() {
3381 int ct = 0;
3382 for (DepEdge* e = _in_head; e != NULL; e = e->next_in()) ct++;
3383 return ct;
3384 }
3385
3386 //------------------------------out_cnt---------------------------
3387 int DepMem::out_cnt() {
3388 int ct = 0;
3389 for (DepEdge* e = _out_head; e != NULL; e = e->next_out()) ct++;
3390 return ct;
3391 }
3392
3393 //------------------------------print-----------------------------
3394 void DepMem::print() {
3395 #ifndef PRODUCT
3396 tty->print(" DepNode %d (", _node->_idx);
3397 for (DepEdge* p = _in_head; p != NULL; p = p->next_in()) {
3398 Node* pred = p->pred()->node();
3399 tty->print(" %d", pred != NULL ? pred->_idx : 0);
3400 }
3401 tty->print(") [");
3402 for (DepEdge* s = _out_head; s != NULL; s = s->next_out()) {
3403 Node* succ = s->succ()->node();
3404 tty->print(" %d", succ != NULL ? succ->_idx : 0);
3405 }
3406 tty->print_cr(" ]");
3407 #endif
3408 }
3409
3410 // =========================== DepEdge =========================
3411
3412 //------------------------------DepPreds---------------------------
3413 void DepEdge::print() {
3414 #ifndef PRODUCT
3415 tty->print_cr("DepEdge: %d [ %d ]", _pred->node()->_idx, _succ->node()->_idx);
3416 #endif
3417 }
3418
3419 // =========================== DepPreds =========================
3420 // Iterator over predecessor edges in the dependence graph.
3421
3422 //------------------------------DepPreds---------------------------
3423 DepPreds::DepPreds(Node* n, DepGraph& dg) {
3424 _n = n;
3425 _done = false;
3426 if (_n->is_Store() || _n->is_Load()) {
3427 _next_idx = MemNode::Address;
3428 _end_idx = n->req();
3429 _dep_next = dg.dep(_n)->in_head();
3430 } else if (_n->is_Mem()) {
3431 _next_idx = 0;
3432 _end_idx = 0;
3433 _dep_next = dg.dep(_n)->in_head();
3434 } else {
3435 _next_idx = 1;
3436 _end_idx = _n->req();
3437 _dep_next = NULL;
3438 }
3439 next();
3440 }
3441
3442 //------------------------------next---------------------------
3443 void DepPreds::next() {
3444 if (_dep_next != NULL) {
3445 _current = _dep_next->pred()->node();
3446 _dep_next = _dep_next->next_in();
3447 } else if (_next_idx < _end_idx) {
3448 _current = _n->in(_next_idx++);
3449 } else {
3450 _done = true;
3451 }
3452 }
3453
3454 // =========================== DepSuccs =========================
3455 // Iterator over successor edges in the dependence graph.
3456
3457 //------------------------------DepSuccs---------------------------
3458 DepSuccs::DepSuccs(Node* n, DepGraph& dg) {
3459 _n = n;
3460 _done = false;
3461 if (_n->is_Load()) {
3462 _next_idx = 0;
3463 _end_idx = _n->outcnt();
3464 _dep_next = dg.dep(_n)->out_head();
3465 } else if (_n->is_Mem() || _n->is_Phi() && _n->bottom_type() == Type::MEMORY) {
3466 _next_idx = 0;
3467 _end_idx = 0;
3468 _dep_next = dg.dep(_n)->out_head();
3469 } else {
3470 _next_idx = 0;
3471 _end_idx = _n->outcnt();
3472 _dep_next = NULL;
3473 }
3474 next();
3475 }
3476
3477 //-------------------------------next---------------------------
3478 void DepSuccs::next() {
3479 if (_dep_next != NULL) {
3480 _current = _dep_next->succ()->node();
3481 _dep_next = _dep_next->next_out();
3482 } else if (_next_idx < _end_idx) {
3483 _current = _n->raw_out(_next_idx++);
3484 } else {
3485 _done = true;
3486 }
3487 }
3488
3489 //
3490 // --------------------------------- vectorization/simd -----------------------------------
3491 //
3492 bool SuperWord::same_origin_idx(Node* a, Node* b) const {
3493 return a != NULL && b != NULL && _clone_map.same_idx(a->_idx, b->_idx);
3494 }
3495 bool SuperWord::same_generation(Node* a, Node* b) const {
3496 return a != NULL && b != NULL && _clone_map.same_gen(a->_idx, b->_idx);
3497 }
3498
3499 Node* SuperWord::find_phi_for_mem_dep(LoadNode* ld) {
3500 assert(in_bb(ld), "must be in block");
3501 if (_clone_map.gen(ld->_idx) == _ii_first) {
3502 #ifndef PRODUCT
3503 if (_vector_loop_debug) {
3504 tty->print_cr("SuperWord::find_phi_for_mem_dep _clone_map.gen(ld->_idx)=%d",
3505 _clone_map.gen(ld->_idx));
3506 }
3507 #endif
3508 return NULL; //we think that any ld in the first gen being vectorizable
3509 }
3510
3511 Node* mem = ld->in(MemNode::Memory);
3512 if (mem->outcnt() <= 1) {
3513 // we don't want to remove the only edge from mem node to load
3514 #ifndef PRODUCT
3515 if (_vector_loop_debug) {
3516 tty->print_cr("SuperWord::find_phi_for_mem_dep input node %d to load %d has no other outputs and edge mem->load cannot be removed",
3517 mem->_idx, ld->_idx);
3518 ld->dump();
3519 mem->dump();
3520 }
3521 #endif
3522 return NULL;
3523 }
3524 if (!in_bb(mem) || same_generation(mem, ld)) {
3525 #ifndef PRODUCT
3526 if (_vector_loop_debug) {
3527 tty->print_cr("SuperWord::find_phi_for_mem_dep _clone_map.gen(mem->_idx)=%d",
3528 _clone_map.gen(mem->_idx));
3529 }
3530 #endif
3531 return NULL; // does not depend on loop volatile node or depends on the same generation
3532 }
3533
3534 //otherwise first node should depend on mem-phi
3535 Node* first = first_node(ld);
3536 assert(first->is_Load(), "must be Load");
3537 Node* phi = first->as_Load()->in(MemNode::Memory);
3538 if (!phi->is_Phi() || phi->bottom_type() != Type::MEMORY) {
3539 #ifndef PRODUCT
3540 if (_vector_loop_debug) {
3541 tty->print_cr("SuperWord::find_phi_for_mem_dep load is not vectorizable node, since it's `first` does not take input from mem phi");
3542 ld->dump();
3543 first->dump();
3544 }
3545 #endif
3546 return NULL;
3547 }
3548
3549 Node* tail = 0;
3550 for (int m = 0; m < _mem_slice_head.length(); m++) {
3551 if (_mem_slice_head.at(m) == phi) {
3552 tail = _mem_slice_tail.at(m);
3553 }
3554 }
3555 if (tail == 0) { //test that found phi is in the list _mem_slice_head
3556 #ifndef PRODUCT
3557 if (_vector_loop_debug) {
3558 tty->print_cr("SuperWord::find_phi_for_mem_dep load %d is not vectorizable node, its phi %d is not _mem_slice_head",
3559 ld->_idx, phi->_idx);
3560 ld->dump();
3561 phi->dump();
3562 }
3563 #endif
3564 return NULL;
3565 }
3566
3567 // now all conditions are met
3568 return phi;
3569 }
3570
3571 Node* SuperWord::first_node(Node* nd) {
3572 for (int ii = 0; ii < _iteration_first.length(); ii++) {
3573 Node* nnn = _iteration_first.at(ii);
3574 if (same_origin_idx(nnn, nd)) {
3575 #ifndef PRODUCT
3576 if (_vector_loop_debug) {
3577 tty->print_cr("SuperWord::first_node: %d is the first iteration node for %d (_clone_map.idx(nnn->_idx) = %d)",
3578 nnn->_idx, nd->_idx, _clone_map.idx(nnn->_idx));
3579 }
3580 #endif
3581 return nnn;
3582 }
3583 }
3584
3585 #ifndef PRODUCT
3586 if (_vector_loop_debug) {
3587 tty->print_cr("SuperWord::first_node: did not find first iteration node for %d (_clone_map.idx(nd->_idx)=%d)",
3588 nd->_idx, _clone_map.idx(nd->_idx));
3589 }
3590 #endif
3591 return 0;
3592 }
3593
3594 Node* SuperWord::last_node(Node* nd) {
3595 for (int ii = 0; ii < _iteration_last.length(); ii++) {
3596 Node* nnn = _iteration_last.at(ii);
3597 if (same_origin_idx(nnn, nd)) {
3598 #ifndef PRODUCT
3599 if (_vector_loop_debug) {
3600 tty->print_cr("SuperWord::last_node _clone_map.idx(nnn->_idx)=%d, _clone_map.idx(nd->_idx)=%d",
3601 _clone_map.idx(nnn->_idx), _clone_map.idx(nd->_idx));
3602 }
3603 #endif
3604 return nnn;
3605 }
3606 }
3607 return 0;
3608 }
3609
3610 int SuperWord::mark_generations() {
3611 Node *ii_err = 0, *tail_err;
3612 for (int i = 0; i < _mem_slice_head.length(); i++) {
3613 Node* phi = _mem_slice_head.at(i);
3614 assert(phi->is_Phi(), "must be phi");
3615
3616 Node* tail = _mem_slice_tail.at(i);
3617 if (_ii_last == -1) {
3618 tail_err = tail;
3619 _ii_last = _clone_map.gen(tail->_idx);
3620 }
3621 else if (_ii_last != _clone_map.gen(tail->_idx)) {
3622 #ifndef PRODUCT
3623 if (TraceSuperWord && Verbose) {
3624 tty->print_cr("SuperWord::mark_generations _ii_last error - found different generations in two tail nodes ");
3625 tail->dump();
3626 tail_err->dump();
3627 }
3628 #endif
3629 return -1;
3630 }
3631
3632 // find first iteration in the loop
3633 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
3634 Node* ii = phi->fast_out(i);
3635 if (in_bb(ii) && ii->is_Store()) { // we speculate that normally Stores of one and one only generation have deps from mem phi
3636 if (_ii_first == -1) {
3637 ii_err = ii;
3638 _ii_first = _clone_map.gen(ii->_idx);
3639 } else if (_ii_first != _clone_map.gen(ii->_idx)) {
3640 #ifndef PRODUCT
3641 if (TraceSuperWord && Verbose) {
3642 tty->print_cr("SuperWord::mark_generations: _ii_first was found before and not equal to one in this node (%d)", _ii_first);
3643 ii->dump();
3644 if (ii_err!= 0) {
3645 ii_err->dump();
3646 }
3647 }
3648 #endif
3649 return -1; // this phi has Stores from different generations of unroll and cannot be simd/vectorized
3650 }
3651 }
3652 }//for (DUIterator_Fast imax,
3653 }//for (int i...
3654
3655 if (_ii_first == -1 || _ii_last == -1) {
3656 #ifndef PRODUCT
3657 if (TraceSuperWord && Verbose) {
3658 tty->print_cr("SuperWord::mark_generations unknown error, something vent wrong");
3659 }
3660 #endif
3661 return -1; // something vent wrong
3662 }
3663 // collect nodes in the first and last generations
3664 assert(_iteration_first.length() == 0, "_iteration_first must be empty");
3665 assert(_iteration_last.length() == 0, "_iteration_last must be empty");
3666 for (int j = 0; j < _block.length(); j++) {
3667 Node* n = _block.at(j);
3668 node_idx_t gen = _clone_map.gen(n->_idx);
3669 if ((signed)gen == _ii_first) {
3670 _iteration_first.push(n);
3671 } else if ((signed)gen == _ii_last) {
3672 _iteration_last.push(n);
3673 }
3674 }
3675
3676 // building order of iterations
3677 if (_ii_order.length() == 0 && ii_err != 0) {
3678 assert(in_bb(ii_err) && ii_err->is_Store(), "should be Store in bb");
3679 Node* nd = ii_err;
3680 while(_clone_map.gen(nd->_idx) != _ii_last) {
3681 _ii_order.push(_clone_map.gen(nd->_idx));
3682 bool found = false;
3683 for (DUIterator_Fast imax, i = nd->fast_outs(imax); i < imax; i++) {
3684 Node* use = nd->fast_out(i);
3685 if (same_origin_idx(use, nd) && use->as_Store()->in(MemNode::Memory) == nd) {
3686 found = true;
3687 nd = use;
3688 break;
3689 }
3690 }//for
3691
3692 if (found == false) {
3693 #ifndef PRODUCT
3694 if (TraceSuperWord && Verbose) {
3695 tty->print_cr("SuperWord::mark_generations: Cannot build order of iterations - no dependent Store for %d", nd->_idx);
3696 }
3697 #endif
3698 _ii_order.clear();
3699 return -1;
3700 }
3701 } //while
3702 _ii_order.push(_clone_map.gen(nd->_idx));
3703 }
3704
3705 #ifndef PRODUCT
3706 if (_vector_loop_debug) {
3707 tty->print_cr("SuperWord::mark_generations");
3708 tty->print_cr("First generation (%d) nodes:", _ii_first);
3709 for (int ii = 0; ii < _iteration_first.length(); ii++) _iteration_first.at(ii)->dump();
3710 tty->print_cr("Last generation (%d) nodes:", _ii_last);
3711 for (int ii = 0; ii < _iteration_last.length(); ii++) _iteration_last.at(ii)->dump();
3712 tty->print_cr(" ");
3713
3714 tty->print("SuperWord::List of generations: ");
3715 for (int jj = 0; jj < _ii_order.length(); ++jj) {
3716 tty->print("%d:%d ", jj, _ii_order.at(jj));
3717 }
3718 tty->print_cr(" ");
3719 }
3720 #endif
3721
3722 return _ii_first;
3723 }
3724
3725 bool SuperWord::fix_commutative_inputs(Node* gold, Node* fix) {
3726 assert(gold->is_Add() && fix->is_Add() || gold->is_Mul() && fix->is_Mul(), "should be only Add or Mul nodes");
3727 assert(same_origin_idx(gold, fix), "should be clones of the same node");
3728 Node* gin1 = gold->in(1);
3729 Node* gin2 = gold->in(2);
3730 Node* fin1 = fix->in(1);
3731 Node* fin2 = fix->in(2);
3732 bool swapped = false;
3733
3734 if (in_bb(gin1) && in_bb(gin2) && in_bb(fin1) && in_bb(fin1)) {
3735 if (same_origin_idx(gin1, fin1) &&
3736 same_origin_idx(gin2, fin2)) {
3737 return true; // nothing to fix
3738 }
3739 if (same_origin_idx(gin1, fin2) &&
3740 same_origin_idx(gin2, fin1)) {
3741 fix->swap_edges(1, 2);
3742 swapped = true;
3743 }
3744 }
3745 // at least one input comes from outside of bb
3746 if (gin1->_idx == fin1->_idx) {
3747 return true; // nothing to fix
3748 }
3749 if (!swapped && (gin1->_idx == fin2->_idx || gin2->_idx == fin1->_idx)) { //swapping is expensive, check condition first
3750 fix->swap_edges(1, 2);
3751 swapped = true;
3752 }
3753
3754 if (swapped) {
3755 #ifndef PRODUCT
3756 if (_vector_loop_debug) {
3757 tty->print_cr("SuperWord::fix_commutative_inputs: fixed node %d", fix->_idx);
3758 }
3759 #endif
3760 return true;
3761 }
3762
3763 #ifndef PRODUCT
3764 if (TraceSuperWord && Verbose) {
3765 tty->print_cr("SuperWord::fix_commutative_inputs: cannot fix node %d", fix->_idx);
3766 }
3767 #endif
3768 return false;
3769 }
3770
3771 bool SuperWord::pack_parallel() {
3772 #ifndef PRODUCT
3773 if (_vector_loop_debug) {
3774 tty->print_cr("SuperWord::pack_parallel: START");
3775 }
3776 #endif
3777
3778 _packset.clear();
3779
3780 for (int ii = 0; ii < _iteration_first.length(); ii++) {
3781 Node* nd = _iteration_first.at(ii);
3782 if (in_bb(nd) && (nd->is_Load() || nd->is_Store() || nd->is_Add() || nd->is_Mul())) {
3783 Node_List* pk = new Node_List();
3784 pk->push(nd);
3785 for (int gen = 1; gen < _ii_order.length(); ++gen) {
3786 for (int kk = 0; kk < _block.length(); kk++) {
3787 Node* clone = _block.at(kk);
3788 if (same_origin_idx(clone, nd) &&
3789 _clone_map.gen(clone->_idx) == _ii_order.at(gen)) {
3790 if (nd->is_Add() || nd->is_Mul()) {
3791 fix_commutative_inputs(nd, clone);
3792 }
3793 pk->push(clone);
3794 if (pk->size() == 4) {
3795 _packset.append(pk);
3796 #ifndef PRODUCT
3797 if (_vector_loop_debug) {
3798 tty->print_cr("SuperWord::pack_parallel: added pack ");
3799 pk->dump();
3800 }
3801 #endif
3802 if (_clone_map.gen(clone->_idx) != _ii_last) {
3803 pk = new Node_List();
3804 }
3805 }
3806 break;
3807 }
3808 }
3809 }//for
3810 }//if
3811 }//for
3812
3813 #ifndef PRODUCT
3814 if (_vector_loop_debug) {
3815 tty->print_cr("SuperWord::pack_parallel: END");
3816 }
3817 #endif
3818
3819 return true;
3820 }
3821
3822 bool SuperWord::hoist_loads_in_graph() {
3823 GrowableArray<Node*> loads;
3824
3825 #ifndef PRODUCT
3826 if (_vector_loop_debug) {
3827 tty->print_cr("SuperWord::hoist_loads_in_graph: total number _mem_slice_head.length() = %d", _mem_slice_head.length());
3828 }
3829 #endif
3830
3831 for (int i = 0; i < _mem_slice_head.length(); i++) {
3832 Node* n = _mem_slice_head.at(i);
3833 if ( !in_bb(n) || !n->is_Phi() || n->bottom_type() != Type::MEMORY) {
3834 #ifndef PRODUCT
3835 if (TraceSuperWord && Verbose) {
3836 tty->print_cr("SuperWord::hoist_loads_in_graph: skipping unexpected node n=%d", n->_idx);
3837 }
3838 #endif
3839 continue;
3840 }
3841
3842 #ifndef PRODUCT
3843 if (_vector_loop_debug) {
3844 tty->print_cr("SuperWord::hoist_loads_in_graph: processing phi %d = _mem_slice_head.at(%d);", n->_idx, i);
3845 }
3846 #endif
3847
3848 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3849 Node* ld = n->fast_out(i);
3850 if (ld->is_Load() && ld->as_Load()->in(MemNode::Memory) == n && in_bb(ld)) {
3851 for (int i = 0; i < _block.length(); i++) {
3852 Node* ld2 = _block.at(i);
3853 if (ld2->is_Load() && same_origin_idx(ld, ld2) &&
3854 !same_generation(ld, ld2)) { // <= do not collect the first generation ld
3855 #ifndef PRODUCT
3856 if (_vector_loop_debug) {
3857 tty->print_cr("SuperWord::hoist_loads_in_graph: will try to hoist load ld2->_idx=%d, cloned from %d (ld->_idx=%d)",
3858 ld2->_idx, _clone_map.idx(ld->_idx), ld->_idx);
3859 }
3860 #endif
3861 // could not do on-the-fly, since iterator is immutable
3862 loads.push(ld2);
3863 }
3864 }// for
3865 }//if
3866 }//for (DUIterator_Fast imax,
3867 }//for (int i = 0; i
3868
3869 for (int i = 0; i < loads.length(); i++) {
3870 LoadNode* ld = loads.at(i)->as_Load();
3871 Node* phi = find_phi_for_mem_dep(ld);
3872 if (phi != NULL) {
3873 #ifndef PRODUCT
3874 if (_vector_loop_debug) {
3875 tty->print_cr("SuperWord::hoist_loads_in_graph replacing MemNode::Memory(%d) edge in %d with one from %d",
3876 MemNode::Memory, ld->_idx, phi->_idx);
3877 }
3878 #endif
3879 _igvn.replace_input_of(ld, MemNode::Memory, phi);
3880 }
3881 }//for
3882
3883 restart(); // invalidate all basic structures, since we rebuilt the graph
3884
3885 #ifndef PRODUCT
3886 if (TraceSuperWord && Verbose) {
3887 tty->print_cr("\nSuperWord::hoist_loads_in_graph() the graph was rebuilt, all structures invalidated and need rebuild");
3888 }
3889 #endif
3890 return true;
3891 }
3892