/*

 * Copyright (c) 1998, 2011, 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/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) ) {

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

  return early;

}

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

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

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

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

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

  } else {

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

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

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

  }

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

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

  //

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

  C->print_method("Before CountedLoop", 3);

  Node *hook = new (C, 6) 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.

    ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);

    if (!limit_check_proj) {

      // The limit check predicate is not generated if this method trapped here before.

#ifdef ASSERT

      if (TraceLoopLimitCheck) {

        tty->print("missing loop limit check:");

        loop->dump_head();

        x->dump(1);

      }

#endif

      return false;

    }

    IfNode* check_iff = limit_check_proj->in(0)->as_If();

    Node* cmp_limit;

    Node* bol;

    if (stride_con > 0) {

      cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(max_jint - stride_m));

      bol = new (C, 2) BoolNode(cmp_limit, BoolTest::le);

    } else {

      cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(min_jint - stride_m));

      bol = new (C, 2) BoolNode(cmp_limit, BoolTest::ge);

    }

    cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);

    bol = _igvn.register_new_node_with_optimizer(bol);

    set_subtree_ctrl(bol);

    // Replace condition in original predicate but preserve Opaque node

    // so that previous predicates could be found.

    assert(check_iff->in(1)->Opcode() == Op_Conv2B &&

           check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, "");

    Node* opq = check_iff->in(1)->in(1);

    _igvn.hash_delete(opq);

    opq->set_req(1, bol);

    // Update ctrl.

    set_ctrl(opq, check_iff->in(0));

    set_ctrl(check_iff->in(1), check_iff->in(0));

#ifndef PRODUCT

    // report that the loop predication has been actually performed

    // for this loop

    if (TraceLoopLimitCheck) {

      tty->print_cr("Counted Loop Limit Check generated:");

      debug_only( bol->dump(2); )

    }

#endif

  }

  if (phi_incr != NULL) {

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

    // should avoid int overflow.

    //

    //   i = init; do {} while(i++ < limit);

    // is converted to

    //   i = init; do {} while(++i < limit+1);

    //

    limit = gvn->transform(new (C, 3) AddINode(limit, stride));

  }

  // Now we need to canonicalize loop condition.

  if (bt == BoolTest::ne) {

    assert(stride_con == 1 || stride_con == -1, "simple increment only");

    // 'ne' can be replaced with 'lt' only when init < limit.

    if (stride_con > 0 && init_t->_hi < limit_t->_lo)

      bt = BoolTest::lt;

    // 'ne' can be replaced with 'gt' only when init > limit.

    if (stride_con < 0 && init_t->_lo > limit_t->_hi)

      bt = BoolTest::gt;

  }

  if (incl_limit) {

    // The limit check guaranties that 'limit <= (max_jint - stride)' so

    // we can convert 'i <= limit' to 'i < limit+1' since stride != 0.

    //

    Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1);

    limit = gvn->transform(new (C, 3) AddINode(limit, one));

    if (bt == BoolTest::le)

      bt = BoolTest::lt;

    else if (bt == BoolTest::ge)

      bt = BoolTest::gt;

    else

      ShouldNotReachHere();

  }

  set_subtree_ctrl( limit );

  } else { // LoopLimitCheck

  // If compare points to incr, we are ok.  Otherwise the compare

  // can directly point to the phi; in this case adjust the compare so that

  // it points to the incr by adjusting the limit.

  if (cmp->in(1) == phi || cmp->in(2) == phi)

    limit = gvn->transform(new (C, 3) AddINode(limit,stride));

  // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.

  // Final value for iterator should be: trip_count * stride + init_trip.

  Node *one_p = gvn->intcon( 1);

  Node *one_m = gvn->intcon(-1);

  Node *trip_count = NULL;

  switch( bt ) {

  case BoolTest::eq:

    ShouldNotReachHere();

  case BoolTest::ne:            // Ahh, the case we desire

    if (stride_con == 1)

      trip_count = gvn->transform(new (C, 3) SubINode(limit,init_trip));

    else if (stride_con == -1)

      trip_count = gvn->transform(new (C, 3) SubINode(init_trip,limit));

    else

      ShouldNotReachHere();

    set_subtree_ctrl(trip_count);

    //_loop.map(trip_count->_idx,loop(limit));

    break;

  case BoolTest::le:            // Maybe convert to '<' case