1 /*

     2  * Copyright 1999-2007 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 #include "incls/_precompiled.incl"

    26 #include "incls/_c1_GraphBuilder.cpp.incl"

    27 

    28 class BlockListBuilder VALUE_OBJ_CLASS_SPEC {

    29  private:

    30   Compilation* _compilation;

    31   IRScope*     _scope;

    32 

    33   BlockList    _blocks;                // internal list of all blocks

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

    35 

    36   // fields used by mark_loops

    37   BitMap       _active;                // for iteration of control flow graph

    38   BitMap       _visited;               // for iteration of control flow graph

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

    40   int          _next_loop_index;       // next free loop number

    41   int          _next_block_number;     // for reverse postorder numbering of blocks

    42 

    43   // accessors

    44   Compilation*  compilation() const              { return _compilation; }

    45   IRScope*      scope() const                    { return _scope; }

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

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

    48 

    49   // unified bailout support

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

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

    52 

    53   // helper functions

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

    55   void handle_exceptions(BlockBegin* current, int cur_bci);

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

    57   void store_one(BlockBegin* current, int local);

    58   void store_two(BlockBegin* current, int local);

    59   void set_entries(int osr_bci);

    60   void set_leaders();

    61 

    62   void make_loop_header(BlockBegin* block);

    63   void mark_loops();

    64   int  mark_loops(BlockBegin* b, bool in_subroutine);

    65 

    66   // debugging

    67 #ifndef PRODUCT

    68   void print();

    69 #endif

    70 

    71  public:

    72   // creation

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

    74 

    75   // accessors for GraphBuilder

    76   BlockList*    bci2block() const                { return _bci2block; }

    77 };

    78 

    79 

    80 // Implementation of BlockListBuilder

    81 

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

    83  : _compilation(compilation)

    84  , _scope(scope)

    85  , _blocks(16)

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

    87  , _next_block_number(0)

    88  , _active()         // size not known yet

    89  , _visited()        // size not known yet

    90  , _next_loop_index(0)

    91  , _loop_map() // size not known yet

    92 {

    93   set_entries(osr_bci);

    94   set_leaders();

    95   CHECK_BAILOUT();

    96 

    97   mark_loops();

    98   NOT_PRODUCT(if (PrintInitialBlockList) print());

    99 

   100 #ifndef PRODUCT

   101   if (PrintCFGToFile) {

   102     stringStream title;

   103     title.print("BlockListBuilder ");

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

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

   106   }

   107 #endif

   108 }

   109 

   110 

   111 void BlockListBuilder::set_entries(int osr_bci) {

   112   // generate start blocks

   113   BlockBegin* std_entry = make_block_at(0, NULL);

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

   115     std_entry->set(BlockBegin::std_entry_flag);

   116   }

   117   if (osr_bci != -1) {

   118     BlockBegin* osr_entry = make_block_at(osr_bci, NULL);

   119     osr_entry->set(BlockBegin::osr_entry_flag);

   120   }

   121 

   122   // generate exception entry blocks

   123   XHandlers* list = xhandlers();

   124   const int n = list->length();

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

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

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

   128     entry->set(BlockBegin::exception_entry_flag);

   129     h->set_entry_block(entry);

   130   }

   131 }

   132 

   133 

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

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

   136 

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

   138   if (block == NULL) {

   139     block = new BlockBegin(cur_bci);

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

   141     _bci2block->at_put(cur_bci, block);

   142     _blocks.append(block);

   143 

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

   145   }

   146 

   147   if (predecessor != NULL) {

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

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

   150     }

   151 

   152     predecessor->add_successor(block);

   153     block->increment_total_preds();

   154   }

   155 

   156   return block;

   157 }

   158 

   159 

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

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

   162 }

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

   164   store_one(current, local);

   165   store_one(current, local + 1);

   166 }

   167 

   168 

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

   170   // Draws edges from a block to its exception handlers

   171   XHandlers* list = xhandlers();

   172   const int n = list->length();

   173 

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

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

   176 

   177     if (h->covers(cur_bci)) {

   178       BlockBegin* entry = h->entry_block();

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

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

   181 

   182       // add each exception handler only once

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

   184         current->add_successor(entry);

   185         entry->increment_total_preds();

   186       }

   187 

   188       // stop when reaching catchall

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

   190     }

   191   }

   192 }

   193 

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

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

   196   make_block_at(next_bci, current);

   197 

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

   199   BlockBegin* sr_block = make_block_at(sr_bci, current);

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

   201     sr_block->set(BlockBegin::subroutine_entry_flag);

   202   }

   203 }

   204 

   205 

   206 void BlockListBuilder::set_leaders() {

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

   208   BlockBegin* current = NULL;

   209 

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

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

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

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

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

   215 

   216   ciBytecodeStream s(method());

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

   218     int cur_bci = s.cur_bci();

   219 

   220     if (bci_block_start.at(cur_bci)) {

   221       current = make_block_at(cur_bci, current);

   222     }

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

   224 

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

   226       handle_exceptions(current, cur_bci);

   227     }

   228 

   229     switch (s.cur_bc()) {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   257 

   258       // track bytecodes that affect the control flow

   259       case Bytecodes::_athrow:  // fall through

   260       case Bytecodes::_ret:     // fall through

   261       case Bytecodes::_ireturn: // fall through

   262       case Bytecodes::_lreturn: // fall through

   263       case Bytecodes::_freturn: // fall through

   264       case Bytecodes::_dreturn: // fall through

   265       case Bytecodes::_areturn: // fall through

   266       case Bytecodes::_return:

   267         current = NULL;

   268         break;

   269 

   270       case Bytecodes::_ifeq:      // fall through

   271       case Bytecodes::_ifne:      // fall through

   272       case Bytecodes::_iflt:      // fall through

   273       case Bytecodes::_ifge:      // fall through

   274       case Bytecodes::_ifgt:      // fall through

   275       case Bytecodes::_ifle:      // fall through

   276       case Bytecodes::_if_icmpeq: // fall through

   277       case Bytecodes::_if_icmpne: // fall through

   278       case Bytecodes::_if_icmplt: // fall through

   279       case Bytecodes::_if_icmpge: // fall through

   280       case Bytecodes::_if_icmpgt: // fall through

   281       case Bytecodes::_if_icmple: // fall through

   282       case Bytecodes::_if_acmpeq: // fall through

   283       case Bytecodes::_if_acmpne: // fall through

   284       case Bytecodes::_ifnull:    // fall through

   285       case Bytecodes::_ifnonnull:

   286         make_block_at(s.next_bci(), current);

   287         make_block_at(s.get_dest(), current);

   288         current = NULL;

   289         break;

   290 

   291       case Bytecodes::_goto:

   292         make_block_at(s.get_dest(), current);

   293         current = NULL;

   294         break;

   295 

   296       case Bytecodes::_goto_w:

   297         make_block_at(s.get_far_dest(), current);

   298         current = NULL;

   299         break;

   300 

   301       case Bytecodes::_jsr:

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

   303         current = NULL;

   304         break;

   305 

   306       case Bytecodes::_jsr_w:

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

   308         current = NULL;

   309         break;

   310 

   311       case Bytecodes::_tableswitch: {

   312         // set block for each case

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

   314         int l = switch_->length();

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

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

   317         }

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

   319         current = NULL;

   320         break;

   321       }

   322 

   323       case Bytecodes::_lookupswitch: {

   324         // set block for each case

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

   326         int l = switch_->number_of_pairs();

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

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

   329         }

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

   331         current = NULL;

   332         break;

   333       }

   334     }

   335   }

   336 }

   337 

   338 

   339 void BlockListBuilder::mark_loops() {

   340   ResourceMark rm;

   341 

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

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

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

   345   _next_loop_index = 0;

   346   _next_block_number = _blocks.length();

   347 

   348   // recursively iterate the control flow graph

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

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

   351 }

   352 

   353 void BlockListBuilder::make_loop_header(BlockBegin* block) {

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

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

   356     // since it screws up block ordering.

   357     return;

   358   }

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

   360     block->set(BlockBegin::parser_loop_header_flag);

   361 

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

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

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

   365     if (_next_loop_index < 31) _next_loop_index++;

   366   } else {

   367     // block already marked as loop header

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

   369   }

   370 }

   371 

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

   373   int block_id = block->block_id();

   374 

   375   if (_visited.at(block_id)) {

   376     if (_active.at(block_id)) {

   377       // reached block via backward branch

   378       make_loop_header(block);

   379     }

   380     // return cached loop information for this block

   381     return _loop_map.at(block_id);

   382   }

   383 

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

   385     in_subroutine = true;

   386   }

   387 

   388   // set active and visited bits before successors are processed

   389   _visited.set_bit(block_id);

   390   _active.set_bit(block_id);

   391 

   392   intptr_t loop_state = 0;

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

   394     // recursively process all successors

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

   396   }

   397 

   398   // clear active-bit after all successors are processed

   399   _active.clear_bit(block_id);

   400 

   401   // reverse-post-order numbering of all blocks

   402   block->set_depth_first_number(_next_block_number);

   403   _next_block_number--;

   404 

   405   if (loop_state != 0 || in_subroutine ) {

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

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

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

   409   }

   410 

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

   412     int header_loop_state = _loop_map.at(block_id);

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

   414 

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

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

   417     if (header_loop_state >= 0) {

   418       clear_bits(loop_state, header_loop_state);

   419     }

   420   }

   421 

   422   // cache and return loop information for this block

   423   _loop_map.at_put(block_id, loop_state);

   424   return loop_state;

   425 }

   426 

   427 

   428 #ifndef PRODUCT

   429 

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

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

   432 }

   433 

   434 void BlockListBuilder::print() {

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

   436   method()->print_short_name();

   437   tty->cr();

   438 

   439   // better readability if blocks are sorted in processing order

   440   _blocks.sort(compare_depth_first);

   441 

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

   443     BlockBegin* cur = _blocks.at(i);

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

   445 

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

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

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

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

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

   451 

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

   453       tty->print("    sux: ");

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

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

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

   457       }

   458     }

   459     tty->cr();

   460   }

   461 }

   462 

   463 #endif

   464 

   465 

   466 // A simple growable array of Values indexed by ciFields

   467 class FieldBuffer: public CompilationResourceObj {

   468  private:

   469   GrowableArray<Value> _values;

   470 

   471  public:

   472   FieldBuffer() {}

   473 

   474   void kill() {

   475     _values.trunc_to(0);

   476   }

   477 

   478   Value at(ciField* field) {

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

   480     int offset = field->offset();

   481     if (offset < _values.length()) {

   482       return _values.at(offset);

   483     } else {

   484       return NULL;

   485     }

   486   }

   487 

   488   void at_put(ciField* field, Value value) {

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

   490     int offset = field->offset();

   491     _values.at_put_grow(offset, value, NULL);

   492   }

   493 

   494 };

   495 

   496 

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

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

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

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

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

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

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

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

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

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

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

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

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

   510 // are treated like generic memory.

   511 

   512 class MemoryBuffer: public CompilationResourceObj {

   513  private:

   514   FieldBuffer                 _values;

   515   GrowableArray<Value>        _objects;

   516   GrowableArray<Value>        _newobjects;

   517   GrowableArray<FieldBuffer*> _fields;

   518 

   519  public:

   520   MemoryBuffer() {}

   521 

   522   StoreField* store(StoreField* st) {

   523     if (!EliminateFieldAccess) {

   524       return st;

   525     }

   526 

   527     Value object = st->obj();

   528     Value value = st->value();

   529     ciField* field = st->field();

   530     if (field->holder()->is_loaded()) {

   531       int offset = field->offset();

   532       int index = _newobjects.find(object);

   533       if (index != -1) {

   534         // newly allocated object with no other stores performed on this field

   535         FieldBuffer* buf = _fields.at(index);

   536         if (buf->at(field) == NULL && is_default_value(value)) {

   537 #ifndef PRODUCT

   538           if (PrintIRDuringConstruction && Verbose) {

   539             tty->print_cr("Eliminated store for object %d:", index);

   540             st->print_line();

   541           }

   542 #endif

   543           return NULL;

   544         } else {

   545           buf->at_put(field, value);

   546         }

   547       } else {

   548         _objects.at_put_grow(offset, object, NULL);

   549         _values.at_put(field, value);

   550       }

   551 

   552       store_value(value);

   553     } else {

   554       // if we held onto field names we could alias based on names but

   555       // we don't know what's being stored to so kill it all.

   556       kill();

   557     }

   558     return st;

   559   }

   560 

   561 

   562   // return true if this value correspond to the default value of a field.

   563   bool is_default_value(Value value) {

   564     Constant* con = value->as_Constant();

   565     if (con) {

   566       switch (con->type()->tag()) {

   567         case intTag:    return con->type()->as_IntConstant()->value() == 0;

   568         case longTag:   return con->type()->as_LongConstant()->value() == 0;

   569         case floatTag:  return jint_cast(con->type()->as_FloatConstant()->value()) == 0;

   570         case doubleTag: return jlong_cast(con->type()->as_DoubleConstant()->value()) == jlong_cast(0);

   571         case objectTag: return con->type() == objectNull;

   572         default:  ShouldNotReachHere();

   573       }

   574     }

   575     return false;

   576   }

   577 

   578 

   579   // return either the actual value of a load or the load itself

   580   Value load(LoadField* load) {

   581     if (!EliminateFieldAccess) {

   582       return load;

   583     }

   584 

   585     if (RoundFPResults && UseSSE < 2 && load->type()->is_float_kind()) {

   586       // can't skip load since value might get rounded as a side effect

   587       return load;

   588     }

   589 

   590     ciField* field = load->field();

   591     Value object   = load->obj();

   592     if (field->holder()->is_loaded() && !field->is_volatile()) {

   593       int offset = field->offset();

   594       Value result = NULL;

   595       int index = _newobjects.find(object);

   596       if (index != -1) {

   597         result = _fields.at(index)->at(field);

   598       } else if (_objects.at_grow(offset, NULL) == object) {

   599         result = _values.at(field);

   600       }

   601       if (result != NULL) {

   602 #ifndef PRODUCT

   603         if (PrintIRDuringConstruction && Verbose) {

   604           tty->print_cr("Eliminated load: ");

   605           load->print_line();

   606         }

   607 #endif

   608         assert(result->type()->tag() == load->type()->tag(), "wrong types");

   609         return result;

   610       }

   611     }

   612     return load;

   613   }

   614 

   615   // Record this newly allocated object

   616   void new_instance(NewInstance* object) {

   617     int index = _newobjects.length();

   618     _newobjects.append(object);

   619     if (_fields.at_grow(index, NULL) == NULL) {

   620       _fields.at_put(index, new FieldBuffer());

   621     } else {

   622       _fields.at(index)->kill();

   623     }

   624   }

   625 

   626   void store_value(Value value) {

   627     int index = _newobjects.find(value);

   628     if (index != -1) {

   629       // stored a newly allocated object into another object.

   630       // Assume we've lost track of it as separate slice of memory.

   631       // We could do better by keeping track of whether individual

   632       // fields could alias each other.

   633       _newobjects.remove_at(index);

   634       // pull out the field info and store it at the end up the list

   635       // of field info list to be reused later.

   636       _fields.append(_fields.at(index));

   637       _fields.remove_at(index);

   638     }

   639   }

   640 

   641   void kill() {

   642     _newobjects.trunc_to(0);

   643     _objects.trunc_to(0);

   644     _values.kill();

   645   }

   646 };

   647 

   648 

   649 // Implementation of GraphBuilder's ScopeData

   650 

   651 GraphBuilder::ScopeData::ScopeData(ScopeData* parent)

   652   : _parent(parent)

   653   , _bci2block(NULL)

   654   , _scope(NULL)

   655   , _has_handler(false)

   656   , _stream(NULL)

   657   , _work_list(NULL)

   658   , _parsing_jsr(false)

   659   , _jsr_xhandlers(NULL)

   660   , _caller_stack_size(-1)

   661   , _continuation(NULL)

   662   , _continuation_state(NULL)

   663   , _num_returns(0)

   664   , _cleanup_block(NULL)

   665   , _cleanup_return_prev(NULL)

   666   , _cleanup_state(NULL)

   667 {

   668   if (parent != NULL) {

   669     _max_inline_size = (intx) ((float) NestedInliningSizeRatio * (float) parent->max_inline_size() / 100.0f);

   670   } else {

   671     _max_inline_size = MaxInlineSize;

   672   }

   673   if (_max_inline_size < MaxTrivialSize) {

   674     _max_inline_size = MaxTrivialSize;

   675   }

   676 }

   677 

   678 

   679 void GraphBuilder::kill_field(ciField* field) {

   680   if (UseLocalValueNumbering) {

   681     vmap()->kill_field(field);

   682   }

   683 }

   684 

   685 

   686 void GraphBuilder::kill_array(Value value) {

   687   if (UseLocalValueNumbering) {

   688     vmap()->kill_array(value->type());

   689   }

   690   _memory->store_value(value);

   691 }

   692 

   693 

   694 void GraphBuilder::kill_all() {

   695   if (UseLocalValueNumbering) {

   696     vmap()->kill_all();

   697   }

   698   _memory->kill();

   699 }

   700 

   701 

   702 BlockBegin* GraphBuilder::ScopeData::block_at(int bci) {

   703   if (parsing_jsr()) {

   704     // It is necessary to clone all blocks associated with a

   705     // subroutine, including those for exception handlers in the scope

   706     // of the method containing the jsr (because those exception

   707     // handlers may contain ret instructions in some cases).

   708     BlockBegin* block = bci2block()->at(bci);

   709     if (block != NULL && block == parent()->bci2block()->at(bci)) {

   710       BlockBegin* new_block = new BlockBegin(block->bci());

   711 #ifndef PRODUCT

   712       if (PrintInitialBlockList) {

   713         tty->print_cr("CFG: cloned block %d (bci %d) as block %d for jsr",

   714                       block->block_id(), block->bci(), new_block->block_id());

   715       }

   716 #endif

   717       // copy data from cloned blocked

   718       new_block->set_depth_first_number(block->depth_first_number());

   719       if (block->is_set(BlockBegin::parser_loop_header_flag)) new_block->set(BlockBegin::parser_loop_header_flag);

   720       // Preserve certain flags for assertion checking

   721       if (block->is_set(BlockBegin::subroutine_entry_flag)) new_block->set(BlockBegin::subroutine_entry_flag);

   722       if (block->is_set(BlockBegin::exception_entry_flag))  new_block->set(BlockBegin::exception_entry_flag);

   723 

   724       // copy was_visited_flag to allow early detection of bailouts

   725       // if a block that is used in a jsr has already been visited before,

   726       // it is shared between the normal control flow and a subroutine

   727       // BlockBegin::try_merge returns false when the flag is set, this leads

   728       // to a compilation bailout

   729       if (block->is_set(BlockBegin::was_visited_flag))  new_block->set(BlockBegin::was_visited_flag);

   730 

   731       bci2block()->at_put(bci, new_block);

   732       block = new_block;

   733     }

   734     return block;

   735   } else {

   736     return bci2block()->at(bci);

   737   }

   738 }

   739 

   740 

   741 XHandlers* GraphBuilder::ScopeData::xhandlers() const {

   742   if (_jsr_xhandlers == NULL) {

   743     assert(!parsing_jsr(), "");

   744     return scope()->xhandlers();

   745   }

   746   assert(parsing_jsr(), "");

   747   return _jsr_xhandlers;

   748 }

   749 

   750 

   751 void GraphBuilder::ScopeData::set_scope(IRScope* scope) {

   752   _scope = scope;

   753   bool parent_has_handler = false;

   754   if (parent() != NULL) {

   755     parent_has_handler = parent()->has_handler();

   756   }

   757   _has_handler = parent_has_handler || scope->xhandlers()->has_handlers();

   758 }

   759 

   760 

   761 void GraphBuilder::ScopeData::set_inline_cleanup_info(BlockBegin* block,

   762                                                       Instruction* return_prev,

   763                                                       ValueStack* return_state) {

   764   _cleanup_block       = block;

   765   _cleanup_return_prev = return_prev;

   766   _cleanup_state       = return_state;

   767 }

   768 

   769 

   770 void GraphBuilder::ScopeData::add_to_work_list(BlockBegin* block) {

   771   if (_work_list == NULL) {

   772     _work_list = new BlockList();

   773   }

   774 

   775   if (!block->is_set(BlockBegin::is_on_work_list_flag)) {

   776     // Do not start parsing the continuation block while in a

   777     // sub-scope

   778     if (parsing_jsr()) {

   779       if (block == jsr_continuation()) {

   780         return;

   781       }

   782     } else {

   783       if (block == continuation()) {

   784         return;

   785       }

   786     }

   787     block->set(BlockBegin::is_on_work_list_flag);

   788     _work_list->push(block);

   789 

   790     sort_top_into_worklist(_work_list, block);

   791   }

   792 }

   793 

   794 

   795 void GraphBuilder::sort_top_into_worklist(BlockList* worklist, BlockBegin* top) {

   796   assert(worklist->top() == top, "");

   797   // sort block descending into work list

   798   const int dfn = top->depth_first_number();

   799   assert(dfn != -1, "unknown depth first number");

   800   int i = worklist->length()-2;

   801   while (i >= 0) {

   802     BlockBegin* b = worklist->at(i);

   803     if (b->depth_first_number() < dfn) {

   804       worklist->at_put(i+1, b);

   805     } else {

   806       break;

   807     }

   808     i --;

   809   }

   810   if (i >= -1) worklist->at_put(i + 1, top);

   811 }

   812 

   813 int GraphBuilder::ScopeData::caller_stack_size() const {

   814   ValueStack* state = scope()->caller_state();

   815   if (state == NULL) {

   816     return 0;

   817   }

   818   return state->stack_size();

   819 }

   820 

   821 

   822 BlockBegin* GraphBuilder::ScopeData::remove_from_work_list() {

   823   if (is_work_list_empty()) {

   824     return NULL;

   825   }

   826   return _work_list->pop();

   827 }

   828 

   829 

   830 bool GraphBuilder::ScopeData::is_work_list_empty() const {

   831   return (_work_list == NULL || _work_list->length() == 0);

   832 }

   833 

   834 

   835 void GraphBuilder::ScopeData::setup_jsr_xhandlers() {

   836   assert(parsing_jsr(), "");

   837   // clone all the exception handlers from the scope

   838   XHandlers* handlers = new XHandlers(scope()->xhandlers());

   839   const int n = handlers->length();

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

   841     // The XHandlers need to be adjusted to dispatch to the cloned

   842     // handler block instead of the default one but the synthetic

   843     // unlocker needs to be handled specially.  The synthetic unlocker

   844     // should be left alone since there can be only one and all code

   845     // should dispatch to the same one.

   846     XHandler* h = handlers->handler_at(i);

   847     if (h->handler_bci() != SynchronizationEntryBCI) {

   848       h->set_entry_block(block_at(h->handler_bci()));

   849     } else {

   850       assert(h->entry_block()->is_set(BlockBegin::default_exception_handler_flag),

   851              "should be the synthetic unlock block");

   852     }

   853   }

   854   _jsr_xhandlers = handlers;

   855 }

   856 

   857 

   858 int GraphBuilder::ScopeData::num_returns() {

   859   if (parsing_jsr()) {

   860     return parent()->num_returns();

   861   }

   862   return _num_returns;

   863 }

   864 

   865 

   866 void GraphBuilder::ScopeData::incr_num_returns() {

   867   if (parsing_jsr()) {

   868     parent()->incr_num_returns();

   869   } else {

   870     ++_num_returns;

   871   }

   872 }

   873 

   874 

   875 // Implementation of GraphBuilder

   876 

   877 #define INLINE_BAILOUT(msg)        { inline_bailout(msg); return false; }

   878 

   879 

   880 void GraphBuilder::load_constant() {

   881   ciConstant con = stream()->get_constant();

   882   if (con.basic_type() == T_ILLEGAL) {

   883     BAILOUT("could not resolve a constant");

   884   } else {

   885     ValueType* t = illegalType;

   886     ValueStack* patch_state = NULL;

   887     switch (con.basic_type()) {

   888       case T_BOOLEAN: t = new IntConstant     (con.as_boolean()); break;

   889       case T_BYTE   : t = new IntConstant     (con.as_byte   ()); break;

   890       case T_CHAR   : t = new IntConstant     (con.as_char   ()); break;

   891       case T_SHORT  : t = new IntConstant     (con.as_short  ()); break;

   892       case T_INT    : t = new IntConstant     (con.as_int    ()); break;

   893       case T_LONG   : t = new LongConstant    (con.as_long   ()); break;

   894       case T_FLOAT  : t = new FloatConstant   (con.as_float  ()); break;

   895       case T_DOUBLE : t = new DoubleConstant  (con.as_double ()); break;

   896       case T_ARRAY  : t = new ArrayConstant   (con.as_object ()->as_array   ()); break;

   897       case T_OBJECT :

   898        {

   899         ciObject* obj = con.as_object();

   900         if (obj->is_klass()) {

   901           ciKlass* klass = obj->as_klass();

   902           if (!klass->is_loaded() || PatchALot) {

   903             patch_state = state()->copy();

   904             t = new ObjectConstant(obj);

   905           } else {

   906             t = new InstanceConstant(klass->java_mirror());

   907           }

   908         } else {

   909           t = new InstanceConstant(obj->as_instance());

   910         }

   911         break;

   912        }

   913       default       : ShouldNotReachHere();

   914     }

   915     Value x;

   916     if (patch_state != NULL) {

   917       x = new Constant(t, patch_state);

   918     } else {

   919       x = new Constant(t);

   920     }

   921     push(t, append(x));

   922   }

   923 }

   924 

   925 

   926 void GraphBuilder::load_local(ValueType* type, int index) {

   927   Value x = state()->load_local(index);

   928   push(type, x);

   929 }

   930 

   931 

   932 void GraphBuilder::store_local(ValueType* type, int index) {

   933   Value x = pop(type);

   934   store_local(state(), x, type, index);

   935 }

   936 

   937 

   938 void GraphBuilder::store_local(ValueStack* state, Value x, ValueType* type, int index) {

   939   if (parsing_jsr()) {

   940     // We need to do additional tracking of the location of the return

   941     // address for jsrs since we don't handle arbitrary jsr/ret

   942     // constructs. Here we are figuring out in which circumstances we

   943     // need to bail out.

   944     if (x->type()->is_address()) {

   945       scope_data()->set_jsr_return_address_local(index);

   946 

   947       // Also check parent jsrs (if any) at this time to see whether

   948       // they are using this local. We don't handle skipping over a

   949       // ret.

   950       for (ScopeData* cur_scope_data = scope_data()->parent();

   951            cur_scope_data != NULL && cur_scope_data->parsing_jsr() && cur_scope_data->scope() == scope();

   952            cur_scope_data = cur_scope_data->parent()) {

   953         if (cur_scope_data->jsr_return_address_local() == index) {

   954           BAILOUT("subroutine overwrites return address from previous subroutine");

   955         }

   956       }

   957     } else if (index == scope_data()->jsr_return_address_local()) {

   958       scope_data()->set_jsr_return_address_local(-1);

   959     }

   960   }

   961 

   962   state->store_local(index, round_fp(x));

   963 }

   964 

   965 

   966 void GraphBuilder::load_indexed(BasicType type) {

   967   Value index = ipop();

   968   Value array = apop();

   969   Value length = NULL;

   970   if (CSEArrayLength ||

   971       (array->as_AccessField() && array->as_AccessField()->field()->is_constant()) ||

   972       (array->as_NewArray() && array->as_NewArray()->length() && array->as_NewArray()->length()->type()->is_constant())) {

   973     length = append(new ArrayLength(array, lock_stack()));

   974   }

   975   push(as_ValueType(type), append(new LoadIndexed(array, index, length, type, lock_stack())));

   976 }

   977 

   978 

   979 void GraphBuilder::store_indexed(BasicType type) {

   980   Value value = pop(as_ValueType(type));

   981   Value index = ipop();

   982   Value array = apop();

   983   Value length = NULL;

   984   if (CSEArrayLength ||

   985       (array->as_AccessField() && array->as_AccessField()->field()->is_constant()) ||

   986       (array->as_NewArray() && array->as_NewArray()->length() && array->as_NewArray()->length()->type()->is_constant())) {

   987     length = append(new ArrayLength(array, lock_stack()));

   988   }

   989   StoreIndexed* result = new StoreIndexed(array, index, length, type, value, lock_stack());

   990   kill_array(value); // invalidate all CSEs that are memory accesses of the same type

   991   append(result);

   992 }

   993 

   994 

   995 void GraphBuilder::stack_op(Bytecodes::Code code) {

   996   switch (code) {

   997     case Bytecodes::_pop:

   998       { state()->raw_pop();

   999       }

  1000       break;

  1001     case Bytecodes::_pop2:

  1002       { state()->raw_pop();

  1003         state()->raw_pop();

  1004       }

  1005       break;

  1006     case Bytecodes::_dup:

  1007       { Value w = state()->raw_pop();

  1008         state()->raw_push(w);

  1009         state()->raw_push(w);

  1010       }

  1011       break;

  1012     case Bytecodes::_dup_x1:

  1013       { Value w1 = state()->raw_pop();

  1014         Value w2 = state()->raw_pop();

  1015         state()->raw_push(w1);

  1016         state()->raw_push(w2);

  1017         state()->raw_push(w1);

  1018       }

  1019       break;

  1020     case Bytecodes::_dup_x2:

  1021       { Value w1 = state()->raw_pop();

  1022         Value w2 = state()->raw_pop();

  1023         Value w3 = state()->raw_pop();

  1024         state()->raw_push(w1);

  1025         state()->raw_push(w3);

  1026         state()->raw_push(w2);

  1027         state()->raw_push(w1);

  1028       }

  1029       break;

  1030     case Bytecodes::_dup2:

  1031       { Value w1 = state()->raw_pop();

  1032         Value w2 = state()->raw_pop();

  1033         state()->raw_push(w2);

  1034         state()->raw_push(w1);

  1035         state()->raw_push(w2);

  1036         state()->raw_push(w1);

  1037       }

  1038       break;

  1039     case Bytecodes::_dup2_x1:

  1040       { Value w1 = state()->raw_pop();

  1041         Value w2 = state()->raw_pop();

  1042         Value w3 = state()->raw_pop();

  1043         state()->raw_push(w2);

  1044         state()->raw_push(w1);

  1045         state()->raw_push(w3);

  1046         state()->raw_push(w2);

  1047         state()->raw_push(w1);

  1048       }

  1049       break;

  1050     case Bytecodes::_dup2_x2:

  1051       { Value w1 = state()->raw_pop();

  1052         Value w2 = state()->raw_pop();

  1053         Value w3 = state()->raw_pop();

  1054         Value w4 = state()->raw_pop();

  1055         state()->raw_push(w2);

  1056         state()->raw_push(w1);

  1057         state()->raw_push(w4);

  1058         state()->raw_push(w3);

  1059         state()->raw_push(w2);

  1060         state()->raw_push(w1);

  1061       }

  1062       break;

  1063     case Bytecodes::_swap:

  1064       { Value w1 = state()->raw_pop();

  1065         Value w2 = state()->raw_pop();

  1066         state()->raw_push(w1);

  1067         state()->raw_push(w2);

  1068       }

  1069       break;

  1070     default:

  1071       ShouldNotReachHere();

  1072       break;

  1073   }

  1074 }

  1075 

  1076 

  1077 void GraphBuilder::arithmetic_op(ValueType* type, Bytecodes::Code code, ValueStack* stack) {

  1078   Value y = pop(type);

  1079   Value x = pop(type);

  1080   // NOTE: strictfp can be queried from current method since we don't

  1081   // inline methods with differing strictfp bits

  1082   Value res = new ArithmeticOp(code, x, y, method()->is_strict(), stack);

  1083   // Note: currently single-precision floating-point rounding on Intel is handled at the LIRGenerator level

  1084   res = append(res);

  1085   if (method()->is_strict()) {

  1086     res = round_fp(res);

  1087   }

  1088   push(type, res);

  1089 }

  1090 

  1091 

  1092 void GraphBuilder::negate_op(ValueType* type) {

  1093   push(type, append(new NegateOp(pop(type))));

  1094 }

  1095 

  1096 

  1097 void GraphBuilder::shift_op(ValueType* type, Bytecodes::Code code) {

  1098   Value s = ipop();

  1099   Value x = pop(type);

  1100   // try to simplify

  1101   // Note: This code should go into the canonicalizer as soon as it can

  1102   //       can handle canonicalized forms that contain more than one node.

  1103   if (CanonicalizeNodes && code == Bytecodes::_iushr) {

  1104     // pattern: x >>> s

  1105     IntConstant* s1 = s->type()->as_IntConstant();

  1106     if (s1 != NULL) {

  1107       // pattern: x >>> s1, with s1 constant

  1108       ShiftOp* l = x->as_ShiftOp();

  1109       if (l != NULL && l->op() == Bytecodes::_ishl) {

  1110         // pattern: (a << b) >>> s1

  1111         IntConstant* s0 = l->y()->type()->as_IntConstant();

  1112         if (s0 != NULL) {

  1113           // pattern: (a << s0) >>> s1

  1114           const int s0c = s0->value() & 0x1F; // only the low 5 bits are significant for shifts

  1115           const int s1c = s1->value() & 0x1F; // only the low 5 bits are significant for shifts

  1116           if (s0c == s1c) {

  1117             if (s0c == 0) {

  1118               // pattern: (a << 0) >>> 0 => simplify to: a

  1119               ipush(l->x());

  1120             } else {

  1121               // pattern: (a << s0c) >>> s0c => simplify to: a & m, with m constant

  1122               assert(0 < s0c && s0c < BitsPerInt, "adjust code below to handle corner cases");

  1123               const int m = (1 << (BitsPerInt - s0c)) - 1;

  1124               Value s = append(new Constant(new IntConstant(m)));

  1125               ipush(append(new LogicOp(Bytecodes::_iand, l->x(), s)));

  1126             }

  1127             return;

  1128           }

  1129         }

  1130       }

  1131     }

  1132   }

  1133   // could not simplify

  1134   push(type, append(new ShiftOp(code, x, s)));

  1135 }