/*

 * Copyright (c) 2007, 2017, 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 "memory/resourceArea.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"

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

  _post_block(arena(), 8, 0, NULL),       // nodes common to current block which are marked as post loop vectorizable

  _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

  _cmovev_kit(_arena, this),              // map to facilitate CMoveVD creation

  _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

  _do_reserve_copy(DoReserveCopyInSuperWord),

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

    _vector_loop_debug = phase->C->directive()->VectorizeDebugOption;

  }

#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

  bool post_loop_allowed = (PostLoopMultiversioning && Matcher::has_predicated_vectors() && cl->is_post_loop());

  if (post_loop_allowed) {

    if (cl->is_reduction_loop()) return; // no predication mapping

    Node *limit = cl->limit();

    if (limit->is_Con()) return; // non constant limits only

    // Now check the limit for expressions we do not handle

    if (limit->is_Add()) {

      Node *in2 = limit->in(2);

      if (in2->is_Con()) {

        int val = in2->get_int();

        // should not try to program these cases

        if (val < 0) return;

      }

    }

  }

  // skip any loop that has not been assigned max unroll by analysis

  if (do_optimization) {

    if (SuperWordLoopUnrollAnalysis && cl->slp_max_unroll() == 0) return;

  }

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

  Node *cl_exit = cl->loopexit();

  if (cl->is_main_loop() && (cl_exit->in(0) != lpt->_head)) {

    #ifndef PRODUCT

      if (TraceSuperWord) {

        tty->print_cr("SuperWord::transform_loop: loop too complicated, cl_exit->in(0) != lpt->_head");

        tty->print("cl_exit %d", cl_exit->_idx); cl_exit->dump();

        tty->print("cl_exit->in(0) %d", cl_exit->in(0)->_idx); cl_exit->in(0)->dump();

        tty->print("lpt->_head %d", lpt->_head->_idx); lpt->_head->dump();

        lpt->dump_head();

      }

    #endif

    return;

  }

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

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

    return;

  }

  // Skip any loops already optimized by slp

  if (cl->is_vectorized_loop()) return;

  if (cl->is_main_loop()) {

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

    if (PostLoopMultiversioning && Matcher::has_predicated_vectors()) {

      if (cl->is_vectorized_loop() && cl->is_main_loop() && !cl->is_reduction_loop()) {

        IdealLoopTree *lpt_next = lpt->_next;

        CountedLoopNode *cl_next = lpt_next->_head->as_CountedLoop();

        _phase->has_range_checks(lpt_next);

        if (cl_next->is_post_loop() && !cl_next->range_checks_present()) {

          if (!cl_next->is_vectorized_loop()) {

            int slp_max_unroll_factor = cl->slp_max_unroll();

            cl_next->set_slp_max_unroll(slp_max_unroll_factor);

          }

        }

      }

    }

  }

}

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

  int rpo_idx = _post_block.length();

  assert(rpo_idx == 0, "post loop block is empty");

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

  bool post_loop_allowed = (PostLoopMultiversioning && Matcher::has_predicated_vectors() && cl->is_post_loop());

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

    bool small_basic_type = false;

    bool flag_small_bt = false;

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

        if (!small_basic_type) {

          switch (bt) {

          case T_CHAR:

          case T_BYTE:

          case T_SHORT:

            small_basic_type = true;

            break;

          case T_LONG:

            // TODO: Remove when support completed for mask context with LONG.

            //       Support needs to be augmented for logical qword operations, currently we map to dword

            //       buckets for vectors on logicals as these were legacy.

            small_basic_type = true;

            break;

          default:

            break;

          }

        }

      }

      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;

        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 && !flag_small_bt) {

          max_vector = cur_max_vector;

        } else if (cur_max_vector > max_vector && UseSubwordForMaxVector) {

          // Analyse subword in the loop to set maximum vector size to take advantage of full vector width for subword types.

          // Here we analyze if narrowing is likely to happen and if it is we set vector size more aggressively.

          // We check for possibility of narrowing by looking through chain operations using subword types.

          if (is_subword_type(bt)) {

            uint start, end;

            VectorNode::vector_operands(n, &start, &end);

            for (uint j = start; j < end; j++) {

              Node* in = n->in(j);

              // Don't propagate through a memory

              if (!in->is_Mem() && in_bb(in) && in->bottom_type()->basic_type() == T_INT) {

                bool same_type = true;

                for (DUIterator_Fast kmax, k = in->fast_outs(kmax); k < kmax; k++) {

                  Node *use = in->fast_out(k);

                  if (!in_bb(use) && use->bottom_type()->basic_type() != bt) {

                    same_type = false;

                    break;

                  }

                }

                if (same_type) {

                  max_vector = cur_max_vector;

                  flag_small_bt = true;

                }

              }

            }

          }

        }

        // We only process post loops on predicated targets where we want to

        // mask map the loop to a single iteration

        if (post_loop_allowed) {

          _post_block.at_put_grow(rpo_idx++, n);

        }

      }

    }

    if (is_slp) {

      local_loop_unroll_factor = max_vector;

      cl->mark_passed_slp();

    }

    cl->mark_was_slp();

    if (cl->is_main_loop()) {

      cl->set_slp_max_unroll(local_loop_unroll_factor);

    } else if (post_loop_allowed) {

      if (!small_basic_type) {

        // avoid replication context for small basic types in programmable masked loops

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

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

  bool post_loop_allowed = (PostLoopMultiversioning && Matcher::has_predicated_vectors() && cl->is_post_loop());

  if (cl->is_main_loop()) {

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