2
* Copyright (c) 1999, 2024, Oracle and/or its affiliates. All rights reserved.
3
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
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
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"
35
typedef GrowableArray<ValueSet*> ValueSetList;
37
Optimizer::Optimizer(IR* ir) {
38
assert(ir->is_valid(), "IR must be valid");
42
class CE_Eliminator: public BlockClosure {
45
int _cee_count; // the number of CEs successfully eliminated
46
int _ifop_count; // the number of IfOps successfully simplified
47
int _has_substitution;
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);
58
CompileLog* log = _hir->compilation()->log();
60
log->set_context("optimize name='cee'");
64
CompileLog* log = _hir->compilation()->log();
66
log->clear_context(); // skip marker if nothing was printed
69
int cee_count() const { return _cee_count; }
70
int ifop_count() const { return _ifop_count; }
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);
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);
83
if (!xhandler->is_predecessor(block)) {
84
xhandler->add_predecessor(block);
89
virtual void block_do(BlockBegin* block);
92
Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);
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_ == nullptr) return;
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;
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();
113
// one Constant may be present between BlockBegin and BlockEnd
114
Value t_const = nullptr;
115
Value f_const = nullptr;
116
if (t_cur->as_Constant() != nullptr && !t_cur->can_trap()) {
118
t_cur = t_cur->next();
120
if (f_cur->as_Constant() != nullptr && !f_cur->can_trap()) {
122
f_cur = f_cur->next();
125
// check if both branches end with a goto
126
Goto* t_goto = t_cur->as_Goto();
127
if (t_goto == nullptr) return;
128
Goto* f_goto = f_cur->as_Goto();
129
if (f_goto == nullptr) return;
131
// check if both gotos merge into the same block
132
BlockBegin* sux = t_goto->default_sux();
133
if (sux != f_goto->default_sux()) return;
135
// check if at least one word was pushed on sux_state
136
// inlining depths must match
137
ValueStack* if_state = if_->state();
138
ValueStack* sux_state = sux->state();
139
if (if_state->scope()->level() > sux_state->scope()->level()) {
140
while (sux_state->scope() != if_state->scope()) {
141
if_state = if_state->caller_state();
142
assert(if_state != nullptr, "states do not match up");
144
} else if (if_state->scope()->level() < sux_state->scope()->level()) {
145
while (sux_state->scope() != if_state->scope()) {
146
sux_state = sux_state->caller_state();
147
assert(sux_state != nullptr, "states do not match up");
151
if (sux_state->stack_size() <= if_state->stack_size()) return;
153
// check if phi function is present at end of successor stack and that
154
// only this phi was pushed on the stack
155
Value sux_phi = sux_state->stack_at(if_state->stack_size());
156
if (sux_phi == nullptr || sux_phi->as_Phi() == nullptr || sux_phi->as_Phi()->block() != sux) return;
157
if (sux_phi->type()->size() != sux_state->stack_size() - if_state->stack_size()) return;
159
// get the values that were pushed in the true- and false-branch
160
Value t_value = t_goto->state()->stack_at(if_state->stack_size());
161
Value f_value = f_goto->state()->stack_at(if_state->stack_size());
163
// backend does not support floats
164
assert(t_value->type()->base() == f_value->type()->base(), "incompatible types");
165
if (t_value->type()->is_float_kind()) return;
167
// check that successor has no other phi functions but sux_phi
168
// this can happen when t_block or f_block contained additional stores to local variables
169
// that are no longer represented by explicit instructions
170
for_each_phi_fun(sux, phi,
171
if (phi != sux_phi) return;
173
// true and false blocks can't have phis
174
for_each_phi_fun(t_block, phi, return; );
175
for_each_phi_fun(f_block, phi, return; );
177
// Only replace safepoint gotos if state_before information is available (if is a safepoint)
178
bool is_safepoint = if_->is_safepoint();
179
if (!is_safepoint && (t_goto->is_safepoint() || f_goto->is_safepoint())) {
184
#define DO_DELAYED_VERIFICATION
186
* We need to verify the internal representation after modifying it.
187
* Verifying only the blocks that have been tampered with is cheaper than verifying the whole graph, but we must
188
* capture blocks_to_verify_later before making the changes, since they might not be reachable afterwards.
189
* DO_DELAYED_VERIFICATION ensures that the code for this is either enabled in full, or not at all.
193
#ifdef DO_DELAYED_VERIFICATION
194
BlockList blocks_to_verify_later;
195
blocks_to_verify_later.append(block);
196
blocks_to_verify_later.append(t_block);
197
blocks_to_verify_later.append(f_block);
198
blocks_to_verify_later.append(sux);
199
_hir->expand_with_neighborhood(blocks_to_verify_later);
200
#endif // DO_DELAYED_VERIFICATION
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();
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);
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);
221
Value result = make_ifop(if_->x(), if_->cond(), if_->y(), t_value, f_value);
222
assert(result != nullptr, "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);
228
// append Goto to successor
229
ValueStack* state_before = if_->state_before();
230
Goto* goto_ = new Goto(sux, state_before, is_safepoint);
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);
239
cur_end = cur_end->set_next(goto_, goto_state->bci());
241
// Adjust control flow graph
242
BlockBegin::disconnect_edge(block, t_block);
243
BlockBegin::disconnect_edge(block, f_block);
244
if (t_block->number_of_preds() == 0) {
245
BlockBegin::disconnect_edge(t_block, sux);
247
adjust_exception_edges(block, t_block);
248
if (f_block->number_of_preds() == 0) {
249
BlockBegin::disconnect_edge(f_block, sux);
251
adjust_exception_edges(block, f_block);
254
block->set_end(goto_);
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;
263
// 3) successfully eliminated a conditional expression
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());
270
#ifdef DO_DELAYED_VERIFICATION
271
_hir->verify_local(blocks_to_verify_later);
272
#endif // DO_DELAYED_VERIFICATION
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);
281
tval = tval->subst();
282
fval = fval->subst();
291
Constant* y_const = y->as_Constant();
292
if (y_const != nullptr) {
293
IfOp* x_ifop = x->as_IfOp();
294
if (x_ifop != nullptr) { // 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();
298
if (x_tval_const != nullptr && x_fval_const != nullptr) {
299
Instruction::Condition x_ifop_cond = x_ifop->cond();
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);
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;
310
if (new_tval == new_fval) {
313
return new IfOp(x_ifop->x(), x_ifop_cond, x_ifop->y(), new_tval, new_fval);
318
Constant* x_const = x->as_Constant();
319
if (x_const != nullptr) { // 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) {
324
return x_compare_res == Constant::cond_true ? tval : fval;
329
return new IfOp(x, cond, y, tval, fval);
332
void Optimizer::eliminate_conditional_expressions() {
333
// find conditional expressions & replace them with IfOps
334
CE_Eliminator ce(ir());
337
// This removes others' relation to block, but doesn't empty block's lists
338
static void disconnect_from_graph(BlockBegin* block) {
339
for (int p = 0; p < block->number_of_preds(); p++) {
340
BlockBegin* pred = block->pred_at(p);
342
while ((idx = pred->end()->find_sux(block)) >= 0) {
343
pred->end()->remove_sux_at(idx);
346
for (int s = 0; s < block->number_of_sux(); s++) {
347
block->sux_at(s)->remove_predecessor(block);
351
class BlockMerger: public BlockClosure {
354
int _merge_count; // the number of block pairs successfully merged
361
_hir->iterate_preorder(this);
362
CompileLog* log = _hir->compilation()->log();
364
log->set_context("optimize name='eliminate_blocks'");
368
CompileLog* log = _hir->compilation()->log();
370
log->clear_context(); // skip marker if nothing was printed
373
bool try_merge(BlockBegin* block) {
374
BlockEnd* end = block->end();
375
if (end->as_Goto() == nullptr) return false;
377
assert(end->number_of_sux() == 1, "end must have exactly one successor");
378
// Note: It would be sufficient to check for the number of successors (= 1)
379
// in order to decide if this block can be merged potentially. That
380
// would then also include switch statements w/ only a default case.
381
// However, in that case we would need to make sure the switch tag
382
// expression is executed if it can produce observable side effects.
383
// We should probably have the canonicalizer simplifying such switch
384
// statements and then we are sure we don't miss these merge opportunities
385
// here (was bug - gri 7/7/99).
386
BlockBegin* sux = end->default_sux();
387
if (sux->number_of_preds() != 1 || sux->is_entry_block() || end->is_safepoint()) return false;
388
// merge the two blocks
391
// verify that state at the end of block and at the beginning of sux are equal
392
// no phi functions must be present at beginning of sux
393
ValueStack* sux_state = sux->state();
394
ValueStack* end_state = end->state();
396
assert(end_state->scope() == sux_state->scope(), "scopes must match");
397
assert(end_state->stack_size() == sux_state->stack_size(), "stack not equal");
398
assert(end_state->locals_size() == sux_state->locals_size(), "locals not equal");
402
for_each_stack_value(sux_state, index, sux_value) {
403
assert(sux_value == end_state->stack_at(index), "stack not equal");
405
for_each_local_value(sux_state, index, sux_value) {
406
Phi* sux_phi = sux_value->as_Phi();
407
if (sux_phi != nullptr && sux_phi->is_illegal()) continue;
408
assert(sux_value == end_state->local_at(index), "locals not equal");
410
assert(sux_state->caller_state() == end_state->caller_state(), "caller not equal");
413
#ifdef DO_DELAYED_VERIFICATION
414
BlockList blocks_to_verify_later;
415
blocks_to_verify_later.append(block);
416
_hir->expand_with_neighborhood(blocks_to_verify_later);
417
#endif // DO_DELAYED_VERIFICATION
419
// find instruction before end & append first instruction of sux block
420
Instruction* prev = end->prev();
421
Instruction* next = sux->next();
422
assert(prev->as_BlockEnd() == nullptr, "must not be a BlockEnd");
423
prev->set_next(next);
424
prev->fixup_block_pointers();
426
// disconnect this block from all other blocks
427
disconnect_from_graph(sux);
428
#ifdef DO_DELAYED_VERIFICATION
429
blocks_to_verify_later.remove(sux); // Sux is not part of graph anymore
430
#endif // DO_DELAYED_VERIFICATION
431
block->set_end(sux->end());
433
// TODO Should this be done in set_end universally?
434
// add exception handlers of deleted block, if any
435
for (int k = 0; k < sux->number_of_exception_handlers(); k++) {
436
BlockBegin* xhandler = sux->exception_handler_at(k);
437
block->add_exception_handler(xhandler);
439
// TODO This should be in disconnect from graph...
440
// also substitute predecessor of exception handler
441
assert(xhandler->is_predecessor(sux), "missing predecessor");
442
xhandler->remove_predecessor(sux);
443
if (!xhandler->is_predecessor(block)) {
444
xhandler->add_predecessor(block);
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());
455
#ifdef DO_DELAYED_VERIFICATION
456
_hir->verify_local(blocks_to_verify_later);
457
#endif // DO_DELAYED_VERIFICATION
459
If* if_ = block->end()->as_If();
461
IfOp* ifop = if_->x()->as_IfOp();
462
Constant* con = if_->y()->as_Constant();
463
bool swapped = false;
465
ifop = if_->y()->as_IfOp();
466
con = if_->x()->as_Constant();
470
Constant* tval = ifop->tval()->as_Constant();
471
Constant* fval = ifop->fval()->as_Constant();
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.
478
while (prev != nullptr && prev->next() != if_) {
482
if (prev != nullptr) {
483
Instruction::Condition cond = if_->cond();
484
BlockBegin* tsux = if_->tsux();
485
BlockBegin* fsux = if_->fsux();
487
cond = Instruction::mirror(cond);
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());
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);
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());
507
#ifdef DO_DELAYED_VERIFICATION
508
_hir->verify_local(blocks_to_verify_later);
509
#endif // DO_DELAYED_VERIFICATION
519
virtual void block_do(BlockBegin* block) {
520
// repeat since the same block may merge again
521
while (try_merge(block)) ;
526
#undef DO_DELAYED_VERIFICATION
529
void Optimizer::eliminate_blocks() {
530
// merge blocks if possible
531
BlockMerger bm(ir());
535
class NullCheckEliminator;
536
class NullCheckVisitor: public InstructionVisitor {
538
NullCheckEliminator* _nce;
539
NullCheckEliminator* nce() { return _nce; }
542
NullCheckVisitor() {}
544
void set_eliminator(NullCheckEliminator* nce) { _nce = nce; }
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);
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);
594
void do_Assert (Assert* x);
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
602
class NullCheckEliminator: public ValueVisitor {
606
ValueSet* _visitable_instructions; // Visit each instruction only once per basic block
607
BlockList* _work_list; // Basic blocks to visit
609
bool visitable(Value x) {
610
assert(_visitable_instructions != nullptr, "check");
611
return _visitable_instructions->contains(x);
613
void mark_visited(Value x) {
614
assert(_visitable_instructions != nullptr, "check");
615
_visitable_instructions->remove(x);
617
void mark_visitable(Value x) {
618
assert(_visitable_instructions != nullptr, "check");
619
_visitable_instructions->put(x);
621
void clear_visitable_state() {
622
assert(_visitable_instructions != nullptr, "check");
623
_visitable_instructions->clear();
626
ValueSet* _set; // current state, propagated to subsequent BlockBegins
627
ValueSetList _block_states; // BlockBegin null-check states for all processed blocks
628
NullCheckVisitor _visitor;
629
NullCheck* _last_explicit_null_check;
631
bool set_contains(Value x) { assert(_set != nullptr, "check"); return _set->contains(x); }
632
void set_put (Value x) { assert(_set != nullptr, "check"); _set->put(x); }
633
void set_remove (Value x) { assert(_set != nullptr, "check"); _set->remove(x); }
635
BlockList* work_list() { return _work_list; }
638
void iterate_one(BlockBegin* block);
640
ValueSet* state() { return _set; }
641
void set_state_from (ValueSet* state) { _set->set_from(state); }
642
ValueSet* state_for (BlockBegin* block) { return _block_states.at(block->block_id()); }
643
void set_state_for (BlockBegin* block, ValueSet* stack) { _block_states.at_put(block->block_id(), stack); }
644
// Returns true if caused a change in the block's state.
645
bool merge_state_for(BlockBegin* block,
646
ValueSet* incoming_state);
650
NullCheckEliminator(Optimizer* opt)
652
, _work_list(new BlockList())
653
, _set(new ValueSet())
654
, _block_states(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), nullptr)
655
, _last_explicit_null_check(nullptr) {
656
_visitable_instructions = new ValueSet();
657
_visitor.set_eliminator(this);
658
CompileLog* log = _opt->ir()->compilation()->log();
660
log->set_context("optimize name='null_check_elimination'");
663
~NullCheckEliminator() {
664
CompileLog* log = _opt->ir()->compilation()->log();
666
log->clear_context(); // skip marker if nothing was printed
669
Optimizer* opt() { return _opt; }
670
IR* ir () { return opt()->ir(); }
673
void iterate(BlockBegin* root);
675
void visit(Value* f);
677
// In some situations (like NullCheck(x); getfield(x)) the debug
678
// information from the explicit NullCheck can be used to populate
679
// the getfield, even if the two instructions are in different
680
// scopes; this allows implicit null checks to be used but the
681
// correct exception information to be generated. We must clear the
682
// last-traversed NullCheck when we reach a potentially-exception-
683
// throwing instruction, as well as in some other cases.
684
void set_last_explicit_null_check(NullCheck* check) { _last_explicit_null_check = check; }
685
NullCheck* last_explicit_null_check() { return _last_explicit_null_check; }
686
Value last_explicit_null_check_obj() { return (_last_explicit_null_check
687
? _last_explicit_null_check->obj()
689
NullCheck* consume_last_explicit_null_check() {
690
_last_explicit_null_check->unpin(Instruction::PinExplicitNullCheck);
691
_last_explicit_null_check->set_can_trap(false);
692
return _last_explicit_null_check;
694
void clear_last_explicit_null_check() { _last_explicit_null_check = nullptr; }
696
// Handlers for relevant instructions
697
// (separated out from NullCheckVisitor for clarity)
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
void handle_Constant (Constant* x);
718
void handle_IfOp (IfOp* x);
723
// There may be other instructions which need to clear the last
724
// explicit null check. Anything across which we can not hoist the
725
// debug information for a NullCheck instruction must clear it. It
726
// might be safer to pattern match "NullCheck ; {AccessField,
727
// ArrayLength, LoadIndexed}" but it is more easily structured this way.
728
// Should test to see performance hit of clearing it for all handlers
729
// with empty bodies below. If it is negligible then we should leave
730
// that in for safety, otherwise should think more about it.
731
void NullCheckVisitor::do_Phi (Phi* x) { nce()->handle_Phi(x); }
732
void NullCheckVisitor::do_Local (Local* x) {}
733
void NullCheckVisitor::do_Constant (Constant* x) { nce()->handle_Constant(x); }
734
void NullCheckVisitor::do_LoadField (LoadField* x) { nce()->handle_AccessField(x); }
735
void NullCheckVisitor::do_StoreField (StoreField* x) { nce()->handle_AccessField(x); }
736
void NullCheckVisitor::do_ArrayLength (ArrayLength* x) { nce()->handle_ArrayLength(x); }
737
void NullCheckVisitor::do_LoadIndexed (LoadIndexed* x) { nce()->handle_LoadIndexed(x); }
738
void NullCheckVisitor::do_StoreIndexed (StoreIndexed* x) { nce()->handle_StoreIndexed(x); }
739
void NullCheckVisitor::do_NegateOp (NegateOp* x) {}
740
void NullCheckVisitor::do_ArithmeticOp (ArithmeticOp* x) { if (x->can_trap()) nce()->clear_last_explicit_null_check(); }
741
void NullCheckVisitor::do_ShiftOp (ShiftOp* x) {}
742
void NullCheckVisitor::do_LogicOp (LogicOp* x) {}
743
void NullCheckVisitor::do_CompareOp (CompareOp* x) {}
744
void NullCheckVisitor::do_IfOp (IfOp* x) { nce()->handle_IfOp(x); }
745
void NullCheckVisitor::do_Convert (Convert* x) {}
746
void NullCheckVisitor::do_NullCheck (NullCheck* x) { nce()->handle_NullCheck(x); }
747
void NullCheckVisitor::do_TypeCast (TypeCast* x) {}
748
void NullCheckVisitor::do_Invoke (Invoke* x) { nce()->handle_Invoke(x); }
749
void NullCheckVisitor::do_NewInstance (NewInstance* x) { nce()->handle_NewInstance(x); }
750
void NullCheckVisitor::do_NewTypeArray (NewTypeArray* x) { nce()->handle_NewArray(x); }
751
void NullCheckVisitor::do_NewObjectArray (NewObjectArray* x) { nce()->handle_NewArray(x); }
752
void NullCheckVisitor::do_NewMultiArray (NewMultiArray* x) { nce()->handle_NewArray(x); }
753
void NullCheckVisitor::do_CheckCast (CheckCast* x) { nce()->clear_last_explicit_null_check(); }
754
void NullCheckVisitor::do_InstanceOf (InstanceOf* x) {}
755
void NullCheckVisitor::do_MonitorEnter (MonitorEnter* x) { nce()->handle_AccessMonitor(x); }
756
void NullCheckVisitor::do_MonitorExit (MonitorExit* x) { nce()->handle_AccessMonitor(x); }
757
void NullCheckVisitor::do_Intrinsic (Intrinsic* x) { nce()->handle_Intrinsic(x); }
758
void NullCheckVisitor::do_BlockBegin (BlockBegin* x) {}
759
void NullCheckVisitor::do_Goto (Goto* x) {}
760
void NullCheckVisitor::do_If (If* x) {}
761
void NullCheckVisitor::do_TableSwitch (TableSwitch* x) {}
762
void NullCheckVisitor::do_LookupSwitch (LookupSwitch* x) {}
763
void NullCheckVisitor::do_Return (Return* x) {}
764
void NullCheckVisitor::do_Throw (Throw* x) { nce()->clear_last_explicit_null_check(); }
765
void NullCheckVisitor::do_Base (Base* x) {}
766
void NullCheckVisitor::do_OsrEntry (OsrEntry* x) {}
767
void NullCheckVisitor::do_ExceptionObject(ExceptionObject* x) { nce()->handle_ExceptionObject(x); }
768
void NullCheckVisitor::do_RoundFP (RoundFP* x) {}
769
void NullCheckVisitor::do_UnsafeGet (UnsafeGet* x) {}
770
void NullCheckVisitor::do_UnsafePut (UnsafePut* x) {}
771
void NullCheckVisitor::do_UnsafeGetAndSet(UnsafeGetAndSet* x) {}
772
void NullCheckVisitor::do_ProfileCall (ProfileCall* x) { nce()->clear_last_explicit_null_check();
773
nce()->handle_ProfileCall(x); }
774
void NullCheckVisitor::do_ProfileReturnType (ProfileReturnType* x) { nce()->handle_ProfileReturnType(x); }
775
void NullCheckVisitor::do_ProfileInvoke (ProfileInvoke* x) {}
776
void NullCheckVisitor::do_RuntimeCall (RuntimeCall* x) {}
777
void NullCheckVisitor::do_MemBar (MemBar* x) {}
778
void NullCheckVisitor::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
780
void NullCheckVisitor::do_Assert (Assert* x) {}
783
void NullCheckEliminator::visit(Value* p) {
784
assert(*p != nullptr, "should not find null instructions");
787
(*p)->visit(&_visitor);
791
bool NullCheckEliminator::merge_state_for(BlockBegin* block, ValueSet* incoming_state) {
792
ValueSet* state = state_for(block);
793
if (state == nullptr) {
794
state = incoming_state->copy();
795
set_state_for(block, state);
798
bool changed = state->set_intersect(incoming_state);
799
if (PrintNullCheckElimination && changed) {
800
tty->print_cr("Block %d's null check state changed", block->block_id());
807
void NullCheckEliminator::iterate_all() {
808
while (work_list()->length() > 0) {
809
iterate_one(work_list()->pop());
814
void NullCheckEliminator::iterate_one(BlockBegin* block) {
815
clear_visitable_state();
816
// clear out an old explicit null checks
817
set_last_explicit_null_check(nullptr);
819
if (PrintNullCheckElimination) {
820
tty->print_cr(" ...iterating block %d in null check elimination for %s::%s%s",
822
ir()->method()->holder()->name()->as_utf8(),
823
ir()->method()->name()->as_utf8(),
824
ir()->method()->signature()->as_symbol()->as_utf8());
827
// Create new state if none present (only happens at root)
828
if (state_for(block) == nullptr) {
829
ValueSet* tmp_state = new ValueSet();
830
set_state_for(block, tmp_state);
831
// Initial state is that local 0 (receiver) is non-null for
832
// non-static methods
833
ValueStack* stack = block->state();
834
IRScope* scope = stack->scope();
835
ciMethod* method = scope->method();
836
if (!method->is_static()) {
837
Local* local0 = stack->local_at(0)->as_Local();
838
assert(local0 != nullptr, "must be");
839
assert(local0->type() == objectType, "invalid type of receiver");
841
if (local0 != nullptr) {
842
// Local 0 is used in this scope
843
tmp_state->put(local0);
844
if (PrintNullCheckElimination) {
845
tty->print_cr("Local 0 (value %d) proven non-null upon entry", local0->id());
851
// Must copy block's state to avoid mutating it during iteration
852
// through the block -- otherwise "not-null" states can accidentally
853
// propagate "up" through the block during processing of backward
854
// branches and algorithm is incorrect (and does not converge)
855
set_state_from(state_for(block));
857
// allow visiting of Phis belonging to this block
858
for_each_phi_fun(block, phi,
862
BlockEnd* e = block->end();
863
assert(e != nullptr, "incomplete graph");
866
// Propagate the state before this block into the exception
867
// handlers. They aren't true successors since we aren't guaranteed
868
// to execute the whole block before executing them. Also putting
869
// them on first seems to help reduce the amount of iteration to
870
// reach a fixed point.
871
for (i = 0; i < block->number_of_exception_handlers(); i++) {
872
BlockBegin* next = block->exception_handler_at(i);
873
if (merge_state_for(next, state())) {
874
if (!work_list()->contains(next)) {
875
work_list()->push(next);
880
// Iterate through block, updating state.
881
for (Instruction* instr = block; instr != nullptr; instr = instr->next()) {
882
// Mark instructions in this block as visitable as they are seen
883
// in the instruction list. This keeps the iteration from
884
// visiting instructions which are references in other blocks or
885
// visiting instructions more than once.
886
mark_visitable(instr);
887
if (instr->is_pinned() || instr->can_trap() || (instr->as_NullCheck() != nullptr)
888
|| (instr->as_Constant() != nullptr && instr->as_Constant()->type()->is_object())
889
|| (instr->as_IfOp() != nullptr)) {
891
instr->input_values_do(this);
892
instr->visit(&_visitor);
896
// Propagate state to successors if necessary
897
for (i = 0; i < e->number_of_sux(); i++) {
898
BlockBegin* next = e->sux_at(i);
899
if (merge_state_for(next, state())) {
900
if (!work_list()->contains(next)) {
901
work_list()->push(next);
908
void NullCheckEliminator::iterate(BlockBegin* block) {
909
work_list()->push(block);
913
void NullCheckEliminator::handle_AccessField(AccessField* x) {
914
if (x->is_static()) {
915
if (x->as_LoadField() != nullptr) {
916
// If the field is a non-null static final object field (as is
917
// often the case for sun.misc.Unsafe), put this LoadField into
919
ciField* field = x->field();
920
if (field->is_constant()) {
921
ciConstant field_val = field->constant_value();
922
BasicType field_type = field_val.basic_type();
923
if (is_reference_type(field_type)) {
924
ciObject* obj_val = field_val.as_object();
925
if (!obj_val->is_null_object()) {
926
if (PrintNullCheckElimination) {
927
tty->print_cr("AccessField %d proven non-null by static final non-null oop check",
936
clear_last_explicit_null_check();
940
Value obj = x->obj();
941
if (set_contains(obj)) {
942
// Value is non-null => update AccessField
943
if (last_explicit_null_check_obj() == obj && !x->needs_patching()) {
944
x->set_explicit_null_check(consume_last_explicit_null_check());
945
x->set_needs_null_check(true);
946
if (PrintNullCheckElimination) {
947
tty->print_cr("Folded NullCheck %d into AccessField %d's null check for value %d",
948
x->explicit_null_check()->id(), x->id(), obj->id());
951
x->set_explicit_null_check(nullptr);
952
x->set_needs_null_check(false);
953
if (PrintNullCheckElimination) {
954
tty->print_cr("Eliminated AccessField %d's null check for value %d", x->id(), obj->id());
959
if (PrintNullCheckElimination) {
960
tty->print_cr("AccessField %d of value %d proves value to be non-null", x->id(), obj->id());
962
// Ensure previous passes do not cause wrong state
963
x->set_needs_null_check(true);
964
x->set_explicit_null_check(nullptr);
966
clear_last_explicit_null_check();
970
void NullCheckEliminator::handle_ArrayLength(ArrayLength* x) {
971
Value array = x->array();
972
if (set_contains(array)) {
973
// Value is non-null => update AccessArray
974
if (last_explicit_null_check_obj() == array) {
975
x->set_explicit_null_check(consume_last_explicit_null_check());
976
x->set_needs_null_check(true);
977
if (PrintNullCheckElimination) {
978
tty->print_cr("Folded NullCheck %d into ArrayLength %d's null check for value %d",
979
x->explicit_null_check()->id(), x->id(), array->id());
982
x->set_explicit_null_check(nullptr);
983
x->set_needs_null_check(false);
984
if (PrintNullCheckElimination) {
985
tty->print_cr("Eliminated ArrayLength %d's null check for value %d", x->id(), array->id());
990
if (PrintNullCheckElimination) {
991
tty->print_cr("ArrayLength %d of value %d proves value to be non-null", x->id(), array->id());
993
// Ensure previous passes do not cause wrong state
994
x->set_needs_null_check(true);
995
x->set_explicit_null_check(nullptr);
997
clear_last_explicit_null_check();
1001
void NullCheckEliminator::handle_LoadIndexed(LoadIndexed* x) {
1002
Value array = x->array();
1003
if (set_contains(array)) {
1004
// Value is non-null => update AccessArray
1005
if (last_explicit_null_check_obj() == array) {
1006
x->set_explicit_null_check(consume_last_explicit_null_check());
1007
x->set_needs_null_check(true);
1008
if (PrintNullCheckElimination) {
1009
tty->print_cr("Folded NullCheck %d into LoadIndexed %d's null check for value %d",
1010
x->explicit_null_check()->id(), x->id(), array->id());
1013
x->set_explicit_null_check(nullptr);
1014
x->set_needs_null_check(false);
1015
if (PrintNullCheckElimination) {
1016
tty->print_cr("Eliminated LoadIndexed %d's null check for value %d", x->id(), array->id());
1021
if (PrintNullCheckElimination) {
1022
tty->print_cr("LoadIndexed %d of value %d proves value to be non-null", x->id(), array->id());
1024
// Ensure previous passes do not cause wrong state
1025
x->set_needs_null_check(true);
1026
x->set_explicit_null_check(nullptr);
1028
clear_last_explicit_null_check();
1032
void NullCheckEliminator::handle_StoreIndexed(StoreIndexed* x) {
1033
Value array = x->array();
1034
if (set_contains(array)) {
1035
// Value is non-null => update AccessArray
1036
if (PrintNullCheckElimination) {
1037
tty->print_cr("Eliminated StoreIndexed %d's null check for value %d", x->id(), array->id());
1039
x->set_needs_null_check(false);
1042
if (PrintNullCheckElimination) {
1043
tty->print_cr("StoreIndexed %d of value %d proves value to be non-null", x->id(), array->id());
1045
// Ensure previous passes do not cause wrong state
1046
x->set_needs_null_check(true);
1048
clear_last_explicit_null_check();
1052
void NullCheckEliminator::handle_NullCheck(NullCheck* x) {
1053
Value obj = x->obj();
1054
if (set_contains(obj)) {
1055
// Already proven to be non-null => this NullCheck is useless
1056
if (PrintNullCheckElimination) {
1057
tty->print_cr("Eliminated NullCheck %d for value %d", x->id(), obj->id());
1059
// Don't unpin since that may shrink obj's live range and make it unavailable for debug info.
1060
// The code generator won't emit LIR for a NullCheck that cannot trap.
1061
x->set_can_trap(false);
1063
// May be null => add to map and set last explicit NullCheck
1064
x->set_can_trap(true);
1065
// make sure it's pinned if it can trap
1066
x->pin(Instruction::PinExplicitNullCheck);
1068
set_last_explicit_null_check(x);
1069
if (PrintNullCheckElimination) {
1070
tty->print_cr("NullCheck %d of value %d proves value to be non-null", x->id(), obj->id());
1076
void NullCheckEliminator::handle_Invoke(Invoke* x) {
1077
if (!x->has_receiver()) {
1079
clear_last_explicit_null_check();
1083
Value recv = x->receiver();
1084
if (!set_contains(recv)) {
1086
if (PrintNullCheckElimination) {
1087
tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
1090
clear_last_explicit_null_check();
1094
void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
1096
if (PrintNullCheckElimination) {
1097
tty->print_cr("NewInstance %d is non-null", x->id());
1102
void NullCheckEliminator::handle_NewArray(NewArray* x) {
1104
if (PrintNullCheckElimination) {
1105
tty->print_cr("NewArray %d is non-null", x->id());
1110
void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1112
if (PrintNullCheckElimination) {
1113
tty->print_cr("ExceptionObject %d is non-null", x->id());
1118
void NullCheckEliminator::handle_AccessMonitor(AccessMonitor* x) {
1119
Value obj = x->obj();
1120
if (set_contains(obj)) {
1121
// Value is non-null => update AccessMonitor
1122
if (PrintNullCheckElimination) {
1123
tty->print_cr("Eliminated AccessMonitor %d's null check for value %d", x->id(), obj->id());
1125
x->set_needs_null_check(false);
1128
if (PrintNullCheckElimination) {
1129
tty->print_cr("AccessMonitor %d of value %d proves value to be non-null", x->id(), obj->id());
1131
// Ensure previous passes do not cause wrong state
1132
x->set_needs_null_check(true);
1134
clear_last_explicit_null_check();
1138
void NullCheckEliminator::handle_Intrinsic(Intrinsic* x) {
1139
if (!x->has_receiver()) {
1140
if (x->id() == vmIntrinsics::_arraycopy) {
1141
for (int i = 0; i < x->number_of_arguments(); i++) {
1142
x->set_arg_needs_null_check(i, !set_contains(x->argument_at(i)));
1147
clear_last_explicit_null_check();
1151
Value recv = x->receiver();
1152
if (set_contains(recv)) {
1153
// Value is non-null => update Intrinsic
1154
if (PrintNullCheckElimination) {
1155
tty->print_cr("Eliminated Intrinsic %d's null check for value %d", vmIntrinsics::as_int(x->id()), recv->id());
1157
x->set_needs_null_check(false);
1160
if (PrintNullCheckElimination) {
1161
tty->print_cr("Intrinsic %d of value %d proves value to be non-null", vmIntrinsics::as_int(x->id()), recv->id());
1163
// Ensure previous passes do not cause wrong state
1164
x->set_needs_null_check(true);
1166
clear_last_explicit_null_check();
1170
void NullCheckEliminator::handle_Phi(Phi* x) {
1172
bool all_non_null = true;
1173
if (x->is_illegal()) {
1174
all_non_null = false;
1176
for (i = 0; i < x->operand_count(); i++) {
1177
Value input = x->operand_at(i);
1178
if (!set_contains(input)) {
1179
all_non_null = false;
1185
// Value is non-null => update Phi
1186
if (PrintNullCheckElimination) {
1187
tty->print_cr("Eliminated Phi %d's null check for phifun because all inputs are non-null", x->id());
1189
x->set_needs_null_check(false);
1190
} else if (set_contains(x)) {
1195
void NullCheckEliminator::handle_ProfileCall(ProfileCall* x) {
1196
for (int i = 0; i < x->nb_profiled_args(); i++) {
1197
x->set_arg_needs_null_check(i, !set_contains(x->profiled_arg_at(i)));
1201
void NullCheckEliminator::handle_ProfileReturnType(ProfileReturnType* x) {
1202
x->set_needs_null_check(!set_contains(x->ret()));
1205
void NullCheckEliminator::handle_Constant(Constant *x) {
1206
ObjectType* ot = x->type()->as_ObjectType();
1207
if (ot != nullptr && ot->is_loaded()) {
1208
ObjectConstant* oc = ot->as_ObjectConstant();
1209
if (oc == nullptr || !oc->value()->is_null_object()) {
1211
if (PrintNullCheckElimination) {
1212
tty->print_cr("Constant %d is non-null", x->id());
1218
void NullCheckEliminator::handle_IfOp(IfOp *x) {
1219
if (x->type()->is_object() && set_contains(x->tval()) && set_contains(x->fval())) {
1221
if (PrintNullCheckElimination) {
1222
tty->print_cr("IfOp %d is non-null", x->id());
1227
void Optimizer::eliminate_null_checks() {
1230
NullCheckEliminator nce(this);
1232
if (PrintNullCheckElimination) {
1233
tty->print_cr("Starting null check elimination for method %s::%s%s",
1234
ir()->method()->holder()->name()->as_utf8(),
1235
ir()->method()->name()->as_utf8(),
1236
ir()->method()->signature()->as_symbol()->as_utf8());
1240
nce.iterate(ir()->start());
1242
// walk over the graph looking for exception
1243
// handlers and iterate over them as well
1244
int nblocks = BlockBegin::number_of_blocks();
1245
BlockList blocks(nblocks);
1246
boolArray visited_block(nblocks, nblocks, false);
1248
blocks.push(ir()->start());
1249
visited_block.at_put(ir()->start()->block_id(), true);
1250
for (int i = 0; i < blocks.length(); i++) {
1251
BlockBegin* b = blocks.at(i);
1252
// exception handlers need to be treated as additional roots
1253
for (int e = b->number_of_exception_handlers(); e-- > 0; ) {
1254
BlockBegin* excp = b->exception_handler_at(e);
1255
int id = excp->block_id();
1256
if (!visited_block.at(id)) {
1258
visited_block.at_put(id, true);
1262
// traverse successors
1263
BlockEnd *end = b->end();
1264
for (int s = end->number_of_sux(); s-- > 0; ) {
1265
BlockBegin* next = end->sux_at(s);
1266
int id = next->block_id();
1267
if (!visited_block.at(id)) {
1269
visited_block.at_put(id, true);
1275
if (PrintNullCheckElimination) {
1276
tty->print_cr("Done with null check elimination for method %s::%s%s",
1277
ir()->method()->holder()->name()->as_utf8(),
1278
ir()->method()->name()->as_utf8(),
1279
ir()->method()->signature()->as_symbol()->as_utf8());