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