/*

 * Copyright 2000-2008 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.

 *

 */

class ciTypeFlow : public ResourceObj {

private:

  ciEnv*    _env;

  ciMethod* _method;

  ciMethodBlocks* _methodBlocks;

  int       _osr_bci;

  // information cached from the method:

  int _max_locals;

  int _max_stack;

  int _code_size;

  bool      _has_irreducible_entry;

  const char* _failure_reason;

public:

  class StateVector;

  class Loop;

  class Block;

  // Build a type flow analyzer

  // Do an OSR analysis if osr_bci >= 0.

  ciTypeFlow(ciEnv* env, ciMethod* method, int osr_bci = InvocationEntryBci);

  // Accessors

  ciMethod* method() const     { return _method; }

  ciEnv*    env()              { return _env; }

  Arena*    arena()            { return _env->arena(); }

  bool      is_osr_flow() const{ return _osr_bci != InvocationEntryBci; }

  int       start_bci() const  { return is_osr_flow()? _osr_bci: 0; }

  int       max_locals() const { return _max_locals; }

  int       max_stack() const  { return _max_stack; }

  int       max_cells() const  { return _max_locals + _max_stack; }

  int       code_size() const  { return _code_size; }

  bool      has_irreducible_entry() const { return _has_irreducible_entry; }

  // Represents information about an "active" jsr call.  This

  // class represents a call to the routine at some entry address

  // with some distinct return address.

  class JsrRecord : public ResourceObj {

  private:

    int _entry_address;

    int _return_address;

  public:

    JsrRecord(int entry_address, int return_address) {

      _entry_address = entry_address;

      _return_address = return_address;

    }

    int entry_address() const  { return _entry_address; }

    int return_address() const { return _return_address; }

    void print_on(outputStream* st) const {

#ifndef PRODUCT

      st->print("%d->%d", entry_address(), return_address());

#endif

    }

  };

  // A JsrSet represents some set of JsrRecords.  This class

  // is used to record a set of all jsr routines which we permit

  // execution to return (ret) from.

  //

  // During abstract interpretation, JsrSets are used to determine

  // whether two paths which reach a given block are unique, and

  // should be cloned apart, or are compatible, and should merge

  // together.

  //

  // Note that different amounts of effort can be expended determining

  // if paths are compatible.  <DISCUSSION>

  class JsrSet : public ResourceObj {

  private:

    GrowableArray<JsrRecord*>* _set;

    JsrRecord* record_at(int i) {

      return _set->at(i);

    }

    // Insert the given JsrRecord into the JsrSet, maintaining the order

    // of the set and replacing any element with the same entry address.

    void insert_jsr_record(JsrRecord* record);

    // Remove the JsrRecord with the given return address from the JsrSet.

    void remove_jsr_record(int return_address);

  public:

    JsrSet(Arena* arena, int default_len = 4);

    // Copy this JsrSet.

    void copy_into(JsrSet* jsrs);

    // Is this JsrSet compatible with some other JsrSet?

    bool is_compatible_with(JsrSet* other);

    // Apply the effect of a single bytecode to the JsrSet.

    void apply_control(ciTypeFlow* analyzer,

                       ciBytecodeStream* str,

                       StateVector* state);

    // What is the cardinality of this set?

    int size() const { return _set->length(); }

    void print_on(outputStream* st) const PRODUCT_RETURN;

  };

  class LocalSet VALUE_OBJ_CLASS_SPEC {

  private:

    enum Constants { max = 63 };

    uint64_t _bits;

  public:

    LocalSet() : _bits(0) {}

    void add(uint32_t i)        { if (i < (uint32_t)max) _bits |=  (1LL << i); }

    void add(LocalSet* ls)      { _bits |= ls->_bits; }

    bool test(uint32_t i) const { return i < (uint32_t)max ? (_bits>>i)&1U : true; }

    void clear()                { _bits = 0; }

    void print_on(outputStream* st, int limit) const  PRODUCT_RETURN;

  };

  // Used as a combined index for locals and temps

  enum Cell {

    Cell_0, Cell_max = INT_MAX

  };

