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_Compilation.hpp"
27
#include "c1/c1_FrameMap.hpp"
28
#include "c1/c1_GraphBuilder.hpp"
29
#include "c1/c1_IR.hpp"
30
#include "c1/c1_InstructionPrinter.hpp"
31
#include "c1/c1_Optimizer.hpp"
32
#include "compiler/oopMap.hpp"
33
#include "memory/resourceArea.hpp"
34
#include "utilities/bitMap.inline.hpp"
35

36

37
// Implementation of XHandlers
38
//
39
// Note: This code could eventually go away if we are
40
//       just using the ciExceptionHandlerStream.
41

42
XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) {
43
  ciExceptionHandlerStream s(method);
44
  while (!s.is_done()) {
45
    _list.append(new XHandler(s.handler()));
46
    s.next();
47
  }
48
  assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent");
49
}
50

51
// deep copy of all XHandler contained in list
52
XHandlers::XHandlers(XHandlers* other) :
53
  _list(other->length())
54
{
55
  for (int i = 0; i < other->length(); i++) {
56
    _list.append(new XHandler(other->handler_at(i)));
57
  }
58
}
59

60
// Returns whether a particular exception type can be caught.  Also
61
// returns true if klass is unloaded or any exception handler
62
// classes are unloaded.  type_is_exact indicates whether the throw
63
// is known to be exactly that class or it might throw a subtype.
64
bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const {
65
  // the type is unknown so be conservative
66
  if (!klass->is_loaded()) {
67
    return true;
68
  }
69

70
  for (int i = 0; i < length(); i++) {
71
    XHandler* handler = handler_at(i);
72
    if (handler->is_catch_all()) {
73
      // catch of ANY
74
      return true;
75
    }
76
    ciInstanceKlass* handler_klass = handler->catch_klass();
77
    // if it's unknown it might be catchable
78
    if (!handler_klass->is_loaded()) {
79
      return true;
80
    }
81
    // if the throw type is definitely a subtype of the catch type
82
    // then it can be caught.
83
    if (klass->is_subtype_of(handler_klass)) {
84
      return true;
85
    }
86
    if (!type_is_exact) {
87
      // If the type isn't exactly known then it can also be caught by
88
      // catch statements where the inexact type is a subtype of the
89
      // catch type.
90
      // given: foo extends bar extends Exception
91
      // throw bar can be caught by catch foo, catch bar, and catch
92
      // Exception, however it can't be caught by any handlers without
93
      // bar in its type hierarchy.
94
      if (handler_klass->is_subtype_of(klass)) {
95
        return true;
96
      }
97
    }
98
  }
99

100
  return false;
101
}
102

103

104
bool XHandlers::equals(XHandlers* others) const {
105
  if (others == nullptr) return false;
106
  if (length() != others->length()) return false;
107

108
  for (int i = 0; i < length(); i++) {
109
    if (!handler_at(i)->equals(others->handler_at(i))) return false;
110
  }
111
  return true;
112
}
113

114
bool XHandler::equals(XHandler* other) const {
115
  assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco");
116

117
  if (entry_pco() != other->entry_pco()) return false;
118
  if (scope_count() != other->scope_count()) return false;
119
  if (_desc != other->_desc) return false;
120

121
  assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal");
122
  return true;
123
}
124

125

126
// Implementation of IRScope
127
BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) {
128
  GraphBuilder gm(compilation, this);
129
  NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats());
130
  if (compilation->bailed_out()) return nullptr;
131
  return gm.start();
132
}
133

134

135
IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph)
136
: _compilation(compilation)
137
, _callees(2)
138
, _requires_phi_function(method->max_locals())
139
{
140
  _caller             = caller;
141
  _level              = caller == nullptr ?  0 : caller->level() + 1;
142
  _method             = method;
143
  _xhandlers          = new XHandlers(method);
144
  _number_of_locks    = 0;
145
  _monitor_pairing_ok = method->has_balanced_monitors();
146
  _wrote_final        = false;
147
  _wrote_fields       = false;
148
  _wrote_volatile     = false;
149
  _start              = nullptr;
150

151
  if (osr_bci != -1) {
152
    // selective creation of phi functions is not possibel in osr-methods
153
    _requires_phi_function.set_range(0, method->max_locals());
154
  }
155

156
  assert(method->holder()->is_loaded() , "method holder must be loaded");
157

158
  // build graph if monitor pairing is ok
159
  if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci);
160
}
161

162

163
int IRScope::max_stack() const {
164
  int my_max = method()->max_stack();
165
  int callee_max = 0;
166
  for (int i = 0; i < number_of_callees(); i++) {
167
    callee_max = MAX2(callee_max, callee_no(i)->max_stack());
168
  }
169
  return my_max + callee_max;
170
}
171

172

173
bool IRScopeDebugInfo::should_reexecute() {
174
  ciMethod* cur_method = scope()->method();
175
  int       cur_bci    = bci();
176
  if (cur_method != nullptr && cur_bci != SynchronizationEntryBCI) {
177
    Bytecodes::Code code = cur_method->java_code_at_bci(cur_bci);
178
    return Interpreter::bytecode_should_reexecute(code);
179
  } else
180
    return false;
181
}
182

183

184
// Implementation of CodeEmitInfo
185

186
// Stack must be NON-null
187
CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers, bool deoptimize_on_exception)
188
  : _scope_debug_info(nullptr)
189
  , _scope(stack->scope())
190
  , _exception_handlers(exception_handlers)
191
  , _oop_map(nullptr)
192
  , _stack(stack)
193
  , _is_method_handle_invoke(false)
194
  , _deoptimize_on_exception(deoptimize_on_exception)
195
  , _force_reexecute(false) {
196
  assert(_stack != nullptr, "must be non null");
197
}
198

199

200
CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack)
201
  : _scope_debug_info(nullptr)
202
  , _scope(info->_scope)
203
  , _exception_handlers(nullptr)
204
  , _oop_map(nullptr)
205
  , _stack(stack == nullptr ? info->_stack : stack)
206
  , _is_method_handle_invoke(info->_is_method_handle_invoke)
207
  , _deoptimize_on_exception(info->_deoptimize_on_exception)
208
  , _force_reexecute(info->_force_reexecute) {
209

210
  // deep copy of exception handlers
211
  if (info->_exception_handlers != nullptr) {
212
    _exception_handlers = new XHandlers(info->_exception_handlers);
213
  }
214
}
215

216

217
void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) {
218
  // record the safepoint before recording the debug info for enclosing scopes
219
  recorder->add_safepoint(pc_offset, _oop_map->deep_copy());
220
  bool reexecute = _force_reexecute || _scope_debug_info->should_reexecute();
221
  _scope_debug_info->record_debug_info(recorder, pc_offset, reexecute, _is_method_handle_invoke);
222
  recorder->end_safepoint(pc_offset);
223
}
224

