/*

 * Copyright (c) 2007, 2015, 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/castnode.hpp"

#include "opto/convertnode.hpp"

#include "opto/divnode.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/opcodes.hpp"

#include "opto/opaquenode.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

  _clone_map(phase->C->clone_map()),      // map of nodes created in cloning

  _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

  _race_possible(false),                  // cases where SDMU is true

  _early_return(true),                    // analysis evaluations routine

  _num_work_vecs(0),                      // amount of vector work we have

  _num_reductions(0),                     // amount of reduction work we have

  _do_vector_loop(phase->C->do_vector_loop()),  // whether to do vectorization/simd style

  _ii_first(-1),                          // first loop generation index - only if do_vector_loop()

  _ii_last(-1),                           // last loop generation index - only if do_vector_loop()

  _ii_order(arena(), 8, 0, 0)

{

#ifndef PRODUCT

  _vector_loop_debug = 0;

  if (_phase->C->method() != NULL) {

    _phase->C->method()->has_option_value("VectorizeDebug", _vector_loop_debug);

  }

#endif

}

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

void SuperWord::transform_loop(IdealLoopTree* lpt, bool do_optimization) {

  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;

  }

  // We only re-enter slp when we vector mapped a queried loop and we want to

  // continue unrolling, in this case, slp is not subsequently done.

  if (cl->do_unroll_only()) 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);

  if (do_optimization) {

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

    SLP_extract();

  }

}

//------------------------------early unrolling analysis------------------------------

void SuperWord::unrolling_analysis(int &local_loop_unroll_factor) {

  bool is_slp = true;

  ResourceMark rm;

  size_t ignored_size = lpt()->_body.size();

  int *ignored_loop_nodes = NEW_RESOURCE_ARRAY(int, ignored_size);

  Node_Stack nstack((int)ignored_size);

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

  Node *cl_exit = cl->loopexit();

  // First clear the entries

  for (uint i = 0; i < lpt()->_body.size(); i++) {

    ignored_loop_nodes[i] = -1;

  }

  int max_vector = Matcher::max_vector_size(T_INT);

  // Process the loop, some/all of the stack entries will not be in order, ergo

  // need to preprocess the ignored initial state before we process the loop

  for (uint i = 0; i < lpt()->_body.size(); i++) {

    Node* n = lpt()->_body.at(i);

    if (n == cl->incr() ||

      n->is_reduction() ||

      n->is_AddP() ||

      n->is_Cmp() ||

      n->is_IfTrue() ||

      n->is_CountedLoop() ||

      (n == cl_exit)) {

      ignored_loop_nodes[i] = n->_idx;

      continue;

    }

    if (n->is_If()) {

      IfNode *iff = n->as_If();

      if (iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN) {

        if (lpt()->is_loop_exit(iff)) {

          ignored_loop_nodes[i] = n->_idx;

          continue;

        }

      }

    }

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

      Node* n_tail = n->in(LoopNode::LoopBackControl);

      if (n_tail != n->in(LoopNode::EntryControl)) {

        if (!n_tail->is_Mem()) {

          is_slp = false;

          break;

        }

      }

    }

    // This must happen after check of phi/if

    if (n->is_Phi() || n->is_If()) {

      ignored_loop_nodes[i] = n->_idx;

      continue;

    }

    if (n->is_LoadStore() || n->is_MergeMem() ||

      (n->is_Proj() && !n->as_Proj()->is_CFG())) {

      is_slp = false;

      break;

    }

    // Ignore nodes with non-primitive type.

    BasicType bt;

    if (n->is_Mem()) {

      bt = n->as_Mem()->memory_type();

    } else {

      bt = n->bottom_type()->basic_type();

    }

    if (is_java_primitive(bt) == false) {

      ignored_loop_nodes[i] = n->_idx;

      continue;

    }

    if (n->is_Mem()) {

      MemNode* current = n->as_Mem();

      Node* adr = n->in(MemNode::Address);

      Node* n_ctrl = _phase->get_ctrl(adr);

      // save a queue of post process nodes

      if (n_ctrl != NULL && lpt()->is_member(_phase->get_loop(n_ctrl))) {

        // Process the memory expression

        int stack_idx = 0;

        bool have_side_effects = true;

        if (adr->is_AddP() == false) {

          nstack.push(adr, stack_idx++);

        } else {

          // Mark the components of the memory operation in nstack

          SWPointer p1(current, this, &nstack, true);

          have_side_effects = p1.node_stack()->is_nonempty();

        }

        // Process the pointer stack

        while (have_side_effects) {

          Node* pointer_node = nstack.node();

          for (uint j = 0; j < lpt()->_body.size(); j++) {

            Node* cur_node = lpt()->_body.at(j);

            if (cur_node == pointer_node) {

              ignored_loop_nodes[j] = cur_node->_idx;

              break;

            }

          }

          nstack.pop();

          have_side_effects = nstack.is_nonempty();

        }

      }

    }

  }

  if (is_slp) {

    // Now we try to find the maximum supported consistent vector which the machine

    // description can use

    for (uint i = 0; i < lpt()->_body.size(); i++) {

      if (ignored_loop_nodes[i] != -1) continue;

      BasicType bt;

      Node* n = lpt()->_body.at(i);

      if (n->is_Mem()) {

        bt = n->as_Mem()->memory_type();

      } else {

        bt = n->bottom_type()->basic_type();

      }

      if (is_java_primitive(bt) == false) continue;

      int cur_max_vector = Matcher::max_vector_size(bt);

      // If a max vector exists which is not larger than _local_loop_unroll_factor

      // stop looking, we already have the max vector to map to.

      if (cur_max_vector < local_loop_unroll_factor) {

        is_slp = false;

        NOT_PRODUCT(if (TraceSuperWordLoopUnrollAnalysis) tty->print_cr("slp analysis fails: unroll limit greater than max vector\n"));

        break;

      }

      // Map the maximal common vector

      if (VectorNode::implemented(n->Opcode(), cur_max_vector, bt)) {

        if (cur_max_vector < max_vector) {

          max_vector = cur_max_vector;

        }

      }

    }

    if (is_slp) {

      local_loop_unroll_factor = max_vector;

      cl->mark_passed_slp();

    }

    cl->mark_was_slp();

    cl->set_slp_max_unroll(local_loop_unroll_factor);

  }

}

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

#ifndef PRODUCT

  if (_do_vector_loop && TraceSuperWord) {

    tty->print("SuperWord::SLP_extract\n");

    tty->print("input loop\n");

    _lpt->dump_head();

    _lpt->dump();

    for (uint i = 0; i < _lpt->_body.size(); i++) {

      _lpt->_body.at(i)->dump();

    }

  }

#endif

  // Ready the block

  if (!construct_bb()) {

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

  }

  // build    _dg, _disjoint_ptrs

  dependence_graph();

  // compute function depth(Node*)

  compute_max_depth();

  if (_do_vector_loop) {

    if (mark_generations() != -1) {

      hoist_loads_in_graph(); // this only rebuild the graph; all basic structs need rebuild explicitly

      if (!construct_bb()) {

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

      }

      dependence_graph();

      compute_max_depth();

    }

#ifndef PRODUCT

    if (TraceSuperWord) {

      tty->print_cr("\nSuperWord::_do_vector_loop: graph after hoist_loads_in_graph");

      _lpt->dump_head();

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

        Node* n = _block.at(j);

        int d = depth(n);

        for (int i = 0;  i < d; i++) tty->print("%s", "  ");

        tty->print("%d :", d);

        n->dump();

      }

    }

#endif

  }

  compute_vector_element_type();

  // Attempt vectorization

  find_adjacent_refs();

  extend_packlist();

  if (_do_vector_loop) {

    if (_packset.length() == 0) {

#ifndef PRODUCT

      if (TraceSuperWord) {

        tty->print_cr("\nSuperWord::_do_vector_loop DFA could not build packset, now trying to build anyway");

      }

#endif

      pack_parallel();

    }

  }

  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;

      NOT_PRODUCT(find_adjacent_refs_trace_1(best_align_to_mem_ref, best_iv_adjustment);)

    }

    SWPointer align_to_ref_p(mem_ref, this, NULL, false);

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

           (!_do_vector_loop || same_origin_idx(s, mem_ref))) {

        SWPointer p2(s, this, NULL, false);

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

      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 {

          SWPointer p2(best_align_to_mem_ref, this, NULL, false);

          if (align_to_ref_p.invar() != p2.invar()) {

            // Do not vectorize memory accesses with different invariants

            // if unaligned memory accesses are not allowed.

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