/*

 * Copyright (c) 2000, 2010, 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 "incls/_precompiled.incl"

#include "incls/_loopTransform.cpp.incl"

//------------------------------is_loop_exit-----------------------------------

// Given an IfNode, return the loop-exiting projection or NULL if both

// arms remain in the loop.

Node *IdealLoopTree::is_loop_exit(Node *iff) const {

  if( iff->outcnt() != 2 ) return NULL; // Ignore partially dead tests

  PhaseIdealLoop *phase = _phase;

  // Test is an IfNode, has 2 projections.  If BOTH are in the loop

  // we need loop unswitching instead of peeling.

  if( !is_member(phase->get_loop( iff->raw_out(0) )) )

    return iff->raw_out(0);

  if( !is_member(phase->get_loop( iff->raw_out(1) )) )

    return iff->raw_out(1);

  return NULL;

}

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

//------------------------------record_for_igvn----------------------------

// Put loop body on igvn work list

void IdealLoopTree::record_for_igvn() {

  for( uint i = 0; i < _body.size(); i++ ) {

    Node *n = _body.at(i);

    _phase->_igvn._worklist.push(n);

  }

}

//------------------------------compute_profile_trip_cnt----------------------------

// Compute loop trip count from profile data as

//    (backedge_count + loop_exit_count) / loop_exit_count

void IdealLoopTree::compute_profile_trip_cnt( PhaseIdealLoop *phase ) {

  if (!_head->is_CountedLoop()) {

    return;

  }

  CountedLoopNode* head = _head->as_CountedLoop();

  if (head->profile_trip_cnt() != COUNT_UNKNOWN) {

    return; // Already computed

  }

  float trip_cnt = (float)max_jint; // default is big

  Node* back = head->in(LoopNode::LoopBackControl);

  while (back != head) {

    if ((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&

        back->in(0) &&

        back->in(0)->is_If() &&

        back->in(0)->as_If()->_fcnt != COUNT_UNKNOWN &&

        back->in(0)->as_If()->_prob != PROB_UNKNOWN) {

      break;

    }

    back = phase->idom(back);

  }

  if (back != head) {

    assert((back->Opcode() == Op_IfTrue || back->Opcode() == Op_IfFalse) &&

           back->in(0), "if-projection exists");

    IfNode* back_if = back->in(0)->as_If();

    float loop_back_cnt = back_if->_fcnt * back_if->_prob;

    // Now compute a loop exit count

    float loop_exit_cnt = 0.0f;

    for( uint i = 0; i < _body.size(); i++ ) {

      Node *n = _body[i];

      if( n->is_If() ) {

        IfNode *iff = n->as_If();

        if( iff->_fcnt != COUNT_UNKNOWN && iff->_prob != PROB_UNKNOWN ) {

          Node *exit = is_loop_exit(iff);

          if( exit ) {

            float exit_prob = iff->_prob;

            if (exit->Opcode() == Op_IfFalse) exit_prob = 1.0 - exit_prob;

            if (exit_prob > PROB_MIN) {

              float exit_cnt = iff->_fcnt * exit_prob;

              loop_exit_cnt += exit_cnt;

            }

          }

        }

      }

    }

    if (loop_exit_cnt > 0.0f) {

      trip_cnt = (loop_back_cnt + loop_exit_cnt) / loop_exit_cnt;

    } else {

      // No exit count so use

      trip_cnt = loop_back_cnt;

    }

  }

#ifndef PRODUCT

  if (TraceProfileTripCount) {

    tty->print_cr("compute_profile_trip_cnt  lp: %d cnt: %f\n", head->_idx, trip_cnt);

  }

#endif

  head->set_profile_trip_cnt(trip_cnt);

}

//---------------------is_invariant_addition-----------------------------

// Return nonzero index of invariant operand for an Add or Sub

// of (nonconstant) invariant and variant values. Helper for reassociate_invariants.

int IdealLoopTree::is_invariant_addition(Node* n, PhaseIdealLoop *phase) {

  int op = n->Opcode();

  if (op == Op_AddI || op == Op_SubI) {

    bool in1_invar = this->is_invariant(n->in(1));

    bool in2_invar = this->is_invariant(n->in(2));

    if (in1_invar && !in2_invar) return 1;

    if (!in1_invar && in2_invar) return 2;

  }

  return 0;

}

//---------------------reassociate_add_sub-----------------------------

// Reassociate invariant add and subtract expressions:

//

// inv1 + (x + inv2)  =>  ( inv1 + inv2) + x

// (x + inv2) + inv1  =>  ( inv1 + inv2) + x

// inv1 + (x - inv2)  =>  ( inv1 - inv2) + x

// inv1 - (inv2 - x)  =>  ( inv1 - inv2) + x

// (x + inv2) - inv1  =>  (-inv1 + inv2) + x

// (x - inv2) + inv1  =>  ( inv1 - inv2) + x

// (x - inv2) - inv1  =>  (-inv1 - inv2) + x

// inv1 + (inv2 - x)  =>  ( inv1 + inv2) - x

// inv1 - (x - inv2)  =>  ( inv1 + inv2) - x

// (inv2 - x) + inv1  =>  ( inv1 + inv2) - x

// (inv2 - x) - inv1  =>  (-inv1 + inv2) - x

// inv1 - (x + inv2)  =>  ( inv1 - inv2) - x

//

Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {

  if (!n1->is_Add() && !n1->is_Sub() || n1->outcnt() == 0) return NULL;

  if (is_invariant(n1)) return NULL;

  int inv1_idx = is_invariant_addition(n1, phase);

  if (!inv1_idx) return NULL;

  // Don't mess with add of constant (igvn moves them to expression tree root.)

  if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;

  Node* inv1 = n1->in(inv1_idx);

  Node* n2 = n1->in(3 - inv1_idx);

  int inv2_idx = is_invariant_addition(n2, phase);

  if (!inv2_idx) return NULL;

  Node* x    = n2->in(3 - inv2_idx);

  Node* inv2 = n2->in(inv2_idx);

  bool neg_x    = n2->is_Sub() && inv2_idx == 1;

  bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;

  bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;

  if (n1->is_Sub() && inv1_idx == 1) {

    neg_x    = !neg_x;

    neg_inv2 = !neg_inv2;

  }

  Node* inv1_c = phase->get_ctrl(inv1);

  Node* inv2_c = phase->get_ctrl(inv2);

  Node* n_inv1;

  if (neg_inv1) {

    Node *zero = phase->_igvn.intcon(0);

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

    n_inv1 = new (phase->C, 3) SubINode(zero, inv1);

    phase->register_new_node(n_inv1, inv1_c);

  } else {

    n_inv1 = inv1;

  }

  Node* inv;

  if (neg_inv2) {

    inv = new (phase->C, 3) SubINode(n_inv1, inv2);

  } else {

    inv = new (phase->C, 3) AddINode(n_inv1, inv2);

  }

  phase->register_new_node(inv, phase->get_early_ctrl(inv));

  Node* addx;

  if (neg_x) {

    addx = new (phase->C, 3) SubINode(inv, x);

  } else {

    addx = new (phase->C, 3) AddINode(x, inv);

  }

  phase->register_new_node(addx, phase->get_ctrl(x));

  return addx;

}

//---------------------reassociate_invariants-----------------------------

// Reassociate invariant expressions:

void IdealLoopTree::reassociate_invariants(PhaseIdealLoop *phase) {

  for (int i = _body.size() - 1; i >= 0; i--) {

    Node *n = _body.at(i);

    for (int j = 0; j < 5; j++) {

      Node* nn = reassociate_add_sub(n, phase);

      if (nn == NULL) break;

      n = nn; // again

    };

  }

}

//------------------------------policy_peeling---------------------------------

// Return TRUE or FALSE if the loop should be peeled or not.  Peel if we can

// make some loop-invariant test (usually a null-check) happen before the loop.

bool IdealLoopTree::policy_peeling( PhaseIdealLoop *phase ) const {

  Node *test = ((IdealLoopTree*)this)->tail();

  int  body_size = ((IdealLoopTree*)this)->_body.size();

  int  uniq      = phase->C->unique();

  // Peeling does loop cloning which can result in O(N^2) node construction

  if( body_size > 255 /* Prevent overflow for large body_size */

      || (body_size * body_size + uniq > MaxNodeLimit) ) {

    return false;           // too large to safely clone

  }

  while( test != _head ) {      // Scan till run off top of loop

    if( test->is_If() ) {       // Test?

      Node *ctrl = phase->get_ctrl(test->in(1));

      if (ctrl->is_top())

        return false;           // Found dead test on live IF?  No peeling!

      // Standard IF only has one input value to check for loop invariance

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

      // Condition is not a member of this loop?

      if( !is_member(phase->get_loop(ctrl)) &&

          is_loop_exit(test) )

        return true;            // Found reason to peel!

    }

    // Walk up dominators to loop _head looking for test which is

    // executed on every path thru loop.

    test = phase->idom(test);

  }

  return false;

}

