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