225

226
void CodeEmitInfo::add_register_oop(LIR_Opr opr) {
227
  assert(_oop_map != nullptr, "oop map must already exist");
228
  assert(opr->is_single_cpu(), "should not call otherwise");
229

230
  VMReg name = frame_map()->regname(opr);
231
  _oop_map->set_oop(name);
232
}
233

234
// Mirror the stack size calculation in the deopt code
235
// How much stack space would we need at this point in the program in
236
// case of deoptimization?
237
int CodeEmitInfo::interpreter_frame_size() const {
238
  ValueStack* state = _stack;
239
  int size = 0;
240
  int callee_parameters = 0;
241
  int callee_locals = 0;
242
  int extra_args = state->scope()->method()->max_stack() - state->stack_size();
243

244
  while (state != nullptr) {
245
    int locks = state->locks_size();
246
    int temps = state->stack_size();
247
    bool is_top_frame = (state == _stack);
248
    ciMethod* method = state->scope()->method();
249

250
    int frame_size = BytesPerWord * Interpreter::size_activation(method->max_stack(),
251
                                                                 temps + callee_parameters,
252
                                                                 extra_args,
253
                                                                 locks,
254
                                                                 callee_parameters,
255
                                                                 callee_locals,
256
                                                                 is_top_frame);
257
    size += frame_size;
258

259
    callee_parameters = method->size_of_parameters();
260
    callee_locals = method->max_locals();
261
    extra_args = 0;
262
    state = state->caller_state();
263
  }
264
  return size + Deoptimization::last_frame_adjust(0, callee_locals) * BytesPerWord;
265
}
266

267
// Implementation of IR
268

269
IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) :
270
  _num_loops(0) {
271
  // setup IR fields
272
  _compilation = compilation;
273
  _top_scope   = new IRScope(compilation, nullptr, -1, method, osr_bci, true);
274
  _code        = nullptr;
275
}
276

277

278
void IR::optimize_blocks() {
279
  Optimizer opt(this);
280
  if (!compilation()->profile_branches()) {
281
    if (DoCEE) {
282
      opt.eliminate_conditional_expressions();
283
#ifndef PRODUCT
284
      if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); }
285
      if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); }
286
#endif
287
    }
288
    if (EliminateBlocks) {
289
      opt.eliminate_blocks();
290
#ifndef PRODUCT
291
      if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); }
292
      if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); }
293
#endif
294
    }
295
  }
296
}
297

298
void IR::eliminate_null_checks() {
299
  Optimizer opt(this);
300
  if (EliminateNullChecks) {
301
    opt.eliminate_null_checks();
302
#ifndef PRODUCT
303
    if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); }
304
    if (PrintIR  || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); }
305
#endif
306
  }
307
}
308

309
// The functionality of this class is to insert a new block between
310
// the 'from' and 'to' block of a critical edge.
311
// It first collects the block pairs, and then processes them.
312
//
313
// Some instructions may introduce more than one edge between two blocks.
314
// By checking if the current 'to' block sets critical_edge_split_flag
315
// (all new blocks set this flag) we can avoid repeated processing.
316
// This is why BlockPair contains the index rather than the original 'to' block.
317
class CriticalEdgeFinder: public BlockClosure {
318
  BlockPairList blocks;
319

320
 public:
321
  CriticalEdgeFinder(IR* ir) {
322
    ir->iterate_preorder(this);
323
  }
324

325
  void block_do(BlockBegin* bb) {
326
    BlockEnd* be = bb->end();
327
    int nos = be->number_of_sux();
328
    if (nos >= 2) {
329
      for (int i = 0; i < nos; i++) {
330
        BlockBegin* sux = be->sux_at(i);
331
        if (sux->number_of_preds() >= 2) {
332
          blocks.append(new BlockPair(bb, i));
333
        }
334
      }
335
    }
336
  }
337

338
  void split_edges() {
339
    for (int i = 0; i < blocks.length(); i++) {
340
      BlockPair* pair = blocks.at(i);
341
      BlockBegin* from = pair->from();
342
      int index = pair->index();
343
      BlockBegin* to = from->end()->sux_at(index);
344
      if (to->is_set(BlockBegin::critical_edge_split_flag)) {
345
        // inserted
346
        continue;
347
      }
348
      BlockBegin* split = from->insert_block_between(to);
349
#ifndef PRODUCT
350
      if ((PrintIR || PrintIR1) && Verbose) {
351
        tty->print_cr("Split critical edge B%d -> B%d (new block B%d)",
352
                      from->block_id(), to->block_id(), split->block_id());
353
      }
354
#endif
355
    }
356
  }
357
};
358

359
void IR::split_critical_edges() {
360
  CriticalEdgeFinder cef(this);
361
  cef.split_edges();
362
}
363

364

365
class UseCountComputer: public ValueVisitor, BlockClosure {
366
 private:
367
  void visit(Value* n) {
368
    // Local instructions and Phis for expression stack values at the
369
    // start of basic blocks are not added to the instruction list
370
    if (!(*n)->is_linked() && (*n)->can_be_linked()) {
371
      assert(false, "a node was not appended to the graph");
372
      Compilation::current()->bailout("a node was not appended to the graph");
373
    }
374
    // use n's input if not visited before
375
    if (!(*n)->is_pinned() && !(*n)->has_uses()) {
376
      // note: a) if the instruction is pinned, it will be handled by compute_use_count
377
      //       b) if the instruction has uses, it was touched before
378
      //       => in both cases we don't need to update n's values
379
      uses_do(n);
380
    }
381
    // use n
382
    (*n)->_use_count++;
383
  }
384

385
  Values* worklist;
386
  int depth;
387
  enum {
388
    max_recurse_depth = 20
389
  };
390

391
  void uses_do(Value* n) {
392
    depth++;
393
    if (depth > max_recurse_depth) {
394
      // don't allow the traversal to recurse too deeply
395
      worklist->push(*n);
396
    } else {
397
      (*n)->input_values_do(this);
398
      // special handling for some instructions
399
      if ((*n)->as_BlockEnd() != nullptr) {
400
        // note on BlockEnd:
401
        //   must 'use' the stack only if the method doesn't
402
        //   terminate, however, in those cases stack is empty
403
        (*n)->state_values_do(this);
404
      }
405
    }
406
    depth--;
407
  }
408

409
  void block_do(BlockBegin* b) {
410
    depth = 0;
411
    // process all pinned nodes as the roots of expression trees
412
    for (Instruction* n = b; n != nullptr; n = n->next()) {
413
      if (n->is_pinned()) uses_do(&n);
414
    }
415
    assert(depth == 0, "should have counted back down");
416

417
    // now process any unpinned nodes which recursed too deeply
418
    while (worklist->length() > 0) {
419
      Value t = worklist->pop();
420
      if (!t->is_pinned()) {
421
        // compute the use count
422
        uses_do(&t);
423

424
        // pin the instruction so that LIRGenerator doesn't recurse
425
        // too deeply during it's evaluation.
426
        t->pin();
427
      }
428
    }
429
    assert(depth == 0, "should have counted back down");
430
  }
431

432
  UseCountComputer() {
433
    worklist = new Values();
434
    depth = 0;
435
  }
436

437
 public:
438
  static void compute(BlockList* blocks) {
439
    UseCountComputer ucc;
440
    blocks->iterate_backward(&ucc);
441
  }
442
};
443

444

445
// helper macro for short definition of trace-output inside code
446
#ifdef ASSERT
447
  #define TRACE_LINEAR_SCAN(level, code)       \
448
    if (TraceLinearScanLevel >= level) {       \
449
      code;                                    \
450
    }
451
#else
452
  #define TRACE_LINEAR_SCAN(level, code)
453
#endif
454

455
class ComputeLinearScanOrder : public StackObj {
456
 private:
457
  int        _max_block_id;        // the highest block_id of a block
458
  int        _num_blocks;          // total number of blocks (smaller than _max_block_id)
459
  int        _num_loops;           // total number of loops
460
  bool       _iterative_dominators;// method requires iterative computation of dominatiors
461

462
  BlockList* _linear_scan_order;   // the resulting list of blocks in correct order
463

464
  ResourceBitMap _visited_blocks;   // used for recursive processing of blocks
465
  ResourceBitMap _active_blocks;    // used for recursive processing of blocks
466
  ResourceBitMap _dominator_blocks; // temporary BitMap used for computation of dominator
467
  intArray       _forward_branches; // number of incoming forward branches for each block
468
  BlockList      _loop_end_blocks;  // list of all loop end blocks collected during count_edges
469
  BitMap2D       _loop_map;         // two-dimensional bit set: a bit is set if a block is contained in a loop
470
  BlockList      _work_list;        // temporary list (used in mark_loops and compute_order)
471
  BlockList      _loop_headers;
472

473
  Compilation* _compilation;
474

475
  // accessors for _visited_blocks and _active_blocks
476
  void init_visited()                     { _active_blocks.clear(); _visited_blocks.clear(); }
477
  bool is_visited(BlockBegin* b) const    { return _visited_blocks.at(b->block_id()); }
478
  bool is_active(BlockBegin* b) const     { return _active_blocks.at(b->block_id()); }
479
  void set_visited(BlockBegin* b)         { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); }
480
  void set_active(BlockBegin* b)          { assert(!is_active(b), "already set");  _active_blocks.set_bit(b->block_id()); }
481
  void clear_active(BlockBegin* b)        { assert(is_active(b), "not already");   _active_blocks.clear_bit(b->block_id()); }
482

483
  // accessors for _forward_branches
484
  void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); }
485
  int  dec_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) - 1); return _forward_branches.at(b->block_id()); }
486

487
  // accessors for _loop_map
488
  bool is_block_in_loop   (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); }
489
  void set_block_in_loop  (int loop_idx, BlockBegin* b)       { _loop_map.set_bit(loop_idx, b->block_id()); }
490
  void clear_block_in_loop(int loop_idx, int block_id)        { _loop_map.clear_bit(loop_idx, block_id); }
491

492
  // count edges between blocks
493
  void count_edges(BlockBegin* cur, BlockBegin* parent);
494

495
  // loop detection
496
  void mark_loops();
497
  void clear_non_natural_loops(BlockBegin* start_block);
498
  void assign_loop_depth(BlockBegin* start_block);
499

500
  // computation of final block order
501
  BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b);
502
  void compute_dominator(BlockBegin* cur, BlockBegin* parent);
503
  void compute_dominator_impl(BlockBegin* cur, BlockBegin* parent);
504
  int  compute_weight(BlockBegin* cur);
505
  bool ready_for_processing(BlockBegin* cur);
506
  void sort_into_work_list(BlockBegin* b);
507
  void append_block(BlockBegin* cur);
508
  void compute_order(BlockBegin* start_block);
509

510
  // fixup of dominators for non-natural loops
511
  bool compute_dominators_iter();
512
  void compute_dominators();
513

514
  // debug functions
515
  DEBUG_ONLY(void print_blocks();)
516
  DEBUG_ONLY(void verify();)
517

518
  Compilation* compilation() const { return _compilation; }
519
 public:
520
  ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block);
521

522
  // accessors for final result
523
  BlockList* linear_scan_order() const    { return _linear_scan_order; }
524
  int        num_loops() const            { return _num_loops; }
525
};
526

527

528
ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
529
  _max_block_id(BlockBegin::number_of_blocks()),
530
  _num_blocks(0),
531
  _num_loops(0),
532
  _iterative_dominators(false),
533
  _linear_scan_order(nullptr), // initialized later with correct size
534
  _visited_blocks(_max_block_id),
535
  _active_blocks(_max_block_id),
536
  _dominator_blocks(_max_block_id),
537
  _forward_branches(_max_block_id, _max_block_id, 0),
538
  _loop_end_blocks(8),
539
  _loop_map(0),             // initialized later with correct size
540
  _work_list(8),
541
  _compilation(c)
542
{
543
  TRACE_LINEAR_SCAN(2, tty->print_cr("***** computing linear-scan block order"));
544

545
  count_edges(start_block, nullptr);
546

547
  if (compilation()->is_profiling()) {
548
    ciMethod *method = compilation()->method();
549
    if (!method->is_accessor()) {
550
      ciMethodData* md = method->method_data_or_null();
551
      assert(md != nullptr, "Sanity");
552
      md->set_compilation_stats(_num_loops, _num_blocks);
553
    }
554
  }
555

556
  if (_num_loops > 0) {
557
    mark_loops();
558
    clear_non_natural_loops(start_block);
559
    assign_loop_depth(start_block);
560
  }
561

562
  compute_order(start_block);
563
  compute_dominators();
564

565
  DEBUG_ONLY(print_blocks());
566
  DEBUG_ONLY(verify());
567
}
568

569

570
// Traverse the CFG:
571
// * count total number of blocks
572
// * count all incoming edges and backward incoming edges
573
// * number loop header blocks
574
// * create a list with all loop end blocks
575
void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) {
576
  TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != nullptr ? parent->block_id() : -1));
577
  assert(cur->dominator() == nullptr, "dominator already initialized");
578