//------------------------------peeled_dom_test_elim---------------------------

// If we got the effect of peeling, either by actually peeling or by making

// a pre-loop which must execute at least once, we can remove all

// loop-invariant dominated tests in the main body.

void PhaseIdealLoop::peeled_dom_test_elim( IdealLoopTree *loop, Node_List &old_new ) {

  bool progress = true;

  while( progress ) {

    progress = false;           // Reset for next iteration

    Node *prev = loop->_head->in(LoopNode::LoopBackControl);//loop->tail();

    Node *test = prev->in(0);

    while( test != loop->_head ) { // Scan till run off top of loop

      int p_op = prev->Opcode();

      if( (p_op == Op_IfFalse || p_op == Op_IfTrue) &&

          test->is_If() &&      // Test?

          !test->in(1)->is_Con() && // And not already obvious?

          // Condition is not a member of this loop?

          !loop->is_member(get_loop(get_ctrl(test->in(1))))){

        // Walk loop body looking for instances of this test

        for( uint i = 0; i < loop->_body.size(); i++ ) {

          Node *n = loop->_body.at(i);

          if( n->is_If() && n->in(1) == test->in(1) /*&& n != loop->tail()->in(0)*/ ) {

            // IfNode was dominated by version in peeled loop body

            progress = true;

            dominated_by( old_new[prev->_idx], n );

          }

        }

      }

      prev = test;

      test = idom(test);

    } // End of scan tests in loop

  } // End of while( progress )

}

