/*

 * 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.inline.hpp"

#include "opto/block.hpp"

#include "opto/cfgnode.hpp"

#include "opto/chaitin.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/matcher.hpp"

#include "opto/opcodes.hpp"

#include "opto/rootnode.hpp"

#include "utilities/copy.hpp"

// Optimization - Graph Style

//-----------------------------------------------------------------------------

void Block_Array::grow( uint i ) {

  assert(i >= Max(), "must be an overflow");

  debug_only(_limit = i+1);

  if( i < _size )  return;

  if( !_size ) {

    _size = 1;

    _blocks = (Block**)_arena->Amalloc( _size * sizeof(Block*) );

    _blocks[0] = NULL;

  }

  uint old = _size;

  while( i >= _size ) _size <<= 1;      // Double to fit

  _blocks = (Block**)_arena->Arealloc( _blocks, old*sizeof(Block*),_size*sizeof(Block*));

  Copy::zero_to_bytes( &_blocks[old], (_size-old)*sizeof(Block*) );

}

//=============================================================================

void Block_List::remove(uint i) {

  assert(i < _cnt, "index out of bounds");

  Copy::conjoint_words_to_lower((HeapWord*)&_blocks[i+1], (HeapWord*)&_blocks[i], ((_cnt-i-1)*sizeof(Block*)));

  pop(); // shrink list by one block

}

void Block_List::insert(uint i, Block *b) {

  push(b); // grow list by one block

  Copy::conjoint_words_to_higher((HeapWord*)&_blocks[i], (HeapWord*)&_blocks[i+1], ((_cnt-i-1)*sizeof(Block*)));

  _blocks[i] = b;

}

#ifndef PRODUCT

void Block_List::print() {

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

    tty->print("B%d ", _blocks[i]->_pre_order);

  }

  tty->print("size = %d\n", size());

}

#endif

//=============================================================================

uint Block::code_alignment() {

  // Check for Root block

  if( _pre_order == 0 ) return CodeEntryAlignment;

  // Check for Start block

  if( _pre_order == 1 ) return InteriorEntryAlignment;

  // Check for loop alignment

  if (has_loop_alignment())  return loop_alignment();

  return 1;                     // no particular alignment

}

uint Block::compute_loop_alignment() {

  Node *h = head();

  if( h->is_Loop() && h->as_Loop()->is_inner_loop() )  {

    // Pre- and post-loops have low trip count so do not bother with

    // NOPs for align loop head.  The constants are hidden from tuning

    // but only because my "divide by 4" heuristic surely gets nearly

    // all possible gain (a "do not align at all" heuristic has a

    // chance of getting a really tiny gain).

    if( h->is_CountedLoop() && (h->as_CountedLoop()->is_pre_loop() ||

                                h->as_CountedLoop()->is_post_loop()) )

      return (OptoLoopAlignment > 4) ? (OptoLoopAlignment>>2) : 1;

    // Loops with low backedge frequency should not be aligned.

    Node *n = h->in(LoopNode::LoopBackControl)->in(0);

    if( n->is_MachIf() && n->as_MachIf()->_prob < 0.01 ) {

      return 1;             // Loop does not loop, more often than not!

    }

    return OptoLoopAlignment; // Otherwise align loop head

  }

  return 1;                     // no particular alignment

}

//-----------------------------------------------------------------------------

// Compute the size of first 'inst_cnt' instructions in this block.

// Return the number of instructions left to compute if the block has

// less then 'inst_cnt' instructions. Stop, and return 0 if sum_size

// exceeds OptoLoopAlignment.

uint Block::compute_first_inst_size(uint& sum_size, uint inst_cnt,

                                    PhaseRegAlloc* ra) {

  uint last_inst = _nodes.size();

  for( uint j = 0; j < last_inst && inst_cnt > 0; j++ ) {

    uint inst_size = _nodes[j]->size(ra);

    if( inst_size > 0 ) {

      inst_cnt--;

      uint sz = sum_size + inst_size;

      if( sz <= (uint)OptoLoopAlignment ) {

        // Compute size of instructions which fit into fetch buffer only

        // since all inst_cnt instructions will not fit even if we align them.

        sum_size = sz;

      } else {

        return 0;

      }

    }

  }

  return inst_cnt;

}

//-----------------------------------------------------------------------------

uint Block::find_node( const Node *n ) const {

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

    if( _nodes[i] == n )

      return i;

  }

  ShouldNotReachHere();

  return 0;

}

// Find and remove n from block list

void Block::find_remove( const Node *n ) {

  _nodes.remove(find_node(n));

}

//------------------------------is_Empty---------------------------------------

// Return empty status of a block.  Empty blocks contain only the head, other

// ideal nodes, and an optional trailing goto.

int Block::is_Empty() const {

  // Root or start block is not considered empty

  if (head()->is_Root() || head()->is_Start()) {

    return not_empty;

  }

  int success_result = completely_empty;

  int end_idx = _nodes.size()-1;

  // Check for ending goto

  if ((end_idx > 0) && (_nodes[end_idx]->is_Goto())) {

    success_result = empty_with_goto;

    end_idx--;

  }

  // Unreachable blocks are considered empty

  if (num_preds() <= 1) {

    return success_result;

  }

  // Ideal nodes are allowable in empty blocks: skip them  Only MachNodes

  // turn directly into code, because only MachNodes have non-trivial

  // emit() functions.

  while ((end_idx > 0) && !_nodes[end_idx]->is_Mach()) {

    end_idx--;

  }

  // No room for any interesting instructions?

  if (end_idx == 0) {

    return success_result;

  }

  return not_empty;

}

//------------------------------has_uncommon_code------------------------------

// Return true if the block's code implies that it is likely to be

// executed infrequently.  Check to see if the block ends in a Halt or

// a low probability call.

bool Block::has_uncommon_code() const {

  Node* en = end();

  if (en->is_Goto())

    en = en->in(0);

  if (en->is_Catch())

    en = en->in(0);

  if (en->is_Proj() && en->in(0)->is_MachCall()) {

    MachCallNode* call = en->in(0)->as_MachCall();

    if (call->cnt() != COUNT_UNKNOWN && call->cnt() <= PROB_UNLIKELY_MAG(4)) {

      // This is true for slow-path stubs like new_{instance,array},

      // slow_arraycopy, complete_monitor_locking, uncommon_trap.

      // The magic number corresponds to the probability of an uncommon_trap,

      // even though it is a count not a probability.

      return true;

    }

  }

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

  return op == Op_Halt;

}

//------------------------------is_uncommon------------------------------------

// True if block is low enough frequency or guarded by a test which

// mostly does not go here.

bool Block::is_uncommon( Block_Array &bbs ) const {

  // Initial blocks must never be moved, so are never uncommon.

  if (head()->is_Root() || head()->is_Start())  return false;

  // Check for way-low freq

  if( _freq < BLOCK_FREQUENCY(0.00001f) ) return true;

  // Look for code shape indicating uncommon_trap or slow path

  if (has_uncommon_code()) return true;

  const float epsilon = 0.05f;

  const float guard_factor = PROB_UNLIKELY_MAG(4) / (1.f - epsilon);

  uint uncommon_preds = 0;

  uint freq_preds = 0;

  uint uncommon_for_freq_preds = 0;

  for( uint i=1; i<num_preds(); i++ ) {

    Block* guard = bbs[pred(i)->_idx];

    // Check to see if this block follows its guard 1 time out of 10000

    // or less.

    //

    // See list of magnitude-4 unlikely probabilities in cfgnode.hpp which

    // we intend to be "uncommon", such as slow-path TLE allocation,

    // predicted call failure, and uncommon trap triggers.

    //

    // Use an epsilon value of 5% to allow for variability in frequency

    // predictions and floating point calculations. The net effect is

    // that guard_factor is set to 9500.

    //

    // Ignore low-frequency blocks.

    // The next check is (guard->_freq < 1.e-5 * 9500.).

    if(guard->_freq*BLOCK_FREQUENCY(guard_factor) < BLOCK_FREQUENCY(0.00001f)) {

      uncommon_preds++;

    } else {

      freq_preds++;

      if( _freq < guard->_freq * guard_factor ) {

        uncommon_for_freq_preds++;

      }

    }

  }

  if( num_preds() > 1 &&

      // The block is uncommon if all preds are uncommon or

      (uncommon_preds == (num_preds()-1) ||

      // it is uncommon for all frequent preds.

       uncommon_for_freq_preds == freq_preds) ) {

    return true;

  }

  return false;

}

//------------------------------dump-------------------------------------------

#ifndef PRODUCT

void Block::dump_bidx(const Block* orig) const {

  if (_pre_order) tty->print("B%d",_pre_order);

  else tty->print("N%d", head()->_idx);

  if (Verbose && orig != this) {

    // Dump the original block's idx

    tty->print(" (");

    orig->dump_bidx(orig);

    tty->print(")");

  }

}

void Block::dump_pred(const Block_Array *bbs, Block* orig) const {

  if (is_connector()) {

    for (uint i=1; i<num_preds(); i++) {

      Block *p = ((*bbs)[pred(i)->_idx]);

      p->dump_pred(bbs, orig);

    }

  } else {

    dump_bidx(orig);

    tty->print(" ");

  }

}

void Block::dump_head( const Block_Array *bbs ) const {

  // Print the basic block

  dump_bidx(this);

  tty->print(": #\t");

  // Print the incoming CFG edges and the outgoing CFG edges

  for( uint i=0; i<_num_succs; i++ ) {

    non_connector_successor(i)->dump_bidx(_succs[i]);

    tty->print(" ");

  }

  tty->print("<- ");

  if( head()->is_block_start() ) {

    for (uint i=1; i<num_preds(); i++) {

      Node *s = pred(i);

      if (bbs) {

        Block *p = (*bbs)[s->_idx];

        p->dump_pred(bbs, p);

      } else {

        while (!s->is_block_start())

          s = s->in(0);

        tty->print("N%d ", s->_idx );

      }

    }

  } else

    tty->print("BLOCK HEAD IS JUNK  ");

  // Print loop, if any

  const Block *bhead = this;    // Head of self-loop

  Node *bh = bhead->head();

  if( bbs && bh->is_Loop() && !head()->is_Root() ) {

    LoopNode *loop = bh->as_Loop();

    const Block *bx = (*bbs)[loop->in(LoopNode::LoopBackControl)->_idx];

    while (bx->is_connector()) {

      bx = (*bbs)[bx->pred(1)->_idx];

    }

    tty->print("\tLoop: B%d-B%d ", bhead->_pre_order, bx->_pre_order);

    // Dump any loop-specific bits, especially for CountedLoops.

    loop->dump_spec(tty);

  } else if (has_loop_alignment()) {

    tty->print(" top-of-loop");

  }

  tty->print(" Freq: %g",_freq);

  if( Verbose || WizardMode ) {

    tty->print(" IDom: %d/#%d", _idom ? _idom->_pre_order : 0, _dom_depth);

    tty->print(" RegPressure: %d",_reg_pressure);

    tty->print(" IHRP Index: %d",_ihrp_index);

    tty->print(" FRegPressure: %d",_freg_pressure);

    tty->print(" FHRP Index: %d",_fhrp_index);

  }

  tty->print_cr("");

}

void Block::dump() const { dump(0); }

void Block::dump( const Block_Array *bbs ) const {

  dump_head(bbs);

  uint cnt = _nodes.size();

  for( uint i=0; i<cnt; i++ )

    _nodes[i]->dump();

  tty->print("\n");

}

#endif

//=============================================================================

//------------------------------PhaseCFG---------------------------------------

PhaseCFG::PhaseCFG( Arena *a, RootNode *r, Matcher &m ) :

  Phase(CFG),

  _bbs(a),

  _root(r),

  _node_latency(NULL)

#ifndef PRODUCT

  , _trace_opto_pipelining(TraceOptoPipelining || C->method_has_option("TraceOptoPipelining"))

#endif

#ifdef ASSERT

  , _raw_oops(a)

#endif

{

  ResourceMark rm;

  // I'll need a few machine-specific GotoNodes.  Make an Ideal GotoNode,

  // then Match it into a machine-specific Node.  Then clone the machine

  // Node on demand.

  Node *x = new (C, 1) GotoNode(NULL);

  x->init_req(0, x);

  _goto = m.match_tree(x);

  assert(_goto != NULL, "");

  _goto->set_req(0,_goto);

  // Build the CFG in Reverse Post Order

  _num_blocks = build_cfg();

  _broot = _bbs[_root->_idx];

}

//------------------------------build_cfg--------------------------------------

// Build a proper looking CFG.  Make every block begin with either a StartNode

// or a RegionNode.  Make every block end with either a Goto, If or Return.

// The RootNode both starts and ends it's own block.  Do this with a recursive

// backwards walk over the control edges.

uint PhaseCFG::build_cfg() {

  Arena *a = Thread::current()->resource_area();

  VectorSet visited(a);

  // Allocate stack with enough space to avoid frequent realloc

  Node_Stack nstack(a, C->unique() >> 1);

  nstack.push(_root, 0);

  uint sum = 0;                 // Counter for blocks

  while (nstack.is_nonempty()) {

    // node and in's index from stack's top

    // 'np' is _root (see above) or RegionNode, StartNode: we push on stack

    // only nodes which point to the start of basic block (see below).

    Node *np = nstack.node();

    // idx > 0, except for the first node (_root) pushed on stack

    // at the beginning when idx == 0.

    // We will use the condition (idx == 0) later to end the build.

    uint idx = nstack.index();

    Node *proj = np->in(idx);

    const Node *x = proj->is_block_proj();

    // Does the block end with a proper block-ending Node?  One of Return,

    // If or Goto? (This check should be done for visited nodes also).

    if (x == NULL) {                    // Does not end right...

      Node *g = _goto->clone(); // Force it to end in a Goto

      g->set_req(0, proj);

      np->set_req(idx, g);

      x = proj = g;

    }

    if (!visited.test_set(x->_idx)) { // Visit this block once

      // Skip any control-pinned middle'in stuff

      Node *p = proj;

      do {

        proj = p;                   // Update pointer to last Control

        p = p->in(0);               // Move control forward

      } while( !p->is_block_proj() &&

               !p->is_block_start() );

      // Make the block begin with one of Region or StartNode.

      if( !p->is_block_start() ) {

        RegionNode *r = new (C, 2) RegionNode( 2 );

        r->init_req(1, p);         // Insert RegionNode in the way

        proj->set_req(0, r);        // Insert RegionNode in the way

        p = r;

      }

      // 'p' now points to the start of this basic block

      // Put self in array of basic blocks

      Block *bb = new (_bbs._arena) Block(_bbs._arena,p);

      _bbs.map(p->_idx,bb);

      _bbs.map(x->_idx,bb);

      if( x != p )                  // Only for root is x == p

        bb->_nodes.push((Node*)x);

      // Now handle predecessors

      ++sum;                        // Count 1 for self block

      uint cnt = bb->num_preds();

      for (int i = (cnt - 1); i > 0; i-- ) { // For all predecessors

        Node *prevproj = p->in(i);  // Get prior input

        assert( !prevproj->is_Con(), "dead input not removed" );

        // Check to see if p->in(i) is a "control-dependent" CFG edge -

        // i.e., it splits at the source (via an IF or SWITCH) and merges

        // at the destination (via a many-input Region).

        // This breaks critical edges.  The RegionNode to start the block

        // will be added when <p,i> is pulled off the node stack

        if ( cnt > 2 ) {             // Merging many things?

          assert( prevproj== bb->pred(i),"");

          if(prevproj->is_block_proj() != prevproj) { // Control-dependent edge?

            // Force a block on the control-dependent edge

            Node *g = _goto->clone();       // Force it to end in a Goto

            g->set_req(0,prevproj);

            p->set_req(i,g);

          }

        }

        nstack.push(p, i);  // 'p' is RegionNode or StartNode

      }

    } else { // Post-processing visited nodes

      nstack.pop();                 // remove node from stack

      // Check if it the fist node pushed on stack at the beginning.

      if (idx == 0) break;          // end of the build

      // Find predecessor basic block

      Block *pb = _bbs[x->_idx];

      // Insert into nodes array, if not already there

      if( !_bbs.lookup(proj->_idx) ) {

        assert( x != proj, "" );

        // Map basic block of projection

        _bbs.map(proj->_idx,pb);

        pb->_nodes.push(proj);

      }

      // Insert self as a child of my predecessor block

      pb->_succs.map(pb->_num_succs++, _bbs[np->_idx]);

      assert( pb->_nodes[ pb->_nodes.size() - pb->_num_succs ]->is_block_proj(),

              "too many control users, not a CFG?" );

    }

  }

  // Return number of basic blocks for all children and self

  return sum;

}

//------------------------------insert_goto_at---------------------------------

// Inserts a goto & corresponding basic block between

// block[block_no] and its succ_no'th successor block

void PhaseCFG::insert_goto_at(uint block_no, uint succ_no) {

  // get block with block_no

  assert(block_no < _num_blocks, "illegal block number");

  Block* in  = _blocks[block_no];

  // get successor block succ_no

  assert(succ_no < in->_num_succs, "illegal successor number");

  Block* out = in->_succs[succ_no];

  // Compute frequency of the new block. Do this before inserting

  // new block in case succ_prob() needs to infer the probability from

  // surrounding blocks.

  float freq = in->_freq * in->succ_prob(succ_no);

  // get ProjNode corresponding to the succ_no'th successor of the in block

  ProjNode* proj = in->_nodes[in->_nodes.size() - in->_num_succs + succ_no]->as_Proj();

  // create region for basic block

  RegionNode* region = new (C, 2) RegionNode(2);

  region->init_req(1, proj);

  // setup corresponding basic block

  Block* block = new (_bbs._arena) Block(_bbs._arena, region);

  _bbs.map(region->_idx, block);

  C->regalloc()->set_bad(region->_idx);

  // add a goto node

  Node* gto = _goto->clone(); // get a new goto node

  gto->set_req(0, region);

  // add it to the basic block

  block->_nodes.push(gto);

  _bbs.map(gto->_idx, block);

  C->regalloc()->set_bad(gto->_idx);

  // hook up successor block

  block->_succs.map(block->_num_succs++, out);

  // remap successor's predecessors if necessary