jdk

1
/*
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.
4
 *
5
 * This code is free software; you can redistribute it and/or modify it
6
 * under the terms of the GNU General Public License version 2 only, as
7
 * published by the Free Software Foundation.
8
 *
9
 * This code is distributed in the hope that it will be useful, but WITHOUT
10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12
 * version 2 for more details (a copy is included in the LICENSE file that
13
 * accompanied this code).
14
 *
15
 * You should have received a copy of the GNU General Public License version
16
 * 2 along with this work; if not, write to the Free Software Foundation,
17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18
 *
19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
 * or visit www.oracle.com if you need additional information or have any
21
 * questions.
22
 *
23
 */
24

25
#include "precompiled.hpp"
26
#include "c1/c1_Canonicalizer.hpp"
27
#include "c1/c1_Optimizer.hpp"
28
#include "c1/c1_ValueMap.hpp"
29
#include "c1/c1_ValueSet.hpp"
30
#include "c1/c1_ValueStack.hpp"
31
#include "memory/resourceArea.hpp"
32
#include "utilities/bitMap.inline.hpp"
33
#include "compiler/compileLog.hpp"
34

35
typedef GrowableArray<ValueSet*> ValueSetList;
36

37
Optimizer::Optimizer(IR* ir) {
38
  assert(ir->is_valid(), "IR must be valid");
39
  _ir = ir;
40
}
41

42
class CE_Eliminator: public BlockClosure {
43
 private:
44
  IR* _hir;
45
  int _cee_count;                                // the number of CEs successfully eliminated
46
  int _ifop_count;                               // the number of IfOps successfully simplified
47
  int _has_substitution;
48

49
 public:
50
  CE_Eliminator(IR* hir) : _hir(hir), _cee_count(0), _ifop_count(0) {
51
    _has_substitution = false;
52
    _hir->iterate_preorder(this);
53
    if (_has_substitution) {
54
      // substituted some ifops/phis, so resolve the substitution
55
      SubstitutionResolver sr(_hir);
56
    }
57

58
    CompileLog* log = _hir->compilation()->log();
59
    if (log != nullptr)
60
      log->set_context("optimize name='cee'");
61
  }
62

63
  ~CE_Eliminator() {
64
    CompileLog* log = _hir->compilation()->log();
65
    if (log != nullptr)
66
      log->clear_context(); // skip marker if nothing was printed
67
  }
68

69
  int cee_count() const                          { return _cee_count; }
70
  int ifop_count() const                         { return _ifop_count; }
71

72
  void adjust_exception_edges(BlockBegin* block, BlockBegin* sux) {
73
    int e = sux->number_of_exception_handlers();
74
    for (int i = 0; i < e; i++) {
75
      BlockBegin* xhandler = sux->exception_handler_at(i);
76
      block->add_exception_handler(xhandler);
77

78
      assert(xhandler->is_predecessor(sux), "missing predecessor");
79
      if (sux->number_of_preds() == 0) {
80
        // sux is disconnected from graph so disconnect from exception handlers
81
        xhandler->remove_predecessor(sux);
82
      }
83
      if (!xhandler->is_predecessor(block)) {
84
        xhandler->add_predecessor(block);
85
      }
86
    }
87
  }
88

89
  virtual void block_do(BlockBegin* block);
90

91
 private:
92
  Value make_ifop(Value x, Instruction::Condition cond, Value y, Value tval, Value fval);
93
};
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_ == nullptr) 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

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()) {
117
    t_const = t_cur;
118
    t_cur = t_cur->next();
119
  }
120
  if (f_cur->as_Constant() != nullptr && !f_cur->can_trap()) {
121
    f_const = f_cur;
122
    f_cur = f_cur->next();
123
  }
124

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;
130

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;
134

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");
143
    }
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");
148
    }
149
  }
150

151
  if (sux_state->stack_size() <= if_state->stack_size()) return;
152

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;
158

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());
162

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;
166

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;
172
                   );
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; );
176

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())) {
180
    return;
181
  }
182

183
#ifdef ASSERT
184
#define DO_DELAYED_VERIFICATION
185
  /*
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.
190
   */
191
#endif // ASSERT
192

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
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 != 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);
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
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);
246
  }
247
  adjust_exception_edges(block, t_block);
248
  if (f_block->number_of_preds() == 0) {
249
    BlockBegin::disconnect_edge(f_block, sux);
250
  }
