/*

 * Copyright 1999-2006 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.

 *

 */

# include "incls/_precompiled.incl"

# include "incls/_c1_IR.cpp.incl"

// Implementation of XHandlers

//

// Note: This code could eventually go away if we are

//       just using the ciExceptionHandlerStream.

XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) {

  ciExceptionHandlerStream s(method);

  while (!s.is_done()) {

    _list.append(new XHandler(s.handler()));

    s.next();

  }

  assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent");

}

// deep copy of all XHandler contained in list

XHandlers::XHandlers(XHandlers* other) :

  _list(other->length())

{

  for (int i = 0; i < other->length(); i++) {

    _list.append(new XHandler(other->handler_at(i)));

  }

}

// Returns whether a particular exception type can be caught.  Also

// returns true if klass is unloaded or any exception handler

// classes are unloaded.  type_is_exact indicates whether the throw

// is known to be exactly that class or it might throw a subtype.

bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const {

  // the type is unknown so be conservative

  if (!klass->is_loaded()) {

    return true;

  }

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

    XHandler* handler = handler_at(i);

    if (handler->is_catch_all()) {

      // catch of ANY

      return true;

    }

    ciInstanceKlass* handler_klass = handler->catch_klass();

    // if it's unknown it might be catchable

    if (!handler_klass->is_loaded()) {

      return true;

    }

    // if the throw type is definitely a subtype of the catch type

    // then it can be caught.

    if (klass->is_subtype_of(handler_klass)) {

      return true;

    }

    if (!type_is_exact) {

      // If the type isn't exactly known then it can also be caught by

      // catch statements where the inexact type is a subtype of the

      // catch type.

      // given: foo extends bar extends Exception

      // throw bar can be caught by catch foo, catch bar, and catch

      // Exception, however it can't be caught by any handlers without

      // bar in its type hierarchy.

      if (handler_klass->is_subtype_of(klass)) {

        return true;

      }

    }

  }

  return false;

}

bool XHandlers::equals(XHandlers* others) const {

  if (others == NULL) return false;

  if (length() != others->length()) return false;

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

    if (!handler_at(i)->equals(others->handler_at(i))) return false;

  }

  return true;

}

bool XHandler::equals(XHandler* other) const {

  assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco");

  if (entry_pco() != other->entry_pco()) return false;

  if (scope_count() != other->scope_count()) return false;

  if (_desc != other->_desc) return false;

  assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal");

  return true;

}

// Implementation of IRScope

BlockBegin* IRScope::header_block(BlockBegin* entry, BlockBegin::Flag f, ValueStack* state) {

  if (entry == NULL) return NULL;

  assert(entry->is_set(f), "entry/flag mismatch");

  // create header block

  BlockBegin* h = new BlockBegin(entry->bci());

  BlockEnd* g = new Goto(entry, false);

  h->set_next(g, entry->bci());

  h->set_end(g);

  h->set(f);

  // setup header block end state

  ValueStack* s = state->copy(); // can use copy since stack is empty (=> no phis)

  assert(s->stack_is_empty(), "must have empty stack at entry point");

  g->set_state(s);

  return h;

}

BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) {

  GraphBuilder gm(compilation, this);

  NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats());

  if (compilation->bailed_out()) return NULL;

  return gm.start();

}

IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph)

: _callees(2)

, _compilation(compilation)

, _lock_stack_size(-1)

, _requires_phi_function(method->max_locals())

{

  _caller             = caller;

  _caller_bci         = caller == NULL ? -1 : caller_bci;

  _caller_state       = NULL; // Must be set later if needed

  _level              = caller == NULL ?  0 : caller->level() + 1;

  _method             = method;

  _xhandlers          = new XHandlers(method);

  _number_of_locks    = 0;

  _monitor_pairing_ok = method->has_balanced_monitors();

  _start              = NULL;

  if (osr_bci == -1) {

    _requires_phi_function.clear();

  } else {

        // selective creation of phi functions is not possibel in osr-methods

    _requires_phi_function.set_range(0, method->max_locals());

  }

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

  // build graph if monitor pairing is ok

  if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci);

}

