/*

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

#include "memory/allocation.hpp"

#include "opto/block.hpp"

#include "opto/machnode.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

//------------------------------Tarjan-----------------------------------------

// A data structure that holds all the information needed to find dominators.

struct Tarjan {

  Block *_block;                // Basic block for this info

  uint _semi;                   // Semi-dominators

  uint _size;                   // Used for faster LINK and EVAL

  Tarjan *_parent;              // Parent in DFS

  Tarjan *_label;               // Used for LINK and EVAL

  Tarjan *_ancestor;            // Used for LINK and EVAL

  Tarjan *_child;               // Used for faster LINK and EVAL

  Tarjan *_dom;                 // Parent in dominator tree (immediate dom)

  Tarjan *_bucket;              // Set of vertices with given semidominator

  Tarjan *_dom_child;           // Child in dominator tree

  Tarjan *_dom_next;            // Next in dominator tree

  // Fast union-find work

  void COMPRESS();

  Tarjan *EVAL(void);

  void LINK( Tarjan *w, Tarjan *tarjan0 );

  void setdepth( uint size );

};

//------------------------------Dominator--------------------------------------

// Compute the dominator tree of the CFG.  The CFG must already have been

// constructed.  This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.

void PhaseCFG::Dominators( ) {

  // Pre-grow the blocks array, prior to the ResourceMark kicking in

  _blocks.map(_num_blocks,0);

  ResourceMark rm;

  // Setup mappings from my Graph to Tarjan's stuff and back

  // Note: Tarjan uses 1-based arrays

  Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1);

  // Tarjan's algorithm, almost verbatim:

  // Step 1:

  _rpo_ctr = _num_blocks;

  uint dfsnum = DFS( tarjan );

  if( dfsnum-1 != _num_blocks ) {// Check for unreachable loops!

    // If the returned dfsnum does not match the number of blocks, then we

    // must have some unreachable loops.  These can be made at any time by

    // IterGVN.  They are cleaned up by CCP or the loop opts, but the last

    // IterGVN can always make more that are not cleaned up.  Highly unlikely

    // except in ZKM.jar, where endless irreducible loops cause the loop opts

    // to not get run.

    //

    // Having found unreachable loops, we have made a bad RPO _block layout.

    // We can re-run the above DFS pass with the correct number of blocks,

    // and hack the Tarjan algorithm below to be robust in the presence of

    // such dead loops (as was done for the NTarjan code farther below).

    // Since this situation is so unlikely, instead I've decided to bail out.

    // CNC 7/24/2001

    C->record_method_not_compilable("unreachable loop");

    return;

  }

  _blocks._cnt = _num_blocks;

  // Tarjan is using 1-based arrays, so these are some initialize flags

  tarjan[0]._size = tarjan[0]._semi = 0;

  tarjan[0]._label = &tarjan[0];

  uint i;

  for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order

    Tarjan *w = &tarjan[i];     // Get vertex from DFS

    // Step 2:

    Node *whead = w->_block->head();

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

      Block *b = _bbs[whead->in(j)->_idx];

      Tarjan *vx = &tarjan[b->_pre_order];

      Tarjan *u = vx->EVAL();

      if( u->_semi < w->_semi )

        w->_semi = u->_semi;

    }

    // w is added to a bucket here, and only here.

    // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).

    // Thus bucket can be a linked list.

    // Thus we do not need a small integer name for each Block.

    w->_bucket = tarjan[w->_semi]._bucket;

    tarjan[w->_semi]._bucket = w;

    w->_parent->LINK( w, &tarjan[0] );

    // Step 3:

    for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {

      Tarjan *u = vx->EVAL();

      vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;

    }

  }

  // Step 4:

  for( i=2; i <= _num_blocks; i++ ) {

    Tarjan *w = &tarjan[i];

    if( w->_dom != &tarjan[w->_semi] )

      w->_dom = w->_dom->_dom;

    w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later

  }

  // No immediate dominator for the root

  Tarjan *w = &tarjan[_broot->_pre_order];

  w->_dom = NULL;

  w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later

  // Convert the dominator tree array into my kind of graph

  for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices

    Tarjan *t = &tarjan[i];     // Handy access

    Tarjan *tdom = t->_dom;     // Handy access to immediate dominator

    if( tdom )  {               // Root has no immediate dominator

      t->_block->_idom = tdom->_block; // Set immediate dominator

      t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child

      tdom->_dom_child = t;     // Make me a child of my parent

    } else

      t->_block->_idom = NULL;  // Root

  }

  w->setdepth( _num_blocks+1 ); // Set depth in dominator tree

}

//----------------------------Block_Stack--------------------------------------

class Block_Stack {

  private:

    struct Block_Descr {

      Block  *block;     // Block

      int    index;      // Index of block's successor pushed on stack

      int    freq_idx;   // Index of block's most frequent successor

    };

    Block_Descr *_stack_top;

    Block_Descr *_stack_max;

    Block_Descr *_stack;

    Tarjan *_tarjan;

    uint most_frequent_successor( Block *b );

  public:

    Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) {

      _stack = NEW_RESOURCE_ARRAY(Block_Descr, size);

      _stack_max = _stack + size;

      _stack_top = _stack - 1; // stack is empty

    }

    void push(uint pre_order, Block *b) {

      Tarjan *t = &_tarjan[pre_order]; // Fast local access

      b->_pre_order = pre_order;    // Flag as visited

      t->_block = b;                // Save actual block

      t->_semi = pre_order;         // Block to DFS map

      t->_label = t;                // DFS to vertex map

      t->_ancestor = NULL;          // Fast LINK & EVAL setup

      t->_child = &_tarjan[0];      // Sentenial

      t->_size = 1;

      t->_bucket = NULL;

      if (pre_order == 1)

        t->_parent = NULL;          // first block doesn't have parent

      else {

        // Save parent (current top block on stack) in DFS

        t->_parent = &_tarjan[_stack_top->block->_pre_order];

      }

      // Now put this block on stack

      ++_stack_top;

      assert(_stack_top < _stack_max, ""); // assert if stack have to grow

      _stack_top->block  = b;

      _stack_top->index  = -1;

      // Find the index into b->succs[] array of the most frequent successor.

      _stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0

    }

    Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; }

    bool is_nonempty() { return (_stack_top >= _stack); }

    bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); }

    Block* next_successor()  {

      int i = _stack_top->index;

      i++;

      if (i == _stack_top->freq_idx) i++;

      if (i >= (int)(_stack_top->block->_num_succs)) {

        i = _stack_top->freq_idx;   // process most frequent successor last

      }

      _stack_top->index = i;

      return _stack_top->block->_succs[ i ];

    }

};

//-------------------------most_frequent_successor-----------------------------

// Find the index into the b->succs[] array of the most frequent successor.

uint Block_Stack::most_frequent_successor( Block *b ) {

  uint freq_idx = 0;

  int eidx = b->end_idx();

  Node *n = b->_nodes[eidx];

  int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode();

  switch( op ) {

  case Op_CountedLoopEnd:

  case Op_If: {               // Split frequency amongst children

    float prob = n->as_MachIf()->_prob;

    // Is succ[0] the TRUE branch or the FALSE branch?

    if( b->_nodes[eidx+1]->Opcode() == Op_IfFalse )

      prob = 1.0f - prob;

    freq_idx = prob < PROB_FAIR;      // freq=1 for succ[0] < 0.5 prob

    break;

  }

  case Op_Catch:                // Split frequency amongst children

    for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ )

      if( b->_nodes[eidx+1+freq_idx]->as_CatchProj()->_con == CatchProjNode::fall_through_index )

        break;

    // Handle case of no fall-thru (e.g., check-cast MUST throw an exception)

    if( freq_idx == b->_num_succs ) freq_idx = 0;

    break;

    // Currently there is no support for finding out the most

    // frequent successor for jumps, so lets just make it the first one

  case Op_Jump:

  case Op_Root:

  case Op_Goto:

  case Op_NeverBranch:

    freq_idx = 0;               // fall thru

    break;

  case Op_TailCall:

  case Op_TailJump:

  case Op_Return:

  case Op_Halt:

  case Op_Rethrow:

    break;

  default:

    ShouldNotReachHere();

  }

  return freq_idx;

}

//------------------------------DFS--------------------------------------------

// Perform DFS search.  Setup 'vertex' as DFS to vertex mapping.  Setup

// 'semi' as vertex to DFS mapping.  Set 'parent' to DFS parent.

uint PhaseCFG::DFS( Tarjan *tarjan ) {

  Block *b = _broot;

  uint pre_order = 1;

  // Allocate stack of size _num_blocks+1 to avoid frequent realloc

  Block_Stack bstack(tarjan, _num_blocks+1);

  // Push on stack the state for the first block

  bstack.push(pre_order, b);

  ++pre_order;

  while (bstack.is_nonempty()) {

    if (!bstack.last_successor()) {

      // Walk over all successors in pre-order (DFS).

      Block *s = bstack.next_successor();

      if (s->_pre_order == 0) { // Check for no-pre-order, not-visited

        // Push on stack the state of successor

        bstack.push(pre_order, s);

        ++pre_order;

      }

    }

    else {

      // Build a reverse post-order in the CFG _blocks array

      Block *stack_top = bstack.pop();

      stack_top->_rpo = --_rpo_ctr;

      _blocks.map(stack_top->_rpo, stack_top);

    }

  }

  return pre_order;

}

//------------------------------COMPRESS---------------------------------------

void Tarjan::COMPRESS()

{

  assert( _ancestor != 0, "" );

  if( _ancestor->_ancestor != 0 ) {

    _ancestor->COMPRESS( );

    if( _ancestor->_label->_semi < _label->_semi )

      _label = _ancestor->_label;

    _ancestor = _ancestor->_ancestor;

  }

}

//------------------------------EVAL-------------------------------------------

Tarjan *Tarjan::EVAL() {

  if( !_ancestor ) return _label;

  COMPRESS();

  return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;

}

//------------------------------LINK-------------------------------------------

void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {

  Tarjan *s = w;

  while( w->_label->_semi < s->_child->_label->_semi ) {

    if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {

      s->_child->_ancestor = s;

      s->_child = s->_child->_child;

    } else {

      s->_child->_size = s->_size;

      s = s->_ancestor = s->_child;

    }

  }

  s->_label = w->_label;

  _size += w->_size;

  if( _size < (w->_size << 1) ) {

    Tarjan *tmp = s; s = _child; _child = tmp;

  }

  while( s != tarjan0 ) {

    s->_ancestor = this;

    s = s->_child;

  }

}

//------------------------------setdepth---------------------------------------

void Tarjan::setdepth( uint stack_size ) {

  Tarjan **top  = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);

  Tarjan **next = top;

  Tarjan **last;

  uint depth = 0;

  *top = this;

  ++top;

  do {

    // next level

    ++depth;

    last = top;

    do {

      // Set current depth for all tarjans on this level

      Tarjan *t = *next;     // next tarjan from stack

      ++next;

      do {

        t->_block->_dom_depth = depth; // Set depth in dominator tree

        Tarjan *dom_child = t->_dom_child;

        t = t->_dom_next;    // next tarjan

        if (dom_child != NULL) {

          *top = dom_child;  // save child on stack

          ++top;

        }

      } while (t != NULL);

    } while (next < last);

  } while (last < top);

}

//*********************** DOMINATORS ON THE SEA OF NODES***********************

//------------------------------NTarjan----------------------------------------

// A data structure that holds all the information needed to find dominators.

struct NTarjan {

  Node *_control;               // Control node associated with this info

  uint _semi;                   // Semi-dominators

  uint _size;                   // Used for faster LINK and EVAL

  NTarjan *_parent;             // Parent in DFS

  NTarjan *_label;              // Used for LINK and EVAL

  NTarjan *_ancestor;           // Used for LINK and EVAL

  NTarjan *_child;              // Used for faster LINK and EVAL

  NTarjan *_dom;                // Parent in dominator tree (immediate dom)

  NTarjan *_bucket;             // Set of vertices with given semidominator

  NTarjan *_dom_child;          // Child in dominator tree

  NTarjan *_dom_next;           // Next in dominator tree

  // Perform DFS search.

  // Setup 'vertex' as DFS to vertex mapping.

  // Setup 'semi' as vertex to DFS mapping.

  // Set 'parent' to DFS parent.

  static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );

  void setdepth( uint size, uint *dom_depth );

  // Fast union-find work

  void COMPRESS();

  NTarjan *EVAL(void);

  void LINK( NTarjan *w, NTarjan *ntarjan0 );

#ifndef PRODUCT

  void dump(int offset) const;

#endif

};

//------------------------------Dominator--------------------------------------

// Compute the dominator tree of the sea of nodes.  This version walks all CFG

// nodes (using the is_CFG() call) and places them in a dominator tree.  Thus,

// it needs a count of the CFG nodes for the mapping table. This is the

// Lengauer & Tarjan O(E-alpha(E,V)) algorithm.

void PhaseIdealLoop::Dominators() {

  ResourceMark rm;

  // Setup mappings from my Graph to Tarjan's stuff and back

  // Note: Tarjan uses 1-based arrays

  NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);

  // Initialize _control field for fast reference

  int i;

  for( i= C->unique()-1; i>=0; i-- )

    ntarjan[i]._control = NULL;

  // Store the DFS order for the main loop

  uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);

  memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint));

  // Tarjan's algorithm, almost verbatim:

  // Step 1:

  VectorSet visited(Thread::current()->resource_area());

  int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);

  // Tarjan is using 1-based arrays, so these are some initialize flags

  ntarjan[0]._size = ntarjan[0]._semi = 0;

  ntarjan[0]._label = &ntarjan[0];

  for( i = dfsnum-1; i>1; i-- ) {        // For all nodes in reverse DFS order

    NTarjan *w = &ntarjan[i];            // Get Node from DFS

    assert(w->_control != NULL,"bad DFS walk");

    // Step 2:

    Node *whead = w->_control;

    for( uint j=0; j < whead->req(); j++ ) { // For each predecessor

      if( whead->in(j) == NULL || !whead->in(j)->is_CFG() )

        continue;                            // Only process control nodes

      uint b = dfsorder[whead->in(j)->_idx];

      if(b == max_uint) continue;

      NTarjan *vx = &ntarjan[b];

      NTarjan *u = vx->EVAL();

      if( u->_semi < w->_semi )

        w->_semi = u->_semi;

    }

    // w is added to a bucket here, and only here.

    // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).

    // Thus bucket can be a linked list.

    w->_bucket = ntarjan[w->_semi]._bucket;

    ntarjan[w->_semi]._bucket = w;

    w->_parent->LINK( w, &ntarjan[0] );

    // Step 3:

    for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {

      NTarjan *u = vx->EVAL();

      vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;

    }

    // Cleanup any unreachable loops now.  Unreachable loops are loops that

    // flow into the main graph (and hence into ROOT) but are not reachable

    // from above.  Such code is dead, but requires a global pass to detect

    // it; this global pass was the 'build_loop_tree' pass run just prior.

    if( !_verify_only && whead->is_Region() ) {

      for( uint i = 1; i < whead->req(); i++ ) {

        if (!has_node(whead->in(i))) {

          // Kill dead input path

          assert( !visited.test(whead->in(i)->_idx),

                  "input with no loop must be dead" );

          _igvn.hash_delete(whead);

          whead->del_req(i);

          _igvn._worklist.push(whead);

          for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {

            Node* p = whead->fast_out(j);

            if( p->is_Phi() ) {

              _igvn.hash_delete(p);

              p->del_req(i);

              _igvn._worklist.push(p);

            }

          }

          i--;                  // Rerun same iteration

        } // End of if dead input path

      } // End of for all input paths

    } // End if if whead is a Region

  } // End of for all Nodes in reverse DFS order

  // Step 4:

  for( i=2; i < dfsnum; i++ ) { // DFS order

    NTarjan *w = &ntarjan[i];

    assert(w->_control != NULL,"Bad DFS walk");

    if( w->_dom != &ntarjan[w->_semi] )

      w->_dom = w->_dom->_dom;

    w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later

  }

  // No immediate dominator for the root

  NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];

  w->_dom = NULL;

  w->_parent = NULL;

  w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later

  // Convert the dominator tree array into my kind of graph

  for( i=1; i<dfsnum; i++ ) {          // For all Tarjan vertices

    NTarjan *t = &ntarjan[i];          // Handy access

    assert(t->_control != NULL,"Bad DFS walk");

    NTarjan *tdom = t->_dom;           // Handy access to immediate dominator

    if( tdom )  {                      // Root has no immediate dominator

      _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator

      t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child

      tdom->_dom_child = t;            // Make me a child of my parent

    } else

      _idom[C->root()->_idx] = NULL; // Root

  }

  w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree

  // Pick up the 'top' node as well

  _idom     [C->top()->_idx] = C->root();

  _dom_depth[C->top()->_idx] = 1;

  // Debug Print of Dominator tree

  if( PrintDominators ) {

#ifndef PRODUCT

    w->dump(0);

#endif

  }

}

//------------------------------DFS--------------------------------------------

// Perform DFS search.  Setup 'vertex' as DFS to vertex mapping.  Setup

// 'semi' as vertex to DFS mapping.  Set 'parent' to DFS parent.

int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {