/*

 * Copyright (c) 1998, 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 "ci/ciMethodData.hpp"

#include "compiler/compileLog.hpp"

#include "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/connode.hpp"

#include "opto/convertnode.hpp"

#include "opto/divnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/loopnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/rootnode.hpp"

#include "opto/superword.hpp"

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

//------------------------------is_loop_iv-------------------------------------

// Determine if a node is Counted loop induction variable.

// The method is declared in node.hpp.

const Node* Node::is_loop_iv() const {

  if (this->is_Phi() && !this->as_Phi()->is_copy() &&

      this->as_Phi()->region()->is_CountedLoop() &&

      this->as_Phi()->region()->as_CountedLoop()->phi() == this) {

    return this;

  } else {

    return NULL;

  }

}

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

//------------------------------dump_spec--------------------------------------

// Dump special per-node info

#ifndef PRODUCT

void LoopNode::dump_spec(outputStream *st) const {

  if (is_inner_loop()) st->print( "inner " );

  if (is_partial_peel_loop()) st->print( "partial_peel " );

  if (partial_peel_has_failed()) st->print( "partial_peel_failed " );

}

#endif

//------------------------------is_valid_counted_loop-------------------------

bool LoopNode::is_valid_counted_loop() const {

  if (is_CountedLoop()) {

    CountedLoopNode*    l  = as_CountedLoop();

    CountedLoopEndNode* le = l->loopexit();

    if (le != NULL &&

        le->proj_out(1 /* true */) == l->in(LoopNode::LoopBackControl)) {

      Node* phi  = l->phi();

      Node* exit = le->proj_out(0 /* false */);

      if (exit != NULL && exit->Opcode() == Op_IfFalse &&

          phi != NULL && phi->is_Phi() &&

          phi->in(LoopNode::LoopBackControl) == l->incr() &&

          le->loopnode() == l && le->stride_is_con()) {

        return true;

      }

    }

  }

  return false;

}

//------------------------------get_early_ctrl---------------------------------

// Compute earliest legal control

Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {

  assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );

  uint i;

  Node *early;

  if (n->in(0) && !n->is_expensive()) {

    early = n->in(0);

    if (!early->is_CFG()) // Might be a non-CFG multi-def

      early = get_ctrl(early);        // So treat input as a straight data input

    i = 1;

  } else {

    early = get_ctrl(n->in(1));

    i = 2;

  }

  uint e_d = dom_depth(early);

  assert( early, "" );

  for (; i < n->req(); i++) {

    Node *cin = get_ctrl(n->in(i));

    assert( cin, "" );

    // Keep deepest dominator depth

    uint c_d = dom_depth(cin);

    if (c_d > e_d) {           // Deeper guy?

      early = cin;              // Keep deepest found so far

      e_d = c_d;

    } else if (c_d == e_d &&    // Same depth?

               early != cin) { // If not equal, must use slower algorithm

      // If same depth but not equal, one _must_ dominate the other

      // and we want the deeper (i.e., dominated) guy.

      Node *n1 = early;

      Node *n2 = cin;

      while (1) {

        n1 = idom(n1);          // Walk up until break cycle

        n2 = idom(n2);

        if (n1 == cin ||        // Walked early up to cin

            dom_depth(n2) < c_d)

          break;                // early is deeper; keep him

        if (n2 == early ||      // Walked cin up to early

            dom_depth(n1) < c_d) {

          early = cin;          // cin is deeper; keep him

          break;

        }

      }

      e_d = dom_depth(early);   // Reset depth register cache

    }

  }

  // Return earliest legal location

  assert(early == find_non_split_ctrl(early), "unexpected early control");

  if (n->is_expensive() && !_verify_only && !_verify_me) {

    assert(n->in(0), "should have control input");

    early = get_early_ctrl_for_expensive(n, early);

  }

  return early;

}

//------------------------------get_early_ctrl_for_expensive---------------------------------

// Move node up the dominator tree as high as legal while still beneficial

Node *PhaseIdealLoop::get_early_ctrl_for_expensive(Node *n, Node* earliest) {

  assert(n->in(0) && n->is_expensive(), "expensive node with control input here");

  assert(OptimizeExpensiveOps, "optimization off?");

  Node* ctl = n->in(0);

  assert(ctl->is_CFG(), "expensive input 0 must be cfg");

  uint min_dom_depth = dom_depth(earliest);

#ifdef ASSERT

  if (!is_dominator(ctl, earliest) && !is_dominator(earliest, ctl)) {

    dump_bad_graph("Bad graph detected in get_early_ctrl_for_expensive", n, earliest, ctl);

    assert(false, "Bad graph detected in get_early_ctrl_for_expensive");

  }

#endif

  if (dom_depth(ctl) < min_dom_depth) {

    return earliest;

  }

  while (1) {

    Node *next = ctl;

    // Moving the node out of a loop on the projection of a If

    // confuses loop predication. So once we hit a Loop in a If branch

    // that doesn't branch to an UNC, we stop. The code that process

    // expensive nodes will notice the loop and skip over it to try to

    // move the node further up.

    if (ctl->is_CountedLoop() && ctl->in(1) != NULL && ctl->in(1)->in(0) != NULL && ctl->in(1)->in(0)->is_If()) {

      if (!ctl->in(1)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {

        break;

      }

      next = idom(ctl->in(1)->in(0));

    } else if (ctl->is_Proj()) {

      // We only move it up along a projection if the projection is

      // the single control projection for its parent: same code path,

      // if it's a If with UNC or fallthrough of a call.

      Node* parent_ctl = ctl->in(0);

      if (parent_ctl == NULL) {

        break;

      } else if (parent_ctl->is_CountedLoopEnd() && parent_ctl->as_CountedLoopEnd()->loopnode() != NULL) {

        next = parent_ctl->as_CountedLoopEnd()->loopnode()->init_control();

      } else if (parent_ctl->is_If()) {

        if (!ctl->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) {

          break;

        }

        assert(idom(ctl) == parent_ctl, "strange");

        next = idom(parent_ctl);

      } else if (ctl->is_CatchProj()) {

        if (ctl->as_Proj()->_con != CatchProjNode::fall_through_index) {

          break;

        }

        assert(parent_ctl->in(0)->in(0)->is_Call(), "strange graph");

        next = parent_ctl->in(0)->in(0)->in(0);

      } else {

        // Check if parent control has a single projection (this

        // control is the only possible successor of the parent

        // control). If so, we can try to move the node above the

        // parent control.

        int nb_ctl_proj = 0;

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

          Node *p = parent_ctl->fast_out(i);

          if (p->is_Proj() && p->is_CFG()) {

            nb_ctl_proj++;

            if (nb_ctl_proj > 1) {

              break;

            }

          }

        }

        if (nb_ctl_proj > 1) {

          break;

        }

        assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call(), "unexpected node");

        assert(idom(ctl) == parent_ctl, "strange");

        next = idom(parent_ctl);

      }

    } else {

      next = idom(ctl);

    }

    if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {

      break;

    }

    ctl = next;

  }

  if (ctl != n->in(0)) {

    _igvn.replace_input_of(n, 0, ctl);

    _igvn.hash_insert(n);

  }

  return ctl;

}

//------------------------------set_early_ctrl---------------------------------

// Set earliest legal control

void PhaseIdealLoop::set_early_ctrl( Node *n ) {

  Node *early = get_early_ctrl(n);

  // Record earliest legal location

  set_ctrl(n, early);

}

//------------------------------set_subtree_ctrl-------------------------------

// set missing _ctrl entries on new nodes

void PhaseIdealLoop::set_subtree_ctrl( Node *n ) {

  // Already set?  Get out.

  if( _nodes[n->_idx] ) return;

  // Recursively set _nodes array to indicate where the Node goes

  uint i;

  for( i = 0; i < n->req(); ++i ) {

    Node *m = n->in(i);

    if( m && m != C->root() )

      set_subtree_ctrl( m );

  }

  // Fixup self

  set_early_ctrl( n );

}

//------------------------------is_counted_loop--------------------------------

bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) {

  PhaseGVN *gvn = &_igvn;

  // Counted loop head must be a good RegionNode with only 3 not NULL

  // control input edges: Self, Entry, LoopBack.

  if (x->in(LoopNode::Self) == NULL || x->req() != 3 || loop->_irreducible) {

    return false;

  }

  Node *init_control = x->in(LoopNode::EntryControl);

  Node *back_control = x->in(LoopNode::LoopBackControl);

  if (init_control == NULL || back_control == NULL)    // Partially dead

    return false;

  // Must also check for TOP when looking for a dead loop

  if (init_control->is_top() || back_control->is_top())

    return false;

  // Allow funny placement of Safepoint

  if (back_control->Opcode() == Op_SafePoint)

    back_control = back_control->in(TypeFunc::Control);

  // Controlling test for loop

  Node *iftrue = back_control;

  uint iftrue_op = iftrue->Opcode();

  if (iftrue_op != Op_IfTrue &&

      iftrue_op != Op_IfFalse)

    // I have a weird back-control.  Probably the loop-exit test is in

    // the middle of the loop and I am looking at some trailing control-flow

    // merge point.  To fix this I would have to partially peel the loop.

    return false; // Obscure back-control

  // Get boolean guarding loop-back test

  Node *iff = iftrue->in(0);

  if (get_loop(iff) != loop || !iff->in(1)->is_Bool())

    return false;

  BoolNode *test = iff->in(1)->as_Bool();

  BoolTest::mask bt = test->_test._test;

  float cl_prob = iff->as_If()->_prob;

  if (iftrue_op == Op_IfFalse) {

    bt = BoolTest(bt).negate();

    cl_prob = 1.0 - cl_prob;

  }

  // Get backedge compare

  Node *cmp = test->in(1);

  int cmp_op = cmp->Opcode();

  if (cmp_op != Op_CmpI)

    return false;                // Avoid pointer & float compares

  // Find the trip-counter increment & limit.  Limit must be loop invariant.

  Node *incr  = cmp->in(1);

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

  // ---------

  // need 'loop()' test to tell if limit is loop invariant

  // ---------

  if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?

    Node *tmp = incr;            // Then reverse order into the CmpI

    incr = limit;

    limit = tmp;

    bt = BoolTest(bt).commute(); // And commute the exit test

  }

  if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant

    return false;

  if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant

    return false;

  Node* phi_incr = NULL;

  // Trip-counter increment must be commutative & associative.

  if (incr->is_Phi()) {

    if (incr->as_Phi()->region() != x || incr->req() != 3)

      return false; // Not simple trip counter expression

    phi_incr = incr;

    incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi

    if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant

      return false;

  }

  Node* trunc1 = NULL;

  Node* trunc2 = NULL;

  const TypeInt* iv_trunc_t = NULL;

  if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {

    return false; // Funny increment opcode

  }

  assert(incr->Opcode() == Op_AddI, "wrong increment code");

  // Get merge point

  Node *xphi = incr->in(1);

  Node *stride = incr->in(2);

  if (!stride->is_Con()) {     // Oops, swap these

    if (!xphi->is_Con())       // Is the other guy a constant?

      return false;             // Nope, unknown stride, bail out

    Node *tmp = xphi;           // 'incr' is commutative, so ok to swap

    xphi = stride;

    stride = tmp;

  }

  // Stride must be constant

  int stride_con = stride->get_int();

  if (stride_con == 0)

    return false; // missed some peephole opt

  if (!xphi->is_Phi())

    return false; // Too much math on the trip counter

  if (phi_incr != NULL && phi_incr != xphi)

    return false;

  PhiNode *phi = xphi->as_Phi();

  // Phi must be of loop header; backedge must wrap to increment

  if (phi->region() != x)

    return false;

  if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr ||

      trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) {

    return false;

  }

  Node *init_trip = phi->in(LoopNode::EntryControl);

  // If iv trunc type is smaller than int, check for possible wrap.

  if (!TypeInt::INT->higher_equal(iv_trunc_t)) {

    assert(trunc1 != NULL, "must have found some truncation");

    // Get a better type for the phi (filtered thru if's)

    const TypeInt* phi_ft = filtered_type(phi);

    // Can iv take on a value that will wrap?

    //

    // Ensure iv's limit is not within "stride" of the wrap value.

    //

    // Example for "short" type

    //    Truncation ensures value is in the range -32768..32767 (iv_trunc_t)

    //    If the stride is +10, then the last value of the induction

    //    variable before the increment (phi_ft->_hi) must be

    //    <= 32767 - 10 and (phi_ft->_lo) must be >= -32768 to

    //    ensure no truncation occurs after the increment.

    if (stride_con > 0) {

      if (iv_trunc_t->_hi - phi_ft->_hi < stride_con ||

          iv_trunc_t->_lo > phi_ft->_lo) {

        return false;  // truncation may occur

      }

    } else if (stride_con < 0) {

      if (iv_trunc_t->_lo - phi_ft->_lo > stride_con ||

          iv_trunc_t->_hi < phi_ft->_hi) {

        return false;  // truncation may occur

      }

    }

    // No possibility of wrap so truncation can be discarded

    // Promote iv type to Int

  } else {

    assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int");

  }

  // If the condition is inverted and we will be rolling

  // through MININT to MAXINT, then bail out.

  if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!

      // Odd stride

      bt == BoolTest::ne && stride_con != 1 && stride_con != -1 ||

      // Count down loop rolls through MAXINT

      (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 ||

      // Count up loop rolls through MININT

      (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) {

    return false; // Bail out

  }

  const TypeInt* init_t = gvn->type(init_trip)->is_int();

  const TypeInt* limit_t = gvn->type(limit)->is_int();

  if (stride_con > 0) {

    jlong init_p = (jlong)init_t->_lo + stride_con;

    if (init_p > (jlong)max_jint || init_p > (jlong)limit_t->_hi)

      return false; // cyclic loop or this loop trips only once

  } else {

    jlong init_p = (jlong)init_t->_hi + stride_con;

    if (init_p < (jlong)min_jint || init_p < (jlong)limit_t->_lo)

      return false; // cyclic loop or this loop trips only once

  }

  if (phi_incr != NULL) {

    // check if there is a possiblity of IV overflowing after the first increment

    if (stride_con > 0) {

      if (init_t->_hi > max_jint - stride_con) {

        return false;

      }

    } else {

      if (init_t->_lo < min_jint - stride_con) {

        return false;

      }

    }

  }

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

  // ---- SUCCESS!   Found A Trip-Counted Loop!  -----

  //

  assert(x->Opcode() == Op_Loop, "regular loops only");

  C->print_method(PHASE_BEFORE_CLOOPS, 3);

  Node *hook = new Node(6);

  if (LoopLimitCheck) {

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

  // Generate loop limit check to avoid integer overflow

  // in cases like next (cyclic loops):

  //

  // for (i=0; i <= max_jint; i++) {}

  // for (i=0; i <  max_jint; i+=2) {}

  //

  //

  // Limit check predicate depends on the loop test:

  //

  // for(;i != limit; i++)       --> limit <= (max_jint)

  // for(;i <  limit; i+=stride) --> limit <= (max_jint - stride + 1)

  // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride    )

  //

  // Check if limit is excluded to do more precise int overflow check.

  bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge);

  int stride_m  = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1));

  // If compare points directly to the phi we need to adjust

  // the compare so that it points to the incr. Limit have

  // to be adjusted to keep trip count the same and the

  // adjusted limit should be checked for int overflow.

  if (phi_incr != NULL) {

    stride_m  += stride_con;

  }

  if (limit->is_Con()) {

    int limit_con = limit->get_int();

    if ((stride_con > 0 && limit_con > (max_jint - stride_m)) ||

        (stride_con < 0 && limit_con < (min_jint - stride_m))) {

      // Bailout: it could be integer overflow.

      return false;

    }

  } else if ((stride_con > 0 && limit_t->_hi <= (max_jint - stride_m)) ||

             (stride_con < 0 && limit_t->_lo >= (min_jint - stride_m))) {

      // Limit's type may satisfy the condition, for example,

      // when it is an array length.

  } else {

    // Generate loop's limit check.

    // Loop limit check predicate should be near the loop.