//------------------------------do_peeling-------------------------------------

// Peel the first iteration of the given loop.

// Step 1: Clone the loop body.  The clone becomes the peeled iteration.

//         The pre-loop illegally has 2 control users (old & new loops).

// Step 2: Make the old-loop fall-in edges point to the peeled iteration.

//         Do this by making the old-loop fall-in edges act as if they came

//         around the loopback from the prior iteration (follow the old-loop

//         backedges) and then map to the new peeled iteration.  This leaves

//         the pre-loop with only 1 user (the new peeled iteration), but the

//         peeled-loop backedge has 2 users.

// Step 3: Cut the backedge on the clone (so its not a loop) and remove the

//         extra backedge user.

void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {

  C->set_major_progress();

  // Peeling a 'main' loop in a pre/main/post situation obfuscates the

  // 'pre' loop from the main and the 'pre' can no longer have it's

  // iterations adjusted.  Therefore, we need to declare this loop as

  // no longer a 'main' loop; it will need new pre and post loops before

  // we can do further RCE.

  Node *h = loop->_head;

  if( h->is_CountedLoop() ) {

    CountedLoopNode *cl = h->as_CountedLoop();

    assert(cl->trip_count() > 0, "peeling a fully unrolled loop");

    cl->set_trip_count(cl->trip_count() - 1);

    if( cl->is_main_loop() ) {

      cl->set_normal_loop();

#ifndef PRODUCT

      if( PrintOpto && VerifyLoopOptimizations ) {

        tty->print("Peeling a 'main' loop; resetting to 'normal' ");

        loop->dump_head();

      }

#endif

    }

  }

  // Step 1: Clone the loop body.  The clone becomes the peeled iteration.

  //         The pre-loop illegally has 2 control users (old & new loops).

  clone_loop( loop, old_new, dom_depth(loop->_head) );

  // Step 2: Make the old-loop fall-in edges point to the peeled iteration.

  //         Do this by making the old-loop fall-in edges act as if they came

  //         around the loopback from the prior iteration (follow the old-loop

  //         backedges) and then map to the new peeled iteration.  This leaves

  //         the pre-loop with only 1 user (the new peeled iteration), but the

  //         peeled-loop backedge has 2 users.

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

    Node* old = loop->_head->fast_out(j);

    if( old->in(0) == loop->_head && old->req() == 3 &&

        (old->is_Loop() || old->is_Phi()) ) {

      Node *new_exit_value = old_new[old->in(LoopNode::LoopBackControl)->_idx];

      if( !new_exit_value )     // Backedge value is ALSO loop invariant?

        // Then loop body backedge value remains the same.

        new_exit_value = old->in(LoopNode::LoopBackControl);

      _igvn.hash_delete(old);

      old->set_req(LoopNode::EntryControl, new_exit_value);

    }

  }

  // Step 3: Cut the backedge on the clone (so its not a loop) and remove the

  //         extra backedge user.

  Node *nnn = old_new[loop->_head->_idx];

  _igvn.hash_delete(nnn);

  nnn->set_req(LoopNode::LoopBackControl, C->top());

  for (DUIterator_Fast j2max, j2 = nnn->fast_outs(j2max); j2 < j2max; j2++) {

    Node* use = nnn->fast_out(j2);

    if( use->in(0) == nnn && use->req() == 3 && use->is_Phi() ) {

      _igvn.hash_delete(use);

      use->set_req(LoopNode::LoopBackControl, C->top());

    }

  }

  // Step 4: Correct dom-depth info.  Set to loop-head depth.

  int dd = dom_depth(loop->_head);

  set_idom(loop->_head, loop->_head->in(1), dd);

  for (uint j3 = 0; j3 < loop->_body.size(); j3++) {

    Node *old = loop->_body.at(j3);

    Node *nnn = old_new[old->_idx];

    if (!has_ctrl(nnn))

      set_idom(nnn, idom(nnn), dd-1);

    // While we're at it, remove any SafePoints from the peeled code

    if( old->Opcode() == Op_SafePoint ) {

      Node *nnn = old_new[old->_idx];

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

    }

  }

  // Now force out all loop-invariant dominating tests.  The optimizer

  // finds some, but we _know_ they are all useless.

  peeled_dom_test_elim(loop,old_new);

  loop->record_for_igvn();

}

