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