/*

 * Copyright (c) 2000, 2018, 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/ciTypeFlow.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.hpp"

#include "opto/addnode.hpp"

#include "opto/castnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/connode.hpp"

#include "opto/loopnode.hpp"

#include "opto/phaseX.hpp"

#include "opto/runtime.hpp"

#include "opto/rootnode.hpp"

#include "opto/subnode.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#ifndef PRODUCT

extern int explicit_null_checks_elided;

#endif

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

//------------------------------Value------------------------------------------

// Return a tuple for whichever arm of the IF is reachable

const Type* IfNode::Value(PhaseGVN* phase) const {

  if( !in(0) ) return Type::TOP;

  if( phase->type(in(0)) == Type::TOP )

    return Type::TOP;

  const Type *t = phase->type(in(1));

  if( t == Type::TOP )          // data is undefined

    return TypeTuple::IFNEITHER; // unreachable altogether

  if( t == TypeInt::ZERO )      // zero, or false

    return TypeTuple::IFFALSE;  // only false branch is reachable

  if( t == TypeInt::ONE )       // 1, or true

    return TypeTuple::IFTRUE;   // only true branch is reachable

  assert( t == TypeInt::BOOL, "expected boolean type" );

  return TypeTuple::IFBOTH;     // No progress

}

const RegMask &IfNode::out_RegMask() const {

  return RegMask::Empty;

}

//------------------------------split_if---------------------------------------

// Look for places where we merge constants, then test on the merged value.

// If the IF test will be constant folded on the path with the constant, we

// win by splitting the IF to before the merge point.

static Node* split_if(IfNode *iff, PhaseIterGVN *igvn) {

  // I could be a lot more general here, but I'm trying to squeeze this

  // in before the Christmas '98 break so I'm gonna be kinda restrictive

  // on the patterns I accept.  CNC

  // Look for a compare of a constant and a merged value

  Node *i1 = iff->in(1);

  if( !i1->is_Bool() ) return NULL;

  BoolNode *b = i1->as_Bool();

  Node *cmp = b->in(1);

  if( !cmp->is_Cmp() ) return NULL;

  i1 = cmp->in(1);

  if( i1 == NULL || !i1->is_Phi() ) return NULL;

  PhiNode *phi = i1->as_Phi();

  if( phi->is_copy() ) return NULL;

  Node *con2 = cmp->in(2);

  if( !con2->is_Con() ) return NULL;

  // See that the merge point contains some constants

  Node *con1=NULL;

  uint i4;

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

    con1 = phi->in(i4);

    if( !con1 ) return NULL;    // Do not optimize partially collapsed merges

    if( con1->is_Con() ) break; // Found a constant

    // Also allow null-vs-not-null checks

    const TypePtr *tp = igvn->type(con1)->isa_ptr();

    if( tp && tp->_ptr == TypePtr::NotNull )

      break;

  }

  if( i4 >= phi->req() ) return NULL; // Found no constants

  igvn->C->set_has_split_ifs(true); // Has chance for split-if

  // Make sure that the compare can be constant folded away

  Node *cmp2 = cmp->clone();

  cmp2->set_req(1,con1);

  cmp2->set_req(2,con2);

  const Type *t = cmp2->Value(igvn);

  // This compare is dead, so whack it!

  igvn->remove_dead_node(cmp2);

  if( !t->singleton() ) return NULL;

  // No intervening control, like a simple Call

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

  if( !r->is_Region() ) return NULL;

  if (r->is_Loop()) return NULL;

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

  // No other users of the cmp/bool

  if (b->outcnt() != 1 || cmp->outcnt() != 1) {

    //tty->print_cr("many users of cmp/bool");

    return NULL;

  }

  // Make sure we can determine where all the uses of merged values go

  for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {

    Node* u = r->fast_out(j);

    if( u == r ) continue;

    if( u == iff ) continue;

    if( u->outcnt() == 0 ) continue; // use is dead & ignorable

    if( !u->is_Phi() ) {

      /*

      if( u->is_Start() ) {

        tty->print_cr("Region has inlined start use");

      } else {

        tty->print_cr("Region has odd use");

        u->dump(2);

      }*/

      return NULL;

    }

    if( u != phi ) {

      // CNC - do not allow any other merged value

      //tty->print_cr("Merging another value");

      //u->dump(2);

      return NULL;

    }

    // Make sure we can account for all Phi uses

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

      Node* v = u->fast_out(k); // User of the phi

      // CNC - Allow only really simple patterns.

      // In particular I disallow AddP of the Phi, a fairly common pattern

      if (v == cmp) continue;  // The compare is OK

      if (v->is_ConstraintCast()) {

        // If the cast is derived from data flow edges, it may not have a control edge.

        // If so, it should be safe to split. But follow-up code can not deal with

        // this (l. 359). So skip.

        if (v->in(0) == NULL) {

          return NULL;

        }

        if (v->in(0)->in(0) == iff) {

          continue;               // CastPP/II of the IfNode is OK

        }

      }

      // Disabled following code because I cannot tell if exactly one

      // path dominates without a real dominator check. CNC 9/9/1999

      //uint vop = v->Opcode();

      //if( vop == Op_Phi ) {     // Phi from another merge point might be OK

      //  Node *r = v->in(0);     // Get controlling point

      //  if( !r ) return NULL;   // Degraded to a copy

      //  // Find exactly one path in (either True or False doms, but not IFF)

      //  int cnt = 0;

      //  for( uint i = 1; i < r->req(); i++ )

      //    if( r->in(i) && r->in(i)->in(0) == iff )

      //      cnt++;

      //  if( cnt == 1 ) continue; // Exactly one of True or False guards Phi

      //}

      if( !v->is_Call() ) {

        /*

        if( v->Opcode() == Op_AddP ) {

          tty->print_cr("Phi has AddP use");

        } else if( v->Opcode() == Op_CastPP ) {

          tty->print_cr("Phi has CastPP use");

        } else if( v->Opcode() == Op_CastII ) {

          tty->print_cr("Phi has CastII use");

        } else {

          tty->print_cr("Phi has use I cant be bothered with");

        }

        */

      }

      return NULL;

      /* CNC - Cut out all the fancy acceptance tests

      // Can we clone this use when doing the transformation?

      // If all uses are from Phis at this merge or constants, then YES.

      if( !v->in(0) && v != cmp ) {

        tty->print_cr("Phi has free-floating use");

        v->dump(2);

        return NULL;

      }

      for( uint l = 1; l < v->req(); l++ ) {

        if( (!v->in(l)->is_Phi() || v->in(l)->in(0) != r) &&

            !v->in(l)->is_Con() ) {

          tty->print_cr("Phi has use");

          v->dump(2);

          return NULL;

        } // End of if Phi-use input is neither Phi nor Constant

      } // End of for all inputs to Phi-use

      */

    } // End of for all uses of Phi

  } // End of for all uses of Region

  // Only do this if the IF node is in a sane state

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

    return NULL;

  // Got a hit!  Do the Mondo Hack!

  //

  //ABC  a1c   def   ghi            B     1     e     h   A C   a c   d f   g i

  // R - Phi - Phi - Phi            Rc - Phi - Phi - Phi   Rx - Phi - Phi - Phi

  //     cmp - 2                         cmp - 2               cmp - 2

  //       bool                            bool_c                bool_x

  //       if                               if_c                  if_x

  //      T  F                              T  F                  T  F

  // ..s..    ..t ..                   ..s..    ..t..        ..s..    ..t..

  //

  // Split the paths coming into the merge point into 2 separate groups of

  // merges.  On the left will be all the paths feeding constants into the

  // Cmp's Phi.  On the right will be the remaining paths.  The Cmp's Phi

  // will fold up into a constant; this will let the Cmp fold up as well as

  // all the control flow.  Below the original IF we have 2 control

  // dependent regions, 's' and 't'.  Now we will merge the two paths

  // just prior to 's' and 't' from the two IFs.  At least 1 path (and quite

  // likely 2 or more) will promptly constant fold away.

  PhaseGVN *phase = igvn;

  // Make a region merging constants and a region merging the rest

  uint req_c = 0;

  for (uint ii = 1; ii < r->req(); ii++) {

    if (phi->in(ii) == con1) {

      req_c++;

    }

    Node* proj = PhaseIdealLoop::find_predicate(r->in(ii));

    if (proj != NULL) {

      return NULL;

    }

  }

  // If all the defs of the phi are the same constant, we already have the desired end state.

  // Skip the split that would create empty phi and region nodes.

  if((r->req() - req_c) == 1) {

    return NULL;

  }

  Node *region_c = new RegionNode(req_c + 1);

  Node *phi_c    = con1;

  uint  len      = r->req();

  Node *region_x = new RegionNode(len - req_c);

  Node *phi_x    = PhiNode::make_blank(region_x, phi);

  for (uint i = 1, i_c = 1, i_x = 1; i < len; i++) {

    if (phi->in(i) == con1) {

      region_c->init_req( i_c++, r  ->in(i) );

    } else {

      region_x->init_req( i_x,   r  ->in(i) );

      phi_x   ->init_req( i_x++, phi->in(i) );

    }

  }

  // Register the new RegionNodes but do not transform them.  Cannot

  // transform until the entire Region/Phi conglomerate has been hacked

  // as a single huge transform.

  igvn->register_new_node_with_optimizer( region_c );

  igvn->register_new_node_with_optimizer( region_x );

  // Prevent the untimely death of phi_x.  Currently he has no uses.  He is

  // about to get one.  If this only use goes away, then phi_x will look dead.

  // However, he will be picking up some more uses down below.

  Node *hook = new Node(4);

  hook->init_req(0, phi_x);

  hook->init_req(1, phi_c);

  phi_x = phase->transform( phi_x );

  // Make the compare

  Node *cmp_c = phase->makecon(t);

  Node *cmp_x = cmp->clone();

  cmp_x->set_req(1,phi_x);

  cmp_x->set_req(2,con2);

  cmp_x = phase->transform(cmp_x);

  // Make the bool

  Node *b_c = phase->transform(new BoolNode(cmp_c,b->_test._test));

  Node *b_x = phase->transform(new BoolNode(cmp_x,b->_test._test));

  // Make the IfNode

  IfNode* iff_c = iff->clone()->as_If();

  iff_c->set_req(0, region_c);

  iff_c->set_req(1, b_c);

  igvn->set_type_bottom(iff_c);

  igvn->_worklist.push(iff_c);

  hook->init_req(2, iff_c);

  IfNode* iff_x = iff->clone()->as_If();

  iff_x->set_req(0, region_x);

  iff_x->set_req(1, b_x);

  igvn->set_type_bottom(iff_x);

  igvn->_worklist.push(iff_x);

  hook->init_req(3, iff_x);

  // Make the true/false arms

  Node *iff_c_t = phase->transform(new IfTrueNode (iff_c));

  Node *iff_c_f = phase->transform(new IfFalseNode(iff_c));

  Node *iff_x_t = phase->transform(new IfTrueNode (iff_x));

  Node *iff_x_f = phase->transform(new IfFalseNode(iff_x));

  // Merge the TRUE paths

  Node *region_s = new RegionNode(3);

  igvn->_worklist.push(region_s);

  region_s->init_req(1, iff_c_t);

  region_s->init_req(2, iff_x_t);

  igvn->register_new_node_with_optimizer( region_s );

  // Merge the FALSE paths

  Node *region_f = new RegionNode(3);

  igvn->_worklist.push(region_f);

  region_f->init_req(1, iff_c_f);

  region_f->init_req(2, iff_x_f);

  igvn->register_new_node_with_optimizer( region_f );

  igvn->hash_delete(cmp);// Remove soon-to-be-dead node from hash table.

  cmp->set_req(1,NULL);  // Whack the inputs to cmp because it will be dead

  cmp->set_req(2,NULL);

  // Check for all uses of the Phi and give them a new home.

  // The 'cmp' got cloned, but CastPP/IIs need to be moved.

  Node *phi_s = NULL;     // do not construct unless needed

  Node *phi_f = NULL;     // do not construct unless needed

  for (DUIterator_Last i2min, i2 = phi->last_outs(i2min); i2 >= i2min; --i2) {

    Node* v = phi->last_out(i2);// User of the phi

    igvn->rehash_node_delayed(v); // Have to fixup other Phi users

    uint vop = v->Opcode();

    Node *proj = NULL;

    if( vop == Op_Phi ) {       // Remote merge point

      Node *r = v->in(0);

      for (uint i3 = 1; i3 < r->req(); i3++)

        if (r->in(i3) && r->in(i3)->in(0) == iff) {

          proj = r->in(i3);

          break;

        }

    } else if( v->is_ConstraintCast() ) {

      proj = v->in(0);          // Controlling projection

    } else {

      assert( 0, "do not know how to handle this guy" );

    }

    guarantee(proj != NULL, "sanity");

    Node *proj_path_data, *proj_path_ctrl;

    if( proj->Opcode() == Op_IfTrue ) {

      if( phi_s == NULL ) {

        // Only construct phi_s if needed, otherwise provides

        // interfering use.

        phi_s = PhiNode::make_blank(region_s,phi);

        phi_s->init_req( 1, phi_c );

        phi_s->init_req( 2, phi_x );

        hook->add_req(phi_s);

        phi_s = phase->transform(phi_s);

      }

      proj_path_data = phi_s;

      proj_path_ctrl = region_s;

    } else {

      if( phi_f == NULL ) {

        // Only construct phi_f if needed, otherwise provides

        // interfering use.

        phi_f = PhiNode::make_blank(region_f,phi);

        phi_f->init_req( 1, phi_c );

        phi_f->init_req( 2, phi_x );

        hook->add_req(phi_f);

        phi_f = phase->transform(phi_f);

      }

      proj_path_data = phi_f;

      proj_path_ctrl = region_f;

    }

    // Fixup 'v' for for the split

    if( vop == Op_Phi ) {       // Remote merge point

      uint i;

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

        if( v->in(i) == phi )

          break;

      v->set_req(i, proj_path_data );

    } else if( v->is_ConstraintCast() ) {

      v->set_req(0, proj_path_ctrl );

      v->set_req(1, proj_path_data );

    } else

      ShouldNotReachHere();

  }

  // Now replace the original iff's True/False with region_s/region_t.

  // This makes the original iff go dead.

  for (DUIterator_Last i3min, i3 = iff->last_outs(i3min); i3 >= i3min; --i3) {

    Node* p = iff->last_out(i3);

    assert( p->Opcode() == Op_IfTrue || p->Opcode() == Op_IfFalse, "" );

    Node *u = (p->Opcode() == Op_IfTrue) ? region_s : region_f;

    // Replace p with u

    igvn->add_users_to_worklist(p);

    for (DUIterator_Last lmin, l = p->last_outs(lmin); l >= lmin;) {

      Node* x = p->last_out(l);

      igvn->hash_delete(x);

      uint uses_found = 0;

      for( uint j = 0; j < x->req(); j++ ) {

        if( x->in(j) == p ) {

          x->set_req(j, u);

          uses_found++;

        }

      }

      l -= uses_found;    // we deleted 1 or more copies of this edge

    }

    igvn->remove_dead_node(p);

  }

  // Force the original merge dead

  igvn->hash_delete(r);

  // First, remove region's dead users.

  for (DUIterator_Last lmin, l = r->last_outs(lmin); l >= lmin;) {

    Node* u = r->last_out(l);

    if( u == r ) {

      r->set_req(0, NULL);

    } else {

      assert(u->outcnt() == 0, "only dead users");

      igvn->remove_dead_node(u);

    }

    l -= 1;

  }

  igvn->remove_dead_node(r);

  // Now remove the bogus extra edges used to keep things alive

  igvn->remove_dead_node( hook );

  // Must return either the original node (now dead) or a new node

  // (Do not return a top here, since that would break the uniqueness of top.)

  return new ConINode(TypeInt::ZERO);

}