579
  if (is_active(cur)) {
580
    TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch"));
581
    assert(is_visited(cur), "block must be visisted when block is active");
582
    assert(parent != nullptr, "must have parent");
583

584
    cur->set(BlockBegin::backward_branch_target_flag);
585

586
    // When a loop header is also the start of an exception handler, then the backward branch is
587
    // an exception edge. Because such edges are usually critical edges which cannot be split, the
588
    // loop must be excluded here from processing.
589
    if (cur->is_set(BlockBegin::exception_entry_flag)) {
590
      // Make sure that dominators are correct in this weird situation
591
      _iterative_dominators = true;
592
      return;
593
    }
594

595
    cur->set(BlockBegin::linear_scan_loop_header_flag);
596
    parent->set(BlockBegin::linear_scan_loop_end_flag);
597

598
    assert(parent->number_of_sux() == 1 && parent->sux_at(0) == cur,
599
           "loop end blocks must have one successor (critical edges are split)");
600

601
    _loop_end_blocks.append(parent);
602
    return;
603
  }
604

605
  // increment number of incoming forward branches
606
  inc_forward_branches(cur);
607

608
  if (is_visited(cur)) {
609
    TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited"));
610
    return;
611
  }
612

613
  _num_blocks++;
614
  set_visited(cur);
615
  set_active(cur);
616

617
  // recursive call for all successors
618
  int i;
619
  for (i = cur->number_of_sux() - 1; i >= 0; i--) {
620
    count_edges(cur->sux_at(i), cur);
621
  }
622
  for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
623
    count_edges(cur->exception_handler_at(i), cur);
624
  }
625

626
  clear_active(cur);
627

628
  // Each loop has a unique number.
629
  // When multiple loops are nested, assign_loop_depth assumes that the
630
  // innermost loop has the lowest number. This is guaranteed by setting
631
  // the loop number after the recursive calls for the successors above
632
  // have returned.
633
  if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
634
    assert(cur->loop_index() == -1, "cannot set loop-index twice");
635
    TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops));
636

637
    cur->set_loop_index(_num_loops);
638
    _loop_headers.append(cur);
639
    _num_loops++;
640
  }
641

642
  TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id()));
643
}
644

645

646
void ComputeLinearScanOrder::mark_loops() {
647
  TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops"));
648

649
  _loop_map = BitMap2D(_num_loops, _max_block_id);
650

651
  for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) {
652
    BlockBegin* loop_end   = _loop_end_blocks.at(i);
653
    BlockBegin* loop_start = loop_end->sux_at(0);
654
    int         loop_idx   = loop_start->loop_index();
655

656
    TRACE_LINEAR_SCAN(3, tty->print_cr("Processing loop from B%d to B%d (loop %d):", loop_start->block_id(), loop_end->block_id(), loop_idx));
657
    assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set");
658
    assert(loop_end->number_of_sux() == 1, "incorrect number of successors");
659
    assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set");
660
    assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set");
661
    assert(_work_list.is_empty(), "work list must be empty before processing");
662

663
    // add the end-block of the loop to the working list
664
    _work_list.push(loop_end);
665
    set_block_in_loop(loop_idx, loop_end);
666
    do {
667
      BlockBegin* cur = _work_list.pop();
668

669
      TRACE_LINEAR_SCAN(3, tty->print_cr("    processing B%d", cur->block_id()));
670
      assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list");
671

672
      // recursive processing of all predecessors ends when start block of loop is reached
673
      if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) {
674
        for (int j = cur->number_of_preds() - 1; j >= 0; j--) {
675
          BlockBegin* pred = cur->pred_at(j);
676

677
          if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) {
678
            // this predecessor has not been processed yet, so add it to work list
679
            TRACE_LINEAR_SCAN(3, tty->print_cr("    pushing B%d", pred->block_id()));
680
            _work_list.push(pred);
681
            set_block_in_loop(loop_idx, pred);
682
          }
683
        }
684
      }
685
    } while (!_work_list.is_empty());
686
  }
687
}
688

689

690
// check for non-natural loops (loops where the loop header does not dominate
691
// all other loop blocks = loops with multiple entries).
692
// such loops are ignored
693
void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) {
694
  for (int i = _num_loops - 1; i >= 0; i--) {
695
    if (is_block_in_loop(i, start_block)) {
696
      // loop i contains the entry block of the method
697
      // -> this is not a natural loop, so ignore it
698
      TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
699

700
      BlockBegin *loop_header = _loop_headers.at(i);
701
      assert(loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Must be loop header");
702

703
      for (int j = 0; j < loop_header->number_of_preds(); j++) {
704
        BlockBegin *pred = loop_header->pred_at(j);
705
        pred->clear(BlockBegin::linear_scan_loop_end_flag);
706
      }
707

708
      loop_header->clear(BlockBegin::linear_scan_loop_header_flag);
709

710
      for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
711
        clear_block_in_loop(i, block_id);
712
      }
713
      _iterative_dominators = true;
714
    }
715
  }
716
}
717

718
void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) {
719
  TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing loop-depth and weight"));
720
  init_visited();
721

722
  assert(_work_list.is_empty(), "work list must be empty before processing");
723
  _work_list.append(start_block);
724

725
  do {
726
    BlockBegin* cur = _work_list.pop();
727

728
    if (!is_visited(cur)) {
729
      set_visited(cur);
730
      TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id()));
731

732
      // compute loop-depth and loop-index for the block
733
      assert(cur->loop_depth() == 0, "cannot set loop-depth twice");
734
      int i;
735
      int loop_depth = 0;
736
      int min_loop_idx = -1;
737
      for (i = _num_loops - 1; i >= 0; i--) {
738
        if (is_block_in_loop(i, cur)) {
739
          loop_depth++;
740
          min_loop_idx = i;
741
        }
742
      }
743
      cur->set_loop_depth(loop_depth);
744
      cur->set_loop_index(min_loop_idx);
745

746
      // append all unvisited successors to work list
747
      for (i = cur->number_of_sux() - 1; i >= 0; i--) {
748
        _work_list.append(cur->sux_at(i));
749
      }
750
      for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
751
        _work_list.append(cur->exception_handler_at(i));
752
      }
753
    }
754
  } while (!_work_list.is_empty());
755
}
756

757

758
BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) {
759
  assert(a != nullptr && b != nullptr, "must have input blocks");
760

761
  _dominator_blocks.clear();
762
  while (a != nullptr) {
763
    _dominator_blocks.set_bit(a->block_id());
764
    assert(a->dominator() != nullptr || a == _linear_scan_order->at(0), "dominator must be initialized");
765
    a = a->dominator();
766
  }
767
  while (b != nullptr && !_dominator_blocks.at(b->block_id())) {
768
    assert(b->dominator() != nullptr || b == _linear_scan_order->at(0), "dominator must be initialized");
769
    b = b->dominator();
770
  }
771

772
  assert(b != nullptr, "could not find dominator");
773
  return b;
774
}
775

776
void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) {
777
  init_visited();
778
  compute_dominator_impl(cur, parent);
779
}
780

