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