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
201
202 // 2) substitute conditional expression
203 // with an IfOp followed by a Goto
204 // cut if_ away and get node before
205 Instruction* cur_end = if_->prev();
206
207 // append constants of true- and false-block if necessary
208 // clone constants because original block must not be destroyed
209 assert((t_value != f_const && f_value != t_const) || t_const == f_const, "mismatch");
210 if (t_value == t_const) {
211 t_value = new Constant(t_const->type());
212 NOT_PRODUCT(t_value->set_printable_bci(if_->printable_bci()));
213 cur_end = cur_end->set_next(t_value);
214 }
215 if (f_value == f_const) {
216 f_value = new Constant(f_const->type());
217 NOT_PRODUCT(f_value->set_printable_bci(if_->printable_bci()));
218 cur_end = cur_end->set_next(f_value);
219 }
220
221 Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);
222 assert(result != NULL, "make_ifop must return a non-null instruction");
223 if (!result->is_linked() && result->can_be_linked()) {
224 NOT_PRODUCT(result->set_printable_bci(if_->printable_bci()));
225 cur_end = cur_end->set_next(result);
226 }
227
228 // append Goto to successor
229 ValueStack* state_before = if_->state_before();
230 Goto* goto_ = new Goto(sux, state_before, is_safepoint);
231
232 // prepare state for Goto
233 ValueStack* goto_state = if_state;
234 goto_state = goto_state->copy(ValueStack::StateAfter, goto_state->bci());
235 goto_state->push(result->type(), result);
236 assert(goto_state->is_same(sux_state), "states must match now");
237 goto_->set_state(goto_state);
238
239 cur_end = cur_end->set_next(goto_, goto_state->bci());
240
241 // Adjust control flow graph
256 // substitute the phi if possible
257 if (sux_phi->as_Phi()->operand_count() == 1) {
258 assert(sux_phi->as_Phi()->operand_at(0) == result, "screwed up phi");
259 sux_phi->set_subst(result);
260 _has_substitution = true;
261 }
262
263 // 3) successfully eliminated a conditional expression
264 _cee_count++;
265 if (PrintCEE) {
266 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());
267 tty->print_cr("%d. IfOp in B%d", ifop_count(), block->block_id());
268 }
269
270 #ifdef DO_DELAYED_VERIFICATION
271 _hir->verify_local(blocks_to_verify_later);
272 #endif // DO_DELAYED_VERIFICATION
273
274 }
275
276 Value CE_Eliminator::make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval) {
277 if (!OptimizeIfOps) {
278 return new IfOp(x, cond, y, tval, fval);
279 }
280
281 tval = tval->subst();
282 fval = fval->subst();
283 if (tval == fval) {
284 _ifop_count++;
285 return tval;
286 }
287
288 x = x->subst();
289 y = y->subst();
290
291 Constant* y_const = y->as_Constant();
292 if (y_const != NULL) {
293 IfOp* x_ifop = x->as_IfOp();
294 if (x_ifop != NULL) { // x is an ifop, y is a constant
295 Constant* x_tval_const = x_ifop->tval()->subst()->as_Constant();
296 Constant* x_fval_const = x_ifop->fval()->subst()->as_Constant();
297
298 if (x_tval_const != NULL && x_fval_const != NULL) {
299 Instruction::Condition x_ifop_cond = x_ifop->cond();
300
301 Constant::CompareResult t_compare_res = x_tval_const->compare(cond, y_const);
302 Constant::CompareResult f_compare_res = x_fval_const->compare(cond, y_const);
303
304 // not_comparable here is a valid return in case we're comparing unloaded oop constants
305 if (t_compare_res != Constant::not_comparable && f_compare_res != Constant::not_comparable) {
306 Value new_tval = t_compare_res == Constant::cond_true ? tval : fval;
307 Value new_fval = f_compare_res == Constant::cond_true ? tval : fval;
308
309 _ifop_count++;
310 if (new_tval == new_fval) {
311 return new_tval;
312 } else {
313 return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
314 }
315 }
316 }
317 } else {
318 Constant* x_const = x->as_Constant();
319 if (x_const != NULL) { // x and y are constants
320 Constant::CompareResult x_compare_res = x_const->compare(cond, y_const);
321 // not_comparable here is a valid return in case we're comparing unloaded oop constants
322 if (x_compare_res != Constant::not_comparable) {
323 _ifop_count++;
324 return x_compare_res == Constant::cond_true ? tval : fval;
325 }
326 }
327 }
328 }
329 return new IfOp(x, cond, y, tval, fval);
330 }
331
332 void Optimizer::eliminate_conditional_expressions() {
333 // find conditional expressions & replace them with IfOps
334 CE_Eliminator ce(ir());
335 }
336
337 // This removes others' relation to block, but doesn't empty block's lists
338 void disconnect_from_graph(BlockBegin* block) {
339 for (int p = 0; p < block->number_of_preds(); p++) {
340 BlockBegin* pred = block->pred_at(p);
341 int idx;
342 while ((idx = pred->end()->find_sux(block)) >= 0) {
343 pred->end()->remove_sux_at(idx);
344 }
345 }
346 for (int s = 0; s < block->number_of_sux(); s++) {
347 block->sux_at(s)->remove_predecessor(block);
348 }
349 }
449 _merge_count++;
450 if (PrintBlockElimination) {
451 tty->print_cr("%d. merged B%d & B%d (stack size = %d)",
452 _merge_count, block->block_id(), sux->block_id(), sux->state()->stack_size());
453 }
454
455 #ifdef DO_DELAYED_VERIFICATION
456 _hir->verify_local(blocks_to_verify_later);
457 #endif // DO_DELAYED_VERIFICATION
458
459 If* if_ = block->end()->as_If();
460 if (if_) {
461 IfOp* ifop = if_->x()->as_IfOp();
462 Constant* con = if_->y()->as_Constant();
463 bool swapped = false;
464 if (!con || !ifop) {
465 ifop = if_->y()->as_IfOp();
466 con = if_->x()->as_Constant();
467 swapped = true;
468 }
469 if (con && ifop) {
470 Constant* tval = ifop->tval()->as_Constant();
471 Constant* fval = ifop->fval()->as_Constant();
472 if (tval && fval) {
473 // Find the instruction before if_, starting with ifop.
474 // When if_ and ifop are not in the same block, prev
475 // becomes NULL In such (rare) cases it is not
476 // profitable to perform the optimization.
477 Value prev = ifop;
478 while (prev != NULL && prev->next() != if_) {
479 prev = prev->next();
480 }
481
482 if (prev != NULL) {
483 Instruction::Condition cond = if_->cond();
484 BlockBegin* tsux = if_->tsux();
485 BlockBegin* fsux = if_->fsux();
486 if (swapped) {
487 cond = Instruction::mirror(cond);
488 }
489
490 BlockBegin* tblock = tval->compare(cond, con, tsux, fsux);
491 BlockBegin* fblock = fval->compare(cond, con, tsux, fsux);
492 if (tblock != fblock && !if_->is_safepoint()) {
493 If* newif = new If(ifop->x(), ifop->cond(), false, ifop->y(),
494 tblock, fblock, if_->state_before(), if_->is_safepoint());
495 newif->set_state(if_->state()->copy());
496
497 assert(prev->next() == if_, "must be guaranteed by above search");
498 NOT_PRODUCT(newif->set_printable_bci(if_->printable_bci()));
499 prev->set_next(newif);
500 block->set_end(newif);
501
502 _merge_count++;
503 if (PrintBlockElimination) {
504 tty->print_cr("%d. replaced If and IfOp at end of B%d with single If", _merge_count, block->block_id());
505 }
506
507 #ifdef DO_DELAYED_VERIFICATION
508 _hir->verify_local(blocks_to_verify_later);
509 #endif // DO_DELAYED_VERIFICATION
510 }
511 }
512 }
513 }
514 }
545
546 void do_Phi (Phi* x);
547 void do_Local (Local* x);
548 void do_Constant (Constant* x);
549 void do_LoadField (LoadField* x);
550 void do_StoreField (StoreField* x);
551 void do_ArrayLength (ArrayLength* x);
552 void do_LoadIndexed (LoadIndexed* x);
553 void do_StoreIndexed (StoreIndexed* x);
554 void do_NegateOp (NegateOp* x);
555 void do_ArithmeticOp (ArithmeticOp* x);
556 void do_ShiftOp (ShiftOp* x);
557 void do_LogicOp (LogicOp* x);
558 void do_CompareOp (CompareOp* x);
559 void do_IfOp (IfOp* x);
560 void do_Convert (Convert* x);
561 void do_NullCheck (NullCheck* x);
562 void do_TypeCast (TypeCast* x);
563 void do_Invoke (Invoke* x);
564 void do_NewInstance (NewInstance* x);
565 void do_NewTypeArray (NewTypeArray* x);
566 void do_NewObjectArray (NewObjectArray* x);
567 void do_NewMultiArray (NewMultiArray* x);
568 void do_CheckCast (CheckCast* x);
569 void do_InstanceOf (InstanceOf* x);
570 void do_MonitorEnter (MonitorEnter* x);
571 void do_MonitorExit (MonitorExit* x);
572 void do_Intrinsic (Intrinsic* x);
573 void do_BlockBegin (BlockBegin* x);
574 void do_Goto (Goto* x);
575 void do_If (If* x);
576 void do_TableSwitch (TableSwitch* x);
577 void do_LookupSwitch (LookupSwitch* x);
578 void do_Return (Return* x);
579 void do_Throw (Throw* x);
580 void do_Base (Base* x);
581 void do_OsrEntry (OsrEntry* x);
582 void do_ExceptionObject(ExceptionObject* x);
583 void do_RoundFP (RoundFP* x);
584 void do_UnsafeGet (UnsafeGet* x);
585 void do_UnsafePut (UnsafePut* x);
586 void do_UnsafeGetAndSet(UnsafeGetAndSet* x);
587 void do_ProfileCall (ProfileCall* x);
588 void do_ProfileReturnType (ProfileReturnType* x);
589 void do_ProfileInvoke (ProfileInvoke* x);
590 void do_RuntimeCall (RuntimeCall* x);
591 void do_MemBar (MemBar* x);
592 void do_RangeCheckPredicate(RangeCheckPredicate* x);
593 #ifdef ASSERT
594 void do_Assert (Assert* x);
595 #endif
596 };
597
598
599 // Because of a static contained within (for the purpose of iteration
600 // over instructions), it is only valid to have one of these active at
601 // a time
602 class NullCheckEliminator: public ValueVisitor {
603 private:
604 Optimizer* _opt;
605
606 ValueSet* _visitable_instructions; // Visit each instruction only once per basic block
607 BlockList* _work_list; // Basic blocks to visit
608
690 _last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);
691 _last_explicit_null_check->set_can_trap(false);
692 return _last_explicit_null_check;
693 }
694 void clear_last_explicit_null_check() { _last_explicit_null_check = NULL; }
695
696 // Handlers for relevant instructions
697 // (separated out from NullCheckVisitor for clarity)
698
699 // The basic contract is that these must leave the instruction in
700 // the desired state; must not assume anything about the state of
701 // the instruction. We make multiple passes over some basic blocks
702 // and the last pass is the only one whose result is valid.
703 void handle_AccessField (AccessField* x);
704 void handle_ArrayLength (ArrayLength* x);
705 void handle_LoadIndexed (LoadIndexed* x);
706 void handle_StoreIndexed (StoreIndexed* x);
707 void handle_NullCheck (NullCheck* x);
708 void handle_Invoke (Invoke* x);
709 void handle_NewInstance (NewInstance* x);
710 void handle_NewArray (NewArray* x);
711 void handle_AccessMonitor (AccessMonitor* x);
712 void handle_Intrinsic (Intrinsic* x);
713 void handle_ExceptionObject (ExceptionObject* x);
714 void handle_Phi (Phi* x);
715 void handle_ProfileCall (ProfileCall* x);
716 void handle_ProfileReturnType (ProfileReturnType* x);
717 };
718
719
720 // NEEDS_CLEANUP
721 // There may be other instructions which need to clear the last
722 // explicit null check. Anything across which we can not hoist the
723 // debug information for a NullCheck instruction must clear it. It
724 // might be safer to pattern match "NullCheck ; {AccessField,
725 // ArrayLength, LoadIndexed}" but it is more easily structured this way.
726 // Should test to see performance hit of clearing it for all handlers
727 // with empty bodies below. If it is negligible then we should leave
728 // that in for safety, otherwise should think more about it.
729 void NullCheckVisitor::do_Phi (Phi* x) { nce()->handle_Phi(x); }
730 void NullCheckVisitor::do_Local (Local* x) {}
731 void NullCheckVisitor::do_Constant (Constant* x) { /* FIXME: handle object constants */ }
732 void NullCheckVisitor::do_LoadField (LoadField* x) { nce()->handle_AccessField(x); }
733 void NullCheckVisitor::do_StoreField (StoreField* x) { nce()->handle_AccessField(x); }
734 void NullCheckVisitor::do_ArrayLength (ArrayLength* x) { nce()->handle_ArrayLength(x); }
735 void NullCheckVisitor::do_LoadIndexed (LoadIndexed* x) { nce()->handle_LoadIndexed(x); }
736 void NullCheckVisitor::do_StoreIndexed (StoreIndexed* x) { nce()->handle_StoreIndexed(x); }
737 void NullCheckVisitor::do_NegateOp (NegateOp* x) {}
738 void NullCheckVisitor::do_ArithmeticOp (ArithmeticOp* x) { if (x->can_trap()) nce()->clear_last_explicit_null_check(); }
739 void NullCheckVisitor::do_ShiftOp (ShiftOp* x) {}
740 void NullCheckVisitor::do_LogicOp (LogicOp* x) {}
741 void NullCheckVisitor::do_CompareOp (CompareOp* x) {}
742 void NullCheckVisitor::do_IfOp (IfOp* x) {}
743 void NullCheckVisitor::do_Convert (Convert* x) {}
744 void NullCheckVisitor::do_NullCheck (NullCheck* x) { nce()->handle_NullCheck(x); }
745 void NullCheckVisitor::do_TypeCast (TypeCast* x) {}
746 void NullCheckVisitor::do_Invoke (Invoke* x) { nce()->handle_Invoke(x); }
747 void NullCheckVisitor::do_NewInstance (NewInstance* x) { nce()->handle_NewInstance(x); }
748 void NullCheckVisitor::do_NewTypeArray (NewTypeArray* x) { nce()->handle_NewArray(x); }
749 void NullCheckVisitor::do_NewObjectArray (NewObjectArray* x) { nce()->handle_NewArray(x); }
750 void NullCheckVisitor::do_NewMultiArray (NewMultiArray* x) { nce()->handle_NewArray(x); }
751 void NullCheckVisitor::do_CheckCast (CheckCast* x) { nce()->clear_last_explicit_null_check(); }
752 void NullCheckVisitor::do_InstanceOf (InstanceOf* x) {}
753 void NullCheckVisitor::do_MonitorEnter (MonitorEnter* x) { nce()->handle_AccessMonitor(x); }
754 void NullCheckVisitor::do_MonitorExit (MonitorExit* x) { nce()->handle_AccessMonitor(x); }
755 void NullCheckVisitor::do_Intrinsic (Intrinsic* x) { nce()->handle_Intrinsic(x); }
756 void NullCheckVisitor::do_BlockBegin (BlockBegin* x) {}
757 void NullCheckVisitor::do_Goto (Goto* x) {}
758 void NullCheckVisitor::do_If (If* x) {}
759 void NullCheckVisitor::do_TableSwitch (TableSwitch* x) {}
760 void NullCheckVisitor::do_LookupSwitch (LookupSwitch* x) {}
761 void NullCheckVisitor::do_Return (Return* x) {}
762 void NullCheckVisitor::do_Throw (Throw* x) { nce()->clear_last_explicit_null_check(); }
763 void NullCheckVisitor::do_Base (Base* x) {}
764 void NullCheckVisitor::do_OsrEntry (OsrEntry* x) {}
765 void NullCheckVisitor::do_ExceptionObject(ExceptionObject* x) { nce()->handle_ExceptionObject(x); }
766 void NullCheckVisitor::do_RoundFP (RoundFP* x) {}
767 void NullCheckVisitor::do_UnsafeGet (UnsafeGet* x) {}
768 void NullCheckVisitor::do_UnsafePut (UnsafePut* x) {}
769 void NullCheckVisitor::do_UnsafeGetAndSet(UnsafeGetAndSet* x) {}
770 void NullCheckVisitor::do_ProfileCall (ProfileCall* x) { nce()->clear_last_explicit_null_check();
771 nce()->handle_ProfileCall(x); }
772 void NullCheckVisitor::do_ProfileReturnType (ProfileReturnType* x) { nce()->handle_ProfileReturnType(x); }
773 void NullCheckVisitor::do_ProfileInvoke (ProfileInvoke* x) {}
774 void NullCheckVisitor::do_RuntimeCall (RuntimeCall* x) {}
775 void NullCheckVisitor::do_MemBar (MemBar* x) {}
776 void NullCheckVisitor::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
777 #ifdef ASSERT
778 void NullCheckVisitor::do_Assert (Assert* x) {}
779 #endif
780
781 void NullCheckEliminator::visit(Value* p) {
782 assert(*p != NULL, "should not find NULL instructions");
783 if (visitable(*p)) {
784 mark_visited(*p);
785 (*p)->visit(&_visitor);
786 }
787 }
788
789 bool NullCheckEliminator::merge_state_for(BlockBegin* block, ValueSet* incoming_state) {
790 ValueSet* state = state_for(block);
791 if (state == NULL) {
792 state = incoming_state->copy();
793 set_state_for(block, state);
1077 }
1078
1079 Value recv = x->receiver();
1080 if (!set_contains(recv)) {
1081 set_put(recv);
1082 if (PrintNullCheckElimination) {
1083 tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
1084 }
1085 }
1086 clear_last_explicit_null_check();
1087 }
1088
1089
1090 void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
1091 set_put(x);
1092 if (PrintNullCheckElimination) {
1093 tty->print_cr("NewInstance %d is non-null", x->id());
1094 }
1095 }
1096
1097
1098 void NullCheckEliminator::handle_NewArray(NewArray* x) {
1099 set_put(x);
1100 if (PrintNullCheckElimination) {
1101 tty->print_cr("NewArray %d is non-null", x->id());
1102 }
1103 }
1104
1105
1106 void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1107 set_put(x);
1108 if (PrintNullCheckElimination) {
1109 tty->print_cr("ExceptionObject %d is non-null", x->id());
1110 }
1111 }
1112
1113
1114 void NullCheckEliminator::handle_AccessMonitor(AccessMonitor* x) {
1115 Value obj = x->obj();
1116 if (set_contains(obj)) {
1181 // Value is non-null => update Phi
1182 if (PrintNullCheckElimination) {
1183 tty->print_cr("Eliminated Phi %d's null check for phifun because all inputs are non-null", x->id());
1184 }
1185 x->set_needs_null_check(false);
1186 } else if (set_contains(x)) {
1187 set_remove(x);
1188 }
1189 }
1190
1191 void NullCheckEliminator::handle_ProfileCall(ProfileCall* x) {
1192 for (int i = 0; i < x->nb_profiled_args(); i++) {
1193 x->set_arg_needs_null_check(i, !set_contains(x->profiled_arg_at(i)));
1194 }
1195 }
1196
1197 void NullCheckEliminator::handle_ProfileReturnType(ProfileReturnType* x) {
1198 x->set_needs_null_check(!set_contains(x->ret()));
1199 }
1200
1201 void Optimizer::eliminate_null_checks() {
1202 ResourceMark rm;
1203
1204 NullCheckEliminator nce(this);
1205
1206 if (PrintNullCheckElimination) {
1207 tty->print_cr("Starting null check elimination for method %s::%s%s",
1208 ir()->method()->holder()->name()->as_utf8(),
1209 ir()->method()->name()->as_utf8(),
1210 ir()->method()->signature()->as_symbol()->as_utf8());
1211 }
1212
1213 // Apply to graph
1214 nce.iterate(ir()->start());
1215
1216 // walk over the graph looking for exception
1217 // handlers and iterate over them as well
1218 int nblocks = BlockBegin::number_of_blocks();
1219 BlockList blocks(nblocks);
1220 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
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 != NULL, "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
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 != NULL) {
296 IfOp* x_ifop = x->as_IfOp();
297 if (x_ifop != NULL) { // 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 != NULL && x_fval_const != NULL) {
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 != NULL) { // 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 }
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 != NULL && prev->next() != if_) {
482 prev = prev->next();
483 }
484
485 if (prev != NULL) {
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 }
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
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 = NULL; }
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 != NULL, "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 == NULL) {
803 state = incoming_state->copy();
804 set_state_for(block, state);
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)) {
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);
|