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