/*

 * Copyright 1997-2007 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.

 *

 */

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#include "incls/_precompiled.incl"

#include "incls/_cfgnode.cpp.incl"

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

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

// Compute the type of the RegionNode.

const Type *RegionNode::Value( PhaseTransform *phase ) const {

  for( uint i=1; i<req(); ++i ) {       // For all paths in

    Node *n = in(i);            // Get Control source

    if( !n ) continue;          // Missing inputs are TOP

    if( phase->type(n) == Type::CONTROL )

      return Type::CONTROL;

  }

  return Type::TOP;             // All paths dead?  Then so are we

}

//------------------------------Identity---------------------------------------

// Check for Region being Identity.

Node *RegionNode::Identity( PhaseTransform *phase ) {

  // Cannot have Region be an identity, even if it has only 1 input.

  // Phi users cannot have their Region input folded away for them,

  // since they need to select the proper data input

  return this;

}

//------------------------------merge_region-----------------------------------

// If a Region flows into a Region, merge into one big happy merge.  This is

// hard to do if there is stuff that has to happen

static Node *merge_region(RegionNode *region, PhaseGVN *phase) {

  if( region->Opcode() != Op_Region ) // Do not do to LoopNodes

    return NULL;

  Node *progress = NULL;        // Progress flag

  PhaseIterGVN *igvn = phase->is_IterGVN();

  uint rreq = region->req();

  for( uint i = 1; i < rreq; i++ ) {

    Node *r = region->in(i);

    if( r && r->Opcode() == Op_Region && // Found a region?

        r->in(0) == r &&        // Not already collapsed?

        r != region &&          // Avoid stupid situations

        r->outcnt() == 2 ) {    // Self user and 'region' user only?

      assert(!r->as_Region()->has_phi(), "no phi users");

      if( !progress ) {         // No progress

        if (region->has_phi()) {

          return NULL;        // Only flatten if no Phi users

          // igvn->hash_delete( phi );

        }

        igvn->hash_delete( region );

        progress = region;      // Making progress

      }

      igvn->hash_delete( r );

      // Append inputs to 'r' onto 'region'

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

        // Move an input from 'r' to 'region'

        region->add_req(r->in(j));

        r->set_req(j, phase->C->top());

        // Update phis of 'region'

        //for( uint k = 0; k < max; k++ ) {

        //  Node *phi = region->out(k);

        //  if( phi->is_Phi() ) {

        //    phi->add_req(phi->in(i));

        //  }

        //}

        rreq++;                 // One more input to Region

      } // Found a region to merge into Region

      // Clobber pointer to the now dead 'r'

      region->set_req(i, phase->C->top());

    }

  }

  return progress;

}

//--------------------------------has_phi--------------------------------------

// Helper function: Return any PhiNode that uses this region or NULL

PhiNode* RegionNode::has_phi() const {

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

    Node* phi = fast_out(i);

    if (phi->is_Phi()) {   // Check for Phi users

      assert(phi->in(0) == (Node*)this, "phi uses region only via in(0)");

      return phi->as_Phi();  // this one is good enough

    }

  }

  return NULL;

}

//-----------------------------has_unique_phi----------------------------------

// Helper function: Return the only PhiNode that uses this region or NULL

PhiNode* RegionNode::has_unique_phi() const {

  // Check that only one use is a Phi

  PhiNode* only_phi = NULL;

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

    Node* phi = fast_out(i);

    if (phi->is_Phi()) {   // Check for Phi users

      assert(phi->in(0) == (Node*)this, "phi uses region only via in(0)");

      if (only_phi == NULL) {

        only_phi = phi->as_Phi();

      } else {

        return NULL;  // multiple phis

      }

    }

  }

  return only_phi;

}

//------------------------------check_phi_clipping-----------------------------

// Helper function for RegionNode's identification of FP clipping

// Check inputs to the Phi

static bool check_phi_clipping( PhiNode *phi, ConNode * &min, uint &min_idx, ConNode * &max, uint &max_idx, Node * &val, uint &val_idx ) {

  min     = NULL;

  max     = NULL;

  val     = NULL;

  min_idx = 0;

  max_idx = 0;

  val_idx = 0;

  uint  phi_max = phi->req();

  if( phi_max == 4 ) {

    for( uint j = 1; j < phi_max; ++j ) {

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

      int opcode = n->Opcode();

      switch( opcode ) {

      case Op_ConI:

        {

          if( min == NULL ) {

            min     = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;

            min_idx = j;

          } else {

            max     = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;

            max_idx = j;

            if( min->get_int() > max->get_int() ) {

              // Swap min and max

              ConNode *temp;

              uint     temp_idx;

              temp     = min;     min     = max;     max     = temp;

              temp_idx = min_idx; min_idx = max_idx; max_idx = temp_idx;

            }

          }

        }

        break;

      default:

        {

          val = n;

          val_idx = j;

        }

        break;

      }

    }

  }

  return ( min && max && val && (min->get_int() <= 0) && (max->get_int() >=0) );

}

