/*

 * Copyright (c) 1999, 2013, 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 "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/connode.hpp"

#include "opto/divnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/matcher.hpp"

#include "opto/mulnode.hpp"

#include "opto/rootnode.hpp"

#include "opto/subnode.hpp"

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

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

  if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {

    // ConvI2L may have type information on it which is unsafe to push up

    // so disable this for now

    return NULL;

  }

  if (n->is_MathExact()) {

    // MathExact has projections that are not correctly handled in the code

    // below.

    return NULL;

  }

  int wins = 0;

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

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

  const Type* type = n->bottom_type();

  const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();

  Node *phi;

  if (t_oop != NULL && t_oop->is_known_instance_field()) {

    int iid    = t_oop->instance_id();

    int index  = C->get_alias_index(t_oop);

    int offset = t_oop->offset();

    phi = new (C) PhiNode(region, type, NULL, iid, index, offset);

  } else {

    phi = PhiNode::make_blank(region, n);

  }

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

      // If x is a TypeNode, capture any more-precise type permanently into Node

      // otherwise it will be not updated during igvn->transform since

      // igvn->type(x) is set to x->Value() already.

      x->raise_bottom_type(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;

    if (x->is_Con()) {

      // Constant's control is always root.

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

      continue;

    }

    // The occasional new node

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

      old_ctrl = NULL;

      old_loop = NULL;               // Not in any prior loop

    } else {

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

    if (new_ctrl == old_ctrl) // Nothing is changed

      continue;

    IdealLoopTree *new_loop = get_loop(new_ctrl);

    // Don't move x into a loop if its uses are

    // outside of loop. Otherwise x will be cloned

    // for each use outside of this loop.

    IdealLoopTree *use_loop = get_loop(region);

    if (!new_loop->is_member(use_loop) &&

        (old_loop == NULL || !new_loop->is_member(old_loop))) {

      // Take early control, later control will be recalculated

      // during next iteration of loop optimizations.

      new_ctrl = get_early_ctrl(x);

      new_loop = get_loop(new_ctrl);

    }

    // Set new location

    set_ctrl(x, 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, bool flip, bool exclude_loop_predicate ) {

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

  if (flip) {

    if (pop == Op_IfTrue)

      pop = Op_IfFalse;

    else

      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.replace_input_of(iff, 1, con);

  // 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 = iff->as_If()->proj_out(pop == Op_IfTrue);

  // Loop predicates may have depending checks which should not

  // be skipped. For example, range check predicate has two checks

  // for lower and upper bounds.

  if (dp == NULL)

    return;

  ProjNode* dp_proj  = dp->as_Proj();

  ProjNode* unc_proj = iff->as_If()->proj_out(1 - dp_proj->_con)->as_Proj();

  if (exclude_loop_predicate &&

      unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate))

    return; // Let IGVN transformation change control dependence.

  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.replace_input_of(cd, 0, prevdom);

      set_early_ctrl(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) SubINode( _igvn.intcon(0), add->in(2) );

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

      add = new (C) 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) LShiftINode( add_invar, scale );

    Node *inv_scale_ctrl =

      dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?

      add_invar_ctrl : scale_ctrl;

    register_new_node( inv_scale, inv_scale_ctrl );

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

    register_new_node( var_scale, n_ctrl );

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

    register_new_node( var_add, n_ctrl );

    _igvn.replace_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) 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) AddPNode( n->in(1), add1, n->in(2)->in(3) );

          register_new_node( add2, n_ctrl );

          _igvn.replace_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) 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) AddPNode( n->in(1), add1, V );

          register_new_node( add2, n_ctrl );

          _igvn.replace_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 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;

  IdealLoopTree* r_loop = get_loop(region);

  assert(r_loop == get_loop(iff), "sanity");

  // Always convert to CMOVE if all results are used only outside this loop.

  bool used_inside_loop = (r_loop == _ltree_root);

  // Check profitability

  int cost = 0;

  int phis = 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

    phis++;

    PhiNode* phi = out->as_Phi();