< prev index next >

src/hotspot/share/c1/c1_Optimizer.cpp

Print this page

  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 

 182 
 183   // 2) substitute conditional expression
 184   //    with an IfOp followed by a Goto
 185   // cut if_ away and get node before
 186   Instruction* cur_end = if_->prev();
 187 
 188   // append constants of true- and false-block if necessary
 189   // clone constants because original block must not be destroyed
 190   assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
 191   if (t_value == t_const) {
 192     t_value = new Constant(t_const->type());
 193     NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
 194     cur_end = cur_end->set_next(t_value);
 195   }
 196   if (f_value == f_const) {
 197     f_value = new Constant(f_const->type());
 198     NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
 199     cur_end = cur_end->set_next(f_value);
 200   }
 201 
 202   Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);

 203   assert(result != NULL, "make_ifop must return a non-null instruction");
 204   if (!result->is_linked() && result->can_be_linked()) {
 205     NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
 206     cur_end = cur_end->set_next(result);
 207   }
 208 
 209   // append Goto to successor
 210   ValueStack* state_before = if_->state_before();
 211   Goto* goto_ = new Goto(sux, state_before, is_safepoint);
 212 
 213   // prepare state for Goto
 214   ValueStack* goto_state = if_state;
 215   goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
 216   goto_state->push(result->type(), result);
 217   assert(goto_state->is_same(sux_state), "states must match now");
 218   goto_->set_state(goto_state);
 219 
 220   cur_end = cur_end->set_next(goto_, goto_state->bci());
 221 
 222   // Adjust control flow graph

 234   // update block end
 235   block->set_end(goto_);
 236 
 237   // substitute the phi if possible
 238   if (sux_phi->as_Phi()->operand_count() == 1) {
 239     assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
 240     sux_phi->set_subst(result);
 241     _has_substitution = true;
 242   }
 243 
 244   // 3) successfully eliminated a conditional expression
 245   _cee_count++;
 246   if (PrintCEE) {
 247     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());
 248     tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
 249   }
 250 
 251   _hir->verify();
 252 }
 253 
 254 Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {

 255   if (!OptimizeIfOps) {
 256     return new IfOp(x, cond, y, tval, fval);
 257   }
 258 
 259   tval = tval->subst();
 260   fval = fval->subst();
 261   if (tval == fval) {
 262     _ifop_count++;
 263     return tval;
 264   }
 265 
 266   x = x->subst();
 267   y = y->subst();
 268 
 269   Constant* y_const = y->as_Constant();
 270   if (y_const != NULL) {
 271     IfOp* x_ifop = x->as_IfOp();
 272     if (x_ifop != NULL) {                 // x is an ifop, y is a constant
 273       Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
 274       Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
 275 
 276       if (x_tval_const != NULL && x_fval_const != NULL) {
 277         Instruction::Condition x_ifop_cond = x_ifop->cond();
 278 
 279         Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
 280         Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
 281 
 282         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 283         if (t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable) {
 284           Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
 285           Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
 286 
 287           _ifop_count++;
 288           if (new_tval == new_fval) {
 289             return new_tval;
 290           } else {
 291             return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
 292           }
 293         }
 294       }
 295     } else {
 296       Constant* x_const = x->as_Constant();
 297       if (x_const != NULL) {         // x and y are constants
 298         Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
 299         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 300         if (x_compare_res != Constant::not_comparable) {
 301           _ifop_count++;
 302           return x_compare_res == Constant::cond_true ? tval : fval;
 303         }
 304       }
 305     }
 306   }
 307   return new IfOp(x, cond, y, tval, fval);
 308 }
 309 
 310 void Optimizer::eliminate_conditional_expressions() {
 311   // find conditional expressions & replace them with IfOps
 312   CE_Eliminator ce(ir());
 313 }
 314 
 315 class BlockMerger: public BlockClosure {
 316  private:
 317   IR* _hir;
 318   int _merge_count;              // the number of block pairs successfully merged
 319 
 320  public:
 321   BlockMerger(IR* hir)
 322   : _hir(hir)
 323   , _merge_count(0)
 324   {
 325     _hir->iterate_preorder(this);
 326     CompileLog* log = _hir->compilation()->log();
 327     if (log != NULL)

 396 
 397         // debugging output
 398         _merge_count++;
 399         if (PrintBlockElimination) {
 400           tty->print_cr("%d. merged B%d & B%d (stack size = %d)",
 401                         _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());
 402         }
 403 
 404         _hir->verify();
 405 
 406         If* if_ = block->end()->as_If();
 407         if (if_) {
 408           IfOp* ifop    = if_->x()->as_IfOp();
 409           Constant* con = if_->y()->as_Constant();
 410           bool swapped = false;
 411           if (!con || !ifop) {
 412             ifop = if_->y()->as_IfOp();
 413             con  = if_->x()->as_Constant();
 414             swapped = true;
 415           }
 416           if (con && ifop) {
 417             Constant* tval = ifop->tval()->as_Constant();
 418             Constant* fval = ifop->fval()->as_Constant();
 419             if (tval && fval) {
 420               // Find the instruction before if_, starting with ifop.
 421               // When if_ and ifop are not in the same block, prev
 422               // becomes NULL In such (rare) cases it is not
 423               // profitable to perform the optimization.
 424               Value prev = ifop;
 425               while (prev != NULL && prev->next() != if_) {
 426                 prev = prev->next();
 427               }
 428 
 429               if (prev != NULL) {
 430                 Instruction::Condition cond = if_->cond();
 431                 BlockBegin* tsux = if_->tsux();
 432                 BlockBegin* fsux = if_->fsux();
 433                 if (swapped) {
 434                   cond = Instruction::mirror(cond);
 435                 }
 436 
 437                 BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);
 438                 BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);
 439                 if (tblock != fblock && !if_->is_safepoint()) {
 440                   If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),
 441                                      tblock, fblock, if_->state_before(), if_->is_safepoint());
 442                   newif->set_state(if_->state()->copy());
 443 
 444                   assert(prev->next() == if_, "must be guaranteed by above search");
 445                   NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));
 446                   prev->set_next(newif);
 447                   block->set_end(newif);
 448 
 449                   _merge_count++;
 450                   if (PrintBlockElimination) {
 451                     tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());
 452                   }
 453 
 454                   _hir->verify();
 455                 }
 456               }
 457             }
 458           }
 459         }
 460 
 461         return true;

 493 
 494   void do_Phi            (Phi*             x);
 495   void do_Local          (Local*           x);
 496   void do_Constant       (Constant*        x);
 497   void do_LoadField      (LoadField*       x);
 498   void do_StoreField     (StoreField*      x);
 499   void do_ArrayLength    (ArrayLength*     x);
 500   void do_LoadIndexed    (LoadIndexed*     x);
 501   void do_StoreIndexed   (StoreIndexed*    x);
 502   void do_NegateOp       (NegateOp*        x);
 503   void do_ArithmeticOp   (ArithmeticOp*    x);
 504   void do_ShiftOp        (ShiftOp*         x);
 505   void do_LogicOp        (LogicOp*         x);
 506   void do_CompareOp      (CompareOp*       x);
 507   void do_IfOp           (IfOp*            x);
 508   void do_Convert        (Convert*         x);
 509   void do_NullCheck      (NullCheck*       x);
 510   void do_TypeCast       (TypeCast*        x);
 511   void do_Invoke         (Invoke*          x);
 512   void do_NewInstance    (NewInstance*     x);

 513   void do_NewTypeArray   (NewTypeArray*    x);
 514   void do_NewObjectArray (NewObjectArray*  x);
 515   void do_NewMultiArray  (NewMultiArray*   x);

 516   void do_CheckCast      (CheckCast*       x);
 517   void do_InstanceOf     (InstanceOf*      x);
 518   void do_MonitorEnter   (MonitorEnter*    x);
 519   void do_MonitorExit    (MonitorExit*     x);
 520   void do_Intrinsic      (Intrinsic*       x);
 521   void do_BlockBegin     (BlockBegin*      x);
 522   void do_Goto           (Goto*            x);
 523   void do_If             (If*              x);
 524   void do_TableSwitch    (TableSwitch*     x);
 525   void do_LookupSwitch   (LookupSwitch*    x);
 526   void do_Return         (Return*          x);
 527   void do_Throw          (Throw*           x);
 528   void do_Base           (Base*            x);
 529   void do_OsrEntry       (OsrEntry*        x);
 530   void do_ExceptionObject(ExceptionObject* x);
 531   void do_RoundFP        (RoundFP*         x);
 532   void do_UnsafeGet      (UnsafeGet*       x);
 533   void do_UnsafePut      (UnsafePut*       x);
 534   void do_UnsafeGetAndSet(UnsafeGetAndSet* x);
 535   void do_ProfileCall    (ProfileCall*     x);
 536   void do_ProfileReturnType (ProfileReturnType*  x);

 537   void do_ProfileInvoke  (ProfileInvoke*   x);
 538   void do_RuntimeCall    (RuntimeCall*     x);
 539   void do_MemBar         (MemBar*          x);
 540   void do_RangeCheckPredicate(RangeCheckPredicate* x);
 541 #ifdef ASSERT
 542   void do_Assert         (Assert*          x);
 543 #endif
 544 };
 545 
 546 
 547 // Because of a static contained within (for the purpose of iteration
 548 // over instructions), it is only valid to have one of these active at
 549 // a time
 550 class NullCheckEliminator: public ValueVisitor {
 551  private:
 552   Optimizer*        _opt;
 553 
 554   ValueSet*         _visitable_instructions;        // Visit each instruction only once per basic block
 555   BlockList*        _work_list;                   // Basic blocks to visit
 556 

 638     _last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);
 639     _last_explicit_null_check->set_can_trap(false);
 640     return _last_explicit_null_check;
 641   }
 642   void        clear_last_explicit_null_check()               { _last_explicit_null_check = NULL; }
 643 
 644   // Handlers for relevant instructions
 645   // (separated out from NullCheckVisitor for clarity)
 646 
 647   // The basic contract is that these must leave the instruction in
 648   // the desired state; must not assume anything about the state of
 649   // the instruction. We make multiple passes over some basic blocks
 650   // and the last pass is the only one whose result is valid.
 651   void handle_AccessField     (AccessField* x);
 652   void handle_ArrayLength     (ArrayLength* x);
 653   void handle_LoadIndexed     (LoadIndexed* x);
 654   void handle_StoreIndexed    (StoreIndexed* x);
 655   void handle_NullCheck       (NullCheck* x);
 656   void handle_Invoke          (Invoke* x);
 657   void handle_NewInstance     (NewInstance* x);

 658   void handle_NewArray        (NewArray* x);
 659   void handle_AccessMonitor   (AccessMonitor* x);
 660   void handle_Intrinsic       (Intrinsic* x);
 661   void handle_ExceptionObject (ExceptionObject* x);
 662   void handle_Phi             (Phi* x);
 663   void handle_ProfileCall     (ProfileCall* x);
 664   void handle_ProfileReturnType (ProfileReturnType* x);

 665 };
 666 
 667 
 668 // NEEDS_CLEANUP
 669 // There may be other instructions which need to clear the last
 670 // explicit null check. Anything across which we can not hoist the
 671 // debug information for a NullCheck instruction must clear it. It
 672 // might be safer to pattern match "NullCheck ; {AccessField,
 673 // ArrayLength, LoadIndexed}" but it is more easily structured this way.
 674 // Should test to see performance hit of clearing it for all handlers
 675 // with empty bodies below. If it is negligible then we should leave
 676 // that in for safety, otherwise should think more about it.
 677 void NullCheckVisitor::do_Phi            (Phi*             x) { nce()->handle_Phi(x);      }
 678 void NullCheckVisitor::do_Local          (Local*           x) {}
 679 void NullCheckVisitor::do_Constant       (Constant*        x) { /* FIXME: handle object constants */ }
 680 void NullCheckVisitor::do_LoadField      (LoadField*       x) { nce()->handle_AccessField(x); }
 681 void NullCheckVisitor::do_StoreField     (StoreField*      x) { nce()->handle_AccessField(x); }
 682 void NullCheckVisitor::do_ArrayLength    (ArrayLength*     x) { nce()->handle_ArrayLength(x); }
 683 void NullCheckVisitor::do_LoadIndexed    (LoadIndexed*     x) { nce()->handle_LoadIndexed(x); }
 684 void NullCheckVisitor::do_StoreIndexed   (StoreIndexed*    x) { nce()->handle_StoreIndexed(x); }
 685 void NullCheckVisitor::do_NegateOp       (NegateOp*        x) {}
 686 void NullCheckVisitor::do_ArithmeticOp   (ArithmeticOp*    x) { if (x->can_trap()) nce()->clear_last_explicit_null_check(); }
 687 void NullCheckVisitor::do_ShiftOp        (ShiftOp*         x) {}
 688 void NullCheckVisitor::do_LogicOp        (LogicOp*         x) {}
 689 void NullCheckVisitor::do_CompareOp      (CompareOp*       x) {}
 690 void NullCheckVisitor::do_IfOp           (IfOp*            x) {}
 691 void NullCheckVisitor::do_Convert        (Convert*         x) {}
 692 void NullCheckVisitor::do_NullCheck      (NullCheck*       x) { nce()->handle_NullCheck(x); }
 693 void NullCheckVisitor::do_TypeCast       (TypeCast*        x) {}
 694 void NullCheckVisitor::do_Invoke         (Invoke*          x) { nce()->handle_Invoke(x); }
 695 void NullCheckVisitor::do_NewInstance    (NewInstance*     x) { nce()->handle_NewInstance(x); }

 696 void NullCheckVisitor::do_NewTypeArray   (NewTypeArray*    x) { nce()->handle_NewArray(x); }
 697 void NullCheckVisitor::do_NewObjectArray (NewObjectArray*  x) { nce()->handle_NewArray(x); }
 698 void NullCheckVisitor::do_NewMultiArray  (NewMultiArray*   x) { nce()->handle_NewArray(x); }

 699 void NullCheckVisitor::do_CheckCast      (CheckCast*       x) { nce()->clear_last_explicit_null_check(); }
 700 void NullCheckVisitor::do_InstanceOf     (InstanceOf*      x) {}
 701 void NullCheckVisitor::do_MonitorEnter   (MonitorEnter*    x) { nce()->handle_AccessMonitor(x); }
 702 void NullCheckVisitor::do_MonitorExit    (MonitorExit*     x) { nce()->handle_AccessMonitor(x); }
 703 void NullCheckVisitor::do_Intrinsic      (Intrinsic*       x) { nce()->handle_Intrinsic(x);     }
 704 void NullCheckVisitor::do_BlockBegin     (BlockBegin*      x) {}
 705 void NullCheckVisitor::do_Goto           (Goto*            x) {}
 706 void NullCheckVisitor::do_If             (If*              x) {}
 707 void NullCheckVisitor::do_TableSwitch    (TableSwitch*     x) {}
 708 void NullCheckVisitor::do_LookupSwitch   (LookupSwitch*    x) {}
 709 void NullCheckVisitor::do_Return         (Return*          x) {}
 710 void NullCheckVisitor::do_Throw          (Throw*           x) { nce()->clear_last_explicit_null_check(); }
 711 void NullCheckVisitor::do_Base           (Base*            x) {}
 712 void NullCheckVisitor::do_OsrEntry       (OsrEntry*        x) {}
 713 void NullCheckVisitor::do_ExceptionObject(ExceptionObject* x) { nce()->handle_ExceptionObject(x); }
 714 void NullCheckVisitor::do_RoundFP        (RoundFP*         x) {}
 715 void NullCheckVisitor::do_UnsafeGet      (UnsafeGet*       x) {}
 716 void NullCheckVisitor::do_UnsafePut      (UnsafePut*       x) {}
 717 void NullCheckVisitor::do_UnsafeGetAndSet(UnsafeGetAndSet* x) {}
 718 void NullCheckVisitor::do_ProfileCall    (ProfileCall*     x) { nce()->clear_last_explicit_null_check();
 719                                                                 nce()->handle_ProfileCall(x); }
 720 void NullCheckVisitor::do_ProfileReturnType (ProfileReturnType* x) { nce()->handle_ProfileReturnType(x); }
 721 void NullCheckVisitor::do_ProfileInvoke  (ProfileInvoke*   x) {}

 722 void NullCheckVisitor::do_RuntimeCall    (RuntimeCall*     x) {}
 723 void NullCheckVisitor::do_MemBar         (MemBar*          x) {}
 724 void NullCheckVisitor::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
 725 #ifdef ASSERT
 726 void NullCheckVisitor::do_Assert         (Assert*          x) {}
 727 #endif
 728 
 729 void NullCheckEliminator::visit(Value* p) {
 730   assert(*p != NULL, "should not find NULL instructions");
 731   if (visitable(*p)) {
 732     mark_visited(*p);
 733     (*p)->visit(&_visitor);
 734   }
 735 }
 736 
 737 bool NullCheckEliminator::merge_state_for(BlockBegin* block, ValueSet* incoming_state) {
 738   ValueSet* state = state_for(block);
 739   if (state == NULL) {
 740     state = incoming_state->copy();
 741     set_state_for(block, state);

1025   }
1026 
1027   Value recv = x->receiver();
1028   if (!set_contains(recv)) {
1029     set_put(recv);
1030     if (PrintNullCheckElimination) {
1031       tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
1032     }
1033   }
1034   clear_last_explicit_null_check();
1035 }
1036 
1037 
1038 void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
1039   set_put(x);
1040   if (PrintNullCheckElimination) {
1041     tty->print_cr("NewInstance %d is non-null", x->id());
1042   }
1043 }
1044 







