diff -r 000000000000 -r a61af66fc99e src/share/vm/opto/ifg.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/opto/ifg.cpp Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,813 @@ +/* + * 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; +}