251
  adjust_exception_edges(block, f_block);
252

253
  // update block end
254
  block->set_end(goto_);
255

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 != 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();
297

298
      if (x_tval_const != nullptr && x_fval_const != nullptr) {
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 != 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) {
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
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);
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
}
350

351
class BlockMerger: public BlockClosure {
352
 private:
353
  IR* _hir;
354
  int _merge_count;              // the number of block pairs successfully merged
355

356
 public:
357
  BlockMerger(IR* hir)
358
  : _hir(hir)
359
  , _merge_count(0)
360
  {
361
    _hir->iterate_preorder(this);
362
    CompileLog* log = _hir->compilation()->log();
363
    if (log != nullptr)
364
      log->set_context("optimize name='eliminate_blocks'");
365
  }
366

367
  ~BlockMerger() {
368
    CompileLog* log = _hir->compilation()->log();
369
    if (log != nullptr)
370
      log->clear_context(); // skip marker if nothing was printed
371
  }
372

373
  bool try_merge(BlockBegin* block) {
374
    BlockEnd* end = block->end();
375
    if (end->as_Goto() == nullptr) return false;
376

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
389

390
#ifdef ASSERT
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();
395

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");
399

400
    int index;
401
    Value sux_value;
402
    for_each_stack_value(sux_state, index, sux_value) {
403
      assert(sux_value == end_state->stack_at(index), "stack not equal");
404
    }
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");
409
      }
410
    assert(sux_state->caller_state() == end_state->caller_state(), "caller not equal");
411
#endif
412

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
418

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();
425

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());
432

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);
438

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);
445
      }
446
    }
447

448
    // debugging output
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 != nullptr && prev->next() != if_) {
479
            prev = prev->next();
480
          }
481

482
          if (prev != nullptr) {
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
    }
515

516
    return true;
517
  }
518

519
  virtual void block_do(BlockBegin* block) {
520
    // repeat since the same block may merge again
521
    while (try_merge(block)) ;
522
  }
523
};
524

525
#ifdef ASSERT
526
#undef DO_DELAYED_VERIFICATION
527
#endif // ASSERT
528

529
void Optimizer::eliminate_blocks() {
530
  // merge blocks if possible
531
  BlockMerger bm(ir());
532
}
533

534

535
class NullCheckEliminator;
536
class NullCheckVisitor: public InstructionVisitor {
537
private:
538
  NullCheckEliminator* _nce;
539
  NullCheckEliminator* nce() { return _nce; }
540

541
public:
542
  NullCheckVisitor() {}
543

544
  void set_eliminator(NullCheckEliminator* nce) { _nce = nce; }
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

609
  bool visitable(Value x) {
610
    assert(_visitable_instructions != nullptr, "check");
611
    return _visitable_instructions->contains(x);
612
  }
613
  void mark_visited(Value x) {
614
    assert(_visitable_instructions != nullptr, "check");
615
    _visitable_instructions->remove(x);
616
  }
617
  void mark_visitable(Value x) {
618
    assert(_visitable_instructions != nullptr, "check");
619
    _visitable_instructions->put(x);
620
  }
621
  void clear_visitable_state() {
622
    assert(_visitable_instructions != nullptr, "check");
623
    _visitable_instructions->clear();
624
  }
625

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;
630

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); }
634

635
  BlockList* work_list()                          { return _work_list; }
636

637
  void iterate_all();
638
  void iterate_one(BlockBegin* block);
639

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);
647

648
 public:
649
  // constructor
650
  NullCheckEliminator(Optimizer* opt)
651
    : _opt(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();
659
    if (log != nullptr)
660
      log->set_context("optimize name='null_check_elimination'");
661
  }
662

663
  ~NullCheckEliminator() {
664
    CompileLog* log = _opt->ir()->compilation()->log();
665
    if (log != nullptr)
666
      log->clear_context(); // skip marker if nothing was printed
667
  }
668

669
  Optimizer*  opt()                               { return _opt; }
670
  IR*         ir ()                               { return opt()->ir(); }
671

672
  // Process a graph
673
  void iterate(BlockBegin* root);
674

675
  void visit(Value* f);
676

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()
688
                                                                         : nullptr); }
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;
693
  }
694
  void        clear_last_explicit_null_check()               { _last_explicit_null_check = nullptr; }
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
  void handle_Constant        (Constant* x);
718
  void handle_IfOp            (IfOp* x);