781
void ComputeLinearScanOrder::compute_dominator_impl(BlockBegin* cur, BlockBegin* parent) {
782
  // Mark as visited to avoid recursive calls with same parent
783
  set_visited(cur);
784

785
  if (cur->dominator() == nullptr) {
786
    TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id()));
787
    cur->set_dominator(parent);
788

789
  } else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) {
790
    TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id()));
791
    // Does not hold for exception blocks
792
    assert(cur->number_of_preds() > 1 || cur->is_set(BlockBegin::exception_entry_flag), "");
793
    cur->set_dominator(common_dominator(cur->dominator(), parent));
794
  }
795

796
  // Additional edge to xhandler of all our successors
797
  // range check elimination needs that the state at the end of a
798
  // block be valid in every block it dominates so cur must dominate
799
  // the exception handlers of its successors.
800
  int num_cur_xhandler = cur->number_of_exception_handlers();
801
  for (int j = 0; j < num_cur_xhandler; j++) {
802
    BlockBegin* xhandler = cur->exception_handler_at(j);
803
    if (!is_visited(xhandler)) {
804
      compute_dominator_impl(xhandler, parent);
805
    }
806
  }
807
}
808

809

810
int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) {
811
  BlockBegin* single_sux = nullptr;
812
  if (cur->number_of_sux() == 1) {
813
    single_sux = cur->sux_at(0);
814
  }
815

816
  // limit loop-depth to 15 bit (only for security reason, it will never be so big)
817
  int weight = (cur->loop_depth() & 0x7FFF) << 16;
818

819
  // general macro for short definition of weight flags
820
  // the first instance of INC_WEIGHT_IF has the highest priority
821
  int cur_bit = 15;
822
  #define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--;
823

824
  // this is necessary for the (very rare) case that two successive blocks have
825
  // the same loop depth, but a different loop index (can happen for endless loops
826
  // with exception handlers)
827
  INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag));
828

829
  // loop end blocks (blocks that end with a backward branch) are added
830
  // after all other blocks of the loop.
831
  INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag));
832

833
  // critical edge split blocks are preferred because than they have a bigger
834
  // proability to be completely empty
835
  INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag));
836

837
  // exceptions should not be thrown in normal control flow, so these blocks
838
  // are added as late as possible
839
  INC_WEIGHT_IF(cur->end()->as_Throw() == nullptr  && (single_sux == nullptr || single_sux->end()->as_Throw()  == nullptr));
840
  INC_WEIGHT_IF(cur->end()->as_Return() == nullptr && (single_sux == nullptr || single_sux->end()->as_Return() == nullptr));
841

842
  // exceptions handlers are added as late as possible
843
  INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag));
844

845
  // guarantee that weight is > 0
846
  weight |= 1;
847

848
  #undef INC_WEIGHT_IF
849
  assert(cur_bit >= 0, "too many flags");
850
  assert(weight > 0, "weight cannot become negative");
851

852
  return weight;
853
}
854

855
bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) {
856
  // Discount the edge just traveled.
857
  // When the number drops to zero, all forward branches were processed
858
  if (dec_forward_branches(cur) != 0) {
859
    return false;
860
  }
861

862
  assert(_linear_scan_order->find(cur) == -1, "block already processed (block can be ready only once)");
863
  assert(_work_list.find(cur) == -1, "block already in work-list (block can be ready only once)");
864
  return true;
865
}
866

867
void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) {
868
  assert(_work_list.find(cur) == -1, "block already in work list");
869

870
  int cur_weight = compute_weight(cur);
871

872
  // the linear_scan_number is used to cache the weight of a block
873
  cur->set_linear_scan_number(cur_weight);
874

875
#ifndef PRODUCT
876
  if (StressLinearScan) {
877
    _work_list.insert_before(0, cur);
878
    return;
879
  }
880
#endif
881

882
  _work_list.append(nullptr); // provide space for new element
883

884
  int insert_idx = _work_list.length() - 1;
885
  while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) {
886
    _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1));
887
    insert_idx--;
888
  }
889
  _work_list.at_put(insert_idx, cur);
890

891
  TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id()));
892
  TRACE_LINEAR_SCAN(3, for (int i = 0; i < _work_list.length(); i++) tty->print_cr("%8d B%2d  weight:%6x", i, _work_list.at(i)->block_id(), _work_list.at(i)->linear_scan_number()));
893

894
#ifdef ASSERT
895
  for (int i = 0; i < _work_list.length(); i++) {
896
    assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
897
    assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
898
  }
899
#endif
900
}
901

902
void ComputeLinearScanOrder::append_block(BlockBegin* cur) {
903
  TRACE_LINEAR_SCAN(3, tty->print_cr("appending block B%d (weight 0x%6x) to linear-scan order", cur->block_id(), cur->linear_scan_number()));
904
  assert(_linear_scan_order->find(cur) == -1, "cannot add the same block twice");
905

906
  // currently, the linear scan order and code emit order are equal.
907
  // therefore the linear_scan_number and the weight of a block must also
908
  // be equal.
909
  cur->set_linear_scan_number(_linear_scan_order->length());
910
  _linear_scan_order->append(cur);
911
}
912

913
void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
914
  TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing final block order"));
915

916
  // the start block is always the first block in the linear scan order
917
  _linear_scan_order = new BlockList(_num_blocks);
918
  append_block(start_block);
919

920
  assert(start_block->end()->as_Base() != nullptr, "start block must end with Base-instruction");
921
  BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
922
  BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
923

924
  BlockBegin* sux_of_osr_entry = nullptr;
925
  if (osr_entry != nullptr) {
926
    // special handling for osr entry:
927
    // ignore the edge between the osr entry and its successor for processing
928
    // the osr entry block is added manually below
929
    assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor");
930
    assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "successor of osr entry must have two predecessors (otherwise it is not present in normal control flow");
931

932
    sux_of_osr_entry = osr_entry->sux_at(0);
933
    dec_forward_branches(sux_of_osr_entry);
934

935
    compute_dominator(osr_entry, start_block);
936
    _iterative_dominators = true;
937
  }
938
  compute_dominator(std_entry, start_block);
939

940
  // start processing with standard entry block
941
  assert(_work_list.is_empty(), "list must be empty before processing");
942

943
  if (ready_for_processing(std_entry)) {
944
    sort_into_work_list(std_entry);
945
  } else {
946
    assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)");
947
  }
948

