/*

 * Copyright 1998-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_loopnode.cpp.incl"

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

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

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

Node *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 NULL;

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

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

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

    return NULL;

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

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

    return NULL;

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

  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 NULL;                // 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 loop-invariant

    return NULL;

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

  uint incr_op = incr->Opcode();

  if( incr_op == Op_Phi && incr->req() == 3 ) {

    incr = incr->in(2);         // Assume incr is on backedge of Phi

    incr_op = incr->Opcode();

  }

  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 NULL; // Funny increment opcode

  }

  // 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 NULL;              // Nope, unknown stride, bail out

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

    xphi = stride;

    stride = tmp;

  }

  //if( loop(xphi) != l) return NULL;// Merge point is in inner loop??

  if( !xphi->is_Phi() ) return NULL; // Too much math on the trip counter

  PhiNode *phi = xphi->as_Phi();

  // Stride must be constant

  const Type *stride_t = stride->bottom_type();

  int stride_con = stride_t->is_int()->get_con();

  assert( stride_con, "missed some peephole opt" );

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

  if( phi->region() != x ) return NULL;

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

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

    return NULL;

  }

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

  //if (!init_trip->is_Con()) return NULL; // avoid rolling over MAXINT/MININT

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

  }

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

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

  //

  // Canonicalize the condition on the test.  If we can exactly determine

  // the trip-counter exit value, then set limit to that value and use

  // a '!=' test.  Otherwise use conditon '<' for count-up loops and

  // '>' for count-down loops.  If the condition is inverted and we will

  // be rolling through MININT to MAXINT, then bail out.

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

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

  }

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

  const Type *limit_t = limit->bottom_type();

  const Type *init_t = init_trip->bottom_type();

  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:

    return NULL;                // Bail out, but this loop trips at most twice!

  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

      return NULL;              // Odd stride; must prove we hit limit exactly

    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 ) return NULL; // Count down loop rolls through MAXINT

    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 ) return NULL; // count up loop rolls through MININT

    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;

  }

  }

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

  // Build a canonical trip test.

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

  incr = incr->clone();

  incr->set_req(1,phi);

  incr->set_req(2,stride);

  incr = _igvn.register_new_node_with_optimizer(incr);

  set_early_ctrl( incr );

  _igvn.hash_delete(phi);

  phi->set_req_X( LoopNode::LoopBackControl, incr, &_igvn );

  // If phi type is more restrictive than Int, raise to

  // Int to prevent (almost) infinite recursion in igvn

  // which can only handle integer types for constants or minint..maxint.

  if (!TypeInt::INT->higher_equal(phi->bottom_type())) {

    Node* nphi = PhiNode::make(phi->in(0), phi->in(LoopNode::EntryControl), TypeInt::INT);

    nphi->set_req(LoopNode::LoopBackControl, phi->in(LoopNode::LoopBackControl));

    nphi = _igvn.register_new_node_with_optimizer(nphi);

    set_ctrl(nphi, get_ctrl(phi));

    _igvn.subsume_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));

  Node *tmp = test->clone();

  assert( tmp->is_Bool(), "" );

  test = (BoolNode*)tmp;

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

  test->set_req(1,cmp);

  _igvn.register_new_node_with_optimizer(test);

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

  // If the exit test is dead, STOP!

  if( test == NULL ) return NULL;

  _igvn.hash_delete(iff);

  iff->set_req_X( 1, test, &_igvn );

  // Replace the old IfNode with a new LoopEndNode

  Node *lex = _igvn.register_new_node_with_optimizer(new (C, 2) CountedLoopEndNode( iff->in(0), iff->in(1), 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 *if_f = 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(if_f));

    // Lazy update of 'get_ctrl' mechanism.

    lazy_replace_proj( if_f  , iff2 );

    lazy_replace_proj( iftrue, ift2 );

    // Swap names

    if_f   = iff2;

    iftrue = ift2;

  } else {

    _igvn.hash_delete(if_f  );

    _igvn.hash_delete(iftrue);

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

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

  }

  set_idom(iftrue, le, dd+1);

  set_idom(if_f,   le, dd+1);

  // Now setup a new CountedLoopNode to replace the existing LoopNode

  CountedLoopNode *l = new (C, 3) CountedLoopNode(init_control, back_control);

  // The following assert is approximately true, and defines the intention

  // of can_be_counted_loop.  It fails, however, because phase->type

  // is not yet initialized for this loop and its parts.

  //assert(l->can_be_counted_loop(this), "sanity");

  _igvn.register_new_node_with_optimizer(l);

  set_loop(l, loop);

  loop->_head = l;

  // Fix all data nodes placed at the old loop head.

  // Uses the lazy-update mechanism of 'get_ctrl'.

  lazy_replace( x, l );

  set_idom(l, init_control, dom_depth(x));

  // Check for immediately preceeding SafePoint and remove

  Node *sfpt2 = le->in(0);

  if( sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2))

    lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control));

  // Free up intermediate goo

  _igvn.remove_dead_node(hook);

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

  // Return trip counter

  return trip_count;

}

//------------------------------Ideal------------------------------------------

// Return a node which is more "ideal" than the current node.

// Attempt to convert into a counted-loop.

Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {

  if (!can_be_counted_loop(phase)) {

    phase->C->set_major_progress();

  }

  return RegionNode::Ideal(phase, can_reshape);

}

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

//------------------------------Ideal------------------------------------------

// Return a node which is more "ideal" than the current node.

// Attempt to convert into a counted-loop.

Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {

  return RegionNode::Ideal(phase, can_reshape);

}

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

// Dump special per-node info

#ifndef PRODUCT

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

  LoopNode::dump_spec(st);

  if( stride_is_con() ) {

    st->print("stride: %d ",stride_con());

  } else {

    st->print("stride: not constant ");

  }

  if( is_pre_loop () ) st->print("pre of N%d" , _main_idx );

  if( is_main_loop() ) st->print("main of N%d", _idx );

  if( is_post_loop() ) st->print("post of N%d", _main_idx );

}

#endif

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

int CountedLoopEndNode::stride_con() const {

  return stride()->bottom_type()->is_int()->get_con();

}