1.1 --- a/src/share/vm/opto/parse1.cpp Wed Sep 17 08:29:17 2008 -0700
1.2 +++ b/src/share/vm/opto/parse1.cpp Wed Sep 17 12:59:52 2008 -0700
1.3 @@ -29,17 +29,17 @@
1.4 // the most. Some of the non-static variables are needed in bytecodeInfo.cpp
1.5 // and eventually should be encapsulated in a proper class (gri 8/18/98).
1.6
1.7 -int nodes_created = 0; int nodes_created_old = 0;
1.8 -int methods_parsed = 0; int methods_parsed_old = 0;
1.9 -int methods_seen = 0; int methods_seen_old = 0;
1.10 +int nodes_created = 0;
1.11 +int methods_parsed = 0;
1.12 +int methods_seen = 0;
1.13 +int blocks_parsed = 0;
1.14 +int blocks_seen = 0;
1.15
1.16 -int explicit_null_checks_inserted = 0, explicit_null_checks_inserted_old = 0;
1.17 -int explicit_null_checks_elided = 0, explicit_null_checks_elided_old = 0;
1.18 +int explicit_null_checks_inserted = 0;
1.19 +int explicit_null_checks_elided = 0;
1.20 int all_null_checks_found = 0, implicit_null_checks = 0;
1.21 int implicit_null_throws = 0;
1.22
1.23 -int parse_idx = 0;
1.24 -size_t parse_arena = 0;
1.25 int reclaim_idx = 0;
1.26 int reclaim_in = 0;
1.27 int reclaim_node = 0;
1.28 @@ -61,6 +61,7 @@
1.29 tty->cr();
1.30 if (methods_seen != methods_parsed)
1.31 tty->print_cr("Reasons for parse failures (NOT cumulative):");
1.32 + tty->print_cr("Blocks parsed: %d Blocks seen: %d", blocks_parsed, blocks_seen);
1.33
1.34 if( explicit_null_checks_inserted )
1.35 tty->print_cr("%d original NULL checks - %d elided (%2d%%); optimizer leaves %d,", explicit_null_checks_inserted, explicit_null_checks_elided, (100*explicit_null_checks_elided)/explicit_null_checks_inserted, all_null_checks_found);
1.36 @@ -373,6 +374,12 @@
1.37 C->record_method_not_compilable_all_tiers(_flow->failure_reason());
1.38 }
1.39
1.40 +#ifndef PRODUCT
1.41 + if (_flow->has_irreducible_entry()) {
1.42 + C->set_parsed_irreducible_loop(true);
1.43 + }
1.44 +#endif
1.45 +
1.46 if (_expected_uses <= 0) {
1.47 _prof_factor = 1;
1.48 } else {
1.49 @@ -556,118 +563,93 @@
1.50 set_map(entry_map);
1.51 do_exits();
1.52
1.53 - // Collect a few more statistics.
1.54 - parse_idx += C->unique();
1.55 - parse_arena += C->node_arena()->used();
1.56 -
1.57 if (log) log->done("parse nodes='%d' memory='%d'",
1.58 C->unique(), C->node_arena()->used());
1.59 }
1.60
1.61 //---------------------------do_all_blocks-------------------------------------
1.62 void Parse::do_all_blocks() {
1.63 - _blocks_merged = 0;
1.64 - _blocks_parsed = 0;
1.65 + bool has_irreducible = flow()->has_irreducible_entry();
1.66
1.67 - int old_blocks_merged = -1;
1.68 - int old_blocks_parsed = -1;
1.69 + // Walk over all blocks in Reverse Post-Order.
1.70 + while (true) {
1.71 + bool progress = false;
1.72 + for (int rpo = 0; rpo < block_count(); rpo++) {
1.73 + Block* block = rpo_at(rpo);
1.74
1.75 - for (int tries = 0; ; tries++) {
1.76 - visit_blocks();
1.77 - if (failing()) return; // Check for bailout
1.78 + if (block->is_parsed()) continue;
1.79
1.80 - // No need for a work list. The outer loop is hardly ever repeated.
1.81 - // The following loop traverses the blocks in a reasonable pre-order,
1.82 - // as produced by the ciTypeFlow pass.
1.83 + if (!block->is_merged()) {
1.84 + // Dead block, no state reaches this block
1.85 + continue;
1.86 + }
1.87
1.88 - // This loop can be taken more than once if there are two entries to
1.89 - // a loop (irreduceable CFG), and the edge which ciTypeFlow chose
1.90 - // as the first predecessor to the loop goes dead in the parser,
1.91 - // due to parse-time optimization. (Could happen with obfuscated code.)
1.92 + // Prepare to parse this block.
1.93 + load_state_from(block);
1.94
1.95 - // Look for progress, or the lack of it:
1.96 - if (_blocks_parsed == block_count()) {
1.97 - // That's all, folks.
1.98 - if (TraceOptoParse) {
1.99 - tty->print_cr("All blocks parsed.");
1.100 + if (stopped()) {
1.101 + // Block is dead.
1.102 + continue;
1.103 }
1.104 +
1.105 + blocks_parsed++;
1.106 +
1.107 + progress = true;
1.108 + if (block->is_loop_head() || block->is_handler() || has_irreducible && !block->is_ready()) {
1.109 + // Not all preds have been parsed. We must build phis everywhere.
1.110 + // (Note that dead locals do not get phis built, ever.)
1.111 + ensure_phis_everywhere();
1.112 +
1.113 + // Leave behind an undisturbed copy of the map, for future merges.
1.114 + set_map(clone_map());
1.115 + }
1.116 +
1.117 + if (control()->is_Region() && !block->is_loop_head() && !has_irreducible && !block->is_handler()) {
1.118 + // In the absence of irreducible loops, the Region and Phis
1.119 + // associated with a merge that doesn't involve a backedge can
1.120 + // be simplfied now since the RPO parsing order guarantees
1.121 + // that any path which was supposed to reach here has already
1.122 + // been parsed or must be dead.
1.123 + Node* c = control();
1.124 + Node* result = _gvn.transform_no_reclaim(control());
1.125 + if (c != result && TraceOptoParse) {
1.126 + tty->print_cr("Block #%d replace %d with %d", block->rpo(), c->_idx, result->_idx);
1.127 + }
1.128 + if (result != top()) {
1.129 + record_for_igvn(result);
1.130 + }
1.131 + }
1.132 +
1.133 + // Parse the block.
1.134 + do_one_block();
1.135 +
1.136 + // Check for bailouts.
1.137 + if (failing()) return;
1.138 + }
1.139 +
1.140 + // with irreducible loops multiple passes might be necessary to parse everything
1.141 + if (!has_irreducible || !progress) {
1.142 break;
1.143 }
1.144 + }
1.145
1.146 - // How much work was done this time around?
1.147 - int new_blocks_merged = _blocks_merged - old_blocks_merged;
1.148 - int new_blocks_parsed = _blocks_parsed - old_blocks_parsed;
1.149 - if (new_blocks_merged == 0) {
1.150 - if (TraceOptoParse) {
1.151 - tty->print_cr("All live blocks parsed; %d dead blocks.", block_count() - _blocks_parsed);
1.152 - }
1.153 - // No new blocks have become parseable. Some blocks are just dead.
1.154 - break;
1.155 - }
1.156 - assert(new_blocks_parsed > 0, "must make progress");
1.157 - assert(tries < block_count(), "the pre-order cannot be this bad!");
1.158 -
1.159 - old_blocks_merged = _blocks_merged;
1.160 - old_blocks_parsed = _blocks_parsed;
1.161 - }
1.162 + blocks_seen += block_count();
1.163
1.164 #ifndef PRODUCT
1.165 // Make sure there are no half-processed blocks remaining.
1.166 // Every remaining unprocessed block is dead and may be ignored now.
1.167 - for (int po = 0; po < block_count(); po++) {
1.168 - Block* block = pre_order_at(po);
1.169 + for (int rpo = 0; rpo < block_count(); rpo++) {
1.170 + Block* block = rpo_at(rpo);
1.171 if (!block->is_parsed()) {
1.172 if (TraceOptoParse) {
1.173 - tty->print("Skipped dead block %d at bci:%d", po, block->start());
1.174 - assert(!block->is_merged(), "no half-processed blocks");
1.175 + tty->print_cr("Skipped dead block %d at bci:%d", rpo, block->start());
1.176 }
1.177 + assert(!block->is_merged(), "no half-processed blocks");
1.178 }
1.179 }
1.180 #endif
1.181 }
1.182
1.183 -//---------------------------visit_blocks--------------------------------------
1.184 -void Parse::visit_blocks() {
1.185 - // Walk over all blocks, parsing every one that has been reached (merged).
1.186 - for (int po = 0; po < block_count(); po++) {
1.187 - Block* block = pre_order_at(po);
1.188 -
1.189 - if (block->is_parsed()) {
1.190 - // Do not parse twice.
1.191 - continue;
1.192 - }
1.193 -
1.194 - if (!block->is_merged()) {
1.195 - // No state on this block. It had not yet been reached.
1.196 - // Delay reaching it until later.
1.197 - continue;
1.198 - }
1.199 -
1.200 - // Prepare to parse this block.
1.201 - load_state_from(block);
1.202 -
1.203 - if (stopped()) {
1.204 - // Block is dead.
1.205 - continue;
1.206 - }
1.207 -
1.208 - if (!block->is_ready() || block->is_handler()) {
1.209 - // Not all preds have been parsed. We must build phis everywhere.
1.210 - // (Note that dead locals do not get phis built, ever.)
1.211 - ensure_phis_everywhere();
1.212 -
1.213 - // Leave behind an undisturbed copy of the map, for future merges.
1.214 - set_map(clone_map());
1.215 - }
1.216 -
1.217 - // Ready or not, parse the block.
1.218 - do_one_block();
1.219 -
1.220 - // Check for bailouts.
1.221 - if (failing()) return;
1.222 - }
1.223 -}
1.224 -
1.225 //-------------------------------build_exits----------------------------------
1.226 // Build normal and exceptional exit merge points.
1.227 void Parse::build_exits() {
1.228 @@ -1134,24 +1116,24 @@
1.229 _blocks = NEW_RESOURCE_ARRAY(Block, _block_count);
1.230 Copy::zero_to_bytes(_blocks, sizeof(Block)*_block_count);
1.231
1.232 - int po;
1.233 + int rpo;
1.234
1.235 // Initialize the structs.
1.236 - for (po = 0; po < block_count(); po++) {
1.237 - Block* block = pre_order_at(po);
1.238 - block->init_node(this, po);
1.239 + for (rpo = 0; rpo < block_count(); rpo++) {
1.240 + Block* block = rpo_at(rpo);
1.241 + block->init_node(this, rpo);
1.242 }
1.243
1.244 // Collect predecessor and successor information.
1.245 - for (po = 0; po < block_count(); po++) {
1.246 - Block* block = pre_order_at(po);
1.247 + for (rpo = 0; rpo < block_count(); rpo++) {
1.248 + Block* block = rpo_at(rpo);
1.249 block->init_graph(this);
1.250 }
1.251 }
1.252
1.253 //-------------------------------init_node-------------------------------------
1.254 -void Parse::Block::init_node(Parse* outer, int po) {
1.255 - _flow = outer->flow()->pre_order_at(po);
1.256 +void Parse::Block::init_node(Parse* outer, int rpo) {
1.257 + _flow = outer->flow()->rpo_at(rpo);
1.258 _pred_count = 0;
1.259 _preds_parsed = 0;
1.260 _count = 0;
1.261 @@ -1177,7 +1159,7 @@
1.262 int p = 0;
1.263 for (int i = 0; i < ns+ne; i++) {
1.264 ciTypeFlow::Block* tf2 = (i < ns) ? tfs->at(i) : tfe->at(i-ns);
1.265 - Block* block2 = outer->pre_order_at(tf2->pre_order());
1.266 + Block* block2 = outer->rpo_at(tf2->rpo());
1.267 _successors[i] = block2;
1.268
1.269 // Accumulate pred info for the other block, too.
1.270 @@ -1368,10 +1350,11 @@
1.271 int nt = b->all_successors();
1.272
1.273 tty->print("Parsing block #%d at bci [%d,%d), successors: ",
1.274 - block()->pre_order(), block()->start(), block()->limit());
1.275 + block()->rpo(), block()->start(), block()->limit());
1.276 for (int i = 0; i < nt; i++) {
1.277 - tty->print((( i < ns) ? " %d" : " %d(e)"), b->successor_at(i)->pre_order());
1.278 + tty->print((( i < ns) ? " %d" : " %d(e)"), b->successor_at(i)->rpo());
1.279 }
1.280 + if (b->is_loop_head()) tty->print(" lphd");
1.281 tty->print_cr("");
1.282 }
1.283
1.284 @@ -1501,7 +1484,7 @@
1.285 #ifndef PRODUCT
1.286 Block* b = block();
1.287 int trap_bci = b->flow()->has_trap()? b->flow()->trap_bci(): -1;
1.288 - tty->print_cr("### Missing successor at bci:%d for block #%d (trap_bci:%d)", target_bci, b->pre_order(), trap_bci);
1.289 + tty->print_cr("### Missing successor at bci:%d for block #%d (trap_bci:%d)", target_bci, b->rpo(), trap_bci);
1.290 #endif
1.291 ShouldNotReachHere();
1.292 }
1.293 @@ -1509,7 +1492,7 @@
1.294 //--------------------------merge_common---------------------------------------
1.295 void Parse::merge_common(Parse::Block* target, int pnum) {
1.296 if (TraceOptoParse) {
1.297 - tty->print("Merging state at block #%d bci:%d", target->pre_order(), target->start());
1.298 + tty->print("Merging state at block #%d bci:%d", target->rpo(), target->start());
1.299 }
1.300
1.301 // Zap extra stack slots to top
1.302 @@ -1534,6 +1517,7 @@
1.303 // which must not be allowed into this block's map.)
1.304 if (pnum > PhiNode::Input // Known multiple inputs.
1.305 || target->is_handler() // These have unpredictable inputs.
1.306 + || target->is_loop_head() // Known multiple inputs
1.307 || control()->is_Region()) { // We must hide this guy.
1.308 // Add a Region to start the new basic block. Phis will be added
1.309 // later lazily.
1.310 @@ -1575,15 +1559,21 @@
1.311
1.312 // Compute where to merge into
1.313 // Merge incoming control path
1.314 - r->set_req(pnum, newin->control());
1.315 + r->init_req(pnum, newin->control());
1.316
1.317 if (pnum == 1) { // Last merge for this Region?
1.318 - _gvn.transform_no_reclaim(r);
1.319 + if (!block()->flow()->is_irreducible_entry()) {
1.320 + Node* result = _gvn.transform_no_reclaim(r);
1.321 + if (r != result && TraceOptoParse) {
1.322 + tty->print_cr("Block #%d replace %d with %d", block()->rpo(), r->_idx, result->_idx);
1.323 + }
1.324 + }
1.325 record_for_igvn(r);
1.326 }
1.327
1.328 // Update all the non-control inputs to map:
1.329 assert(TypeFunc::Parms == newin->jvms()->locoff(), "parser map should contain only youngest jvms");
1.330 + bool check_elide_phi = target->is_SEL_backedge(save_block);
1.331 for (uint j = 1; j < newin->req(); j++) {
1.332 Node* m = map()->in(j); // Current state of target.
1.333 Node* n = newin->in(j); // Incoming change to target state.
1.334 @@ -1603,7 +1593,11 @@
1.335 merge_memory_edges(n->as_MergeMem(), pnum, nophi);
1.336 continue;
1.337 default: // All normal stuff
1.338 - if (phi == NULL) phi = ensure_phi(j, nophi);
1.339 + if (phi == NULL) {
1.340 + if (!check_elide_phi || !target->can_elide_SEL_phi(j)) {
1.341 + phi = ensure_phi(j, nophi);
1.342 + }
1.343 + }
1.344 break;
1.345 }
1.346 }
1.347 @@ -1736,9 +1730,13 @@
1.348 uint nof_monitors = map()->jvms()->nof_monitors();
1.349
1.350 assert(TypeFunc::Parms == map()->jvms()->locoff(), "parser map should contain only youngest jvms");
1.351 + bool check_elide_phi = block()->is_SEL_head();
1.352 for (uint i = TypeFunc::Parms; i < monoff; i++) {
1.353 - ensure_phi(i);
1.354 + if (!check_elide_phi || !block()->can_elide_SEL_phi(i)) {
1.355 + ensure_phi(i);
1.356 + }
1.357 }
1.358 +
1.359 // Even monitors need Phis, though they are well-structured.
1.360 // This is true for OSR methods, and also for the rare cases where
1.361 // a monitor object is the subject of a replace_in_map operation.