  // A StateVector summarizes the type information at some

  // point in the program

  class StateVector : public ResourceObj {

  private:

    ciType**    _types;

    int         _stack_size;

    int         _monitor_count;

    ciTypeFlow* _outer;

    int         _trap_bci;

    int         _trap_index;

    LocalSet    _def_locals;  // For entire block

    static ciType* type_meet_internal(ciType* t1, ciType* t2, ciTypeFlow* analyzer);

  public:

    // Special elements in our type lattice.

    enum {

      T_TOP     = T_VOID,      // why not?

      T_BOTTOM  = T_CONFLICT,

      T_LONG2   = T_SHORT,     // 2nd word of T_LONG

      T_DOUBLE2 = T_CHAR,      // 2nd word of T_DOUBLE

      T_NULL    = T_BYTE       // for now.

    };

    static ciType* top_type()    { return ciType::make((BasicType)T_TOP); }

    static ciType* bottom_type() { return ciType::make((BasicType)T_BOTTOM); }

    static ciType* long2_type()  { return ciType::make((BasicType)T_LONG2); }

    static ciType* double2_type(){ return ciType::make((BasicType)T_DOUBLE2); }

    static ciType* null_type()   { return ciType::make((BasicType)T_NULL); }

    static ciType* half_type(ciType* t) {

      switch (t->basic_type()) {

      case T_LONG:    return long2_type();

      case T_DOUBLE:  return double2_type();

      default:        ShouldNotReachHere(); return NULL;

      }

    }

    // The meet operation for our type lattice.

    ciType* type_meet(ciType* t1, ciType* t2) {

      return type_meet_internal(t1, t2, outer());

    }

    // Accessors

    ciTypeFlow* outer() const          { return _outer; }

    int         stack_size() const     { return _stack_size; }

    void    set_stack_size(int ss)     { _stack_size = ss; }

    int         monitor_count() const  { return _monitor_count; }

    void    set_monitor_count(int mc)  { _monitor_count = mc; }

    LocalSet* def_locals() { return &_def_locals; }

    const LocalSet* def_locals() const { return &_def_locals; }

    static Cell start_cell()           { return (Cell)0; }

    static Cell next_cell(Cell c)      { return (Cell)(((int)c) + 1); }

    Cell        limit_cell() const {

      return (Cell)(outer()->max_locals() + stack_size());

    }

    // Cell creation

    Cell      local(int lnum) const {

      assert(lnum < outer()->max_locals(), "index check");

      return (Cell)(lnum);

    }

    Cell      stack(int snum) const {

      assert(snum < stack_size(), "index check");

      return (Cell)(outer()->max_locals() + snum);

    }

    Cell      tos() const { return stack(stack_size()-1); }

    // For external use only:

    ciType* local_type_at(int i) const { return type_at(local(i)); }

    ciType* stack_type_at(int i) const { return type_at(stack(i)); }

    // Accessors for the type of some Cell c

    ciType*   type_at(Cell c) const {

      assert(start_cell() <= c && c < limit_cell(), "out of bounds");

      return _types[c];

    }

    void      set_type_at(Cell c, ciType* type) {

      assert(start_cell() <= c && c < limit_cell(), "out of bounds");

      _types[c] = type;

    }

    // Top-of-stack operations.

    void      set_type_at_tos(ciType* type) { set_type_at(tos(), type); }

    ciType*   type_at_tos() const           { return type_at(tos()); }

    void      push(ciType* type) {

      _stack_size++;

      set_type_at_tos(type);

    }

    void      pop() {

      debug_only(set_type_at_tos(bottom_type()));

      _stack_size--;

    }

    ciType*   pop_value() {

      ciType* t = type_at_tos();

      pop();

      return t;

    }

    // Convenience operations.

    bool      is_reference(ciType* type) const {

      return type == null_type() || !type->is_primitive_type();

    }

    bool      is_int(ciType* type) const {

      return type->basic_type() == T_INT;

    }

    bool      is_long(ciType* type) const {

      return type->basic_type() == T_LONG;

    }

    bool      is_float(ciType* type) const {

      return type->basic_type() == T_FLOAT;

    }