// if this IfNode follows a range check pattern return the projection

// for the failed path

ProjNode* IfNode::range_check_trap_proj(int& flip_test, Node*& l, Node*& r) {

  if (outcnt() != 2) {

    return NULL;

  }

  Node* b = in(1);

  if (b == NULL || !b->is_Bool())  return NULL;

  BoolNode* bn = b->as_Bool();

  Node* cmp = bn->in(1);

  if (cmp == NULL)  return NULL;

  if (cmp->Opcode() != Op_CmpU)  return NULL;

  l = cmp->in(1);

  r = cmp->in(2);

  flip_test = 1;

  if (bn->_test._test == BoolTest::le) {

    l = cmp->in(2);

    r = cmp->in(1);

    flip_test = 2;

  } else if (bn->_test._test != BoolTest::lt) {

    return NULL;

  }

  if (l->is_top())  return NULL;   // Top input means dead test

  if (r->Opcode() != Op_LoadRange && !is_RangeCheck())  return NULL;

  // We have recognized one of these forms:

  //  Flip 1:  If (Bool[<] CmpU(l, LoadRange)) ...

  //  Flip 2:  If (Bool[<=] CmpU(LoadRange, l)) ...

  ProjNode* iftrap = proj_out_or_null(flip_test == 2 ? true : false);

  return iftrap;

}

