/*

 * Copyright (c) 1997, 2014, 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 "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/block.hpp"

#include "opto/c2compiler.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/machnode.hpp"

#include "opto/opcodes.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "runtime/deoptimization.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

// To avoid float value underflow

#define MIN_BLOCK_FREQUENCY 1.e-35f

//----------------------------schedule_node_into_block-------------------------

// Insert node n into block b. Look for projections of n and make sure they

// are in b also.

void PhaseCFG::schedule_node_into_block( Node *n, Block *b ) {

  // Set basic block of n, Add n to b,

  map_node_to_block(n, b);

  b->add_inst(n);

  // After Matching, nearly any old Node may have projections trailing it.

  // These are usually machine-dependent flags.  In any case, they might

  // float to another block below this one.  Move them up.

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

    Node*  use  = n->fast_out(i);

    if (use->is_Proj()) {

      Block* buse = get_block_for_node(use);

      if (buse != b) {              // In wrong block?

        if (buse != NULL) {

          buse->find_remove(use);   // Remove from wrong block

        }

        map_node_to_block(use, b);

        b->add_inst(use);

      }

    }

  }

}

//----------------------------replace_block_proj_ctrl-------------------------

// Nodes that have is_block_proj() nodes as their control need to use

// the appropriate Region for their actual block as their control since

// the projection will be in a predecessor block.

void PhaseCFG::replace_block_proj_ctrl( Node *n ) {

  const Node *in0 = n->in(0);

  assert(in0 != NULL, "Only control-dependent");

  const Node *p = in0->is_block_proj();

  if (p != NULL && p != n) {    // Control from a block projection?

    assert(!n->pinned() || n->is_MachConstantBase(), "only pinned MachConstantBase node is expected here");

    // Find trailing Region

    Block *pb = get_block_for_node(in0); // Block-projection already has basic block

    uint j = 0;

    if (pb->_num_succs != 1) {  // More then 1 successor?

      // Search for successor

      uint max = pb->number_of_nodes();

      assert( max > 1, "" );

      uint start = max - pb->_num_succs;

      // Find which output path belongs to projection

      for (j = start; j < max; j++) {

        if( pb->get_node(j) == in0 )

          break;

      }

      assert( j < max, "must find" );

      // Change control to match head of successor basic block

      j -= start;

    }

    n->set_req(0, pb->_succs[j]->head());

  }

}

//------------------------------schedule_pinned_nodes--------------------------

// Set the basic block for Nodes pinned into blocks

void PhaseCFG::schedule_pinned_nodes(VectorSet &visited) {

  // Allocate node stack of size C->unique()+8 to avoid frequent realloc

  GrowableArray <Node *> spstack(C->unique() + 8);

  spstack.push(_root);

  while (spstack.is_nonempty()) {

    Node* node = spstack.pop();

    if (!visited.test_set(node->_idx)) { // Test node and flag it as visited

      if (node->pinned() && !has_block(node)) {  // Pinned?  Nail it down!

        assert(node->in(0), "pinned Node must have Control");

        // Before setting block replace block_proj control edge

        replace_block_proj_ctrl(node);

        Node* input = node->in(0);

        while (!input->is_block_start()) {

          input = input->in(0);

        }

        Block* block = get_block_for_node(input); // Basic block of controlling input

        schedule_node_into_block(node, block);

      }

      // process all inputs that are non NULL

      for (int i = node->req() - 1; i >= 0; --i) {

        if (node->in(i) != NULL) {

          spstack.push(node->in(i));

        }

      }

    }

  }

}

#ifdef ASSERT

// Assert that new input b2 is dominated by all previous inputs.

// Check this by by seeing that it is dominated by b1, the deepest

// input observed until b2.

static void assert_dom(Block* b1, Block* b2, Node* n, const PhaseCFG* cfg) {

  if (b1 == NULL)  return;

  assert(b1->_dom_depth < b2->_dom_depth, "sanity");

  Block* tmp = b2;

  while (tmp != b1 && tmp != NULL) {

    tmp = tmp->_idom;

  }

  if (tmp != b1) {

    // Detected an unschedulable graph.  Print some nice stuff and die.

    tty->print_cr("!!! Unschedulable graph !!!");

    for (uint j=0; j<n->len(); j++) { // For all inputs

      Node* inn = n->in(j); // Get input

      if (inn == NULL)  continue;  // Ignore NULL, missing inputs

      Block* inb = cfg->get_block_for_node(inn);

      tty->print("B%d idom=B%d depth=%2d ",inb->_pre_order,

                 inb->_idom ? inb->_idom->_pre_order : 0, inb->_dom_depth);

      inn->dump();

    }

    tty->print("Failing node: ");

    n->dump();

    assert(false, "unscheduable graph");

  }

}

#endif

static Block* find_deepest_input(Node* n, const PhaseCFG* cfg) {

  // Find the last input dominated by all other inputs.

  Block* deepb           = NULL;        // Deepest block so far

  int    deepb_dom_depth = 0;

  for (uint k = 0; k < n->len(); k++) { // For all inputs

    Node* inn = n->in(k);               // Get input

    if (inn == NULL)  continue;         // Ignore NULL, missing inputs

    Block* inb = cfg->get_block_for_node(inn);

    assert(inb != NULL, "must already have scheduled this input");

    if (deepb_dom_depth < (int) inb->_dom_depth) {

      // The new inb must be dominated by the previous deepb.

      // The various inputs must be linearly ordered in the dom

      // tree, or else there will not be a unique deepest block.

      DEBUG_ONLY(assert_dom(deepb, inb, n, cfg));

      deepb = inb;                      // Save deepest block

      deepb_dom_depth = deepb->_dom_depth;

    }

  }

  assert(deepb != NULL, "must be at least one input to n");

  return deepb;

}

//------------------------------schedule_early---------------------------------

// Find the earliest Block any instruction can be placed in.  Some instructions

// are pinned into Blocks.  Unpinned instructions can appear in last block in

// which all their inputs occur.

bool PhaseCFG::schedule_early(VectorSet &visited, Node_List &roots) {

  // Allocate stack with enough space to avoid frequent realloc

  Node_Stack nstack(roots.Size() + 8);

  // _root will be processed among C->top() inputs

  roots.push(C->top());

  visited.set(C->top()->_idx);

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

    // Use local variables nstack_top_n & nstack_top_i to cache values

    // on stack's top.

    Node* parent_node = roots.pop();

    uint  input_index = 0;

    while (true) {

      if (input_index == 0) {

        // Fixup some control.  Constants without control get attached

        // to root and nodes that use is_block_proj() nodes should be attached

        // to the region that starts their block.

        const Node* control_input = parent_node->in(0);

        if (control_input != NULL) {

          replace_block_proj_ctrl(parent_node);

        } else {

          // Is a constant with NO inputs?

          if (parent_node->req() == 1) {

            parent_node->set_req(0, _root);

          }

        }

      }

      // First, visit all inputs and force them to get a block.  If an

      // input is already in a block we quit following inputs (to avoid

      // cycles). Instead we put that Node on a worklist to be handled

      // later (since IT'S inputs may not have a block yet).

      // Assume all n's inputs will be processed

      bool done = true;

      while (input_index < parent_node->len()) {

        Node* in = parent_node->in(input_index++);

        if (in == NULL) {

          continue;

        }

        int is_visited = visited.test_set(in->_idx);

        if (!has_block(in)) {

          if (is_visited) {

            return false;

          }

          // Save parent node and next input's index.

          nstack.push(parent_node, input_index);

          // Process current input now.

          parent_node = in;

          input_index = 0;

          // Not all n's inputs processed.

          done = false;

          break;

        } else if (!is_visited) {

          // Visit this guy later, using worklist

          roots.push(in);

        }

      }

      if (done) {

        // All of n's inputs have been processed, complete post-processing.

        // Some instructions are pinned into a block.  These include Region,

        // Phi, Start, Return, and other control-dependent instructions and

        // any projections which depend on them.

        if (!parent_node->pinned()) {

          // Set earliest legal block.

          Block* earliest_block = find_deepest_input(parent_node, this);

          map_node_to_block(parent_node, earliest_block);

        } else {

          assert(get_block_for_node(parent_node) == get_block_for_node(parent_node->in(0)), "Pinned Node should be at the same block as its control edge");

        }

        if (nstack.is_empty()) {

          // Finished all nodes on stack.

          // Process next node on the worklist 'roots'.

          break;

        }

        // Get saved parent node and next input's index.

        parent_node = nstack.node();

        input_index = nstack.index();

        nstack.pop();

      }

    }

  }

  return true;

}

//------------------------------dom_lca----------------------------------------

// Find least common ancestor in dominator tree

// LCA is a current notion of LCA, to be raised above 'this'.

// As a convenient boundary condition, return 'this' if LCA is NULL.

// Find the LCA of those two nodes.

Block* Block::dom_lca(Block* LCA) {

  if (LCA == NULL || LCA == this)  return this;

  Block* anc = this;

  while (anc->_dom_depth > LCA->_dom_depth)

    anc = anc->_idom;           // Walk up till anc is as high as LCA

  while (LCA->_dom_depth > anc->_dom_depth)

    LCA = LCA->_idom;           // Walk up till LCA is as high as anc

  while (LCA != anc) {          // Walk both up till they are the same

    LCA = LCA->_idom;

    anc = anc->_idom;

  }

  return LCA;

}

//--------------------------raise_LCA_above_use--------------------------------

// We are placing a definition, and have been given a def->use edge.

// The definition must dominate the use, so move the LCA upward in the

// dominator tree to dominate the use.  If the use is a phi, adjust

// the LCA only with the phi input paths which actually use this def.

static Block* raise_LCA_above_use(Block* LCA, Node* use, Node* def, const PhaseCFG* cfg) {

  Block* buse = cfg->get_block_for_node(use);

  if (buse == NULL)    return LCA;   // Unused killing Projs have no use block

  if (!use->is_Phi())  return buse->dom_lca(LCA);

  uint pmax = use->req();       // Number of Phi inputs

  // Why does not this loop just break after finding the matching input to

  // the Phi?  Well...it's like this.  I do not have true def-use/use-def

  // chains.  Means I cannot distinguish, from the def-use direction, which

  // of many use-defs lead from the same use to the same def.  That is, this

  // Phi might have several uses of the same def.  Each use appears in a

  // different predecessor block.  But when I enter here, I cannot distinguish

  // which use-def edge I should find the predecessor block for.  So I find

  // them all.  Means I do a little extra work if a Phi uses the same value

  // more than once.

  for (uint j=1; j<pmax; j++) { // For all inputs

    if (use->in(j) == def) {    // Found matching input?

      Block* pred = cfg->get_block_for_node(buse->pred(j));

      LCA = pred->dom_lca(LCA);

    }

  }

  return LCA;

}

//----------------------------raise_LCA_above_marks----------------------------

// Return a new LCA that dominates LCA and any of its marked predecessors.

// Search all my parents up to 'early' (exclusive), looking for predecessors

// which are marked with the given index.  Return the LCA (in the dom tree)

// of all marked blocks.  If there are none marked, return the original

// LCA.

static Block* raise_LCA_above_marks(Block* LCA, node_idx_t mark, Block* early, const PhaseCFG* cfg) {

  Block_List worklist;

  worklist.push(LCA);

  while (worklist.size() > 0) {

    Block* mid = worklist.pop();

    if (mid == early)  continue;  // stop searching here

    // Test and set the visited bit.

    if (mid->raise_LCA_visited() == mark)  continue;  // already visited

    // Don't process the current LCA, otherwise the search may terminate early

    if (mid != LCA && mid->raise_LCA_mark() == mark) {

      // Raise the LCA.

      LCA = mid->dom_lca(LCA);

      if (LCA == early)  break;   // stop searching everywhere

      assert(early->dominates(LCA), "early is high enough");

      // Resume searching at that point, skipping intermediate levels.

      worklist.push(LCA);

      if (LCA == mid)

        continue; // Don't mark as visited to avoid early termination.

    } else {

      // Keep searching through this block's predecessors.

      for (uint j = 1, jmax = mid->num_preds(); j < jmax; j++) {

        Block* mid_parent = cfg->get_block_for_node(mid->pred(j));

        worklist.push(mid_parent);

      }

    }

    mid->set_raise_LCA_visited(mark);

  }

  return LCA;

}

//--------------------------memory_early_block--------------------------------

// This is a variation of find_deepest_input, the heart of schedule_early.

// Find the "early" block for a load, if we considered only memory and

// address inputs, that is, if other data inputs were ignored.

//

// Because a subset of edges are considered, the resulting block will

// be earlier (at a shallower dom_depth) than the true schedule_early

// point of the node. We compute this earlier block as a more permissive

// site for anti-dependency insertion, but only if subsume_loads is enabled.

static Block* memory_early_block(Node* load, Block* early, const PhaseCFG* cfg) {

  Node* base;

  Node* index;

  Node* store = load->in(MemNode::Memory);

  load->as_Mach()->memory_inputs(base, index);

  assert(base != NodeSentinel && index != NodeSentinel,

         "unexpected base/index inputs");

  Node* mem_inputs[4];

  int mem_inputs_length = 0;

  if (base != NULL)  mem_inputs[mem_inputs_length++] = base;

  if (index != NULL) mem_inputs[mem_inputs_length++] = index;

  if (store != NULL) mem_inputs[mem_inputs_length++] = store;

  // In the comparision below, add one to account for the control input,

  // which may be null, but always takes up a spot in the in array.

  if (mem_inputs_length + 1 < (int) load->req()) {

    // This "load" has more inputs than just the memory, base and index inputs.

    // For purposes of checking anti-dependences, we need to start

    // from the early block of only the address portion of the instruction,

    // and ignore other blocks that may have factored into the wider

    // schedule_early calculation.

    if (load->in(0) != NULL) mem_inputs[mem_inputs_length++] = load->in(0);

    Block* deepb           = NULL;        // Deepest block so far

    int    deepb_dom_depth = 0;

    for (int i = 0; i < mem_inputs_length; i++) {

      Block* inb = cfg->get_block_for_node(mem_inputs[i]);

      if (deepb_dom_depth < (int) inb->_dom_depth) {

        // The new inb must be dominated by the previous deepb.

        // The various inputs must be linearly ordered in the dom

        // tree, or else there will not be a unique deepest block.

        DEBUG_ONLY(assert_dom(deepb, inb, load, cfg));

        deepb = inb;                      // Save deepest block

        deepb_dom_depth = deepb->_dom_depth;

      }

    }

    early = deepb;

  }

  return early;

}

//--------------------------insert_anti_dependences---------------------------

// A load may need to witness memory that nearby stores can overwrite.

// For each nearby store, either insert an "anti-dependence" edge

// from the load to the store, or else move LCA upward to force the

// load to (eventually) be scheduled in a block above the store.

//

// Do not add edges to stores on distinct control-flow paths;

// only add edges to stores which might interfere.

//

// Return the (updated) LCA.  There will not be any possibly interfering

// store between the load's "early block" and the updated LCA.

// Any stores in the updated LCA will have new precedence edges

// back to the load.  The caller is expected to schedule the load

// in the LCA, in which case the precedence edges will make LCM

// preserve anti-dependences.  The caller may also hoist the load

// above the LCA, if it is not the early block.

Block* PhaseCFG::insert_anti_dependences(Block* LCA, Node* load, bool verify) {

  assert(load->needs_anti_dependence_check(), "must be a load of some sort");

  assert(LCA != NULL, "");

  DEBUG_ONLY(Block* LCA_orig = LCA);

  // Compute the alias index.  Loads and stores with different alias indices

  // do not need anti-dependence edges.

  uint load_alias_idx = C->get_alias_index(load->adr_type());

#ifdef ASSERT

  if (load_alias_idx == Compile::AliasIdxBot && C->AliasLevel() > 0 &&

      (PrintOpto || VerifyAliases ||

       PrintMiscellaneous && (WizardMode || Verbose))) {

    // Load nodes should not consume all of memory.

    // Reporting a bottom type indicates a bug in adlc.

    // If some particular type of node validly consumes all of memory,

    // sharpen the preceding "if" to exclude it, so we can catch bugs here.

    tty->print_cr("*** Possible Anti-Dependence Bug:  Load consumes all of memory.");

    load->dump(2);

    if (VerifyAliases)  assert(load_alias_idx != Compile::AliasIdxBot, "");

  }

#endif

  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrComp),

         "String compare is only known 'load' that does not conflict with any stores");

  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrEquals),

         "String equals is a 'load' that does not conflict with any stores");

  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_StrIndexOf),

         "String indexOf is a 'load' that does not conflict with any stores");

  assert(load_alias_idx || (load->is_Mach() && load->as_Mach()->ideal_Opcode() == Op_AryEq),

         "Arrays equals is a 'load' that do not conflict with any stores");

  if (!C->alias_type(load_alias_idx)->is_rewritable()) {

    // It is impossible to spoil this load by putting stores before it,

    // because we know that the stores will never update the value

    // which 'load' must witness.

    return LCA;

  }

  node_idx_t load_index = load->_idx;

  // Note the earliest legal placement of 'load', as determined by

  // by the unique point in the dom tree where all memory effects

  // and other inputs are first available.  (Computed by schedule_early.)

  // For normal loads, 'early' is the shallowest place (dom graph wise)

  // to look for anti-deps between this load and any store.

  Block* early = get_block_for_node(load);

  // If we are subsuming loads, compute an "early" block that only considers

  // memory or address inputs. This block may be different than the

  // schedule_early block in that it could be at an even shallower depth in the

  // dominator tree, and allow for a broader discovery of anti-dependences.

  if (C->subsume_loads()) {

    early = memory_early_block(load, early, this);

  }

  ResourceArea *area = Thread::current()->resource_area();

  Node_List worklist_mem(area);     // prior memory state to store

  Node_List worklist_store(area);   // possible-def to explore

  Node_List worklist_visited(area); // visited mergemem nodes

  Node_List non_early_stores(area); // all relevant stores outside of early

  bool must_raise_LCA = false;

#ifdef TRACK_PHI_INPUTS

  // %%% This extra checking fails because MergeMem nodes are not GVNed.

  // Provide "phi_inputs" to check if every input to a PhiNode is from the

  // original memory state.  This indicates a PhiNode for which should not

  // prevent the load from sinking.  For such a block, set_raise_LCA_mark

  // may be overly conservative.

  // Mechanism: count inputs seen for each Phi encountered in worklist_store.

  DEBUG_ONLY(GrowableArray<uint> phi_inputs(area, C->unique(),0,0));

#endif

  // 'load' uses some memory state; look for users of the same state.

  // Recurse through MergeMem nodes to the stores that use them.