    bool      is_double(ciType* type) const {

      return type->basic_type() == T_DOUBLE;

    }

    void store_to_local(int lnum) {

      _def_locals.add((uint) lnum);

    }

    void      push_translate(ciType* type);

    void      push_int() {

      push(ciType::make(T_INT));

    }

    void      pop_int() {

      assert(is_int(type_at_tos()), "must be integer");

      pop();

    }

    void      check_int(Cell c) {

      assert(is_int(type_at(c)), "must be integer");

    }

    void      push_double() {

      push(ciType::make(T_DOUBLE));

      push(double2_type());

    }

    void      pop_double() {

      assert(type_at_tos() == double2_type(), "must be 2nd half");

      pop();

      assert(is_double(type_at_tos()), "must be double");

      pop();

    }

    void      push_float() {

      push(ciType::make(T_FLOAT));

    }

    void      pop_float() {

      assert(is_float(type_at_tos()), "must be float");

      pop();

    }

    void      push_long() {

      push(ciType::make(T_LONG));

      push(long2_type());

    }

    void      pop_long() {

      assert(type_at_tos() == long2_type(), "must be 2nd half");

      pop();

      assert(is_long(type_at_tos()), "must be long");

      pop();

    }

    void      push_object(ciKlass* klass) {

      push(klass);

    }

    void      pop_object() {

      assert(is_reference(type_at_tos()), "must be reference type");

      pop();

    }

    void      pop_array() {

      assert(type_at_tos() == null_type() ||

             type_at_tos()->is_array_klass(), "must be array type");

      pop();

    }

    // pop_objArray and pop_typeArray narrow the tos to ciObjArrayKlass

    // or ciTypeArrayKlass (resp.).  In the rare case that an explicit

    // null is popped from the stack, we return NULL.  Caller beware.

    ciObjArrayKlass* pop_objArray() {

      ciType* array = pop_value();

      if (array == null_type())  return NULL;

      assert(array->is_obj_array_klass(), "must be object array type");

      return array->as_obj_array_klass();

    }

    ciTypeArrayKlass* pop_typeArray() {

      ciType* array = pop_value();

      if (array == null_type())  return NULL;

      assert(array->is_type_array_klass(), "must be prim array type");

      return array->as_type_array_klass();

    }

    void      push_null() {

      push(null_type());

    }

    void      do_null_assert(ciKlass* unloaded_klass);

    // Helper convenience routines.

    void do_aaload(ciBytecodeStream* str);

    void do_checkcast(ciBytecodeStream* str);

    void do_getfield(ciBytecodeStream* str);

    void do_getstatic(ciBytecodeStream* str);

    void do_invoke(ciBytecodeStream* str, bool has_receiver);

    void do_jsr(ciBytecodeStream* str);

    void do_ldc(ciBytecodeStream* str);

    void do_multianewarray(ciBytecodeStream* str);

    void do_new(ciBytecodeStream* str);

    void do_newarray(ciBytecodeStream* str);

    void do_putfield(ciBytecodeStream* str);

    void do_putstatic(ciBytecodeStream* str);

    void do_ret(ciBytecodeStream* str);

    void overwrite_local_double_long(int index) {

      // Invalidate the previous local if it contains first half of

      // a double or long value since it's seconf half is being overwritten.

      int prev_index = index - 1;

      if (prev_index >= 0 &&

          (is_double(type_at(local(prev_index))) ||

           is_long(type_at(local(prev_index))))) {

        set_type_at(local(prev_index), bottom_type());

      }

    }

    void load_local_object(int index) {

      ciType* type = type_at(local(index));

      assert(is_reference(type), "must be reference type");

      push(type);

    }

    void store_local_object(int index) {

      ciType* type = pop_value();

      assert(is_reference(type) || type->is_return_address(),

             "must be reference type or return address");

      overwrite_local_double_long(index);

      set_type_at(local(index), type);

      store_to_local(index);

    }

    void load_local_double(int index) {

      ciType* type = type_at(local(index));

      ciType* type2 = type_at(local(index+1));

      assert(is_double(type), "must be double type");

      assert(type2 == double2_type(), "must be 2nd half");

      push(type);

      push(double2_type());

    }

