/*
* 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "compiler/compileLog.hpp"
#include "compiler/oopMap.hpp"
#include "memory/allocation.inline.hpp"
#include "opto/addnode.hpp"
#include "opto/callnode.hpp"
#include "opto/cfgnode.hpp"
#include "opto/chaitin.hpp"
#include "opto/coalesce.hpp"
#include "opto/connode.hpp"
#include "opto/idealGraphPrinter.hpp"
#include "opto/indexSet.hpp"
#include "opto/machnode.hpp"
#include "opto/memnode.hpp"
#include "opto/opcodes.hpp"
#include "opto/rootnode.hpp"
//=============================================================================
#ifndef PRODUCT
if( _msize_valid ) {
} else {
}
if( is_multidef() ) {
}
}
}
// 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---------------------------------------
}
}
}
//------------------------------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++ ) {
}
}
}
// 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();
#ifdef ASSERT
// Veify the graph before RA.
verify(&live_arena);
#endif
{
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
// 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;
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
verify(&live_arena, true);
#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;
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
verify(&live_arena, true);
#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
#ifdef ASSERT
// Veify the graph after RA.
verify(&live_arena);
#endif
// 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
#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?
set_bad(i);
} else { // Must be a register-set
// Live ranges record the highest register in their mask.
// We want the low register for the AD file writer's convenience.
// We have to use pair [lo,lo+1] even for wide vectors because
// the rest of code generation works only with pairs. It is safe
// since for registers encoding only 'lo' is used.
// Second reg from pair is used in ScheduleAndBundle on SPARC where
// vector max size is 8 which corresponds to registers pair.
// It is also used in BuildOopMaps but oop operations are not
// vectorized.
} else { // Misaligned; extract 2 bits
}
}
} else {
set_bad(i);
}
}
// Done!
}
//------------------------------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
"oops must be in Op_RegP's" );
// Check for vector live range (only if vector register is used).
// On SPARC vector uses RegD which could be misaligned so it is not
// processes as vector in RA.
"vector must be in vector registers");
// Check for bound register masks
// Check for maximum frequency value
// 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
} 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;
case Op_VecS:
break;
case Op_VecD:
break;
case Op_VecX:
break;
case Op_VecY:
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
"vector must be in vector registers");
// 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!
#ifdef ASSERT
if (is_vect) {
}
#endif
}
// 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 (!is_vect && !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.clear_to_sets();
}
}
}
}
//------------------------------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.
#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
}
//------------------------------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
// 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.
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 || VerifyRegisterAllocator ) {
}
#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.
// Ties also happen when live ranges are defined and used only inside
// one block. In which case their area is 0 and score set to max.
// In such case choose bound live range over unbound to free registers
// or with smaller cost 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
}
//------------------------------is_legal_reg-----------------------------------
// Is 'reg' register legal for 'lrg'?
// RA uses OptoReg which represent the highest element of a registers set.
// For example, vectorX (128bit) on x86 uses [XMM,XMMb,XMMc,XMMd] set
// in which XMMd is used by RA to represent such vectors. A double value
// uses [XMM,XMMb] pairs and XMMb is used by RA for it.
// The register mask uses largest bits set of overlapping register sets.
// On x86 with AVX it uses 8 bits for each XMM registers set.
//
// The 'lrg' already has cleared-to-set register mask (done in Select()
// before calling choose_color()). Passing mask.Member(reg) check above
// indicates that the size (num_regs) of 'reg' set is less or equal to
// 'lrg' set size.
// For set size 1 any register which is member of 'lrg' mask is legal.
return true;
// For larger sets only an aligned register with the same set size is legal.
return true;
}
return false;
}
//------------------------------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
return reg;
}
}
// If no bias info exists, just go with the register selection ordering
// Find an aligned set
}
// 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.
// 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->clear_to_sets();
}
// 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
// chosen. Restrict the mask to just what was picked.
// For vectors and pairs, also insert the low bit of the pair
for (int i = 1; i < n_regs; i++)
} 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.
// 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" );
// 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!
// Initialize it once and make it shared:
// set control to _root and place it into Start block
// (where top() node is placed).
}
}
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;
}
}
}
// 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------------------------------
// Dump lo-degree list
// Dump lo-stk-degree list
// Dump lo-degree list
}
//------------------------------dump_simplified--------------------------------
}
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 {
else
// Hah! We have a bound machine register
} else {
}
}
}
}
//----------------------dump_for_spill_split_recycle--------------------------
// Display which live ranges need to be split and the allocator's state
}
}
dump();
}
}
//------------------------------dump_frame------------------------------------
// 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
OptoReg::Name begin_in_preserve = OptoReg::add(_matcher._old_SP, -(int)C->in_preserve_stack_slots());
if (return_addr == reg) {
} else if (reg >= begin_in_preserve) {
// Preserved slots are present on x86
else
} 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 (!defs_only) {
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-------------------------------
#ifndef PRODUCT
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