int IRScope::max_stack() const {

  int my_max = method()->max_stack();

  int callee_max = 0;

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

    callee_max = MAX2(callee_max, callee_no(i)->max_stack());

  }

  return my_max + callee_max;

}

void IRScope::compute_lock_stack_size() {

  if (!InlineMethodsWithExceptionHandlers) {

    _lock_stack_size = 0;

    return;

  }

  // Figure out whether we have to preserve expression stack elements

  // for parent scopes, and if so, how many

  IRScope* cur_scope = this;

  while (cur_scope != NULL && !cur_scope->xhandlers()->has_handlers()) {

    cur_scope = cur_scope->caller();

  }

  _lock_stack_size = (cur_scope == NULL ? 0 :

                      (cur_scope->caller_state() == NULL ? 0 :

                       cur_scope->caller_state()->stack_size()));

}

int IRScope::top_scope_bci() const {

  assert(!is_top_scope(), "no correct answer for top scope possible");

  const IRScope* scope = this;

  while (!scope->caller()->is_top_scope()) {

    scope = scope->caller();

  }

  return scope->caller_bci();

}

// Implementation of CodeEmitInfo

// Stack must be NON-null

CodeEmitInfo::CodeEmitInfo(int bci, ValueStack* stack, XHandlers* exception_handlers)

  : _scope(stack->scope())

  , _bci(bci)

  , _scope_debug_info(NULL)

  , _oop_map(NULL)

  , _stack(stack)

  , _exception_handlers(exception_handlers)

  , _next(NULL)

  , _id(-1) {

  assert(_stack != NULL, "must be non null");

  assert(_bci == SynchronizationEntryBCI || Bytecodes::is_defined(scope()->method()->java_code_at_bci(_bci)), "make sure bci points at a real bytecode");

}

CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, bool lock_stack_only)

  : _scope(info->_scope)

  , _exception_handlers(NULL)

  , _bci(info->_bci)

  , _scope_debug_info(NULL)

  , _oop_map(NULL) {

  if (lock_stack_only) {

    if (info->_stack != NULL) {

      _stack = info->_stack->copy_locks();

    } else {

      _stack = NULL;

    }

  } else {

    _stack = info->_stack;

  }

  // deep copy of exception handlers

  if (info->_exception_handlers != NULL) {

    _exception_handlers = new XHandlers(info->_exception_handlers);

  }

}

void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) {

  // record the safepoint before recording the debug info for enclosing scopes

  recorder->add_safepoint(pc_offset, _oop_map->deep_copy());

  _scope_debug_info->record_debug_info(recorder, pc_offset);

  recorder->end_safepoint(pc_offset);

}

void CodeEmitInfo::add_register_oop(LIR_Opr opr) {

  assert(_oop_map != NULL, "oop map must already exist");

  assert(opr->is_single_cpu(), "should not call otherwise");

  int frame_size = frame_map()->framesize();

  int arg_count = frame_map()->oop_map_arg_count();

  VMReg name = frame_map()->regname(opr);

  _oop_map->set_oop(name);

}

// Implementation of IR

IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) :

    _locals_size(in_WordSize(-1))

  , _num_loops(0) {

  // initialize data structures

  ValueType::initialize();

  Instruction::initialize();

  BlockBegin::initialize();

  GraphBuilder::initialize();

  // setup IR fields

  _compilation = compilation;

  _top_scope   = new IRScope(compilation, NULL, -1, method, osr_bci, true);

  _code        = NULL;

}

void IR::optimize() {

  Optimizer opt(this);

  if (DoCEE) {

    opt.eliminate_conditional_expressions();

#ifndef PRODUCT

    if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); }

    if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); }

