1 /*
2 * Copyright (c) 1999, 2010, 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 "utilities/bitMap.inline.hpp"
33
34
35 // Implementation of XHandlers
36 //
37 // Note: This code could eventually go away if we are
38 // just using the ciExceptionHandlerStream.
39
40 XHandlers::XHandlers(ciMethod* method) : _list(method->exception_table_length()) {
41 ciExceptionHandlerStream s(method);
42 while (!s.is_done()) {
43 _list.append(new XHandler(s.handler()));
44 s.next();
45 }
46 assert(s.count() == method->exception_table_length(), "exception table lengths inconsistent");
47 }
48
49 // deep copy of all XHandler contained in list
50 XHandlers::XHandlers(XHandlers* other) :
51 _list(other->length())
52 {
53 for (int i = 0; i < other->length(); i++) {
54 _list.append(new XHandler(other->handler_at(i)));
55 }
56 }
57
58 // Returns whether a particular exception type can be caught. Also
59 // returns true if klass is unloaded or any exception handler
60 // classes are unloaded. type_is_exact indicates whether the throw
61 // is known to be exactly that class or it might throw a subtype.
62 bool XHandlers::could_catch(ciInstanceKlass* klass, bool type_is_exact) const {
63 // the type is unknown so be conservative
64 if (!klass->is_loaded()) {
65 return true;
66 }
67
68 for (int i = 0; i < length(); i++) {
69 XHandler* handler = handler_at(i);
70 if (handler->is_catch_all()) {
71 // catch of ANY
72 return true;
73 }
74 ciInstanceKlass* handler_klass = handler->catch_klass();
75 // if it's unknown it might be catchable
76 if (!handler_klass->is_loaded()) {
77 return true;
78 }
79 // if the throw type is definitely a subtype of the catch type
80 // then it can be caught.
81 if (klass->is_subtype_of(handler_klass)) {
82 return true;
83 }
84 if (!type_is_exact) {
85 // If the type isn't exactly known then it can also be caught by
86 // catch statements where the inexact type is a subtype of the
87 // catch type.
88 // given: foo extends bar extends Exception
89 // throw bar can be caught by catch foo, catch bar, and catch
90 // Exception, however it can't be caught by any handlers without
91 // bar in its type hierarchy.
92 if (handler_klass->is_subtype_of(klass)) {
93 return true;
94 }
95 }
96 }
97
98 return false;
99 }
100
101
102 bool XHandlers::equals(XHandlers* others) const {
103 if (others == NULL) return false;
104 if (length() != others->length()) return false;
105
106 for (int i = 0; i < length(); i++) {
107 if (!handler_at(i)->equals(others->handler_at(i))) return false;
108 }
109 return true;
110 }
111
112 bool XHandler::equals(XHandler* other) const {
113 assert(entry_pco() != -1 && other->entry_pco() != -1, "must have entry_pco");
114
115 if (entry_pco() != other->entry_pco()) return false;
116 if (scope_count() != other->scope_count()) return false;
117 if (_desc != other->_desc) return false;
118
119 assert(entry_block() == other->entry_block(), "entry_block must be equal when entry_pco is equal");
120 return true;
121 }
122
123
124 // Implementation of IRScope
125
126 BlockBegin* IRScope::header_block(BlockBegin* entry, BlockBegin::Flag f, ValueStack* state) {
127 if (entry == NULL) return NULL;
128 assert(entry->is_set(f), "entry/flag mismatch");
129 // create header block
130 BlockBegin* h = new BlockBegin(entry->bci());
131 BlockEnd* g = new Goto(entry, false);
132 h->set_next(g, entry->bci());
133 h->set_end(g);
134 h->set(f);
135 // setup header block end state
136 ValueStack* s = state->copy(); // can use copy since stack is empty (=> no phis)
137 assert(s->stack_is_empty(), "must have empty stack at entry point");
138 g->set_state(s);
139 return h;
140 }
141
142
143 BlockBegin* IRScope::build_graph(Compilation* compilation, int osr_bci) {
144 GraphBuilder gm(compilation, this);
145 NOT_PRODUCT(if (PrintValueNumbering && Verbose) gm.print_stats());
146 if (compilation->bailed_out()) return NULL;
147 return gm.start();
148 }
149
150
151 IRScope::IRScope(Compilation* compilation, IRScope* caller, int caller_bci, ciMethod* method, int osr_bci, bool create_graph)
152 : _callees(2)
153 , _compilation(compilation)
154 , _lock_stack_size(-1)
155 , _requires_phi_function(method->max_locals())
156 {
157 _caller = caller;
158 _caller_bci = caller == NULL ? -1 : caller_bci;
159 _caller_state = NULL; // Must be set later if needed
160 _level = caller == NULL ? 0 : caller->level() + 1;
161 _method = method;
162 _xhandlers = new XHandlers(method);
163 _number_of_locks = 0;
164 _monitor_pairing_ok = method->has_balanced_monitors();
165 _start = NULL;
166
167 if (osr_bci == -1) {
168 _requires_phi_function.clear();
169 } else {
170 // selective creation of phi functions is not possibel in osr-methods
171 _requires_phi_function.set_range(0, method->max_locals());
172 }
173
174 assert(method->holder()->is_loaded() , "method holder must be loaded");
175
176 // build graph if monitor pairing is ok
177 if (create_graph && monitor_pairing_ok()) _start = build_graph(compilation, osr_bci);
178 }
179
180
181 int IRScope::max_stack() const {
182 int my_max = method()->max_stack();
183 int callee_max = 0;
184 for (int i = 0; i < number_of_callees(); i++) {
185 callee_max = MAX2(callee_max, callee_no(i)->max_stack());
186 }
187 return my_max + callee_max;
188 }
189
190
191 void IRScope::compute_lock_stack_size() {
192 if (!InlineMethodsWithExceptionHandlers) {
193 _lock_stack_size = 0;
194 return;
195 }
196
197 // Figure out whether we have to preserve expression stack elements
198 // for parent scopes, and if so, how many
199 IRScope* cur_scope = this;
200 while (cur_scope != NULL && !cur_scope->xhandlers()->has_handlers()) {
201 cur_scope = cur_scope->caller();
202 }
203 _lock_stack_size = (cur_scope == NULL ? 0 :
204 (cur_scope->caller_state() == NULL ? 0 :
205 cur_scope->caller_state()->stack_size()));
206 }
207
208 int IRScope::top_scope_bci() const {
209 assert(!is_top_scope(), "no correct answer for top scope possible");
210 const IRScope* scope = this;
211 while (!scope->caller()->is_top_scope()) {
212 scope = scope->caller();
213 }
214 return scope->caller_bci();
215 }
216
217 bool IRScopeDebugInfo::should_reexecute() {
218 ciMethod* cur_method = scope()->method();
219 int cur_bci = bci();
220 if (cur_method != NULL && cur_bci != SynchronizationEntryBCI) {
221 Bytecodes::Code code = cur_method->java_code_at_bci(cur_bci);
222 return Interpreter::bytecode_should_reexecute(code);
223 } else
224 return false;
225 }
226
227
228 // Implementation of CodeEmitInfo
229
230 // Stack must be NON-null
231 CodeEmitInfo::CodeEmitInfo(int bci, ValueStack* stack, XHandlers* exception_handlers)
232 : _scope(stack->scope())
233 , _bci(bci)
234 , _scope_debug_info(NULL)
235 , _oop_map(NULL)
236 , _stack(stack)
237 , _exception_handlers(exception_handlers)
238 , _next(NULL)
239 , _id(-1)
240 , _is_method_handle_invoke(false) {
241 assert(_stack != NULL, "must be non null");
242 assert(_bci == SynchronizationEntryBCI || Bytecodes::is_defined(scope()->method()->java_code_at_bci(_bci)), "make sure bci points at a real bytecode");
243 }
244
245
246 CodeEmitInfo::CodeEmitInfo(CodeEmitInfo* info, bool lock_stack_only)
247 : _scope(info->_scope)
248 , _exception_handlers(NULL)
249 , _bci(info->_bci)
250 , _scope_debug_info(NULL)
251 , _oop_map(NULL)
252 , _is_method_handle_invoke(info->_is_method_handle_invoke) {
253 if (lock_stack_only) {
254 if (info->_stack != NULL) {
255 _stack = info->_stack->copy_locks();
256 } else {
257 _stack = NULL;
258 }
259 } else {
260 _stack = info->_stack;
261 }
262
263 // deep copy of exception handlers
264 if (info->_exception_handlers != NULL) {
265 _exception_handlers = new XHandlers(info->_exception_handlers);
266 }
267 }
268
269
270 void CodeEmitInfo::record_debug_info(DebugInformationRecorder* recorder, int pc_offset) {
271 // record the safepoint before recording the debug info for enclosing scopes
272 recorder->add_safepoint(pc_offset, _oop_map->deep_copy());
273 _scope_debug_info->record_debug_info(recorder, pc_offset, true/*topmost*/, _is_method_handle_invoke);
274 recorder->end_safepoint(pc_offset);
275 }
276
277
278 void CodeEmitInfo::add_register_oop(LIR_Opr opr) {
279 assert(_oop_map != NULL, "oop map must already exist");
280 assert(opr->is_single_cpu(), "should not call otherwise");
281
282 int frame_size = frame_map()->framesize();
283 int arg_count = frame_map()->oop_map_arg_count();
284 VMReg name = frame_map()->regname(opr);
285 _oop_map->set_oop(name);
286 }
287
288
289
290
291 // Implementation of IR
292
293 IR::IR(Compilation* compilation, ciMethod* method, int osr_bci) :
294 _locals_size(in_WordSize(-1))
295 , _num_loops(0) {
296 // setup IR fields
297 _compilation = compilation;
298 _top_scope = new IRScope(compilation, NULL, -1, method, osr_bci, true);
299 _code = NULL;
300 }
301
302
303 void IR::optimize() {
304 Optimizer opt(this);
305 if (!compilation()->profile_branches()) {
306 if (DoCEE) {
307 opt.eliminate_conditional_expressions();
308 #ifndef PRODUCT
309 if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after CEE"); print(true); }
310 if (PrintIR || PrintIR1 ) { tty->print_cr("IR after CEE"); print(false); }
311 #endif
312 }
313 if (EliminateBlocks) {
314 opt.eliminate_blocks();
315 #ifndef PRODUCT
316 if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after block elimination"); print(true); }
317 if (PrintIR || PrintIR1 ) { tty->print_cr("IR after block elimination"); print(false); }
318 #endif
319 }
320 }
321 if (EliminateNullChecks) {
322 opt.eliminate_null_checks();
323 #ifndef PRODUCT
324 if (PrintCFG || PrintCFG1) { tty->print_cr("CFG after null check elimination"); print(true); }
325 if (PrintIR || PrintIR1 ) { tty->print_cr("IR after null check elimination"); print(false); }
326 #endif
327 }
328 }
329
330
331 static int sort_pairs(BlockPair** a, BlockPair** b) {
332 if ((*a)->from() == (*b)->from()) {
333 return (*a)->to()->block_id() - (*b)->to()->block_id();
334 } else {
335 return (*a)->from()->block_id() - (*b)->from()->block_id();
336 }
337 }
338
339
340 class CriticalEdgeFinder: public BlockClosure {
341 BlockPairList blocks;
342 IR* _ir;
343
344 public:
345 CriticalEdgeFinder(IR* ir): _ir(ir) {}
346 void block_do(BlockBegin* bb) {
347 BlockEnd* be = bb->end();
348 int nos = be->number_of_sux();
349 if (nos >= 2) {
350 for (int i = 0; i < nos; i++) {
351 BlockBegin* sux = be->sux_at(i);
352 if (sux->number_of_preds() >= 2) {
353 blocks.append(new BlockPair(bb, sux));
354 }
355 }
356 }
357 }
358
359 void split_edges() {
360 BlockPair* last_pair = NULL;
361 blocks.sort(sort_pairs);
362 for (int i = 0; i < blocks.length(); i++) {
363 BlockPair* pair = blocks.at(i);
364 if (last_pair != NULL && pair->is_same(last_pair)) continue;
365 BlockBegin* from = pair->from();
366 BlockBegin* to = pair->to();
367 BlockBegin* split = from->insert_block_between(to);
368 #ifndef PRODUCT
369 if ((PrintIR || PrintIR1) && Verbose) {
370 tty->print_cr("Split critical edge B%d -> B%d (new block B%d)",
371 from->block_id(), to->block_id(), split->block_id());
372 }
373 #endif
374 last_pair = pair;
375 }
376 }
377 };
378
379 void IR::split_critical_edges() {
380 CriticalEdgeFinder cef(this);
381
382 iterate_preorder(&cef);
383 cef.split_edges();
384 }
385
386
387 class UseCountComputer: public ValueVisitor, BlockClosure {
388 private:
389 void visit(Value* n) {
390 // Local instructions and Phis for expression stack values at the
391 // start of basic blocks are not added to the instruction list
392 if ((*n)->bci() == -99 && (*n)->as_Local() == NULL &&
393 (*n)->as_Phi() == NULL) {
394 assert(false, "a node was not appended to the graph");
395 Compilation::current()->bailout("a node was not appended to the graph");
396 }
397 // use n's input if not visited before
398 if (!(*n)->is_pinned() && !(*n)->has_uses()) {
399 // note: a) if the instruction is pinned, it will be handled by compute_use_count
400 // b) if the instruction has uses, it was touched before
401 // => in both cases we don't need to update n's values
402 uses_do(n);
403 }
404 // use n
405 (*n)->_use_count++;
406 }
407
408 Values* worklist;
409 int depth;
410 enum {
411 max_recurse_depth = 20
412 };
413
414 void uses_do(Value* n) {
415 depth++;
416 if (depth > max_recurse_depth) {
417 // don't allow the traversal to recurse too deeply
418 worklist->push(*n);
419 } else {
420 (*n)->input_values_do(this);
421 // special handling for some instructions
422 if ((*n)->as_BlockEnd() != NULL) {
423 // note on BlockEnd:
424 // must 'use' the stack only if the method doesn't
425 // terminate, however, in those cases stack is empty
426 (*n)->state_values_do(this);
427 }
428 }
429 depth--;
430 }
431
432 void block_do(BlockBegin* b) {
433 depth = 0;
434 // process all pinned nodes as the roots of expression trees
435 for (Instruction* n = b; n != NULL; n = n->next()) {
436 if (n->is_pinned()) uses_do(&n);
437 }
438 assert(depth == 0, "should have counted back down");
439
440 // now process any unpinned nodes which recursed too deeply
441 while (worklist->length() > 0) {
442 Value t = worklist->pop();
443 if (!t->is_pinned()) {
444 // compute the use count
445 uses_do(&t);
446
447 // pin the instruction so that LIRGenerator doesn't recurse
448 // too deeply during it's evaluation.
449 t->pin();
450 }
451 }
452 assert(depth == 0, "should have counted back down");
453 }
454
455 UseCountComputer() {
456 worklist = new Values();
457 depth = 0;
458 }
459
460 public:
461 static void compute(BlockList* blocks) {
462 UseCountComputer ucc;
463 blocks->iterate_backward(&ucc);
464 }
465 };
466
467
468 // helper macro for short definition of trace-output inside code
469 #ifndef PRODUCT
470 #define TRACE_LINEAR_SCAN(level, code) \
471 if (TraceLinearScanLevel >= level) { \
472 code; \
473 }
474 #else
475 #define TRACE_LINEAR_SCAN(level, code)
476 #endif
477
478 class ComputeLinearScanOrder : public StackObj {
479 private:
480 int _max_block_id; // the highest block_id of a block
481 int _num_blocks; // total number of blocks (smaller than _max_block_id)
482 int _num_loops; // total number of loops
483 bool _iterative_dominators;// method requires iterative computation of dominatiors
484
485 BlockList* _linear_scan_order; // the resulting list of blocks in correct order
486
487 BitMap _visited_blocks; // used for recursive processing of blocks
488 BitMap _active_blocks; // used for recursive processing of blocks
489 BitMap _dominator_blocks; // temproary BitMap used for computation of dominator
490 intArray _forward_branches; // number of incoming forward branches for each block
491 BlockList _loop_end_blocks; // list of all loop end blocks collected during count_edges
492 BitMap2D _loop_map; // two-dimensional bit set: a bit is set if a block is contained in a loop
493 BlockList _work_list; // temporary list (used in mark_loops and compute_order)
494
495 Compilation* _compilation;
496
497 // accessors for _visited_blocks and _active_blocks
498 void init_visited() { _active_blocks.clear(); _visited_blocks.clear(); }
499 bool is_visited(BlockBegin* b) const { return _visited_blocks.at(b->block_id()); }
500 bool is_active(BlockBegin* b) const { return _active_blocks.at(b->block_id()); }
501 void set_visited(BlockBegin* b) { assert(!is_visited(b), "already set"); _visited_blocks.set_bit(b->block_id()); }
502 void set_active(BlockBegin* b) { assert(!is_active(b), "already set"); _active_blocks.set_bit(b->block_id()); }
503 void clear_active(BlockBegin* b) { assert(is_active(b), "not already"); _active_blocks.clear_bit(b->block_id()); }
504
505 // accessors for _forward_branches
506 void inc_forward_branches(BlockBegin* b) { _forward_branches.at_put(b->block_id(), _forward_branches.at(b->block_id()) + 1); }
507 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()); }
508
509 // accessors for _loop_map
510 bool is_block_in_loop (int loop_idx, BlockBegin* b) const { return _loop_map.at(loop_idx, b->block_id()); }
511 void set_block_in_loop (int loop_idx, BlockBegin* b) { _loop_map.set_bit(loop_idx, b->block_id()); }
512 void clear_block_in_loop(int loop_idx, int block_id) { _loop_map.clear_bit(loop_idx, block_id); }
513
514 // count edges between blocks
515 void count_edges(BlockBegin* cur, BlockBegin* parent);
516
517 // loop detection
518 void mark_loops();
519 void clear_non_natural_loops(BlockBegin* start_block);
520 void assign_loop_depth(BlockBegin* start_block);
521
522 // computation of final block order
523 BlockBegin* common_dominator(BlockBegin* a, BlockBegin* b);
524 void compute_dominator(BlockBegin* cur, BlockBegin* parent);
525 int compute_weight(BlockBegin* cur);
526 bool ready_for_processing(BlockBegin* cur);
527 void sort_into_work_list(BlockBegin* b);
528 void append_block(BlockBegin* cur);
529 void compute_order(BlockBegin* start_block);
530
531 // fixup of dominators for non-natural loops
532 bool compute_dominators_iter();
533 void compute_dominators();
534
535 // debug functions
536 NOT_PRODUCT(void print_blocks();)
537 DEBUG_ONLY(void verify();)
538
539 Compilation* compilation() const { return _compilation; }
540 public:
541 ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block);
542
543 // accessors for final result
544 BlockList* linear_scan_order() const { return _linear_scan_order; }
545 int num_loops() const { return _num_loops; }
546 };
547
548
549 ComputeLinearScanOrder::ComputeLinearScanOrder(Compilation* c, BlockBegin* start_block) :
550 _max_block_id(BlockBegin::number_of_blocks()),
551 _num_blocks(0),
552 _num_loops(0),
553 _iterative_dominators(false),
554 _visited_blocks(_max_block_id),
555 _active_blocks(_max_block_id),
556 _dominator_blocks(_max_block_id),
557 _forward_branches(_max_block_id, 0),
558 _loop_end_blocks(8),
559 _work_list(8),
560 _linear_scan_order(NULL), // initialized later with correct size
561 _loop_map(0, 0), // initialized later with correct size
562 _compilation(c)
563 {
564 TRACE_LINEAR_SCAN(2, "***** computing linear-scan block order");
565
566 init_visited();
567 count_edges(start_block, NULL);
568
569 if (compilation()->is_profiling()) {
570 compilation()->method()->method_data()->set_compilation_stats(_num_loops, _num_blocks);
571 }
572
573 if (_num_loops > 0) {
574 mark_loops();
575 clear_non_natural_loops(start_block);
576 assign_loop_depth(start_block);
577 }
578
579 compute_order(start_block);
580 compute_dominators();
581
582 NOT_PRODUCT(print_blocks());
583 DEBUG_ONLY(verify());
584 }
585
586
587 // Traverse the CFG:
588 // * count total number of blocks
589 // * count all incoming edges and backward incoming edges
590 // * number loop header blocks
591 // * create a list with all loop end blocks
592 void ComputeLinearScanOrder::count_edges(BlockBegin* cur, BlockBegin* parent) {
593 TRACE_LINEAR_SCAN(3, tty->print_cr("Enter count_edges for block B%d coming from B%d", cur->block_id(), parent != NULL ? parent->block_id() : -1));
594 assert(cur->dominator() == NULL, "dominator already initialized");
595
596 if (is_active(cur)) {
597 TRACE_LINEAR_SCAN(3, tty->print_cr("backward branch"));
598 assert(is_visited(cur), "block must be visisted when block is active");
599 assert(parent != NULL, "must have parent");
600
601 cur->set(BlockBegin::linear_scan_loop_header_flag);
602 cur->set(BlockBegin::backward_branch_target_flag);
603
604 parent->set(BlockBegin::linear_scan_loop_end_flag);
605
606 // When a loop header is also the start of an exception handler, then the backward branch is
607 // an exception edge. Because such edges are usually critical edges which cannot be split, the
608 // loop must be excluded here from processing.
609 if (cur->is_set(BlockBegin::exception_entry_flag)) {
610 // Make sure that dominators are correct in this weird situation
611 _iterative_dominators = true;
612 return;
613 }
614 assert(parent->number_of_sux() == 1 && parent->sux_at(0) == cur,
615 "loop end blocks must have one successor (critical edges are split)");
616
617 _loop_end_blocks.append(parent);
618 return;
619 }
620
621 // increment number of incoming forward branches
622 inc_forward_branches(cur);
623
624 if (is_visited(cur)) {
625 TRACE_LINEAR_SCAN(3, tty->print_cr("block already visited"));
626 return;
627 }
628
629 _num_blocks++;
630 set_visited(cur);
631 set_active(cur);
632
633 // recursive call for all successors
634 int i;
635 for (i = cur->number_of_sux() - 1; i >= 0; i--) {
636 count_edges(cur->sux_at(i), cur);
637 }
638 for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
639 count_edges(cur->exception_handler_at(i), cur);
640 }
641
642 clear_active(cur);
643
644 // Each loop has a unique number.
645 // When multiple loops are nested, assign_loop_depth assumes that the
646 // innermost loop has the lowest number. This is guaranteed by setting
647 // the loop number after the recursive calls for the successors above
648 // have returned.
649 if (cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
650 assert(cur->loop_index() == -1, "cannot set loop-index twice");
651 TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops));
652
653 cur->set_loop_index(_num_loops);
654 _num_loops++;
655 }
656
657 TRACE_LINEAR_SCAN(3, tty->print_cr("Finished count_edges for block B%d", cur->block_id()));
658 }
659
660
661 void ComputeLinearScanOrder::mark_loops() {
662 TRACE_LINEAR_SCAN(3, tty->print_cr("----- marking loops"));
663
664 _loop_map = BitMap2D(_num_loops, _max_block_id);
665 _loop_map.clear();
666
667 for (int i = _loop_end_blocks.length() - 1; i >= 0; i--) {
668 BlockBegin* loop_end = _loop_end_blocks.at(i);
669 BlockBegin* loop_start = loop_end->sux_at(0);
670 int loop_idx = loop_start->loop_index();
671
672 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));
673 assert(loop_end->is_set(BlockBegin::linear_scan_loop_end_flag), "loop end flag must be set");
674 assert(loop_end->number_of_sux() == 1, "incorrect number of successors");
675 assert(loop_start->is_set(BlockBegin::linear_scan_loop_header_flag), "loop header flag must be set");
676 assert(loop_idx >= 0 && loop_idx < _num_loops, "loop index not set");
677 assert(_work_list.is_empty(), "work list must be empty before processing");
678
679 // add the end-block of the loop to the working list
680 _work_list.push(loop_end);
681 set_block_in_loop(loop_idx, loop_end);
682 do {
683 BlockBegin* cur = _work_list.pop();
684
685 TRACE_LINEAR_SCAN(3, tty->print_cr(" processing B%d", cur->block_id()));
686 assert(is_block_in_loop(loop_idx, cur), "bit in loop map must be set when block is in work list");
687
688 // recursive processing of all predecessors ends when start block of loop is reached
689 if (cur != loop_start && !cur->is_set(BlockBegin::osr_entry_flag)) {
690 for (int j = cur->number_of_preds() - 1; j >= 0; j--) {
691 BlockBegin* pred = cur->pred_at(j);
692
693 if (!is_block_in_loop(loop_idx, pred) /*&& !pred->is_set(BlockBeginosr_entry_flag)*/) {
694 // this predecessor has not been processed yet, so add it to work list
695 TRACE_LINEAR_SCAN(3, tty->print_cr(" pushing B%d", pred->block_id()));
696 _work_list.push(pred);
697 set_block_in_loop(loop_idx, pred);
698 }
699 }
700 }
701 } while (!_work_list.is_empty());
702 }
703 }
704
705
706 // check for non-natural loops (loops where the loop header does not dominate
707 // all other loop blocks = loops with mulitple entries).
708 // such loops are ignored
709 void ComputeLinearScanOrder::clear_non_natural_loops(BlockBegin* start_block) {
710 for (int i = _num_loops - 1; i >= 0; i--) {
711 if (is_block_in_loop(i, start_block)) {
712 // loop i contains the entry block of the method
713 // -> this is not a natural loop, so ignore it
714 TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
715
716 for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
717 clear_block_in_loop(i, block_id);
718 }
719 _iterative_dominators = true;
720 }
721 }
722 }
723
724 void ComputeLinearScanOrder::assign_loop_depth(BlockBegin* start_block) {
725 TRACE_LINEAR_SCAN(3, "----- computing loop-depth and weight");
726 init_visited();
727
728 assert(_work_list.is_empty(), "work list must be empty before processing");
729 _work_list.append(start_block);
730
731 do {
732 BlockBegin* cur = _work_list.pop();
733
734 if (!is_visited(cur)) {
735 set_visited(cur);
736 TRACE_LINEAR_SCAN(4, tty->print_cr("Computing loop depth for block B%d", cur->block_id()));
737
738 // compute loop-depth and loop-index for the block
739 assert(cur->loop_depth() == 0, "cannot set loop-depth twice");
740 int i;
741 int loop_depth = 0;
742 int min_loop_idx = -1;
743 for (i = _num_loops - 1; i >= 0; i--) {
744 if (is_block_in_loop(i, cur)) {
745 loop_depth++;
746 min_loop_idx = i;
747 }
748 }
749 cur->set_loop_depth(loop_depth);
750 cur->set_loop_index(min_loop_idx);
751
752 // append all unvisited successors to work list
753 for (i = cur->number_of_sux() - 1; i >= 0; i--) {
754 _work_list.append(cur->sux_at(i));
755 }
756 for (i = cur->number_of_exception_handlers() - 1; i >= 0; i--) {
757 _work_list.append(cur->exception_handler_at(i));
758 }
759 }
760 } while (!_work_list.is_empty());
761 }
762
763
764 BlockBegin* ComputeLinearScanOrder::common_dominator(BlockBegin* a, BlockBegin* b) {
765 assert(a != NULL && b != NULL, "must have input blocks");
766
767 _dominator_blocks.clear();
768 while (a != NULL) {
769 _dominator_blocks.set_bit(a->block_id());
770 assert(a->dominator() != NULL || a == _linear_scan_order->at(0), "dominator must be initialized");
771 a = a->dominator();
772 }
773 while (b != NULL && !_dominator_blocks.at(b->block_id())) {
774 assert(b->dominator() != NULL || b == _linear_scan_order->at(0), "dominator must be initialized");
775 b = b->dominator();
776 }
777
778 assert(b != NULL, "could not find dominator");
779 return b;
780 }
781
782 void ComputeLinearScanOrder::compute_dominator(BlockBegin* cur, BlockBegin* parent) {
783 if (cur->dominator() == NULL) {
784 TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: initializing dominator of B%d to B%d", cur->block_id(), parent->block_id()));
785 cur->set_dominator(parent);
786
787 } else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) {
788 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()));
789 assert(cur->number_of_preds() > 1, "");
790 cur->set_dominator(common_dominator(cur->dominator(), parent));
791 }
792 }
793
794
795 int ComputeLinearScanOrder::compute_weight(BlockBegin* cur) {
796 BlockBegin* single_sux = NULL;
797 if (cur->number_of_sux() == 1) {
798 single_sux = cur->sux_at(0);
799 }
800
801 // limit loop-depth to 15 bit (only for security reason, it will never be so big)
802 int weight = (cur->loop_depth() & 0x7FFF) << 16;
803
804 // general macro for short definition of weight flags
805 // the first instance of INC_WEIGHT_IF has the highest priority
806 int cur_bit = 15;
807 #define INC_WEIGHT_IF(condition) if ((condition)) { weight |= (1 << cur_bit); } cur_bit--;
808
809 // this is necessery for the (very rare) case that two successing blocks have
810 // the same loop depth, but a different loop index (can happen for endless loops
811 // with exception handlers)
812 INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_header_flag));
813
814 // loop end blocks (blocks that end with a backward branch) are added
815 // after all other blocks of the loop.
816 INC_WEIGHT_IF(!cur->is_set(BlockBegin::linear_scan_loop_end_flag));
817
818 // critical edge split blocks are prefered because than they have a bigger
819 // proability to be completely empty
820 INC_WEIGHT_IF(cur->is_set(BlockBegin::critical_edge_split_flag));
821
822 // exceptions should not be thrown in normal control flow, so these blocks
823 // are added as late as possible
824 INC_WEIGHT_IF(cur->end()->as_Throw() == NULL && (single_sux == NULL || single_sux->end()->as_Throw() == NULL));
825 INC_WEIGHT_IF(cur->end()->as_Return() == NULL && (single_sux == NULL || single_sux->end()->as_Return() == NULL));
826
827 // exceptions handlers are added as late as possible
828 INC_WEIGHT_IF(!cur->is_set(BlockBegin::exception_entry_flag));
829
830 // guarantee that weight is > 0
831 weight |= 1;
832
833 #undef INC_WEIGHT_IF
834 assert(cur_bit >= 0, "too many flags");
835 assert(weight > 0, "weight cannot become negative");
836
837 return weight;
838 }
839
840 bool ComputeLinearScanOrder::ready_for_processing(BlockBegin* cur) {
841 // Discount the edge just traveled.
842 // When the number drops to zero, all forward branches were processed
843 if (dec_forward_branches(cur) != 0) {
844 return false;
845 }
846
847 assert(_linear_scan_order->index_of(cur) == -1, "block already processed (block can be ready only once)");
848 assert(_work_list.index_of(cur) == -1, "block already in work-list (block can be ready only once)");
849 return true;
850 }
851
852 void ComputeLinearScanOrder::sort_into_work_list(BlockBegin* cur) {
853 assert(_work_list.index_of(cur) == -1, "block already in work list");
854
855 int cur_weight = compute_weight(cur);
856
857 // the linear_scan_number is used to cache the weight of a block
858 cur->set_linear_scan_number(cur_weight);
859
860 #ifndef PRODUCT
861 if (StressLinearScan) {
862 _work_list.insert_before(0, cur);
863 return;
864 }
865 #endif
866
867 _work_list.append(NULL); // provide space for new element
868
869 int insert_idx = _work_list.length() - 1;
870 while (insert_idx > 0 && _work_list.at(insert_idx - 1)->linear_scan_number() > cur_weight) {
871 _work_list.at_put(insert_idx, _work_list.at(insert_idx - 1));
872 insert_idx--;
873 }
874 _work_list.at_put(insert_idx, cur);
875
876 TRACE_LINEAR_SCAN(3, tty->print_cr("Sorted B%d into worklist. new worklist:", cur->block_id()));
877 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()));
878
879 #ifdef ASSERT
880 for (int i = 0; i < _work_list.length(); i++) {
881 assert(_work_list.at(i)->linear_scan_number() > 0, "weight not set");
882 assert(i == 0 || _work_list.at(i - 1)->linear_scan_number() <= _work_list.at(i)->linear_scan_number(), "incorrect order in worklist");
883 }
884 #endif
885 }
886
887 void ComputeLinearScanOrder::append_block(BlockBegin* cur) {
888 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()));
889 assert(_linear_scan_order->index_of(cur) == -1, "cannot add the same block twice");
890
891 // currently, the linear scan order and code emit order are equal.
892 // therefore the linear_scan_number and the weight of a block must also
893 // be equal.
894 cur->set_linear_scan_number(_linear_scan_order->length());
895 _linear_scan_order->append(cur);
896 }
897
898 void ComputeLinearScanOrder::compute_order(BlockBegin* start_block) {
899 TRACE_LINEAR_SCAN(3, "----- computing final block order");
900
901 // the start block is always the first block in the linear scan order
902 _linear_scan_order = new BlockList(_num_blocks);
903 append_block(start_block);
904
905 assert(start_block->end()->as_Base() != NULL, "start block must end with Base-instruction");
906 BlockBegin* std_entry = ((Base*)start_block->end())->std_entry();
907 BlockBegin* osr_entry = ((Base*)start_block->end())->osr_entry();
908
909 BlockBegin* sux_of_osr_entry = NULL;
910 if (osr_entry != NULL) {
911 // special handling for osr entry:
912 // ignore the edge between the osr entry and its successor for processing
913 // the osr entry block is added manually below
914 assert(osr_entry->number_of_sux() == 1, "osr entry must have exactly one successor");
915 assert(osr_entry->sux_at(0)->number_of_preds() >= 2, "sucessor of osr entry must have two predecessors (otherwise it is not present in normal control flow");
916
917 sux_of_osr_entry = osr_entry->sux_at(0);
918 dec_forward_branches(sux_of_osr_entry);
919
920 compute_dominator(osr_entry, start_block);
921 _iterative_dominators = true;
922 }
923 compute_dominator(std_entry, start_block);
924
925 // start processing with standard entry block
926 assert(_work_list.is_empty(), "list must be empty before processing");
927
928 if (ready_for_processing(std_entry)) {
929 sort_into_work_list(std_entry);
930 } else {
931 assert(false, "the std_entry must be ready for processing (otherwise, the method has no start block)");
932 }
933
934 do {
935 BlockBegin* cur = _work_list.pop();
936
937 if (cur == sux_of_osr_entry) {
938 // the osr entry block is ignored in normal processing, it is never added to the
939 // work list. Instead, it is added as late as possible manually here.
940 append_block(osr_entry);
941 compute_dominator(cur, osr_entry);
942 }
943 append_block(cur);
944
945 int i;
946 int num_sux = cur->number_of_sux();
947 // changed loop order to get "intuitive" order of if- and else-blocks
948 for (i = 0; i < num_sux; i++) {
949 BlockBegin* sux = cur->sux_at(i);
950 compute_dominator(sux, cur);
951 if (ready_for_processing(sux)) {
952 sort_into_work_list(sux);
953 }
954 }
955 num_sux = cur->number_of_exception_handlers();
956 for (i = 0; i < num_sux; i++) {
957 BlockBegin* sux = cur->exception_handler_at(i);
958 compute_dominator(sux, cur);
959 if (ready_for_processing(sux)) {
960 sort_into_work_list(sux);
961 }
962 }
963 } while (_work_list.length() > 0);
964 }
965
966
967 bool ComputeLinearScanOrder::compute_dominators_iter() {
968 bool changed = false;
969 int num_blocks = _linear_scan_order->length();
970
971 assert(_linear_scan_order->at(0)->dominator() == NULL, "must not have dominator");
972 assert(_linear_scan_order->at(0)->number_of_preds() == 0, "must not have predecessors");
973 for (int i = 1; i < num_blocks; i++) {
974 BlockBegin* block = _linear_scan_order->at(i);
975
976 BlockBegin* dominator = block->pred_at(0);
977 int num_preds = block->number_of_preds();
978 for (int i = 1; i < num_preds; i++) {
979 dominator = common_dominator(dominator, block->pred_at(i));
980 }
981
982 if (dominator != block->dominator()) {
983 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()));
984
985 block->set_dominator(dominator);
986 changed = true;
987 }
988 }
989 return changed;
990 }
991
992 void ComputeLinearScanOrder::compute_dominators() {
993 TRACE_LINEAR_SCAN(3, tty->print_cr("----- computing dominators (iterative computation reqired: %d)", _iterative_dominators));
994
995 // iterative computation of dominators is only required for methods with non-natural loops
996 // and OSR-methods. For all other methods, the dominators computed when generating the
997 // linear scan block order are correct.
998 if (_iterative_dominators) {
999 do {
1000 TRACE_LINEAR_SCAN(1, tty->print_cr("DOM: next iteration of fix-point calculation"));
1001 } while (compute_dominators_iter());
1002 }
1003
1004 // check that dominators are correct
1005 assert(!compute_dominators_iter(), "fix point not reached");
1006 }
1007
1008
1009 #ifndef PRODUCT
1010 void ComputeLinearScanOrder::print_blocks() {
1011 if (TraceLinearScanLevel >= 2) {
1012 tty->print_cr("----- loop information:");
1013 for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
1014 BlockBegin* cur = _linear_scan_order->at(block_idx);
1015
1016 tty->print("%4d: B%2d: ", cur->linear_scan_number(), cur->block_id());
1017 for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
1018 tty->print ("%d ", is_block_in_loop(loop_idx, cur));
1019 }
1020 tty->print_cr(" -> loop_index: %2d, loop_depth: %2d", cur->loop_index(), cur->loop_depth());
1021 }
1022 }
1023
1024 if (TraceLinearScanLevel >= 1) {
1025 tty->print_cr("----- linear-scan block order:");
1026 for (int block_idx = 0; block_idx < _linear_scan_order->length(); block_idx++) {
1027 BlockBegin* cur = _linear_scan_order->at(block_idx);
1028 tty->print("%4d: B%2d loop: %2d depth: %2d", cur->linear_scan_number(), cur->block_id(), cur->loop_index(), cur->loop_depth());
1029
1030 tty->print(cur->is_set(BlockBegin::exception_entry_flag) ? " ex" : " ");
1031 tty->print(cur->is_set(BlockBegin::critical_edge_split_flag) ? " ce" : " ");
1032 tty->print(cur->is_set(BlockBegin::linear_scan_loop_header_flag) ? " lh" : " ");
1033 tty->print(cur->is_set(BlockBegin::linear_scan_loop_end_flag) ? " le" : " ");
1034
1035 if (cur->dominator() != NULL) {
1036 tty->print(" dom: B%d ", cur->dominator()->block_id());
1037 } else {
1038 tty->print(" dom: NULL ");
1039 }
1040
1041 if (cur->number_of_preds() > 0) {
1042 tty->print(" preds: ");
1043 for (int j = 0; j < cur->number_of_preds(); j++) {
1044 BlockBegin* pred = cur->pred_at(j);
1045 tty->print("B%d ", pred->block_id());
1046 }
1047 }
1048 if (cur->number_of_sux() > 0) {
1049 tty->print(" sux: ");
1050 for (int j = 0; j < cur->number_of_sux(); j++) {
1051 BlockBegin* sux = cur->sux_at(j);
1052 tty->print("B%d ", sux->block_id());
1053 }
1054 }
1055 if (cur->number_of_exception_handlers() > 0) {
1056 tty->print(" ex: ");
1057 for (int j = 0; j < cur->number_of_exception_handlers(); j++) {
1058 BlockBegin* ex = cur->exception_handler_at(j);
1059 tty->print("B%d ", ex->block_id());
1060 }
1061 }
1062 tty->cr();
1063 }
1064 }
1065 }
1066 #endif
1067
1068 #ifdef ASSERT
1069 void ComputeLinearScanOrder::verify() {
1070 assert(_linear_scan_order->length() == _num_blocks, "wrong number of blocks in list");
1071
1072 if (StressLinearScan) {
1073 // blocks are scrambled when StressLinearScan is used
1074 return;
1075 }
1076
1077 // check that all successors of a block have a higher linear-scan-number
1078 // and that all predecessors of a block have a lower linear-scan-number
1079 // (only backward branches of loops are ignored)
1080 int i;
1081 for (i = 0; i < _linear_scan_order->length(); i++) {
1082 BlockBegin* cur = _linear_scan_order->at(i);
1083
1084 assert(cur->linear_scan_number() == i, "incorrect linear_scan_number");
1085 assert(cur->linear_scan_number() >= 0 && cur->linear_scan_number() == _linear_scan_order->index_of(cur), "incorrect linear_scan_number");
1086
1087 int j;
1088 for (j = cur->number_of_sux() - 1; j >= 0; j--) {
1089 BlockBegin* sux = cur->sux_at(j);
1090
1091 assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number");
1092 if (!cur->is_set(BlockBegin::linear_scan_loop_end_flag)) {
1093 assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
1094 }
1095 if (cur->loop_depth() == sux->loop_depth()) {
1096 assert(cur->loop_index() == sux->loop_index() || sux->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index");
1097 }
1098 }
1099
1100 for (j = cur->number_of_preds() - 1; j >= 0; j--) {
1101 BlockBegin* pred = cur->pred_at(j);
1102
1103 assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number");
1104 if (!cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1105 assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
1106 }
1107 if (cur->loop_depth() == pred->loop_depth()) {
1108 assert(cur->loop_index() == pred->loop_index() || cur->is_set(BlockBegin::linear_scan_loop_header_flag), "successing blocks with same loop depth must have same loop index");
1109 }
1110
1111 assert(cur->dominator()->linear_scan_number() <= cur->pred_at(j)->linear_scan_number(), "dominator must be before predecessors");
1112 }
1113
1114 // check dominator
1115 if (i == 0) {
1116 assert(cur->dominator() == NULL, "first block has no dominator");
1117 } else {
1118 assert(cur->dominator() != NULL, "all but first block must have dominator");
1119 }
1120 assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0), "Single predecessor must also be dominator");
1121 }
1122
1123 // check that all loops are continuous
1124 for (int loop_idx = 0; loop_idx < _num_loops; loop_idx++) {
1125 int block_idx = 0;
1126 assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "the first block must not be present in any loop");
1127
1128 // skip blocks before the loop
1129 while (block_idx < _num_blocks && !is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
1130 block_idx++;
1131 }
1132 // skip blocks of loop
1133 while (block_idx < _num_blocks && is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx))) {
1134 block_idx++;
1135 }
1136 // after the first non-loop block, there must not be another loop-block
1137 while (block_idx < _num_blocks) {
1138 assert(!is_block_in_loop(loop_idx, _linear_scan_order->at(block_idx)), "loop not continuous in linear-scan order");
1139 block_idx++;
1140 }
1141 }
1142 }
1143 #endif
1144
1145
1146 void IR::compute_code() {
1147 assert(is_valid(), "IR must be valid");
1148
1149 ComputeLinearScanOrder compute_order(compilation(), start());
1150 _num_loops = compute_order.num_loops();
1151 _code = compute_order.linear_scan_order();
1152 }
1153
1154
1155 void IR::compute_use_counts() {
1156 // make sure all values coming out of this block get evaluated.
1157 int num_blocks = _code->length();
1158 for (int i = 0; i < num_blocks; i++) {
1159 _code->at(i)->end()->state()->pin_stack_for_linear_scan();
1160 }
1161
1162 // compute use counts
1163 UseCountComputer::compute(_code);
1164 }
1165
1166
1167 void IR::iterate_preorder(BlockClosure* closure) {
1168 assert(is_valid(), "IR must be valid");
1169 start()->iterate_preorder(closure);
1170 }
1171
1172
1173 void IR::iterate_postorder(BlockClosure* closure) {
1174 assert(is_valid(), "IR must be valid");
1175 start()->iterate_postorder(closure);
1176 }
1177
1178 void IR::iterate_linear_scan_order(BlockClosure* closure) {
1179 linear_scan_order()->iterate_forward(closure);
1180 }
1181
1182
1183 #ifndef PRODUCT
1184 class BlockPrinter: public BlockClosure {
1185 private:
1186 InstructionPrinter* _ip;
1187 bool _cfg_only;
1188 bool _live_only;
1189
1190 public:
1191 BlockPrinter(InstructionPrinter* ip, bool cfg_only, bool live_only = false) {
1192 _ip = ip;
1193 _cfg_only = cfg_only;
1194 _live_only = live_only;
1195 }
1196
1197 virtual void block_do(BlockBegin* block) {
1198 if (_cfg_only) {
1199 _ip->print_instr(block); tty->cr();
1200 } else {
1201 block->print_block(*_ip, _live_only);
1202 }
1203 }
1204 };
1205
1206
1207 void IR::print(BlockBegin* start, bool cfg_only, bool live_only) {
1208 ttyLocker ttyl;
1209 InstructionPrinter ip(!cfg_only);
1210 BlockPrinter bp(&ip, cfg_only, live_only);
1211 start->iterate_preorder(&bp);
1212 tty->cr();
1213 }
1214
1215 void IR::print(bool cfg_only, bool live_only) {
1216 if (is_valid()) {
1217 print(start(), cfg_only, live_only);
1218 } else {
1219 tty->print_cr("invalid IR");
1220 }
1221 }
1222
1223
1224 define_array(BlockListArray, BlockList*)
1225 define_stack(BlockListList, BlockListArray)
1226
1227 class PredecessorValidator : public BlockClosure {
1228 private:
1229 BlockListList* _predecessors;
1230 BlockList* _blocks;
1231
1232 static int cmp(BlockBegin** a, BlockBegin** b) {
1233 return (*a)->block_id() - (*b)->block_id();
1234 }
1235
1236 public:
1237 PredecessorValidator(IR* hir) {
1238 ResourceMark rm;
1239 _predecessors = new BlockListList(BlockBegin::number_of_blocks(), NULL);
1240 _blocks = new BlockList();
1241
1242 int i;
1243 hir->start()->iterate_preorder(this);
1244 if (hir->code() != NULL) {
1245 assert(hir->code()->length() == _blocks->length(), "must match");
1246 for (i = 0; i < _blocks->length(); i++) {
1247 assert(hir->code()->contains(_blocks->at(i)), "should be in both lists");
1248 }
1249 }
1250
1251 for (i = 0; i < _blocks->length(); i++) {
1252 BlockBegin* block = _blocks->at(i);
1253 BlockList* preds = _predecessors->at(block->block_id());
1254 if (preds == NULL) {
1255 assert(block->number_of_preds() == 0, "should be the same");
1256 continue;
1257 }
1258
1259 // clone the pred list so we can mutate it
1260 BlockList* pred_copy = new BlockList();
1261 int j;
1262 for (j = 0; j < block->number_of_preds(); j++) {
1263 pred_copy->append(block->pred_at(j));
1264 }
1265 // sort them in the same order
1266 preds->sort(cmp);
1267 pred_copy->sort(cmp);
1268 int length = MIN2(preds->length(), block->number_of_preds());
1269 for (j = 0; j < block->number_of_preds(); j++) {
1270 assert(preds->at(j) == pred_copy->at(j), "must match");
1271 }
1272
1273 assert(preds->length() == block->number_of_preds(), "should be the same");
1274 }
1275 }
1276
1277 virtual void block_do(BlockBegin* block) {
1278 _blocks->append(block);
1279 BlockEnd* be = block->end();
1280 int n = be->number_of_sux();
1281 int i;
1282 for (i = 0; i < n; i++) {
1283 BlockBegin* sux = be->sux_at(i);
1284 assert(!sux->is_set(BlockBegin::exception_entry_flag), "must not be xhandler");
1285
1286 BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL);
1287 if (preds == NULL) {
1288 preds = new BlockList();
1289 _predecessors->at_put(sux->block_id(), preds);
1290 }
1291 preds->append(block);
1292 }
1293
1294 n = block->number_of_exception_handlers();
1295 for (i = 0; i < n; i++) {
1296 BlockBegin* sux = block->exception_handler_at(i);
1297 assert(sux->is_set(BlockBegin::exception_entry_flag), "must be xhandler");
1298
1299 BlockList* preds = _predecessors->at_grow(sux->block_id(), NULL);
1300 if (preds == NULL) {
1301 preds = new BlockList();
1302 _predecessors->at_put(sux->block_id(), preds);
1303 }
1304 preds->append(block);
1305 }
1306 }
1307 };
1308
1309 void IR::verify() {
1310 #ifdef ASSERT
1311 PredecessorValidator pv(this);
1312 #endif
1313 }
1314
1315 #endif // PRODUCT
1316
1317 void SubstitutionResolver::visit(Value* v) {
1318 Value v0 = *v;
1319 if (v0) {
1320 Value vs = v0->subst();
1321 if (vs != v0) {
1322 *v = v0->subst();
1323 }
1324 }
1325 }
1326
1327 #ifdef ASSERT
1328 class SubstitutionChecker: public ValueVisitor {
1329 void visit(Value* v) {
1330 Value v0 = *v;
1331 if (v0) {
1332 Value vs = v0->subst();
1333 assert(vs == v0, "missed substitution");
1334 }
1335 }
1336 };
1337 #endif
1338
1339
1340 void SubstitutionResolver::block_do(BlockBegin* block) {
1341 Instruction* last = NULL;
1342 for (Instruction* n = block; n != NULL;) {
1343 n->values_do(this);
1344 // need to remove this instruction from the instruction stream
1345 if (n->subst() != n) {
1346 assert(last != NULL, "must have last");
1347 last->set_next(n->next(), n->next()->bci());
1348 } else {
1349 last = n;
1350 }
1351 n = last->next();
1352 }
1353
1354 #ifdef ASSERT
1355 SubstitutionChecker check_substitute;
1356 if (block->state()) block->state()->values_do(&check_substitute);
1357 block->block_values_do(&check_substitute);
1358 if (block->end() && block->end()->state()) block->end()->state()->values_do(&check_substitute);
1359 #endif
1360 }