/*

 * Copyright 1999-2006 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/_loopopts.cpp.incl"

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

//------------------------------split_thru_phi---------------------------------

// Split Node 'n' through merge point if there is enough win.

Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {

  int wins = 0;

  assert( !n->is_CFG(), "" );

  assert( region->is_Region(), "" );

  Node *phi = new (C, region->req()) PhiNode( region, n->bottom_type() );

  uint old_unique = C->unique();

  for( uint i = 1; i < region->req(); i++ ) {

    Node *x;

    Node* the_clone = NULL;

    if( region->in(i) == C->top() ) {

      x = C->top();             // Dead path?  Use a dead data op

    } else {

      x = n->clone();           // Else clone up the data op

      the_clone = x;            // Remember for possible deletion.

      // Alter data node to use pre-phi inputs

      if( n->in(0) == region )

        x->set_req( 0, region->in(i) );

      for( uint j = 1; j < n->req(); j++ ) {

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

        if( in->is_Phi() && in->in(0) == region )

          x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone

      }

    }

    // Check for a 'win' on some paths

    const Type *t = x->Value(&_igvn);

    bool singleton = t->singleton();

    // A TOP singleton indicates that there are no possible values incoming

    // along a particular edge. In most cases, this is OK, and the Phi will

    // be eliminated later in an Ideal call. However, we can't allow this to

    // happen if the singleton occurs on loop entry, as the elimination of

    // the PhiNode may cause the resulting node to migrate back to a previous

    // loop iteration.

    if( singleton && t == Type::TOP ) {

      // Is_Loop() == false does not confirm the absence of a loop (e.g., an

      // irreducible loop may not be indicated by an affirmative is_Loop());

      // therefore, the only top we can split thru a phi is on a backedge of

      // a loop.

      singleton &= region->is_Loop() && (i != LoopNode::EntryControl);

    }

    if( singleton ) {

      wins++;

      x = ((PhaseGVN&)_igvn).makecon(t);

    } else {

      // We now call Identity to try to simplify the cloned node.

      // Note that some Identity methods call phase->type(this).

      // Make sure that the type array is big enough for

      // our new node, even though we may throw the node away.

      // (Note: This tweaking with igvn only works because x is a new node.)

      _igvn.set_type(x, t);

      Node *y = x->Identity(&_igvn);

      if( y != x ) {

        wins++;

        x = y;

      } else {

        y = _igvn.hash_find(x);

        if( y ) {

          wins++;

          x = y;

        } else {

          // Else x is a new node we are keeping

          // We do not need register_new_node_with_optimizer

          // because set_type has already been called.

          _igvn._worklist.push(x);

        }

      }

    }

    if (x != the_clone && the_clone != NULL)

      _igvn.remove_dead_node(the_clone);

    phi->set_req( i, x );

  }

  // Too few wins?

  if( wins <= policy ) {

    _igvn.remove_dead_node(phi);

    return NULL;

  }

  // Record Phi

  register_new_node( phi, region );

  for( uint i2 = 1; i2 < phi->req(); i2++ ) {

    Node *x = phi->in(i2);

    // If we commoned up the cloned 'x' with another existing Node,

    // the existing Node picks up a new use.  We need to make the

    // existing Node occur higher up so it dominates its uses.

    Node *old_ctrl;

    IdealLoopTree *old_loop;

    // The occasional new node

    if( x->_idx >= old_unique ) {   // Found a new, unplaced node?

      old_ctrl = x->is_Con() ? C->root() : NULL;

      old_loop = NULL;              // Not in any prior loop

    } else {

      old_ctrl = x->is_Con() ? C->root() : get_ctrl(x);

      old_loop = get_loop(old_ctrl); // Get prior loop

    }

    // New late point must dominate new use

    Node *new_ctrl = dom_lca( old_ctrl, region->in(i2) );

    // Set new location

    set_ctrl(x, new_ctrl);

    IdealLoopTree *new_loop = get_loop( new_ctrl );

    // If changing loop bodies, see if we need to collect into new body

    if( old_loop != new_loop ) {

      if( old_loop && !old_loop->_child )

        old_loop->_body.yank(x);

      if( !new_loop->_child )

        new_loop->_body.push(x);  // Collect body info

    }

  }

  return phi;

}

//------------------------------dominated_by------------------------------------

// Replace the dominated test with an obvious true or false.  Place it on the

// IGVN worklist for later cleanup.  Move control-dependent data Nodes on the

// live path up to the dominating control.

void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff ) {

#ifndef PRODUCT

  if( VerifyLoopOptimizations && PrintOpto ) tty->print_cr("dominating test");

#endif

  // prevdom is the dominating projection of the dominating test.

  assert( iff->is_If(), "" );

  assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");

  int pop = prevdom->Opcode();

  assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );

  // 'con' is set to true or false to kill the dominated test.

  Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);

  set_ctrl(con, C->root()); // Constant gets a new use

  // Hack the dominated test

  _igvn.hash_delete(iff);

  iff->set_req(1, con);

  _igvn._worklist.push(iff);

  // If I dont have a reachable TRUE and FALSE path following the IfNode then

  // I can assume this path reaches an infinite loop.  In this case it's not

  // important to optimize the data Nodes - either the whole compilation will

  // be tossed or this path (and all data Nodes) will go dead.

  if( iff->outcnt() != 2 ) return;

  // Make control-dependent data Nodes on the live path (path that will remain

  // once the dominated IF is removed) become control-dependent on the

  // dominating projection.

  Node* dp = ((IfNode*)iff)->proj_out(pop == Op_IfTrue);

  IdealLoopTree *old_loop = get_loop(dp);

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

    Node* cd = dp->fast_out(i); // Control-dependent node

    if( cd->depends_only_on_test() ) {

      assert( cd->in(0) == dp, "" );

      _igvn.hash_delete( cd );

      cd->set_req(0, prevdom);

      set_early_ctrl( cd );

      _igvn._worklist.push(cd);

      IdealLoopTree *new_loop = get_loop(get_ctrl(cd));

      if( old_loop != new_loop ) {

        if( !old_loop->_child ) old_loop->_body.yank(cd);

        if( !new_loop->_child ) new_loop->_body.push(cd);

      }

      --i;

      --imax;

    }

  }

}

//------------------------------has_local_phi_input----------------------------

// Return TRUE if 'n' has Phi inputs from its local block and no other

// block-local inputs (all non-local-phi inputs come from earlier blocks)

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

  Node *n_ctrl = get_ctrl(n);

  // See if some inputs come from a Phi in this block, or from before

  // this block.

  uint i;

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

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

    if( phi->is_Phi() && phi->in(0) == n_ctrl )

      break;

  }

  if( i >= n->req() )

    return NULL;                // No Phi inputs; nowhere to clone thru

  // Check for inputs created between 'n' and the Phi input.  These

  // must split as well; they have already been given the chance

  // (courtesy of a post-order visit) and since they did not we must

  // recover the 'cost' of splitting them by being very profitable

  // when splitting 'n'.  Since this is unlikely we simply give up.

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

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

    if( get_ctrl(m) == n_ctrl && !m->is_Phi() ) {

      // We allow the special case of AddP's with no local inputs.

      // This allows us to split-up address expressions.

      if (m->is_AddP() &&

          get_ctrl(m->in(2)) != n_ctrl &&

          get_ctrl(m->in(3)) != n_ctrl) {

        // Move the AddP up to dominating point

        set_ctrl_and_loop(m, find_non_split_ctrl(idom(n_ctrl)));

        continue;

      }

      return NULL;

    }

  }

  return n_ctrl;

}

//------------------------------remix_address_expressions----------------------

// Rework addressing expressions to get the most loop-invariant stuff

// moved out.  We'd like to do all associative operators, but it's especially

// important (common) to do address expressions.

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

  if (!has_ctrl(n))  return NULL;

  Node *n_ctrl = get_ctrl(n);

  IdealLoopTree *n_loop = get_loop(n_ctrl);

  // See if 'n' mixes loop-varying and loop-invariant inputs and

  // itself is loop-varying.

  // Only interested in binary ops (and AddP)

  if( n->req() < 3 || n->req() > 4 ) return NULL;

  Node *n1_ctrl = get_ctrl(n->in(                    1));

  Node *n2_ctrl = get_ctrl(n->in(                    2));

  Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3));

  IdealLoopTree *n1_loop = get_loop( n1_ctrl );

  IdealLoopTree *n2_loop = get_loop( n2_ctrl );

  IdealLoopTree *n3_loop = get_loop( n3_ctrl );

  // Does one of my inputs spin in a tighter loop than self?

  if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) ||

      (n_loop->is_member( n2_loop ) && n_loop != n2_loop) ||

      (n_loop->is_member( n3_loop ) && n_loop != n3_loop) )

    return NULL;                // Leave well enough alone

  // Is at least one of my inputs loop-invariant?

  if( n1_loop == n_loop &&

      n2_loop == n_loop &&

      n3_loop == n_loop )

    return NULL;                // No loop-invariant inputs

  int n_op = n->Opcode();

  // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2).

  if( n_op == Op_LShiftI ) {

    // Scale is loop invariant

    Node *scale = n->in(2);

    Node *scale_ctrl = get_ctrl(scale);

    IdealLoopTree *scale_loop = get_loop(scale_ctrl );

    if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )

      return NULL;

    const TypeInt *scale_t = scale->bottom_type()->isa_int();

    if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )

      return NULL;              // Dont bother with byte/short masking

    // Add must vary with loop (else shift would be loop-invariant)

    Node *add = n->in(1);

    Node *add_ctrl = get_ctrl(add);

    IdealLoopTree *add_loop = get_loop(add_ctrl);

    //assert( n_loop == add_loop, "" );

    if( n_loop != add_loop ) return NULL;  // happens w/ evil ZKM loops

    // Convert I-V into I+ (0-V); same for V-I

    if( add->Opcode() == Op_SubI &&

        _igvn.type( add->in(1) ) != TypeInt::ZERO ) {

      Node *zero = _igvn.intcon(0);

      set_ctrl(zero, C->root());

      Node *neg = new (C, 3) SubINode( _igvn.intcon(0), add->in(2) );

      register_new_node( neg, get_ctrl(add->in(2) ) );

      add = new (C, 3) AddINode( add->in(1), neg );

      register_new_node( add, add_ctrl );

    }

    if( add->Opcode() != Op_AddI ) return NULL;

    // See if one add input is loop invariant

    Node *add_var = add->in(1);

    Node *add_var_ctrl = get_ctrl(add_var);

    IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );

    Node *add_invar = add->in(2);

    Node *add_invar_ctrl = get_ctrl(add_invar);

    IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );

    if( add_var_loop == n_loop ) {

    } else if( add_invar_loop == n_loop ) {

      // Swap to find the invariant part

      add_invar = add_var;

      add_invar_ctrl = add_var_ctrl;

      add_invar_loop = add_var_loop;

      add_var = add->in(2);

      Node *add_var_ctrl = get_ctrl(add_var);

      IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );

    } else                      // Else neither input is loop invariant

      return NULL;

    if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )

      return NULL;              // No invariant part of the add?

    // Yes!  Reshape address expression!

    Node *inv_scale = new (C, 3) LShiftINode( add_invar, scale );

    register_new_node( inv_scale, add_invar_ctrl );

    Node *var_scale = new (C, 3) LShiftINode( add_var, scale );

    register_new_node( var_scale, n_ctrl );

    Node *var_add = new (C, 3) AddINode( var_scale, inv_scale );

    register_new_node( var_add, n_ctrl );

    _igvn.hash_delete( n );

    _igvn.subsume_node( n, var_add );

    return var_add;

  }

  // Replace (I+V) with (V+I)

  if( n_op == Op_AddI ||

      n_op == Op_AddL ||

      n_op == Op_AddF ||

      n_op == Op_AddD ||

      n_op == Op_MulI ||

      n_op == Op_MulL ||

      n_op == Op_MulF ||

      n_op == Op_MulD ) {

    if( n2_loop == n_loop ) {

      assert( n1_loop != n_loop, "" );

      n->swap_edges(1, 2);

    }

  }

  // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),

  // but not if I2 is a constant.

  if( n_op == Op_AddP ) {

    if( n2_loop == n_loop && n3_loop != n_loop ) {

      if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {

        Node *n22_ctrl = get_ctrl(n->in(2)->in(2));

        Node *n23_ctrl = get_ctrl(n->in(2)->in(3));

        IdealLoopTree *n22loop = get_loop( n22_ctrl );

        IdealLoopTree *n23_loop = get_loop( n23_ctrl );

        if( n22loop != n_loop && n22loop->is_member(n_loop) &&

            n23_loop == n_loop ) {

          Node *add1 = new (C, 4) AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );

          // Stuff new AddP in the loop preheader

          register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );

          Node *add2 = new (C, 4) AddPNode( n->in(1), add1, n->in(2)->in(3) );

          register_new_node( add2, n_ctrl );

          _igvn.hash_delete( n );

          _igvn.subsume_node( n, add2 );

          return add2;

        }

      }

    }

    // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)

    if( n2_loop != n_loop && n3_loop == n_loop ) {

      if( n->in(3)->Opcode() == Op_AddI ) {

        Node *V = n->in(3)->in(1);

        Node *I = n->in(3)->in(2);

        if( is_member(n_loop,get_ctrl(V)) ) {

        } else {

          Node *tmp = V; V = I; I = tmp;

        }

        if( !is_member(n_loop,get_ctrl(I)) ) {

          Node *add1 = new (C, 4) AddPNode( n->in(1), n->in(2), I );

          // Stuff new AddP in the loop preheader

          register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );

          Node *add2 = new (C, 4) AddPNode( n->in(1), add1, V );

          register_new_node( add2, n_ctrl );

          _igvn.hash_delete( n );

          _igvn.subsume_node( n, add2 );

          return add2;

        }

      }

    }

  }

  return NULL;

}

//------------------------------conditional_move-------------------------------

// Attempt to replace a Phi with a conditional move.  We have some pretty

// strict profitability requirements.  All Phis at the merge point must

// be converted, so we can remove the control flow.  We need to limit the

// number of c-moves to a small handful.  All code that was in the side-arms

// of the CFG diamond is now speculatively executed.  This code has to be

// "cheap enough".  We are pretty much limited to CFG diamonds that merge

// 1 or 2 items with a total of 1 or 2 ops executed speculatively.

Node *PhaseIdealLoop::conditional_move( Node *region ) {

  assert( region->is_Region(), "sanity check" );

  if( region->req() != 3 ) return NULL;

  // Check for CFG diamond

  Node *lp = region->in(1);

  Node *rp = region->in(2);

  if( !lp || !rp ) return NULL;

  Node *lp_c = lp->in(0);

  if( lp_c == NULL || lp_c != rp->in(0) || !lp_c->is_If() ) return NULL;

  IfNode *iff = lp_c->as_If();

  // Check for highly predictable branch.  No point in CMOV'ing if

  // we are going to predict accurately all the time.

  // %%% This hides patterns produced by utility methods like Math.min.

  if( iff->_prob < PROB_UNLIKELY_MAG(3) ||

      iff->_prob > PROB_LIKELY_MAG(3) )

    return NULL;

  // Check for ops pinned in an arm of the diamond.

  // Can't remove the control flow in this case

  if( lp->outcnt() > 1 ) return NULL;

  if( rp->outcnt() > 1 ) return NULL;

  // Check profitability

  int cost = 0;

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

    Node *out = region->fast_out(i);

    if( !out->is_Phi() ) continue; // Ignore other control edges, etc

    PhiNode* phi = out->as_Phi();

    switch (phi->type()->basic_type()) {

    case T_LONG:

      cost++;                   // Probably encodes as 2 CMOV's

    case T_INT:                 // These all CMOV fine

    case T_FLOAT:

    case T_DOUBLE:

    case T_ADDRESS:             // (RawPtr)

      cost++;

      break;

    case T_OBJECT: {            // Base oops are OK, but not derived oops

      const TypeOopPtr *tp = phi->type()->isa_oopptr();

      // Derived pointers are Bad (tm): what's the Base (for GC purposes) of a

      // CMOVE'd derived pointer?  It's a CMOVE'd derived base.  Thus

      // CMOVE'ing a derived pointer requires we also CMOVE the base.  If we

      // have a Phi for the base here that we convert to a CMOVE all is well

      // and good.  But if the base is dead, we'll not make a CMOVE.  Later

      // the allocator will have to produce a base by creating a CMOVE of the

      // relevant bases.  This puts the allocator in the business of

      // manufacturing expensive instructions, generally a bad plan.

      // Just Say No to Conditionally-Moved Derived Pointers.

      if( tp && tp->offset() != 0 )

        return NULL;

      cost++;

      break;

    }

    default:

      return NULL;              // In particular, can't do memory or I/O

    }

    // Add in cost any speculative ops

    for( uint j = 1; j < region->req(); j++ ) {

      Node *proj = region->in(j);

      Node *inp = phi->in(j);

      if (get_ctrl(inp) == proj) { // Found local op

        cost++;

        // Check for a chain of dependent ops; these will all become

        // speculative in a CMOV.

        for( uint k = 1; k < inp->req(); k++ )

          if (get_ctrl(inp->in(k)) == proj)

            return NULL;        // Too much speculative goo

      }

    }

    // See if the Phi is used by a Cmp.  This will likely Split-If, a

    // higher-payoff operation.

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

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

      if( use->is_Cmp() )

        return NULL;

    }

  }

  if( cost >= ConditionalMoveLimit ) return NULL; // Too much goo

  // --------------

  // Now replace all Phis with CMOV's

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

  uint flip = (lp->Opcode() == Op_IfTrue);

  while( 1 ) {

    PhiNode* phi = NULL;

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

      Node *out = region->fast_out(i);

      if (out->is_Phi()) {

        phi = out->as_Phi();

        break;

      }

    }

    if (phi == NULL)  break;

#ifndef PRODUCT

    if( PrintOpto && VerifyLoopOptimizations ) tty->print_cr("CMOV");

#endif

    // Move speculative ops

    for( uint j = 1; j < region->req(); j++ ) {

      Node *proj = region->in(j);

      Node *inp = phi->in(j);

      if (get_ctrl(inp) == proj) { // Found local op

#ifndef PRODUCT

        if( PrintOpto && VerifyLoopOptimizations ) {

          tty->print("  speculate: ");

          inp->dump();

        }

#endif

        set_ctrl(inp, cmov_ctrl);

      }

    }

    Node *cmov = CMoveNode::make( C, cmov_ctrl, iff->in(1), phi->in(1+flip), phi->in(2-flip), _igvn.type(phi) );

    register_new_node( cmov, cmov_ctrl );

    _igvn.hash_delete(phi);

    _igvn.subsume_node( phi, cmov );

#ifndef PRODUCT

    if( VerifyLoopOptimizations ) verify();