//------------------------------check_if_clipping------------------------------

// Helper function for RegionNode's identification of FP clipping

// Check that inputs to Region come from two IfNodes,

//

//            If

//      False    True

//       If        |

//  False  True    |

//    |      |     |

//  RegionNode_inputs

//

static bool check_if_clipping( const RegionNode *region, IfNode * &bot_if, IfNode * &top_if ) {

  top_if = NULL;

  bot_if = NULL;

  // Check control structure above RegionNode for (if  ( if  ) )

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

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

  Node *in3 = region->in(3);

  // Check that all inputs are projections

  if( in1->is_Proj() && in2->is_Proj() && in3->is_Proj() ) {

    Node *in10 = in1->in(0);

    Node *in20 = in2->in(0);

    Node *in30 = in3->in(0);

    // Check that #1 and #2 are ifTrue and ifFalse from same If

    if( in10 != NULL && in10->is_If() &&

        in20 != NULL && in20->is_If() &&

        in30 != NULL && in30->is_If() && in10 == in20 &&

        (in1->Opcode() != in2->Opcode()) ) {

      Node  *in100 = in10->in(0);

      Node *in1000 = (in100 != NULL && in100->is_Proj()) ? in100->in(0) : NULL;

      // Check that control for in10 comes from other branch of IF from in3

      if( in1000 != NULL && in1000->is_If() &&

          in30 == in1000 && (in3->Opcode() != in100->Opcode()) ) {

        // Control pattern checks

        top_if = (IfNode*)in1000;

        bot_if = (IfNode*)in10;

      }

    }

  }

  return (top_if != NULL);

}

//------------------------------check_convf2i_clipping-------------------------

// Helper function for RegionNode's identification of FP clipping

// Verify that the value input to the phi comes from "ConvF2I; LShift; RShift"

static bool check_convf2i_clipping( PhiNode *phi, uint idx, ConvF2INode * &convf2i, Node *min, Node *max) {

  convf2i = NULL;

  // Check for the RShiftNode

  Node *rshift = phi->in(idx);

  assert( rshift, "Previous checks ensure phi input is present");

  if( rshift->Opcode() != Op_RShiftI )  { return false; }

  // Check for the LShiftNode

  Node *lshift = rshift->in(1);

  assert( lshift, "Previous checks ensure phi input is present");

  if( lshift->Opcode() != Op_LShiftI )  { return false; }

  // Check for the ConvF2INode

  Node *conv = lshift->in(1);

  if( conv->Opcode() != Op_ConvF2I ) { return false; }

  // Check that shift amounts are only to get sign bits set after F2I

  jint max_cutoff     = max->get_int();

  jint min_cutoff     = min->get_int();

  jint left_shift     = lshift->in(2)->get_int();

  jint right_shift    = rshift->in(2)->get_int();

  jint max_post_shift = nth_bit(BitsPerJavaInteger - left_shift - 1);

  if( left_shift != right_shift ||

      0 > left_shift || left_shift >= BitsPerJavaInteger ||

      max_post_shift < max_cutoff ||

      max_post_shift < -min_cutoff ) {

    // Shifts are necessary but current transformation eliminates them

    return false;

  }

  // OK to return the result of ConvF2I without shifting

  convf2i = (ConvF2INode*)conv;

  return true;

}

//------------------------------check_compare_clipping-------------------------

// Helper function for RegionNode's identification of FP clipping

static bool check_compare_clipping( bool less_than, IfNode *iff, ConNode *limit, Node * & input ) {

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

  if ( !i1->is_Bool() ) { return false; }

  BoolNode *bool1 = i1->as_Bool();

  if(       less_than && bool1->_test._test != BoolTest::le ) { return false; }

  else if( !less_than && bool1->_test._test != BoolTest::lt ) { return false; }

  const Node *cmpF = bool1->in(1);

  if( cmpF->Opcode() != Op_CmpF )      { return false; }

  // Test that the float value being compared against

  // is equivalent to the int value used as a limit

  Node *nodef = cmpF->in(2);

  if( nodef->Opcode() != Op_ConF ) { return false; }

  jfloat conf = nodef->getf();

  jint   coni = limit->get_int();

  if( ((int)conf) != coni )        { return false; }

  input = cmpF->in(1);

  return true;

}

