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