1 /*

     2  * Copyright 2000-2006 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 

    26 class ciTypeFlow : public ResourceObj {

    27 private:

    28   ciEnv*    _env;

    29   ciMethod* _method;

    30   ciMethodBlocks* _methodBlocks;

    31   int       _osr_bci;

    32 

    33   // information cached from the method:

    34   int _max_locals;

    35   int _max_stack;

    36   int _code_size;

    37 

    38   const char* _failure_reason;

    39 

    40 public:

    41   class StateVector;

    42   class Block;

    43 

    44   // Build a type flow analyzer

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

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

    47 

    48   // Accessors

    49   ciMethod* method() const     { return _method; }

    50   ciEnv*    env()              { return _env; }

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

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

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

    54   int       max_locals() const { return _max_locals; }

    55   int       max_stack() const  { return _max_stack; }

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

    57   int       code_size() const  { return _code_size; }

    58 

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

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

    61   // with some distinct return address.

    62   class JsrRecord : public ResourceObj {

    63   private:

    64     int _entry_address;

    65     int _return_address;

    66   public:

    67     JsrRecord(int entry_address, int return_address) {

    68       _entry_address = entry_address;

    69       _return_address = return_address;

    70     }

    71 

    72     int entry_address() const  { return _entry_address; }

    73     int return_address() const { return _return_address; }

    74 

    75     void print_on(outputStream* st) const {

    76 #ifndef PRODUCT

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

    78 #endif

    79     }

    80   };

    81 

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

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

    84   // execution to return (ret) from.

    85   //

    86   // During abstract interpretation, JsrSets are used to determine

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

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

    89   // together.

    90   //

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

    92   // if paths are compatible.  <DISCUSSION>

    93   class JsrSet : public ResourceObj {

    94   private:

    95     GrowableArray<JsrRecord*>* _set;

    96 

    97     JsrRecord* record_at(int i) {

    98       return _set->at(i);

    99     }

   100 

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

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

   103     void insert_jsr_record(JsrRecord* record);

   104 

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

   106     void remove_jsr_record(int return_address);

   107 

   108   public:

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

   110 

   111     // Copy this JsrSet.

   112     void copy_into(JsrSet* jsrs);

   113 

   114     // Is this JsrSet compatible with some other JsrSet?

   115     bool is_compatible_with(JsrSet* other);

   116 

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

   118     void apply_control(ciTypeFlow* analyzer,

   119                        ciBytecodeStream* str,

   120                        StateVector* state);

   121 

   122     // What is the cardinality of this set?

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

   124 

   125     void print_on(outputStream* st) const PRODUCT_RETURN;

   126   };

   127 

   128   // Used as a combined index for locals and temps

   129   enum Cell {

   130     Cell_0

   131   };

   132 

   133   // A StateVector summarizes the type information at some

   134   // point in the program

   135   class StateVector : public ResourceObj {

   136   private:

   137     ciType**    _types;

   138     int         _stack_size;

   139     int         _monitor_count;

   140     ciTypeFlow* _outer;

   141 

   142     int         _trap_bci;

   143     int         _trap_index;

   144 

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

   146 

   147   public:

   148     // Special elements in our type lattice.

   149     enum {

   150       T_TOP     = T_VOID,      // why not?

   151       T_BOTTOM  = T_CONFLICT,

   152       T_LONG2   = T_SHORT,     // 2nd word of T_LONG

   153       T_DOUBLE2 = T_CHAR,      // 2nd word of T_DOUBLE

   154       T_NULL    = T_BYTE       // for now.

   155     };

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

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

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

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

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

   161 

   162     static ciType* half_type(ciType* t) {

   163       switch (t->basic_type()) {

   164       case T_LONG:    return long2_type();

   165       case T_DOUBLE:  return double2_type();

   166       default:        ShouldNotReachHere(); return NULL;

   167       }

   168     }

   169 

   170     // The meet operation for our type lattice.

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

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

   173     }

   174 

   175     // Accessors

   176     ciTypeFlow* outer() const          { return _outer; }

   177 

   178     int         stack_size() const     { return _stack_size; }

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

   180 

   181     int         monitor_count() const  { return _monitor_count; }

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

   183 

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

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

   186     Cell        limit_cell() const {

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

   188     }

   189 

   190     // Cell creation

   191     Cell      local(int lnum) const {

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

   193       return (Cell)(lnum);

   194     }

   195 

   196     Cell      stack(int snum) const {

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

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

   199     }

   200 

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

   202 

   203     // For external use only:

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

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

   206 

   207     // Accessors for the type of some Cell c

   208     ciType*   type_at(Cell c) const {

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

   210       return _types[c];

   211     }

   212 

   213     void      set_type_at(Cell c, ciType* type) {

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

   215       _types[c] = type;

   216     }

   217 

   218     // Top-of-stack operations.

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

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

   221 

   222     void      push(ciType* type) {

   223       _stack_size++;

   224       set_type_at_tos(type);

   225     }

   226     void      pop() {

   227       debug_only(set_type_at_tos(bottom_type()));

   228       _stack_size--;

   229     }

   230     ciType*   pop_value() {

   231       ciType* t = type_at_tos();

   232       pop();

   233       return t;

   234     }

   235 

   236     // Convenience operations.

   237     bool      is_reference(ciType* type) const {

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

   239     }

   240     bool      is_int(ciType* type) const {

   241       return type->basic_type() == T_INT;

   242     }

   243     bool      is_long(ciType* type) const {

   244       return type->basic_type() == T_LONG;

   245     }

   246     bool      is_float(ciType* type) const {

   247       return type->basic_type() == T_FLOAT;

   248     }

   249     bool      is_double(ciType* type) const {

   250       return type->basic_type() == T_DOUBLE;

   251     }

   252 

   253     void      push_translate(ciType* type);

   254 

   255     void      push_int() {

   256       push(ciType::make(T_INT));

   257     }

   258     void      pop_int() {

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

   260       pop();

   261     }

   262     void      check_int(Cell c) {

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

   264     }

   265     void      push_double() {

   266       push(ciType::make(T_DOUBLE));

   267       push(double2_type());

   268     }

   269     void      pop_double() {

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

   271       pop();

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

   273       pop();

   274     }

   275     void      push_float() {

   276       push(ciType::make(T_FLOAT));

   277     }

   278     void      pop_float() {

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

   280       pop();

   281     }

   282     void      push_long() {

   283       push(ciType::make(T_LONG));

   284       push(long2_type());

   285     }

   286     void      pop_long() {

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

   288       pop();

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

   290       pop();

   291     }

   292     void      push_object(ciKlass* klass) {

   293       push(klass);

   294     }

   295     void      pop_object() {

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

   297       pop();

   298     }

   299     void      pop_array() {

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

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

   302       pop();

   303     }

   304     // pop_objArray and pop_typeArray narrow the tos to ciObjArrayKlass

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

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

   307     ciObjArrayKlass* pop_objArray() {

   308       ciType* array = pop_value();

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

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

   311       return array->as_obj_array_klass();

   312     }

   313     ciTypeArrayKlass* pop_typeArray() {

   314       ciType* array = pop_value();

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

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

   317       return array->as_type_array_klass();

   318     }

   319     void      push_null() {

   320       push(null_type());

   321     }

   322     void      do_null_assert(ciKlass* unloaded_klass);

   323 

   324     // Helper convenience routines.

   325     void do_aaload(ciBytecodeStream* str);

   326     void do_checkcast(ciBytecodeStream* str);

   327     void do_getfield(ciBytecodeStream* str);

   328     void do_getstatic(ciBytecodeStream* str);

   329     void do_invoke(ciBytecodeStream* str, bool has_receiver);

   330     void do_jsr(ciBytecodeStream* str);

   331     void do_ldc(ciBytecodeStream* str);

   332     void do_multianewarray(ciBytecodeStream* str);

   333     void do_new(ciBytecodeStream* str);

   334     void do_newarray(ciBytecodeStream* str);

   335     void do_putfield(ciBytecodeStream* str);

   336     void do_putstatic(ciBytecodeStream* str);

   337     void do_ret(ciBytecodeStream* str);

   338 

   339     void overwrite_local_double_long(int index) {

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

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

   342       int prev_index = index - 1;

   343       if (prev_index >= 0 &&

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

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

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

   347       }

   348     }

   349 

   350     void load_local_object(int index) {

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

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

   353       push(type);

   354     }

   355     void store_local_object(int index) {

   356       ciType* type = pop_value();

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

   358              "must be reference type or return address");

   359       overwrite_local_double_long(index);

   360       set_type_at(local(index), type);

   361     }

   362 

   363     void load_local_double(int index) {

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

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

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

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

   368       push(type);

   369       push(double2_type());

   370     }

   371     void store_local_double(int index) {

   372       ciType* type2 = pop_value();

   373       ciType* type = pop_value();

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

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

   376       overwrite_local_double_long(index);

   377       set_type_at(local(index), type);

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

   379     }

   380 

   381     void load_local_float(int index) {

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

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

   384       push(type);

   385     }

   386     void store_local_float(int index) {

   387       ciType* type = pop_value();

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

   389       overwrite_local_double_long(index);

   390       set_type_at(local(index), type);

   391     }

   392 

   393     void load_local_int(int index) {

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

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

   396       push(type);

   397     }

   398     void store_local_int(int index) {

   399       ciType* type = pop_value();

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

   401       overwrite_local_double_long(index);

   402       set_type_at(local(index), type);

   403     }

   404 

   405     void load_local_long(int index) {

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

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

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

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

   410       push(type);

   411       push(long2_type());

   412     }

   413     void store_local_long(int index) {

   414       ciType* type2 = pop_value();

   415       ciType* type = pop_value();

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

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

   418       overwrite_local_double_long(index);

   419       set_type_at(local(index), type);

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

   421     }

   422 

   423     // Stop interpretation of this path with a trap.

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

   425 

   426   public:

   427     StateVector(ciTypeFlow* outer);

   428 

   429     // Copy our value into some other StateVector

   430     void copy_into(StateVector* copy) const;

   431 

   432     // Meets this StateVector with another, destructively modifying this

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

   434     bool meet(const StateVector* incoming);

   435 

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

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

   438 

   439     // Apply the effect of one bytecode to this StateVector

   440     bool apply_one_bytecode(ciBytecodeStream* stream);

   441 

   442     // What is the bci of the trap?

   443     int  trap_bci() { return _trap_bci; }

   444 

   445     // What is the index associated with the trap?

   446     int  trap_index() { return _trap_index; }

   447 

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

   449     void print_on(outputStream* st) const              PRODUCT_RETURN;

   450   };

   451 

   452   // Parameter for "find_block" calls:

   453   // Describes the difference between a public and private copy.

   454   enum CreateOption {

   455     create_public_copy,

   456     create_private_copy,

   457     no_create

   458   };

   459 

   460   // A basic block

   461   class Block : public ResourceObj {

   462   private:

   463     ciBlock*                          _ciblock;

   464     GrowableArray<Block*>*           _exceptions;

   465     GrowableArray<ciInstanceKlass*>* _exc_klasses;

   466     GrowableArray<Block*>*           _successors;

   467     StateVector*                     _state;

   468     JsrSet*                          _jsrs;

   469 

   470     int                              _trap_bci;

   471     int                              _trap_index;

   472 

   473     // A reasonable approximation to pre-order, provided.to the client.

   474     int                              _pre_order;

   475 

   476     // Has this block been cloned for some special purpose?

   477     bool                             _private_copy;

   478 

   479     // A pointer used for our internal work list

   480     Block*                 _next;

   481     bool                   _on_work_list;

   482 

   483     ciBlock*     ciblock() const     { return _ciblock; }

   484     StateVector* state() const     { return _state; }

   485 

   486     // Compute the exceptional successors and types for this Block.

   487     void compute_exceptions();

   488 

   489   public:

   490     // constructors

   491     Block(ciTypeFlow* outer, ciBlock* ciblk, JsrSet* jsrs);

   492 

   493     void set_trap(int trap_bci, int trap_index) {

   494       _trap_bci = trap_bci;

   495       _trap_index = trap_index;

   496       assert(has_trap(), "");

   497     }

   498     bool has_trap()   const  { return _trap_bci != -1; }

   499     int  trap_bci()   const  { assert(has_trap(), ""); return _trap_bci; }

   500     int  trap_index() const  { assert(has_trap(), ""); return _trap_index; }

   501 

   502     // accessors

   503     ciTypeFlow* outer() const { return state()->outer(); }

   504     int start() const         { return _ciblock->start_bci(); }

   505     int limit() const         { return _ciblock->limit_bci(); }

   506     int control() const       { return _ciblock->control_bci(); }

   507 

   508     bool    is_private_copy() const       { return _private_copy; }

   509     void   set_private_copy(bool z);

   510     int        private_copy_count() const { return outer()->private_copy_count(ciblock()->index(), _jsrs); }

   511 

   512     // access to entry state

   513     int     stack_size() const         { return _state->stack_size(); }

   514     int     monitor_count() const      { return _state->monitor_count(); }

   515     ciType* local_type_at(int i) const { return _state->local_type_at(i); }

   516     ciType* stack_type_at(int i) const { return _state->stack_type_at(i); }

   517 

   518     // Get the successors for this Block.

   519     GrowableArray<Block*>* successors(ciBytecodeStream* str,

   520                                       StateVector* state,

   521                                       JsrSet* jsrs);

   522     GrowableArray<Block*>* successors() {

   523       assert(_successors != NULL, "must be filled in");

   524       return _successors;

   525     }

   526 

   527     // Helper function for "successors" when making private copies of

   528     // loop heads for C2.

   529     Block * clone_loop_head(ciTypeFlow* analyzer,

   530                             int branch_bci,

   531                             Block* target,

   532                             JsrSet* jsrs);

   533 

   534     // Get the exceptional successors for this Block.

   535     GrowableArray<Block*>* exceptions() {

   536       if (_exceptions == NULL) {

   537         compute_exceptions();

   538       }

   539       return _exceptions;

   540     }

   541 

   542     // Get the exception klasses corresponding to the

   543     // exceptional successors for this Block.

   544     GrowableArray<ciInstanceKlass*>* exc_klasses() {

   545       if (_exc_klasses == NULL) {

   546         compute_exceptions();

   547       }

   548       return _exc_klasses;

   549     }

   550 

   551     // Is this Block compatible with a given JsrSet?

   552     bool is_compatible_with(JsrSet* other) {

   553       return _jsrs->is_compatible_with(other);

   554     }

   555 

   556     // Copy the value of our state vector into another.

   557     void copy_state_into(StateVector* copy) const {

   558       _state->copy_into(copy);

   559     }

   560 

   561     // Copy the value of our JsrSet into another

   562     void copy_jsrs_into(JsrSet* copy) const {

   563       _jsrs->copy_into(copy);

   564     }

   565 

   566     // Meets the start state of this block with another state, destructively

   567     // modifying this one.  Returns true if any modification takes place.

   568     bool meet(const StateVector* incoming) {

   569       return state()->meet(incoming);

   570     }

   571 

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

   573     // exception path.  This means the stack is replaced by the

   574     // appropriate exception type.

   575     bool meet_exception(ciInstanceKlass* exc, const StateVector* incoming) {

   576       return state()->meet_exception(exc, incoming);

   577     }

   578 

   579     // Work list manipulation

   580     void   set_next(Block* block) { _next = block; }

   581     Block* next() const           { return _next; }

   582 

   583     void   set_on_work_list(bool c) { _on_work_list = c; }

   584     bool   is_on_work_list() const  { return _on_work_list; }

   585 

   586     bool   has_pre_order() const  { return _pre_order >= 0; }

   587     void   set_pre_order(int po)  { assert(!has_pre_order() && po >= 0, ""); _pre_order = po; }

   588     int    pre_order() const      { assert(has_pre_order(), ""); return _pre_order; }

   589     bool   is_start() const       { return _pre_order == outer()->start_block_num(); }

   590 

   591     // A ranking used in determining order within the work list.

   592     bool   is_simpler_than(Block* other);

   593 

   594     void   print_value_on(outputStream* st) const PRODUCT_RETURN;

   595     void   print_on(outputStream* st) const       PRODUCT_RETURN;

   596   };

   597 

   598   // Standard indexes of successors, for various bytecodes.

   599   enum {

   600     FALL_THROUGH   = 0,  // normal control

   601     IF_NOT_TAKEN   = 0,  // the not-taken branch of an if (i.e., fall-through)

   602     IF_TAKEN       = 1,  // the taken branch of an if

   603     GOTO_TARGET    = 0,  // unique successor for goto, jsr, or ret

   604     SWITCH_DEFAULT = 0,  // default branch of a switch

   605     SWITCH_CASES   = 1   // first index for any non-default switch branches

   606     // Unlike in other blocks, the successors of a switch are listed uniquely.

   607   };

   608 

   609 private:

   610   // A mapping from pre_order to Blocks.  This array is created

   611   // only at the end of the flow.

   612   Block** _block_map;

   613 

   614   // For each ciBlock index, a list of Blocks which share this ciBlock.

   615   GrowableArray<Block*>** _idx_to_blocklist;

   616   // count of ciBlocks

   617   int _ciblock_count;

   618 

   619   // Tells if a given instruction is able to generate an exception edge.

   620   bool can_trap(ciBytecodeStream& str);

   621 

   622 public:

   623   // Return the block beginning at bci which has a JsrSet compatible

   624   // with jsrs.

   625   Block* block_at(int bci, JsrSet* set, CreateOption option = create_public_copy);

   626 

   627   // block factory

   628   Block* get_block_for(int ciBlockIndex, JsrSet* jsrs, CreateOption option = create_public_copy);

   629 

   630   // How many of the blocks have the private_copy bit set?

   631   int private_copy_count(int ciBlockIndex, JsrSet* jsrs) const;

   632 

   633   // Return an existing block containing bci which has a JsrSet compatible

   634   // with jsrs, or NULL if there is none.

   635   Block* existing_block_at(int bci, JsrSet* set) { return block_at(bci, set, no_create); }

   636 

   637   // Tell whether the flow analysis has encountered an error of some sort.

   638   bool failing() { return env()->failing() || _failure_reason != NULL; }

   639 

   640   // Reason this compilation is failing, such as "too many basic blocks".

   641   const char* failure_reason() { return _failure_reason; }

   642 

   643   // Note a failure.

   644   void record_failure(const char* reason);

   645 

   646   // Return the block of a given pre-order number.

   647   int have_block_count() const      { return _block_map != NULL; }

   648   int block_count() const           { assert(have_block_count(), "");

   649                                       return _next_pre_order; }

   650   Block* pre_order_at(int po) const { assert(0 <= po && po < block_count(), "out of bounds");

   651                                       return _block_map[po]; }

   652   Block* start_block() const        { return pre_order_at(start_block_num()); }

   653   int start_block_num() const       { return 0; }

   654 

   655 private:

   656   // A work list used during flow analysis.

   657   Block* _work_list;

   658 

   659   // Next Block::_pre_order.  After mapping, doubles as block_count.

   660   int _next_pre_order;

   661 

   662   // Are there more blocks on the work list?

   663   bool work_list_empty() { return _work_list == NULL; }

   664 

   665   // Get the next basic block from our work list.

   666   Block* work_list_next();

   667 

   668   // Add a basic block to our work list.

   669   void add_to_work_list(Block* block);

   670 

   671   // State used for make_jsr_record

   672   int _jsr_count;

   673   GrowableArray<JsrRecord*>* _jsr_records;

   674 

   675 public:

   676   // Make a JsrRecord for a given (entry, return) pair, if such a record

   677   // does not already exist.

   678   JsrRecord* make_jsr_record(int entry_address, int return_address);

   679 

   680 private:

   681   // Get the initial state for start_bci:

   682   const StateVector* get_start_state();

   683 

   684   // Merge the current state into all exceptional successors at the

   685   // current point in the code.

   686   void flow_exceptions(GrowableArray<Block*>* exceptions,

   687                        GrowableArray<ciInstanceKlass*>* exc_klasses,

   688                        StateVector* state);

   689 

   690   // Merge the current state into all successors at the current point

   691   // in the code.

   692   void flow_successors(GrowableArray<Block*>* successors,

   693                        StateVector* state);

   694 

   695   // Interpret the effects of the bytecodes on the incoming state

   696   // vector of a basic block.  Push the changed state to succeeding

   697   // basic blocks.

   698   void flow_block(Block* block,

   699                   StateVector* scratch_state,

   700                   JsrSet* scratch_jsrs);

   701 

   702   // Perform the type flow analysis, creating and cloning Blocks as

   703   // necessary.

   704   void flow_types();

   705 

   706   // Create the block map, which indexes blocks in pre_order.

   707   void map_blocks();

   708 

   709 public:

   710   // Perform type inference flow analysis.

   711   void do_flow();

   712 

   713   void print_on(outputStream* st) const PRODUCT_RETURN;

   714 };