949
  do {
950
    BlockBegin* cur = _work_list.pop();
951

952
    if (cur == sux_of_osr_entry) {
953
      // the osr entry block is ignored in normal processing, it is never added to the
954
      // work list. Instead, it is added as late as possible manually here.
955
      append_block(osr_entry);
956
      compute_dominator(cur, osr_entry);
957
    }
958
    append_block(cur);
959

960
    int i;
961
    int num_sux = cur->number_of_sux();
962
    // changed loop order to get "intuitive" order of if- and else-blocks
963
    for (i = 0; i < num_sux; i++) {
964
      BlockBegin* sux = cur->sux_at(i);
965
      compute_dominator(sux, cur);
966
      if (ready_for_processing(sux)) {
967
        sort_into_work_list(sux);
968
      }
969
    }
970
    num_sux = cur->number_of_exception_handlers();
971
    for (i = 0; i < num_sux; i++) {
972
      BlockBegin* sux = cur->exception_handler_at(i);
973
      if (ready_for_processing(sux)) {
974
        sort_into_work_list(sux);
975
      }
976
    }
977
  } while (_work_list.length() > 0);
978
}
979

980

981
bool ComputeLinearScanOrder::compute_dominators_iter() {
982
  bool changed = false;
983
  int num_blocks = _linear_scan_order->length();
984

985
  assert(_linear_scan_order->at(0)->dominator() == nullptr, "must not have dominator");
986
  assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors");
987
  for (int i = 1; i < num_blocks; i++) {
988
    BlockBegin* block = _linear_scan_order->at(i);
989

990
    BlockBegin* dominator = block->pred_at(0);
991
    int num_preds = block->number_of_preds();
992

993
    TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: Processing B%d", block->block_id()));
994

995
    for (int j = 0; j < num_preds; j++) {
996

997
      BlockBegin *pred = block->pred_at(j);
998
      TRACE_LINEAR_SCAN(4, tty->print_cr("   DOM: Subrocessing B%d", pred->block_id()));
999

1000
      if (block->is_set(BlockBegin::exception_entry_flag)) {
1001
        dominator = common_dominator(dominator, pred);
1002
        int num_pred_preds = pred->number_of_preds();
1003
        for (int k = 0; k < num_pred_preds; k++) {
1004
          dominator = common_dominator(dominator, pred->pred_at(k));
1005
        }
1006
      } else {
1007
        dominator = common_dominator(dominator, pred);
1008
      }
1009
    }
1010

1011
    if (dominator != block->dominator()) {
1012
      TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: updating dominator of B%d from B%d to B%d", block->block_id(), block->dominator()->block_id(), dominator->block_id()));
1013

1014
      block->set_dominator(dominator);
1015
      changed = true;
1016
    }
1017
  }
1018
  return changed;
1019
}
1020

1021
void ComputeLinearScanOrder::compute_dominators() {
1022
  TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators));
1023

1024
  // iterative computation of dominators is only required for methods with non-natural loops
1025
  // and OSR-methods. For all other methods, the dominators computed when generating the
1026
  // linear scan block order are correct.
1027
  if (_iterative_dominators) {
1028
    do {
1029
      TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation"));
1030
    } while (compute_dominators_iter());
1031
  }
1032

1033
  // check that dominators are correct
1034
  assert(!compute_dominators_iter(), "fix point not reached");
1035

1036
  // Add Blocks to dominates-Array
1037
  int num_blocks = _linear_scan_order->length();
1038
  for (int i = 0; i < num_blocks; i++) {
1039
    BlockBegin* block = _linear_scan_order->at(i);
1040

1041
    BlockBegin *dom = block->dominator();
1042
    if (dom) {
1043
      assert(dom->dominator_depth() != -1, "Dominator must have been visited before");
1044
      dom->dominates()->append(block);
1045
      block->set_dominator_depth(dom->dominator_depth() + 1);
1046
    } else {
1047
      block->set_dominator_depth(0);
1048
    }
1049
  }
1050
}
1051

1052

1053
#ifdef ASSERT
1054
void ComputeLinearScanOrder::print_blocks() {
1055
  if (TraceLinearScanLevel >= 2) {
1056
    tty->print_cr("----- loop information:");
1057
    for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
1058
      BlockBegin* cur = _linear_scan_order->at(block_idx);
1059

1060
      tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id());
1061
      for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
1062
        tty->print ("%d ", is_block_in_loop(loop_idx, cur));
1063
      }
1064
      tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth());
1065
    }
1066
  }
1067

1068
  if (TraceLinearScanLevel >= 1) {
1069
    tty->print_cr("----- linear-scan block order:");
1070
    for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
1071
      BlockBegin* cur = _linear_scan_order->at(block_idx);
1072
      tty->print("%4d: B%2d    loop: %2d  depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth());
1073

1074
      tty->print(cur->is_set(BlockBegin::exception_entry_flag)         ? " ex" : "   ");
1075
      tty->print(cur->is_set(BlockBegin::critical_edge_split_flag)     ? " ce" : "   ");
1076
      tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : "   ");
1077
      tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag)    ? " le" : "   ");
1078

1079
      if (cur->dominator() != nullptr) {
1080
        tty->print("    dom: B%d ", cur->dominator()->block_id());
1081
      } else {
1082
        tty->print("    dom: null ");
1083
      }
1084

1085
      if (cur->number_of_preds() > 0) {
1086
        tty->print("    preds: ");
1087
        for (int j = 0; j < cur->number_of_preds(); j++) {
1088
          BlockBegin* pred = cur->pred_at(j);
1089
          tty->print("B%d ", pred->block_id());
1090
        }
1091
      }
1092
      if (cur->number_of_sux() > 0) {
1093
        tty->print("    sux: ");
1094
        for (int j = 0; j < cur->number_of_sux(); j++) {
1095
          BlockBegin* sux = cur->sux_at(j);
1096
          tty->print("B%d ", sux->block_id());
1097
        }
1098
      }
1099
      if (cur->number_of_exception_handlers() > 0) {
1100
        tty->print("    ex: ");
1101
        for (int j = 0; j < cur->number_of_exception_handlers(); j++) {
1102
          BlockBegin* ex = cur->exception_handler_at(j);
1103
          tty->print("B%d ", ex->block_id());
1104
        }
1105
      }
1106
      tty->cr();
1107
    }
1108
  }
1109
}
1110

1111
void ComputeLinearScanOrder::verify() {
1112
  assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list");
1113

1114
  if (StressLinearScan) {
1115
    // blocks are scrambled when StressLinearScan is used
1116
    return;
1117
  }
1118

1119
  // check that all successors of a block have a higher linear-scan-number
1120
  // and that all predecessors of a block have a lower linear-scan-number
1121
  // (only backward branches of loops are ignored)
1122
  int i;
1123
  for (i = 0; i < _linear_scan_order->length(); i++) {
1124
    BlockBegin* cur = _linear_scan_order->at(i);
1125

1126
    assert(cur->linear_scan_number() == i, "incorrect linear_scan_number");
1127
    assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->find(cur), "incorrect linear_scan_number");
1128

1129
    int j;
1130
    for (j = cur->number_of_sux() - 1; j >= 0; j--) {
1131
      BlockBegin* sux = cur->sux_at(j);
1132

1133
      assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->find(sux), "incorrect linear_scan_number");
1134
      if (!sux->is_set(BlockBegin::backward_branch_target_flag)) {
1135
        assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
1136
      }
1137
      if (cur->loop_depth() == sux->loop_depth()) {
1138
        assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successive blocks with same loop depth must have same loop index");
1139
      }
1140
    }