#endif

  }

  if (EliminateBlocks) {

    opt.eliminate_blocks();

#ifndef PRODUCT

    if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); }

    if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); }

#endif

  }

  if (EliminateNullChecks) {

    opt.eliminate_null_checks();

#ifndef PRODUCT

    if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); }

    if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); }

#endif

  }

}

static int sort_pairs(BlockPair** a, BlockPair** b) {

  if ((*a)->from() == (*b)->from()) {

    return (*a)->to()->block_id() - (*b)->to()->block_id();

  } else {

    return (*a)->from()->block_id() - (*b)->from()->block_id();

  }

}

class CriticalEdgeFinder: public BlockClosure {

  BlockPairList blocks;

  IR*       _ir;

 public:

  CriticalEdgeFinder(IR* ir): _ir(ir) {}

  void block_do(BlockBegin* bb) {

    BlockEnd* be = bb->end();

    int nos = be->number_of_sux();

    if (nos >= 2) {

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

        BlockBegin* sux = be->sux_at(i);

        if (sux->number_of_preds() >= 2) {

          blocks.append(new BlockPair(bb, sux));

        }

      }

    }

  }

  void split_edges() {

    BlockPair* last_pair = NULL;

    blocks.sort(sort_pairs);

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

      BlockPair* pair = blocks.at(i);

      if (last_pair != NULL && pair->is_same(last_pair)) continue;

      BlockBegin* from = pair->from();

      BlockBegin* to = pair->to();

      BlockBegin* split = from->insert_block_between(to);

#ifndef PRODUCT

      if ((PrintIR || PrintIR1) && Verbose) {

        tty->print_cr("Split critical edge B%d -> B%d (new block B%d)",

                      from->block_id(), to->block_id(), split->block_id());

      }

#endif

      last_pair = pair;

    }

  }

};

void IR::split_critical_edges() {

  CriticalEdgeFinder cef(this);

  iterate_preorder(&cef);

  cef.split_edges();

}

class UseCountComputer: public AllStatic {

 private:

  static void update_use_count(Value* n) {

    // Local instructions and Phis for expression stack values at the

    // start of basic blocks are not added to the instruction list

    if ((*n)->bci() == -99 && (*n)->as_Local() == NULL &&

        (*n)->as_Phi() == NULL) {

      assert(false, "a node was not appended to the graph");

      Compilation::current_compilation()->bailout("a node was not appended to the graph");

    }

    // use n's input if not visited before

    if (!(*n)->is_pinned() && !(*n)->has_uses()) {

      // note: a) if the instruction is pinned, it will be handled by compute_use_count

      //       b) if the instruction has uses, it was touched before

      //       => in both cases we don't need to update n's values

      uses_do(n);

    }

    // use n

    (*n)->_use_count++;

  }

  static Values* worklist;

  static int depth;

  enum {

    max_recurse_depth = 20

  };

  static void uses_do(Value* n) {

    depth++;

    if (depth > max_recurse_depth) {

      // don't allow the traversal to recurse too deeply

      worklist->push(*n);

    } else {

      (*n)->input_values_do(update_use_count);

      // special handling for some instructions

      if ((*n)->as_BlockEnd() != NULL) {

        // note on BlockEnd:

        //   must 'use' the stack only if the method doesn't

        //   terminate, however, in those cases stack is empty

        (*n)->state_values_do(update_use_count);

      }

    }

    depth--;

  }

  static void basic_compute_use_count(BlockBegin* b) {

    depth = 0;

    // process all pinned nodes as the roots of expression trees

    for (Instruction* n = b; n != NULL; n = n->next()) {

      if (n->is_pinned()) uses_do(&n);

    }

    assert(depth == 0, "should have counted back down");

    // now process any unpinned nodes which recursed too deeply

    while (worklist->length() > 0) {

      Value t = worklist->pop();

      if (!t->is_pinned()) {

        // compute the use count

        uses_do(&t);

        // pin the instruction so that LIRGenerator doesn't recurse

        // too deeply during it's evaluation.

        t->pin();

      }

    }

    assert(depth == 0, "should have counted back down");

  }

