/*

 * Copyright (c) 1999, 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 "c1/c1_Compilation.hpp"

#include "c1/c1_FrameMap.hpp"

#include "c1/c1_GraphBuilder.hpp"

#include "c1/c1_IR.hpp"

#include "c1/c1_InstructionPrinter.hpp"

#include "c1/c1_Optimizer.hpp"

#include "utilities/bitMap.inline.hpp"

// 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::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)

, _requires_phi_function(method->max_locals())

{

  _caller             = caller;

  _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;

}

bool IRScopeDebugInfo::should_reexecute() {

  ciMethod* cur_method = scope()->method();

  int       cur_bci    = bci();

  if (cur_method != NULL && cur_bci != SynchronizationEntryBCI) {

    Bytecodes::Code code = cur_method->java_code_at_bci(cur_bci);

    return Interpreter::bytecode_should_reexecute(code);

  } else

    return false;

}

// Implementation of CodeEmitInfo

// Stack must be NON-null

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

  : _scope(stack->scope())

  , _scope_debug_info(NULL)

  , _oop_map(NULL)

  , _stack(stack)

  , _exception_handlers(exception_handlers)

  , _is_method_handle_invoke(false) {

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

}

CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack)

  : _scope(info->_scope)

  , _exception_handlers(NULL)

  , _scope_debug_info(NULL)

  , _oop_map(NULL)

  , _stack(stack == NULL ? info->_stack : stack)

  , _is_method_handle_invoke(info->_is_method_handle_invoke) {

  // 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, true/*topmost*/, _is_method_handle_invoke);

  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");

  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) {

  // 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 (!compilation()->profile_branches()) {

    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 ValueVisitor, BlockClosure {

 private:

  void visit(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)->is_linked() && (*n)->can_be_linked()) {

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

      Compilation::current()->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++;

  }

  Values* worklist;

  int depth;

  enum {

    max_recurse_depth = 20

  };

  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(this);

      // 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(this);

      }

    }

    depth--;

  }

  void block_do(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");

  }

  UseCountComputer() {

    worklist = new Values();

    depth = 0;

  }

 public:

  static void compute(BlockList* blocks) {

    UseCountComputer ucc;

    blocks->iterate_backward(&ucc);

  }

};

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

  Compilation* _compilation;

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

  Compilation* compilation() const { return _compilation; }

 public:

  ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block);

  // accessors for final result

  BlockList* linear_scan_order() const    { return _linear_scan_order; }

  int        num_loops() const            { return _num_loops; }

};

ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :

  _max_block_id(BlockBegin::number_of_blocks()),

  _num_blocks(0),

  _num_loops(0),

  _iterative_dominators(false),

  _visited_blocks(_max_block_id),

  _active_blocks(_max_block_id),

  _dominator_blocks(_max_block_id),

  _forward_branches(_max_block_id, 0),

  _loop_end_blocks(8),

  _work_list(8),

  _linear_scan_order(NULL), // initialized later with correct size

  _loop_map(0, 0),          // initialized later with correct size

  _compilation(c)

{

  TRACE_LINEAR_SCAN(2, "***** computing linear-scan block order");

  init_visited();

  count_edges(start_block, NULL);

  if (compilation()->is_profiling()) {

    ciMethod *method = compilation()->method();

    if (!method->is_accessor()) {

      ciMethodData* md = method->method_data_or_null();

      assert(md != NULL, "Sanity");

      md->set_compilation_stats(_num_loops, _num_blocks);

    }

  }

  if (_num_loops > 0) {

    mark_loops();

    clear_non_natural_loops(start_block);

    assign_loop_depth(start_block);