reg_split.cpp revision 566
553N/A * Copyright 2000-2008 Sun Microsystems, Inc. All Rights Reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 553N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 553N/A * CA 95054 USA or visit www.sun.com if you need additional information or 0N/A#
include "incls/_precompiled.incl" 0N/A//------------------------------Split-------------------------------------- 0N/A// Walk the graph in RPO and for each lrg which spills, propogate reaching 0N/A// definitions. During propogation, split the live range around regions of 0N/A// High Register Pressure (HRP). If a Def is in a region of Low Register 0N/A// Pressure (LRP), it will not get spilled until we encounter a region of 0N/A// HRP between it and one of its uses. We will spill at the transition 0N/A// point between LRP and HRP. Uses in the HRP region will use the spilled 0N/A// Def. The first Use outside the HRP region will generate a SpillCopy to 0N/A// hoist the live range back up into a register, and all subsequent uses 0N/A// will use that new Def until another HRP region is encountered. Defs in 0N/A// HRP regions will get trailing SpillCopies to push the LRG down into the 0N/A// stack immediately. 0N/A// As a side effect, unlink from (hence make dead) coalesced copies. 0N/A//------------------------------get_spillcopy_wide----------------------------- 0N/A// Get a SpillCopy node with wide-enough masks. Use the 'wide-mask', the 0N/A// wide ideal-register spill-mask if possible. If the 'wide-mask' does 0N/A// not cover the input (or output), use the input (or output) mask instead. 0N/A // If ideal reg doesn't exist we've got a bad schedule happening 0N/A // that is forcing us to spill something that isn't spillable. 0N/A // Bail rather than abort 0N/A assert(
false,
"attempted to spill a non-spillable item");
// Don't come here for mis-aligned doubles }
else {
// wide ideal mask does not overlap with o_mask // Mis-aligned doubles come here and XMM->FPR moves on x86. // Does the ideal-reg-mask overlap with o_mask? I.e., can I use // a reg-reg move or do I need a trip across register classes // (and thus through memory)? // Here we assume a trip through memory is required. //------------------------------insert_proj------------------------------------ // Insert the spill at chosen location. Skip over any interveneing Proj's or // Phis. Skip over a CatchNode and projs, inserting in the fall-through block // instead. Update high-pressure indices. Create a new live range. // Skip intervening ProjNodes. Do not insert between a ProjNode and // Do not insert between a call and his Catch // Put the instruction at the top of the fall-thru block. // Find the fall-thru projection i =
1;
// Right at start of block // Adjust the point where we go hi-pressure // Assign a new Live Range Number to the SpillCopy and grow // the node->live range mapping. //------------------------------split_DEF-------------------------------------- // Only three of these really occur as DOWN/USE will always color // Any Split with a DEF cannot CISC-Spill now. Thus we need // two helper routines, one for Split DEFS (insert after instruction), // one for Split USES (insert before instruction). DEF insertion // happens inside Split, where the Leaveblock array is updated. // Increment the counter for this lrg // If we are spilling the memory op for an implicit null check, at the // null check location (ie - null check is in HRP block) we need to do // the null-check first, then spill-down in the following block. // (The implicit_null_check function ensures the use is also dominated // by the branch-not-taken block.) // Spill goes in the branch-not-taken block loc = 0;
// Just past the Region assert(
loc >= 0,
"must insert past block head" );
// Get a def-side SpillCopy // Did we fail to split?, then bail // Insert the spill at chosen location // Insert new node into Reaches array // Update debug list of reaching down definitions by adding this one // return updated count of live ranges //------------------------------split_USE-------------------------------------- // Splits at uses can involve redeffing the LRG, so no CISC Spilling there. // Debug uses want to know if def is already stack enabled. // Increment the counter for this lrg // Some setup stuff for handling debug node uses //------------------------------------------- // Check for use of debug info // Actually it's perfectly legal for constant debug info to appear // just unlikely. In this case the optimizer left a ConI of a 4 // as both inputs to a Phi with only a debug use. It's a single-def // live range of a rematerializable value. The live range spills, // rematerializes and now the ConI directly feeds into the debug info. // assert(!def->is_Con(), "constant debug info already constructed directly"); // Special split handling for Debug Info // If DEF is DOWN, just hook the edge and return // If DEF is UP, Split it DOWN for this USE. // DEF is DOWN, so connect USE directly to the DEF // Block and index where the use occurs. // Put the clone just prior to use // DEF is UP, so must copy it DOWN and hook in USE // Insert SpillCopy before the USE, which uses DEF as its input, // and defs a new live range, which is used by this node. // insert into basic block // No further split handling needed for this use }
// End special splitting for debug info live range // Finally, check to see if USE is CISC-Spillable, and if so, // gather_lrg_masks will add the flags bit to its mask, and // no use side copy is needed. This frees up the live range // register choices without causing copy coalescing, etc. // Convert operand number to edge index number //------------------------------------------- // Insert a Copy before the use // Block and index where the use occurs. // Phi input spill-copys belong at the end of the prior block // Put the clone just prior to use if( !
spill )
return 0;
// Bailed out // Insert SpillCopy before the USE, which uses the reaching DEF as // its input, and defs a new live range, which is used by this node. // return updated live range count //------------------------------split_Rematerialize---------------------------- // Clone a local copy of the def. // The input live ranges will be stretched to the site of the new // instruction. They might be stretched past a def and will thus // have the old and new values of the same live range alive at the // same time - a definite no-no. Split out private copies of // Check for single-def (LRG cannot redefined) if(
lidx >=
_maxlrg )
continue;
// Value is a recent spill-copy // Check when generating nodes // See if any inputs are currently being spilled, and take the // latest copy of spilled inputs. // Walk backwards thru spill copy node intermediates // walkThru found a multidef LRG, which is unsafe to use, so // just keep the original def used in the clone. // Rematerialized op is def->spilled+1 // Increment the counter for this lrg // See if the cloned def kills any flags, and copy those kills as well // Adjust the point where we go hi-pressure //------------------------------is_high_pressure------------------------------- // Function to compute whether or not this live range is "high pressure" // in this block - whether it spills eagerly or not. // Forced spilling due to conflict? Then split only at binding uses // or defs, not for supposed capacity problems. // CNC - Turned off 7/8/99, causes too much spilling // if( lrg->_is_bound ) return false; // Not yet reached the high-pressure cutoff point, so low pressure // Register pressure for the block as a whole depends on reg class // Bound live ranges will split at the binding points first; // Intermediate splits should assume the live range's register set // got "freed up" and that num_regs will become INT_PRESSURE. // Effective register pressure limit. // High pressure if block pressure requires more register freedom //------------------------------prompt_use--------------------------------- // True if lidx is used before any real register is def'd in the block // Scan block for 1st use. // Ignore PHI use, these can be up or down for(
uint j =
1; j < n->
req(); j++ )
return true;
// Found 1st use! //------------------------------Split-------------------------------------- //----------Split Routine---------- // ***** NEW SPLITTING HEURISTIC ***** // DEFS: If the DEF is in a High Register Pressure(HRP) Block, split there. // Else, no split unless there is a HRP block between a DEF and // one of its uses, and then split at the HRP block. // USES: If USE is in HRP, split at use to leave main LRG on stack. // Else, hoist LRG back up to register only (ie - split is also DEF) // We will compute a new maxlrg as we go // Array of counters to count splits per live range //----------Setup Code---------- // Create a convenient mapping from lrg numbers to reaches/leaves indices // Keep track of DEFS & Phis for later passes // Gather info on which LRG's are spilling, and build maps // Initialize the split counts to zero // Create side arrays for propagating reaching defs info. // Each block needs a node pointer for each spilling live range for the // Def which is live into the block. Phi nodes handle multiple input // Defs by querying the output of their predecessor blocks and resolving // them to a single Def at the phi. The pointer is updated for each // Def in the block, and then becomes the output for the block when // processing of the block is complete. We also need to track whether // a Def is UP or DOWN. UP means that it should get a register (ie - // it is always in LRP regions), and DOWN means that it is probably // on the stack (ie - it crosses HRP regions). // Initialize Reaches & UP // Initialize to array of empty vectorsets //----------PASS 1---------- //----------Propagation & Node Insertion Code---------- // Walk the Blocks in RPO for DEF & USE info // Reaches & UP arrays for this block // Reset counter of start of non-Phi nodes in block //----------Block Entry Handling---------- // Check for need to insert a new phi // Cycle through this block's predecessors, collecting Reaches // info for each spilled LRG. If they are identical, no phi is // needed. If they differ, check for a phi, and insert if missing, // or update edges if present. Set current block's Reaches set to // be either the phi's or the reaching def, as appropriate. // If no Phi is needed, check if the LRG needs to spill on entry // to the block due to HRP. // Grab the live range number // Do not bother splitting or putting in Phis for single-def // rematerialized live ranges. This happens alot to constants // with long live ranges. // reset the Reaches & UP entries // Record following instruction in case 'n' rematerializes and // Initialize needs_phi and needs_split // Walk the predecessor blocks to check inputs for that live range // Grab predecessor block header // Grab the appropriate reaching def info for inpidx // Initialize node for saving type info // Compare inputs to see if a Phi is needed // Grab predecessor block headers // Grab the appropriate reaching def info for inpidx // For each LRG, decide if a phi is necessary // See if the phi has mismatched inputs, UP vs. DOWN // Move n2/u2 to n1/u1 for next iteration // Preserve a non-NULL predecessor for later type referencing }
// End for all potential Phi inputs // check block for appropriate phinode & update edges // bail if this is not a phi // Keep track of index of first non-PhiNode instruction in block // break out of the for loop as we have handled all phi nodes // must be looking at a phi // found the necessary phi // initialize the Reaches entry for this LRG }
// end if found correct phi // If a phi is needed or exist, check for it // add new phinode if one not already found // create a new phi node and insert it into the block // type is taken from left over pointer to a predecessor assert(
n3,
"No non-NULL reaching DEF for a Phi");
// initialize the Reaches entry for this LRG // add node to block & node_to_block mapping // Reset new phi's mapping to be the spilling live range }
// end if not found correct phi // Here you have either found or created the Phi, so record it // PhiNodes should either force the LRG UP or DOWN depending // on its inputs and the register pressure in the Phi's block. // If entering a high-pressure area with no immediate use, // If we are not split up/down and all inputs are down, then we }
// end if phi is needed // Do not need a phi, so grab the reaching DEF // Grab predecessor block header // Grab the appropriate reaching def info for k // reset the Reaches & UP entries }
// end else no Phi is needed }
// end for all spilling live ranges tty->
print(
"Reaching Definitions after Phi handling\n");
//----------Non-Phi Node Splitting---------- // Since phi-nodes have now been handled, the Reachblock array for this // block is initialized with the correct starting value for the defs which // reach non-phi instructions in this block. Thus, process non-phi // instructions normally, inserting SpillCopy nodes for all spill // Memoize any DOWN reaching definitions for use as DEBUG info //----------Walk Instructions in the Block and Split---------- // For all non-phi instructions in the block // Find the defining Node's live range index // Skip phi nodes after removing dead copies. // Check for useless Phis. These appear if we spill, then // coalesce away copies. Dont touch Phis in spilling live // ranges; they are busy getting modifed in this pass. // Look for the Phi merging 2 unique inputs for( i =
1; i <
cnt; i++ ) {
// Ignore repeats and self if( n->
in(i) != u && n->
in(i) != n ) {
if( u !=
NULL )
// If it's the 2nd, bail out u = n->
in(i);
// Else record it assert( u,
"at least 1 valid input expected" );
if( i >=
cnt ) {
// Found one unique input n->
replace_by(u);
// Then replace with unique input // ********** Handle Crossing HRP Boundry ********** // Check for need to split at HRP boundry - split if UP // bail out if no reaching DEF // bail out if live range is 'isolated' around inner loop // If live range is currently UP // set location to insert spills at // SPLIT DOWN HERE - NO CISC SPILL // If there is already a valid stack definition available, use it // Insert point is just past last use or def in the block // Hit top of block? Quit going backwards // Found a def? Better split after it. for( i =
1; i < n->
req(); i++ )
// Found a use? Better split after it. if( i < n->
req() )
break;
// If it wasn't split bail // This is a new DEF, so update UP tty->
print(
"\nNew Split DOWN DEF of Spill Idx ");
}
// end for all spilling live ranges }
// end if crossing HRP Boundry // If the LRG index is oob, then this is a new spillcopy, skip it. // Remove coalesced copy from CFG b->
_ihrp_index--;
// Adjust the point where we go hi-pressure // ********** Handle USES ********** // Implicit null checks never use the spilled value // Search all inputs for a Spill-USE // Derived/base pairs may be added to our inputs during this loop. // If inpidx > old_last, then one of these new inputs is being // handled. Skip the derived part of the pair, but process // the base like any other input. continue;
// skip derived_debug added below // Not a brand-new split, and it is a spill use // Check for valid reaching DEF // (+++) %%%% remove this in favor of pre-pass in matcher.cpp // monitor references do not care where they live, so just hook // The effect of this clone is to drop the node out of the block, // so that the allocator does not see it anymore, and therefore // does not attempt to assign it a register. // Rematerializable? Then clone def at use site instead if( !
def )
return 0;
// Bail out // Base pointers and oopmap references do not care where they live. // This def has been rematerialized a couple of times without // progress. It doesn't care if it lives UP or DOWN, so // If it wasn't split bail insidx++;
// Reset iterator to skip USE side split // Just hook the def edge // After oopoff, we have derived/base pairs. We must mention all // derived pointers here as derived/base pairs for GC. If the // derived value is spilling and we have a copy both in Reachblock // (called here 'def') and debug_defs[slidx] we need to mention // We have already set 'def' as a derived value. // Also set debug_defs[slidx] as a derived value. break;
// Found an instance of debug derived if( k ==
cnt ) {
// No instance of debug_defs[slidx] // We have to process the added base later since it is not // handled yet at this point but skip derived part. "must match skip condition above");
// Increment cnt to handle added input edges on // subsequent iterations. // Special logic for DEBUG info // If this is debug info use & there is a reaching DOWN def // Just hook it in & move on // (Note that this can make two sides of a split live at the // same time: The debug def on stack, and another def in a // register. The GC needs to know about both of them, but any // derived pointers after oopoff will refer to only one of the // two defs and the GC would therefore miss the other. Thus // this hack is only allowed for debug info which is Java state // and therefore never a derived pointer.) // Grab register mask info // Need special logic to handle bound USES. Insert a split at this // bound use if we can't rematerialize the def, or if we need the // split to form a misaligned pair. // These need a Split regardless of overlap or pressure // SPLIT - NO DEF - NO CISC SPILL // If it wasn't split bail insidx++;
// Reset iterator to skip USE side split // Here is the logic chart which describes USE Splitting: // 0 = false or DOWN, 1 = true or UP // Overlap | DEF | USE | Action //------------------------------------------------------- // 0 | 0 | 0 | Copy - mem -> mem // 0 | 0 | 1 | Split-UP - Check HRP // 0 | 1 | 0 | Split-DOWN - Debug Info? // 0 | 1 | 1 | Copy - reg -> reg // 1 | 0 | 0 | Reset Input Edge (no Split) // 1 | 0 | 1 | Split-UP - Check HRP // 1 | 1 | 0 | Split-DOWN - Debug Info? // 1 | 1 | 1 | Reset Input Edge (no Split) // So, if (dup == uup), then overlap test determines action, // with true being no split, and false being copy. Else, // if DEF is DOWN, Split-UP, and check HRP to decide on // resetting DEF. Finally if DEF is UP, Split-DOWN, with // special handling for Debug Info. // Both are either up or down, and there is overlap, No Split else {
// Both are either up or down, and there is no overlap if(
dup ) {
// If UP, reg->reg copy // COPY ACROSS HERE - NO DEF - NO CISC SPILL // If it wasn't split bail insidx++;
// Reset iterator to skip USE side split else {
// DOWN, mem->mem copy // COPY UP & DOWN HERE - NO DEF - NO CISC SPILL // First Split-UP to move value into Register // Then Split-DOWN as if previous Split was DEF // If it wasn't split bail insidx +=
2;
// Reset iterator to skip USE side splits // dup != uup, so check dup for direction of Split if(
dup ) {
// If UP, Split-DOWN and check Debug Info // If this node is already a SpillCopy, just patch the edge // except the case of spilling to stack. // COPY DOWN HERE - NO DEF - NO CISC SPILL // If it wasn't split bail insidx++;
// Reset iterator to skip USE side split // Check for debug-info split. Capture it for later // debug splits of the same value else {
// DOWN, Split-UP and check register pressure // COPY UP HERE - NO DEF - CISC SPILL // If it wasn't split bail insidx++;
// Reset iterator to skip USE side split // COPY UP HERE - WITH DEF - NO CISC SPILL // If it wasn't split bail // Flag this lift-up in a low-pressure block as // already-spilled, so if it spills again it will // spill hard (instead of not spilling hard and // Since this is a new DEF, update Reachblock & UP insidx++;
// Reset iterator to skip USE side split }
// End If not nullcheck // ********** Handle DEFS ********** // DEFS either Split DOWN in HRP regions or when the LRG is bound, or // just reset the Reaches info in LRP regions. DEFS must always update // Add to defs list for later assignment of new live range number // Set a flag on the Node indicating it has already spilled. // Only do it for capacity spills not conflict spills. // Only split at Def if this is a HRP block or bound (and spilled once) // Check for LRG being up in a register and we are inside a high // pressure area. Spill it down immediately. // Do a split at the def site. // If it wasn't split bail tty->
print(
"\nNew Split DOWN DEF of Spill Idx ");
else {
// Neither bound nor HRP, must be LRP // otherwise, just record the def // UP should come from the outRegmask() of the DEF // Update debug list of reaching down definitions, kill if DEF is UP // ********** Split Left Over Mem-Mem Moves ********** // Check for mem-mem copies and split them now. Do not do this // to copies about to be spilled; they will be Split shortly. // Put the spill just before the copy }
// End For All Instructions in Block - Non-PHI Pass // Check if each LRG is live out of this block so as not to propagate // beyond the last use of a LRG. // The index defidx is not live. Check the liveout array to ensure that // it contains no members which compress to defidx. Finding such an // instance may be a case to add liveout adjustment in compress_uf_map(). //----------PASS 2---------- // Reset all DEF live range numbers here //----------Phi Node Splitting---------- // Clean up a phi here, and assign a new live range number // Cycle through this block's predecessors, collecting Reaches // info for each spilled LRG and update edges. // Walk the phis list to patch inputs, split phis, and name phis // Grab the live range number // Update node to lidx map // Get PASS1's up/down decision for the block. // Force down if double-spilling live range // When splitting a Phi we an split it normal or "inverted". // An inverted split makes the splits target the Phi's UP/DOWN // sense inverted; then the Phi is followed by a final def-side // split to invert back. It changes which blocks the spill code // Walk the predecessor blocks and assign the reaching def to the Phi. // Split Phi nodes by placing USE side splits wherever the reaching // DEF has the wrong UP/DOWN value. // Get predecessor block pre-order number // If input up/down sense and reg-pressure DISagree if( !
def )
return 0;
// Bail out // Update the Phi's input edge array // Grab the UP/DOWN sense for the input // If it wasn't split bail }
// End for all inputs to the Phi }
// End for all Phi Nodes // Update _maxlrg to save Union asserts //----------PASS 3---------- // Pass over all Phi's to union the live ranges // Walk all inputs to Phi and Union input live range with Phi live range }
// End for all inputs to the Phi Node }
// End for all Phi Nodes // Now union all two address instructions // Set new lidx for DEF & handle 2-addr instructions // Union the input and output live ranges // Validate all live range index assignments // Issue a warning if splitting made no progress // Return updated count of live ranges