/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#include "incls/_precompiled.incl"

#include "incls/_gcm.cpp.incl"

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

  _bbs.map(n->_idx, 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 = _bbs[use->_idx];

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

        if (buse != NULL)

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

        _bbs.map(use->_idx, b);     // Re-insert in this block

        b->add_inst(use);

      }

    }

  }

}

//------------------------------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 *n = spstack.pop();

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

      if( n->pinned() && !_bbs.lookup(n->_idx) ) {  // Pinned?  Nail it down!

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

        assert( input, "pinned Node must have Control" );

        while( !input->is_block_start() )

          input = input->in(0);

        Block *b = _bbs[input->_idx];  // Basic block of controlling input

        schedule_node_into_block(n, b);

      }

      for( int i = n->req() - 1; i >= 0; --i ) {  // For all inputs

        if( n->in(i) != NULL )

          spstack.push(n->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, Block_Array &bbs) {

  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 = bbs[inn->_idx];

      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, Block_Array &bbs) {

  // 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 = bbs[inn->_idx];

    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, bbs));

      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); // (unique >> 1) + 24 from Java2D stats

  // roots.push(_root); _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 *nstack_top_n = roots.pop();

    uint  nstack_top_i = 0;

//while_nstack_nonempty:

    while (true) {

      // Get parent node and next input's index from stack's top.

      Node *n = nstack_top_n;

      uint  i = nstack_top_i;

      if (i == 0) {

        // Special control input processing.

        // While I am here, go ahead and look for Nodes which are taking control

        // from a is_block_proj Node.  After I inserted RegionNodes to make proper

        // blocks, the control at a is_block_proj more properly comes from the

        // Region being controlled by the block_proj Node.

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

        if (in0 != NULL) {              // Control-dependent?

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

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

            // Find trailing Region

            Block *pb = _bbs[in0->_idx]; // Block-projection already has basic block

            uint j = 0;

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

              // Search for successor

              uint max = pb->_nodes.size();

              assert( max > 1, "" );

              uint start = max - pb->_num_succs;

              // Find which output path belongs to projection

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

                if( pb->_nodes[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());

          }

        } else {               // n->in(0) == NULL

          if (n->req() == 1) { // This guy is a constant with NO inputs?

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

      bool done = true;              // Assume all n's inputs will be processed

      while (i < n->len()) {         // For all inputs

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

        ++i;

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

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

        if (!_bbs.lookup(in->_idx)) { // Missing block selection?

          if (is_visited) {

            // assert( !visited.test(in->_idx), "did not schedule early" );

            return false;

          }

          nstack.push(n, i);         // Save parent node and next input's index.

          nstack_top_n = in;         // Process current input now.

          nstack_top_i = 0;

          done = false;              // Not all n's inputs processed.

          break; // continue while_nstack_nonempty;

        } else if (!is_visited) {    // Input not yet visited?

          roots.push(in);            // Visit this guy later, using worklist

        }

      }

      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 (!n->pinned()) {

          // Set earliest legal block.

          _bbs.map(n->_idx, find_deepest_input(n, _bbs));

        }

        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.

        nstack_top_n = nstack.node();

        nstack_top_i = nstack.index();

        nstack.pop();

      } //    if (done)

    }   // while (true)

  }     // while (roots.size() != 0)

  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, Block_Array &bbs) {

  Block* buse = bbs[use->_idx];

  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 = bbs[buse->pred(j)->_idx];

      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, Block_Array &bbs) {

  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 = bbs[ mid->pred(j)->_idx ];

        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, Block_Array &bbs) {

  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 = bbs[mem_inputs[i]->_idx];

      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, bbs));

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

  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 = _bbs[load_index];

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

  }

  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.

  // Each of these stores is a possible definition of memory

  // that 'load' needs to use.  We need to force 'load'

  // to occur before each such store.  When the store is in

  // the same block as 'load', we insert an anti-dependence

  // edge load->store.

  // The relevant stores "nearby" the load consist of a tree rooted

  // at initial_mem, with internal nodes of type MergeMem.

  // Therefore, the branches visited by the worklist are of this form:

  //    initial_mem -> (MergeMem ->)* store

  // The anti-dependence constraints apply only to the fringe of this tree.

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

  worklist_store.push(initial_mem);

  worklist_visited.push(initial_mem);

  worklist_mem.push(NULL);

  while (worklist_store.size() > 0) {

    // Examine a nearby store to see if it might interfere with our load.

    Node* mem   = worklist_mem.pop();

    Node* store = worklist_store.pop();

    uint op = store->Opcode();

    // MergeMems do not directly have anti-deps.

    // Treat them as internal nodes in a forward tree of memory states,

    // the leaves of which are each a 'possible-def'.

    if (store == initial_mem    // root (exclusive) of tree we are searching

        || op == Op_MergeMem    // internal node of tree we are searching

        ) {

      mem = store;   // It's not a possibly interfering store.

      if (store == initial_mem)

        initial_mem = NULL;  // only process initial memory once

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

        store = mem->fast_out(i);

        if (store->is_MergeMem()) {

          // Be sure we don't get into combinatorial problems.

          // (Allow phis to be repeated; they can merge two relevant states.)

          uint j = worklist_visited.size();

          for (; j > 0; j--) {

            if (worklist_visited.at(j-1) == store)  break;

          }

          if (j > 0)  continue; // already on work list; do not repeat

          worklist_visited.push(store);

        }

        worklist_mem.push(mem);

        worklist_store.push(store);

      }

      continue;

    }

    if (op == Op_MachProj || op == Op_Catch)   continue;

    if (store->needs_anti_dependence_check())  continue;  // not really a store

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

    // indices do not need anti-dependence edges.  Wide MemBar's are

    // anti-dependent on everything (except immutable memories).

    const TypePtr* adr_type = store->adr_type();