1.1 --- a/src/share/vm/ci/ciTypeFlow.cpp Wed Sep 17 08:29:17 2008 -0700
1.2 +++ b/src/share/vm/ci/ciTypeFlow.cpp Wed Sep 17 12:59:52 2008 -0700
1.3 @@ -338,8 +338,10 @@
1.4 }
1.5 _trap_bci = -1;
1.6 _trap_index = 0;
1.7 + _def_locals.clear();
1.8 }
1.9
1.10 +
1.11 // ------------------------------------------------------------------
1.12 // ciTypeFlow::get_start_state
1.13 //
1.14 @@ -735,7 +737,7 @@
1.15 void ciTypeFlow::StateVector::do_new(ciBytecodeStream* str) {
1.16 bool will_link;
1.17 ciKlass* klass = str->get_klass(will_link);
1.18 - if (!will_link) {
1.19 + if (!will_link || str->is_unresolved_klass()) {
1.20 trap(str, klass, str->get_klass_index());
1.21 } else {
1.22 push_object(klass);
1.23 @@ -1268,7 +1270,9 @@
1.24 }
1.25 case Bytecodes::_iinc:
1.26 {
1.27 - check_int(local(str->get_index()));
1.28 + int lnum = str->get_index();
1.29 + check_int(local(lnum));
1.30 + store_to_local(lnum);
1.31 break;
1.32 }
1.33 case Bytecodes::_iload: load_local_int(str->get_index()); break;
1.34 @@ -1506,6 +1510,46 @@
1.35 }
1.36 #endif
1.37
1.38 +
1.39 +// ------------------------------------------------------------------
1.40 +// ciTypeFlow::SuccIter::next
1.41 +//
1.42 +void ciTypeFlow::SuccIter::next() {
1.43 + int succ_ct = _pred->successors()->length();
1.44 + int next = _index + 1;
1.45 + if (next < succ_ct) {
1.46 + _index = next;
1.47 + _succ = _pred->successors()->at(next);
1.48 + return;
1.49 + }
1.50 + for (int i = next - succ_ct; i < _pred->exceptions()->length(); i++) {
1.51 + // Do not compile any code for unloaded exception types.
1.52 + // Following compiler passes are responsible for doing this also.
1.53 + ciInstanceKlass* exception_klass = _pred->exc_klasses()->at(i);
1.54 + if (exception_klass->is_loaded()) {
1.55 + _index = next;
1.56 + _succ = _pred->exceptions()->at(i);
1.57 + return;
1.58 + }
1.59 + next++;
1.60 + }
1.61 + _index = -1;
1.62 + _succ = NULL;
1.63 +}
1.64 +
1.65 +// ------------------------------------------------------------------
1.66 +// ciTypeFlow::SuccIter::set_succ
1.67 +//
1.68 +void ciTypeFlow::SuccIter::set_succ(Block* succ) {
1.69 + int succ_ct = _pred->successors()->length();
1.70 + if (_index < succ_ct) {
1.71 + _pred->successors()->at_put(_index, succ);
1.72 + } else {
1.73 + int idx = _index - succ_ct;
1.74 + _pred->exceptions()->at_put(idx, succ);
1.75 + }
1.76 +}
1.77 +
1.78 // ciTypeFlow::Block
1.79 //
1.80 // A basic block.
1.81 @@ -1526,10 +1570,11 @@
1.82 _jsrs = new_jsrs;
1.83 _next = NULL;
1.84 _on_work_list = false;
1.85 - _pre_order = -1; assert(!has_pre_order(), "");
1.86 - _private_copy = false;
1.87 + _backedge_copy = false;
1.88 + _exception_entry = false;
1.89 _trap_bci = -1;
1.90 _trap_index = 0;
1.91 + df_init();
1.92
1.93 if (CITraceTypeFlow) {
1.94 tty->print_cr(">> Created new block");
1.95 @@ -1541,55 +1586,13 @@
1.96 }
1.97
1.98 // ------------------------------------------------------------------
1.99 -// ciTypeFlow::Block::clone_loop_head
1.100 -//
1.101 -ciTypeFlow::Block*
1.102 -ciTypeFlow::Block::clone_loop_head(ciTypeFlow* analyzer,
1.103 - int branch_bci,
1.104 - ciTypeFlow::Block* target,
1.105 - ciTypeFlow::JsrSet* jsrs) {
1.106 - // Loop optimizations are not performed on Tier1 compiles. Do nothing.
1.107 - if (analyzer->env()->comp_level() < CompLevel_full_optimization) {
1.108 - return target;
1.109 - }
1.110 -
1.111 - // The current block ends with a branch.
1.112 - //
1.113 - // If the target block appears to be the test-clause of a for loop, and
1.114 - // it is not too large, and it has not yet been cloned, clone it.
1.115 - // The pre-existing copy becomes the private clone used only by
1.116 - // the initial iteration of the loop. (We know we are simulating
1.117 - // the initial iteration right now, since we have never calculated
1.118 - // successors before for this block.)
1.119 -
1.120 - if (branch_bci <= start()
1.121 - && (target->limit() - target->start()) <= CICloneLoopTestLimit
1.122 - && target->private_copy_count() == 0) {
1.123 - // Setting the private_copy bit ensures that the target block cannot be
1.124 - // reached by any other paths, such as fall-in from the loop body.
1.125 - // The private copy will be accessible only on successor lists
1.126 - // created up to this point.
1.127 - target->set_private_copy(true);
1.128 - if (CITraceTypeFlow) {
1.129 - tty->print(">> Cloning a test-clause block ");
1.130 - print_value_on(tty);
1.131 - tty->cr();
1.132 - }
1.133 - // If the target is the current block, then later on a new copy of the
1.134 - // target block will be created when its bytecodes are reached by
1.135 - // an alternate path. (This is the case for loops with the loop
1.136 - // head at the bci-wise bottom of the loop, as with pre-1.4.2 javac.)
1.137 - //
1.138 - // Otherwise, duplicate the target block now and use it immediately.
1.139 - // (The case for loops with the loop head at the bci-wise top of the
1.140 - // loop, as with 1.4.2 javac.)
1.141 - //
1.142 - // In either case, the new copy of the block will remain public.
1.143 - if (target != this) {
1.144 - target = analyzer->block_at(branch_bci, jsrs);
1.145 - }
1.146 - }
1.147 - return target;
1.148 +// ciTypeFlow::Block::df_init
1.149 +void ciTypeFlow::Block::df_init() {
1.150 + _pre_order = -1; assert(!has_pre_order(), "");
1.151 + _post_order = -1; assert(!has_post_order(), "");
1.152 + _loop = NULL;
1.153 + _irreducible_entry = false;
1.154 + _rpo_next = NULL;
1.155 }
1.156
1.157 // ------------------------------------------------------------------
1.158 @@ -1644,7 +1647,6 @@
1.159 case Bytecodes::_ifnull: case Bytecodes::_ifnonnull:
1.160 // Our successors are the branch target and the next bci.
1.161 branch_bci = str->get_dest();
1.162 - clone_loop_head(analyzer, branch_bci, this, jsrs);
1.163 _successors =
1.164 new (arena) GrowableArray<Block*>(arena, 2, 0, NULL);
1.165 assert(_successors->length() == IF_NOT_TAKEN, "");
1.166 @@ -1658,14 +1660,7 @@
1.167 _successors =
1.168 new (arena) GrowableArray<Block*>(arena, 1, 0, NULL);
1.169 assert(_successors->length() == GOTO_TARGET, "");
1.170 - target = analyzer->block_at(branch_bci, jsrs);
1.171 - // If the target block has not been visited yet, and looks like
1.172 - // a two-way branch, attempt to clone it if it is a loop head.
1.173 - if (target->_successors != NULL
1.174 - && target->_successors->length() == (IF_TAKEN + 1)) {
1.175 - target = clone_loop_head(analyzer, branch_bci, target, jsrs);
1.176 - }
1.177 - _successors->append(target);
1.178 + _successors->append(analyzer->block_at(branch_bci, jsrs));
1.179 break;
1.180
1.181 case Bytecodes::_jsr:
1.182 @@ -1801,65 +1796,60 @@
1.183 }
1.184
1.185 // ------------------------------------------------------------------
1.186 -// ciTypeFlow::Block::is_simpler_than
1.187 -//
1.188 -// A relation used to order our work list. We work on a block earlier
1.189 -// if it has a smaller jsr stack or it occurs earlier in the program
1.190 -// text.
1.191 -//
1.192 -// Note: maybe we should redo this functionality to make blocks
1.193 -// which correspond to exceptions lower priority.
1.194 -bool ciTypeFlow::Block::is_simpler_than(ciTypeFlow::Block* other) {
1.195 - if (other == NULL) {
1.196 - return true;
1.197 - } else {
1.198 - int size1 = _jsrs->size();
1.199 - int size2 = other->_jsrs->size();
1.200 - if (size1 < size2) {
1.201 - return true;
1.202 - } else if (size2 < size1) {
1.203 - return false;
1.204 - } else {
1.205 -#if 0
1.206 - if (size1 > 0) {
1.207 - int r1 = _jsrs->record_at(0)->return_address();
1.208 - int r2 = _jsrs->record_at(0)->return_address();
1.209 - if (r1 < r2) {
1.210 - return true;
1.211 - } else if (r2 < r1) {
1.212 - return false;
1.213 - } else {
1.214 - int e1 = _jsrs->record_at(0)->return_address();
1.215 - int e2 = _jsrs->record_at(0)->return_address();
1.216 - if (e1 < e2) {
1.217 - return true;
1.218 - } else if (e2 < e1) {
1.219 - return false;
1.220 - }
1.221 - }
1.222 - }
1.223 -#endif
1.224 - return (start() <= other->start());
1.225 - }
1.226 - }
1.227 +// ciTypeFlow::Block::set_backedge_copy
1.228 +// Use this only to make a pre-existing public block into a backedge copy.
1.229 +void ciTypeFlow::Block::set_backedge_copy(bool z) {
1.230 + assert(z || (z == is_backedge_copy()), "cannot make a backedge copy public");
1.231 + _backedge_copy = z;
1.232 }
1.233
1.234 // ------------------------------------------------------------------
1.235 -// ciTypeFlow::Block::set_private_copy
1.236 -// Use this only to make a pre-existing public block into a private copy.
1.237 -void ciTypeFlow::Block::set_private_copy(bool z) {
1.238 - assert(z || (z == is_private_copy()), "cannot make a private copy public");
1.239 - _private_copy = z;
1.240 +// ciTypeFlow::Block::is_clonable_exit
1.241 +//
1.242 +// At most 2 normal successors, one of which continues looping,
1.243 +// and all exceptional successors must exit.
1.244 +bool ciTypeFlow::Block::is_clonable_exit(ciTypeFlow::Loop* lp) {
1.245 + int normal_cnt = 0;
1.246 + int in_loop_cnt = 0;
1.247 + for (SuccIter iter(this); !iter.done(); iter.next()) {
1.248 + Block* succ = iter.succ();
1.249 + if (iter.is_normal_ctrl()) {
1.250 + if (++normal_cnt > 2) return false;
1.251 + if (lp->contains(succ->loop())) {
1.252 + if (++in_loop_cnt > 1) return false;
1.253 + }
1.254 + } else {
1.255 + if (lp->contains(succ->loop())) return false;
1.256 + }
1.257 + }
1.258 + return in_loop_cnt == 1;
1.259 +}
1.260 +
1.261 +// ------------------------------------------------------------------
1.262 +// ciTypeFlow::Block::looping_succ
1.263 +//
1.264 +ciTypeFlow::Block* ciTypeFlow::Block::looping_succ(ciTypeFlow::Loop* lp) {
1.265 + assert(successors()->length() <= 2, "at most 2 normal successors");
1.266 + for (SuccIter iter(this); !iter.done(); iter.next()) {
1.267 + Block* succ = iter.succ();
1.268 + if (lp->contains(succ->loop())) {
1.269 + return succ;
1.270 + }
1.271 + }
1.272 + return NULL;
1.273 }
1.274
1.275 #ifndef PRODUCT
1.276 // ------------------------------------------------------------------
1.277 // ciTypeFlow::Block::print_value_on
1.278 void ciTypeFlow::Block::print_value_on(outputStream* st) const {
1.279 - if (has_pre_order()) st->print("#%-2d ", pre_order());
1.280 + if (has_pre_order()) st->print("#%-2d ", pre_order());
1.281 + if (has_rpo()) st->print("rpo#%-2d ", rpo());
1.282 st->print("[%d - %d)", start(), limit());
1.283 + if (is_loop_head()) st->print(" lphd");
1.284 + if (is_irreducible_entry()) st->print(" irred");
1.285 if (_jsrs->size() > 0) { st->print("/"); _jsrs->print_on(st); }
1.286 - if (is_private_copy()) st->print("/private_copy");
1.287 + if (is_backedge_copy()) st->print("/backedge_copy");
1.288 }
1.289
1.290 // ------------------------------------------------------------------
1.291 @@ -1871,6 +1861,16 @@
1.292 st->print_cr(" ==================================================== ");
1.293 st->print (" ");
1.294 print_value_on(st);
1.295 + st->print(" Stored locals: "); def_locals()->print_on(st, outer()->method()->max_locals()); tty->cr();
1.296 + if (loop() && loop()->parent() != NULL) {
1.297 + st->print(" loops:");
1.298 + Loop* lp = loop();
1.299 + do {
1.300 + st->print(" %d<-%d", lp->head()->pre_order(),lp->tail()->pre_order());
1.301 + if (lp->is_irreducible()) st->print("(ir)");
1.302 + lp = lp->parent();
1.303 + } while (lp->parent() != NULL);
1.304 + }
1.305 st->cr();
1.306 _state->print_on(st);
1.307 if (_successors == NULL) {
1.308 @@ -1907,6 +1907,21 @@
1.309 }
1.310 #endif
1.311
1.312 +#ifndef PRODUCT
1.313 +// ------------------------------------------------------------------
1.314 +// ciTypeFlow::LocalSet::print_on
1.315 +void ciTypeFlow::LocalSet::print_on(outputStream* st, int limit) const {
1.316 + st->print("{");
1.317 + for (int i = 0; i < max; i++) {
1.318 + if (test(i)) st->print(" %d", i);
1.319 + }
1.320 + if (limit > max) {
1.321 + st->print(" %d..%d ", max, limit);
1.322 + }
1.323 + st->print(" }");
1.324 +}
1.325 +#endif
1.326 +
1.327 // ciTypeFlow
1.328 //
1.329 // This is a pass over the bytecodes which computes the following:
1.330 @@ -1922,12 +1937,11 @@
1.331 _max_locals = method->max_locals();
1.332 _max_stack = method->max_stack();
1.333 _code_size = method->code_size();
1.334 + _has_irreducible_entry = false;
1.335 _osr_bci = osr_bci;
1.336 _failure_reason = NULL;
1.337 assert(start_bci() >= 0 && start_bci() < code_size() , "correct osr_bci argument");
1.338 -
1.339 _work_list = NULL;
1.340 - _next_pre_order = 0;
1.341
1.342 _ciblock_count = _methodBlocks->num_blocks();
1.343 _idx_to_blocklist = NEW_ARENA_ARRAY(arena(), GrowableArray<Block*>*, _ciblock_count);
1.344 @@ -1949,12 +1963,6 @@
1.345 _work_list = next_block->next();
1.346 next_block->set_next(NULL);
1.347 next_block->set_on_work_list(false);
1.348 - if (!next_block->has_pre_order()) {
1.349 - // Assign "pre_order" as each new block is taken from the work list.
1.350 - // This number may be used by following phases to order block visits.
1.351 - assert(!have_block_count(), "must not have mapped blocks yet")
1.352 - next_block->set_pre_order(_next_pre_order++);
1.353 - }
1.354 return next_block;
1.355 }
1.356
1.357 @@ -1962,30 +1970,37 @@
1.358 // ciTypeFlow::add_to_work_list
1.359 //
1.360 // Add a basic block to our work list.
1.361 +// List is sorted by decreasing postorder sort (same as increasing RPO)
1.362 void ciTypeFlow::add_to_work_list(ciTypeFlow::Block* block) {
1.363 assert(!block->is_on_work_list(), "must not already be on work list");
1.364
1.365 if (CITraceTypeFlow) {
1.366 - tty->print(">> Adding block%s ", block->has_pre_order() ? " (again)" : "");
1.367 + tty->print(">> Adding block ");
1.368 block->print_value_on(tty);
1.369 tty->print_cr(" to the work list : ");
1.370 }
1.371
1.372 block->set_on_work_list(true);
1.373 - if (block->is_simpler_than(_work_list)) {
1.374 +
1.375 + // decreasing post order sort
1.376 +
1.377 + Block* prev = NULL;
1.378 + Block* current = _work_list;
1.379 + int po = block->post_order();
1.380 + while (current != NULL) {
1.381 + if (!current->has_post_order() || po > current->post_order())
1.382 + break;
1.383 + prev = current;
1.384 + current = current->next();
1.385 + }
1.386 + if (prev == NULL) {
1.387 block->set_next(_work_list);
1.388 _work_list = block;
1.389 } else {
1.390 - Block *temp = _work_list;
1.391 - while (!block->is_simpler_than(temp->next())) {
1.392 - if (CITraceTypeFlow) {
1.393 - tty->print(".");
1.394 - }
1.395 - temp = temp->next();
1.396 - }
1.397 - block->set_next(temp->next());
1.398 - temp->set_next(block);
1.399 + block->set_next(current);
1.400 + prev->set_next(block);
1.401 }
1.402 +
1.403 if (CITraceTypeFlow) {
1.404 tty->cr();
1.405 }
1.406 @@ -2008,7 +2023,7 @@
1.407 assert(ciblk->start_bci() == bci, "bad ciBlock boundaries");
1.408 Block* block = get_block_for(ciblk->index(), jsrs, option);
1.409
1.410 - assert(block == NULL? (option == no_create): block->is_private_copy() == (option == create_private_copy), "create option consistent with result");
1.411 + assert(block == NULL? (option == no_create): block->is_backedge_copy() == (option == create_backedge_copy), "create option consistent with result");
1.412
1.413 if (CITraceTypeFlow) {
1.414 if (block != NULL) {
1.415 @@ -2072,8 +2087,9 @@
1.416 }
1.417
1.418 if (block->meet_exception(exception_klass, state)) {
1.419 - // Block was modified. Add it to the work list.
1.420 - if (!block->is_on_work_list()) {
1.421 + // Block was modified and has PO. Add it to the work list.
1.422 + if (block->has_post_order() &&
1.423 + !block->is_on_work_list()) {
1.424 add_to_work_list(block);
1.425 }
1.426 }
1.427 @@ -2091,8 +2107,9 @@
1.428 for (int i = 0; i < len; i++) {
1.429 Block* block = successors->at(i);
1.430 if (block->meet(state)) {
1.431 - // Block was modified. Add it to the work list.
1.432 - if (!block->is_on_work_list()) {
1.433 + // Block was modified and has PO. Add it to the work list.
1.434 + if (block->has_post_order() &&
1.435 + !block->is_on_work_list()) {
1.436 add_to_work_list(block);
1.437 }
1.438 }
1.439 @@ -2133,6 +2150,111 @@
1.440 return true;
1.441 }
1.442
1.443 +// ------------------------------------------------------------------
1.444 +// ciTypeFlow::clone_loop_heads
1.445 +//
1.446 +// Clone the loop heads
1.447 +bool ciTypeFlow::clone_loop_heads(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) {
1.448 + bool rslt = false;
1.449 + for (PreorderLoops iter(loop_tree_root()); !iter.done(); iter.next()) {
1.450 + lp = iter.current();
1.451 + Block* head = lp->head();
1.452 + if (lp == loop_tree_root() ||
1.453 + lp->is_irreducible() ||
1.454 + !head->is_clonable_exit(lp))
1.455 + continue;
1.456 +
1.457 + // check not already cloned
1.458 + if (head->backedge_copy_count() != 0)
1.459 + continue;
1.460 +
1.461 + // check _no_ shared head below us
1.462 + Loop* ch;
1.463 + for (ch = lp->child(); ch != NULL && ch->head() != head; ch = ch->sibling());
1.464 + if (ch != NULL)
1.465 + continue;
1.466 +
1.467 + // Clone head
1.468 + Block* new_head = head->looping_succ(lp);
1.469 + Block* clone = clone_loop_head(lp, temp_vector, temp_set);
1.470 + // Update lp's info
1.471 + clone->set_loop(lp);
1.472 + lp->set_head(new_head);
1.473 + lp->set_tail(clone);
1.474 + // And move original head into outer loop
1.475 + head->set_loop(lp->parent());
1.476 +
1.477 + rslt = true;
1.478 + }
1.479 + return rslt;
1.480 +}
1.481 +
1.482 +// ------------------------------------------------------------------
1.483 +// ciTypeFlow::clone_loop_head
1.484 +//
1.485 +// Clone lp's head and replace tail's successors with clone.
1.486 +//
1.487 +// |
1.488 +// v
1.489 +// head <-> body
1.490 +// |
1.491 +// v
1.492 +// exit
1.493 +//
1.494 +// new_head
1.495 +//
1.496 +// |
1.497 +// v
1.498 +// head ----------\
1.499 +// | |
1.500 +// | v
1.501 +// | clone <-> body
1.502 +// | |
1.503 +// | /--/
1.504 +// | |
1.505 +// v v
1.506 +// exit
1.507 +//
1.508 +ciTypeFlow::Block* ciTypeFlow::clone_loop_head(Loop* lp, StateVector* temp_vector, JsrSet* temp_set) {
1.509 + Block* head = lp->head();
1.510 + Block* tail = lp->tail();
1.511 + if (CITraceTypeFlow) {
1.512 + tty->print(">> Requesting clone of loop head "); head->print_value_on(tty);
1.513 + tty->print(" for predecessor "); tail->print_value_on(tty);
1.514 + tty->cr();
1.515 + }
1.516 + Block* clone = block_at(head->start(), head->jsrs(), create_backedge_copy);
1.517 + assert(clone->backedge_copy_count() == 1, "one backedge copy for all back edges");
1.518 +
1.519 + assert(!clone->has_pre_order(), "just created");
1.520 + clone->set_next_pre_order();
1.521 +
1.522 + // Insert clone after (orig) tail in reverse post order
1.523 + clone->set_rpo_next(tail->rpo_next());
1.524 + tail->set_rpo_next(clone);
1.525 +
1.526 + // tail->head becomes tail->clone
1.527 + for (SuccIter iter(tail); !iter.done(); iter.next()) {
1.528 + if (iter.succ() == head) {
1.529 + iter.set_succ(clone);
1.530 + break;
1.531 + }
1.532 + }
1.533 + flow_block(tail, temp_vector, temp_set);
1.534 + if (head == tail) {
1.535 + // For self-loops, clone->head becomes clone->clone
1.536 + flow_block(clone, temp_vector, temp_set);
1.537 + for (SuccIter iter(clone); !iter.done(); iter.next()) {
1.538 + if (iter.succ() == head) {
1.539 + iter.set_succ(clone);
1.540 + break;
1.541 + }
1.542 + }
1.543 + }
1.544 + flow_block(clone, temp_vector, temp_set);
1.545 +
1.546 + return clone;
1.547 +}
1.548
1.549 // ------------------------------------------------------------------
1.550 // ciTypeFlow::flow_block
1.551 @@ -2159,11 +2281,14 @@
1.552
1.553 // Grab the state from the current block.
1.554 block->copy_state_into(state);
1.555 + state->def_locals()->clear();
1.556
1.557 GrowableArray<Block*>* exceptions = block->exceptions();
1.558 GrowableArray<ciInstanceKlass*>* exc_klasses = block->exc_klasses();
1.559 bool has_exceptions = exceptions->length() > 0;
1.560
1.561 + bool exceptions_used = false;
1.562 +
1.563 ciBytecodeStream str(method());
1.564 str.reset_to_bci(start);
1.565 Bytecodes::Code code;
1.566 @@ -2172,6 +2297,7 @@
1.567 // Check for exceptional control flow from this point.
1.568 if (has_exceptions && can_trap(str)) {
1.569 flow_exceptions(exceptions, exc_klasses, state);
1.570 + exceptions_used = true;
1.571 }
1.572 // Apply the effects of the current bytecode to our state.
1.573 bool res = state->apply_one_bytecode(&str);
1.574 @@ -2189,9 +2315,14 @@
1.575 block->print_on(tty);
1.576 }
1.577
1.578 + // Save set of locals defined in this block
1.579 + block->def_locals()->add(state->def_locals());
1.580 +
1.581 // Record (no) successors.
1.582 block->successors(&str, state, jsrs);
1.583
1.584 + assert(!has_exceptions || exceptions_used, "Not removing exceptions");
1.585 +
1.586 // Discontinue interpretation of this Block.
1.587 return;
1.588 }
1.589 @@ -2202,6 +2333,7 @@
1.590 // Check for exceptional control flow from this point.
1.591 if (has_exceptions && can_trap(str)) {
1.592 flow_exceptions(exceptions, exc_klasses, state);
1.593 + exceptions_used = true;
1.594 }
1.595
1.596 // Fix the JsrSet to reflect effect of the bytecode.
1.597 @@ -2218,11 +2350,306 @@
1.598 successors = block->successors(&str, NULL, NULL);
1.599 }
1.600
1.601 + // Save set of locals defined in this block
1.602 + block->def_locals()->add(state->def_locals());
1.603 +
1.604 + // Remove untaken exception paths
1.605 + if (!exceptions_used)
1.606 + exceptions->clear();
1.607 +
1.608 // Pass our state to successors.
1.609 flow_successors(successors, state);
1.610 }
1.611
1.612 // ------------------------------------------------------------------
1.613 +// ciTypeFlow::PostOrderLoops::next
1.614 +//
1.615 +// Advance to next loop tree using a postorder, left-to-right traversal.
1.616 +void ciTypeFlow::PostorderLoops::next() {
1.617 + assert(!done(), "must not be done.");
1.618 + if (_current->sibling() != NULL) {
1.619 + _current = _current->sibling();
1.620 + while (_current->child() != NULL) {
1.621 + _current = _current->child();
1.622 + }
1.623 + } else {
1.624 + _current = _current->parent();
1.625 + }
1.626 +}
1.627 +
1.628 +// ------------------------------------------------------------------
1.629 +// ciTypeFlow::PreOrderLoops::next
1.630 +//
1.631 +// Advance to next loop tree using a preorder, left-to-right traversal.
1.632 +void ciTypeFlow::PreorderLoops::next() {
1.633 + assert(!done(), "must not be done.");
1.634 + if (_current->child() != NULL) {
1.635 + _current = _current->child();
1.636 + } else if (_current->sibling() != NULL) {
1.637 + _current = _current->sibling();
1.638 + } else {
1.639 + while (_current != _root && _current->sibling() == NULL) {
1.640 + _current = _current->parent();
1.641 + }
1.642 + if (_current == _root) {
1.643 + _current = NULL;
1.644 + assert(done(), "must be done.");
1.645 + } else {
1.646 + assert(_current->sibling() != NULL, "must be more to do");
1.647 + _current = _current->sibling();
1.648 + }
1.649 + }
1.650 +}
1.651 +
1.652 +// ------------------------------------------------------------------
1.653 +// ciTypeFlow::Loop::sorted_merge
1.654 +//
1.655 +// Merge the branch lp into this branch, sorting on the loop head
1.656 +// pre_orders. Returns the leaf of the merged branch.
1.657 +// Child and sibling pointers will be setup later.
1.658 +// Sort is (looking from leaf towards the root)
1.659 +// descending on primary key: loop head's pre_order, and
1.660 +// ascending on secondary key: loop tail's pre_order.
1.661 +ciTypeFlow::Loop* ciTypeFlow::Loop::sorted_merge(Loop* lp) {
1.662 + Loop* leaf = this;
1.663 + Loop* prev = NULL;
1.664 + Loop* current = leaf;
1.665 + while (lp != NULL) {
1.666 + int lp_pre_order = lp->head()->pre_order();
1.667 + // Find insertion point for "lp"
1.668 + while (current != NULL) {
1.669 + if (current == lp)
1.670 + return leaf; // Already in list
1.671 + if (current->head()->pre_order() < lp_pre_order)
1.672 + break;
1.673 + if (current->head()->pre_order() == lp_pre_order &&
1.674 + current->tail()->pre_order() > lp->tail()->pre_order()) {
1.675 + break;
1.676 + }
1.677 + prev = current;
1.678 + current = current->parent();
1.679 + }
1.680 + Loop* next_lp = lp->parent(); // Save future list of items to insert
1.681 + // Insert lp before current
1.682 + lp->set_parent(current);
1.683 + if (prev != NULL) {
1.684 + prev->set_parent(lp);
1.685 + } else {
1.686 + leaf = lp;
1.687 + }
1.688 + prev = lp; // Inserted item is new prev[ious]
1.689 + lp = next_lp; // Next item to insert
1.690 + }
1.691 + return leaf;
1.692 +}
1.693 +
1.694 +// ------------------------------------------------------------------
1.695 +// ciTypeFlow::build_loop_tree
1.696 +//
1.697 +// Incrementally build loop tree.
1.698 +void ciTypeFlow::build_loop_tree(Block* blk) {
1.699 + assert(!blk->is_post_visited(), "precondition");
1.700 + Loop* innermost = NULL; // merge of loop tree branches over all successors
1.701 +
1.702 + for (SuccIter iter(blk); !iter.done(); iter.next()) {
1.703 + Loop* lp = NULL;
1.704 + Block* succ = iter.succ();
1.705 + if (!succ->is_post_visited()) {
1.706 + // Found backedge since predecessor post visited, but successor is not
1.707 + assert(succ->pre_order() <= blk->pre_order(), "should be backedge");
1.708 +
1.709 + // Create a LoopNode to mark this loop.
1.710 + lp = new (arena()) Loop(succ, blk);
1.711 + if (succ->loop() == NULL)
1.712 + succ->set_loop(lp);
1.713 + // succ->loop will be updated to innermost loop on a later call, when blk==succ
1.714 +
1.715 + } else { // Nested loop
1.716 + lp = succ->loop();
1.717 +
1.718 + // If succ is loop head, find outer loop.
1.719 + while (lp != NULL && lp->head() == succ) {
1.720 + lp = lp->parent();
1.721 + }
1.722 + if (lp == NULL) {
1.723 + // Infinite loop, it's parent is the root
1.724 + lp = loop_tree_root();
1.725 + }
1.726 + }
1.727 +
1.728 + // Check for irreducible loop.
1.729 + // Successor has already been visited. If the successor's loop head
1.730 + // has already been post-visited, then this is another entry into the loop.
1.731 + while (lp->head()->is_post_visited() && lp != loop_tree_root()) {
1.732 + _has_irreducible_entry = true;
1.733 + lp->set_irreducible(succ);
1.734 + if (!succ->is_on_work_list()) {
1.735 + // Assume irreducible entries need more data flow
1.736 + add_to_work_list(succ);
1.737 + }
1.738 + lp = lp->parent();
1.739 + assert(lp != NULL, "nested loop must have parent by now");
1.740 + }
1.741 +
1.742 + // Merge loop tree branch for all successors.
1.743 + innermost = innermost == NULL ? lp : innermost->sorted_merge(lp);
1.744 +
1.745 + } // end loop
1.746 +
1.747 + if (innermost == NULL) {
1.748 + assert(blk->successors()->length() == 0, "CFG exit");
1.749 + blk->set_loop(loop_tree_root());
1.750 + } else if (innermost->head() == blk) {
1.751 + // If loop header, complete the tree pointers
1.752 + if (blk->loop() != innermost) {
1.753 +#if ASSERT
1.754 + assert(blk->loop()->head() == innermost->head(), "same head");
1.755 + Loop* dl;
1.756 + for (dl = innermost; dl != NULL && dl != blk->loop(); dl = dl->parent());
1.757 + assert(dl == blk->loop(), "blk->loop() already in innermost list");
1.758 +#endif
1.759 + blk->set_loop(innermost);
1.760 + }
1.761 + innermost->def_locals()->add(blk->def_locals());
1.762 + Loop* l = innermost;
1.763 + Loop* p = l->parent();
1.764 + while (p && l->head() == blk) {
1.765 + l->set_sibling(p->child()); // Put self on parents 'next child'
1.766 + p->set_child(l); // Make self the first child of parent
1.767 + p->def_locals()->add(l->def_locals());
1.768 + l = p; // Walk up the parent chain
1.769 + p = l->parent();
1.770 + }
1.771 + } else {
1.772 + blk->set_loop(innermost);
1.773 + innermost->def_locals()->add(blk->def_locals());
1.774 + }
1.775 +}
1.776 +
1.777 +// ------------------------------------------------------------------
1.778 +// ciTypeFlow::Loop::contains
1.779 +//
1.780 +// Returns true if lp is nested loop.
1.781 +bool ciTypeFlow::Loop::contains(ciTypeFlow::Loop* lp) const {
1.782 + assert(lp != NULL, "");
1.783 + if (this == lp || head() == lp->head()) return true;
1.784 + int depth1 = depth();
1.785 + int depth2 = lp->depth();
1.786 + if (depth1 > depth2)
1.787 + return false;
1.788 + while (depth1 < depth2) {
1.789 + depth2--;
1.790 + lp = lp->parent();
1.791 + }
1.792 + return this == lp;
1.793 +}
1.794 +
1.795 +// ------------------------------------------------------------------
1.796 +// ciTypeFlow::Loop::depth
1.797 +//
1.798 +// Loop depth
1.799 +int ciTypeFlow::Loop::depth() const {
1.800 + int dp = 0;
1.801 + for (Loop* lp = this->parent(); lp != NULL; lp = lp->parent())
1.802 + dp++;
1.803 + return dp;
1.804 +}
1.805 +
1.806 +#ifndef PRODUCT
1.807 +// ------------------------------------------------------------------
1.808 +// ciTypeFlow::Loop::print
1.809 +void ciTypeFlow::Loop::print(outputStream* st, int indent) const {
1.810 + for (int i = 0; i < indent; i++) st->print(" ");
1.811 + st->print("%d<-%d %s",
1.812 + is_root() ? 0 : this->head()->pre_order(),
1.813 + is_root() ? 0 : this->tail()->pre_order(),
1.814 + is_irreducible()?" irr":"");
1.815 + st->print(" defs: ");
1.816 + def_locals()->print_on(st, _head->outer()->method()->max_locals());
1.817 + st->cr();
1.818 + for (Loop* ch = child(); ch != NULL; ch = ch->sibling())
1.819 + ch->print(st, indent+2);
1.820 +}
1.821 +#endif
1.822 +
1.823 +// ------------------------------------------------------------------
1.824 +// ciTypeFlow::df_flow_types
1.825 +//
1.826 +// Perform the depth first type flow analysis. Helper for flow_types.
1.827 +void ciTypeFlow::df_flow_types(Block* start,
1.828 + bool do_flow,
1.829 + StateVector* temp_vector,
1.830 + JsrSet* temp_set) {
1.831 + int dft_len = 100;
1.832 + GrowableArray<Block*> stk(arena(), dft_len, 0, NULL);
1.833 +
1.834 + ciBlock* dummy = _methodBlocks->make_dummy_block();
1.835 + JsrSet* root_set = new JsrSet(NULL, 0);
1.836 + Block* root_head = new (arena()) Block(this, dummy, root_set);
1.837 + Block* root_tail = new (arena()) Block(this, dummy, root_set);
1.838 + root_head->set_pre_order(0);
1.839 + root_head->set_post_order(0);
1.840 + root_tail->set_pre_order(max_jint);
1.841 + root_tail->set_post_order(max_jint);
1.842 + set_loop_tree_root(new (arena()) Loop(root_head, root_tail));
1.843 +
1.844 + stk.push(start);
1.845 +
1.846 + _next_pre_order = 0; // initialize pre_order counter
1.847 + _rpo_list = NULL;
1.848 + int next_po = 0; // initialize post_order counter
1.849 +
1.850 + // Compute RPO and the control flow graph
1.851 + int size;
1.852 + while ((size = stk.length()) > 0) {
1.853 + Block* blk = stk.top(); // Leave node on stack
1.854 + if (!blk->is_visited()) {
1.855 + // forward arc in graph
1.856 + assert (!blk->has_pre_order(), "");
1.857 + blk->set_next_pre_order();
1.858 +
1.859 + if (_next_pre_order >= MaxNodeLimit / 2) {
1.860 + // Too many basic blocks. Bail out.
1.861 + // This can happen when try/finally constructs are nested to depth N,
1.862 + // and there is O(2**N) cloning of jsr bodies. See bug 4697245!
1.863 + // "MaxNodeLimit / 2" is used because probably the parser will
1.864 + // generate at least twice that many nodes and bail out.
1.865 + record_failure("too many basic blocks");
1.866 + return;
1.867 + }
1.868 + if (do_flow) {
1.869 + flow_block(blk, temp_vector, temp_set);
1.870 + if (failing()) return; // Watch for bailouts.
1.871 + }
1.872 + } else if (!blk->is_post_visited()) {
1.873 + // cross or back arc
1.874 + for (SuccIter iter(blk); !iter.done(); iter.next()) {
1.875 + Block* succ = iter.succ();
1.876 + if (!succ->is_visited()) {
1.877 + stk.push(succ);
1.878 + }
1.879 + }
1.880 + if (stk.length() == size) {
1.881 + // There were no additional children, post visit node now
1.882 + stk.pop(); // Remove node from stack
1.883 +
1.884 + build_loop_tree(blk);
1.885 + blk->set_post_order(next_po++); // Assign post order
1.886 + prepend_to_rpo_list(blk);
1.887 + assert(blk->is_post_visited(), "");
1.888 +
1.889 + if (blk->is_loop_head() && !blk->is_on_work_list()) {
1.890 + // Assume loop heads need more data flow
1.891 + add_to_work_list(blk);
1.892 + }
1.893 + }
1.894 + } else {
1.895 + stk.pop(); // Remove post-visited node from stack
1.896 + }
1.897 + }
1.898 +}
1.899 +
1.900 +// ------------------------------------------------------------------
1.901 // ciTypeFlow::flow_types
1.902 //
1.903 // Perform the type flow analysis, creating and cloning Blocks as
1.904 @@ -2233,91 +2660,93 @@
1.905 JsrSet* temp_set = new JsrSet(NULL, 16);
1.906
1.907 // Create the method entry block.
1.908 - Block* block = block_at(start_bci(), temp_set);
1.909 - block->set_pre_order(_next_pre_order++);
1.910 - assert(block->is_start(), "start block must have order #0");
1.911 + Block* start = block_at(start_bci(), temp_set);
1.912
1.913 // Load the initial state into it.
1.914 const StateVector* start_state = get_start_state();
1.915 if (failing()) return;
1.916 - block->meet(start_state);
1.917 - add_to_work_list(block);
1.918 + start->meet(start_state);
1.919
1.920 - // Trickle away.
1.921 + // Depth first visit
1.922 + df_flow_types(start, true /*do flow*/, temp_vector, temp_set);
1.923 +
1.924 + if (failing()) return;
1.925 + assert(_rpo_list == start, "must be start");
1.926 +
1.927 + // Any loops found?
1.928 + if (loop_tree_root()->child() != NULL &&
1.929 + env()->comp_level() >= CompLevel_full_optimization) {
1.930 + // Loop optimizations are not performed on Tier1 compiles.
1.931 +
1.932 + bool changed = clone_loop_heads(loop_tree_root(), temp_vector, temp_set);
1.933 +
1.934 + // If some loop heads were cloned, recompute postorder and loop tree
1.935 + if (changed) {
1.936 + loop_tree_root()->set_child(NULL);
1.937 + for (Block* blk = _rpo_list; blk != NULL;) {
1.938 + Block* next = blk->rpo_next();
1.939 + blk->df_init();
1.940 + blk = next;
1.941 + }
1.942 + df_flow_types(start, false /*no flow*/, temp_vector, temp_set);
1.943 + }
1.944 + }
1.945 +
1.946 + if (CITraceTypeFlow) {
1.947 + tty->print_cr("\nLoop tree");
1.948 + loop_tree_root()->print();
1.949 + }
1.950 +
1.951 + // Continue flow analysis until fixed point reached
1.952 +
1.953 + debug_only(int max_block = _next_pre_order;)
1.954 +
1.955 while (!work_list_empty()) {
1.956 - Block* block = work_list_next();
1.957 - flow_block(block, temp_vector, temp_set);
1.958 + Block* blk = work_list_next();
1.959 + assert (blk->has_post_order(), "post order assigned above");
1.960
1.961 + flow_block(blk, temp_vector, temp_set);
1.962
1.963 - // NodeCountCutoff is the number of nodes at which the parser
1.964 - // will bail out. Probably if we already have lots of BBs,
1.965 - // the parser will generate at least twice that many nodes and bail out.
1.966 - // Therefore, this is a conservatively large limit at which to
1.967 - // bail out in the pre-parse typeflow pass.
1.968 - int block_limit = MaxNodeLimit / 2;
1.969 -
1.970 - if (_next_pre_order >= block_limit) {
1.971 - // Too many basic blocks. Bail out.
1.972 - //
1.973 - // This can happen when try/finally constructs are nested to depth N,
1.974 - // and there is O(2**N) cloning of jsr bodies. See bug 4697245!
1.975 - record_failure("too many basic blocks");
1.976 - return;
1.977 - }
1.978 -
1.979 - // Watch for bailouts.
1.980 - if (failing()) return;
1.981 + assert (max_block == _next_pre_order, "no new blocks");
1.982 + assert (!failing(), "no more bailouts");
1.983 }
1.984 }
1.985
1.986 // ------------------------------------------------------------------
1.987 // ciTypeFlow::map_blocks
1.988 //
1.989 -// Create the block map, which indexes blocks in pre_order.
1.990 +// Create the block map, which indexes blocks in reverse post-order.
1.991 void ciTypeFlow::map_blocks() {
1.992 assert(_block_map == NULL, "single initialization");
1.993 - int pre_order_limit = _next_pre_order;
1.994 - _block_map = NEW_ARENA_ARRAY(arena(), Block*, pre_order_limit);
1.995 - assert(pre_order_limit == block_count(), "");
1.996 - int po;
1.997 - for (po = 0; po < pre_order_limit; po++) {
1.998 - debug_only(_block_map[po] = NULL);
1.999 + int block_ct = _next_pre_order;
1.1000 + _block_map = NEW_ARENA_ARRAY(arena(), Block*, block_ct);
1.1001 + assert(block_ct == block_count(), "");
1.1002 +
1.1003 + Block* blk = _rpo_list;
1.1004 + for (int m = 0; m < block_ct; m++) {
1.1005 + int rpo = blk->rpo();
1.1006 + assert(rpo == m, "should be sequential");
1.1007 + _block_map[rpo] = blk;
1.1008 + blk = blk->rpo_next();
1.1009 }
1.1010 - ciMethodBlocks *mblks = _methodBlocks;
1.1011 - ciBlock* current = NULL;
1.1012 - int limit_bci = code_size();
1.1013 - for (int bci = 0; bci < limit_bci; bci++) {
1.1014 - ciBlock* ciblk = mblks->block_containing(bci);
1.1015 - if (ciblk != NULL && ciblk != current) {
1.1016 - current = ciblk;
1.1017 - int curidx = ciblk->index();
1.1018 - int block_count = (_idx_to_blocklist[curidx] == NULL) ? 0 : _idx_to_blocklist[curidx]->length();
1.1019 - for (int i = 0; i < block_count; i++) {
1.1020 - Block* block = _idx_to_blocklist[curidx]->at(i);
1.1021 - if (!block->has_pre_order()) continue;
1.1022 - int po = block->pre_order();
1.1023 - assert(_block_map[po] == NULL, "unique ref to block");
1.1024 - assert(0 <= po && po < pre_order_limit, "");
1.1025 - _block_map[po] = block;
1.1026 - }
1.1027 - }
1.1028 - }
1.1029 - for (po = 0; po < pre_order_limit; po++) {
1.1030 - assert(_block_map[po] != NULL, "must not drop any blocks");
1.1031 - Block* block = _block_map[po];
1.1032 + assert(blk == NULL, "should be done");
1.1033 +
1.1034 + for (int j = 0; j < block_ct; j++) {
1.1035 + assert(_block_map[j] != NULL, "must not drop any blocks");
1.1036 + Block* block = _block_map[j];
1.1037 // Remove dead blocks from successor lists:
1.1038 for (int e = 0; e <= 1; e++) {
1.1039 GrowableArray<Block*>* l = e? block->exceptions(): block->successors();
1.1040 - for (int i = 0; i < l->length(); i++) {
1.1041 - Block* s = l->at(i);
1.1042 - if (!s->has_pre_order()) {
1.1043 + for (int k = 0; k < l->length(); k++) {
1.1044 + Block* s = l->at(k);
1.1045 + if (!s->has_post_order()) {
1.1046 if (CITraceTypeFlow) {
1.1047 tty->print("Removing dead %s successor of #%d: ", (e? "exceptional": "normal"), block->pre_order());
1.1048 s->print_value_on(tty);
1.1049 tty->cr();
1.1050 }
1.1051 l->remove(s);
1.1052 - --i;
1.1053 + --k;
1.1054 }
1.1055 }
1.1056 }
1.1057 @@ -2329,7 +2758,7 @@
1.1058 //
1.1059 // Find a block with this ciBlock which has a compatible JsrSet.
1.1060 // If no such block exists, create it, unless the option is no_create.
1.1061 -// If the option is create_private_copy, always create a fresh private copy.
1.1062 +// If the option is create_backedge_copy, always create a fresh backedge copy.
1.1063 ciTypeFlow::Block* ciTypeFlow::get_block_for(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs, CreateOption option) {
1.1064 Arena* a = arena();
1.1065 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
1.1066 @@ -2342,11 +2771,11 @@
1.1067 _idx_to_blocklist[ciBlockIndex] = blocks;
1.1068 }
1.1069
1.1070 - if (option != create_private_copy) {
1.1071 + if (option != create_backedge_copy) {
1.1072 int len = blocks->length();
1.1073 for (int i = 0; i < len; i++) {
1.1074 Block* block = blocks->at(i);
1.1075 - if (!block->is_private_copy() && block->is_compatible_with(jsrs)) {
1.1076 + if (!block->is_backedge_copy() && block->is_compatible_with(jsrs)) {
1.1077 return block;
1.1078 }
1.1079 }
1.1080 @@ -2357,15 +2786,15 @@
1.1081
1.1082 // We did not find a compatible block. Create one.
1.1083 Block* new_block = new (a) Block(this, _methodBlocks->block(ciBlockIndex), jsrs);
1.1084 - if (option == create_private_copy) new_block->set_private_copy(true);
1.1085 + if (option == create_backedge_copy) new_block->set_backedge_copy(true);
1.1086 blocks->append(new_block);
1.1087 return new_block;
1.1088 }
1.1089
1.1090 // ------------------------------------------------------------------
1.1091 -// ciTypeFlow::private_copy_count
1.1092 +// ciTypeFlow::backedge_copy_count
1.1093 //
1.1094 -int ciTypeFlow::private_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const {
1.1095 +int ciTypeFlow::backedge_copy_count(int ciBlockIndex, ciTypeFlow::JsrSet* jsrs) const {
1.1096 GrowableArray<Block*>* blocks = _idx_to_blocklist[ciBlockIndex];
1.1097
1.1098 if (blocks == NULL) {
1.1099 @@ -2376,7 +2805,7 @@
1.1100 int len = blocks->length();
1.1101 for (int i = 0; i < len; i++) {
1.1102 Block* block = blocks->at(i);
1.1103 - if (block->is_private_copy() && block->is_compatible_with(jsrs)) {
1.1104 + if (block->is_backedge_copy() && block->is_compatible_with(jsrs)) {
1.1105 count++;
1.1106 }
1.1107 }
1.1108 @@ -2405,10 +2834,12 @@
1.1109 if (failing()) {
1.1110 return;
1.1111 }
1.1112 +
1.1113 + map_blocks();
1.1114 +
1.1115 if (CIPrintTypeFlow || CITraceTypeFlow) {
1.1116 - print_on(tty);
1.1117 + rpo_print_on(tty);
1.1118 }
1.1119 - map_blocks();
1.1120 }
1.1121
1.1122 // ------------------------------------------------------------------
1.1123 @@ -2466,4 +2897,19 @@
1.1124 st->print_cr("********************************************************");
1.1125 st->cr();
1.1126 }
1.1127 +
1.1128 +void ciTypeFlow::rpo_print_on(outputStream* st) const {
1.1129 + st->print_cr("********************************************************");
1.1130 + st->print ("TypeFlow for ");
1.1131 + method()->name()->print_symbol_on(st);
1.1132 + int limit_bci = code_size();
1.1133 + st->print_cr(" %d bytes", limit_bci);
1.1134 + for (Block* blk = _rpo_list; blk != NULL; blk = blk->rpo_next()) {
1.1135 + blk->print_on(st);
1.1136 + st->print_cr("--------------------------------------------------------");
1.1137 + st->cr();
1.1138 + }
1.1139 + st->print_cr("********************************************************");
1.1140 + st->cr();
1.1141 +}
1.1142 #endif
