1 /*
   2  * Copyright (c) 1999, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "c1/c1_Canonicalizer.hpp"
  27 #include "c1/c1_Optimizer.hpp"
  28 #include "c1/c1_ValueMap.hpp"
  29 #include "c1/c1_ValueSet.hpp"
  30 #include "c1/c1_ValueStack.hpp"
  31 #include "utilities/bitMap.inline.hpp"
  32 
  33 define_array(ValueSetArray, ValueSet*);
  34 define_stack(ValueSetList, ValueSetArray);
  35 
  36 
  37 Optimizer::Optimizer(IR* ir) {
  38   assert(ir->is_valid(), "IR must be valid");
  39   _ir = ir;
  40 }
  41 
  42 class CE_Eliminator: public BlockClosure {
  43  private:
  44   IR* _hir;
  45   int _cee_count;                                // the number of CEs successfully eliminated
  46   int _ifop_count;                               // the number of IfOps successfully simplified
  47   int _has_substitution;
  48 
  49  public:
  50   CE_Eliminator(IR* hir) : _cee_count(0), _ifop_count(0), _hir(hir) {
  51     _has_substitution = false;
  52     _hir->iterate_preorder(this);
  53     if (_has_substitution) {
  54       // substituted some ifops/phis, so resolve the substitution
  55       SubstitutionResolver sr(_hir);
  56     }
  57   }
  58   int cee_count() const                          { return _cee_count; }
  59   int ifop_count() const                         { return _ifop_count; }
  60 
  61   void adjust_exception_edges(BlockBegin* block, BlockBegin* sux) {
  62     int e = sux->number_of_exception_handlers();
  63     for (int i = 0; i < e; i++) {
  64       BlockBegin* xhandler = sux->exception_handler_at(i);
  65       block->add_exception_handler(xhandler);
  66 
  67       assert(xhandler->is_predecessor(sux), "missing predecessor");
  68       if (sux->number_of_preds() == 0) {
  69         // sux is disconnected from graph so disconnect from exception handlers
  70         xhandler->remove_predecessor(sux);
  71       }
  72       if (!xhandler->is_predecessor(block)) {
  73         xhandler->add_predecessor(block);
  74       }
  75     }
  76   }
  77 
  78   virtual void block_do(BlockBegin* block);
  79 
  80  private:
  81   Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);
  82 };
  83 
  84 void CE_Eliminator::block_do(BlockBegin* block) {
  85   // 1) find conditional expression
  86   // check if block ends with an If
  87   If* if_ = block->end()->as_If();
  88   if (if_ == NULL) return;
  89 
  90   // check if If works on int or object types
  91   // (we cannot handle If's working on long, float or doubles yet,
  92   // since IfOp doesn't support them - these If's show up if cmp
  93   // operations followed by If's are eliminated)
  94   ValueType* if_type = if_->x()->type();
  95   if (!if_type->is_int() && !if_type->is_object()) return;
  96 
  97   BlockBegin* t_block = if_->tsux();
  98   BlockBegin* f_block = if_->fsux();
  99   Instruction* t_cur = t_block->next();
 100   Instruction* f_cur = f_block->next();
 101 
 102   // one Constant may be present between BlockBegin and BlockEnd
 103   Value t_const = NULL;
 104   Value f_const = NULL;
 105   if (t_cur->as_Constant() != NULL && !t_cur->can_trap()) {
 106     t_const = t_cur;
 107     t_cur = t_cur->next();
 108   }
 109   if (f_cur->as_Constant() != NULL && !f_cur->can_trap()) {
 110     f_const = f_cur;
 111     f_cur = f_cur->next();
 112   }
 113 
 114   // check if both branches end with a goto
 115   Goto* t_goto = t_cur->as_Goto();
 116   if (t_goto == NULL) return;
 117   Goto* f_goto = f_cur->as_Goto();
 118   if (f_goto == NULL) return;
 119 
 120   // check if both gotos merge into the same block
 121   BlockBegin* sux = t_goto->default_sux();
 122   if (sux != f_goto->default_sux()) return;
 123 
 124   // check if at least one word was pushed on sux_state
 125   // inlining depths must match
 126   ValueStack* if_state = if_->state();
 127   ValueStack* sux_state = sux->state();
 128   if (if_state->scope()->level() > sux_state->scope()->level()) {
 129     while (sux_state->scope() != if_state->scope()) {
 130       if_state = if_state->caller_state();
 131       assert(if_state != NULL, "states do not match up");
 132     }
 133   } else if (if_state->scope()->level() < sux_state->scope()->level()) {
 134     while (sux_state->scope() != if_state->scope()) {
 135       sux_state = sux_state->caller_state();
 136       assert(sux_state != NULL, "states do not match up");
 137     }
 138   }
 139 
 140   if (sux_state->stack_size() <= if_state->stack_size()) return;
 141 
 142   // check if phi function is present at end of successor stack and that
 143   // only this phi was pushed on the stack
 144   Value sux_phi = sux_state->stack_at(if_state->stack_size());
 145   if (sux_phi == NULL || sux_phi->as_Phi() == NULL || sux_phi->as_Phi()->block() != sux) return;
 146   if (sux_phi->type()->size() != sux_state->stack_size() - if_state->stack_size()) return;
 147 
 148   // get the values that were pushed in the true- and false-branch
 149   Value t_value = t_goto->state()->stack_at(if_state->stack_size());
 150   Value f_value = f_goto->state()->stack_at(if_state->stack_size());
 151 
 152   // backend does not support floats
 153   assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");
 154   if (t_value->type()->is_float_kind()) return;
 155 
 156   // check that successor has no other phi functions but sux_phi
 157   // this can happen when t_block or f_block contained additonal stores to local variables
 158   // that are no longer represented by explicit instructions
 159   for_each_phi_fun(sux, phi,
 160                    if (phi != sux_phi) return;
 161                    );
 162   // true and false blocks can't have phis
 163   for_each_phi_fun(t_block, phi, return; );
 164   for_each_phi_fun(f_block, phi, return; );
 165 
 166   // 2) substitute conditional expression
 167   //    with an IfOp followed by a Goto
 168   // cut if_ away and get node before
 169   Instruction* cur_end = if_->prev(block);
 170 
 171   // append constants of true- and false-block if necessary
 172   // clone constants because original block must not be destroyed
 173   assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
 174   if (t_value == t_const) {
 175     t_value = new Constant(t_const->type());
 176     NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
 177     cur_end = cur_end->set_next(t_value);
 178   }
 179   if (f_value == f_const) {
 180     f_value = new Constant(f_const->type());
 181     NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
 182     cur_end = cur_end->set_next(f_value);
 183   }
 184 
 185   Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);
 186   assert(result != NULL, "make_ifop must return a non-null instruction");
 187   if (!result->is_linked() && result->can_be_linked()) {
 188     NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
 189     cur_end = cur_end->set_next(result);
 190   }
 191 
 192   // append Goto to successor
 193   ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;
 194   Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());
 195 
 196   // prepare state for Goto
 197   ValueStack* goto_state = if_state;
 198   goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
 199   goto_state->push(result->type(), result);
 200   assert(goto_state->is_same(sux_state), "states must match now");
 201   goto_->set_state(goto_state);
 202 
 203   cur_end = cur_end->set_next(goto_, goto_state->bci());
 204 
 205   // Adjust control flow graph
 206   BlockBegin::disconnect_edge(block, t_block);
 207   BlockBegin::disconnect_edge(block, f_block);
 208   if (t_block->number_of_preds() == 0) {
 209     BlockBegin::disconnect_edge(t_block, sux);
 210   }
 211   adjust_exception_edges(block, t_block);
 212   if (f_block->number_of_preds() == 0) {
 213     BlockBegin::disconnect_edge(f_block, sux);
 214   }
 215   adjust_exception_edges(block, f_block);
 216 
 217   // update block end
 218   block->set_end(goto_);
 219 
 220   // substitute the phi if possible
 221   if (sux_phi->as_Phi()->operand_count() == 1) {
 222     assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
 223     sux_phi->set_subst(result);
 224     _has_substitution = true;
 225   }
 226 
 227   // 3) successfully eliminated a conditional expression
 228   _cee_count++;
 229   if (PrintCEE) {
 230     tty->print_cr("%d. CEE in B%d (B%d B%d)", cee_count(), block->block_id(), t_block->block_id(), f_block->block_id());
 231     tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
 232   }
 233 
 234   _hir->verify();
 235 }
 236 
 237 Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {
 238   if (!OptimizeIfOps) {
 239     return new IfOp(x, cond, y, tval, fval);
 240   }
 241 
 242   tval = tval->subst();
 243   fval = fval->subst();
 244   if (tval == fval) {
 245     _ifop_count++;
 246     return tval;
 247   }
 248 
 249   x = x->subst();
 250   y = y->subst();
 251 
 252   Constant* y_const = y->as_Constant();
 253   if (y_const != NULL) {
 254     IfOp* x_ifop = x->as_IfOp();
 255     if (x_ifop != NULL) {                 // x is an ifop, y is a constant
 256       Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
 257       Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
 258 
 259       if (x_tval_const != NULL && x_fval_const != NULL) {
 260         Instruction::Condition x_ifop_cond = x_ifop->cond();
 261 
 262         Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
 263         Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
 264 
 265         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 266         if (t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable) {
 267           Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
 268           Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
 269 
 270           _ifop_count++;
 271           if (new_tval == new_fval) {
 272             return new_tval;
 273           } else {
 274             return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
 275           }
 276         }
 277       }
 278     } else {
 279       Constant* x_const = x->as_Constant();
 280       if (x_const != NULL) {         // x and y are constants
 281         Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
 282         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 283         if (x_compare_res != Constant::not_comparable) {
 284           _ifop_count++;
 285           return x_compare_res == Constant::cond_true ? tval : fval;
 286         }
 287       }
 288     }
 289   }
 290   return new IfOp(x, cond, y, tval, fval);
 291 }
 292 
 293 void Optimizer::eliminate_conditional_expressions() {
 294   // find conditional expressions & replace them with IfOps
 295   CE_Eliminator ce(ir());
 296 }
 297 
 298 class BlockMerger: public BlockClosure {
 299  private:
 300   IR* _hir;
 301   int _merge_count;              // the number of block pairs successfully merged
 302 
 303  public:
 304   BlockMerger(IR* hir)
 305   : _hir(hir)
 306   , _merge_count(0)
 307   {
 308     _hir->iterate_preorder(this);
 309   }
 310 
 311   bool try_merge(BlockBegin* block) {
 312     BlockEnd* end = block->end();
 313     if (end->as_Goto() != NULL) {
 314       assert(end->number_of_sux() == 1, "end must have exactly one successor");
 315       // Note: It would be sufficient to check for the number of successors (= 1)
 316       //       in order to decide if this block can be merged potentially. That
 317       //       would then also include switch statements w/ only a default case.
 318       //       However, in that case we would need to make sure the switch tag
 319       //       expression is executed if it can produce observable side effects.
 320       //       We should probably have the canonicalizer simplifying such switch
 321       //       statements and then we are sure we don't miss these merge opportunities
 322       //       here (was bug - gri 7/7/99).
 323       BlockBegin* sux = end->default_sux();
 324       if (sux->number_of_preds() == 1 && !sux->is_entry_block() && !end->is_safepoint()) {
 325         // merge the two blocks
 326 
 327 #ifdef ASSERT
 328         // verify that state at the end of block and at the beginning of sux are equal
 329         // no phi functions must be present at beginning of sux
 330         ValueStack* sux_state = sux->state();
 331         ValueStack* end_state = end->state();
 332 
 333         assert(end_state->scope() == sux_state->scope(), "scopes must match");
 334         assert(end_state->stack_size() == sux_state->stack_size(), "stack not equal");
 335         assert(end_state->locals_size() == sux_state->locals_size(), "locals not equal");
 336 
 337         int index;
 338         Value sux_value;
 339         for_each_stack_value(sux_state, index, sux_value) {
 340           assert(sux_value == end_state->stack_at(index), "stack not equal");
 341         }
 342         for_each_local_value(sux_state, index, sux_value) {
 343           assert(sux_value == end_state->local_at(index), "locals not equal");
 344         }
 345         assert(sux_state->caller_state() == end_state->caller_state(), "caller not equal");
 346 #endif
 347 
 348         // find instruction before end & append first instruction of sux block
 349         Instruction* prev = end->prev(block);
 350         Instruction* next = sux->next();
 351         assert(prev->as_BlockEnd() == NULL, "must not be a BlockEnd");
 352         prev->set_next(next);
 353         sux->disconnect_from_graph();
 354         block->set_end(sux->end());
 355         // add exception handlers of deleted block, if any
 356         for (int k = 0; k < sux->number_of_exception_handlers(); k++) {
 357           BlockBegin* xhandler = sux->exception_handler_at(k);
 358           block->add_exception_handler(xhandler);
 359 
 360           // also substitute predecessor of exception handler
 361           assert(xhandler->is_predecessor(sux), "missing predecessor");
 362           xhandler->remove_predecessor(sux);
 363           if (!xhandler->is_predecessor(block)) {
 364             xhandler->add_predecessor(block);
 365           }
 366         }
 367 
 368         // debugging output
 369         _merge_count++;
 370         if (PrintBlockElimination) {
 371           tty->print_cr("%d. merged B%d & B%d (stack size = %d)",
 372                         _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());
 373         }
 374 
 375         _hir->verify();
 376 
 377         If* if_ = block->end()->as_If();
 378         if (if_) {
 379           IfOp* ifop    = if_->x()->as_IfOp();
 380           Constant* con = if_->y()->as_Constant();
 381           bool swapped = false;
 382           if (!con || !ifop) {
 383             ifop = if_->y()->as_IfOp();
 384             con  = if_->x()->as_Constant();
 385             swapped = true;
 386           }
 387           if (con && ifop) {
 388             Constant* tval = ifop->tval()->as_Constant();
 389             Constant* fval = ifop->fval()->as_Constant();
 390             if (tval && fval) {
 391               // Find the instruction before if_, starting with ifop.
 392               // When if_ and ifop are not in the same block, prev
 393               // becomes NULL In such (rare) cases it is not
 394               // profitable to perform the optimization.
 395               Value prev = ifop;
 396               while (prev != NULL && prev->next() != if_) {
 397                 prev = prev->next();
 398               }
 399 
 400               if (prev != NULL) {
 401                 Instruction::Condition cond = if_->cond();
 402                 BlockBegin* tsux = if_->tsux();
 403                 BlockBegin* fsux = if_->fsux();
 404                 if (swapped) {
 405                   cond = Instruction::mirror(cond);
 406                 }
 407 
 408                 BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);
 409                 BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);
 410                 if (tblock != fblock && !if_->is_safepoint()) {
 411                   If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),
 412                                      tblock, fblock, if_->state_before(), if_->is_safepoint());
 413                   newif->set_state(if_->state()->copy());
 414 
 415                   assert(prev->next() == if_, "must be guaranteed by above search");
 416                   NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));
 417                   prev->set_next(newif);
 418                   block->set_end(newif);
 419 
 420                   _merge_count++;
 421                   if (PrintBlockElimination) {
 422                     tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());
 423                   }
 424 
 425                   _hir->verify();
 426                 }
 427               }
 428             }
 429           }
 430         }
 431 
 432         return true;
 433       }
 434     }
 435     return false;
 436   }
 437 
 438   virtual void block_do(BlockBegin* block) {
 439     _hir->verify();
 440     // repeat since the same block may merge again
 441     while (try_merge(block)) {
 442       _hir->verify();
 443     }
 444   }
 445 };
 446 
 447 
 448 void Optimizer::eliminate_blocks() {
 449   // merge blocks if possible
 450   BlockMerger bm(ir());
 451 }
 452 
 453 
 454 class NullCheckEliminator;
 455 class NullCheckVisitor: public InstructionVisitor {
 456 private:
 457   NullCheckEliminator* _nce;
 458   NullCheckEliminator* nce() { return _nce; }
 459 
 460 public:
 461   NullCheckVisitor() {}
 462 
 463   void set_eliminator(NullCheckEliminator* nce) { _nce = nce; }
 464 
 465   void do_Phi            (Phi*             x);
 466   void do_Local          (Local*           x);
 467   void do_Constant       (Constant*        x);
 468   void do_LoadField      (LoadField*       x);
 469   void do_StoreField     (StoreField*      x);
 470   void do_ArrayLength    (ArrayLength*     x);
 471   void do_LoadIndexed    (LoadIndexed*     x);
 472   void do_StoreIndexed   (StoreIndexed*    x);
 473   void do_NegateOp       (NegateOp*        x);
 474   void do_ArithmeticOp   (ArithmeticOp*    x);
 475   void do_ShiftOp        (ShiftOp*         x);
 476   void do_LogicOp        (LogicOp*         x);
 477   void do_CompareOp      (CompareOp*       x);
 478   void do_IfOp           (IfOp*            x);
 479   void do_Convert        (Convert*         x);
 480   void do_NullCheck      (NullCheck*       x);
 481   void do_Invoke         (Invoke*          x);
 482   void do_NewInstance    (NewInstance*     x);
 483   void do_NewTypeArray   (NewTypeArray*    x);
 484   void do_NewObjectArray (NewObjectArray*  x);
 485   void do_NewMultiArray  (NewMultiArray*   x);
 486   void do_CheckCast      (CheckCast*       x);
 487   void do_InstanceOf     (InstanceOf*      x);
 488   void do_MonitorEnter   (MonitorEnter*    x);
 489   void do_MonitorExit    (MonitorExit*     x);
 490   void do_Intrinsic      (Intrinsic*       x);
 491   void do_BlockBegin     (BlockBegin*      x);
 492   void do_Goto           (Goto*            x);
 493   void do_If             (If*              x);
 494   void do_IfInstanceOf   (IfInstanceOf*    x);
 495   void do_TableSwitch    (TableSwitch*     x);
 496   void do_LookupSwitch   (LookupSwitch*    x);
 497   void do_Return         (Return*          x);
 498   void do_Throw          (Throw*           x);
 499   void do_Base           (Base*            x);
 500   void do_OsrEntry       (OsrEntry*        x);
 501   void do_ExceptionObject(ExceptionObject* x);
 502   void do_RoundFP        (RoundFP*         x);
 503   void do_UnsafeGetRaw   (UnsafeGetRaw*    x);
 504   void do_UnsafePutRaw   (UnsafePutRaw*    x);
 505   void do_UnsafeGetObject(UnsafeGetObject* x);
 506   void do_UnsafePutObject(UnsafePutObject* x);
 507   void do_UnsafePrefetchRead (UnsafePrefetchRead*  x);
 508   void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x);
 509   void do_ProfileCall    (ProfileCall*     x);
 510   void do_ProfileInvoke  (ProfileInvoke*   x);
 511   void do_RuntimeCall    (RuntimeCall*     x);
 512 };
 513 
 514 
 515 // Because of a static contained within (for the purpose of iteration
 516 // over instructions), it is only valid to have one of these active at
 517 // a time
 518 class NullCheckEliminator: public ValueVisitor {
 519  private:
 520   Optimizer*        _opt;
 521 
 522   ValueSet*         _visitable_instructions;        // Visit each instruction only once per basic block
 523   BlockList*        _work_list;                   // Basic blocks to visit
 524 
 525   bool visitable(Value x) {
 526     assert(_visitable_instructions != NULL, "check");
 527     return _visitable_instructions->contains(x);
 528   }
 529   void mark_visited(Value x) {
 530     assert(_visitable_instructions != NULL, "check");
 531     _visitable_instructions->remove(x);
 532   }
 533   void mark_visitable(Value x) {
 534     assert(_visitable_instructions != NULL, "check");
 535     _visitable_instructions->put(x);
 536   }
 537   void clear_visitable_state() {
 538     assert(_visitable_instructions != NULL, "check");
 539     _visitable_instructions->clear();
 540   }
 541 
 542   ValueSet*         _set;                         // current state, propagated to subsequent BlockBegins
 543   ValueSetList      _block_states;                // BlockBegin null-check states for all processed blocks
 544   NullCheckVisitor  _visitor;
 545   NullCheck*        _last_explicit_null_check;
 546 
 547   bool set_contains(Value x)                      { assert(_set != NULL, "check"); return _set->contains(x); }
 548   void set_put     (Value x)                      { assert(_set != NULL, "check"); _set->put(x); }
 549   void set_remove  (Value x)                      { assert(_set != NULL, "check"); _set->remove(x); }
 550 
 551   BlockList* work_list()                          { return _work_list; }
 552 
 553   void iterate_all();
 554   void iterate_one(BlockBegin* block);
 555 
 556   ValueSet* state()                               { return _set; }
 557   void      set_state_from (ValueSet* state)      { _set->set_from(state); }
 558   ValueSet* state_for      (BlockBegin* block)    { return _block_states[block->block_id()]; }
 559   void      set_state_for  (BlockBegin* block, ValueSet* stack) { _block_states[block->block_id()] = stack; }
 560   // Returns true if caused a change in the block's state.
 561   bool      merge_state_for(BlockBegin* block,
 562                             ValueSet*   incoming_state);
 563 
 564  public:
 565   // constructor
 566   NullCheckEliminator(Optimizer* opt)
 567     : _opt(opt)
 568     , _set(new ValueSet())
 569     , _last_explicit_null_check(NULL)
 570     , _block_states(BlockBegin::number_of_blocks(), NULL)
 571     , _work_list(new BlockList()) {
 572     _visitable_instructions = new ValueSet();
 573     _visitor.set_eliminator(this);
 574   }
 575 
 576   Optimizer*  opt()                               { return _opt; }
 577   IR*         ir ()                               { return opt()->ir(); }
 578 
 579   // Process a graph
 580   void iterate(BlockBegin* root);
 581 
 582   void visit(Value* f);
 583 
 584   // In some situations (like NullCheck(x); getfield(x)) the debug
 585   // information from the explicit NullCheck can be used to populate
 586   // the getfield, even if the two instructions are in different
 587   // scopes; this allows implicit null checks to be used but the
 588   // correct exception information to be generated. We must clear the
 589   // last-traversed NullCheck when we reach a potentially-exception-
 590   // throwing instruction, as well as in some other cases.
 591   void        set_last_explicit_null_check(NullCheck* check) { _last_explicit_null_check = check; }
 592   NullCheck*  last_explicit_null_check()                     { return _last_explicit_null_check; }
 593   Value       last_explicit_null_check_obj()                 { return (_last_explicit_null_check
 594                                                                          ? _last_explicit_null_check->obj()
 595                                                                          : NULL); }
 596   NullCheck*  consume_last_explicit_null_check() {
 597     _last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);
 598     _last_explicit_null_check->set_can_trap(false);
 599     return _last_explicit_null_check;
 600   }
 601   void        clear_last_explicit_null_check()               { _last_explicit_null_check = NULL; }
 602 
 603   // Handlers for relevant instructions
 604   // (separated out from NullCheckVisitor for clarity)
 605 
 606   // The basic contract is that these must leave the instruction in
 607   // the desired state; must not assume anything about the state of
 608   // the instruction. We make multiple passes over some basic blocks
 609   // and the last pass is the only one whose result is valid.
 610   void handle_AccessField     (AccessField* x);
 611   void handle_ArrayLength     (ArrayLength* x);
 612   void handle_LoadIndexed     (LoadIndexed* x);
 613   void handle_StoreIndexed    (StoreIndexed* x);
 614   void handle_NullCheck       (NullCheck* x);
 615   void handle_Invoke          (Invoke* x);
 616   void handle_NewInstance     (NewInstance* x);
 617   void handle_NewArray        (NewArray* x);
 618   void handle_AccessMonitor   (AccessMonitor* x);
 619   void handle_Intrinsic       (Intrinsic* x);
 620   void handle_ExceptionObject (ExceptionObject* x);
 621   void handle_Phi             (Phi* x);
 622 };
 623 
 624 
 625 // NEEDS_CLEANUP
 626 // There may be other instructions which need to clear the last
 627 // explicit null check. Anything across which we can not hoist the
 628 // debug information for a NullCheck instruction must clear it. It
 629 // might be safer to pattern match "NullCheck ; {AccessField,
 630 // ArrayLength, LoadIndexed}" but it is more easily structured this way.
 631 // Should test to see performance hit of clearing it for all handlers
 632 // with empty bodies below. If it is negligible then we should leave
 633 // that in for safety, otherwise should think more about it.
 634 void NullCheckVisitor::do_Phi            (Phi*             x) { nce()->handle_Phi(x);      }
 635 void NullCheckVisitor::do_Local          (Local*           x) {}
 636 void NullCheckVisitor::do_Constant       (Constant*        x) { /* FIXME: handle object constants */ }
 637 void NullCheckVisitor::do_LoadField      (LoadField*       x) { nce()->handle_AccessField(x); }
 638 void NullCheckVisitor::do_StoreField     (StoreField*      x) { nce()->handle_AccessField(x); }
 639 void NullCheckVisitor::do_ArrayLength    (ArrayLength*     x) { nce()->handle_ArrayLength(x); }
 640 void NullCheckVisitor::do_LoadIndexed    (LoadIndexed*     x) { nce()->handle_LoadIndexed(x); }
 641 void NullCheckVisitor::do_StoreIndexed   (StoreIndexed*    x) { nce()->handle_StoreIndexed(x); }
 642 void NullCheckVisitor::do_NegateOp       (NegateOp*        x) {}
 643 void NullCheckVisitor::do_ArithmeticOp   (ArithmeticOp*    x) { if (x->can_trap()) nce()->clear_last_explicit_null_check(); }
 644 void NullCheckVisitor::do_ShiftOp        (ShiftOp*         x) {}
 645 void NullCheckVisitor::do_LogicOp        (LogicOp*         x) {}
 646 void NullCheckVisitor::do_CompareOp      (CompareOp*       x) {}
 647 void NullCheckVisitor::do_IfOp           (IfOp*            x) {}
 648 void NullCheckVisitor::do_Convert        (Convert*         x) {}
 649 void NullCheckVisitor::do_NullCheck      (NullCheck*       x) { nce()->handle_NullCheck(x); }
 650 void NullCheckVisitor::do_Invoke         (Invoke*          x) { nce()->handle_Invoke(x); }
 651 void NullCheckVisitor::do_NewInstance    (NewInstance*     x) { nce()->handle_NewInstance(x); }
 652 void NullCheckVisitor::do_NewTypeArray   (NewTypeArray*    x) { nce()->handle_NewArray(x); }
 653 void NullCheckVisitor::do_NewObjectArray (NewObjectArray*  x) { nce()->handle_NewArray(x); }
 654 void NullCheckVisitor::do_NewMultiArray  (NewMultiArray*   x) { nce()->handle_NewArray(x); }
 655 void NullCheckVisitor::do_CheckCast      (CheckCast*       x) { nce()->clear_last_explicit_null_check(); }
 656 void NullCheckVisitor::do_InstanceOf     (InstanceOf*      x) {}
 657 void NullCheckVisitor::do_MonitorEnter   (MonitorEnter*    x) { nce()->handle_AccessMonitor(x); }
 658 void NullCheckVisitor::do_MonitorExit    (MonitorExit*     x) { nce()->handle_AccessMonitor(x); }
 659 void NullCheckVisitor::do_Intrinsic      (Intrinsic*       x) { nce()->handle_Intrinsic(x);     }
 660 void NullCheckVisitor::do_BlockBegin     (BlockBegin*      x) {}
 661 void NullCheckVisitor::do_Goto           (Goto*            x) {}
 662 void NullCheckVisitor::do_If             (If*              x) {}
 663 void NullCheckVisitor::do_IfInstanceOf   (IfInstanceOf*    x) {}
 664 void NullCheckVisitor::do_TableSwitch    (TableSwitch*     x) {}
 665 void NullCheckVisitor::do_LookupSwitch   (LookupSwitch*    x) {}
 666 void NullCheckVisitor::do_Return         (Return*          x) {}
 667 void NullCheckVisitor::do_Throw          (Throw*           x) { nce()->clear_last_explicit_null_check(); }
 668 void NullCheckVisitor::do_Base           (Base*            x) {}
 669 void NullCheckVisitor::do_OsrEntry       (OsrEntry*        x) {}
 670 void NullCheckVisitor::do_ExceptionObject(ExceptionObject* x) { nce()->handle_ExceptionObject(x); }
 671 void NullCheckVisitor::do_RoundFP        (RoundFP*         x) {}
 672 void NullCheckVisitor::do_UnsafeGetRaw   (UnsafeGetRaw*    x) {}
 673 void NullCheckVisitor::do_UnsafePutRaw   (UnsafePutRaw*    x) {}
 674 void NullCheckVisitor::do_UnsafeGetObject(UnsafeGetObject* x) {}
 675 void NullCheckVisitor::do_UnsafePutObject(UnsafePutObject* x) {}
 676 void NullCheckVisitor::do_UnsafePrefetchRead (UnsafePrefetchRead*  x) {}
 677 void NullCheckVisitor::do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) {}
 678 void NullCheckVisitor::do_ProfileCall    (ProfileCall*     x) { nce()->clear_last_explicit_null_check(); }
 679 void NullCheckVisitor::do_ProfileInvoke  (ProfileInvoke*   x) {}
 680 void NullCheckVisitor::do_RuntimeCall    (RuntimeCall*     x) {}
 681 
 682 
 683 void NullCheckEliminator::visit(Value* p) {
 684   assert(*p != NULL, "should not find NULL instructions");
 685   if (visitable(*p)) {
 686     mark_visited(*p);
 687     (*p)->visit(&_visitor);
 688   }
 689 }
 690 
 691 bool NullCheckEliminator::merge_state_for(BlockBegin* block, ValueSet* incoming_state) {
 692   ValueSet* state = state_for(block);
 693   if (state == NULL) {
 694     state = incoming_state->copy();
 695     set_state_for(block, state);
 696     return true;
 697   } else {
 698     bool changed = state->set_intersect(incoming_state);
 699     if (PrintNullCheckElimination && changed) {
 700       tty->print_cr("Block %d's null check state changed", block->block_id());
 701     }
 702     return changed;
 703   }
 704 }
 705 
 706 
 707 void NullCheckEliminator::iterate_all() {
 708   while (work_list()->length() > 0) {
 709     iterate_one(work_list()->pop());
 710   }
 711 }
 712 
 713 
 714 void NullCheckEliminator::iterate_one(BlockBegin* block) {
 715   clear_visitable_state();
 716   // clear out an old explicit null checks
 717   set_last_explicit_null_check(NULL);
 718 
 719   if (PrintNullCheckElimination) {
 720     tty->print_cr(" ...iterating block %d in null check elimination for %s::%s%s",
 721                   block->block_id(),
 722                   ir()->method()->holder()->name()->as_utf8(),
 723                   ir()->method()->name()->as_utf8(),
 724                   ir()->method()->signature()->as_symbol()->as_utf8());
 725   }
 726 
 727   // Create new state if none present (only happens at root)
 728   if (state_for(block) == NULL) {
 729     ValueSet* tmp_state = new ValueSet();
 730     set_state_for(block, tmp_state);
 731     // Initial state is that local 0 (receiver) is non-null for
 732     // non-static methods
 733     ValueStack* stack  = block->state();
 734     IRScope*    scope  = stack->scope();
 735     ciMethod*   method = scope->method();
 736     if (!method->is_static()) {
 737       Local* local0 = stack->local_at(0)->as_Local();
 738       assert(local0 != NULL, "must be");
 739       assert(local0->type() == objectType, "invalid type of receiver");
 740 
 741       if (local0 != NULL) {
 742         // Local 0 is used in this scope
 743         tmp_state->put(local0);
 744         if (PrintNullCheckElimination) {
 745           tty->print_cr("Local 0 (value %d) proven non-null upon entry", local0->id());
 746         }
 747       }
 748     }
 749   }
 750 
 751   // Must copy block's state to avoid mutating it during iteration
 752   // through the block -- otherwise "not-null" states can accidentally
 753   // propagate "up" through the block during processing of backward
 754   // branches and algorithm is incorrect (and does not converge)
 755   set_state_from(state_for(block));
 756 
 757   // allow visiting of Phis belonging to this block
 758   for_each_phi_fun(block, phi,
 759                    mark_visitable(phi);
 760                    );
 761 
 762   BlockEnd* e = block->end();
 763   assert(e != NULL, "incomplete graph");
 764   int i;
 765 
 766   // Propagate the state before this block into the exception
 767   // handlers.  They aren't true successors since we aren't guaranteed
 768   // to execute the whole block before executing them.  Also putting
 769   // them on first seems to help reduce the amount of iteration to
 770   // reach a fixed point.
 771   for (i = 0; i < block->number_of_exception_handlers(); i++) {
 772     BlockBegin* next = block->exception_handler_at(i);
 773     if (merge_state_for(next, state())) {
 774       if (!work_list()->contains(next)) {
 775         work_list()->push(next);
 776       }
 777     }
 778   }
 779 
 780   // Iterate through block, updating state.
 781   for (Instruction* instr = block; instr != NULL; instr = instr->next()) {
 782     // Mark instructions in this block as visitable as they are seen
 783     // in the instruction list.  This keeps the iteration from
 784     // visiting instructions which are references in other blocks or
 785     // visiting instructions more than once.
 786     mark_visitable(instr);
 787     if (instr->is_pinned() || instr->can_trap() || (instr->as_NullCheck() != NULL)) {
 788       mark_visited(instr);
 789       instr->input_values_do(this);
 790       instr->visit(&_visitor);
 791     }
 792   }
 793 
 794   // Propagate state to successors if necessary
 795   for (i = 0; i < e->number_of_sux(); i++) {
 796     BlockBegin* next = e->sux_at(i);
 797     if (merge_state_for(next, state())) {
 798       if (!work_list()->contains(next)) {
 799         work_list()->push(next);
 800       }
 801     }
 802   }
 803 }
 804 
 805 
 806 void NullCheckEliminator::iterate(BlockBegin* block) {
 807   work_list()->push(block);
 808   iterate_all();
 809 }
 810 
 811 void NullCheckEliminator::handle_AccessField(AccessField* x) {
 812   if (x->is_static()) {
 813     if (x->as_LoadField() != NULL) {
 814       // If the field is a non-null static final object field (as is
 815       // often the case for sun.misc.Unsafe), put this LoadField into
 816       // the non-null map
 817       ciField* field = x->field();
 818       if (field->is_constant()) {
 819         ciConstant field_val = field->constant_value();
 820         BasicType field_type = field_val.basic_type();
 821         if (field_type == T_OBJECT || field_type == T_ARRAY) {
 822           ciObject* obj_val = field_val.as_object();
 823           if (!obj_val->is_null_object()) {
 824             if (PrintNullCheckElimination) {
 825               tty->print_cr("AccessField %d proven non-null by static final non-null oop check",
 826                             x->id());
 827             }
 828             set_put(x);
 829           }
 830         }
 831       }
 832     }
 833     // Be conservative
 834     clear_last_explicit_null_check();
 835     return;
 836   }
 837 
 838   Value obj = x->obj();
 839   if (set_contains(obj)) {
 840     // Value is non-null => update AccessField
 841     if (last_explicit_null_check_obj() == obj && !x->needs_patching()) {
 842       x->set_explicit_null_check(consume_last_explicit_null_check());
 843       x->set_needs_null_check(true);
 844       if (PrintNullCheckElimination) {
 845         tty->print_cr("Folded NullCheck %d into AccessField %d's null check for value %d",
 846                       x->explicit_null_check()->id(), x->id(), obj->id());
 847       }
 848     } else {
 849       x->set_explicit_null_check(NULL);
 850       x->set_needs_null_check(false);
 851       if (PrintNullCheckElimination) {
 852         tty->print_cr("Eliminated AccessField %d's null check for value %d", x->id(), obj->id());
 853       }
 854     }
 855   } else {
 856     set_put(obj);
 857     if (PrintNullCheckElimination) {
 858       tty->print_cr("AccessField %d of value %d proves value to be non-null", x->id(), obj->id());
 859     }
 860     // Ensure previous passes do not cause wrong state
 861     x->set_needs_null_check(true);
 862     x->set_explicit_null_check(NULL);
 863   }
 864   clear_last_explicit_null_check();
 865 }
 866 
 867 
 868 void NullCheckEliminator::handle_ArrayLength(ArrayLength* x) {
 869   Value array = x->array();
 870   if (set_contains(array)) {
 871     // Value is non-null => update AccessArray
 872     if (last_explicit_null_check_obj() == array) {
 873       x->set_explicit_null_check(consume_last_explicit_null_check());
 874       x->set_needs_null_check(true);
 875       if (PrintNullCheckElimination) {
 876         tty->print_cr("Folded NullCheck %d into ArrayLength %d's null check for value %d",
 877                       x->explicit_null_check()->id(), x->id(), array->id());
 878       }
 879     } else {
 880       x->set_explicit_null_check(NULL);
 881       x->set_needs_null_check(false);
 882       if (PrintNullCheckElimination) {
 883         tty->print_cr("Eliminated ArrayLength %d's null check for value %d", x->id(), array->id());
 884       }
 885     }
 886   } else {
 887     set_put(array);
 888     if (PrintNullCheckElimination) {
 889       tty->print_cr("ArrayLength %d of value %d proves value to be non-null", x->id(), array->id());
 890     }
 891     // Ensure previous passes do not cause wrong state
 892     x->set_needs_null_check(true);
 893     x->set_explicit_null_check(NULL);
 894   }
 895   clear_last_explicit_null_check();
 896 }
 897 
 898 
 899 void NullCheckEliminator::handle_LoadIndexed(LoadIndexed* x) {
 900   Value array = x->array();
 901   if (set_contains(array)) {
 902     // Value is non-null => update AccessArray
 903     if (last_explicit_null_check_obj() == array) {
 904       x->set_explicit_null_check(consume_last_explicit_null_check());
 905       x->set_needs_null_check(true);
 906       if (PrintNullCheckElimination) {
 907         tty->print_cr("Folded NullCheck %d into LoadIndexed %d's null check for value %d",
 908                       x->explicit_null_check()->id(), x->id(), array->id());
 909       }
 910     } else {
 911       x->set_explicit_null_check(NULL);
 912       x->set_needs_null_check(false);
 913       if (PrintNullCheckElimination) {
 914         tty->print_cr("Eliminated LoadIndexed %d's null check for value %d", x->id(), array->id());
 915       }
 916     }
 917   } else {
 918     set_put(array);
 919     if (PrintNullCheckElimination) {
 920       tty->print_cr("LoadIndexed %d of value %d proves value to be non-null", x->id(), array->id());
 921     }
 922     // Ensure previous passes do not cause wrong state
 923     x->set_needs_null_check(true);
 924     x->set_explicit_null_check(NULL);
 925   }
 926   clear_last_explicit_null_check();
 927 }
 928 
 929 
 930 void NullCheckEliminator::handle_StoreIndexed(StoreIndexed* x) {
 931   Value array = x->array();
 932   if (set_contains(array)) {
 933     // Value is non-null => update AccessArray
 934     if (PrintNullCheckElimination) {
 935       tty->print_cr("Eliminated StoreIndexed %d's null check for value %d", x->id(), array->id());
 936     }
 937     x->set_needs_null_check(false);
 938   } else {
 939     set_put(array);
 940     if (PrintNullCheckElimination) {
 941       tty->print_cr("StoreIndexed %d of value %d proves value to be non-null", x->id(), array->id());
 942     }
 943     // Ensure previous passes do not cause wrong state
 944     x->set_needs_null_check(true);
 945   }
 946   clear_last_explicit_null_check();
 947 }
 948 
 949 
 950 void NullCheckEliminator::handle_NullCheck(NullCheck* x) {
 951   Value obj = x->obj();
 952   if (set_contains(obj)) {
 953     // Already proven to be non-null => this NullCheck is useless
 954     if (PrintNullCheckElimination) {
 955       tty->print_cr("Eliminated NullCheck %d for value %d", x->id(), obj->id());
 956     }
 957     // Don't unpin since that may shrink obj's live range and make it unavailable for debug info.
 958     // The code generator won't emit LIR for a NullCheck that cannot trap.
 959     x->set_can_trap(false);
 960   } else {
 961     // May be null => add to map and set last explicit NullCheck
 962     x->set_can_trap(true);
 963     // make sure it's pinned if it can trap
 964     x->pin(Instruction::PinExplicitNullCheck);
 965     set_put(obj);
 966     set_last_explicit_null_check(x);
 967     if (PrintNullCheckElimination) {
 968       tty->print_cr("NullCheck %d of value %d proves value to be non-null", x->id(), obj->id());
 969     }
 970   }
 971 }
 972 
 973 
 974 void NullCheckEliminator::handle_Invoke(Invoke* x) {
 975   if (!x->has_receiver()) {
 976     // Be conservative
 977     clear_last_explicit_null_check();
 978     return;
 979   }
 980 
 981   Value recv = x->receiver();
 982   if (!set_contains(recv)) {
 983     set_put(recv);
 984     if (PrintNullCheckElimination) {
 985       tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
 986     }
 987   }
 988   clear_last_explicit_null_check();
 989 }
 990 
 991 
 992 void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
 993   set_put(x);
 994   if (PrintNullCheckElimination) {
 995     tty->print_cr("NewInstance %d is non-null", x->id());
 996   }
 997 }
 998 
 999 
