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