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