/*

 * Copyright (c) 2007, 2010, 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(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;

  // Do vectors exist on this architecture?

  if (vector_width_in_bytes() == 0) 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

  construct_bb();

  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() && 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);

      }

    }

  }

  if (memops.size() == 0) return;

  // Find a memory reference to align to.  The pre-loop trip count

  // is modified to align this reference to a vector-aligned address

  find_align_to_ref(memops);

  if (align_to_ref() == NULL) return;

  SWPointer align_to_ref_p(align_to_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();

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

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

#ifndef PRODUCT

  if (TraceSuperWord)

    tty->print_cr("\noffset = %d iv_adjustment = %d  elt_align = %d scale = %d iv_stride = %d",

                  offset, iv_adjustment, align_to_ref_p.memory_size(), align_to_ref_p.scale_in_bytes(), iv_stride());

#endif

  // Set alignment relative to "align_to_ref"

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

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

    SWPointer p2(s, this);

    if (p2.comparable(align_to_ref_p)) {

      int align = memory_alignment(s, iv_adjustment);

      set_alignment(s, align);

    } else {

      memops.remove(i);

    }

  }

  // Create initial pack pairs of memory operations

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

    Node* s1 = memops.at(i);

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

      Node* s2 = memops.at(j);

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

        int align = alignment(s1);

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

          Node_List* pair = new Node_List();

          pair->push(s1);

          pair->push(s2);

          _packset.append(pair);

        }

      }

    }

  }

#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.

void 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

  int max_ct        = 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()) {

      SWPointer p(s, this);

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

          cmp_ct.at(j) == max_ct && (data_size(s) < min_size ||

                                     data_size(s) == min_size &&

                                        p.offset_in_bytes() < min_iv_offset)) {

        max_ct = cmp_ct.at(j);

        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()) {

        SWPointer p(s, this);

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

            cmp_ct.at(j) == max_ct && (data_size(s) < min_size ||

                                       data_size(s) == min_size &&

                                          p.offset_in_bytes() < min_iv_offset)) {

          max_ct = cmp_ct.at(j);

          max_idx = j;

          min_size = data_size(s);

          min_iv_offset = p.offset_in_bytes();

        }

      }

    }

  }

  if (max_ct > 0)

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

#ifndef PRODUCT

  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

}

//------------------------------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();

  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;

}

//---------------------------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);

    if (n->is_Mem() || n->is_Phi() && n->bottom_type() == Type::MEMORY) {

      _dg.make_node(n);

    }

  }

  // For each memory slice, create the dependences

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

    Node* n      = _mem_slice_head.at(i);

    Node* n_tail = _mem_slice_tail.at(i);

    // Get slice in predecessor order (last is first)

    mem_slice_preds(n_tail, n, _nlist);

    // Make the slice dependent on the root

    DepMem* slice = _dg.dep(n);

    _dg.make_edge(_dg.root(), slice);

    // Create a sink for the slice

    DepMem* slice_sink = _dg.make_node(NULL);

    _dg.make_edge(slice_sink, _dg.tail());

    // Now visit each pair of memory ops, creating the edges

    for (int j = _nlist.length() - 1; j >= 0 ; j--) {

      Node* s1 = _nlist.at(j);

      // If no dependency yet, use slice

      if (_dg.dep(s1)->in_cnt() == 0) {

        _dg.make_edge(slice, s1);

      }

      SWPointer p1(s1->as_Mem(), this);

      bool sink_dependent = true;

      for (int k = j - 1; k >= 0; k--) {

        Node* s2 = _nlist.at(k);

        if (s1->is_Load() && s2->is_Load())

          continue;

        SWPointer p2(s2->as_Mem(), this);

        int cmp = p1.cmp(p2);

        if (SuperWordRTDepCheck &&

            p1.base() != p2.base() && p1.valid() && p2.valid()) {

          // Create a runtime check to disambiguate

          OrderedPair pp(p1.base(), p2.base());

          _disjoint_ptrs.append_if_missing(pp);

        } else if (!SWPointer::not_equal(cmp)) {

          // Possibly same address

          _dg.make_edge(s1, s2);

          sink_dependent = false;

        }

      }

      if (sink_dependent) {

        _dg.make_edge(s1, slice_sink);

      }

    }

#ifndef PRODUCT

    if (TraceSuperWord) {

      tty->print_cr("\nDependence graph for slice: %d", n->_idx);

      for (int q = 0; q < _nlist.length(); q++) {

        _dg.print(_nlist.at(q));

      }

      tty->cr();

    }

#endif

    _nlist.clear();

  }

#ifndef PRODUCT

  if (TraceSuperWord) {

    tty->print_cr("\ndisjoint_ptrs: %s", _disjoint_ptrs.length() > 0 ? "" : "NONE");

    for (int r = 0; r < _disjoint_ptrs.length(); r++) {

      _disjoint_ptrs.at(r).print();

      tty->cr();

    }

    tty->cr();

  }

#endif

}

//---------------------------mem_slice_preds---------------------------

// Return a memory slice (node list) in predecessor order starting at "start"

void SuperWord::mem_slice_preds(Node* start, Node* stop, GrowableArray<Node*> &preds) {

  assert(preds.length() == 0, "start empty");

  Node* n = start;

  Node* prev = NULL;

  while (true) {

    assert(in_bb(n), "must be in block");

    for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {

      Node* out = n->fast_out(i);

      if (out->is_Load()) {

        if (in_bb(out)) {

          preds.push(out);

        }

      } else {

        // FIXME

        if (out->is_MergeMem() && !in_bb(out)) {

          // Either unrolling is causing a memory edge not to disappear,

          // or need to run igvn.optimize() again before SLP

        } else if (out->is_Phi() && out->bottom_type() == Type::MEMORY && !in_bb(out)) {

          // Ditto.  Not sure what else to check further.

        } else if (out->Opcode() == Op_StoreCM && out->in(MemNode::OopStore) == n) {

          // StoreCM has an input edge used as a precedence edge.

          // Maybe an issue when oop stores are vectorized.

        } else {

          assert(out == prev || prev == NULL, "no branches off of store slice");

        }

      }

    }

    if (n == stop) break;

    preds.push(n);

    prev = n;

    n = n->in(MemNode::Memory);

  }

}

//------------------------------stmts_can_pack---------------------------

// Can s1 and s2 be in a pack with s1 immediately preceding s2 and

// s1 aligned at "align"

bool SuperWord::stmts_can_pack(Node* s1, Node* s2, int align) {

  // Do not use superword for non-primitives

  if((s1->is_Mem() && !is_java_primitive(s1->as_Mem()->memory_type())) ||

     (s2->is_Mem() && !is_java_primitive(s2->as_Mem()->memory_type())))

    return false;

  if (isomorphic(s1, s2)) {

    if (independent(s1, s2)) {

      if (!exists_at(s1, 0) && !exists_at(s2, 1)) {

        if (!s1->is_Mem() || are_adjacent_refs(s1, s2)) {

          int s1_align = alignment(s1);

          int s2_align = alignment(s2);

          if (s1_align == top_align || s1_align == align) {

            if (s2_align == top_align || s2_align == align + data_size(s1)) {

              return true;

            }

          }

        }

      }

    }

  }

  return false;

}

//------------------------------exists_at---------------------------

// Does s exist in a pack at position pos?

bool SuperWord::exists_at(Node* s, uint pos) {

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

    Node_List* p = _packset.at(i);

    if (p->at(pos) == s) {

      return true;

    }

  }

  return false;

}

//------------------------------are_adjacent_refs---------------------------