719
};
720

721

722
// NEEDS_CLEANUP
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) {}
779
#ifdef ASSERT
780
void NullCheckVisitor::do_Assert         (Assert*          x) {}
781
#endif
782

783
void NullCheckEliminator::visit(Value* p) {
784
  assert(*p != nullptr, "should not find null instructions");
785
  if (visitable(*p)) {
786
    mark_visited(*p);
787
    (*p)->visit(&_visitor);
788
  }
789
}
790

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);
796
    return true;
797
  } else {
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());
801
    }
802
    return changed;
803
  }
804
}
805

806

807
void NullCheckEliminator::iterate_all() {
808
  while (work_list()->length() > 0) {
809
    iterate_one(work_list()->pop());
810
  }
811
}
812

813

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);
818

819
  if (PrintNullCheckElimination) {
820
    tty->print_cr(" ...iterating block %d in null check elimination for %s::%s%s",
821
                  block->block_id(),
822
                  ir()->method()->holder()->name()->as_utf8(),
823
                  ir()->method()->name()->as_utf8(),
824
                  ir()->method()->signature()->as_symbol()->as_utf8());
825
  }
826

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");
840

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());
846
        }
847
      }
848
    }
849
  }
850

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));
856

857
  // allow visiting of Phis belonging to this block
858
  for_each_phi_fun(block, phi,
859
                   mark_visitable(phi);
860
                   );
861

862
  BlockEnd* e = block->end();
863
  assert(e != nullptr, "incomplete graph");
864
  int i;
865

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);
876
      }
877
    }
878
  }
879

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)) {
890
      mark_visited(instr);
891
      instr->input_values_do(this);
892
      instr->visit(&_visitor);
893
    }
894
  }
895

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);
902
      }
903
    }
904
  }
905
}
906

907

908
void NullCheckEliminator::iterate(BlockBegin* block) {
909
  work_list()->push(block);
910
  iterate_all();
911
}
912

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
918
      // the non-null map
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",
928
                            x->id());
929
            }
930
            set_put(x);
931
          }
932
        }
933
      }
934
    }
935
    // Be conservative
936
    clear_last_explicit_null_check();
937
    return;
938
  }
939

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());
949
      }
950
    } else {
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());
955
      }
956
    }
957
  } else {
958
    set_put(obj);
959
    if (PrintNullCheckElimination) {
960
      tty->print_cr("AccessField %d of value %d proves value to be non-null", x->id(), obj->id());
961
    }
962
    // Ensure previous passes do not cause wrong state
963
    x->set_needs_null_check(true);
964
    x->set_explicit_null_check(nullptr);
965
  }
966
  clear_last_explicit_null_check();
967
}
968

969

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());
980
      }
981
    } else {
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());
986
      }
987
    }
988
  } else {
989
    set_put(array);
990
    if (PrintNullCheckElimination) {
991
      tty->print_cr("ArrayLength %d of value %d proves value to be non-null", x->id(), array->id());
992
    }
993
    // Ensure previous passes do not cause wrong state
994
    x->set_needs_null_check(true);
995
    x->set_explicit_null_check(nullptr);
996
  }
997
  clear_last_explicit_null_check();
998
}
999

1000

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());
1011
      }
1012
    } else {
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());
1017
      }
1018
    }
1019
  } else {
1020
    set_put(array);
1021
    if (PrintNullCheckElimination) {
1022
      tty->print_cr("LoadIndexed %d of value %d proves value to be non-null", x->id(), array->id());
1023
    }
1024
    // Ensure previous passes do not cause wrong state
1025
    x->set_needs_null_check(true);
1026
    x->set_explicit_null_check(nullptr);
1027
  }
1028
  clear_last_explicit_null_check();
1029
}
1030

1031

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());
1038
    }
1039
    x->set_needs_null_check(false);
1040
  } else {
1041
    set_put(array);
1042
    if (PrintNullCheckElimination) {
1043
      tty->print_cr("StoreIndexed %d of value %d proves value to be non-null", x->id(), array->id());
1044
    }
1045
    // Ensure previous passes do not cause wrong state
1046
    x->set_needs_null_check(true);
1047
  }
1048
  clear_last_explicit_null_check();
1049
}
1050

1051

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());
1058
    }
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);
1062
  } else {
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);
1067
    set_put(obj);
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());
1071
    }
1072
  }
1073
}
1074

1075