//------------------------------policy_maximally_unroll------------------------

// Return exact loop trip count, or 0 if not maximally unrolling

bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const {

  CountedLoopNode *cl = _head->as_CountedLoop();

  assert( cl->is_normal_loop(), "" );

  Node *init_n = cl->init_trip();

  Node *limit_n = cl->limit();

  // Non-constant bounds

  if( init_n   == NULL || !init_n->is_Con()  ||

      limit_n  == NULL || !limit_n->is_Con() ||

      // protect against stride not being a constant

      !cl->stride_is_con() ) {

    return false;

  }

  int init   = init_n->get_int();

  int limit  = limit_n->get_int();

  int span   = limit - init;

  int stride = cl->stride_con();

  if (init >= limit || stride > span) {

    // return a false (no maximally unroll) and the regular unroll/peel

    // route will make a small mess which CCP will fold away.

    return false;

  }

  uint trip_count = span/stride;   // trip_count can be greater than 2 Gig.

  assert( (int)trip_count*stride == span, "must divide evenly" );

  // Real policy: if we maximally unroll, does it get too big?

  // Allow the unrolled mess to get larger than standard loop

  // size.  After all, it will no longer be a loop.

  uint body_size    = _body.size();

  uint unroll_limit = (uint)LoopUnrollLimit * 4;

  assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");

  cl->set_trip_count(trip_count);

  if( trip_count <= unroll_limit && body_size <= unroll_limit ) {

    uint new_body_size = body_size * trip_count;

    if (new_body_size <= unroll_limit &&

        body_size == new_body_size / trip_count &&

        // Unrolling can result in a large amount of node construction

        new_body_size < MaxNodeLimit - phase->C->unique()) {

      return true;    // maximally unroll

    }

  }

  return false;               // Do not maximally unroll

}

//------------------------------policy_unroll----------------------------------

// Return TRUE or FALSE if the loop should be unrolled or not.  Unroll if

// the loop is a CountedLoop and the body is small enough.

bool IdealLoopTree::policy_unroll( PhaseIdealLoop *phase ) const {

  CountedLoopNode *cl = _head->as_CountedLoop();

  assert( cl->is_normal_loop() || cl->is_main_loop(), "" );

  // protect against stride not being a constant

  if( !cl->stride_is_con() ) return false;

  // protect against over-unrolling

  if( cl->trip_count() <= 1 ) return false;

  int future_unroll_ct = cl->unrolled_count() * 2;

  // Don't unroll if the next round of unrolling would push us

  // over the expected trip count of the loop.  One is subtracted

  // from the expected trip count because the pre-loop normally

  // executes 1 iteration.

  if (UnrollLimitForProfileCheck > 0 &&

      cl->profile_trip_cnt() != COUNT_UNKNOWN &&

      future_unroll_ct        > UnrollLimitForProfileCheck &&

      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {

    return false;

  }

  // When unroll count is greater than LoopUnrollMin, don't unroll if:

  //   the residual iterations are more than 10% of the trip count

  //   and rounds of "unroll,optimize" are not making significant progress

  //   Progress defined as current size less than 20% larger than previous size.

  if (UseSuperWord && cl->node_count_before_unroll() > 0 &&

      future_unroll_ct > LoopUnrollMin &&

      (future_unroll_ct - 1) * 10.0 > cl->profile_trip_cnt() &&

      1.2 * cl->node_count_before_unroll() < (double)_body.size()) {

    return false;

  }

  Node *init_n = cl->init_trip();

  Node *limit_n = cl->limit();

  // Non-constant bounds.

  // Protect against over-unrolling when init or/and limit are not constant

  // (so that trip_count's init value is maxint) but iv range is known.

  if( init_n   == NULL || !init_n->is_Con()  ||

      limit_n  == NULL || !limit_n->is_Con() ) {

    Node* phi = cl->phi();

    if( phi != NULL ) {

      assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");

      const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();

      int next_stride = cl->stride_con() * 2; // stride after this unroll

      if( next_stride > 0 ) {

        if( iv_type->_lo + next_stride <= iv_type->_lo || // overflow

            iv_type->_lo + next_stride >  iv_type->_hi ) {

          return false;  // over-unrolling

        }

      } else if( next_stride < 0 ) {

        if( iv_type->_hi + next_stride >= iv_type->_hi || // overflow

            iv_type->_hi + next_stride <  iv_type->_lo ) {

          return false;  // over-unrolling

        }

      }

    }

  }

  // Adjust body_size to determine if we unroll or not

  uint body_size = _body.size();

  // Key test to unroll CaffeineMark's Logic test

  int xors_in_loop = 0;

  // Also count ModL, DivL and MulL which expand mightly

  for( uint k = 0; k < _body.size(); k++ ) {

    switch( _body.at(k)->Opcode() ) {

    case Op_XorI: xors_in_loop++; break; // CaffeineMark's Logic test

    case Op_ModL: body_size += 30; break;

    case Op_DivL: body_size += 30; break;

    case Op_MulL: body_size += 10; break;

    }

  }

  // Check for being too big

  if( body_size > (uint)LoopUnrollLimit ) {

    if( xors_in_loop >= 4 && body_size < (uint)LoopUnrollLimit*4) return true;

    // Normal case: loop too big

    return false;

  }

  // Check for stride being a small enough constant

  if( abs(cl->stride_con()) > (1<<3) ) return false;

  // Unroll once!  (Each trip will soon do double iterations)

  return true;

}

//------------------------------policy_align-----------------------------------

// Return TRUE or FALSE if the loop should be cache-line aligned.  Gather the

// expression that does the alignment.  Note that only one array base can be

// aligned in a loop (unless the VM guarantees mutual alignment).  Note that

// if we vectorize short memory ops into longer memory ops, we may want to

// increase alignment.

bool IdealLoopTree::policy_align( PhaseIdealLoop *phase ) const {

  return false;

}