 public:

  static void compute(BlockList* blocks) {

    worklist = new Values();

    blocks->blocks_do(basic_compute_use_count);

    worklist = NULL;

  }

};

Values* UseCountComputer::worklist = NULL;

int UseCountComputer::depth = 0;

// helper macro for short definition of trace-output inside code

#ifndef PRODUCT

  #define TRACE_LINEAR_SCAN(level, code)       \

    if (TraceLinearScanLevel >= level) {       \

      code;                                    \

    }

#else

  #define TRACE_LINEAR_SCAN(level, code)

#endif

class ComputeLinearScanOrder : public StackObj {

 private:

  int        _max_block_id;        // the highest block_id of a block

  int        _num_blocks;          // total number of blocks (smaller than _max_block_id)

  int        _num_loops;           // total number of loops

  bool       _iterative_dominators;// method requires iterative computation of dominatiors

  BlockList* _linear_scan_order;   // the resulting list of blocks in correct order

  BitMap     _visited_blocks;      // used for recursive processing of blocks

  BitMap     _active_blocks;       // used for recursive processing of blocks

  BitMap     _dominator_blocks;    // temproary BitMap used for computation of dominator

  intArray   _forward_branches;    // number of incoming forward branches for each block

  BlockList  _loop_end_blocks;     // list of all loop end blocks collected during count_edges

  BitMap2D   _loop_map;            // two-dimensional bit set: a bit is set if a block is contained in a loop

  BlockList  _work_list;           // temporary list (used in mark_loops and compute_order)

  // accessors for _visited_blocks and _active_blocks

  void init_visited()                     { _active_blocks.clear(); _visited_blocks.clear(); }

  bool is_visited(BlockBegin* b) const    { return _visited_blocks.at(b->block_id()); }

  bool is_active(BlockBegin* b) const     { return _active_blocks.at(b->block_id()); }

  void set_visited(BlockBegin* b)         { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); }

  void set_active(BlockBegin* b)          { assert(!is_active(b), "already set");  _active_blocks.set_bit(b->block_id()); }

  void clear_active(BlockBegin* b)        { assert(is_active(b), "not already");   _active_blocks.clear_bit(b->block_id()); }

  // accessors for _forward_branches

  void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); }

  int  dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); }

  // accessors for _loop_map

  bool is_block_in_loop   (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); }

  void set_block_in_loop  (int loop_idx, BlockBegin* b)       { _loop_map.set_bit(loop_idx, b->block_id()); }

  void clear_block_in_loop(int loop_idx, int block_id)        { _loop_map.clear_bit(loop_idx, block_id); }

  // count edges between blocks

  void count_edges(BlockBegin* cur, BlockBegin* parent);

  // loop detection

  void mark_loops();

  void clear_non_natural_loops(BlockBegin* start_block);

  void assign_loop_depth(BlockBegin* start_block);

  // computation of final block order

  BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b);

  void compute_dominator(BlockBegin* cur, BlockBegin* parent);

  int  compute_weight(BlockBegin* cur);

  bool ready_for_processing(BlockBegin* cur);

  void sort_into_work_list(BlockBegin* b);

  void append_block(BlockBegin* cur);

  void compute_order(BlockBegin* start_block);

  // fixup of dominators for non-natural loops

  bool compute_dominators_iter();

  void compute_dominators();

  // debug functions

  NOT_PRODUCT(void print_blocks();)

  DEBUG_ONLY(void verify();)

 public:

  ComputeLinearScanOrder(BlockBegin* start_block);

  // accessors for final result

  BlockList* linear_scan_order() const    { return _linear_scan_order; }

  int        num_loops() const            { return _num_loops; }

};