chaitin.cpp revision 196
/*
* Copyright 2000-2008 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.com if you need additional information or
* have any questions.
*
*/
#include "incls/_precompiled.incl"
#include "incls/_chaitin.cpp.incl"
//=============================================================================
#ifndef PRODUCT
if( _msize_valid ) {
} else {
}
if( _def == NodeSentinel ) {
}
}
}
// Flags
if( _msize_valid ) {
}
}
#endif
//------------------------------score------------------------------------------
// Compute score from cost and area. Low score is best to spill.
}
// Scale _area by RegisterCostAreaRatio/64K then subtract from cost.
// Bigger area lowers score, encourages spilling this live range.
// Bigger cost raise score, prevents spilling this live range.
// (Note: 1/65536 is the magic constant below; I dont trust the C optimizer
// to turn a divide by a constant into a multiply by the reciprical).
// Account for area. Basically, LRGs covering large areas are better
// to spill because more other LRGs get freed up.
return 1e35;
if( _was_spilled2 ) // If spilled once before, we are unlikely
return score;
}
//------------------------------LRG_List---------------------------------------
}
}
}
#define NUMBUCKS 3
//------------------------------Chaitin----------------------------------------
#ifndef PRODUCT
#else
#endif
),
#ifndef PRODUCT
#endif
{
uint i,j;
// Build a list of basic blocks, sorted by frequency
// Experiment with sorting strategies to speed compilation
for( i = 0; i < NUMBUCKS; i++ ) {
buckcnt[i] = 0;
// Bump by three orders of magnitude each time
cutoff *= 0.001;
for( j = 0; j < _cfg._num_blocks; j++ ) {
}
}
// Sort blocks into buckets
for( i = 0; i < _cfg._num_blocks; i++ ) {
for( j = 0; j < NUMBUCKS; j++ ) {
// Assign block to end of list for appropriate bucket
break; // kick out of inner loop
}
}
}
// Dump buckets into final block array
for( i = 0; i < NUMBUCKS; i++ ) {
for( j = 0; j < buckcnt[i]; j++ ) {
}
}
}
void PhaseChaitin::Register_Allocate() {
// Above the OLD FP (and in registers) are the incoming arguments. Stack
// slots in this area are called "arg_slots". Above the NEW FP (and in
// area. These are all "frame_slots". Arg_slots start at the zero
// stack_slots and count up to the known arg_size. Frame_slots start at
// the stack_slot #arg_size and go up. After allocation I map stack
// slots to actual offsets. Stack-slots in the arg_slot area are biased
// by the frame_size; stack-slots in the frame_slot area are biased by 0.
_trip_cnt = 0;
_alternate = 0;
_matcher._allocation_started = true;
// Need live-ness for the IFG; need the IFG for coalescing. If the
// liveness is JUST for coalescing, then I can get some mileage by renaming
// all copy-related live ranges low and then using the max copy-related
// live range as a cut-off for LIVE and the IFG. In other words, I can
// build a subset of LIVE and IFG just for copies.
// Need IFG for coalescing and coloring
// Come out of SSA world to the Named world. Assign (virtual) registers to
// Nodes. Use the same register for all inputs and the output of PhiNodes
// - effectively ending SSA form. This requires either coalescing live
// ranges or inserting copies. For the moment, we insert "virtual copies"
// - we pretend there is a copy prior to each Phi in predecessor blocks.
// We will attempt to coalesce such "virtual copies" before we manifest
// them for real.
de_ssa();
{
gather_lrg_masks( false ); // Collect LRG masks
}
// Base pointers are currently "used" by instructions which define new
// derived pointers. This makes base pointers live up to the where the
// derived pointer is made, but not beyond. Really, they need to be live
// across any GC point where the derived value is live. So this code looks
// at all the GC points, and "stretches" the live range of any base pointer
// to the GC point.
if( stretch_base_pointer_live_ranges(&live_arena) ) {
// Since some live range stretched, I need to recompute live
gather_lrg_masks( false );
}
// Create the interference graph using virtual copies
build_ifg_virtual( ); // Include stack slots this time
// Aggressive (but pessimistic) copy coalescing.
// This pass works on virtual copies. Any virtual copies which are not
// coalesced get manifested as actual copies
{
// faster. Union requires a 'for all' operation which is slow on the
// triangular adjacency matrix (quick reminder: the IFG is 'sparse' -
// meaning I can visit all the Nodes neighbors less than a Node in time
// O(# of neighbors), but I have to visit all the Nodes greater than a
// given Node and search them for an instance, i.e., time O(#MaxLRG)).
PhaseAggressiveCoalesce coalesce( *this );
// Insert un-coalesced copies. Visit all Phis. Where inputs to a Phi do
// not match the Phi itself, insert a copy.
}
// After aggressive coalesce, attempt a first cut at coloring.
// To color, we need the IFG and for that we need LIVE.
{
gather_lrg_masks( true );
}
// Build physical interference graph
uint must_spill = 0;
// If we have a guaranteed spill, might as well spill now
if( must_spill ) {
if( !_maxlrg ) return;
// Bail out if unique gets too large (ie - unique > MaxNodeLimit)
if (C->failing()) return;
// Bail out if unique gets too large (ie - unique > MaxNodeLimit - 2*NodeLimitFudgeFactor)
// or we failed to split
if (C->failing()) return;
#ifdef ASSERT
if( VerifyOpto ) {
}
#endif
NOT_PRODUCT( C->verify_graph_edges(); )
compact(); // Compact LRGs; return new lower max lrg
{
gather_lrg_masks( true ); // Collect intersect mask
}
// Only do conservative coalescing if requested
if( OptoCoalesce ) {
// Conservative (and pessimistic) copy coalescing of those spills
PhaseConservativeCoalesce coalesce( *this );
// If max live ranges greater than cutoff, don't color the stack.
// This cutoff can be larger than below since it is only done once.
}
#ifdef ASSERT
#endif
} else {
#ifdef ASSERT
set_was_low();
#endif
}
// Prepare for Simplify & Select
cache_lrg_info(); // Count degree of LRGs
// Simplify the InterFerence Graph by removing LRGs of low degree.
// LRGs of low degree are trivially colorable.
Simplify();
// Select colors by re-inserting LRGs back into the IFG in reverse order.
// Return whether or not something spills.
// If we spill, split and recycle the entire thing
while( spills ) {
if( _trip_cnt++ > 24 ) {
if( _trip_cnt > 27 ) {
C->record_method_not_compilable("failed spill-split-recycle sanity check");
return;
}
}
if( !_maxlrg ) return;
// Bail out if unique gets too large (ie - unique > MaxNodeLimit - 2*NodeLimitFudgeFactor)
if (C->failing()) return;
#ifdef ASSERT
if( VerifyOpto ) {
}
#endif
compact(); // Compact LRGs; return new lower max lrg
// Nuke the live-ness and interference graph and LiveRanGe info
{
// Create LiveRanGe array.
// Intersect register masks for all USEs and DEFs
gather_lrg_masks( true );
}
// Only do conservative coalescing if requested
if( OptoCoalesce ) {
// Conservative (and pessimistic) copy coalescing
PhaseConservativeCoalesce coalesce( *this );
// Check for few live ranges determines how aggressive coalesce is.
}
#ifdef ASSERT
#endif
cache_lrg_info(); // Count degree of LRGs
// Simplify the InterFerence Graph by removing LRGs of low degree.
// LRGs of low degree are trivially colorable.
Simplify();
// Select colors by re-inserting LRGs back into the IFG in reverse order.
// Return whether or not something spills.
}
// Count number of Simplify-Select trips per coloring success.
_allocator_successes += 1;
// Peephole remove copies
// max_reg is past the largest *register* used.
// Convert that to a frame_slot number.
_framesize = C->out_preserve_stack_slots();
assert((int)(_matcher._new_SP+_framesize) >= (int)_matcher._out_arg_limit, "framesize must be large enough");
// This frame must preserve the required fp alignment
if (stack_alignment_in_words > 0)
#ifndef PRODUCT
if( (int)_framesize > _max_framesize )
#endif
// Convert CISC spills
fixup_spills();
// Log regalloc results
}
if (C->failing()) return;
NOT_PRODUCT( C->verify_graph_edges(); )
// Move important info out of the live_arena to longer lasting storage.
if( _names[i] ) { // Live range associated with Node?
} else { // Must be a register-pair
// Live ranges record the highest register in their mask.
// We want the low register for the AD file writer's convenience.
} else { // Misaligned; extract 2 bits
}
}
} else {
_node_regs[i].set_bad();
}
}
// Done!
}
//------------------------------de_ssa-----------------------------------------
void PhaseChaitin::de_ssa() {
// Set initial Names for all Nodes. Most Nodes get the virtual register
// number. A few get the ZERO live range number. These do not
// get allocated, but instead rely on correct scheduling to ensure that
// only one instance is simultaneously live at a time.
// Handle all the normal Nodes in the block
// Pre-color to the zero live range, or pick virtual register
}
}
// Reset the Union-Find mapping to be identity
}
//------------------------------gather_lrg_masks-------------------------------
// Gather LiveRanGe information, including register masks. Modification of
// cisc spillable in_RegMasks should not be done before AggressiveCoalesce.
// Nail down the frame pointer live range
// For all blocks
// For all instructions
// Get virtual register number, same as LiveRanGe index
if( vreg ) { // No vreg means un-allocable (e.g. memory)
// Collect has-copy bit
if( idx ) {
}
// Check for float-vs-int live range (used in register-pressure
// calculations)
if( n_type->is_floatingpoint() )
// Check for twice prior spilling. Once prior spilling might have
// spilled 'soft', 2nd prior spill should have spilled 'hard' and
// further spilling is unlikely to make progress.
}
#ifndef PRODUCT
// collect defs for MultiDef printing
}
}
#endif
// Check for a single def LRG; these can spill nicely
// via rematerialization. Flag as NULL for no def found
// yet, or 'n' for single def or -1 for many defs.
// Limit result register mask to acceptable registers
// Check for bound register masks
// Check for maximum frequency value
"oops must be in Op_RegP's" );
// Check for multi-kill projection
switch( ireg ) {
case MachProjNode::fat_proj:
// Fat projections have size equal to number of registers killed
break;
case Op_RegP:
#ifdef _LP64
#else
#endif
// Register pressure is tracked relative to the maximum values
// suggested for that platform, INTPRESSURE and FLOATPRESSURE,
// and relative to other types which compete for the same regs.
//
// The following table contains suggested values based on the
// architectures as defined in each .ad file.
// INTPRESSURE and FLOATPRESSURE may be tuned differently for
// compile-speed or performance.
// Note1:
// SPARC and SPARCV9 reg_pressures are at 2 instead of 1
// since .ad registers are defined as high and low halves.
// These reg_pressure values remain compatible with the code
// in is_high_pressure() which relates get_invalid_mask_size(),
// Block::_reg_pressure and INTPRESSURE, FLOATPRESSURE.
// Note2:
// SPARC -d32 has 24 registers available for integral values,
// but only 10 of these are safe for 64-bit longs.
// Using set_reg_pressure(2) for both int and long means
// the allocator will believe it can fit 26 longs into
// registers. Using 2 for longs and 1 for ints means the
// allocator will attempt to put 52 integers into registers.
// The settings below limit this problem to methods with
// many long values which are being run on 32-bit SPARC.
//
// ------------------- reg_pressure --------------------
// Each entry is reg_pressure_per_value,number_of_regs
// RegL RegI RegFlags RegF RegD INTPRESSURE FLOATPRESSURE
// IA32 2 1 1 1 1 6 6
// IA64 1 1 1 1 1 50 41
// SPARC 2 2 2 2 2 48 (24) 52 (26)
// SPARCV9 2 2 2 2 2 48 (24) 52 (26)
// AMD64 1 1 1 1 1 14 15
// -----------------------------------------------------
#if defined(SPARC)
#else
#endif
if( n_type->isa_oop_ptr() ) {
}
break;
case Op_RegL: // Check for long or double
case Op_RegD:
// Define platform specific register pressure
#ifdef SPARC
} else {
}
#else
#endif
// If this def of a double forces a mis-aligned double,
// flag as '_fat_proj' - really flag as allowing misalignment
// AND changes how we count interferences. A mis-aligned
// double can interfere with TWO aligned pairs, or effectively
// FOUR registers!
if( rm.is_misaligned_Pair() ) {
}
break;
case Op_RegF:
case Op_RegI:
case Op_RegN:
case Op_RegFlags:
case 0: // not an ideal register
#ifdef SPARC
#else
#endif
break;
default:
}
}
// Now do the same for inputs
// Setup for CISC SPILLING
if( UseCISCSpill && after_aggressive ) {
inp = n->cisc_operand();
// Convert operand number to edge index number
}
// Prepare register mask for each input
if( !vreg ) continue;
// If this instruction is CISC Spillable, add the flags
// bit to its appropriate input
#ifndef PRODUCT
if( TraceCISCSpill ) {
n->dump();
}
#endif
n->as_Mach()->use_cisc_RegMask();
}
// // Testing for floating point code shape
// Node *test = n->in(k);
// if( test->is_Mach() ) {
// MachNode *m = test->as_Mach();
// int op = m->ideal_Opcode();
// if (n->is_Call() && (op == Op_AddF || op == Op_MulF) ) {
// int zzz = 1;
// }
// }
// Limit result register mask to acceptable registers.
// Do not limit registers from uncommon uses before
// AggressiveCoalesce. This effectively pre-virtual-splits
// around uncommon uses of common defs.
if( !after_aggressive &&
// Since we are BEFORE aggressive coalesce, leave the register
// mask untrimmed by the call. This encourages more coalescing.
// Later, AFTER aggressive, this live range will have to spill
// but the spiller handles slow-path calls very nicely.
} else {
}
// Check for bound register masks
// If this use of a double forces a mis-aligned double,
// flag as '_fat_proj' - really flag as allowing misalignment
// AND changes how we count interferences. A mis-aligned
// double can interfere with TWO aligned pairs, or effectively
// FOUR registers!
}
// if the LRG is an unaligned pair, we will have to spill
// so clear the LRG's register mask if it is not already spilled
if ( !n->is_SpillCopy() &&
}
// Check for maximum frequency value
} // End for all allocated inputs
} // end for all instructions
} // end for all blocks
// Final per-liverange setup
lrg.ClearToPairs();
}
}
}
//------------------------------set_was_low------------------------------------
// Set the was-lo-degree bit. Conservative coalescing should not change the
// colorability of the graph. If any live range was of low-degree before
// coalescing, it should Simplify. This call sets the was-lo-degree bit.
// The bit is checked in Simplify.
void PhaseChaitin::set_was_low() {
#ifdef ASSERT
} else { // Else check the Brigg's assertion
// Brigg's observation is that the lo-degree neighbors of a
// hi-degree live range will not interfere with the color choices
// of said hi-degree live range. The Simplify reverse-stack-coloring
// order takes care of the details. Hence you do not have to count
// low-degree neighbors when determining if this guy colors.
int briggs_degree = 0;
}
}
}
#endif
}
#define REGISTER_CONSTRAINED 16
//------------------------------cache_lrg_info---------------------------------
void PhaseChaitin::cache_lrg_info( ) {
// Check for being of low degree: means we can be trivially colored.
// Low degree, dead or must-spill guys just get to simplify right away
lrg._must_spill ) {
// Split low degree list into those guys that must get a
// register and those that can go to register or stack.
// The idea is LRGs that can go register or stack color first when
// they have a good chance of getting a register. The register-only
// lo-degree live ranges always get a register.
_lo_stk_degree = i;
} else {
_lo_degree = i;
}
} else { // Else high degree
_hi_degree = i;
}
}
}
//------------------------------Pre-Simplify-----------------------------------
// Simplify the IFG by removing LRGs of low degree that have NO copies
void PhaseChaitin::Pre_Simplify( ) {
// Warm up the lo-degree no-copy list
int lo_no_copy = 0;
lrgs(i)._must_spill ) {
lo_no_copy = i;
}
}
while( lo_no_copy ) {
// Put the simplified guy on the simplified list.
_simplified = lo;
// Yank this guy from the IFG.
// If any neighbors' degrees fall below their number of
// allowed registers, then put that neighbor on the low degree
// list. Note that 'degree' can only fall and 'numregs' is
// unchanged by this action. Thus the two are equal at most once,
// so LRGs hit the lo-degree worklists at most once.
// Check for just becoming of-low-degree
if( n->just_lo_degree() && !n->_has_copy ) {
// Put on lo-degree list
n->_next = lo_no_copy;
}
}
} // End of while lo-degree no_copy worklist not empty
// No more lo-degree no-copy live ranges to simplify
}
//------------------------------Simplify---------------------------------------
// Simplify the IFG by removing LRGs of low degree.
void PhaseChaitin::Simplify( ) {
while( 1 ) { // Repeat till simplified it all
// May want to explore simplifying lo_degree before _lo_stk_degree.
// This might result in more spills coloring into registers during
// Select().
while( _lo_degree || _lo_stk_degree ) {
// If possible, pull from lo_stk first
if( _lo_degree ) {
lo = _lo_degree;
} else {
lo = _lo_stk_degree;
}
// Put the simplified guy on the simplified list.
_simplified = lo;
// If this guy is "at risk" then mark his current neighbors
}
}
// Yank this guy from the IFG.
// If any neighbors' degrees fall below their number of
// allowed registers, then put that neighbor on the low degree
// list. Note that 'degree' can only fall and 'numregs' is
// unchanged by this action. Thus the two are equal at most once,
// so LRGs hit the lo-degree worklist at most once.
#ifdef ASSERT
if( VerifyOpto ) {
}
#endif
// Check for just becoming of-low-degree just counting registers.
// _must_spill live ranges are already on the low degree list.
if( n->just_lo_degree() && !n->_must_spill ) {
// Pull from hi-degree list
else _hi_degree = next;
n->_next = _lo_degree;
}
}
} // End of while lo-degree/lo_stk_degree worklist not empty
// Check for got everything: is hi-degree list empty?
if( !_hi_degree ) break;
// Time to pick a potential spill guy
// Find cheapest guy
debug_only( int lo_no_simplify=0; );
// It's just vaguely possible to move hi-degree to lo-degree without
// going through a just-lo-degree stage: If you remove a double from
// a float live range it's degree will drop by 2 and you can skip the
// just-lo-degree stage. It's very rare (shows up after 5000+ methods
// in -Xcomp of Java2Demo). So just choose this guy to simplify next.
lo_score = i;
break;
}
// wins. Ties happen because all live ranges in question have spilled
// a few times before and the spill-score adds a huge number which
// washes out the low order bits. We are choosing the lesser of 2
// evils; in this case pick largest area to spill.
lo_score = i;
}
}
// The live range we choose for spilling is either hi-degree, or very
// rarely it can be low-degree. If we choose a hi-degree live range
// there better not be any lo-degree choices.
assert( lo_lrg->lo_degree() || !lo_no_simplify, "Live range was lo-degree before coalesce; should simplify" );
// Pull from hi-degree list
else _hi_degree = next;
// Jam him on the lo-degree list, despite his high degree.
// Maybe he'll get a color, and maybe he'll spill.
// Only Select() will know.
} // End of while not simplified everything
}
//------------------------------bias_color-------------------------------------
// Choose a color using the biasing heuristic
// Check for "at_risk" LRG's
if( risk_lrg != 0 ) {
// Walk the colored neighbors of the "at_risk" candidate
// Choose a color which is both legal and already taken by a neighbor
// of the "at_risk" candidate in order to improve the chances of the
// "at_risk" candidate of coloring
// If this LRG's register is legal for us, choose it
return reg;
}
}
if( copy_lrg != 0 ) {
// If he has a color,
// And it is legal for you,
return reg;
} else if( chunk == 0 ) {
// Choose a color which is legal for him
} else {
}
return reg;
}
}
// If no bias info exists, just go with the register selection ordering
// Find an aligned pair
}
// CNC - Fun hack. Alternate 1st and 2nd selection. Enables post-allocate
// copy removal to remove many more copies, by preventing a just-assigned
// register from being repeatedly assigned.
// This 'Remove; find; Insert' idiom is an expensive way to find the
// SECOND element in the mask.
}
}
//------------------------------choose_color-----------------------------------
// Choose a color in the current chunk
assert( C->in_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP-1)), "must not allocate stack0 (inside preserve area)");
assert(C->out_preserve_stack_slots() == 0 || chunk != 0 || lrg._is_bound || lrg.mask().is_bound1() || !lrg.mask().Member(OptoReg::Name(_matcher._old_SP+0)), "must not allocate stack0 (inside preserve area)");
// Use a heuristic to "bias" the color choice
// Fat-proj case or misaligned double argument.
// Return the highest element in the set.
}
//------------------------------Select-----------------------------------------
// Select colors by re-inserting LRGs back into the IFG. LRGs are re-inserted
// in reverse order of removal. As long as nothing of hi-degree was yanked,
// everything going back is guaranteed a color. Select that color. If some
// hi-degree LRG cannot get a color then we record that we must spill.
while( _simplified ) {
// Pull next LRG from the simplified list - in reverse order of removal
#ifndef PRODUCT
if (trace_spilling()) {
lrg->degrees_of_freedom());
}
#endif
// Re-insert into the IFG
// capture allstackedness flag before mask is hacked
// Yeah, yeah, yeah, I know, I know. I can refactor this
// to avoid the GOTO, although the refactored code will not
// be much clearer. We arrive here IFF we have a stack-based
// live range that cannot color in the current chunk, and it
// has to move into the next free stack chunk.
int chunk = 0; // Current chunk is first chunk
// Remove neighbor colors
// Note that neighbor might be a spill_reg. In this case, exclusion
// of its color will be a no-op, since the spill_reg chunk is in outer
// space. Also, if neighbor is in a different chunk, this exclusion
// will be a no-op. (Later on, if lrg runs out of possible colors in
// its chunk, a new chunk of color may be tried, in which case
// examination of neighbors is started again, at retry_next_chunk.)
// Only subtract masks in the same chunk
#ifndef PRODUCT
#endif
#ifndef PRODUCT
}
#endif
}
}
//assert(is_allstack == lrg->mask().is_AllStack(), "nbrs must not change AllStackedness");
// Aligned pairs need aligned masks
lrg->ClearToPairs();
// Check if a color is available and if so pick the color
#ifdef SPARC
#endif
//---------------
// If we fail to color and the AllStack flag is set, trigger
// a chunk-rollover event
// Bump register mask up to next stack chunk
goto retry_next_chunk;
}
//---------------
// Did we get a color?
#ifndef PRODUCT
#endif
// Record selected register
// Fold reg back into normal space
// If the live range is not bound, then we actually had some choices
// to make. In this case, the mask has more bits in it than the colors
// choosen. Restrict the mask to just what was picked.
// For pairs, also insert the low bit of the pair
} else { // Else fatproj
// mask must be equal to fatproj bits, by definition
}
#ifndef PRODUCT
if (trace_spilling()) {
}
#endif
// Note that reg is the highest-numbered register in the newly-bound mask.
} // end color available case
//---------------
// Live range is live and no colors available
else {
// Assign the special spillreg register
// Do not empty the regmask; leave mask_size lying around
// for use during Spilling
#ifndef PRODUCT
if( trace_spilling() ) {
s->dump();
}
#endif
} // end spill case
}
}
//------------------------------copy_was_spilled-------------------------------
// Copy 'was_spilled'-edness from the source Node to the dst Node.
}
}
}
//------------------------------set_was_spilled--------------------------------
// Set the 'spilled_once' or 'spilled_twice' flag on a node.
}
//------------------------------fixup_spills-----------------------------------
// Convert Ideal spill instructions into proper FramePtr + offset Loads and
// Stores. Use-def chains are NOT preserved, but Node->LRG->reg maps are.
void PhaseChaitin::fixup_spills() {
// This function does only cisc spill work.
if( !UseCISCSpill ) return;
// Grab the Frame Pointer
// For all blocks
// For all instructions in block
// Dead instruction???
C->top() == n || // Or the random TOP node
n->is_Proj(), // Or a fat-proj kill node
"No dead instructions after post-alloc" );
int inp = n->cisc_operand();
// Convert operand number to edge index number
// Doubles record the HIGH register of an adjacent pair.
// This is a CISC Spill, get stack offset and construct new node
#ifndef PRODUCT
if( TraceCISCSpill ) {
n->dump();
}
#endif
// Bailout if we might exceed node limit when spilling this instruction
C->check_node_count(0, "out of nodes fixing spills");
if (C->failing()) return;
// Transform node
}
//
#ifndef PRODUCT
if( TraceCISCSpill ) {
}
#endif
} else {
#ifndef PRODUCT
if( TraceCISCSpill ) {
n->dump();
}
#endif
++_unused_cisc_instructions; // input can be on stack
}
}
} // End of for all instructions
} // End of for all blocks
}
//------------------------------find_base_for_derived--------------------------
// Helper to stretch above; recursively discover the base Node for a
// given derived Node. Easy for AddP-related machine nodes, but needs
// to be recursive for derived Phis.
// See if already computed; if so return it
// See if this happens to be a base.
// NOTE: we use TypePtr instead of TypeOopPtr because we can have
// pointers derived from NULL! These are always along paths that
// can't happen at run-time but the optimizer cannot deduce it so
// we have to handle it gracefully.
// If its an OOP with a non-zero offset, then it is derived.
return derived;
}
// Derived is NULL+offset? Base is NULL!
return base;
}
// Check for AddP-related opcodes
return base;
}
// Recursively find bases for Phis.
// First check to see if we can avoid a base Phi here.
uint i;
break;
// Went to the end without finding any different bases?
return base;
}
// Now we see we need a base-Phi here to merge the bases
// Search the current block for an existing base-Phi
break;
}
// See if Phi matches.
uint j;
break;
break;
}
}
// Cache info for later passes
return base;
}
//------------------------------stretch_base_pointer_live_ranges---------------
// At each Safepoint, insert extra debug edges for each pair of derived value/
// base pointer that is live across the Safepoint for oopmap building. The
// edge pairs get added in after sfpt->jvmtail()->oopoff(), but are in the
// required edge set.
int must_recompute_live = false;
// For all blocks in RPO do...
// Note use of deep-copy constructor. I cannot hammer the original
// liveout bits, because they are needed by the following coalesce pass.
// Pre-split compares of loop-phis. Loop-phis form a cycle we would
// like to see in the same register. Compare uses the loop-phi and so
// extends its live range BUT cannot be part of the cycle. If this
// extended live range overlaps with the update of the loop-phi value
// we need both alive at the same time -- which requires at least 1
// copy. But because Intel has only 2-address registers we end up with
// at least 2 copies, one before the loop-phi update instruction and
// one after. Instead we split the input to the compare just after the
// phi.
must_recompute_live = true;
}
}
}
// Get value being defined
// Remove from live-out set
// Copies do not define a new value and so do not interfere.
// Remove the copies source from the liveout set before interfering.
}
// Found a safepoint?
if( jvms ) {
// Now scan for a live derived pointer
// Find reaching DEF for base and derived values
// This works because we are still in SSA during this call.
// If its an OOP with a non-zero offset, then it is derived.
// Add reaching DEFs of derived pointer and base pointer as a
// pair of inputs
// See if the base pointer is already live to this point.
// Since I'm working on the SSA form, live-ness amounts to
// reaching def's. So if I find the base's live range then
// I know the base's def reaches here.
// Base pointer is not currently live. Since I stretched
// the base pointer to here and it crosses basic-block
// boundaries, the global live info is now incorrect.
// Recompute live.
must_recompute_live = true;
} // End of if base pointer is not live to debug info
}
} // End of scan all live data for derived ptrs crossing GC point
} // End of if found a GC point
// Make all inputs live
if( !n->is_Phi() ) { // Phi function uses come from prior block
}
}
} // End of forall instructions in block
} // End of forall blocks
// If I created a new live range I need to recompute live
must_recompute_live = true;
return must_recompute_live != 0;
}
//------------------------------add_reference----------------------------------
// Extend the node to LRG mapping
}
//------------------------------dump-------------------------------------------
#ifndef PRODUCT
if( _node_regs ) { // Got a post-allocation copy of allocation?
else
}
else
} else
n->out_RegMask().dump();
}
uint k;
for( k = 0; k < n->req(); k++) {
else {
// Data MultiNode's can have projections with no real registers.
// Don't die while dumping them.
if( _node_regs ) {
else
}
else
} else
n->in_RegMask(k).dump();
}
}
}
for( ; k < n->len(); k++ ) {
if( !m ) break;
}
}
}
// For all instructions
// Print live-out info at end of block
if( _live ) {
uint i;
}
}
}
void PhaseChaitin::dump() const {
// For all blocks
// End of per-block dump
if (!_ifg) {
return;
}
// Dump LRG array
}
// Dump lo-degree list
// Dump lo-stk-degree list
// Dump lo-degree list
}
//------------------------------dump_degree_lists------------------------------
void PhaseChaitin::dump_degree_lists() const {
// Dump lo-degree list
// Dump lo-stk-degree list
// Dump lo-degree list
}
//------------------------------dump_simplified--------------------------------
void PhaseChaitin::dump_simplified() const {
}
if ((int)reg < 0)
else
}
//------------------------------dump_register----------------------------------
// Dump a register name into a buffer. Be intelligent if we get called
// before allocation is complete.
if( !this ) { // Not got anything?
} else if( _node_regs ) {
// Post allocation, use direct mappings, no LRG info available
} else {
if( !_ifg ) {
} else if( !lidx ) { // Special, not allocated value
} else { // Hah! We have a bound machine register
}
}
}
//----------------------dump_for_spill_split_recycle--------------------------
void PhaseChaitin::dump_for_spill_split_recycle() const {
// Display which live ranges need to be split and the allocator's state
}
}
dump();
}
}
//------------------------------dump_frame------------------------------------
void PhaseChaitin::dump_frame() const {
// Incoming arguments in registers dump
for( int k = 0; k < argcnt; k++ ) {
}
}
}
// Check for un-owned padding above incoming args
}
// Incoming argument area dump
while( reg > begin_in_arg ) {
int j;
for( j = 0; j < argcnt; j++) {
break;
}
}
if( j >= argcnt )
}
// Old outgoing preserve area
}
// Old SP
reg2offset_unchecked(OptoReg::add(_matcher._old_SP,-1)) - reg2offset_unchecked(_matcher._new_SP)+jintSize);
// Preserve area dump
else
}
// Spill area dump
}
// Outgoing argument area dump
}
// Outgoing new preserve area
}
}
//------------------------------dump_bb----------------------------------------
if( b->_pre_order == pre_order )
dump(b);
}
}
//------------------------------dump_lrg---------------------------------------
if( _ifg ) {
return;
}
}
}
// For all blocks
int dump_once = 0;
// For all instructions
if( Find_const(n) == lidx ) {
if( !dump_once++ ) {
}
dump(n);
continue;
}
if (!m) continue; // be robust in the dumper
if( Find_const(m) == lidx ) {
if( !dump_once++ ) {
}
dump(n);
}
}
}
} // End of per-block dump
}
#endif // not PRODUCT
//------------------------------print_chaitin_statistics-------------------------------
int PhaseChaitin::_final_loads = 0;
int PhaseChaitin::_final_stores = 0;
int PhaseChaitin::_final_memoves= 0;
int PhaseChaitin::_final_copies = 0;
double PhaseChaitin::_final_load_cost = 0;
double PhaseChaitin::_final_store_cost = 0;
double PhaseChaitin::_final_memove_cost= 0;
double PhaseChaitin::_final_copy_cost = 0;
int PhaseChaitin::_conserv_coalesce = 0;
int PhaseChaitin::_conserv_coalesce_pair = 0;
int PhaseChaitin::_conserv_coalesce_trie = 0;
int PhaseChaitin::_conserv_coalesce_quad = 0;
int PhaseChaitin::_post_alloc = 0;
int PhaseChaitin::_lost_opp_pp_coalesce = 0;
int PhaseChaitin::_lost_opp_cflow_coalesce = 0;
int PhaseChaitin::_used_cisc_instructions = 0;
int PhaseChaitin::_unused_cisc_instructions = 0;
int PhaseChaitin::_allocator_attempts = 0;
int PhaseChaitin::_allocator_successes = 0;
#ifndef PRODUCT
void PhaseChaitin::print_chaitin_statistics() {
tty->print_cr("Inserted %d spill loads, %d spill stores, %d mem-mem moves and %d copies.", _final_loads, _final_stores, _final_memoves, _final_copies);
tty->print_cr("Total load cost= %6.0f, store cost = %6.0f, mem-mem cost = %5.2f, copy cost = %5.0f.", _final_load_cost, _final_store_cost, _final_memove_cost, _final_copy_cost);
if( _allocator_successes != 0 )
tty->print_cr("Average allocation trips %f", (float)_allocator_attempts/(float)_allocator_successes);
tty->print_cr("High Pressure Blocks = %d, Low Pressure Blocks = %d", _high_pressure, _low_pressure);
}
#endif // not PRODUCT