duke@435: /*
xdono@1279:  * Copyright 2006-2009 Sun Microsystems, Inc.  All Rights Reserved.
duke@435:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435:  *
duke@435:  * This code is free software; you can redistribute it and/or modify it
duke@435:  * under the terms of the GNU General Public License version 2 only, as
duke@435:  * published by the Free Software Foundation.
duke@435:  *
duke@435:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@435:  * version 2 for more details (a copy is included in the LICENSE file that
duke@435:  * accompanied this code).
duke@435:  *
duke@435:  * You should have received a copy of the GNU General Public License version
duke@435:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@435:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435:  *
duke@435:  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@435:  * CA 95054 USA or visit www.sun.com if you need additional information or
duke@435:  * have any questions.
duke@435:  *
duke@435:  */
duke@435: 
duke@435: #include "incls/_precompiled.incl"
duke@435: #include "incls/_ciMethodBlocks.cpp.incl"
duke@435: 
duke@435: // ciMethodBlocks
duke@435: 
duke@435: 
duke@435: 
duke@435: ciBlock *ciMethodBlocks::block_containing(int bci) {
duke@435:   ciBlock *blk = _bci_to_block[bci];
duke@435:   return blk;
duke@435: }
duke@435: 
duke@435: bool ciMethodBlocks::is_block_start(int bci) {
duke@435:   assert(bci >=0 && bci < _code_size, "valid bytecode range");
duke@435:   ciBlock *b = _bci_to_block[bci];
duke@435:   assert(b != NULL, "must have block for bytecode");
duke@435:   return b->start_bci() == bci;
duke@435: }
duke@435: 
duke@435: // ------------------------------------------------------------------
duke@435: // ciMethodBlocks::split_block_at
duke@435: //
duke@435: // Split the block spanning bci into two separate ranges.  The former
duke@435: // block becomes the second half and a new range is created for the
duke@435: // first half.  Returns the range beginning at bci.
duke@435: ciBlock *ciMethodBlocks::split_block_at(int bci) {
duke@435:   ciBlock *former_block = block_containing(bci);
never@802:   ciBlock *new_block = new(_arena) ciBlock(_method, _num_blocks++, former_block->start_bci());
duke@435:   _blocks->append(new_block);
duke@435:   assert(former_block != NULL, "must not be NULL");
duke@435:   new_block->set_limit_bci(bci);
duke@435:   former_block->set_start_bci(bci);
duke@435:   for (int pos=bci-1; pos >= 0; pos--) {
duke@435:     ciBlock *current_block = block_containing(pos);
duke@435:     if (current_block == former_block) {
duke@435:       // Replace it.
duke@435:       _bci_to_block[pos] = new_block;
duke@435:     } else if (current_block == NULL) {
duke@435:       // Non-bytecode start.  Skip.
duke@435:       continue;
duke@435:     } else {
duke@435:       // We are done with our backwards walk
duke@435:       break;
duke@435:     }
duke@435:   }
kvn@461:   // Move an exception handler information if needed.
kvn@461:   if (former_block->is_handler()) {
kvn@461:     int ex_start = former_block->ex_start_bci();
kvn@461:     int ex_end = former_block->ex_limit_bci();
kvn@461:     new_block->set_exception_range(ex_start, ex_end);
kvn@461:     // Clear information in former_block.
kvn@461:     former_block->clear_exception_handler();
kvn@461:   }
duke@435:   return former_block;
duke@435: }
duke@435: 
duke@435: ciBlock *ciMethodBlocks::make_block_at(int bci) {
duke@435:   ciBlock *cb = block_containing(bci);
duke@435:   if (cb == NULL ) {
duke@435:     // This is our first time visiting this bytecode.  Create
duke@435:     // a fresh block and assign it this starting point.
never@802:     ciBlock *nb = new(_arena) ciBlock(_method, _num_blocks++, bci);
duke@435:     _blocks->append(nb);
duke@435:      _bci_to_block[bci] = nb;
duke@435:     return nb;
duke@435:   } else if (cb->start_bci() == bci) {
duke@435:     // The block begins at bci.  Simply return it.
duke@435:     return cb;
duke@435:   } else {
duke@435:     // We have already created a block containing bci but
duke@435:     // not starting at bci.  This existing block needs to
duke@435:     // be split into two.
duke@435:     return split_block_at(bci);
duke@435:   }
duke@435: }
duke@435: 
never@802: ciBlock *ciMethodBlocks::make_dummy_block() {
never@802:   ciBlock *dum = new(_arena) ciBlock(_method, -1, 0);
never@802:   return dum;
never@802: }
never@802: 
duke@435: void ciMethodBlocks::do_analysis() {
duke@435:   ciBytecodeStream s(_method);
duke@435:   ciBlock *cur_block = block_containing(0);
duke@435:   int limit_bci = _method->code_size();
duke@435: 
duke@435:   while (s.next() != ciBytecodeStream::EOBC()) {
duke@435:     int bci = s.cur_bci();
duke@435:     // Determine if a new block has been made at the current bci.  If
duke@435:     // this block differs from our current range, switch to the new
duke@435:     // one and end the old one.
duke@435:     assert(cur_block != NULL, "must always have a current block");
duke@435:     ciBlock *new_block = block_containing(bci);
kvn@461:     if (new_block == NULL || new_block == cur_block) {
duke@435:       // We have not marked this bci as the start of a new block.
duke@435:       // Keep interpreting the current_range.
duke@435:       _bci_to_block[bci] = cur_block;
duke@435:     } else {
duke@435:       cur_block->set_limit_bci(bci);
duke@435:       cur_block = new_block;
duke@435:     }
duke@435: 
duke@435:     switch (s.cur_bc()) {
duke@435:       case Bytecodes::_ifeq        :
duke@435:       case Bytecodes::_ifne        :
duke@435:       case Bytecodes::_iflt        :
duke@435:       case Bytecodes::_ifge        :
duke@435:       case Bytecodes::_ifgt        :
duke@435:       case Bytecodes::_ifle        :
duke@435:       case Bytecodes::_if_icmpeq   :
duke@435:       case Bytecodes::_if_icmpne   :
duke@435:       case Bytecodes::_if_icmplt   :
duke@435:       case Bytecodes::_if_icmpge   :
duke@435:       case Bytecodes::_if_icmpgt   :
duke@435:       case Bytecodes::_if_icmple   :
duke@435:       case Bytecodes::_if_acmpeq   :
duke@435:       case Bytecodes::_if_acmpne   :
duke@435:       case Bytecodes::_ifnull      :
duke@435:       case Bytecodes::_ifnonnull   :
duke@435:       {
duke@435:         cur_block->set_control_bci(bci);
duke@435:         ciBlock *fall_through = make_block_at(s.next_bci());
duke@435:         int dest_bci = s.get_dest();
duke@435:         ciBlock *dest = make_block_at(dest_bci);
duke@435:         break;
duke@435:       }
duke@435: 
duke@435:       case Bytecodes::_goto        :
duke@435:       {
duke@435:         cur_block->set_control_bci(bci);
duke@435:         if (s.next_bci() < limit_bci) {
duke@435:           (void) make_block_at(s.next_bci());
duke@435:         }
duke@435:         int dest_bci = s.get_dest();
duke@435:         ciBlock *dest = make_block_at(dest_bci);
duke@435:         break;
duke@435:       }
duke@435: 
duke@435:       case Bytecodes::_jsr         :
duke@435:       {
duke@435:         cur_block->set_control_bci(bci);
duke@435:         ciBlock *ret = make_block_at(s.next_bci());
duke@435:         int dest_bci = s.get_dest();
duke@435:         ciBlock *dest = make_block_at(dest_bci);
duke@435:         break;
duke@435:       }
duke@435: 
duke@435:       case Bytecodes::_tableswitch :
duke@435:         {
duke@435:           cur_block->set_control_bci(bci);
duke@435:           Bytecode_tableswitch* switch_ = Bytecode_tableswitch_at(s.cur_bcp());
duke@435:           int len = switch_->length();
duke@435:           ciBlock *dest;
duke@435:           int dest_bci;
duke@435:           for (int i = 0; i < len; i++) {
duke@435:             dest_bci = s.cur_bci() + switch_->dest_offset_at(i);
duke@435:             dest = make_block_at(dest_bci);
duke@435:           }
duke@435:           dest_bci = s.cur_bci() + switch_->default_offset();
duke@435:           make_block_at(dest_bci);
duke@435:           if (s.next_bci() < limit_bci) {
duke@435:             dest = make_block_at(s.next_bci());
duke@435:           }
duke@435:         }
duke@435:         break;
duke@435: 
duke@435:       case Bytecodes::_lookupswitch:
duke@435:         {
duke@435:           cur_block->set_control_bci(bci);
duke@435:           Bytecode_lookupswitch* switch_ = Bytecode_lookupswitch_at(s.cur_bcp());
duke@435:           int len = switch_->number_of_pairs();
duke@435:           ciBlock *dest;
duke@435:           int dest_bci;
duke@435:           for (int i = 0; i < len; i++) {
duke@435:             dest_bci = s.cur_bci() + switch_->pair_at(i)->offset();
duke@435:             dest = make_block_at(dest_bci);
duke@435:           }
duke@435:           dest_bci = s.cur_bci() + switch_->default_offset();
duke@435:           dest = make_block_at(dest_bci);
duke@435:           if (s.next_bci() < limit_bci) {
duke@435:             dest = make_block_at(s.next_bci());
duke@435:           }
duke@435:         }
duke@435:         break;
duke@435: 
duke@435:       case Bytecodes::_goto_w      :
duke@435:       {
duke@435:         cur_block->set_control_bci(bci);
duke@435:         if (s.next_bci() < limit_bci) {
duke@435:           (void) make_block_at(s.next_bci());
duke@435:         }
duke@435:         int dest_bci = s.get_far_dest();
duke@435:         ciBlock *dest = make_block_at(dest_bci);
duke@435:         break;
duke@435:       }
duke@435: 
duke@435:       case Bytecodes::_jsr_w       :
duke@435:       {
duke@435:         cur_block->set_control_bci(bci);
duke@435:         ciBlock *ret = make_block_at(s.next_bci());
duke@435:         int dest_bci = s.get_far_dest();
duke@435:         ciBlock *dest = make_block_at(dest_bci);
duke@435:         break;
duke@435:       }
duke@435: 
duke@435:       case Bytecodes::_athrow      :
duke@435:         cur_block->set_may_throw();
duke@435:         // fall-through
duke@435:       case Bytecodes::_ret         :
duke@435:       case Bytecodes::_ireturn     :
duke@435:       case Bytecodes::_lreturn     :
duke@435:       case Bytecodes::_freturn     :
duke@435:       case Bytecodes::_dreturn     :
duke@435:       case Bytecodes::_areturn     :
duke@435:       case Bytecodes::_return      :
duke@435:         cur_block->set_control_bci(bci);
duke@435:         if (s.next_bci() < limit_bci) {
duke@435:           (void) make_block_at(s.next_bci());
duke@435:         }
duke@435:         break;
duke@435:     }
duke@435:   }
duke@435:   //  End the last block
duke@435:   cur_block->set_limit_bci(limit_bci);
duke@435: }
duke@435: 
duke@435: ciMethodBlocks::ciMethodBlocks(Arena *arena, ciMethod *meth): _method(meth),
duke@435:                           _arena(arena), _num_blocks(0), _code_size(meth->code_size()) {
duke@435:   int block_estimate = _code_size / 8;
duke@435: 
duke@435:   _blocks =  new(_arena) GrowableArray<ciBlock *>(block_estimate);
duke@435:   int b2bsize = _code_size * sizeof(ciBlock **);
duke@435:   _bci_to_block = (ciBlock **) arena->Amalloc(b2bsize);
duke@435:   Copy::zero_to_words((HeapWord*) _bci_to_block, b2bsize / sizeof(HeapWord));
duke@435: 
duke@435:   // create initial block covering the entire method
never@802:   ciBlock *b = new(arena) ciBlock(_method, _num_blocks++, 0);
duke@435:   _blocks->append(b);
duke@435:   _bci_to_block[0] = b;
duke@435: 
duke@435:   // create blocks for exception handlers
duke@435:   if (meth->has_exception_handlers()) {
duke@435:     for(ciExceptionHandlerStream str(meth); !str.is_done(); str.next()) {
duke@435:       ciExceptionHandler* handler = str.handler();
duke@435:       ciBlock *eb = make_block_at(handler->handler_bci());
kvn@461:       //
kvn@461:       // Several exception handlers can have the same handler_bci:
kvn@461:       //
kvn@461:       //  try {
kvn@461:       //    if (a.foo(b) < 0) {
kvn@461:       //      return a.error();
kvn@461:       //    }
kvn@461:       //    return CoderResult.UNDERFLOW;
kvn@461:       //  } finally {
kvn@461:       //      a.position(b);
kvn@461:       //  }
kvn@461:       //
kvn@461:       //  The try block above is divided into 2 exception blocks
kvn@461:       //  separated by 'areturn' bci.
kvn@461:       //
duke@435:       int ex_start = handler->start();
duke@435:       int ex_end = handler->limit();
kvn@1081:       // ensure a block at the start of exception range and start of following code
kvn@1081:       (void) make_block_at(ex_start);
kvn@1081:       if (ex_end < _code_size)
kvn@1081:         (void) make_block_at(ex_end);
kvn@1081: 
kvn@461:       if (eb->is_handler()) {
kvn@461:         // Extend old handler exception range to cover additional range.
kvn@461:         int old_ex_start = eb->ex_start_bci();
kvn@461:         int old_ex_end   = eb->ex_limit_bci();
kvn@461:         if (ex_start > old_ex_start)
kvn@461:           ex_start = old_ex_start;
kvn@461:         if (ex_end < old_ex_end)
kvn@461:           ex_end = old_ex_end;
kvn@461:         eb->clear_exception_handler(); // Reset exception information
kvn@461:       }
duke@435:       eb->set_exception_range(ex_start, ex_end);
duke@435:     }
duke@435:   }
duke@435: 
duke@435:   // scan the bytecodes and identify blocks
duke@435:   do_analysis();
duke@435: 
duke@435:   // mark blocks that have exception handlers
duke@435:   if (meth->has_exception_handlers()) {
duke@435:     for(ciExceptionHandlerStream str(meth); !str.is_done(); str.next()) {
duke@435:       ciExceptionHandler* handler = str.handler();
duke@435:       int ex_start = handler->start();
duke@435:       int ex_end = handler->limit();
duke@435: 
duke@435:       int bci = ex_start;
duke@435:       while (bci < ex_end) {
duke@435:         ciBlock *b = block_containing(bci);
duke@435:         b->set_has_handler();
duke@435:         bci = b->limit_bci();
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ciMethodBlocks::clear_processed() {
duke@435:   for (int i = 0; i < _blocks->length(); i++)
duke@435:     _blocks->at(i)->clear_processed();
duke@435: }
duke@435: 
duke@435: #ifndef PRODUCT
duke@435: void ciMethodBlocks::dump() {
duke@435:   tty->print("---- blocks for method: ");
duke@435:   _method->print();
duke@435:   tty->cr();
duke@435:   for (int i = 0; i < _blocks->length(); i++) {
duke@435:     tty->print("  B%d: ", i); _blocks->at(i)->dump();
duke@435:   }
duke@435: }
duke@435: #endif
duke@435: 
duke@435: 
never@802: ciBlock::ciBlock(ciMethod *method, int index, int start_bci) :
duke@435: #ifndef PRODUCT
duke@435:                          _method(method),
duke@435: #endif
duke@435:                          _idx(index), _flags(0), _start_bci(start_bci), _limit_bci(-1), _control_bci(fall_through_bci),
duke@435:                          _ex_start_bci(-1), _ex_limit_bci(-1) {
duke@435: }
duke@435: 
duke@435: void ciBlock::set_exception_range(int start_bci, int limit_bci)  {
duke@435:    assert(limit_bci >= start_bci, "valid range");
kvn@461:    assert(!is_handler() && _ex_start_bci == -1 && _ex_limit_bci == -1, "must not be handler");
duke@435:    _ex_start_bci = start_bci;
duke@435:    _ex_limit_bci = limit_bci;
kvn@461:    set_handler();
duke@435: }
duke@435: 
duke@435: #ifndef PRODUCT
never@685: static const char *flagnames[] = {
duke@435:   "Processed",
duke@435:   "Handler",
duke@435:   "MayThrow",
duke@435:   "Jsr",
duke@435:   "Ret",
duke@435:   "RetTarget",
duke@435:   "HasHandler",
duke@435: };
duke@435: 
duke@435: void ciBlock::dump() {
duke@435:   tty->print(" [%d .. %d), {", _start_bci, _limit_bci);
duke@435:   for (int i = 0; i < 8; i++) {
duke@435:     if ((_flags & (1 << i)) != 0) {
duke@435:       tty->print(" %s", flagnames[i]);
duke@435:     }
duke@435:   }
duke@435:   tty->print(" ]");
duke@435:   if (is_handler())
duke@435:     tty->print(" handles(%d..%d)", _ex_start_bci, _ex_limit_bci);
duke@435:   tty->cr();
duke@435: }
duke@435: 
duke@435: // ------------------------------------------------------------------
duke@435: // ciBlock::print_on
duke@435: void ciBlock::print_on(outputStream* st) const {
duke@435:   st->print_cr("--------------------------------------------------------");
duke@435:   st->print   ("ciBlock [%d - %d) control : ", start_bci(), limit_bci());
duke@435:   if (control_bci() == fall_through_bci) {
duke@435:     st->print_cr("%d:fall through", limit_bci());
duke@435:   } else {
duke@435:     st->print_cr("%d:%s", control_bci(),
duke@435:         Bytecodes::name(method()->java_code_at_bci(control_bci())));
duke@435:   }
duke@435: 
duke@435:   if (Verbose || WizardMode) {
duke@435:     method()->print_codes_on(start_bci(), limit_bci(), st);
duke@435:   }
duke@435: }
duke@435: #endif