1045 
1046 void NullCheckEliminator::handle_NewArray(NewArray* x) {
1047   set_put(x);
1048   if (PrintNullCheckElimination) {
1049     tty->print_cr("NewArray %d is non-null", x->id());
1050   }
1051 }
1052 
1053 
1054 void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1055   set_put(x);
1056   if (PrintNullCheckElimination) {
1057     tty->print_cr("ExceptionObject %d is non-null", x->id());
1058   }
1059 }
1060 
1061 
1062 void NullCheckEliminator::handle_AccessMonitor(AccessMonitor* x) {
1063   Value obj = x->obj();
1064   if (set_contains(obj)) {

1129     // Value is non-null => update Phi
1130     if (PrintNullCheckElimination) {
1131       tty->print_cr("Eliminated Phi %d's null check for phifun because all inputs are non-null", x->id());
1132     }
1133     x->set_needs_null_check(false);
1134   } else if (set_contains(x)) {
1135     set_remove(x);
1136   }
1137 }
1138 
1139 void NullCheckEliminator::handle_ProfileCall(ProfileCall* x) {
1140   for (int i = 0; i < x->nb_profiled_args(); i++) {
1141     x->set_arg_needs_null_check(i, !set_contains(x->profiled_arg_at(i)));
1142   }
1143 }
1144 
1145 void NullCheckEliminator::handle_ProfileReturnType(ProfileReturnType* x) {
1146   x->set_needs_null_check(!set_contains(x->ret()));
1147 }
1148 