1000 void NullCheckEliminator::handle_NewArray(NewArray* x) {
1001   set_put(x);
1002   if (PrintNullCheckElimination) {
1003     tty->print_cr("NewArray %d is non-null", x->id());
1004   }
1005 }
1006 
1007 
1008 void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1009   set_put(x);
1010   if (PrintNullCheckElimination) {
1011     tty->print_cr("ExceptionObject %d is non-null", x->id());
1012   }
1013 }
1014 
1015 
1016 void NullCheckEliminator::handle_AccessMonitor(AccessMonitor* x) {
1017   Value obj = x->obj();
1018   if (set_contains(obj)) {
1019     // Value is non-null => update AccessMonitor
1020     if (PrintNullCheckElimination) {
1021       tty->print_cr("Eliminated AccessMonitor %d's null check for value %d", x->id(), obj->id());
1022     }
1023     x->set_needs_null_check(false);
1024   } else {
1025     set_put(obj);
1026     if (PrintNullCheckElimination) {
1027       tty->print_cr("AccessMonitor %d of value %d proves value to be non-null", x->id(), obj->id());
1028     }
1029     // Ensure previous passes do not cause wrong state
1030     x->set_needs_null_check(true);
1031   }
1032   clear_last_explicit_null_check();
1033 }
1034 
1035 
1036 void NullCheckEliminator::handle_Intrinsic(Intrinsic* x) {
1037   if (!x->has_receiver()) {
1038     if (x->id() == vmIntrinsics::_arraycopy) {
1039       for (int i = 0; i < x->number_of_arguments(); i++) {
1040         x->set_arg_needs_null_check(i, !set_contains(x->argument_at(i)));
1041       }
1042     }
1043 
1044     // Be conservative
1045     clear_last_explicit_null_check();
1046     return;
1047   }
1048 
1049   Value recv = x->receiver();
1050   if (set_contains(recv)) {
1051     // Value is non-null => update Intrinsic
1052     if (PrintNullCheckElimination) {
1053       tty->print_cr("Eliminated Intrinsic %d's null check for value %d", x->id(), recv->id());
1054     }
1055     x->set_needs_null_check(false);
1056   } else {
1057     set_put(recv);
1058     if (PrintNullCheckElimination) {
1059       tty->print_cr("Intrinsic %d of value %d proves value to be non-null", x->id(), recv->id());
1060     }
1061     // Ensure previous passes do not cause wrong state
1062     x->set_needs_null_check(true);
1063   }
1064   clear_last_explicit_null_check();
1065 }
1066 
1067 
1068 void NullCheckEliminator::handle_Phi(Phi* x) {
1069   int i;
1070   bool all_non_null = true;
1071   if (x->is_illegal()) {
1072     all_non_null = false;
1073   } else {
1074     for (i = 0; i < x->operand_count(); i++) {
1075       Value input = x->operand_at(i);
1076       if (!set_contains(input)) {
1077         all_non_null = false;
1078       }
1079     }
1080   }
1081 
1082   if (all_non_null) {
1083     // Value is non-null => update Phi
1084     if (PrintNullCheckElimination) {
1085       tty->print_cr("Eliminated Phi %d's null check for phifun because all inputs are non-null", x->id());
1086     }
1087     x->set_needs_null_check(false);
1088   } else if (set_contains(x)) {
1089     set_remove(x);
1090   }
1091 }
1092 
1093 
1094 void Optimizer::eliminate_null_checks() {
1095   ResourceMark rm;
1096 
1097   NullCheckEliminator nce(this);
1098 
1099   if (PrintNullCheckElimination) {
1100     tty->print_cr("Starting null check elimination for method %s::%s%s",
1101                   ir()->method()->holder()->name()->as_utf8(),
1102                   ir()->method()->name()->as_utf8(),
1103                   ir()->method()->signature()->as_symbol()->as_utf8());
1104   }
1105 
1106   // Apply to graph
1107   nce.iterate(ir()->start());
1108 
1109   // walk over the graph looking for exception
1110   // handlers and iterate over them as well
1111   int nblocks = BlockBegin::number_of_blocks();
1112   BlockList blocks(nblocks);
1113   boolArray visited_block(nblocks, false);
1114 
1115   blocks.push(ir()->start());
1116   visited_block[ir()->start()->block_id()] = true;
1117   for (int i = 0; i < blocks.length(); i++) {
1118     BlockBegin* b = blocks[i];
1119     // exception handlers need to be treated as additional roots
1120     for (int e = b->number_of_exception_handlers(); e-- > 0; ) {
1121       BlockBegin* excp = b->exception_handler_at(e);
1122       int id = excp->block_id();
1123       if (!visited_block[id]) {
1124         blocks.push(excp);
1125         visited_block[id] = true;
1126         nce.iterate(excp);
1127       }
1128     }
1129     // traverse successors
1130     BlockEnd *end = b->end();
1131     for (int s = end->number_of_sux(); s-- > 0; ) {
1132       BlockBegin* next = end->sux_at(s);
1133       int id = next->block_id();
1134       if (!visited_block[id]) {
1135         blocks.push(next);
1136         visited_block[id] = true;
1137       }
1138     }
1139   }
1140 
1141 
1142   if (PrintNullCheckElimination) {
1143     tty->print_cr("Done with null check elimination for method %s::%s%s",
1144                   ir()->method()->holder()->name()->as_utf8(),
1145                   ir()->method()->name()->as_utf8(),
1146                   ir()->method()->signature()->as_symbol()->as_utf8());
1147   }
1148 }