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