/*

 * 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.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_c1_GraphBuilder.cpp.incl"

class BlockListBuilder VALUE_OBJ_CLASS_SPEC {

 private:

  Compilation* _compilation;

  IRScope*     _scope;

  BlockList    _blocks;                // internal list of all blocks

  BlockList*   _bci2block;             // mapping from bci to blocks for GraphBuilder

  // fields used by mark_loops

  BitMap       _active;                // for iteration of control flow graph

  BitMap       _visited;               // for iteration of control flow graph

  intArray     _loop_map;              // caches the information if a block is contained in a loop

  int          _next_loop_index;       // next free loop number

  int          _next_block_number;     // for reverse postorder numbering of blocks

  // accessors

  Compilation*  compilation() const              { return _compilation; }

  IRScope*      scope() const                    { return _scope; }

  ciMethod*     method() const                   { return scope()->method(); }

  XHandlers*    xhandlers() const                { return scope()->xhandlers(); }

  // unified bailout support

  void          bailout(const char* msg) const   { compilation()->bailout(msg); }

  bool          bailed_out() const               { return compilation()->bailed_out(); }

  // helper functions

  BlockBegin* make_block_at(int bci, BlockBegin* predecessor);

  void handle_exceptions(BlockBegin* current, int cur_bci);

  void handle_jsr(BlockBegin* current, int sr_bci, int next_bci);

  void store_one(BlockBegin* current, int local);

  void store_two(BlockBegin* current, int local);

  void set_entries(int osr_bci);

  void set_leaders();

  void make_loop_header(BlockBegin* block);

  void mark_loops();

  int  mark_loops(BlockBegin* b, bool in_subroutine);

  // debugging

#ifndef PRODUCT

  void print();

#endif

 public:

  // creation

  BlockListBuilder(Compilation* compilation, IRScope* scope, int osr_bci);

  // accessors for GraphBuilder

  BlockList*    bci2block() const                { return _bci2block; }

};

// Implementation of BlockListBuilder

BlockListBuilder::BlockListBuilder(Compilation* compilation, IRScope* scope, int osr_bci)

 : _compilation(compilation)

 , _scope(scope)

 , _blocks(16)

 , _bci2block(new BlockList(scope->method()->code_size(), NULL))

 , _next_block_number(0)

 , _active()         // size not known yet

 , _visited()        // size not known yet

 , _next_loop_index(0)

 , _loop_map() // size not known yet

{

  set_entries(osr_bci);

  set_leaders();

  CHECK_BAILOUT();

  mark_loops();

  NOT_PRODUCT(if (PrintInitialBlockList) print());

#ifndef PRODUCT

  if (PrintCFGToFile) {

    stringStream title;

    title.print("BlockListBuilder ");

    scope->method()->print_name(&title);

    CFGPrinter::print_cfg(_bci2block, title.as_string(), false, false);

  }

#endif

}

void BlockListBuilder::set_entries(int osr_bci) {

  // generate start blocks

  BlockBegin* std_entry = make_block_at(0, NULL);

  if (scope()->caller() == NULL) {

    std_entry->set(BlockBegin::std_entry_flag);

  }

  if (osr_bci != -1) {

    BlockBegin* osr_entry = make_block_at(osr_bci, NULL);

    osr_entry->set(BlockBegin::osr_entry_flag);

  }

  // generate exception entry blocks

  XHandlers* list = xhandlers();

  const int n = list->length();

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

    XHandler* h = list->handler_at(i);

    BlockBegin* entry = make_block_at(h->handler_bci(), NULL);

    entry->set(BlockBegin::exception_entry_flag);

    h->set_entry_block(entry);

  }

}

BlockBegin* BlockListBuilder::make_block_at(int cur_bci, BlockBegin* predecessor) {

  assert(method()->bci_block_start().at(cur_bci), "wrong block starts of MethodLivenessAnalyzer");

  BlockBegin* block = _bci2block->at(cur_bci);

  if (block == NULL) {

    block = new BlockBegin(cur_bci);

    block->init_stores_to_locals(method()->max_locals());

    _bci2block->at_put(cur_bci, block);

    _blocks.append(block);

    assert(predecessor == NULL || predecessor->bci() < cur_bci, "targets for backward branches must already exist");

  }

  if (predecessor != NULL) {

    if (block->is_set(BlockBegin::exception_entry_flag)) {

      BAILOUT_("Exception handler can be reached by both normal and exceptional control flow", block);

    }

    predecessor->add_successor(block);

    block->increment_total_preds();

  }

  return block;

}

inline void BlockListBuilder::store_one(BlockBegin* current, int local) {

  current->stores_to_locals().set_bit(local);

}

inline void BlockListBuilder::store_two(BlockBegin* current, int local) {

  store_one(current, local);

  store_one(current, local + 1);

}

void BlockListBuilder::handle_exceptions(BlockBegin* current, int cur_bci) {

  // Draws edges from a block to its exception handlers

  XHandlers* list = xhandlers();

  const int n = list->length();

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

    XHandler* h = list->handler_at(i);

    if (h->covers(cur_bci)) {

      BlockBegin* entry = h->entry_block();

      assert(entry != NULL && entry == _bci2block->at(h->handler_bci()), "entry must be set");

      assert(entry->is_set(BlockBegin::exception_entry_flag), "flag must be set");

      // add each exception handler only once

      if (!current->is_successor(entry)) {

        current->add_successor(entry);

        entry->increment_total_preds();

      }

      // stop when reaching catchall

      if (h->catch_type() == 0) break;

    }

  }

}

void BlockListBuilder::handle_jsr(BlockBegin* current, int sr_bci, int next_bci) {

  // start a new block after jsr-bytecode and link this block into cfg

  make_block_at(next_bci, current);

  // start a new block at the subroutine entry at mark it with special flag

  BlockBegin* sr_block = make_block_at(sr_bci, current);

  if (!sr_block->is_set(BlockBegin::subroutine_entry_flag)) {

    sr_block->set(BlockBegin::subroutine_entry_flag);

  }

}

void BlockListBuilder::set_leaders() {

  bool has_xhandlers = xhandlers()->has_handlers();

  BlockBegin* current = NULL;

  // The information which bci starts a new block simplifies the analysis

  // Without it, backward branches could jump to a bci where no block was created

  // during bytecode iteration. This would require the creation of a new block at the

  // branch target and a modification of the successor lists.

  BitMap bci_block_start = method()->bci_block_start();

  ciBytecodeStream s(method());

  while (s.next() != ciBytecodeStream::EOBC()) {

    int cur_bci = s.cur_bci();

    if (bci_block_start.at(cur_bci)) {

      current = make_block_at(cur_bci, current);

    }

    assert(current != NULL, "must have current block");

    if (has_xhandlers && GraphBuilder::can_trap(method(), s.cur_bc())) {

      handle_exceptions(current, cur_bci);

    }

    switch (s.cur_bc()) {

      // track stores to local variables for selective creation of phi functions

      case Bytecodes::_iinc:     store_one(current, s.get_index()); break;

      case Bytecodes::_istore:   store_one(current, s.get_index()); break;

      case Bytecodes::_lstore:   store_two(current, s.get_index()); break;

      case Bytecodes::_fstore:   store_one(current, s.get_index()); break;

      case Bytecodes::_dstore:   store_two(current, s.get_index()); break;

      case Bytecodes::_astore:   store_one(current, s.get_index()); break;

      case Bytecodes::_istore_0: store_one(current, 0); break;

      case Bytecodes::_istore_1: store_one(current, 1); break;

      case Bytecodes::_istore_2: store_one(current, 2); break;

      case Bytecodes::_istore_3: store_one(current, 3); break;

      case Bytecodes::_lstore_0: store_two(current, 0); break;

      case Bytecodes::_lstore_1: store_two(current, 1); break;

      case Bytecodes::_lstore_2: store_two(current, 2); break;

      case Bytecodes::_lstore_3: store_two(current, 3); break;

      case Bytecodes::_fstore_0: store_one(current, 0); break;

      case Bytecodes::_fstore_1: store_one(current, 1); break;

      case Bytecodes::_fstore_2: store_one(current, 2); break;

      case Bytecodes::_fstore_3: store_one(current, 3); break;

      case Bytecodes::_dstore_0: store_two(current, 0); break;

      case Bytecodes::_dstore_1: store_two(current, 1); break;

      case Bytecodes::_dstore_2: store_two(current, 2); break;

      case Bytecodes::_dstore_3: store_two(current, 3); break;

      case Bytecodes::_astore_0: store_one(current, 0); break;

      case Bytecodes::_astore_1: store_one(current, 1); break;

      case Bytecodes::_astore_2: store_one(current, 2); break;

      case Bytecodes::_astore_3: store_one(current, 3); break;

      // track bytecodes that affect the control flow

      case Bytecodes::_athrow:  // fall through

      case Bytecodes::_ret:     // fall through

      case Bytecodes::_ireturn: // fall through

      case Bytecodes::_lreturn: // fall through

      case Bytecodes::_freturn: // fall through

      case Bytecodes::_dreturn: // fall through

      case Bytecodes::_areturn: // fall through

      case Bytecodes::_return:

        current = NULL;

        break;

      case Bytecodes::_ifeq:      // fall through

      case Bytecodes::_ifne:      // fall through

      case Bytecodes::_iflt:      // fall through

      case Bytecodes::_ifge:      // fall through

      case Bytecodes::_ifgt:      // fall through

      case Bytecodes::_ifle:      // fall through

      case Bytecodes::_if_icmpeq: // fall through

      case Bytecodes::_if_icmpne: // fall through

      case Bytecodes::_if_icmplt: // fall through

      case Bytecodes::_if_icmpge: // fall through

      case Bytecodes::_if_icmpgt: // fall through

      case Bytecodes::_if_icmple: // fall through

      case Bytecodes::_if_acmpeq: // fall through

      case Bytecodes::_if_acmpne: // fall through

      case Bytecodes::_ifnull:    // fall through

      case Bytecodes::_ifnonnull:

        make_block_at(s.next_bci(), current);

        make_block_at(s.get_dest(), current);

        current = NULL;

        break;

      case Bytecodes::_goto:

        make_block_at(s.get_dest(), current);

        current = NULL;

        break;

      case Bytecodes::_goto_w:

        make_block_at(s.get_far_dest(), current);

        current = NULL;

        break;

      case Bytecodes::_jsr:

        handle_jsr(current, s.get_dest(), s.next_bci());

        current = NULL;

        break;

      case Bytecodes::_jsr_w:

        handle_jsr(current, s.get_far_dest(), s.next_bci());

        current = NULL;

        break;

      case Bytecodes::_tableswitch: {

        // set block for each case

        Bytecode_tableswitch *switch_ = Bytecode_tableswitch_at(s.cur_bcp());

        int l = switch_->length();

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

          make_block_at(cur_bci + switch_->dest_offset_at(i), current);

        }

        make_block_at(cur_bci + switch_->default_offset(), current);

        current = NULL;

        break;

      }

      case Bytecodes::_lookupswitch: {

        // set block for each case

        Bytecode_lookupswitch *switch_ = Bytecode_lookupswitch_at(s.cur_bcp());

        int l = switch_->number_of_pairs();

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

          make_block_at(cur_bci + switch_->pair_at(i)->offset(), current);

        }

        make_block_at(cur_bci + switch_->default_offset(), current);

        current = NULL;

        break;

      }

    }

  }

}

void BlockListBuilder::mark_loops() {

  ResourceMark rm;

  _active = BitMap(BlockBegin::number_of_blocks());         _active.clear();

  _visited = BitMap(BlockBegin::number_of_blocks());        _visited.clear();

  _loop_map = intArray(BlockBegin::number_of_blocks(), 0);

  _next_loop_index = 0;

  _next_block_number = _blocks.length();

  // recursively iterate the control flow graph

  mark_loops(_bci2block->at(0), false);

  assert(_next_block_number >= 0, "invalid block numbers");

}

void BlockListBuilder::make_loop_header(BlockBegin* block) {

  if (block->is_set(BlockBegin::exception_entry_flag)) {

    // exception edges may look like loops but don't mark them as such

    // since it screws up block ordering.

    return;

  }

  if (!block->is_set(BlockBegin::parser_loop_header_flag)) {

    block->set(BlockBegin::parser_loop_header_flag);

    assert(_loop_map.at(block->block_id()) == 0, "must not be set yet");

    assert(0 <= _next_loop_index && _next_loop_index < BitsPerInt, "_next_loop_index is used as a bit-index in integer");

    _loop_map.at_put(block->block_id(), 1 << _next_loop_index);

    if (_next_loop_index < 31) _next_loop_index++;

  } else {

    // block already marked as loop header

    assert(is_power_of_2((unsigned int)_loop_map.at(block->block_id())), "exactly one bit must be set");

  }

}

int BlockListBuilder::mark_loops(BlockBegin* block, bool in_subroutine) {

  int block_id = block->block_id();

  if (_visited.at(block_id)) {

    if (_active.at(block_id)) {

      // reached block via backward branch

      make_loop_header(block);

    }

    // return cached loop information for this block

    return _loop_map.at(block_id);

  }

  if (block->is_set(BlockBegin::subroutine_entry_flag)) {

    in_subroutine = true;

  }

  // set active and visited bits before successors are processed

  _visited.set_bit(block_id);

  _active.set_bit(block_id);

  intptr_t loop_state = 0;

  for (int i = block->number_of_sux() - 1; i >= 0; i--) {

    // recursively process all successors

    loop_state |= mark_loops(block->sux_at(i), in_subroutine);

  }

  // clear active-bit after all successors are processed

  _active.clear_bit(block_id);

  // reverse-post-order numbering of all blocks

  block->set_depth_first_number(_next_block_number);

  _next_block_number--;

  if (loop_state != 0 || in_subroutine ) {

    // block is contained at least in one loop, so phi functions are necessary

    // phi functions are also necessary for all locals stored in a subroutine

    scope()->requires_phi_function().set_union(block->stores_to_locals());

  }

  if (block->is_set(BlockBegin::parser_loop_header_flag)) {

    int header_loop_state = _loop_map.at(block_id);

    assert(is_power_of_2((unsigned)header_loop_state), "exactly one bit must be set");

    // If the highest bit is set (i.e. when integer value is negative), the method

    // has 32 or more loops. This bit is never cleared because it is used for multiple loops

    if (header_loop_state >= 0) {

      clear_bits(loop_state, header_loop_state);

    }

  }

  // cache and return loop information for this block

  _loop_map.at_put(block_id, loop_state);

  return loop_state;

}

#ifndef PRODUCT

int compare_depth_first(BlockBegin** a, BlockBegin** b) {

  return (*a)->depth_first_number() - (*b)->depth_first_number();

}

void BlockListBuilder::print() {

  tty->print("----- initial block list of BlockListBuilder for method ");

  method()->print_short_name();

  tty->cr();

  // better readability if blocks are sorted in processing order

  _blocks.sort(compare_depth_first);

  for (int i = 0; i < _blocks.length(); i++) {

    BlockBegin* cur = _blocks.at(i);

    tty->print("%4d: B%-4d bci: %-4d  preds: %-4d ", cur->depth_first_number(), cur->block_id(), cur->bci(), cur->total_preds());

    tty->print(cur->is_set(BlockBegin::std_entry_flag)               ? " std" : "    ");

    tty->print(cur->is_set(BlockBegin::osr_entry_flag)               ? " osr" : "    ");

    tty->print(cur->is_set(BlockBegin::exception_entry_flag)         ? " ex" : "   ");

    tty->print(cur->is_set(BlockBegin::subroutine_entry_flag)        ? " sr" : "   ");

    tty->print(cur->is_set(BlockBegin::parser_loop_header_flag)      ? " lh" : "   ");

    if (cur->number_of_sux() > 0) {

      tty->print("    sux: ");

      for (int j = 0; j < cur->number_of_sux(); j++) {

        BlockBegin* sux = cur->sux_at(j);

        tty->print("B%d ", sux->block_id());

      }

    }

    tty->cr();

  }

}

#endif

// A simple growable array of Values indexed by ciFields

class FieldBuffer: public CompilationResourceObj {

 private:

  GrowableArray<Value> _values;

 public:

  FieldBuffer() {}

  void kill() {

    _values.trunc_to(0);

  }

  Value at(ciField* field) {

    assert(field->holder()->is_loaded(), "must be a loaded field");

    int offset = field->offset();

    if (offset < _values.length()) {

      return _values.at(offset);

    } else {

      return NULL;

    }

  }

  void at_put(ciField* field, Value value) {

    assert(field->holder()->is_loaded(), "must be a loaded field");

    int offset = field->offset();

    _values.at_put_grow(offset, value, NULL);

  }

};

// MemoryBuffer is fairly simple model of the current state of memory.

// It partitions memory into several pieces.  The first piece is

// generic memory where little is known about the owner of the memory.

// This is conceptually represented by the tuple <O, F, V> which says

// that the field F of object O has value V.  This is flattened so

// that F is represented by the offset of the field and the parallel

// arrays _objects and _values are used for O and V.  Loads of O.F can

// simply use V.  Newly allocated objects are kept in a separate list

// along with a parallel array for each object which represents the

// current value of its fields.  Stores of the default value to fields

// which have never been stored to before are eliminated since they

// are redundant.  Once newly allocated objects are stored into

// another object or they are passed out of the current compile they

// are treated like generic memory.

class MemoryBuffer: public CompilationResourceObj {

 private:

  FieldBuffer                 _values;

  GrowableArray<Value>        _objects;

  GrowableArray<Value>        _newobjects;

  GrowableArray<FieldBuffer*> _fields;

 public:

  MemoryBuffer() {}

  StoreField* store(StoreField* st) {

    if (!EliminateFieldAccess) {

      return st;

    }

    Value object = st->obj();

    Value value = st->value();