/*

 * 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 "precompiled.hpp"

#include "compiler/compileLog.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/connode.hpp"

#include "opto/divnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "opto/subnode.hpp"

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

  phase->_igvn.replace_node(n1, addx);

  assert(phase->get_loop(phase->get_ctrl(n1)) == this, "");

  _body.yank(n1);

  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.

#ifndef PRODUCT

  if (TraceLoopOpts) {

    tty->print("Peel         ");

    loop->dump_head();

  }

#endif

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

  // 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.

        // 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.

      _igvn.hash_delete(use);

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

    }

  }

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

  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

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

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