//------------------------------is_range_check---------------------------------

// Return 0 if not a range check.  Return 1 if a range check and set index and

// offset.  Return 2 if we had to negate the test.  Index is NULL if the check

// is versus a constant.

int RangeCheckNode::is_range_check(Node* &range, Node* &index, jint &offset) {

  int flip_test = 0;

  Node* l = NULL;

  Node* r = NULL;

  ProjNode* iftrap = range_check_trap_proj(flip_test, l, r);

  if (iftrap == NULL) {

    return 0;

  }

  // Make sure it's a real range check by requiring an uncommon trap

  // along the OOB path.  Otherwise, it's possible that the user wrote

  // something which optimized to look like a range check but behaves

  // in some other way.

  if (iftrap->is_uncommon_trap_proj(Deoptimization::Reason_range_check) == NULL) {

    return 0;

  }

  // Look for index+offset form

  Node* ind = l;

  jint  off = 0;

  if (l->is_top()) {

    return 0;

  } else if (l->Opcode() == Op_AddI) {

    if ((off = l->in(1)->find_int_con(0)) != 0) {

      ind = l->in(2)->uncast();

    } else if ((off = l->in(2)->find_int_con(0)) != 0) {

      ind = l->in(1)->uncast();

    }

  } else if ((off = l->find_int_con(-1)) >= 0) {

    // constant offset with no variable index

    ind = NULL;

  } else {

    // variable index with no constant offset (or dead negative index)

    off = 0;