1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/lcm.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,934 @@
1.4 +/*
1.5 + * Copyright 1998-2007 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Optimization - Graph Style
1.29 +
1.30 +#include "incls/_precompiled.incl"
1.31 +#include "incls/_lcm.cpp.incl"
1.32 +
1.33 +//------------------------------implicit_null_check----------------------------
1.34 +// Detect implicit-null-check opportunities. Basically, find NULL checks
1.35 +// with suitable memory ops nearby. Use the memory op to do the NULL check.
1.36 +// I can generate a memory op if there is not one nearby.
1.37 +// The proj is the control projection for the not-null case.
1.38 +// The val is the pointer being checked for nullness.
1.39 +void Block::implicit_null_check(PhaseCFG *cfg, Node *proj, Node *val, int allowed_reasons) {
1.40 + // Assume if null check need for 0 offset then always needed
1.41 + // Intel solaris doesn't support any null checks yet and no
1.42 + // mechanism exists (yet) to set the switches at an os_cpu level
1.43 + if( !ImplicitNullChecks || MacroAssembler::needs_explicit_null_check(0)) return;
1.44 +
1.45 + // Make sure the ptr-is-null path appears to be uncommon!
1.46 + float f = end()->as_MachIf()->_prob;
1.47 + if( proj->Opcode() == Op_IfTrue ) f = 1.0f - f;
1.48 + if( f > PROB_UNLIKELY_MAG(4) ) return;
1.49 +
1.50 + uint bidx = 0; // Capture index of value into memop
1.51 + bool was_store; // Memory op is a store op
1.52 +
1.53 + // Get the successor block for if the test ptr is non-null
1.54 + Block* not_null_block; // this one goes with the proj
1.55 + Block* null_block;
1.56 + if (_nodes[_nodes.size()-1] == proj) {
1.57 + null_block = _succs[0];
1.58 + not_null_block = _succs[1];
1.59 + } else {
1.60 + assert(_nodes[_nodes.size()-2] == proj, "proj is one or the other");
1.61 + not_null_block = _succs[0];
1.62 + null_block = _succs[1];
1.63 + }
1.64 +
1.65 + // Search the exception block for an uncommon trap.
1.66 + // (See Parse::do_if and Parse::do_ifnull for the reason
1.67 + // we need an uncommon trap. Briefly, we need a way to
1.68 + // detect failure of this optimization, as in 6366351.)
1.69 + {
1.70 + bool found_trap = false;
1.71 + for (uint i1 = 0; i1 < null_block->_nodes.size(); i1++) {
1.72 + Node* nn = null_block->_nodes[i1];
1.73 + if (nn->is_MachCall() &&
1.74 + nn->as_MachCall()->entry_point() ==
1.75 + SharedRuntime::uncommon_trap_blob()->instructions_begin()) {
1.76 + const Type* trtype = nn->in(TypeFunc::Parms)->bottom_type();
1.77 + if (trtype->isa_int() && trtype->is_int()->is_con()) {
1.78 + jint tr_con = trtype->is_int()->get_con();
1.79 + Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(tr_con);
1.80 + Deoptimization::DeoptAction action = Deoptimization::trap_request_action(tr_con);
1.81 + assert((int)reason < (int)BitsPerInt, "recode bit map");
1.82 + if (is_set_nth_bit(allowed_reasons, (int) reason)
1.83 + && action != Deoptimization::Action_none) {
1.84 + // This uncommon trap is sure to recompile, eventually.
1.85 + // When that happens, C->too_many_traps will prevent
1.86 + // this transformation from happening again.
1.87 + found_trap = true;
1.88 + }
1.89 + }
1.90 + break;
1.91 + }
1.92 + }
1.93 + if (!found_trap) {
1.94 + // We did not find an uncommon trap.
1.95 + return;
1.96 + }
1.97 + }
1.98 +
1.99 + // Search the successor block for a load or store who's base value is also
1.100 + // the tested value. There may be several.
1.101 + Node_List *out = new Node_List(Thread::current()->resource_area());
1.102 + MachNode *best = NULL; // Best found so far
1.103 + for (DUIterator i = val->outs(); val->has_out(i); i++) {
1.104 + Node *m = val->out(i);
1.105 + if( !m->is_Mach() ) continue;
1.106 + MachNode *mach = m->as_Mach();
1.107 + was_store = false;
1.108 + switch( mach->ideal_Opcode() ) {
1.109 + case Op_LoadB:
1.110 + case Op_LoadC:
1.111 + case Op_LoadD:
1.112 + case Op_LoadF:
1.113 + case Op_LoadI:
1.114 + case Op_LoadL:
1.115 + case Op_LoadP:
1.116 + case Op_LoadS:
1.117 + case Op_LoadKlass:
1.118 + case Op_LoadRange:
1.119 + case Op_LoadD_unaligned:
1.120 + case Op_LoadL_unaligned:
1.121 + break;
1.122 + case Op_StoreB:
1.123 + case Op_StoreC:
1.124 + case Op_StoreCM:
1.125 + case Op_StoreD:
1.126 + case Op_StoreF:
1.127 + case Op_StoreI:
1.128 + case Op_StoreL:
1.129 + case Op_StoreP:
1.130 + was_store = true; // Memory op is a store op
1.131 + // Stores will have their address in slot 2 (memory in slot 1).
1.132 + // If the value being nul-checked is in another slot, it means we
1.133 + // are storing the checked value, which does NOT check the value!
1.134 + if( mach->in(2) != val ) continue;
1.135 + break; // Found a memory op?
1.136 + case Op_StrComp:
1.137 + // Not a legit memory op for implicit null check regardless of
1.138 + // embedded loads
1.139 + continue;
1.140 + default: // Also check for embedded loads
1.141 + if( !mach->needs_anti_dependence_check() )
1.142 + continue; // Not an memory op; skip it
1.143 + break;
1.144 + }
1.145 + // check if the offset is not too high for implicit exception
1.146 + {
1.147 + intptr_t offset = 0;
1.148 + const TypePtr *adr_type = NULL; // Do not need this return value here
1.149 + const Node* base = mach->get_base_and_disp(offset, adr_type);
1.150 + if (base == NULL || base == NodeSentinel) {
1.151 + // cannot reason about it; is probably not implicit null exception
1.152 + } else {
1.153 + const TypePtr* tptr = base->bottom_type()->is_ptr();
1.154 + // Give up if offset is not a compile-time constant
1.155 + if( offset == Type::OffsetBot || tptr->_offset == Type::OffsetBot )
1.156 + continue;
1.157 + offset += tptr->_offset; // correct if base is offseted
1.158 + if( MacroAssembler::needs_explicit_null_check(offset) )
1.159 + continue; // Give up is reference is beyond 4K page size
1.160 + }
1.161 + }
1.162 +
1.163 + // Check ctrl input to see if the null-check dominates the memory op
1.164 + Block *cb = cfg->_bbs[mach->_idx];
1.165 + cb = cb->_idom; // Always hoist at least 1 block
1.166 + if( !was_store ) { // Stores can be hoisted only one block
1.167 + while( cb->_dom_depth > (_dom_depth + 1))
1.168 + cb = cb->_idom; // Hoist loads as far as we want
1.169 + // The non-null-block should dominate the memory op, too. Live
1.170 + // range spilling will insert a spill in the non-null-block if it is
1.171 + // needs to spill the memory op for an implicit null check.
1.172 + if (cb->_dom_depth == (_dom_depth + 1)) {
1.173 + if (cb != not_null_block) continue;
1.174 + cb = cb->_idom;
1.175 + }
1.176 + }
1.177 + if( cb != this ) continue;
1.178 +
1.179 + // Found a memory user; see if it can be hoisted to check-block
1.180 + uint vidx = 0; // Capture index of value into memop
1.181 + uint j;
1.182 + for( j = mach->req()-1; j > 0; j-- ) {
1.183 + if( mach->in(j) == val ) vidx = j;
1.184 + // Block of memory-op input
1.185 + Block *inb = cfg->_bbs[mach->in(j)->_idx];
1.186 + Block *b = this; // Start from nul check
1.187 + while( b != inb && b->_dom_depth > inb->_dom_depth )
1.188 + b = b->_idom; // search upwards for input
1.189 + // See if input dominates null check
1.190 + if( b != inb )
1.191 + break;
1.192 + }
1.193 + if( j > 0 )
1.194 + continue;
1.195 + Block *mb = cfg->_bbs[mach->_idx];
1.196 + // Hoisting stores requires more checks for the anti-dependence case.
1.197 + // Give up hoisting if we have to move the store past any load.
1.198 + if( was_store ) {
1.199 + Block *b = mb; // Start searching here for a local load
1.200 + // mach use (faulting) trying to hoist
1.201 + // n might be blocker to hoisting
1.202 + while( b != this ) {
1.203 + uint k;
1.204 + for( k = 1; k < b->_nodes.size(); k++ ) {
1.205 + Node *n = b->_nodes[k];
1.206 + if( n->needs_anti_dependence_check() &&
1.207 + n->in(LoadNode::Memory) == mach->in(StoreNode::Memory) )
1.208 + break; // Found anti-dependent load
1.209 + }
1.210 + if( k < b->_nodes.size() )
1.211 + break; // Found anti-dependent load
1.212 + // Make sure control does not do a merge (would have to check allpaths)
1.213 + if( b->num_preds() != 2 ) break;
1.214 + b = cfg->_bbs[b->pred(1)->_idx]; // Move up to predecessor block
1.215 + }
1.216 + if( b != this ) continue;
1.217 + }
1.218 +
1.219 + // Make sure this memory op is not already being used for a NullCheck
1.220 + Node *e = mb->end();
1.221 + if( e->is_MachNullCheck() && e->in(1) == mach )
1.222 + continue; // Already being used as a NULL check
1.223 +
1.224 + // Found a candidate! Pick one with least dom depth - the highest
1.225 + // in the dom tree should be closest to the null check.
1.226 + if( !best ||
1.227 + cfg->_bbs[mach->_idx]->_dom_depth < cfg->_bbs[best->_idx]->_dom_depth ) {
1.228 + best = mach;
1.229 + bidx = vidx;
1.230 +
1.231 + }
1.232 + }
1.233 + // No candidate!
1.234 + if( !best ) return;
1.235 +
1.236 + // ---- Found an implicit null check
1.237 + extern int implicit_null_checks;
1.238 + implicit_null_checks++;
1.239 +
1.240 + // Hoist the memory candidate up to the end of the test block.
1.241 + Block *old_block = cfg->_bbs[best->_idx];
1.242 + old_block->find_remove(best);
1.243 + add_inst(best);
1.244 + cfg->_bbs.map(best->_idx,this);
1.245 +
1.246 + // Move the control dependence
1.247 + if (best->in(0) && best->in(0) == old_block->_nodes[0])
1.248 + best->set_req(0, _nodes[0]);
1.249 +
1.250 + // Check for flag-killing projections that also need to be hoisted
1.251 + // Should be DU safe because no edge updates.
1.252 + for (DUIterator_Fast jmax, j = best->fast_outs(jmax); j < jmax; j++) {
1.253 + Node* n = best->fast_out(j);
1.254 + if( n->Opcode() == Op_MachProj ) {
1.255 + cfg->_bbs[n->_idx]->find_remove(n);
1.256 + add_inst(n);
1.257 + cfg->_bbs.map(n->_idx,this);
1.258 + }
1.259 + }
1.260 +
1.261 + Compile *C = cfg->C;
1.262 + // proj==Op_True --> ne test; proj==Op_False --> eq test.
1.263 + // One of two graph shapes got matched:
1.264 + // (IfTrue (If (Bool NE (CmpP ptr NULL))))
1.265 + // (IfFalse (If (Bool EQ (CmpP ptr NULL))))
1.266 + // NULL checks are always branch-if-eq. If we see a IfTrue projection
1.267 + // then we are replacing a 'ne' test with a 'eq' NULL check test.
1.268 + // We need to flip the projections to keep the same semantics.
1.269 + if( proj->Opcode() == Op_IfTrue ) {
1.270 + // Swap order of projections in basic block to swap branch targets
1.271 + Node *tmp1 = _nodes[end_idx()+1];
1.272 + Node *tmp2 = _nodes[end_idx()+2];
1.273 + _nodes.map(end_idx()+1, tmp2);
1.274 + _nodes.map(end_idx()+2, tmp1);
1.275 + Node *tmp = new (C, 1) Node(C->top()); // Use not NULL input
1.276 + tmp1->replace_by(tmp);
1.277 + tmp2->replace_by(tmp1);
1.278 + tmp->replace_by(tmp2);
1.279 + tmp->destruct();
1.280 + }
1.281 +
1.282 + // Remove the existing null check; use a new implicit null check instead.
1.283 + // Since schedule-local needs precise def-use info, we need to correct
1.284 + // it as well.
1.285 + Node *old_tst = proj->in(0);
1.286 + MachNode *nul_chk = new (C) MachNullCheckNode(old_tst->in(0),best,bidx);
1.287 + _nodes.map(end_idx(),nul_chk);
1.288 + cfg->_bbs.map(nul_chk->_idx,this);
1.289 + // Redirect users of old_test to nul_chk
1.290 + for (DUIterator_Last i2min, i2 = old_tst->last_outs(i2min); i2 >= i2min; --i2)
1.291 + old_tst->last_out(i2)->set_req(0, nul_chk);
1.292 + // Clean-up any dead code
1.293 + for (uint i3 = 0; i3 < old_tst->req(); i3++)
1.294 + old_tst->set_req(i3, NULL);
1.295 +
1.296 + cfg->latency_from_uses(nul_chk);
1.297 + cfg->latency_from_uses(best);
1.298 +}
1.299 +
1.300 +
1.301 +//------------------------------select-----------------------------------------
1.302 +// Select a nice fellow from the worklist to schedule next. If there is only
1.303 +// one choice, then use it. Projections take top priority for correctness
1.304 +// reasons - if I see a projection, then it is next. There are a number of
1.305 +// other special cases, for instructions that consume condition codes, et al.
1.306 +// These are chosen immediately. Some instructions are required to immediately
1.307 +// precede the last instruction in the block, and these are taken last. Of the
1.308 +// remaining cases (most), choose the instruction with the greatest latency
1.309 +// (that is, the most number of pseudo-cycles required to the end of the
1.310 +// routine). If there is a tie, choose the instruction with the most inputs.
1.311 +Node *Block::select(PhaseCFG *cfg, Node_List &worklist, int *ready_cnt, VectorSet &next_call, uint sched_slot) {
1.312 +
1.313 + // If only a single entry on the stack, use it
1.314 + uint cnt = worklist.size();
1.315 + if (cnt == 1) {
1.316 + Node *n = worklist[0];
1.317 + worklist.map(0,worklist.pop());
1.318 + return n;
1.319 + }
1.320 +
1.321 + uint choice = 0; // Bigger is most important
1.322 + uint latency = 0; // Bigger is scheduled first
1.323 + uint score = 0; // Bigger is better
1.324 + uint idx; // Index in worklist
1.325 +
1.326 + for( uint i=0; i<cnt; i++ ) { // Inspect entire worklist
1.327 + // Order in worklist is used to break ties.
1.328 + // See caller for how this is used to delay scheduling
1.329 + // of induction variable increments to after the other
1.330 + // uses of the phi are scheduled.
1.331 + Node *n = worklist[i]; // Get Node on worklist
1.332 +
1.333 + int iop = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : 0;
1.334 + if( n->is_Proj() || // Projections always win
1.335 + n->Opcode()== Op_Con || // So does constant 'Top'
1.336 + iop == Op_CreateEx || // Create-exception must start block
1.337 + iop == Op_CheckCastPP
1.338 + ) {
1.339 + worklist.map(i,worklist.pop());
1.340 + return n;
1.341 + }
1.342 +
1.343 + // Final call in a block must be adjacent to 'catch'
1.344 + Node *e = end();
1.345 + if( e->is_Catch() && e->in(0)->in(0) == n )
1.346 + continue;
1.347 +
1.348 + // Memory op for an implicit null check has to be at the end of the block
1.349 + if( e->is_MachNullCheck() && e->in(1) == n )
1.350 + continue;
1.351 +
1.352 + uint n_choice = 2;
1.353 +
1.354 + // See if this instruction is consumed by a branch. If so, then (as the
1.355 + // branch is the last instruction in the basic block) force it to the
1.356 + // end of the basic block
1.357 + if ( must_clone[iop] ) {
1.358 + // See if any use is a branch
1.359 + bool found_machif = false;
1.360 +
1.361 + for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1.362 + Node* use = n->fast_out(j);
1.363 +
1.364 + // The use is a conditional branch, make them adjacent
1.365 + if (use->is_MachIf() && cfg->_bbs[use->_idx]==this ) {
1.366 + found_machif = true;
1.367 + break;
1.368 + }
1.369 +
1.370 + // More than this instruction pending for successor to be ready,
1.371 + // don't choose this if other opportunities are ready
1.372 + if (ready_cnt[use->_idx] > 1)
1.373 + n_choice = 1;
1.374 + }
1.375 +
1.376 + // loop terminated, prefer not to use this instruction
1.377 + if (found_machif)
1.378 + continue;
1.379 + }
1.380 +
1.381 + // See if this has a predecessor that is "must_clone", i.e. sets the
1.382 + // condition code. If so, choose this first
1.383 + for (uint j = 0; j < n->req() ; j++) {
1.384 + Node *inn = n->in(j);
1.385 + if (inn) {
1.386 + if (inn->is_Mach() && must_clone[inn->as_Mach()->ideal_Opcode()] ) {
1.387 + n_choice = 3;
1.388 + break;
1.389 + }
1.390 + }
1.391 + }
1.392 +
1.393 + // MachTemps should be scheduled last so they are near their uses
1.394 + if (n->is_MachTemp()) {
1.395 + n_choice = 1;
1.396 + }
1.397 +
1.398 + uint n_latency = cfg->_node_latency.at_grow(n->_idx);
1.399 + uint n_score = n->req(); // Many inputs get high score to break ties
1.400 +
1.401 + // Keep best latency found
1.402 + if( choice < n_choice ||
1.403 + ( choice == n_choice &&
1.404 + ( latency < n_latency ||
1.405 + ( latency == n_latency &&
1.406 + ( score < n_score ))))) {
1.407 + choice = n_choice;
1.408 + latency = n_latency;
1.409 + score = n_score;
1.410 + idx = i; // Also keep index in worklist
1.411 + }
1.412 + } // End of for all ready nodes in worklist
1.413 +
1.414 + Node *n = worklist[idx]; // Get the winner
1.415 +
1.416 + worklist.map(idx,worklist.pop()); // Compress worklist
1.417 + return n;
1.418 +}
1.419 +
1.420 +
1.421 +//------------------------------set_next_call----------------------------------
1.422 +void Block::set_next_call( Node *n, VectorSet &next_call, Block_Array &bbs ) {
1.423 + if( next_call.test_set(n->_idx) ) return;
1.424 + for( uint i=0; i<n->len(); i++ ) {
1.425 + Node *m = n->in(i);
1.426 + if( !m ) continue; // must see all nodes in block that precede call
1.427 + if( bbs[m->_idx] == this )
1.428 + set_next_call( m, next_call, bbs );
1.429 + }
1.430 +}
1.431 +
1.432 +//------------------------------needed_for_next_call---------------------------
1.433 +// Set the flag 'next_call' for each Node that is needed for the next call to
1.434 +// be scheduled. This flag lets me bias scheduling so Nodes needed for the
1.435 +// next subroutine call get priority - basically it moves things NOT needed
1.436 +// for the next call till after the call. This prevents me from trying to
1.437 +// carry lots of stuff live across a call.
1.438 +void Block::needed_for_next_call(Node *this_call, VectorSet &next_call, Block_Array &bbs) {
1.439 + // Find the next control-defining Node in this block
1.440 + Node* call = NULL;
1.441 + for (DUIterator_Fast imax, i = this_call->fast_outs(imax); i < imax; i++) {
1.442 + Node* m = this_call->fast_out(i);
1.443 + if( bbs[m->_idx] == this && // Local-block user
1.444 + m != this_call && // Not self-start node
1.445 + m->is_Call() )
1.446 + call = m;
1.447 + break;
1.448 + }
1.449 + if (call == NULL) return; // No next call (e.g., block end is near)
1.450 + // Set next-call for all inputs to this call
1.451 + set_next_call(call, next_call, bbs);
1.452 +}
1.453 +
1.454 +//------------------------------sched_call-------------------------------------
1.455 +uint Block::sched_call( Matcher &matcher, Block_Array &bbs, uint node_cnt, Node_List &worklist, int *ready_cnt, MachCallNode *mcall, VectorSet &next_call ) {
1.456 + RegMask regs;
1.457 +
1.458 + // Schedule all the users of the call right now. All the users are
1.459 + // projection Nodes, so they must be scheduled next to the call.
1.460 + // Collect all the defined registers.
1.461 + for (DUIterator_Fast imax, i = mcall->fast_outs(imax); i < imax; i++) {
1.462 + Node* n = mcall->fast_out(i);
1.463 + assert( n->Opcode()==Op_MachProj, "" );
1.464 + --ready_cnt[n->_idx];
1.465 + assert( !ready_cnt[n->_idx], "" );
1.466 + // Schedule next to call
1.467 + _nodes.map(node_cnt++, n);
1.468 + // Collect defined registers
1.469 + regs.OR(n->out_RegMask());
1.470 + // Check for scheduling the next control-definer
1.471 + if( n->bottom_type() == Type::CONTROL )
1.472 + // Warm up next pile of heuristic bits
1.473 + needed_for_next_call(n, next_call, bbs);
1.474 +
1.475 + // Children of projections are now all ready
1.476 + for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1.477 + Node* m = n->fast_out(j); // Get user
1.478 + if( bbs[m->_idx] != this ) continue;
1.479 + if( m->is_Phi() ) continue;
1.480 + if( !--ready_cnt[m->_idx] )
1.481 + worklist.push(m);
1.482 + }
1.483 +
1.484 + }
1.485 +
1.486 + // Act as if the call defines the Frame Pointer.
1.487 + // Certainly the FP is alive and well after the call.
1.488 + regs.Insert(matcher.c_frame_pointer());
1.489 +
1.490 + // Set all registers killed and not already defined by the call.
1.491 + uint r_cnt = mcall->tf()->range()->cnt();
1.492 + int op = mcall->ideal_Opcode();
1.493 + MachProjNode *proj = new (matcher.C, 1) MachProjNode( mcall, r_cnt+1, RegMask::Empty, MachProjNode::fat_proj );
1.494 + bbs.map(proj->_idx,this);
1.495 + _nodes.insert(node_cnt++, proj);
1.496 +
1.497 + // Select the right register save policy.
1.498 + const char * save_policy;
1.499 + switch (op) {
1.500 + case Op_CallRuntime:
1.501 + case Op_CallLeaf:
1.502 + case Op_CallLeafNoFP:
1.503 + // Calling C code so use C calling convention
1.504 + save_policy = matcher._c_reg_save_policy;
1.505 + break;
1.506 +
1.507 + case Op_CallStaticJava:
1.508 + case Op_CallDynamicJava:
1.509 + // Calling Java code so use Java calling convention
1.510 + save_policy = matcher._register_save_policy;
1.511 + break;
1.512 +
1.513 + default:
1.514 + ShouldNotReachHere();
1.515 + }
1.516 +
1.517 + // When using CallRuntime mark SOE registers as killed by the call
1.518 + // so values that could show up in the RegisterMap aren't live in a
1.519 + // callee saved register since the register wouldn't know where to
1.520 + // find them. CallLeaf and CallLeafNoFP are ok because they can't
1.521 + // have debug info on them. Strictly speaking this only needs to be
1.522 + // done for oops since idealreg2debugmask takes care of debug info
1.523 + // references but there no way to handle oops differently than other
1.524 + // pointers as far as the kill mask goes.
1.525 + bool exclude_soe = op == Op_CallRuntime;
1.526 +
1.527 + // Fill in the kill mask for the call
1.528 + for( OptoReg::Name r = OptoReg::Name(0); r < _last_Mach_Reg; r=OptoReg::add(r,1) ) {
1.529 + if( !regs.Member(r) ) { // Not already defined by the call
1.530 + // Save-on-call register?
1.531 + if ((save_policy[r] == 'C') ||
1.532 + (save_policy[r] == 'A') ||
1.533 + ((save_policy[r] == 'E') && exclude_soe)) {
1.534 + proj->_rout.Insert(r);
1.535 + }
1.536 + }
1.537 + }
1.538 +
1.539 + return node_cnt;
1.540 +}
1.541 +
1.542 +
1.543 +//------------------------------schedule_local---------------------------------
1.544 +// Topological sort within a block. Someday become a real scheduler.
1.545 +bool Block::schedule_local(PhaseCFG *cfg, Matcher &matcher, int *ready_cnt, VectorSet &next_call) {
1.546 + // Already "sorted" are the block start Node (as the first entry), and
1.547 + // the block-ending Node and any trailing control projections. We leave
1.548 + // these alone. PhiNodes and ParmNodes are made to follow the block start
1.549 + // Node. Everything else gets topo-sorted.
1.550 +
1.551 +#ifndef PRODUCT
1.552 + if (cfg->trace_opto_pipelining()) {
1.553 + tty->print_cr("# --- schedule_local B%d, before: ---", _pre_order);
1.554 + for (uint i = 0;i < _nodes.size();i++) {
1.555 + tty->print("# ");
1.556 + _nodes[i]->fast_dump();
1.557 + }
1.558 + tty->print_cr("#");
1.559 + }
1.560 +#endif
1.561 +
1.562 + // RootNode is already sorted
1.563 + if( _nodes.size() == 1 ) return true;
1.564 +
1.565 + // Move PhiNodes and ParmNodes from 1 to cnt up to the start
1.566 + uint node_cnt = end_idx();
1.567 + uint phi_cnt = 1;
1.568 + uint i;
1.569 + for( i = 1; i<node_cnt; i++ ) { // Scan for Phi
1.570 + Node *n = _nodes[i];
1.571 + if( n->is_Phi() || // Found a PhiNode or ParmNode
1.572 + (n->is_Proj() && n->in(0) == head()) ) {
1.573 + // Move guy at 'phi_cnt' to the end; makes a hole at phi_cnt
1.574 + _nodes.map(i,_nodes[phi_cnt]);
1.575 + _nodes.map(phi_cnt++,n); // swap Phi/Parm up front
1.576 + } else { // All others
1.577 + // Count block-local inputs to 'n'
1.578 + uint cnt = n->len(); // Input count
1.579 + uint local = 0;
1.580 + for( uint j=0; j<cnt; j++ ) {
1.581 + Node *m = n->in(j);
1.582 + if( m && cfg->_bbs[m->_idx] == this && !m->is_top() )
1.583 + local++; // One more block-local input
1.584 + }
1.585 + ready_cnt[n->_idx] = local; // Count em up
1.586 +
1.587 + // A few node types require changing a required edge to a precedence edge
1.588 + // before allocation.
1.589 + if( UseConcMarkSweepGC ) {
1.590 + if( n->is_Mach() && n->as_Mach()->ideal_Opcode() == Op_StoreCM ) {
1.591 + // Note: Required edges with an index greater than oper_input_base
1.592 + // are not supported by the allocator.
1.593 + // Note2: Can only depend on unmatched edge being last,
1.594 + // can not depend on its absolute position.
1.595 + Node *oop_store = n->in(n->req() - 1);
1.596 + n->del_req(n->req() - 1);
1.597 + n->add_prec(oop_store);
1.598 + assert(cfg->_bbs[oop_store->_idx]->_dom_depth <= this->_dom_depth, "oop_store must dominate card-mark");
1.599 + }
1.600 + }
1.601 + if( n->is_Mach() && n->as_Mach()->ideal_Opcode() == Op_MemBarAcquire ) {
1.602 + Node *x = n->in(TypeFunc::Parms);
1.603 + n->del_req(TypeFunc::Parms);
1.604 + n->add_prec(x);
1.605 + }
1.606 + }
1.607 + }
1.608 + for(uint i2=i; i2<_nodes.size(); i2++ ) // Trailing guys get zapped count
1.609 + ready_cnt[_nodes[i2]->_idx] = 0;
1.610 +
1.611 + // All the prescheduled guys do not hold back internal nodes
1.612 + uint i3;
1.613 + for(i3 = 0; i3<phi_cnt; i3++ ) { // For all pre-scheduled
1.614 + Node *n = _nodes[i3]; // Get pre-scheduled
1.615 + for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1.616 + Node* m = n->fast_out(j);
1.617 + if( cfg->_bbs[m->_idx] ==this ) // Local-block user
1.618 + ready_cnt[m->_idx]--; // Fix ready count
1.619 + }
1.620 + }
1.621 +
1.622 + Node_List delay;
1.623 + // Make a worklist
1.624 + Node_List worklist;
1.625 + for(uint i4=i3; i4<node_cnt; i4++ ) { // Put ready guys on worklist
1.626 + Node *m = _nodes[i4];
1.627 + if( !ready_cnt[m->_idx] ) { // Zero ready count?
1.628 + if (m->is_iteratively_computed()) {
1.629 + // Push induction variable increments last to allow other uses
1.630 + // of the phi to be scheduled first. The select() method breaks
1.631 + // ties in scheduling by worklist order.
1.632 + delay.push(m);
1.633 + } else {
1.634 + worklist.push(m); // Then on to worklist!
1.635 + }
1.636 + }
1.637 + }
1.638 + while (delay.size()) {
1.639 + Node* d = delay.pop();
1.640 + worklist.push(d);
1.641 + }
1.642 +
1.643 + // Warm up the 'next_call' heuristic bits
1.644 + needed_for_next_call(_nodes[0], next_call, cfg->_bbs);
1.645 +
1.646 +#ifndef PRODUCT
1.647 + if (cfg->trace_opto_pipelining()) {
1.648 + for (uint j=0; j<_nodes.size(); j++) {
1.649 + Node *n = _nodes[j];
1.650 + int idx = n->_idx;
1.651 + tty->print("# ready cnt:%3d ", ready_cnt[idx]);
1.652 + tty->print("latency:%3d ", cfg->_node_latency.at_grow(idx));
1.653 + tty->print("%4d: %s\n", idx, n->Name());
1.654 + }
1.655 + }
1.656 +#endif
1.657 +
1.658 + // Pull from worklist and schedule
1.659 + while( worklist.size() ) { // Worklist is not ready
1.660 +
1.661 +#ifndef PRODUCT
1.662 + if (cfg->trace_opto_pipelining()) {
1.663 + tty->print("# ready list:");
1.664 + for( uint i=0; i<worklist.size(); i++ ) { // Inspect entire worklist
1.665 + Node *n = worklist[i]; // Get Node on worklist
1.666 + tty->print(" %d", n->_idx);
1.667 + }
1.668 + tty->cr();
1.669 + }
1.670 +#endif
1.671 +
1.672 + // Select and pop a ready guy from worklist
1.673 + Node* n = select(cfg, worklist, ready_cnt, next_call, phi_cnt);
1.674 + _nodes.map(phi_cnt++,n); // Schedule him next
1.675 +
1.676 +#ifndef PRODUCT
1.677 + if (cfg->trace_opto_pipelining()) {
1.678 + tty->print("# select %d: %s", n->_idx, n->Name());
1.679 + tty->print(", latency:%d", cfg->_node_latency.at_grow(n->_idx));
1.680 + n->dump();
1.681 + if (Verbose) {
1.682 + tty->print("# ready list:");
1.683 + for( uint i=0; i<worklist.size(); i++ ) { // Inspect entire worklist
1.684 + Node *n = worklist[i]; // Get Node on worklist
1.685 + tty->print(" %d", n->_idx);
1.686 + }
1.687 + tty->cr();
1.688 + }
1.689 + }
1.690 +
1.691 +#endif
1.692 + if( n->is_MachCall() ) {
1.693 + MachCallNode *mcall = n->as_MachCall();
1.694 + phi_cnt = sched_call(matcher, cfg->_bbs, phi_cnt, worklist, ready_cnt, mcall, next_call);
1.695 + continue;
1.696 + }
1.697 + // Children are now all ready
1.698 + for (DUIterator_Fast i5max, i5 = n->fast_outs(i5max); i5 < i5max; i5++) {
1.699 + Node* m = n->fast_out(i5); // Get user
1.700 + if( cfg->_bbs[m->_idx] != this ) continue;
1.701 + if( m->is_Phi() ) continue;
1.702 + if( !--ready_cnt[m->_idx] )
1.703 + worklist.push(m);
1.704 + }
1.705 + }
1.706 +
1.707 + if( phi_cnt != end_idx() ) {
1.708 + // did not schedule all. Retry, Bailout, or Die
1.709 + Compile* C = matcher.C;
1.710 + if (C->subsume_loads() == true && !C->failing()) {
1.711 + // Retry with subsume_loads == false
1.712 + // If this is the first failure, the sentinel string will "stick"
1.713 + // to the Compile object, and the C2Compiler will see it and retry.
1.714 + C->record_failure(C2Compiler::retry_no_subsuming_loads());
1.715 + }
1.716 + // assert( phi_cnt == end_idx(), "did not schedule all" );
1.717 + return false;
1.718 + }
1.719 +
1.720 +#ifndef PRODUCT
1.721 + if (cfg->trace_opto_pipelining()) {
1.722 + tty->print_cr("#");
1.723 + tty->print_cr("# after schedule_local");
1.724 + for (uint i = 0;i < _nodes.size();i++) {
1.725 + tty->print("# ");
1.726 + _nodes[i]->fast_dump();
1.727 + }
1.728 + tty->cr();
1.729 + }
1.730 +#endif
1.731 +
1.732 +
1.733 + return true;
1.734 +}
1.735 +
1.736 +//--------------------------catch_cleanup_fix_all_inputs-----------------------
1.737 +static void catch_cleanup_fix_all_inputs(Node *use, Node *old_def, Node *new_def) {
1.738 + for (uint l = 0; l < use->len(); l++) {
1.739 + if (use->in(l) == old_def) {
1.740 + if (l < use->req()) {
1.741 + use->set_req(l, new_def);
1.742 + } else {
1.743 + use->rm_prec(l);
1.744 + use->add_prec(new_def);
1.745 + l--;
1.746 + }
1.747 + }
1.748 + }
1.749 +}
1.750 +
1.751 +//------------------------------catch_cleanup_find_cloned_def------------------
1.752 +static Node *catch_cleanup_find_cloned_def(Block *use_blk, Node *def, Block *def_blk, Block_Array &bbs, int n_clone_idx) {
1.753 + assert( use_blk != def_blk, "Inter-block cleanup only");
1.754 +
1.755 + // The use is some block below the Catch. Find and return the clone of the def
1.756 + // that dominates the use. If there is no clone in a dominating block, then
1.757 + // create a phi for the def in a dominating block.
1.758 +
1.759 + // Find which successor block dominates this use. The successor
1.760 + // blocks must all be single-entry (from the Catch only; I will have
1.761 + // split blocks to make this so), hence they all dominate.
1.762 + while( use_blk->_dom_depth > def_blk->_dom_depth+1 )
1.763 + use_blk = use_blk->_idom;
1.764 +
1.765 + // Find the successor
1.766 + Node *fixup = NULL;
1.767 +
1.768 + uint j;
1.769 + for( j = 0; j < def_blk->_num_succs; j++ )
1.770 + if( use_blk == def_blk->_succs[j] )
1.771 + break;
1.772 +
1.773 + if( j == def_blk->_num_succs ) {
1.774 + // Block at same level in dom-tree is not a successor. It needs a
1.775 + // PhiNode, the PhiNode uses from the def and IT's uses need fixup.
1.776 + Node_Array inputs = new Node_List(Thread::current()->resource_area());
1.777 + for(uint k = 1; k < use_blk->num_preds(); k++) {
1.778 + inputs.map(k, catch_cleanup_find_cloned_def(bbs[use_blk->pred(k)->_idx], def, def_blk, bbs, n_clone_idx));
1.779 + }
1.780 +
1.781 + // Check to see if the use_blk already has an identical phi inserted.
1.782 + // If it exists, it will be at the first position since all uses of a
1.783 + // def are processed together.
1.784 + Node *phi = use_blk->_nodes[1];
1.785 + if( phi->is_Phi() ) {
1.786 + fixup = phi;
1.787 + for (uint k = 1; k < use_blk->num_preds(); k++) {
1.788 + if (phi->in(k) != inputs[k]) {
1.789 + // Not a match
1.790 + fixup = NULL;
1.791 + break;
1.792 + }
1.793 + }
1.794 + }
1.795 +
1.796 + // If an existing PhiNode was not found, make a new one.
1.797 + if (fixup == NULL) {
1.798 + Node *new_phi = PhiNode::make(use_blk->head(), def);
1.799 + use_blk->_nodes.insert(1, new_phi);
1.800 + bbs.map(new_phi->_idx, use_blk);
1.801 + for (uint k = 1; k < use_blk->num_preds(); k++) {
1.802 + new_phi->set_req(k, inputs[k]);
1.803 + }
1.804 + fixup = new_phi;
1.805 + }
1.806 +
1.807 + } else {
1.808 + // Found the use just below the Catch. Make it use the clone.
1.809 + fixup = use_blk->_nodes[n_clone_idx];
1.810 + }
1.811 +
1.812 + return fixup;
1.813 +}
1.814 +
1.815 +//--------------------------catch_cleanup_intra_block--------------------------
1.816 +// Fix all input edges in use that reference "def". The use is in the same
1.817 +// block as the def and both have been cloned in each successor block.
1.818 +static void catch_cleanup_intra_block(Node *use, Node *def, Block *blk, int beg, int n_clone_idx) {
1.819 +
1.820 + // Both the use and def have been cloned. For each successor block,
1.821 + // get the clone of the use, and make its input the clone of the def
1.822 + // found in that block.
1.823 +
1.824 + uint use_idx = blk->find_node(use);
1.825 + uint offset_idx = use_idx - beg;
1.826 + for( uint k = 0; k < blk->_num_succs; k++ ) {
1.827 + // Get clone in each successor block
1.828 + Block *sb = blk->_succs[k];
1.829 + Node *clone = sb->_nodes[offset_idx+1];
1.830 + assert( clone->Opcode() == use->Opcode(), "" );
1.831 +
1.832 + // Make use-clone reference the def-clone
1.833 + catch_cleanup_fix_all_inputs(clone, def, sb->_nodes[n_clone_idx]);
1.834 + }
1.835 +}
1.836 +
1.837 +//------------------------------catch_cleanup_inter_block---------------------
1.838 +// Fix all input edges in use that reference "def". The use is in a different
1.839 +// block than the def.
1.840 +static void catch_cleanup_inter_block(Node *use, Block *use_blk, Node *def, Block *def_blk, Block_Array &bbs, int n_clone_idx) {
1.841 + if( !use_blk ) return; // Can happen if the use is a precedence edge
1.842 +
1.843 + Node *new_def = catch_cleanup_find_cloned_def(use_blk, def, def_blk, bbs, n_clone_idx);
1.844 + catch_cleanup_fix_all_inputs(use, def, new_def);
1.845 +}
1.846 +
1.847 +//------------------------------call_catch_cleanup-----------------------------
1.848 +// If we inserted any instructions between a Call and his CatchNode,
1.849 +// clone the instructions on all paths below the Catch.
1.850 +void Block::call_catch_cleanup(Block_Array &bbs) {
1.851 +
1.852 + // End of region to clone
1.853 + uint end = end_idx();
1.854 + if( !_nodes[end]->is_Catch() ) return;
1.855 + // Start of region to clone
1.856 + uint beg = end;
1.857 + while( _nodes[beg-1]->Opcode() != Op_MachProj ||
1.858 + !_nodes[beg-1]->in(0)->is_Call() ) {
1.859 + beg--;
1.860 + assert(beg > 0,"Catch cleanup walking beyond block boundary");
1.861 + }
1.862 + // Range of inserted instructions is [beg, end)
1.863 + if( beg == end ) return;
1.864 +
1.865 + // Clone along all Catch output paths. Clone area between the 'beg' and
1.866 + // 'end' indices.
1.867 + for( uint i = 0; i < _num_succs; i++ ) {
1.868 + Block *sb = _succs[i];
1.869 + // Clone the entire area; ignoring the edge fixup for now.
1.870 + for( uint j = end; j > beg; j-- ) {
1.871 + Node *clone = _nodes[j-1]->clone();
1.872 + sb->_nodes.insert( 1, clone );
1.873 + bbs.map(clone->_idx,sb);
1.874 + }
1.875 + }
1.876 +
1.877 +
1.878 + // Fixup edges. Check the def-use info per cloned Node
1.879 + for(uint i2 = beg; i2 < end; i2++ ) {
1.880 + uint n_clone_idx = i2-beg+1; // Index of clone of n in each successor block
1.881 + Node *n = _nodes[i2]; // Node that got cloned
1.882 + // Need DU safe iterator because of edge manipulation in calls.
1.883 + Unique_Node_List *out = new Unique_Node_List(Thread::current()->resource_area());
1.884 + for (DUIterator_Fast j1max, j1 = n->fast_outs(j1max); j1 < j1max; j1++) {
1.885 + out->push(n->fast_out(j1));
1.886 + }
1.887 + uint max = out->size();
1.888 + for (uint j = 0; j < max; j++) {// For all users
1.889 + Node *use = out->pop();
1.890 + Block *buse = bbs[use->_idx];
1.891 + if( use->is_Phi() ) {
1.892 + for( uint k = 1; k < use->req(); k++ )
1.893 + if( use->in(k) == n ) {
1.894 + Node *fixup = catch_cleanup_find_cloned_def(bbs[buse->pred(k)->_idx], n, this, bbs, n_clone_idx);
1.895 + use->set_req(k, fixup);
1.896 + }
1.897 + } else {
1.898 + if (this == buse) {
1.899 + catch_cleanup_intra_block(use, n, this, beg, n_clone_idx);
1.900 + } else {
1.901 + catch_cleanup_inter_block(use, buse, n, this, bbs, n_clone_idx);
1.902 + }
1.903 + }
1.904 + } // End for all users
1.905 +
1.906 + } // End of for all Nodes in cloned area
1.907 +
1.908 + // Remove the now-dead cloned ops
1.909 + for(uint i3 = beg; i3 < end; i3++ ) {
1.910 + _nodes[beg]->disconnect_inputs(NULL);
1.911 + _nodes.remove(beg);
1.912 + }
1.913 +
1.914 + // If the successor blocks have a CreateEx node, move it back to the top
1.915 + for(uint i4 = 0; i4 < _num_succs; i4++ ) {
1.916 + Block *sb = _succs[i4];
1.917 + uint new_cnt = end - beg;
1.918 + // Remove any newly created, but dead, nodes.
1.919 + for( uint j = new_cnt; j > 0; j-- ) {
1.920 + Node *n = sb->_nodes[j];
1.921 + if (n->outcnt() == 0 &&
1.922 + (!n->is_Proj() || n->as_Proj()->in(0)->outcnt() == 1) ){
1.923 + n->disconnect_inputs(NULL);
1.924 + sb->_nodes.remove(j);
1.925 + new_cnt--;
1.926 + }
1.927 + }
1.928 + // If any newly created nodes remain, move the CreateEx node to the top
1.929 + if (new_cnt > 0) {
1.930 + Node *cex = sb->_nodes[1+new_cnt];
1.931 + if( cex->is_Mach() && cex->as_Mach()->ideal_Opcode() == Op_CreateEx ) {
1.932 + sb->_nodes.remove(1+new_cnt);
1.933 + sb->_nodes.insert(1,cex);
1.934 + }
1.935 + }
1.936 + }
1.937 +}
