/*

 * Copyright (c) 2007, 2012, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

#include "precompiled.hpp"

#include "compiler/compileLog.hpp"

#include "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/divnode.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/opcodes.hpp"

#include "opto/superword.hpp"

#include "opto/vectornode.hpp"

//

//                  S U P E R W O R D   T R A N S F O R M

//=============================================================================

//------------------------------SuperWord---------------------------

SuperWord::SuperWord(PhaseIdealLoop* phase) :

  _phase(phase),

  _igvn(phase->_igvn),

  _arena(phase->C->comp_arena()),

  _packset(arena(), 8,  0, NULL),         // packs for the current block

  _bb_idx(arena(), (int)(1.10 * phase->C->unique()), 0, 0), // node idx to index in bb

  _block(arena(), 8,  0, NULL),           // nodes in current block

  _data_entry(arena(), 8,  0, NULL),      // nodes with all inputs from outside

  _mem_slice_head(arena(), 8,  0, NULL),  // memory slice heads

  _mem_slice_tail(arena(), 8,  0, NULL),  // memory slice tails

  _node_info(arena(), 8,  0, SWNodeInfo::initial), // info needed per node

  _align_to_ref(NULL),                    // memory reference to align vectors to

  _disjoint_ptrs(arena(), 8,  0, OrderedPair::initial), // runtime disambiguated pointer pairs

  _dg(_arena),                            // dependence graph

  _visited(arena()),                      // visited node set

  _post_visited(arena()),                 // post visited node set

  _n_idx_list(arena(), 8),                // scratch list of (node,index) pairs

  _stk(arena(), 8, 0, NULL),              // scratch stack of nodes

  _nlist(arena(), 8, 0, NULL),            // scratch list of nodes

  _lpt(NULL),                             // loop tree node

  _lp(NULL),                              // LoopNode

  _bb(NULL),                              // basic block

  _iv(NULL)                               // induction var

{}

//------------------------------transform_loop---------------------------

void SuperWord::transform_loop(IdealLoopTree* lpt) {

  assert(UseSuperWord, "should be");

  // Do vectors exist on this architecture?

  if (Matcher::vector_width_in_bytes(T_BYTE) < 2) return;

  assert(lpt->_head->is_CountedLoop(), "must be");

  CountedLoopNode *cl = lpt->_head->as_CountedLoop();

  if (!cl->is_valid_counted_loop()) return; // skip malformed counted loop

  if (!cl->is_main_loop() ) return; // skip normal, pre, and post loops

  // Check for no control flow in body (other than exit)

  Node *cl_exit = cl->loopexit();

  if (cl_exit->in(0) != lpt->_head) return;

  // Make sure the are no extra control users of the loop backedge

  if (cl->back_control()->outcnt() != 1) {

    return;

  }

  // Check for pre-loop ending with CountedLoopEnd(Bool(Cmp(x,Opaque1(limit))))

  CountedLoopEndNode* pre_end = get_pre_loop_end(cl);

  if (pre_end == NULL) return;

  Node *pre_opaq1 = pre_end->limit();

  if (pre_opaq1->Opcode() != Op_Opaque1) return;

  init(); // initialize data structures

  set_lpt(lpt);

  set_lp(cl);

  // For now, define one block which is the entire loop body

  set_bb(cl);

  assert(_packset.length() == 0, "packset must be empty");

  SLP_extract();

}

//------------------------------SLP_extract---------------------------

// Extract the superword level parallelism

//

// 1) A reverse post-order of nodes in the block is constructed.  By scanning

//    this list from first to last, all definitions are visited before their uses.

//

// 2) A point-to-point dependence graph is constructed between memory references.

//    This simplies the upcoming "independence" checker.

//

// 3) The maximum depth in the node graph from the beginning of the block

//    to each node is computed.  This is used to prune the graph search

//    in the independence checker.

//

// 4) For integer types, the necessary bit width is propagated backwards

//    from stores to allow packed operations on byte, char, and short

//    integers.  This reverses the promotion to type "int" that javac

//    did for operations like: char c1,c2,c3;  c1 = c2 + c3.

//

// 5) One of the memory references is picked to be an aligned vector reference.

//    The pre-loop trip count is adjusted to align this reference in the

//    unrolled body.

//

// 6) The initial set of pack pairs is seeded with memory references.

//

// 7) The set of pack pairs is extended by following use->def and def->use links.

//

// 8) The pairs are combined into vector sized packs.

//

// 9) Reorder the memory slices to co-locate members of the memory packs.

//

// 10) Generate ideal vector nodes for the final set of packs and where necessary,

//    inserting scalar promotion, vector creation from multiple scalars, and

//    extraction of scalar values from vectors.

//

void SuperWord::SLP_extract() {

  // Ready the block

  if (!construct_bb())

    return; // Exit if no interesting nodes or complex graph.

  dependence_graph();

  compute_max_depth();

  compute_vector_element_type();

  // Attempt vectorization

  find_adjacent_refs();

  extend_packlist();

  combine_packs();

  construct_my_pack_map();

  filter_packs();

  schedule();

  output();

}

//------------------------------find_adjacent_refs---------------------------

// Find the adjacent memory references and create pack pairs for them.

// This is the initial set of packs that will then be extended by

// following use->def and def->use links.  The align positions are

// assigned relative to the reference "align_to_ref"

void SuperWord::find_adjacent_refs() {

  // Get list of memory operations

  Node_List memops;

  for (int i = 0; i < _block.length(); i++) {

    Node* n = _block.at(i);

    if (n->is_Mem() && !n->is_LoadStore() && in_bb(n) &&

        is_java_primitive(n->as_Mem()->memory_type())) {

      int align = memory_alignment(n->as_Mem(), 0);

      if (align != bottom_align) {

        memops.push(n);

      }

    }

  }

  Node_List align_to_refs;

  int best_iv_adjustment = 0;

  MemNode* best_align_to_mem_ref = NULL;

  while (memops.size() != 0) {

    // Find a memory reference to align to.

    MemNode* mem_ref = find_align_to_ref(memops);

    if (mem_ref == NULL) break;

    align_to_refs.push(mem_ref);

    int iv_adjustment = get_iv_adjustment(mem_ref);

    if (best_align_to_mem_ref == NULL) {

      // Set memory reference which is the best from all memory operations

      // to be used for alignment. The pre-loop trip count is modified to align

      // this reference to a vector-aligned address.

      best_align_to_mem_ref = mem_ref;

      best_iv_adjustment = iv_adjustment;

    }

    SWPointer align_to_ref_p(mem_ref, this);

    // Set alignment relative to "align_to_ref" for all related memory operations.

    for (int i = memops.size() - 1; i >= 0; i--) {

      MemNode* s = memops.at(i)->as_Mem();

      if (isomorphic(s, mem_ref)) {

        SWPointer p2(s, this);

        if (p2.comparable(align_to_ref_p)) {

          int align = memory_alignment(s, iv_adjustment);

          set_alignment(s, align);

        }

      }

    }

    // Create initial pack pairs of memory operations for which

    // alignment is set and vectors will be aligned.

    bool create_pack = true;

    if (memory_alignment(mem_ref, best_iv_adjustment) == 0) {

      if (!Matcher::misaligned_vectors_ok()) {

        int vw = vector_width(mem_ref);

        int vw_best = vector_width(best_align_to_mem_ref);

        if (vw > vw_best) {

          // Do not vectorize a memory access with more elements per vector

          // if unaligned memory access is not allowed because number of

          // iterations in pre-loop will be not enough to align it.

          create_pack = false;

        }

      }

    } else {

      if (same_velt_type(mem_ref, best_align_to_mem_ref)) {

        // Can't allow vectorization of unaligned memory accesses with the

        // same type since it could be overlapped accesses to the same array.

        create_pack = false;

      } else {

        // Allow independent (different type) unaligned memory operations

        // if HW supports them.

        if (!Matcher::misaligned_vectors_ok()) {

          create_pack = false;

        } else {

          // Check if packs of the same memory type but

          // with a different alignment were created before.

          for (uint i = 0; i < align_to_refs.size(); i++) {

            MemNode* mr = align_to_refs.at(i)->as_Mem();

            if (same_velt_type(mr, mem_ref) &&

                memory_alignment(mr, iv_adjustment) != 0)

              create_pack = false;

          }

        }

      }

    }

    if (create_pack) {

      for (uint i = 0; i < memops.size(); i++) {

        Node* s1 = memops.at(i);

        int align = alignment(s1);

        if (align == top_align) continue;

        for (uint j = 0; j < memops.size(); j++) {

          Node* s2 = memops.at(j);

          if (alignment(s2) == top_align) continue;

          if (s1 != s2 && are_adjacent_refs(s1, s2)) {

            if (stmts_can_pack(s1, s2, align)) {

              Node_List* pair = new Node_List();

              pair->push(s1);

              pair->push(s2);

              _packset.append(pair);

            }

          }

        }

      }

    } else { // Don't create unaligned pack

      // First, remove remaining memory ops of the same type from the list.

      for (int i = memops.size() - 1; i >= 0; i--) {

        MemNode* s = memops.at(i)->as_Mem();

        if (same_velt_type(s, mem_ref)) {

          memops.remove(i);

        }

      }

      // Second, remove already constructed packs of the same type.

      for (int i = _packset.length() - 1; i >= 0; i--) {

        Node_List* p = _packset.at(i);

        MemNode* s = p->at(0)->as_Mem();

        if (same_velt_type(s, mem_ref)) {

          remove_pack_at(i);

        }

      }

      // If needed find the best memory reference for loop alignment again.

      if (same_velt_type(mem_ref, best_align_to_mem_ref)) {

        // Put memory ops from remaining packs back on memops list for

        // the best alignment search.

        uint orig_msize = memops.size();

        for (int i = 0; i < _packset.length(); i++) {

          Node_List* p = _packset.at(i);

          MemNode* s = p->at(0)->as_Mem();

          assert(!same_velt_type(s, mem_ref), "sanity");

          memops.push(s);

        }

        MemNode* best_align_to_mem_ref = find_align_to_ref(memops);

        if (best_align_to_mem_ref == NULL) break;

        best_iv_adjustment = get_iv_adjustment(best_align_to_mem_ref);

        // Restore list.

        while (memops.size() > orig_msize)

          (void)memops.pop();

      }

    } // unaligned memory accesses

    // Remove used mem nodes.

    for (int i = memops.size() - 1; i >= 0; i--) {

      MemNode* m = memops.at(i)->as_Mem();

      if (alignment(m) != top_align) {

        memops.remove(i);

      }

    }

  } // while (memops.size() != 0

  set_align_to_ref(best_align_to_mem_ref);

#ifndef PRODUCT

  if (TraceSuperWord) {

    tty->print_cr("\nAfter find_adjacent_refs");

    print_packset();

  }

#endif

}

//------------------------------find_align_to_ref---------------------------

// Find a memory reference to align the loop induction variable to.

// Looks first at stores then at loads, looking for a memory reference

// with the largest number of references similar to it.

MemNode* SuperWord::find_align_to_ref(Node_List &memops) {

  GrowableArray<int> cmp_ct(arena(), memops.size(), memops.size(), 0);

  // Count number of comparable memory ops

  for (uint i = 0; i < memops.size(); i++) {

    MemNode* s1 = memops.at(i)->as_Mem();

    SWPointer p1(s1, this);

    // Discard if pre loop can't align this reference

    if (!ref_is_alignable(p1)) {

      *cmp_ct.adr_at(i) = 0;

      continue;

    }

    for (uint j = i+1; j < memops.size(); j++) {

      MemNode* s2 = memops.at(j)->as_Mem();

      if (isomorphic(s1, s2)) {

        SWPointer p2(s2, this);

        if (p1.comparable(p2)) {

          (*cmp_ct.adr_at(i))++;

          (*cmp_ct.adr_at(j))++;

        }

      }

    }

  }

  // Find Store (or Load) with the greatest number of "comparable" references,

  // biggest vector size, smallest data size and smallest iv offset.

  int max_ct        = 0;

  int max_vw        = 0;

  int max_idx       = -1;

  int min_size      = max_jint;

  int min_iv_offset = max_jint;

  for (uint j = 0; j < memops.size(); j++) {

    MemNode* s = memops.at(j)->as_Mem();

    if (s->is_Store()) {

      int vw = vector_width_in_bytes(s);

      assert(vw > 1, "sanity");

      SWPointer p(s, this);

      if (cmp_ct.at(j) >  max_ct ||

          cmp_ct.at(j) == max_ct &&

            (vw >  max_vw ||

             vw == max_vw &&

              (data_size(s) <  min_size ||

               data_size(s) == min_size &&

                 (p.offset_in_bytes() < min_iv_offset)))) {

        max_ct = cmp_ct.at(j);

        max_vw = vw;

        max_idx = j;

        min_size = data_size(s);

        min_iv_offset = p.offset_in_bytes();

      }

    }

  }

  // If no stores, look at loads

  if (max_ct == 0) {

    for (uint j = 0; j < memops.size(); j++) {

      MemNode* s = memops.at(j)->as_Mem();

      if (s->is_Load()) {

        int vw = vector_width_in_bytes(s);

        assert(vw > 1, "sanity");

        SWPointer p(s, this);

        if (cmp_ct.at(j) >  max_ct ||

            cmp_ct.at(j) == max_ct &&

              (vw >  max_vw ||

               vw == max_vw &&

                (data_size(s) <  min_size ||

                 data_size(s) == min_size &&

                   (p.offset_in_bytes() < min_iv_offset)))) {

          max_ct = cmp_ct.at(j);

          max_vw = vw;

          max_idx = j;

          min_size = data_size(s);

          min_iv_offset = p.offset_in_bytes();

        }

      }

    }

  }

#ifdef ASSERT

  if (TraceSuperWord && Verbose) {

    tty->print_cr("\nVector memops after find_align_to_refs");

    for (uint i = 0; i < memops.size(); i++) {

      MemNode* s = memops.at(i)->as_Mem();

      s->dump();

    }

  }

#endif

  if (max_ct > 0) {

#ifdef ASSERT

    if (TraceSuperWord) {

      tty->print("\nVector align to node: ");

      memops.at(max_idx)->as_Mem()->dump();

    }

#endif

    return memops.at(max_idx)->as_Mem();

  }

  return NULL;

}

//------------------------------ref_is_alignable---------------------------

// Can the preloop align the reference to position zero in the vector?

bool SuperWord::ref_is_alignable(SWPointer& p) {

  if (!p.has_iv()) {

    return true;   // no induction variable

  }

  CountedLoopEndNode* pre_end = get_pre_loop_end(lp()->as_CountedLoop());

  assert(pre_end->stride_is_con(), "pre loop stride is constant");

  int preloop_stride = pre_end->stride_con();

  int span = preloop_stride * p.scale_in_bytes();

  // Stride one accesses are alignable.

  if (ABS(span) == p.memory_size())

    return true;

  // If initial offset from start of object is computable,

  // compute alignment within the vector.

  int vw = vector_width_in_bytes(p.mem());

  assert(vw > 1, "sanity");

  if (vw % span == 0) {

    Node* init_nd = pre_end->init_trip();

    if (init_nd->is_Con() && p.invar() == NULL) {

      int init = init_nd->bottom_type()->is_int()->get_con();

      int init_offset = init * p.scale_in_bytes() + p.offset_in_bytes();

      assert(init_offset >= 0, "positive offset from object start");

      if (span > 0) {

        return (vw - (init_offset % vw)) % span == 0;

      } else {

        assert(span < 0, "nonzero stride * scale");

        return (init_offset % vw) % -span == 0;

      }

    }

  }

  return false;

}

//---------------------------get_iv_adjustment---------------------------

// Calculate loop's iv adjustment for this memory ops.

int SuperWord::get_iv_adjustment(MemNode* mem_ref) {

  SWPointer align_to_ref_p(mem_ref, this);

  int offset = align_to_ref_p.offset_in_bytes();

  int scale  = align_to_ref_p.scale_in_bytes();

  int vw       = vector_width_in_bytes(mem_ref);

  assert(vw > 1, "sanity");

  int stride_sign   = (scale * iv_stride()) > 0 ? 1 : -1;

  // At least one iteration is executed in pre-loop by default. As result

  // several iterations are needed to align memory operations in main-loop even

  // if offset is 0.

  int iv_adjustment_in_bytes = (stride_sign * vw - (offset % vw));

  int elt_size = align_to_ref_p.memory_size();

  assert(((ABS(iv_adjustment_in_bytes) % elt_size) == 0),

         err_msg_res("(%d) should be divisible by (%d)", iv_adjustment_in_bytes, elt_size));

  int iv_adjustment = iv_adjustment_in_bytes/elt_size;

#ifndef PRODUCT

  if (TraceSuperWord)

    tty->print_cr("\noffset = %d iv_adjust = %d elt_size = %d scale = %d iv_stride = %d vect_size %d",

                  offset, iv_adjustment, elt_size, scale, iv_stride(), vw);

#endif

  return iv_adjustment;

}

//---------------------------dependence_graph---------------------------

// Construct dependency graph.

// Add dependence edges to load/store nodes for memory dependence

//    A.out()->DependNode.in(1) and DependNode.out()->B.prec(x)

void SuperWord::dependence_graph() {

  // First, assign a dependence node to each memory node

  for (int i = 0; i < _block.length(); i++ ) {

    Node *n = _block.at(i);