1149 void Optimizer::eliminate_null_checks() {
1150   ResourceMark rm;
1151 
1152   NullCheckEliminator nce(this);
1153 
1154   if (PrintNullCheckElimination) {
1155     tty->print_cr("Starting null check elimination for method %s::%s%s",
1156                   ir()->method()->holder()->name()->as_utf8(),
1157                   ir()->method()->name()->as_utf8(),
1158                   ir()->method()->signature()->as_symbol()->as_utf8());
1159   }
1160 
1161   // Apply to graph
1162   nce.iterate(ir()->start());
1163 
1164   // walk over the graph looking for exception
1165   // handlers and iterate over them as well
1166   int nblocks = BlockBegin::number_of_blocks();
1167   BlockList blocks(nblocks);
1168   boolArray visited_block(nblocks, nblocks, false);

  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_ == NULL) 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 

 183 
 184   // 2) substitute conditional expression
 185   //    with an IfOp followed by a Goto
 186   // cut if_ away and get node before
 187   Instruction* cur_end = if_->prev();
 188 
 189   // append constants of true- and false-block if necessary
 190   // clone constants because original block must not be destroyed
 191   assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
 192   if (t_value == t_const) {
 193     t_value = new Constant(t_const->type());
 194     NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
 195     cur_end = cur_end->set_next(t_value);
 196   }
 197   if (f_value == f_const) {
 198     f_value = new Constant(f_const->type());
 199     NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
 200     cur_end = cur_end->set_next(f_value);
 201   }
 202 
 203   Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value,
 204                            if_->state_before(), if_->substitutability_check());
 205   assert(result != NULL, "make_ifop must return a non-null instruction");
 206   if (!result->is_linked() && result->can_be_linked()) {
 207     NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
 208     cur_end = cur_end->set_next(result);
 209   }
 210 
 211   // append Goto to successor
 212   ValueStack* state_before = if_->state_before();
 213   Goto* goto_ = new Goto(sux, state_before, is_safepoint);
 214 
 215   // prepare state for Goto
 216   ValueStack* goto_state = if_state;
 217   goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
 218   goto_state->push(result->type(), result);
 219   assert(goto_state->is_same(sux_state), "states must match now");
 220   goto_->set_state(goto_state);
 221 
 222   cur_end = cur_end->set_next(goto_, goto_state->bci());
 223 
 224   // Adjust control flow graph

 236   // update block end
 237   block->set_end(goto_);
 238 
 239   // substitute the phi if possible
 240   if (sux_phi->as_Phi()->operand_count() == 1) {
 241     assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
 242     sux_phi->set_subst(result);
 243     _has_substitution = true;
 244   }
 245 
 246   // 3) successfully eliminated a conditional expression
 247   _cee_count++;
 248   if (PrintCEE) {
 249     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());
 250     tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
 251   }
 252 
 253   _hir->verify();
 254 }
 255 
 256 Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval,
 257                                ValueStack* state_before, bool substitutability_check) {
 258   if (!OptimizeIfOps) {
 259     return new IfOp(x, cond, y, tval, fval, state_before, substitutability_check);
 260   }
 261 
 262   tval = tval->subst();
 263   fval = fval->subst();
 264   if (tval == fval) {
 265     _ifop_count++;
 266     return tval;
 267   }
 268 
 269   x = x->subst();
 270   y = y->subst();
 271 
 272   Constant* y_const = y->as_Constant();
 273   if (y_const != NULL) {
 274     IfOp* x_ifop = x->as_IfOp();
 275     if (x_ifop != NULL) {                 // x is an ifop, y is a constant
 276       Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
 277       Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
 278 
 279       if (x_tval_const != NULL && x_fval_const != NULL) {
 280         Instruction::Condition x_ifop_cond = x_ifop->cond();
 281 
 282         Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
 283         Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
 284 
 285         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 286         if (t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable) {
 287           Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
 288           Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
 289 
 290           _ifop_count++;
 291           if (new_tval == new_fval) {
 292             return new_tval;
 293           } else {
 294             return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval, state_before, substitutability_check);
 295           }
 296         }
 297       }
 298     } else {
 299       Constant* x_const = x->as_Constant();
 300       if (x_const != NULL) {         // x and y are constants
 301         Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
 302         // not_comparable here is a valid return in case we're comparing unloaded oop constants
 303         if (x_compare_res != Constant::not_comparable) {
 304           _ifop_count++;
 305           return x_compare_res == Constant::cond_true ? tval : fval;
 306         }
 307       }
 308     }
 309   }
 310   return new IfOp(x, cond, y, tval, fval, state_before, substitutability_check);
 311 }
 312 
 313 void Optimizer::eliminate_conditional_expressions() {
 314   // find conditional expressions & replace them with IfOps
 315   CE_Eliminator ce(ir());
 316 }
 317 
 318 class BlockMerger: public BlockClosure {
 319  private:
 320   IR* _hir;
 321   int _merge_count;              // the number of block pairs successfully merged
 322 
 323  public:
 324   BlockMerger(IR* hir)
 325   : _hir(hir)
 326   , _merge_count(0)
 327   {
 328     _hir->iterate_preorder(this);
 329     CompileLog* log = _hir->compilation()->log();
 330     if (log != NULL)

 399 
 400         // debugging output
 401         _merge_count++;
 402         if (PrintBlockElimination) {
 403           tty->print_cr("%d. merged B%d & B%d (stack size = %d)",
 404                         _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());
 405         }
 406 
 407         _hir->verify();
 408 
 409         If* if_ = block->end()->as_If();
 410         if (if_) {
 411           IfOp* ifop    = if_->x()->as_IfOp();
 412           Constant* con = if_->y()->as_Constant();
 413           bool swapped = false;
 414           if (!con || !ifop) {
 415             ifop = if_->y()->as_IfOp();
 416             con  = if_->x()->as_Constant();
 417             swapped = true;
 418           }
 419           if (con && ifop && !ifop->substitutability_check()) {
 420             Constant* tval = ifop->tval()->as_Constant();
 421             Constant* fval = ifop->fval()->as_Constant();
 422             if (tval && fval) {
 423               // Find the instruction before if_, starting with ifop.
 424               // When if_ and ifop are not in the same block, prev
 425               // becomes NULL In such (rare) cases it is not
 426               // profitable to perform the optimization.
 427               Value prev = ifop;
 428               while (prev != NULL && prev->next() != if_) {
 429                 prev = prev->next();
 430               }
 431 
 432               if (prev != NULL) {
 433                 Instruction::Condition cond = if_->cond();
 434                 BlockBegin* tsux = if_->tsux();
 435                 BlockBegin* fsux = if_->fsux();
 436                 if (swapped) {
 437                   cond = Instruction::mirror(cond);
 438                 }
 439 
 440                 BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);
 441                 BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);
 442                 if (tblock != fblock && !if_->is_safepoint()) {
 443                   If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),
 444                                      tblock, fblock, if_->state_before(), if_->is_safepoint(), ifop->substitutability_check());
 445                   newif->set_state(if_->state()->copy());
 446 
 447                   assert(prev->next() == if_, "must be guaranteed by above search");
 448                   NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));
 449                   prev->set_next(newif);
 450                   block->set_end(newif);
 451 
 452                   _merge_count++;
 453                   if (PrintBlockElimination) {
 454                     tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());
 455                   }
 456 
 457                   _hir->verify();
 458                 }
 459               }
 460             }
 461           }
 462         }
 463 
 464         return true;

 496 
 497   void do_Phi            (Phi*             x);
 498   void do_Local          (Local*           x);
 499   void do_Constant       (Constant*        x);
 500   void do_LoadField      (LoadField*       x);
 501   void do_StoreField     (StoreField*      x);
 502   void do_ArrayLength    (ArrayLength*     x);
 503   void do_LoadIndexed    (LoadIndexed*     x);
 504   void do_StoreIndexed   (StoreIndexed*    x);
 505   void do_NegateOp       (NegateOp*        x);
 506   void do_ArithmeticOp   (ArithmeticOp*    x);
 507   void do_ShiftOp        (ShiftOp*         x);
 508   void do_LogicOp        (LogicOp*         x);
 509   void do_CompareOp      (CompareOp*       x);
 510   void do_IfOp           (IfOp*            x);
 511   void do_Convert        (Convert*         x);
 512   void do_NullCheck      (NullCheck*       x);
 513   void do_TypeCast       (TypeCast*        x);
 514   void do_Invoke         (Invoke*          x);
 515   void do_NewInstance    (NewInstance*     x);
 516   void do_NewInlineTypeInstance(NewInlineTypeInstance* x);
 517   void do_NewTypeArray   (NewTypeArray*    x);
 518   void do_NewObjectArray (NewObjectArray*  x);
 519   void do_NewMultiArray  (NewMultiArray*   x);
 520   void do_Deoptimize     (Deoptimize*      x);
 521   void do_CheckCast      (CheckCast*       x);
 522   void do_InstanceOf     (InstanceOf*      x);
 523   void do_MonitorEnter   (MonitorEnter*    x);
 524   void do_MonitorExit    (MonitorExit*     x);
 525   void do_Intrinsic      (Intrinsic*       x);
 526   void do_BlockBegin     (BlockBegin*      x);
 527   void do_Goto           (Goto*            x);
 528   void do_If             (If*              x);
 529   void do_TableSwitch    (TableSwitch*     x);
 530   void do_LookupSwitch   (LookupSwitch*    x);
 531   void do_Return         (Return*          x);
 532   void do_Throw          (Throw*           x);
 533   void do_Base           (Base*            x);
 534   void do_OsrEntry       (OsrEntry*        x);
 535   void do_ExceptionObject(ExceptionObject* x);
 536   void do_RoundFP        (RoundFP*         x);
 537   void do_UnsafeGet      (UnsafeGet*       x);
 538   void do_UnsafePut      (UnsafePut*       x);
 539   void do_UnsafeGetAndSet(UnsafeGetAndSet* x);
 540   void do_ProfileCall    (ProfileCall*     x);
 541   void do_ProfileReturnType (ProfileReturnType*  x);
 542   void do_ProfileACmpTypes(ProfileACmpTypes*  x);
 543   void do_ProfileInvoke  (ProfileInvoke*   x);
 544   void do_RuntimeCall    (RuntimeCall*     x);
 545   void do_MemBar         (MemBar*          x);
 546   void do_RangeCheckPredicate(RangeCheckPredicate* x);
 547 #ifdef ASSERT
 548   void do_Assert         (Assert*          x);
 549 #endif
 550 };
 551 
 552 
 553 // Because of a static contained within (for the purpose of iteration
 554 // over instructions), it is only valid to have one of these active at
 555 // a time
 556 class NullCheckEliminator: public ValueVisitor {
 557  private:
 558   Optimizer*        _opt;
 559 
 560   ValueSet*         _visitable_instructions;        // Visit each instruction only once per basic block
 561   BlockList*        _work_list;                   // Basic blocks to visit
 562 

 644     _last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);
 645     _last_explicit_null_check->set_can_trap(false);
 646     return _last_explicit_null_check;
 647   }
 648   void        clear_last_explicit_null_check()               { _last_explicit_null_check = NULL; }
 649 
 650   // Handlers for relevant instructions
 651   // (separated out from NullCheckVisitor for clarity)
 652 
 653   // The basic contract is that these must leave the instruction in
 654   // the desired state; must not assume anything about the state of
 655   // the instruction. We make multiple passes over some basic blocks
 656   // and the last pass is the only one whose result is valid.
 657   void handle_AccessField     (AccessField* x);
 658   void handle_ArrayLength     (ArrayLength* x);
 659   void handle_LoadIndexed     (LoadIndexed* x);
 660   void handle_StoreIndexed    (StoreIndexed* x);
 661   void handle_NullCheck       (NullCheck* x);
 662   void handle_Invoke          (Invoke* x);
 663   void handle_NewInstance     (NewInstance* x);
 664   void handle_NewInlineTypeInstance(NewInlineTypeInstance* x);
 665   void handle_NewArray        (NewArray* x);
 666   void handle_AccessMonitor   (AccessMonitor* x);
 667   void handle_Intrinsic       (Intrinsic* x);
 668   void handle_ExceptionObject (ExceptionObject* x);
 669   void handle_Phi             (Phi* x);
 670   void handle_ProfileCall     (ProfileCall* x);
 671   void handle_ProfileReturnType (ProfileReturnType* x);
 672   void handle_ProfileACmpTypes(ProfileACmpTypes* x);
 673 };
 674 
 675 
 676 // NEEDS_CLEANUP
 677 // There may be other instructions which need to clear the last
 678 // explicit null check. Anything across which we can not hoist the
 679 // debug information for a NullCheck instruction must clear it. It
 680 // might be safer to pattern match "NullCheck ; {AccessField,
 681 // ArrayLength, LoadIndexed}" but it is more easily structured this way.
 682 // Should test to see performance hit of clearing it for all handlers
 683 // with empty bodies below. If it is negligible then we should leave
 684 // that in for safety, otherwise should think more about it.
 685 void NullCheckVisitor::do_Phi            (Phi*             x) { nce()->handle_Phi(x);      }
 686 void NullCheckVisitor::do_Local          (Local*           x) {}
 687 void NullCheckVisitor::do_Constant       (Constant*        x) { /* FIXME: handle object constants */ }
 688 void NullCheckVisitor::do_LoadField      (LoadField*       x) { nce()->handle_AccessField(x); }
 689 void NullCheckVisitor::do_StoreField     (StoreField*      x) { nce()->handle_AccessField(x); }
 690 void NullCheckVisitor::do_ArrayLength    (ArrayLength*     x) { nce()->handle_ArrayLength(x); }
 691 void NullCheckVisitor::do_LoadIndexed    (LoadIndexed*     x) { nce()->handle_LoadIndexed(x); }
 692 void NullCheckVisitor::do_StoreIndexed   (StoreIndexed*    x) { nce()->handle_StoreIndexed(x); }
 693 void NullCheckVisitor::do_NegateOp       (NegateOp*        x) {}
 694 void NullCheckVisitor::do_ArithmeticOp   (ArithmeticOp*    x) { if (x->can_trap()) nce()->clear_last_explicit_null_check(); }
 695 void NullCheckVisitor::do_ShiftOp        (ShiftOp*         x) {}
 696 void NullCheckVisitor::do_LogicOp        (LogicOp*         x) {}
 697 void NullCheckVisitor::do_CompareOp      (CompareOp*       x) {}
 698 void NullCheckVisitor::do_IfOp           (IfOp*            x) {}
 699 void NullCheckVisitor::do_Convert        (Convert*         x) {}
 700 void NullCheckVisitor::do_NullCheck      (NullCheck*       x) { nce()->handle_NullCheck(x); }
 701 void NullCheckVisitor::do_TypeCast       (TypeCast*        x) {}
 702 void NullCheckVisitor::do_Invoke         (Invoke*          x) { nce()->handle_Invoke(x); }
 703 void NullCheckVisitor::do_NewInstance    (NewInstance*     x) { nce()->handle_NewInstance(x); }
 704 void NullCheckVisitor::do_NewInlineTypeInstance(NewInlineTypeInstance* x) { nce()->handle_NewInlineTypeInstance(x); }
 705 void NullCheckVisitor::do_NewTypeArray   (NewTypeArray*    x) { nce()->handle_NewArray(x); }
 706 void NullCheckVisitor::do_NewObjectArray (NewObjectArray*  x) { nce()->handle_NewArray(x); }
 707 void NullCheckVisitor::do_NewMultiArray  (NewMultiArray*   x) { nce()->handle_NewArray(x); }
 708 void NullCheckVisitor::do_Deoptimize     (Deoptimize*      x) {}
 709 void NullCheckVisitor::do_CheckCast      (CheckCast*       x) { nce()->clear_last_explicit_null_check(); }
 710 void NullCheckVisitor::do_InstanceOf     (InstanceOf*      x) {}
 711 void NullCheckVisitor::do_MonitorEnter   (MonitorEnter*    x) { nce()->handle_AccessMonitor(x); }
 712 void NullCheckVisitor::do_MonitorExit    (MonitorExit*     x) { nce()->handle_AccessMonitor(x); }
 713 void NullCheckVisitor::do_Intrinsic      (Intrinsic*       x) { nce()->handle_Intrinsic(x);     }
 714 void NullCheckVisitor::do_BlockBegin     (BlockBegin*      x) {}
 715 void NullCheckVisitor::do_Goto           (Goto*            x) {}
 716 void NullCheckVisitor::do_If             (If*              x) {}
 717 void NullCheckVisitor::do_TableSwitch    (TableSwitch*     x) {}
 718 void NullCheckVisitor::do_LookupSwitch   (LookupSwitch*    x) {}
 719 void NullCheckVisitor::do_Return         (Return*          x) {}
 720 void NullCheckVisitor::do_Throw          (Throw*           x) { nce()->clear_last_explicit_null_check(); }
 721 void NullCheckVisitor::do_Base           (Base*            x) {}
 722 void NullCheckVisitor::do_OsrEntry       (OsrEntry*        x) {}
 723 void NullCheckVisitor::do_ExceptionObject(ExceptionObject* x) { nce()->handle_ExceptionObject(x); }
 724 void NullCheckVisitor::do_RoundFP        (RoundFP*         x) {}
 725 void NullCheckVisitor::do_UnsafeGet      (UnsafeGet*       x) {}
 726 void NullCheckVisitor::do_UnsafePut      (UnsafePut*       x) {}
 727 void NullCheckVisitor::do_UnsafeGetAndSet(UnsafeGetAndSet* x) {}
 728 void NullCheckVisitor::do_ProfileCall    (ProfileCall*     x) { nce()->clear_last_explicit_null_check();
 729                                                                 nce()->handle_ProfileCall(x); }
 730 void NullCheckVisitor::do_ProfileReturnType (ProfileReturnType* x) { nce()->handle_ProfileReturnType(x); }
 731 void NullCheckVisitor::do_ProfileInvoke  (ProfileInvoke*   x) {}
 732 void NullCheckVisitor::do_ProfileACmpTypes(ProfileACmpTypes* x) { nce()->handle_ProfileACmpTypes(x); }
 733 void NullCheckVisitor::do_RuntimeCall    (RuntimeCall*     x) {}
 734 void NullCheckVisitor::do_MemBar         (MemBar*          x) {}
 735 void NullCheckVisitor::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
 736 #ifdef ASSERT
 737 void NullCheckVisitor::do_Assert         (Assert*          x) {}
 738 #endif
 739 
 740 void NullCheckEliminator::visit(Value* p) {
 741   assert(*p != NULL, "should not find NULL instructions");
 742   if (visitable(*p)) {
 743     mark_visited(*p);
 744     (*p)->visit(&_visitor);
 745   }
 746 }
 747 
 748 bool NullCheckEliminator::merge_state_for(BlockBegin* block, ValueSet* incoming_state) {
 749   ValueSet* state = state_for(block);
 750   if (state == NULL) {
 751     state = incoming_state->copy();
 752     set_state_for(block, state);

1036   }
1037 
1038   Value recv = x->receiver();
1039   if (!set_contains(recv)) {
1040     set_put(recv);
1041     if (PrintNullCheckElimination) {
1042       tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
1043     }
1044   }
1045   clear_last_explicit_null_check();
1046 }
1047 
1048 
1049 void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
1050   set_put(x);
1051   if (PrintNullCheckElimination) {
1052     tty->print_cr("NewInstance %d is non-null", x->id());
1053   }
1054 }
1055 
1056 void NullCheckEliminator::handle_NewInlineTypeInstance(NewInlineTypeInstance* x) {
1057   set_put(x);
1058   if (PrintNullCheckElimination) {
1059     tty->print_cr("NewInlineTypeInstance %d is non-null", x->id());
1060   }
1061 }
1062 
1063 
1064 void NullCheckEliminator::handle_NewArray(NewArray* x) {
1065   set_put(x);
1066   if (PrintNullCheckElimination) {
1067     tty->print_cr("NewArray %d is non-null", x->id());
1068   }
1069 }
1070 
1071 
1072 void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1073   set_put(x);
1074   if (PrintNullCheckElimination) {
1075     tty->print_cr("ExceptionObject %d is non-null", x->id());
1076   }
1077 }
1078 
1079 
1080 void NullCheckEliminator::handle_AccessMonitor(AccessMonitor* x) {
1081   Value obj = x->obj();
1082   if (set_contains(obj)) {

1147     // Value is non-null => update Phi
1148     if (PrintNullCheckElimination) {
1149       tty->print_cr("Eliminated Phi %d's null check for phifun because all inputs are non-null", x->id());
1150     }
1151     x->set_needs_null_check(false);
1152   } else if (set_contains(x)) {
1153     set_remove(x);
1154   }
1155 }
1156 
1157 void NullCheckEliminator::handle_ProfileCall(ProfileCall* x) {
1158   for (int i = 0; i < x->nb_profiled_args(); i++) {
1159     x->set_arg_needs_null_check(i, !set_contains(x->profiled_arg_at(i)));
1160   }
1161 }
1162 
1163 void NullCheckEliminator::handle_ProfileReturnType(ProfileReturnType* x) {
1164   x->set_needs_null_check(!set_contains(x->ret()));
1165 }
1166 
1167 void NullCheckEliminator::handle_ProfileACmpTypes(ProfileACmpTypes* x) {
1168   x->set_left_maybe_null(!set_contains(x->left()));
1169   x->set_right_maybe_null(!set_contains(x->right()));
1170 }
1171 
1172 void Optimizer::eliminate_null_checks() {
1173   ResourceMark rm;
1174 
1175   NullCheckEliminator nce(this);
1176 
1177   if (PrintNullCheckElimination) {
1178     tty->print_cr("Starting null check elimination for method %s::%s%s",
1179                   ir()->method()->holder()->name()->as_utf8(),
1180                   ir()->method()->name()->as_utf8(),
1181                   ir()->method()->signature()->as_symbol()->as_utf8());
1182   }
1183 
1184   // Apply to graph
1185   nce.iterate(ir()->start());
1186 
1187   // walk over the graph looking for exception
1188   // handlers and iterate over them as well
1189   int nblocks = BlockBegin::number_of_blocks();
1190   BlockList blocks(nblocks);
1191   boolArray visited_block(nblocks, nblocks, false);
< prev index next >