1141

1142
    for (j = cur->number_of_preds() - 1; j >= 0; j--) {
1143
      BlockBegin* pred = cur->pred_at(j);
1144

1145
      assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->find(pred), "incorrect linear_scan_number");
1146
      if (!cur->is_set(BlockBegin::backward_branch_target_flag)) {
1147
        assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
1148
      }
1149
      if (cur->loop_depth() == pred->loop_depth()) {
1150
        assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successive blocks with same loop depth must have same loop index");
1151
      }
1152

1153
      assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors");
1154
    }
1155

1156
    // check dominator
1157
    if (i == 0) {
1158
      assert(cur->dominator() == nullptr, "first block has no dominator");
1159
    } else {
1160
      assert(cur->dominator() != nullptr, "all but first block must have dominator");
1161
    }
1162
    // Assertion does not hold for exception handlers
1163
    assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator");
1164
  }
1165

1166
  // check that all loops are continuous
1167
  for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
1168
    int block_idx = 0;
1169
    assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop");
1170

1171
    // skip blocks before the loop
1172
    while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
1173
      block_idx++;
1174
    }
1175
    // skip blocks of loop
1176
    while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
1177
      block_idx++;
1178
    }
1179
    // after the first non-loop block, there must not be another loop-block
1180
    while (block_idx < _num_blocks) {
1181
      assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order");
1182
      block_idx++;
1183
    }
1184
  }
1185
}
1186
#endif // ASSERT
1187

1188

1189
void IR::compute_code() {
1190
  assert(is_valid(), "IR must be valid");
1191

1192
  ComputeLinearScanOrder compute_order(compilation(), start());
1193
  _num_loops = compute_order.num_loops();
1194
  _code = compute_order.linear_scan_order();
1195
}
1196

1197

1198
void IR::compute_use_counts() {
1199
  // make sure all values coming out of this block get evaluated.
1200
  int num_blocks = _code->length();
1201
  for (int i = 0; i < num_blocks; i++) {
1202
    _code->at(i)->end()->state()->pin_stack_for_linear_scan();
1203
  }
1204

1205
  // compute use counts
1206
  UseCountComputer::compute(_code);
1207
}
1208

1209

1210
void IR::iterate_preorder(BlockClosure* closure) {
1211
  assert(is_valid(), "IR must be valid");
1212
  start()->iterate_preorder(closure);
1213
}
1214

1215

1216
void IR::iterate_postorder(BlockClosure* closure) {
1217
  assert(is_valid(), "IR must be valid");
1218
  start()->iterate_postorder(closure);
1219
}
1220

1221
void IR::iterate_linear_scan_order(BlockClosure* closure) {
1222
  linear_scan_order()->iterate_forward(closure);
1223
}
1224

1225

1226
#ifndef PRODUCT
1227
class BlockPrinter: public BlockClosure {
1228
 private:
1229
  InstructionPrinter* _ip;
1230
  bool                _cfg_only;
1231
  bool                _live_only;
1232

1233
 public:
1234
  BlockPrinter(InstructionPrinter* ip, bool cfg_only, bool live_only = false) {
1235
    _ip       = ip;
1236
    _cfg_only = cfg_only;
1237
    _live_only = live_only;
1238
  }
1239

1240
  virtual void block_do(BlockBegin* block) {
1241
    if (_cfg_only) {
1242
      _ip->print_instr(block); tty->cr();
1243
    } else {
1244
      block->print_block(*_ip, _live_only);
1245
    }
1246
  }
1247
};
1248

1249

1250
void IR::print(BlockBegin* start, bool cfg_only, bool live_only) {
1251
  ttyLocker ttyl;
1252
  InstructionPrinter ip(!cfg_only);
1253
  BlockPrinter bp(&ip, cfg_only, live_only);
1254
  start->iterate_preorder(&bp);
1255
  tty->cr();
1256
}
1257

1258
void IR::print(bool cfg_only, bool live_only) {
1259
  if (is_valid()) {
1260
    print(start(), cfg_only, live_only);
1261
  } else {
1262
    tty->print_cr("invalid IR");
1263
  }
1264
}
1265
#endif // PRODUCT
1266

1267
#ifdef ASSERT
1268
class EndNotNullValidator : public BlockClosure {
1269
 public:
1270
  virtual void block_do(BlockBegin* block) {
1271
    assert(block->end() != nullptr, "Expect block end to exist.");
1272
  }
1273
};
1274

1275
class XentryFlagValidator : public BlockClosure {
1276
 public:
1277
  virtual void block_do(BlockBegin* block) {
1278
    for (int i = 0; i < block->end()->number_of_sux(); i++) {
1279
      assert(!block->end()->sux_at(i)->is_set(BlockBegin::exception_entry_flag), "must not be xhandler");
1280
    }
1281
    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1282
      assert(block->exception_handler_at(i)->is_set(BlockBegin::exception_entry_flag), "must be xhandler");
1283
    }
1284
  }
1285
};
1286

1287
typedef GrowableArray<BlockList*> BlockListList;
1288

1289
// Validation goals:
1290
// - code() length == blocks length
1291
// - code() contents == blocks content
1292
// - Each block's computed predecessors match sux lists (length)
1293
// - Each block's computed predecessors match sux lists (set content)
1294
class PredecessorAndCodeValidator : public BlockClosure {
1295
 private:
1296
  BlockListList* _predecessors; // Each index i will hold predecessors of block with id i
1297
  BlockList*     _blocks;
1298

1299
  static int cmp(BlockBegin** a, BlockBegin** b) {
1300
    return (*a)->block_id() - (*b)->block_id();
1301
  }
1302

1303
 public:
1304
  PredecessorAndCodeValidator(IR* hir) {
1305
    ResourceMark rm;
1306
    _predecessors = new BlockListList(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), nullptr);
1307
    _blocks = new BlockList(BlockBegin::number_of_blocks());
1308

1309
    hir->start()->iterate_preorder(this);
1310
    if (hir->code() != nullptr) {
1311
      assert(hir->code()->length() == _blocks->length(), "must match");
1312
      for (int i = 0; i < _blocks->length(); i++) {
1313
        assert(hir->code()->contains(_blocks->at(i)), "should be in both lists");
1314
      }
1315
    }
1316

1317
    for (int i = 0; i < _blocks->length(); i++) {
1318
      BlockBegin* block = _blocks->at(i);
1319
      verify_block_preds_against_collected_preds(block);
1320
    }
1321
  }