1076
void NullCheckEliminator::handle_Invoke(Invoke* x) {
1077
  if (!x->has_receiver()) {
1078
    // Be conservative
1079
    clear_last_explicit_null_check();
1080
    return;
1081
  }
1082

1083
  Value recv = x->receiver();
1084
  if (!set_contains(recv)) {
1085
    set_put(recv);
1086
    if (PrintNullCheckElimination) {
1087
      tty->print_cr("Invoke %d of value %d proves value to be non-null", x->id(), recv->id());
1088
    }
1089
  }
1090
  clear_last_explicit_null_check();
1091
}
1092

1093

1094
void NullCheckEliminator::handle_NewInstance(NewInstance* x) {
1095
  set_put(x);
1096
  if (PrintNullCheckElimination) {
1097
    tty->print_cr("NewInstance %d is non-null", x->id());
1098
  }
1099
}
1100

1101

1102
void NullCheckEliminator::handle_NewArray(NewArray* x) {
1103
  set_put(x);
1104
  if (PrintNullCheckElimination) {
1105
    tty->print_cr("NewArray %d is non-null", x->id());
1106
  }
1107
}
1108

1109

1110
void NullCheckEliminator::handle_ExceptionObject(ExceptionObject* x) {
1111
  set_put(x);
1112
  if (PrintNullCheckElimination) {
1113
    tty->print_cr("ExceptionObject %d is non-null", x->id());
1114
  }
1115
}
1116

1117

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());
1124
    }
1125
    x->set_needs_null_check(false);
1126
  } else {
1127
    set_put(obj);
1128
    if (PrintNullCheckElimination) {
1129
      tty->print_cr("AccessMonitor %d of value %d proves value to be non-null", x->id(), obj->id());
1130
    }
1131
    // Ensure previous passes do not cause wrong state
1132
    x->set_needs_null_check(true);
1133
  }
1134
  clear_last_explicit_null_check();
1135
}
1136

1137

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)));
1143
      }
1144
    }
1145

1146
    // Be conservative
1147
    clear_last_explicit_null_check();
1148
    return;
1149
  }
1150

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());
1156
    }
1157
    x->set_needs_null_check(false);
1158
  } else {
1159
    set_put(recv);
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());
1162
    }
1163
    // Ensure previous passes do not cause wrong state
1164
    x->set_needs_null_check(true);
1165
  }
1166
  clear_last_explicit_null_check();
1167
}
1168

1169

1170
void NullCheckEliminator::handle_Phi(Phi* x) {
1171
  int i;
1172
  bool all_non_null = true;
1173
  if (x->is_illegal()) {
1174
    all_non_null = false;
1175
  } else {
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;
1180
      }
1181
    }
1182
  }
1183

1184
  if (all_non_null) {
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());
1188
    }
1189
    x->set_needs_null_check(false);
1190
  } else if (set_contains(x)) {
1191
    set_remove(x);
1192
  }
1193
}
1194

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)));
1198
  }
1199
}
1200

1201
void NullCheckEliminator::handle_ProfileReturnType(ProfileReturnType* x) {
1202
  x->set_needs_null_check(!set_contains(x->ret()));
1203
}
1204

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()) {
1210
      set_put(x);
1211
      if (PrintNullCheckElimination) {
1212
        tty->print_cr("Constant %d is non-null", x->id());
1213
      }
1214
    }
1215
  }
1216
}
1217

1218
void NullCheckEliminator::handle_IfOp(IfOp *x) {
1219
  if (x->type()->is_object() && set_contains(x->tval()) && set_contains(x->fval())) {
1220
    set_put(x);
1221
    if (PrintNullCheckElimination) {
1222
      tty->print_cr("IfOp %d is non-null", x->id());
1223
    }
1224
  }
1225
}
1226

1227
void Optimizer::eliminate_null_checks() {
1228
  ResourceMark rm;
1229

1230
  NullCheckEliminator nce(this);
1231

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());
1237
  }
1238

1239
  // Apply to graph
1240
  nce.iterate(ir()->start());
1241

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);
1247

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)) {
1257
        blocks.push(excp);
1258
        visited_block.at_put(id, true);
1259
        nce.iterate(excp);
1260
      }
1261
    }
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)) {
1268
        blocks.push(next);
1269
        visited_block.at_put(id, true);
1270
      }
1271
    }
1272
  }
1273

1274

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());
1280
  }
1281
}
1282