/*

 * Copyright (c) 2000, 2019, 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/castnode.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"

#include "opto/superword.hpp"

#include "opto/vectornode.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);

  }

  // put body of outer strip mined loop on igvn work list as well

  if (_head->is_CountedLoop() && _head->as_Loop()->is_strip_mined()) {

    CountedLoopNode* l = _head->as_CountedLoop();

    Node* outer_loop = l->outer_loop();

    assert(outer_loop != NULL, "missing piece of strip mined loop");

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

    Node* outer_loop_tail = l->outer_loop_tail();

    assert(outer_loop_tail != NULL, "missing piece of strip mined loop");

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

    Node* outer_loop_end = l->outer_loop_end();

    assert(outer_loop_end != NULL, "missing piece of strip mined loop");

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

    Node* outer_safepoint = l->outer_safepoint();

    assert(outer_safepoint != NULL, "missing piece of strip mined loop");

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

    Node* cle_out = _head->as_CountedLoop()->loopexit()->proj_out(false);

    assert(cle_out != NULL, "missing piece of strip mined loop");

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

  }

}

//------------------------------compute_exact_trip_count-----------------------

// Compute loop 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_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 && limit_n != NULL) {

    // Use longs to avoid integer overflow.

    int stride_con = cl->stride_con();

    const TypeInt* init_type = phase->_igvn.type(init_n)->is_int();

    const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();

    jlong init_con = (stride_con > 0) ? init_type->_lo : init_type->_hi;

    jlong limit_con = (stride_con > 0) ? limit_type->_hi : limit_type->_lo;

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

      if (init_n->is_Con() && limit_n->is_Con()) {

        // Set exact trip count.

        cl->set_exact_trip_count((uint)trip_count);

      } else if (cl->unrolled_count() == 1) {

        // Set maximum trip count before unrolling.

        cl->set_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

float IdealLoopTree::compute_profile_trip_cnt_helper(Node* n) {

  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;

          return exit_cnt;

        }

      }

    }

  }

  if (n->is_Jump()) {

    JumpNode *jmp = n->as_Jump();

    if (jmp->_fcnt != COUNT_UNKNOWN) {

      float* probs = jmp->_probs;

      float exit_prob = 0;

      PhaseIdealLoop *phase = _phase;

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

        JumpProjNode* u = jmp->fast_out(i)->as_JumpProj();

        if (!is_member(_phase->get_loop(u))) {

          exit_prob += probs[u->_con];

        }

      }

      return exit_prob * jmp->_fcnt;

    }

  }

  return 0;

}

void IdealLoopTree::compute_profile_trip_cnt(PhaseIdealLoop *phase) {

  if (!_head->is_Loop()) {

    return;

  }

  LoopNode* head = _head->as_Loop();

  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 &&

        (back->Opcode() == Op_IfTrue ? 1-back->in(0)->as_If()->_prob : back->in(0)->as_If()->_prob) > PROB_MIN) {

      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->Opcode() == Op_IfTrue ? back_if->_prob : (1 - back_if->_prob));

    // Now compute a loop exit count

    float loop_exit_cnt = 0.0f;

    if (_child == NULL) {

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

        Node *n = _body[i];

        loop_exit_cnt += compute_profile_trip_cnt_helper(n);

      }

    } else {

      ResourceMark rm;

      Unique_Node_List wq;

      wq.push(back);

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

        Node *n = wq.at(i);

        assert(n->is_CFG(), "only control nodes");

        if (n != head) {

          if (n->is_Region()) {

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

              wq.push(n->in(j));

            }

          } else {

            loop_exit_cnt += compute_profile_trip_cnt_helper(n);

            wq.push(n->in(0));

          }

        }

      }

    }

    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;

    }

  } else {

    head->mark_profile_trip_failed();

  }

#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;

  if (!phase->may_require_nodes(10, 10)) 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 if the loop should be peeled, otherwise return FALSE. Peeling

// is applicable if we can make a loop-invariant test (usually a null-check)

// execute before we enter the loop. When TRUE, the estimated node budget is

// also requested.

bool IdealLoopTree::policy_peeling(PhaseIdealLoop *phase) {

  uint estimate = estimate_peeling(phase);

  return estimate == 0 ? false : phase->may_require_nodes(estimate);

}

// Perform actual policy and size estimate for the loop peeling transform, and

// return the estimated loop size if peeling is applicable, otherwise return

// zero. No node budget is allocated.

uint IdealLoopTree::estimate_peeling(PhaseIdealLoop *phase) {

  // If nodes are depleted, some transform has miscalculated its needs.

  assert(!phase->exceeding_node_budget(), "sanity");

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

  if (_body.size() > 255) {

    return 0;   // Suppress too large body size.

  }

  // Optimistic estimate that approximates loop body complexity via data and

  // control flow fan-out (instead of using the more pessimistic: BodySize^2).

  uint estimate = est_loop_clone_sz(2);

  if (phase->exceeding_node_budget(estimate)) {

    return 0;   // Too large to safely clone.

  }

  // Check for vectorized loops, any peeling done was already applied.

  if (_head->is_CountedLoop()) {

    CountedLoopNode* cl = _head->as_CountedLoop();

    if (cl->is_unroll_only() || cl->trip_count() == 1) {

      return 0;

    }

  }

  Node* test = tail();

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

             test->Opcode() == Op_RangeCheck,

             "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 estimate;    // Found reason to peel!

      }

    }

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

    // every path through the loop.

    test = phase->idom(test);

  }

  return 0;

}

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

//   |      / \                / \      |