/*

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

  assert(stride_con != 0, "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);

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

  Node *hook = new (C, 6) Node(6);

  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

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

    set_subtree_ctrl( limit );

    hook->init_req(4, limit);

    bt = BoolTest::lt;

    // Make the new limit be in the same loop nest as the old limit

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

    // Fall into next case

  case BoolTest::lt: {          // Maybe convert to '!=' case

    if (stride_con < 0) // Count down loop rolls through MAXINT

      ShouldNotReachHere();

    Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip));

    set_subtree_ctrl( range );

    hook->init_req(0, range);

    Node *bias  = gvn->transform(new (C, 3) AddINode(range,stride));

    set_subtree_ctrl( bias );

    hook->init_req(1, bias);

    Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_m));

    set_subtree_ctrl( bias1 );

    hook->init_req(2, bias1);

    trip_count  = gvn->transform(new (C, 3) DivINode(0,bias1,stride));

    set_subtree_ctrl( trip_count );

    hook->init_req(3, trip_count);

    break;

  }

  case BoolTest::ge:            // Maybe convert to '>' case

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

    set_subtree_ctrl( limit );

    hook->init_req(4 ,limit);

    bt = BoolTest::gt;

    // Make the new limit be in the same loop nest as the old limit

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

    // Fall into next case

  case BoolTest::gt: {          // Maybe convert to '!=' case

    if (stride_con > 0) // count up loop rolls through MININT

      ShouldNotReachHere();

    Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip));

    set_subtree_ctrl( range );

    hook->init_req(0, range);

    Node *bias  = gvn->transform(new (C, 3) AddINode(range,stride));

    set_subtree_ctrl( bias );

    hook->init_req(1, bias);

    Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_p));

    set_subtree_ctrl( bias1 );

    hook->init_req(2, bias1);

    trip_count  = gvn->transform(new (C, 3) DivINode(0,bias1,stride));

    set_subtree_ctrl( trip_count );

    hook->init_req(3, trip_count);

    break;

  }

  } // switch( bt )

  Node *span = gvn->transform(new (C, 3) MulINode(trip_count,stride));

  set_subtree_ctrl( span );

  hook->init_req(5, span);

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

  set_subtree_ctrl( limit );

  // Check for SafePoint on backedge and remove

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

  if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) {

    lazy_replace( sfpt, iftrue );

    loop->_tail = iftrue;

  }

  // Build a canonical trip test.

  // Clone code, as old values may be in use.

  Node* nphi = PhiNode::make(x, init_trip, TypeInt::INT);

  nphi = _igvn.register_new_node_with_optimizer(nphi);

  set_ctrl(nphi, get_ctrl(phi));

  incr = incr->clone();

  incr->set_req(1,nphi);

  incr->set_req(2,stride);

  incr = _igvn.register_new_node_with_optimizer(incr);

  set_early_ctrl( incr );

  nphi->set_req(LoopNode::LoopBackControl, incr);

  _igvn.replace_node(phi, nphi);

  phi = nphi->as_Phi();

  cmp = cmp->clone();

  cmp->set_req(1,incr);

  cmp->set_req(2,limit);

  cmp = _igvn.register_new_node_with_optimizer(cmp);

  set_ctrl(cmp, iff->in(0));

  test = test->clone()->as_Bool();

  (*(BoolTest*)&test->_test)._test = bt;

  test->set_req(1,cmp);

  _igvn.register_new_node_with_optimizer(test);

  set_ctrl(test, iff->in(0));

  // Replace the old IfNode with a new LoopEndNode

  Node *lex = _igvn.register_new_node_with_optimizer(new (C, 2) CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));

  IfNode *le = lex->as_If();

  uint dd = dom_depth(iff);

  set_idom(le, le->in(0), dd); // Update dominance for loop exit

  set_loop(le, loop);

  // Get the loop-exit control

  Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue));

  // Need to swap loop-exit and loop-back control?

  if (iftrue_op == Op_IfFalse) {

    Node *ift2=_igvn.register_new_node_with_optimizer(new (C, 1) IfTrueNode (le));

    Node *iff2=_igvn.register_new_node_with_optimizer(new (C, 1) IfFalseNode(le));

    loop->_tail = back_control = ift2;

    set_loop(ift2, loop);

    set_loop(iff2, get_loop(iffalse));

    // Lazy update of 'get_ctrl' mechanism.

    lazy_replace_proj( iffalse, iff2 );

    lazy_replace_proj( iftrue,  ift2 );

    // Swap names

    iffalse = iff2;

    iftrue  = ift2;

  } else {

    _igvn.hash_delete(iffalse);

    _igvn.hash_delete(iftrue);

    iffalse->set_req_X( 0, le, &_igvn );

    iftrue ->set_req_X( 0, le, &_igvn );

  }