    void store_local_double(int index) {

      ciType* type2 = pop_value();

      ciType* type = pop_value();

      assert(is_double(type), "must be double");

      assert(type2 == double2_type(), "must be 2nd half");

      overwrite_local_double_long(index);

      set_type_at(local(index), type);

      set_type_at(local(index+1), type2);

      store_to_local(index);

      store_to_local(index+1);

    }

    void load_local_float(int index) {

      ciType* type = type_at(local(index));

      assert(is_float(type), "must be float type");

      push(type);

    }

    void store_local_float(int index) {

      ciType* type = pop_value();

      assert(is_float(type), "must be float type");

      overwrite_local_double_long(index);

      set_type_at(local(index), type);

      store_to_local(index);

    }

    void load_local_int(int index) {

      ciType* type = type_at(local(index));

      assert(is_int(type), "must be int type");

      push(type);

    }

    void store_local_int(int index) {

      ciType* type = pop_value();

      assert(is_int(type), "must be int type");

      overwrite_local_double_long(index);

      set_type_at(local(index), type);

      store_to_local(index);

    }

    void load_local_long(int index) {

      ciType* type = type_at(local(index));

      ciType* type2 = type_at(local(index+1));

      assert(is_long(type), "must be long type");

      assert(type2 == long2_type(), "must be 2nd half");

      push(type);

      push(long2_type());

    }

    void store_local_long(int index) {

      ciType* type2 = pop_value();

      ciType* type = pop_value();

      assert(is_long(type), "must be long");

      assert(type2 == long2_type(), "must be 2nd half");

      overwrite_local_double_long(index);

      set_type_at(local(index), type);

      set_type_at(local(index+1), type2);

      store_to_local(index);

      store_to_local(index+1);

    }

    // Stop interpretation of this path with a trap.

    void trap(ciBytecodeStream* str, ciKlass* klass, int index);

  public:

    StateVector(ciTypeFlow* outer);

    // Copy our value into some other StateVector

    void copy_into(StateVector* copy) const;

    // Meets this StateVector with another, destructively modifying this

    // one.  Returns true if any modification takes place.

    bool meet(const StateVector* incoming);

    // Ditto, except that the incoming state is coming from an exception.

    bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming);

    // Apply the effect of one bytecode to this StateVector

    bool apply_one_bytecode(ciBytecodeStream* stream);

    // What is the bci of the trap?

    int  trap_bci() { return _trap_bci; }

    // What is the index associated with the trap?

    int  trap_index() { return _trap_index; }

    void print_cell_on(outputStream* st, Cell c) const PRODUCT_RETURN;

    void print_on(outputStream* st) const              PRODUCT_RETURN;

  };

  // Parameter for "find_block" calls:

  // Describes the difference between a public and backedge copy.

  enum CreateOption {

    create_public_copy,

    create_backedge_copy,

    no_create

  };

  // Successor iterator

  class SuccIter : public StackObj {

  private:

    Block* _pred;

    int    _index;

    Block* _succ;

  public:

    SuccIter()                        : _pred(NULL), _index(-1), _succ(NULL) {}

    SuccIter(Block* pred)             : _pred(pred), _index(-1), _succ(NULL) { next(); }

    int    index()     { return _index; }

    Block* pred()      { return _pred; }           // Return predecessor

    bool   done()      { return _index < 0; }      // Finished?

    Block* succ()      { return _succ; }           // Return current successor

    void   next();                                 // Advance

    void   set_succ(Block* succ);                  // Update current successor

    bool   is_normal_ctrl() { return index() < _pred->successors()->length(); }

  };

  // A basic block

  class Block : public ResourceObj {

  private:

    ciBlock*                          _ciblock;

    GrowableArray<Block*>*           _exceptions;

    GrowableArray<ciInstanceKlass*>* _exc_klasses;

    GrowableArray<Block*>*           _successors;

    StateVector*                     _state;

    JsrSet*                          _jsrs;

    int                              _trap_bci;

    int                              _trap_index;