truffle: src/share/vm/opto/ifg.cpp comparison

comparison src/share/vm/opto/ifg.cpp @ 0:a61af66fc99e jdk7-b24

Initial load

author	duke
date	Sat, 01 Dec 2007 00:00:00 +0000
parents
children	ea18057223c4

comparison

equal deleted inserted replaced

--1:000000000000
+:a61af66fc99e
+/*
+* Copyright 1998-2006 Sun Microsystems, Inc.  All Rights Reserved.
+* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+*
+* This code is free software; you can redistribute it and/or modify it
+* 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/_ifg.cpp.incl"
+#define EXACT_PRESSURE 1
+//=============================================================================
+//------------------------------IFG--------------------------------------------
+PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
+}
+//------------------------------init-------------------------------------------
+void PhaseIFG::init( uint maxlrg ) {
+_maxlrg = maxlrg;
+_yanked = new (_arena) VectorSet(_arena);
+_is_square = false;
+// Make uninitialized adjacency lists
+_adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
+// Also make empty live range structures
+_lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
+memset(_lrgs,0,sizeof(LRG)*maxlrg);
+// Init all to empty
+for( uint i = 0; i < maxlrg; i++ ) {
+_adjs[i].initialize(maxlrg);
+_lrgs[i].Set_All();
+}
+}
+//------------------------------add--------------------------------------------
+// Add edge between vertices a & b.  These are sorted (triangular matrix),
+// then the smaller number is inserted in the larger numbered array.
+int PhaseIFG::add_edge( uint a, uint b ) {
+lrgs(a).invalid_degree();
+lrgs(b).invalid_degree();
+// Sort a and b, so that a is bigger
+assert( !_is_square, "only on triangular" );
+if( a < b ) { uint tmp = a; a = b; b = tmp; }
+return _adjs[a].insert( b );
+}
+//------------------------------add_vector-------------------------------------
+// Add an edge between 'a' and everything in the vector.
+void PhaseIFG::add_vector( uint a, IndexSet *vec ) {
+// IFG is triangular, so do the inserts where 'a' < 'b'.
+assert( !_is_square, "only on triangular" );
+IndexSet *adjs_a = &_adjs[a];
+if( !vec->count() ) return;
+IndexSetIterator elements(vec);
+uint neighbor;
+while ((neighbor = elements.next()) != 0) {
+add_edge( a, neighbor );
+}
+}
+//------------------------------test-------------------------------------------
+// Is there an edge between a and b?
+int PhaseIFG::test_edge( uint a, uint b ) const {
+// Sort a and b, so that a is larger
+assert( !_is_square, "only on triangular" );
+if( a < b ) { uint tmp = a; a = b; b = tmp; }
+return _adjs[a].member(b);
+}
+//------------------------------SquareUp---------------------------------------
+// Convert triangular matrix to square matrix
+void PhaseIFG::SquareUp() {
+assert( !_is_square, "only on triangular" );
+// Simple transpose
+for( uint i = 0; i < _maxlrg; i++ ) {
+IndexSetIterator elements(&_adjs[i]);
+uint datum;
+while ((datum = elements.next()) != 0) {
+_adjs[datum].insert( i );
+}
+}
+_is_square = true;
+}
+//------------------------------Compute_Effective_Degree-----------------------
+// Compute effective degree in bulk
+void PhaseIFG::Compute_Effective_Degree() {
+assert( _is_square, "only on square" );
+for( uint i = 0; i < _maxlrg; i++ )
+lrgs(i).set_degree(effective_degree(i));
+}
+//------------------------------test_edge_sq-----------------------------------
+int PhaseIFG::test_edge_sq( uint a, uint b ) const {
+assert( _is_square, "only on square" );
+// Swap, so that 'a' has the lesser count.  Then binary search is on
+// the smaller of a's list and b's list.
+if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; }
+//return _adjs[a].unordered_member(b);
+return _adjs[a].member(b);
+}
+//------------------------------Union------------------------------------------
+// Union edges of B into A
+void PhaseIFG::Union( uint a, uint b ) {
+assert( _is_square, "only on square" );
+IndexSet *A = &_adjs[a];
+IndexSetIterator b_elements(&_adjs[b]);
+uint datum;
+while ((datum = b_elements.next()) != 0) {
+if(A->insert(datum)) {
+_adjs[datum].insert(a);
+lrgs(a).invalid_degree();
+lrgs(datum).invalid_degree();
+}
+}
+}
+//------------------------------remove_node------------------------------------
+// Yank a Node and all connected edges from the IFG.  Return a
+// list of neighbors (edges) yanked.
+IndexSet *PhaseIFG::remove_node( uint a ) {
+assert( _is_square, "only on square" );
+assert( !_yanked->test(a), "" );
+_yanked->set(a);
+// I remove the LRG from all neighbors.
+IndexSetIterator elements(&_adjs[a]);
+LRG &lrg_a = lrgs(a);
+uint datum;
+while ((datum = elements.next()) != 0) {
+_adjs[datum].remove(a);
+lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) );
+}
+return neighbors(a);
+}
+//------------------------------re_insert--------------------------------------
+// Re-insert a yanked Node.
+void PhaseIFG::re_insert( uint a ) {
+assert( _is_square, "only on square" );
+assert( _yanked->test(a), "" );
+(*_yanked) >>= a;
+IndexSetIterator elements(&_adjs[a]);
+uint datum;
+while ((datum = elements.next()) != 0) {
+_adjs[datum].insert(a);
+lrgs(datum).invalid_degree();
+}
+}
+//------------------------------compute_degree---------------------------------
+// Compute the degree between 2 live ranges.  If both live ranges are
+// aligned-adjacent powers-of-2 then we use the MAX size.  If either is
+// mis-aligned (or for Fat-Projections, not-adjacent) then we have to
+// MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
+// this is so.
+int LRG::compute_degree( LRG &l ) const {
+int tmp;
+int num_regs = _num_regs;
+int nregs = l.num_regs();
+tmp =  (_fat_proj || l._fat_proj)     // either is a fat-proj?
+? (num_regs * nregs)                // then use product
+: MAX2(num_regs,nregs);             // else use max
+return tmp;
+}
+//------------------------------effective_degree-------------------------------
+// Compute effective degree for this live range.  If both live ranges are
+// aligned-adjacent powers-of-2 then we use the MAX size.  If either is
+// mis-aligned (or for Fat-Projections, not-adjacent) then we have to
+// MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
+// this is so.
+int PhaseIFG::effective_degree( uint lidx ) const {
+int eff = 0;
+int num_regs = lrgs(lidx).num_regs();
+int fat_proj = lrgs(lidx)._fat_proj;
+IndexSet *s = neighbors(lidx);
+IndexSetIterator elements(s);
+uint nidx;
+while((nidx = elements.next()) != 0) {
+LRG &lrgn = lrgs(nidx);
+int nregs = lrgn.num_regs();
+eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj?
+? (num_regs * nregs)              // then use product
+: MAX2(num_regs,nregs);           // else use max
+}
+return eff;
+}
+#ifndef PRODUCT
+//------------------------------dump-------------------------------------------
+void PhaseIFG::dump() const {
+tty->print_cr("-- Interference Graph --%s--",
+_is_square ? "square" : "triangular" );
+if( _is_square ) {
+for( uint i = 0; i < _maxlrg; i++ ) {
+tty->print( (*_yanked)[i] ? "XX " : "  ");
+tty->print("L%d: { ",i);
+IndexSetIterator elements(&_adjs[i]);
+uint datum;
+while ((datum = elements.next()) != 0) {
+tty->print("L%d ", datum);
+}
+tty->print_cr("}");
+}
+return;
+}
+// Triangular
+for( uint i = 0; i < _maxlrg; i++ ) {
+uint j;
+tty->print( (*_yanked)[i] ? "XX " : "  ");
+tty->print("L%d: { ",i);
+for( j = _maxlrg; j > i; j-- )
+if( test_edge(j - 1,i) ) {
+tty->print("L%d ",j - 1);
+}
+tty->print("| ");
+IndexSetIterator elements(&_adjs[i]);
+uint datum;
+while ((datum = elements.next()) != 0) {
+tty->print("L%d ", datum);
+}
+tty->print("}\n");
+}
+tty->print("\n");
+}
+//------------------------------stats------------------------------------------
+void PhaseIFG::stats() const {
+ResourceMark rm;
+int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2);
+memset( h_cnt, 0, sizeof(int)*_maxlrg*2 );
+uint i;
+for( i = 0; i < _maxlrg; i++ ) {
+h_cnt[neighbor_cnt(i)]++;
+}
+tty->print_cr("--Histogram of counts--");
+for( i = 0; i < _maxlrg*2; i++ )
+if( h_cnt[i] )
+tty->print("%d/%d ",i,h_cnt[i]);
+tty->print_cr("");
+}
+//------------------------------verify-----------------------------------------
+void PhaseIFG::verify( const PhaseChaitin *pc ) const {
+// IFG is square, sorted and no need for Find
+for( uint i = 0; i < _maxlrg; i++ ) {
+assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" );
+IndexSet *set = &_adjs[i];
+IndexSetIterator elements(set);
+uint idx;
+uint last = 0;
+while ((idx = elements.next()) != 0) {
+assert( idx != i, "Must have empty diagonal");
+assert( pc->Find_const(idx) == idx, "Must not need Find" );
+assert( _adjs[idx].member(i), "IFG not square" );
+assert( !(*_yanked)[idx], "No yanked neighbors" );
+assert( last < idx, "not sorted increasing");
+last = idx;
+}
+assert( !lrgs(i)._degree_valid ||
+effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong" );
+}
+}
+#endif
+//------------------------------interfere_with_live----------------------------
+// Interfere this register with everything currently live.  Use the RegMasks
+// to trim the set of possible interferences. Return a count of register-only
+// inteferences as an estimate of register pressure.
+void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) {
+uint retval = 0;
+// Interfere with everything live.
+const RegMask &rm = lrgs(r).mask();
+// Check for interference by checking overlap of regmasks.
+// Only interfere if acceptable register masks overlap.
+IndexSetIterator elements(liveout);
+uint l;
+while( (l = elements.next()) != 0 )
+if( rm.overlap( lrgs(l).mask() ) )
+_ifg->add_edge( r, l );
+}
+//------------------------------build_ifg_virtual------------------------------
+// Actually build the interference graph.  Uses virtual registers only, no
+// physical register masks.  This allows me to be very aggressive when
+// coalescing copies.  Some of this aggressiveness will have to be undone
+// later, but I'd rather get all the copies I can now (since unremoved copies
+// at this point can end up in bad places).  Copies I re-insert later I have
+// more opportunity to insert them in low-frequency locations.
+void PhaseChaitin::build_ifg_virtual( ) {
+// For all blocks (in any order) do...
+for( uint i=0; i<_cfg._num_blocks; i++ ) {
+Block *b = _cfg._blocks[i];
+IndexSet *liveout = _live->live(b);
+// The IFG is built by a single reverse pass over each basic block.
+// Starting with the known live-out set, we remove things that get
+// defined and add things that become live (essentially executing one
+// pass of a standard LIVE analysis). Just before a Node defines a value
+// (and removes it from the live-ness set) that value is certainly live.
+// The defined value interferes with everything currently live.  The
+// value is then removed from the live-ness set and it's inputs are
+// added to the live-ness set.
+for( uint j = b->end_idx() + 1; j > 1; j-- ) {
+Node *n = b->_nodes[j-1];
+// Get value being defined
+uint r = n2lidx(n);
+// Some special values do not allocate
+if( r ) {
+// Remove from live-out set
+liveout->remove(r);
+// Copies do not define a new value and so do not interfere.
+// Remove the copies source from the liveout set before interfering.
+uint idx = n->is_Copy();
+if( idx ) liveout->remove( n2lidx(n->in(idx)) );
+// Interfere with everything live
+interfere_with_live( r, liveout );
+}
+// Make all inputs live
+if( !n->is_Phi() ) {      // Phi function uses come from prior block
+for( uint k = 1; k < n->req(); k++ )
+liveout->insert( n2lidx(n->in(k)) );
+}
+// 2-address instructions always have the defined value live
+// on entry to the instruction, even though it is being defined
+// by the instruction.  We pretend a virtual copy sits just prior
+// to the instruction and kills the src-def'd register.
+// In other words, for 2-address instructions the defined value
+// interferes with all inputs.
+uint idx;
+if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) {
+const MachNode *mach = n->as_Mach();
+// Sometimes my 2-address ADDs are commuted in a bad way.
+// We generally want the USE-DEF register to refer to the
+// loop-varying quantity, to avoid a copy.
+uint op = mach->ideal_Opcode();
+// Check that mach->num_opnds() == 3 to ensure instruction is
+// not subsuming constants, effectively excludes addI_cin_imm
+// Can NOT swap for instructions like addI_cin_imm since it
+// is adding zero to yhi + carry and the second ideal-input
+// points to the result of adding low-halves.
+// Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm
+if( (op == Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) &&
+n->in(1)->bottom_type()->base() == Type::Int &&
+// See if the ADD is involved in a tight data loop the wrong way
+n->in(2)->is_Phi() &&
+n->in(2)->in(2) == n ) {
+Node *tmp = n->in(1);
+n->set_req( 1, n->in(2) );
+n->set_req( 2, tmp );
+}
+// Defined value interferes with all inputs
+uint lidx = n2lidx(n->in(idx));
+for( uint k = 1; k < n->req(); k++ ) {
+uint kidx = n2lidx(n->in(k));
+if( kidx != lidx )
+_ifg->add_edge( r, kidx );
+}
+}
+} // End of forall instructions in block
+} // End of forall blocks
+}
+//------------------------------count_int_pressure-----------------------------
+uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) {
+IndexSetIterator elements(liveout);
+uint lidx;
+uint cnt = 0;
+while ((lidx = elements.next()) != 0) {
+if( lrgs(lidx).mask().is_UP() &&
+lrgs(lidx).mask_size() &&
+!lrgs(lidx)._is_float &&
+lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) )
+cnt += lrgs(lidx).reg_pressure();
+}
+return cnt;
+}
+//------------------------------count_float_pressure---------------------------
+uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) {
+IndexSetIterator elements(liveout);
+uint lidx;
+uint cnt = 0;
+while ((lidx = elements.next()) != 0) {
+if( lrgs(lidx).mask().is_UP() &&
+lrgs(lidx).mask_size() &&
+lrgs(lidx)._is_float )
+cnt += lrgs(lidx).reg_pressure();
+}
+return cnt;
+}
+//------------------------------lower_pressure---------------------------------
+// Adjust register pressure down by 1.  Capture last hi-to-low transition,
+static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {
+if( lrg->mask().is_UP() && lrg->mask_size() ) {
+if( lrg->_is_float ) {
+pressure[1] -= lrg->reg_pressure();
+if( pressure[1] == (uint)FLOATPRESSURE ) {
+hrp_index[1] = where;
+#ifdef EXACT_PRESSURE
+if( pressure[1] > b->_freg_pressure )
+b->_freg_pressure = pressure[1]+1;
+#else
+b->_freg_pressure = (uint)FLOATPRESSURE+1;
+#endif
+}
+} else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
+pressure[0] -= lrg->reg_pressure();
+if( pressure[0] == (uint)INTPRESSURE   ) {
+hrp_index[0] = where;
+#ifdef EXACT_PRESSURE
+if( pressure[0] > b->_reg_pressure )
+b->_reg_pressure = pressure[0]+1;
+#else
+b->_reg_pressure = (uint)INTPRESSURE+1;
+#endif
+}
+}
+}
+}
+//------------------------------build_ifg_physical-----------------------------
+// Build the interference graph using physical registers when available.
+// That is, if 2 live ranges are simultaneously alive but in their acceptable
+// register sets do not overlap, then they do not interfere.
+uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
+NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )
+uint spill_reg = LRG::SPILL_REG;
+uint must_spill = 0;
+// For all blocks (in any order) do...
+for( uint i = 0; i < _cfg._num_blocks; i++ ) {
+Block *b = _cfg._blocks[i];
+// Clone (rather than smash in place) the liveout info, so it is alive
+// for the "collect_gc_info" phase later.
+IndexSet liveout(_live->live(b));
+uint last_inst = b->end_idx();
+// Compute last phi index
+uint last_phi;
+for( last_phi = 1; last_phi < last_inst; last_phi++ )
+if( !b->_nodes[last_phi]->is_Phi() )
+break;
+// Reset block's register pressure values for each ifg construction
+uint pressure[2], hrp_index[2];
+pressure[0] = pressure[1] = 0;
+hrp_index[0] = hrp_index[1] = last_inst+1;
+b->_reg_pressure = b->_freg_pressure = 0;
+// Liveout things are presumed live for the whole block.  We accumulate
+// 'area' accordingly.  If they get killed in the block, we'll subtract
+// the unused part of the block from the area.
+double cost = b->_freq * double(last_inst-last_phi);
+assert( cost >= 0, "negative spill cost" );
+IndexSetIterator elements(&liveout);
+uint lidx;
+while ((lidx = elements.next()) != 0) {
+LRG &lrg = lrgs(lidx);
+lrg._area += cost;
+// Compute initial register pressure
+if( lrg.mask().is_UP() && lrg.mask_size() ) {
+if( lrg._is_float ) {   // Count float pressure
+pressure[1] += lrg.reg_pressure();
+#ifdef EXACT_PRESSURE
+if( pressure[1] > b->_freg_pressure )
+b->_freg_pressure = pressure[1];
+#endif
+// Count int pressure, but do not count the SP, flags
+} else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
+pressure[0] += lrg.reg_pressure();
+#ifdef EXACT_PRESSURE
+if( pressure[0] > b->_reg_pressure )
+b->_reg_pressure = pressure[0];
+#endif
+}
+}
+}
+assert( pressure[0] == count_int_pressure  (&liveout), "" );
+assert( pressure[1] == count_float_pressure(&liveout), "" );
+// The IFG is built by a single reverse pass over each basic block.
+// Starting with the known live-out set, we remove things that get
+// defined and add things that become live (essentially executing one
+// pass of a standard LIVE analysis).  Just before a Node defines a value
+// (and removes it from the live-ness set) that value is certainly live.
+// The defined value interferes with everything currently live.  The
+// value is then removed from the live-ness set and it's inputs are added
+// to the live-ness set.
+uint j;
+for( j = last_inst + 1; j > 1; j-- ) {
+Node *n = b->_nodes[j - 1];
+// Get value being defined
+uint r = n2lidx(n);
+// Some special values do not allocate
+if( r ) {
+// A DEF normally costs block frequency; rematerialized values are
+// removed from the DEF sight, so LOWER costs here.
+lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq;
+// If it is not live, then this instruction is dead.  Probably caused
+// by spilling and rematerialization.  Who cares why, yank this baby.
+if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) {
+Node *def = n->in(0);
+if( !n->is_Proj() ||
+// Could also be a flags-projection of a dead ADD or such.
+(n2lidx(def) && !liveout.member(n2lidx(def)) ) ) {
+b->_nodes.remove(j - 1);
+if( lrgs(r)._def == n ) lrgs(r)._def = 0;
+n->disconnect_inputs(NULL);
+_cfg._bbs.map(n->_idx,NULL);
+n->replace_by(C->top());
+// Since yanking a Node from block, high pressure moves up one
+hrp_index[0]--;
+hrp_index[1]--;
+continue;
+}
+// Fat-projections kill many registers which cannot be used to
+// hold live ranges.
+if( lrgs(r)._fat_proj ) {
+// Count the int-only registers
+RegMask itmp = lrgs(r).mask();
+itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);
+int iregs = itmp.Size();
+#ifdef EXACT_PRESSURE
+if( pressure[0]+iregs > b->_reg_pressure )
+b->_reg_pressure = pressure[0]+iregs;
+#endif
+if( pressure[0]       <= (uint)INTPRESSURE &&
+pressure[0]+iregs >  (uint)INTPRESSURE ) {
+#ifndef EXACT_PRESSURE
+b->_reg_pressure = (uint)INTPRESSURE+1;
+#endif
+hrp_index[0] = j-1;
+}
+// Count the float-only registers
+RegMask ftmp = lrgs(r).mask();
+ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);
+int fregs = ftmp.Size();
+#ifdef EXACT_PRESSURE
+if( pressure[1]+fregs > b->_freg_pressure )
+b->_freg_pressure = pressure[1]+fregs;
+#endif
+if( pressure[1]       <= (uint)FLOATPRESSURE &&
+pressure[1]+fregs >  (uint)FLOATPRESSURE ) {
+#ifndef EXACT_PRESSURE
+b->_freg_pressure = (uint)FLOATPRESSURE+1;
+#endif
+hrp_index[1] = j-1;
+}
+}
+} else {                // Else it is live
+// A DEF also ends 'area' partway through the block.
+lrgs(r)._area -= cost;
+assert( lrgs(r)._area >= 0, "negative spill area" );
+// Insure high score for immediate-use spill copies so they get a color
+if( n->is_SpillCopy()
+&& lrgs(r)._def != NodeSentinel     // MultiDef live range can still split
+&& n->outcnt() == 1              // and use must be in this block
+&& _cfg._bbs[n->unique_out()->_idx] == b ) {
+// All single-use MachSpillCopy(s) that immediately precede their
+// use must color early.  If a longer live range steals their
+// color, the spill copy will split and may push another spill copy
+// further away resulting in an infinite spill-split-retry cycle.
+// Assigning a zero area results in a high score() and a good
+// location in the simplify list.
+//
+Node *single_use = n->unique_out();
+assert( b->find_node(single_use) >= j, "Use must be later in block");
+// Use can be earlier in block if it is a Phi, but then I should be a MultiDef
+// Find first non SpillCopy 'm' that follows the current instruction
+// (j - 1) is index for current instruction 'n'
+Node *m = n;
+for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; }
+if( m == single_use ) {
+lrgs(r)._area = 0.0;
+}
+}
+// Remove from live-out set
+if( liveout.remove(r) ) {
+// Adjust register pressure.
+// Capture last hi-to-lo pressure transition
+lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index );
+assert( pressure[0] == count_int_pressure  (&liveout), "" );
+assert( pressure[1] == count_float_pressure(&liveout), "" );
+}
+// Copies do not define a new value and so do not interfere.
+// Remove the copies source from the liveout set before interfering.
+uint idx = n->is_Copy();
+if( idx ) {
+uint x = n2lidx(n->in(idx));
+if( liveout.remove( x ) ) {
+lrgs(x)._area -= cost;
+// Adjust register pressure.
+lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index );
+assert( pressure[0] == count_int_pressure  (&liveout), "" );
+assert( pressure[1] == count_float_pressure(&liveout), "" );
+}
+}
+} // End of if live or not
+// Interfere with everything live.  If the defined value must
+// go in a particular register, just remove that register from
+// all conflicting parties and avoid the interference.
+// Make exclusions for rematerializable defs.  Since rematerializable
+// DEFs are not bound but the live range is, some uses must be bound.
+// If we spill live range 'r', it can rematerialize at each use site
+// according to its bindings.
+const RegMask &rmask = lrgs(r).mask();
+if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) {
+// Smear odd bits; leave only aligned pairs of bits.
+RegMask r2mask = rmask;
+r2mask.SmearToPairs();
+// Check for common case
+int r_size = lrgs(r).num_regs();
+OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical;
+IndexSetIterator elements(&liveout);
+uint l;
+while ((l = elements.next()) != 0) {
+LRG &lrg = lrgs(l);
+// If 'l' must spill already, do not further hack his bits.
+// He'll get some interferences and be forced to spill later.
+if( lrg._must_spill ) continue;
+// Remove bound register(s) from 'l's choices
+RegMask old = lrg.mask();
+uint old_size = lrg.mask_size();
+// Remove the bits from LRG 'r' from LRG 'l' so 'l' no
+// longer interferes with 'r'.  If 'l' requires aligned
+// adjacent pairs, subtract out bit pairs.
+if( lrg.num_regs() == 2 && !lrg._fat_proj ) {
+lrg.SUBTRACT( r2mask );
+lrg.compute_set_mask_size();
+} else if( r_size != 1 ) {
+lrg.SUBTRACT( rmask );
+lrg.compute_set_mask_size();
+} else {            // Common case: size 1 bound removal
+if( lrg.mask().Member(r_reg) ) {
+lrg.Remove(r_reg);
+lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1);
+}
+}
+// If 'l' goes completely dry, it must spill.
+if( lrg.not_free() ) {
+// Give 'l' some kind of reasonable mask, so he picks up
+// interferences (and will spill later).
+lrg.set_mask( old );
+lrg.set_mask_size(old_size);
+must_spill++;
+lrg._must_spill = 1;
+lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
+}
+}
+} // End of if bound
+// Now interference with everything that is live and has
+// compatible register sets.
+interfere_with_live(r,&liveout);
+} // End of if normal register-allocated value
+cost -= b->_freq;         // Area remaining in the block
+if( cost < 0.0 ) cost = 0.0;  // Cost goes negative in the Phi area
+// Make all inputs live
+if( !n->is_Phi() ) {      // Phi function uses come from prior block
+JVMState* jvms = n->jvms();
+uint debug_start = jvms ? jvms->debug_start() : 999999;
+// Start loop at 1 (skip control edge) for most Nodes.
+// SCMemProj's might be the sole use of a StoreLConditional.
+// While StoreLConditionals set memory (the SCMemProj use)
+// they also def flags; if that flag def is unused the
+// allocator sees a flag-setting instruction with no use of
+// the flags and assumes it's dead.  This keeps the (useless)
+// flag-setting behavior alive while also keeping the (useful)
+// memory update effect.
+for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) {
+Node *def = n->in(k);
+uint x = n2lidx(def);
+if( !x ) continue;
+LRG &lrg = lrgs(x);
+// No use-side cost for spilling debug info
+if( k < debug_start )
+// A USE costs twice block frequency (once for the Load, once
+// for a Load-delay).  Rematerialized uses only cost once.
+lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq));
+// It is live now
+if( liveout.insert( x ) ) {
+// Newly live things assumed live from here to top of block
+lrg._area += cost;
+// Adjust register pressure
+if( lrg.mask().is_UP() && lrg.mask_size() ) {
+if( lrg._is_float ) {
+pressure[1] += lrg.reg_pressure();
+#ifdef EXACT_PRESSURE
+if( pressure[1] > b->_freg_pressure )
+b->_freg_pressure = pressure[1];
+#endif
+} else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
+pressure[0] += lrg.reg_pressure();
+#ifdef EXACT_PRESSURE
+if( pressure[0] > b->_reg_pressure )
+b->_reg_pressure = pressure[0];
+#endif
+}
+}
+assert( pressure[0] == count_int_pressure  (&liveout), "" );
+assert( pressure[1] == count_float_pressure(&liveout), "" );
+}
+assert( lrg._area >= 0, "negative spill area" );
+}
+}
+} // End of reverse pass over all instructions in block
+// If we run off the top of the block with high pressure and
+// never see a hi-to-low pressure transition, just record that
+// the whole block is high pressure.
+if( pressure[0] > (uint)INTPRESSURE   ) {
+hrp_index[0] = 0;
+#ifdef EXACT_PRESSURE
+if( pressure[0] > b->_reg_pressure )
+b->_reg_pressure = pressure[0];
+#else
+b->_reg_pressure = (uint)INTPRESSURE+1;
+#endif
+}
+if( pressure[1] > (uint)FLOATPRESSURE ) {
+hrp_index[1] = 0;
+#ifdef EXACT_PRESSURE
+if( pressure[1] > b->_freg_pressure )
+b->_freg_pressure = pressure[1];
+#else
+b->_freg_pressure = (uint)FLOATPRESSURE+1;
+#endif
+}
+// Compute high pressure indice; avoid landing in the middle of projnodes
+j = hrp_index[0];
+if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
+Node *cur = b->_nodes[j];
+while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
+j--;
+cur = b->_nodes[j];
+}
+}
+b->_ihrp_index = j;
+j = hrp_index[1];
+if( j < b->_nodes.size() && j < b->end_idx()+1 ) {
+Node *cur = b->_nodes[j];
+while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {
+j--;
+cur = b->_nodes[j];
+}
+}
+b->_fhrp_index = j;
+#ifndef PRODUCT
+// Gather Register Pressure Statistics
+if( PrintOptoStatistics ) {
+if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE )
+_high_pressure++;
+else
+_low_pressure++;
+}
+#endif
+} // End of for all blocks
+return must_spill;
+}

Mercurial > hg > truffle

comparison src/share/vm/opto/ifg.cpp @ 0:a61af66fc99e jdk7-b24