//------------------------------is_unreachable_region--------------------------

// Find if the Region node is reachable from the root.

bool RegionNode::is_unreachable_region(PhaseGVN *phase) const {

  assert(req() == 2, "");

  // First, cut the simple case of fallthrough region when NONE of

  // region's phis references itself directly or through a data node.

  uint max = outcnt();

  uint i;

  for (i = 0; i < max; i++) {

    Node* phi = raw_out(i);

    if (phi != NULL && phi->is_Phi()) {

      assert(phase->eqv(phi->in(0), this) && phi->req() == 2, "");

      if (phi->outcnt() == 0)

        continue; // Safe case - no loops

      if (phi->outcnt() == 1) {

        Node* u = phi->raw_out(0);

        // Skip if only one use is an other Phi or Call or Uncommon trap.

        // It is safe to consider this case as fallthrough.

        if (u != NULL && (u->is_Phi() || u->is_CFG()))

          continue;

      }

      // Check when phi references itself directly or through an other node.

      if (phi->as_Phi()->simple_data_loop_check(phi->in(1)) >= PhiNode::Unsafe)

        break; // Found possible unsafe data loop.

    }

  }

  if (i >= max)

    return false; // An unsafe case was NOT found - don't need graph walk.

  // Unsafe case - check if the Region node is reachable from root.

  ResourceMark rm;

  Arena *a = Thread::current()->resource_area();

  Node_List nstack(a);

  VectorSet visited(a);

  // Mark all control nodes reachable from root outputs

  Node *n = (Node*)phase->C->root();

  nstack.push(n);

  visited.set(n->_idx);

  while (nstack.size() != 0) {

    n = nstack.pop();

    uint max = n->outcnt();

    for (uint i = 0; i < max; i++) {

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

      if (m != NULL && m->is_CFG()) {

        if (phase->eqv(m, this)) {

          return false; // We reached the Region node - it is not dead.

        }

        if (!visited.test_set(m->_idx))

          nstack.push(m);

      }

    }

  }

  return true; // The Region node is unreachable - it is dead.

}

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

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