1322

1323
  virtual void block_do(BlockBegin* block) {
1324
    _blocks->append(block);
1325
    collect_predecessors(block);
1326
  }
1327

1328
 private:
1329
  void collect_predecessors(BlockBegin* block) {
1330
    for (int i = 0; i < block->end()->number_of_sux(); i++) {
1331
      collect_predecessor(block, block->end()->sux_at(i));
1332
    }
1333
    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1334
      collect_predecessor(block, block->exception_handler_at(i));
1335
    }
1336
  }
1337

1338
  void collect_predecessor(BlockBegin* const pred, const BlockBegin* sux) {
1339
    BlockList* preds = _predecessors->at_grow(sux->block_id(), nullptr);
1340
    if (preds == nullptr) {
1341
      preds = new BlockList();
1342
      _predecessors->at_put(sux->block_id(), preds);
1343
    }
1344
    preds->append(pred);
1345
  }
1346

1347
  void verify_block_preds_against_collected_preds(const BlockBegin* block) const {
1348
    BlockList* preds = _predecessors->at(block->block_id());
1349
    if (preds == nullptr) {
1350
      assert(block->number_of_preds() == 0, "should be the same");
1351
      return;
1352
    }
1353
    assert(preds->length() == block->number_of_preds(), "should be the same");
1354

1355
    // clone the pred list so we can mutate it
1356
    BlockList* pred_copy = new BlockList();
1357
    for (int j = 0; j < block->number_of_preds(); j++) {
1358
      pred_copy->append(block->pred_at(j));
1359
    }
1360
    // sort them in the same order
1361
    preds->sort(cmp);
1362
    pred_copy->sort(cmp);
1363
    for (int j = 0; j < block->number_of_preds(); j++) {
1364
      assert(preds->at(j) == pred_copy->at(j), "must match");
1365
    }
1366
  }
1367
};
1368

1369
class VerifyBlockBeginField : public BlockClosure {
1370
public:
1371
  virtual void block_do(BlockBegin* block) {
1372
    for (Instruction* cur = block; cur != nullptr; cur = cur->next()) {
1373
      assert(cur->block() == block, "Block begin is not correct");
1374
    }
1375
  }
1376
};
1377

1378
class ValidateEdgeMutuality : public BlockClosure {
1379
 public:
1380
  virtual void block_do(BlockBegin* block) {
1381
    for (int i = 0; i < block->end()->number_of_sux(); i++) {
1382
      assert(block->end()->sux_at(i)->is_predecessor(block), "Block's successor should have it as predecessor");
1383
    }
1384

1385
    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1386
      assert(block->exception_handler_at(i)->is_predecessor(block), "Block's exception handler should have it as predecessor");
1387
    }
1388

1389
    for (int i = 0; i < block->number_of_preds(); i++) {
1390
      assert(block->pred_at(i) != nullptr, "Predecessor must exist");
1391
      assert(block->pred_at(i)->end() != nullptr, "Predecessor end must exist");
1392
      bool is_sux      = block->pred_at(i)->end()->is_sux(block);
1393
      bool is_xhandler = block->pred_at(i)->is_exception_handler(block);
1394
      assert(is_sux || is_xhandler, "Block's predecessor should have it as successor or xhandler");
1395
    }
1396
  }
1397
};
1398

1399
void IR::expand_with_neighborhood(BlockList& blocks) {
1400
  int original_size = blocks.length();
1401
  for (int h = 0; h < original_size; h++) {
1402
    BlockBegin* block = blocks.at(h);
1403

1404
    for (int i = 0; i < block->end()->number_of_sux(); i++) {
1405
      if (!blocks.contains(block->end()->sux_at(i))) {
1406
        blocks.append(block->end()->sux_at(i));
1407
      }
1408
    }
1409

1410
    for (int i = 0; i < block->number_of_preds(); i++) {
1411
      if (!blocks.contains(block->pred_at(i))) {
1412
        blocks.append(block->pred_at(i));
1413
      }
1414
    }
1415

1416
    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1417
      if (!blocks.contains(block->exception_handler_at(i))) {
1418
        blocks.append(block->exception_handler_at(i));
1419
      }
1420
    }
1421
  }
1422
}
1423

1424
void IR::verify_local(BlockList& blocks) {
1425
  EndNotNullValidator ennv;
1426
  blocks.iterate_forward(&ennv);
1427

1428
  ValidateEdgeMutuality vem;
1429
  blocks.iterate_forward(&vem);
1430

1431
  VerifyBlockBeginField verifier;
1432
  blocks.iterate_forward(&verifier);
1433
}
1434

1435
void IR::verify() {
1436
  XentryFlagValidator xe;
1437
  iterate_postorder(&xe);
1438

1439
  PredecessorAndCodeValidator pv(this);
1440

1441
  EndNotNullValidator ennv;
1442
  iterate_postorder(&ennv);
1443

1444
  ValidateEdgeMutuality vem;
1445
  iterate_postorder(&vem);
1446

1447
  VerifyBlockBeginField verifier;
1448
  iterate_postorder(&verifier);
1449
}
1450
#endif // ASSERT
1451

1452
void SubstitutionResolver::visit(Value* v) {
1453
  Value v0 = *v;
1454
  if (v0) {
1455
    Value vs = v0->subst();
1456
    if (vs != v0) {
1457
      *v = v0->subst();
1458
    }
1459
  }
1460
}
1461

1462
#ifdef ASSERT
1463
class SubstitutionChecker: public ValueVisitor {
1464
  void visit(Value* v) {
1465
    Value v0 = *v;
1466
    if (v0) {
1467
      Value vs = v0->subst();
1468
      assert(vs == v0, "missed substitution");
1469
    }
1470
  }
1471
};
1472
#endif
1473

1474

1475
void SubstitutionResolver::block_do(BlockBegin* block) {
1476
  Instruction* last = nullptr;
1477
  for (Instruction* n = block; n != nullptr;) {
1478
    n->values_do(this);
1479
    // need to remove this instruction from the instruction stream
1480
    if (n->subst() != n) {
1481
      guarantee(last != nullptr, "must have last");
1482
      last->set_next(n->next());
1483
    } else {
1484
      last = n;
1485
    }
1486
    n = last->next();
1487
  }
1488

1489
#ifdef ASSERT
1490
  SubstitutionChecker check_substitute;
1491
  if (block->state()) block->state()->values_do(&check_substitute);
1492
  block->block_values_do(&check_substitute);
1493
  if (block->end() && block->end()->state()) block->end()->state()->values_do(&check_substitute);
1494
#endif
1495
}
1496