/*

 * 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/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"

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 relocInfo::addr_unit(); // no particular alignment

}

uint Block::compute_loop_alignment() {

  Node *h = head();

  int unit_sz = relocInfo::addr_unit();

  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*unit_sz) ? (OptoLoopAlignment>>2) : unit_sz;

    }

    // 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 unit_sz; // Loop does not loop, more often than not!

    }

    return OptoLoopAlignment; // Otherwise align loop head

  }

  return unit_sz; // 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 = number_of_nodes();

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

    uint inst_size = get_node(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 < number_of_nodes(); i++ ) {

    if( get_node(i) == n )

      return i;

  }

  ShouldNotReachHere();

  return 0;

}

// Find and remove n from block list

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

  remove_node(find_node(n));

}

bool Block::contains(const Node *n) const {

  return _nodes.contains(n);

}

// 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 = number_of_nodes() - 1;

  // Check for ending goto

  if ((end_idx > 0) && (get_node(end_idx)->is_MachGoto())) {

    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) && !get_node(end_idx)->is_Mach()) {

    end_idx--;

  }

  // No room for any interesting instructions?

  if (end_idx == 0) {

    return success_result;

  }

  return not_empty;

}

// 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_MachGoto())

    en = en->in(0);

  if (en->is_Catch())

    en = en->in(0);

  if (en->is_MachProj() && 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;

}

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

// mostly does not go here.

bool PhaseCFG::is_uncommon(const Block* block) {

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

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

  // Check for way-low freq

  if(block->_freq < BLOCK_FREQUENCY(0.00001f) ) return true;

  // Look for code shape indicating uncommon_trap or slow path

  if (block->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< block->num_preds(); i++ ) {

    Block* guard = get_block_for_node(block->pred(i));

    // 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(block->_freq < guard->_freq * guard_factor ) {

        uncommon_for_freq_preds++;

      }

    }

  }

  if( block->num_preds() > 1 &&

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

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

      // it is uncommon for all frequent preds.

       uncommon_for_freq_preds == freq_preds) ) {

    return true;

  }

  return false;

}

#ifndef PRODUCT

void Block::dump_bidx(const Block* orig, outputStream* st) const {

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

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

  if (Verbose && orig != this) {

    // Dump the original block's idx

    st->print(" (");

    orig->dump_bidx(orig, st);

    st->print(")");

  }

}

void Block::dump_pred(const PhaseCFG* cfg, Block* orig, outputStream* st) const {

  if (is_connector()) {

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

      Block *p = cfg->get_block_for_node(pred(i));

      p->dump_pred(cfg, orig, st);

    }

  } else {

    dump_bidx(orig, st);

    st->print(" ");

  }

}

void Block::dump_head(const PhaseCFG* cfg, outputStream* st) const {

  // Print the basic block

  dump_bidx(this, st);

  st->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], st);

    st->print(" ");

  }

  st->print("<- ");

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

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

      Node *s = pred(i);

      if (cfg != NULL) {

        Block *p = cfg->get_block_for_node(s);

        p->dump_pred(cfg, p, st);

      } else {

        while (!s->is_block_start())

          s = s->in(0);

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

      }

    }

  } else {

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

  }

  // Print loop, if any

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

  Node *bh = bhead->head();

  if ((cfg != NULL) && bh->is_Loop() && !head()->is_Root()) {

    LoopNode *loop = bh->as_Loop();

    const Block *bx = cfg->get_block_for_node(loop->in(LoopNode::LoopBackControl));

    while (bx->is_connector()) {

      bx = cfg->get_block_for_node(bx->pred(1));

    }

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

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

    loop->dump_spec(st);

  } else if (has_loop_alignment()) {

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

  }

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

  if( Verbose || WizardMode ) {

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

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

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

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

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

  }

  st->cr();

}

void Block::dump() const {

  dump(NULL);

}

void Block::dump(const PhaseCFG* cfg) const {

  dump_head(cfg);

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

    get_node(i)->dump();

  }

  tty->print("\n");

}

#endif

PhaseCFG::PhaseCFG(Arena* arena, RootNode* root, Matcher& matcher)

: Phase(CFG)

, _block_arena(arena)

, _regalloc(NULL)

, _scheduling_for_pressure(false)

, _root(root)

, _matcher(matcher)

, _node_to_block_mapping(arena)

, _node_latency(NULL)

#ifndef PRODUCT

#endif

#ifdef ASSERT

, _raw_oops(arena)

#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 GotoNode(NULL);

  x->init_req(0, x);

  _goto = matcher.match_tree(x);

  assert(_goto != NULL, "");

  _goto->set_req(0,_goto);

  // Build the CFG in Reverse Post Order

  _number_of_blocks = build_cfg();

  _root_block = get_block_for_node(_root);

}

// 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->live_nodes() >> 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 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 (_block_arena) Block(_block_arena, p);

      map_node_to_block(p, bb);

      map_node_to_block(x, bb);

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

        bb->push_node((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 = get_block_for_node(x);

      // Insert into nodes array, if not already there

      if (!has_block(proj)) {

        assert( x != proj, "" );

        // Map basic block of projection

        map_node_to_block(proj, pb);

        pb->push_node(proj);

      }

      // Insert self as a child of my predecessor block

      pb->_succs.map(pb->_num_succs++, get_block_for_node(np));

      assert( pb->get_node(pb->number_of_nodes() - 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;

}

// 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 < number_of_blocks(), "illegal block number");

  Block* in  = get_block(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->get_node(in->number_of_nodes() - in->_num_succs + succ_no)->as_Proj();

  // create region for basic block

  RegionNode* region = new RegionNode(2);