// the CFG, but we can still strip out dead paths.

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

  if( !can_reshape && !in(0) ) return NULL;     // Already degraded to a Copy

  assert(!in(0) || !in(0)->is_Root(), "not a specially hidden merge");

  // Check for RegionNode with no Phi users and both inputs come from either

  // arm of the same IF.  If found, then the control-flow split is useless.

  bool has_phis = false;

  if (can_reshape) {            // Need DU info to check for Phi users

    has_phis = (has_phi() != NULL);       // Cache result

    if (!has_phis) {            // No Phi users?  Nothing merging?

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

        Node *if1 = in(i);

        if( !if1 ) continue;

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

        if( !iff || !iff->is_If() ) continue;

        for( uint j=i+1; j<req(); j++ ) {

          if( in(j) && in(j)->in(0) == iff &&

              if1->Opcode() != in(j)->Opcode() ) {

            // Add the IF Projections to the worklist. They (and the IF itself)

            // will be eliminated if dead.

            phase->is_IterGVN()->add_users_to_worklist(iff);

            set_req(i, iff->in(0));// Skip around the useless IF diamond

            set_req(j, NULL);

            return this;      // Record progress

          }

        }

      }

    }

  }

  // Remove TOP or NULL input paths. If only 1 input path remains, this Region

  // degrades to a copy.

  bool add_to_worklist = false;

  int cnt = 0;                  // Count of values merging

  DEBUG_ONLY( int cnt_orig = req(); ) // Save original inputs count

  int del_it = 0;               // The last input path we delete

  // For all inputs...

  for( uint i=1; i<req(); ++i ){// For all paths in

    Node *n = in(i);            // Get the input

    if( n != NULL ) {

      // Remove useless control copy inputs

      if( n->is_Region() && n->as_Region()->is_copy() ) {

        set_req(i, n->nonnull_req());

        i--;

        continue;

      }

      if( n->is_Proj() ) {      // Remove useless rethrows

        Node *call = n->in(0);

        if (call->is_Call() && call->as_Call()->entry_point() == OptoRuntime::rethrow_stub()) {

          set_req(i, call->in(0));

          i--;

          continue;

        }

      }

      if( phase->type(n) == Type::TOP ) {

        set_req(i, NULL);       // Ignore TOP inputs

        i--;

        continue;

      }

      cnt++;                    // One more value merging

    } else if (can_reshape) {   // Else found dead path with DU info

      PhaseIterGVN *igvn = phase->is_IterGVN();

      del_req(i);               // Yank path from self

      del_it = i;

      uint max = outcnt();

      DUIterator j;

      bool progress = true;

      while(progress) {         // Need to establish property over all users

        progress = false;

        for (j = outs(); has_out(j); j++) {

          Node *n = out(j);

          if( n->req() != req() && n->is_Phi() ) {

            assert( n->in(0) == this, "" );

            igvn->hash_delete(n); // Yank from hash before hacking edges

            n->set_req_X(i,NULL,igvn);// Correct DU info

            n->del_req(i);        // Yank path from Phis

            if( max != outcnt() ) {

              progress = true;

              j = refresh_out_pos(j);

              max = outcnt();

            }

          }

        }

      }

      add_to_worklist = true;

      i--;

    }

  }

  if (can_reshape && cnt == 1) {

    // Is it dead loop?

    // If it is LoopNopde it had 2 (+1 itself) inputs and

    // one of them was cut. The loop is dead if it was EntryContol.

    assert(!this->is_Loop() || cnt_orig == 3, "Loop node should have 3 inputs");

    if (this->is_Loop() && del_it == LoopNode::EntryControl ||

       !this->is_Loop() && has_phis && is_unreachable_region(phase)) {

      // Yes,  the region will be removed during the next step below.

      // Cut the backedge input and remove phis since no data paths left.

      // We don't cut outputs to other nodes here since we need to put them

      // on the worklist.

      del_req(1);

      cnt = 0;

      assert( req() == 1, "no more inputs expected" );

      uint max = outcnt();

      bool progress = true;

      Node *top = phase->C->top();

      PhaseIterGVN *igvn = phase->is_IterGVN();

      DUIterator j;

      while(progress) {

        progress = false;

        for (j = outs(); has_out(j); j++) {

          Node *n = out(j);

          if( n->is_Phi() ) {

            assert( igvn->eqv(n->in(0), this), "" );

            assert( n->req() == 2 &&  n->in(1) != NULL, "Only one data input expected" );

            // Break dead loop data path.

            // Eagerly replace phis with top to avoid phis copies generation.

            igvn->add_users_to_worklist(n);

            igvn->hash_delete(n); // Yank from hash before hacking edges

            igvn->subsume_node(n, top);

            if( max != outcnt() ) {

              progress = true;

              j = refresh_out_pos(j);

              max = outcnt();

            }

          }

        }

      }

      add_to_worklist = true;

    }

  }

  if (add_to_worklist) {

    phase->is_IterGVN()->add_users_to_worklist(this); // Revisit collapsed Phis

  }

  if( cnt <= 1 ) {              // Only 1 path in?

    set_req(0, NULL);           // Null control input for region copy

    if( cnt == 0 && !can_reshape) { // Parse phase - leave the node as it is.

      // No inputs or all inputs are NULL.

      return NULL;

    } else if (can_reshape) {   // Optimization phase - remove the node

      PhaseIterGVN *igvn = phase->is_IterGVN();

      Node *parent_ctrl;

      if( cnt == 0 ) {

        assert( req() == 1, "no inputs expected" );

        // During IGVN phase such region will be subsumed by TOP node

        // so region's phis will have TOP as control node.

        // Kill phis here to avoid it. PhiNode::is_copy() will be always false.

        // Also set other user's input to top.

        parent_ctrl = phase->C->top();

      } else {

        // The fallthrough case since we already checked dead loops above.

        parent_ctrl = in(1);

        assert(parent_ctrl != NULL, "Region is a copy of some non-null control");

        assert(!igvn->eqv(parent_ctrl, this), "Close dead loop");

      }

      if (!add_to_worklist)

        igvn->add_users_to_worklist(this); // Check for further allowed opts

      for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) {

        Node* n = last_out(i);

        igvn->hash_delete(n); // Remove from worklist before modifying edges

        if( n->is_Phi() ) {   // Collapse all Phis

          // Eagerly replace phis to avoid copies generation.

          igvn->add_users_to_worklist(n);

          igvn->hash_delete(n); // Yank from hash before hacking edges

          if( cnt == 0 ) {

            assert( n->req() == 1, "No data inputs expected" );

            igvn->subsume_node(n, parent_ctrl); // replaced by top

          } else {

            assert( n->req() == 2 &&  n->in(1) != NULL, "Only one data input expected" );

            Node* in1 = n->in(1);               // replaced by unique input

            if( n->as_Phi()->is_unsafe_data_reference(in1) )