/*

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

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/connode.hpp"

#include "opto/convertnode.hpp"

#include "opto/divnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/movenode.hpp"

#include "opto/opaquenode.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_exact_trip_count-----------------------

// Compute loop exact trip count if possible. Do not recalculate trip count for

// split loops (pre-main-post) which have their limits and inits behind Opaque node.

void IdealLoopTree::compute_exact_trip_count( PhaseIdealLoop *phase ) {

  if (!_head->as_Loop()->is_valid_counted_loop()) {

    return;

  }

  CountedLoopNode* cl = _head->as_CountedLoop();

  // Trip count may become nonexact for iteration split loops since

  // RCE modifies limits. Note, _trip_count value is not reset since

  // it is used to limit unrolling of main loop.

  cl->set_nonexact_trip_count();

  // Loop's test should be part of loop.

  if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))

    return; // Infinite loop

#ifdef ASSERT

  BoolTest::mask bt = cl->loopexit()->test_trip();

  assert(bt == BoolTest::lt || bt == BoolTest::gt ||

         bt == BoolTest::ne, "canonical test is expected");

#endif

  Node* init_n = cl->init_trip();

  Node* limit_n = cl->limit();

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

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

    // Use longs to avoid integer overflow.

    int stride_con  = cl->stride_con();

    jlong init_con   = cl->init_trip()->get_int();

    jlong limit_con  = cl->limit()->get_int();

    int stride_m    = stride_con - (stride_con > 0 ? 1 : -1);

    jlong trip_count = (limit_con - init_con + stride_m)/stride_con;

    if (trip_count > 0 && (julong)trip_count < (julong)max_juint) {

      // Set exact trip count.

      cl->set_exact_trip_count((uint)trip_count);

    }

  }

}

//------------------------------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 SubINode(zero, inv1);

    phase->register_new_node(n_inv1, inv1_c);

  } else {

    n_inv1 = inv1;

  }

  Node* inv;

  if (neg_inv2) {

    inv = new SubINode(n_inv1, inv2);

  } else {

    inv = new AddINode(n_inv1, inv2);

  }

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

  Node* addx;

  if (neg_x) {

    addx = new SubINode(inv, x);

  } else {

    addx = new 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();

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

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

    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.

//

//                   orig

//

//                  stmt1

//                    |

//                    v

//              loop predicate

//                    |

//                    v

//                   loop<----+

//                     |      |

//                   stmt2    |

//                     |      |

//                     v      |

//                    if      ^

//                   / \      |

//                  /   \     |

//                 v     v    |

//               false true   |

//               /       \    |

//              /         ----+

//             |

//             v

//           exit

//

//

//            after clone loop

//

//                   stmt1

//                     |

//                     v

//               loop predicate

//                 /       \

//        clone   /         \   orig

//               /           \

//              /             \

//             v               v

//   +---->loop clone          loop<----+

//   |      |                    |      |

//   |    stmt2 clone          stmt2    |

//   |      |                    |      |

//   |      v                    v      |

//   ^      if clone            If      ^

//   |      / \                / \      |

//   |     /   \              /   \     |

//   |    v     v            v     v    |

//   |    true  false      false true   |

//   |    /         \      /       \    |

//   +----           \    /         ----+

//                    \  /

//                    1v v2

//                  region

//                     |

//                     v

//                   exit

//

//

//         after peel and predicate move

//

//                   stmt1

//                    /

//                   /

//        clone     /            orig

//                 /

//                /              +----------+

//               /               |          |

//              /          loop predicate   |

//             /                 |          |

//            v                  v          |

//   TOP-->loop clone          loop<----+   |

//          |                    |      |   |

//        stmt2 clone          stmt2    |   |

//          |                    |      |   ^

//          v                    v      |   |

//          if clone            If      ^   |

//          / \                / \      |   |

//         /   \              /   \     |   |

//        v     v            v     v    |   |

//      true   false      false  true   |   |

//        |         \      /       \    |   |

//        |          \    /         ----+   ^

//        |           \  /                  |

//        |           1v v2                 |

//        v         region                  |

//        |            |                    |

//        |            v                    |

//        |          exit                   |

//        |                                 |

//        +--------------->-----------------+

//

//

//              final graph

//

//                  stmt1

//                    |

//                    v

//                  stmt2 clone

//                    |

//                    v

//                   if clone

//                  / |

//                 /  |

//                v   v

//            false  true

//             |      |

//             |      v

//             | loop predicate

//             |      |

//             |      v

//             |     loop<----+

//             |      |       |

//             |    stmt2     |

//             |      |       |

//             |      v       |

//             v      if      ^

//             |     /  \     |

//             |    /    \    |

//             |   v     v    |

//             | false  true  |

//             |  |        \  |

//             v  v         --+

//            region

//              |

//              v

//             exit

//

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

  Node* head = loop->_head;

  bool counted_loop = head->is_CountedLoop();

  if (counted_loop) {

    CountedLoopNode *cl = head->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

    }

  }

  Node* entry = head->in(LoopNode::EntryControl);

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