1 /*

     2  * Copyright 1998-2006 Sun Microsystems, Inc.  All Rights Reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 #include "incls/_precompiled.incl"

    26 #include "incls/_ifg.cpp.incl"

    27 

    28 #define EXACT_PRESSURE 1

    29 

    30 //=============================================================================

    31 //------------------------------IFG--------------------------------------------

    32 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {

    33 }

    34 

    35 //------------------------------init-------------------------------------------

    36 void PhaseIFG::init( uint maxlrg ) {

    37   _maxlrg = maxlrg;

    38   _yanked = new (_arena) VectorSet(_arena);

    39   _is_square = false;

    40   // Make uninitialized adjacency lists

    41   _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);

    42   // Also make empty live range structures

    43   _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );

    44   memset(_lrgs,0,sizeof(LRG)*maxlrg);

    45   // Init all to empty

    46   for( uint i = 0; i < maxlrg; i++ ) {

    47     _adjs[i].initialize(maxlrg);

    48     _lrgs[i].Set_All();

    49   }

    50 }

    51 

    52 //------------------------------add--------------------------------------------

    53 // Add edge between vertices a & b.  These are sorted (triangular matrix),

    54 // then the smaller number is inserted in the larger numbered array.

    55 int PhaseIFG::add_edge( uint a, uint b ) {

    56   lrgs(a).invalid_degree();

    57   lrgs(b).invalid_degree();

    58   // Sort a and b, so that a is bigger

    59   assert( !_is_square, "only on triangular" );

    60   if( a < b ) { uint tmp = a; a = b; b = tmp; }

    61   return _adjs[a].insert( b );

    62 }

    63 

    64 //------------------------------add_vector-------------------------------------

    65 // Add an edge between 'a' and everything in the vector.

    66 void PhaseIFG::add_vector( uint a, IndexSet *vec ) {

    67   // IFG is triangular, so do the inserts where 'a' < 'b'.

    68   assert( !_is_square, "only on triangular" );

    69   IndexSet *adjs_a = &_adjs[a];

    70   if( !vec->count() ) return;

    71 

    72   IndexSetIterator elements(vec);

    73   uint neighbor;

    74   while ((neighbor = elements.next()) != 0) {

    75     add_edge( a, neighbor );

    76   }

    77 }

    78 

    79 //------------------------------test-------------------------------------------

    80 // Is there an edge between a and b?

    81 int PhaseIFG::test_edge( uint a, uint b ) const {

    82   // Sort a and b, so that a is larger

    83   assert( !_is_square, "only on triangular" );

    84   if( a < b ) { uint tmp = a; a = b; b = tmp; }

    85   return _adjs[a].member(b);

    86 }

    87 

    88 //------------------------------SquareUp---------------------------------------

    89 // Convert triangular matrix to square matrix

    90 void PhaseIFG::SquareUp() {

    91   assert( !_is_square, "only on triangular" );

    92 

    93   // Simple transpose

    94   for( uint i = 0; i < _maxlrg; i++ ) {

    95     IndexSetIterator elements(&_adjs[i]);

    96     uint datum;

    97     while ((datum = elements.next()) != 0) {

    98       _adjs[datum].insert( i );

    99     }

   100   }

   101   _is_square = true;

   102 }

   103 

   104 //------------------------------Compute_Effective_Degree-----------------------

   105 // Compute effective degree in bulk

   106 void PhaseIFG::Compute_Effective_Degree() {

   107   assert( _is_square, "only on square" );

   108 

   109   for( uint i = 0; i < _maxlrg; i++ )

   110     lrgs(i).set_degree(effective_degree(i));

   111 }

   112 

   113 //------------------------------test_edge_sq-----------------------------------

   114 int PhaseIFG::test_edge_sq( uint a, uint b ) const {

   115   assert( _is_square, "only on square" );

   116   // Swap, so that 'a' has the lesser count.  Then binary search is on

   117   // the smaller of a's list and b's list.

   118   if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; }

   119   //return _adjs[a].unordered_member(b);

   120   return _adjs[a].member(b);

   121 }

   122 

   123 //------------------------------Union------------------------------------------

   124 // Union edges of B into A

   125 void PhaseIFG::Union( uint a, uint b ) {

   126   assert( _is_square, "only on square" );

   127   IndexSet *A = &_adjs[a];

   128   IndexSetIterator b_elements(&_adjs[b]);

   129   uint datum;

   130   while ((datum = b_elements.next()) != 0) {

   131     if(A->insert(datum)) {

   132       _adjs[datum].insert(a);

   133       lrgs(a).invalid_degree();

   134       lrgs(datum).invalid_degree();

   135     }

   136   }

   137 }

   138 

   139 //------------------------------remove_node------------------------------------

   140 // Yank a Node and all connected edges from the IFG.  Return a

   141 // list of neighbors (edges) yanked.

   142 IndexSet *PhaseIFG::remove_node( uint a ) {

   143   assert( _is_square, "only on square" );

   144   assert( !_yanked->test(a), "" );

   145   _yanked->set(a);

   146 

   147   // I remove the LRG from all neighbors.

   148   IndexSetIterator elements(&_adjs[a]);

   149   LRG &lrg_a = lrgs(a);

   150   uint datum;

   151   while ((datum = elements.next()) != 0) {

   152     _adjs[datum].remove(a);

   153     lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) );

   154   }

   155   return neighbors(a);

   156 }

   157 

   158 //------------------------------re_insert--------------------------------------

   159 // Re-insert a yanked Node.

   160 void PhaseIFG::re_insert( uint a ) {

   161   assert( _is_square, "only on square" );

   162   assert( _yanked->test(a), "" );

   163   (*_yanked) >>= a;

   164 

   165   IndexSetIterator elements(&_adjs[a]);

   166   uint datum;

   167   while ((datum = elements.next()) != 0) {

   168     _adjs[datum].insert(a);

   169     lrgs(datum).invalid_degree();

   170   }

   171 }

   172 

   173 //------------------------------compute_degree---------------------------------

   174 // Compute the degree between 2 live ranges.  If both live ranges are

   175 // aligned-adjacent powers-of-2 then we use the MAX size.  If either is

   176 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to

   177 // MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why

   178 // this is so.

   179 int LRG::compute_degree( LRG &l ) const {

   180   int tmp;

   181   int num_regs = _num_regs;

   182   int nregs = l.num_regs();

   183   tmp =  (_fat_proj || l._fat_proj)     // either is a fat-proj?

   184     ? (num_regs * nregs)                // then use product

   185     : MAX2(num_regs,nregs);             // else use max

   186   return tmp;

   187 }

   188 

   189 //------------------------------effective_degree-------------------------------

   190 // Compute effective degree for this live range.  If both live ranges are

   191 // aligned-adjacent powers-of-2 then we use the MAX size.  If either is

   192 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to

   193 // MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why

   194 // this is so.

   195 int PhaseIFG::effective_degree( uint lidx ) const {

   196   int eff = 0;

   197   int num_regs = lrgs(lidx).num_regs();

   198   int fat_proj = lrgs(lidx)._fat_proj;

   199   IndexSet *s = neighbors(lidx);

   200   IndexSetIterator elements(s);

   201   uint nidx;

   202   while((nidx = elements.next()) != 0) {

   203     LRG &lrgn = lrgs(nidx);

   204     int nregs = lrgn.num_regs();

   205     eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj?

   206       ? (num_regs * nregs)              // then use product

   207       : MAX2(num_regs,nregs);           // else use max

   208   }

   209   return eff;

   210 }

   211 

   212 

   213 #ifndef PRODUCT

   214 //------------------------------dump-------------------------------------------

   215 void PhaseIFG::dump() const {

   216   tty->print_cr("-- Interference Graph --%s--",

   217                 _is_square ? "square" : "triangular" );

   218   if( _is_square ) {

   219     for( uint i = 0; i < _maxlrg; i++ ) {

   220       tty->print( (*_yanked)[i] ? "XX " : "  ");

   221       tty->print("L%d: { ",i);

   222       IndexSetIterator elements(&_adjs[i]);

   223       uint datum;

   224       while ((datum = elements.next()) != 0) {

   225         tty->print("L%d ", datum);

   226       }

   227       tty->print_cr("}");

   228 

   229     }

   230     return;

   231   }

   232 

   233   // Triangular

   234   for( uint i = 0; i < _maxlrg; i++ ) {

   235     uint j;

   236     tty->print( (*_yanked)[i] ? "XX " : "  ");

   237     tty->print("L%d: { ",i);

   238     for( j = _maxlrg; j > i; j-- )

   239       if( test_edge(j - 1,i) ) {

   240         tty->print("L%d ",j - 1);

   241       }

   242     tty->print("| ");

   243     IndexSetIterator elements(&_adjs[i]);

   244     uint datum;

   245     while ((datum = elements.next()) != 0) {

   246       tty->print("L%d ", datum);

   247     }

   248     tty->print("}\n");

   249   }

   250   tty->print("\n");

   251 }

   252 

   253 //------------------------------stats------------------------------------------

   254 void PhaseIFG::stats() const {

   255   ResourceMark rm;

   256   int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2);

   257   memset( h_cnt, 0, sizeof(int)*_maxlrg*2 );

   258   uint i;

   259   for( i = 0; i < _maxlrg; i++ ) {

   260     h_cnt[neighbor_cnt(i)]++;

   261   }

   262   tty->print_cr("--Histogram of counts--");

   263   for( i = 0; i < _maxlrg*2; i++ )

   264     if( h_cnt[i] )

   265       tty->print("%d/%d ",i,h_cnt[i]);

   266   tty->print_cr("");

   267 }

   268 

   269 //------------------------------verify-----------------------------------------

   270 void PhaseIFG::verify( const PhaseChaitin *pc ) const {

   271   // IFG is square, sorted and no need for Find

   272   for( uint i = 0; i < _maxlrg; i++ ) {

   273     assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" );

   274     IndexSet *set = &_adjs[i];

   275     IndexSetIterator elements(set);

   276     uint idx;

   277     uint last = 0;

   278     while ((idx = elements.next()) != 0) {

   279       assert( idx != i, "Must have empty diagonal");

   280       assert( pc->Find_const(idx) == idx, "Must not need Find" );

   281       assert( _adjs[idx].member(i), "IFG not square" );

   282       assert( !(*_yanked)[idx], "No yanked neighbors" );

   283       assert( last < idx, "not sorted increasing");

   284       last = idx;

   285     }

   286     assert( !lrgs(i)._degree_valid ||

   287             effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong" );

   288   }

   289 }

   290 #endif

   291 

   292 //------------------------------interfere_with_live----------------------------

   293 // Interfere this register with everything currently live.  Use the RegMasks

   294 // to trim the set of possible interferences. Return a count of register-only

   295 // inteferences as an estimate of register pressure.

   296 void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) {

   297   uint retval = 0;

   298   // Interfere with everything live.

   299   const RegMask &rm = lrgs(r).mask();

   300   // Check for interference by checking overlap of regmasks.

   301   // Only interfere if acceptable register masks overlap.

   302   IndexSetIterator elements(liveout);

   303   uint l;

   304   while( (l = elements.next()) != 0 )

   305     if( rm.overlap( lrgs(l).mask() ) )

   306       _ifg->add_edge( r, l );

   307 }

   308 

   309 //------------------------------build_ifg_virtual------------------------------

   310 // Actually build the interference graph.  Uses virtual registers only, no

   311 // physical register masks.  This allows me to be very aggressive when

   312 // coalescing copies.  Some of this aggressiveness will have to be undone

   313 // later, but I'd rather get all the copies I can now (since unremoved copies

   314 // at this point can end up in bad places).  Copies I re-insert later I have

   315 // more opportunity to insert them in low-frequency locations.

   316 void PhaseChaitin::build_ifg_virtual( ) {

   317 

   318   // For all blocks (in any order) do...

   319   for( uint i=0; i<_cfg._num_blocks; i++ ) {

   320     Block *b = _cfg._blocks[i];

   321     IndexSet *liveout = _live->live(b);

   322 

   323     // The IFG is built by a single reverse pass over each basic block.

   324     // Starting with the known live-out set, we remove things that get

   325     // defined and add things that become live (essentially executing one

   326     // pass of a standard LIVE analysis). Just before a Node defines a value

   327     // (and removes it from the live-ness set) that value is certainly live.

   328     // The defined value interferes with everything currently live.  The

   329     // value is then removed from the live-ness set and it's inputs are

   330     // added to the live-ness set.

   331     for( uint j = b->end_idx() + 1; j > 1; j-- ) {

   332       Node *n = b->_nodes[j-1];

   333 

   334       // Get value being defined

   335       uint r = n2lidx(n);

   336 

   337       // Some special values do not allocate

   338       if( r ) {

   339 

   340         // Remove from live-out set

   341         liveout->remove(r);

   342 

   343         // Copies do not define a new value and so do not interfere.

   344         // Remove the copies source from the liveout set before interfering.

   345         uint idx = n->is_Copy();

   346         if( idx ) liveout->remove( n2lidx(n->in(idx)) );

   347 

   348         // Interfere with everything live

   349         interfere_with_live( r, liveout );

   350       }

   351 

   352       // Make all inputs live

   353       if( !n->is_Phi() ) {      // Phi function uses come from prior block

   354         for( uint k = 1; k < n->req(); k++ )

   355           liveout->insert( n2lidx(n->in(k)) );

   356       }

   357 

   358       // 2-address instructions always have the defined value live

   359       // on entry to the instruction, even though it is being defined

   360       // by the instruction.  We pretend a virtual copy sits just prior

   361       // to the instruction and kills the src-def'd register.

   362       // In other words, for 2-address instructions the defined value

   363       // interferes with all inputs.

   364       uint idx;

   365       if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) {

   366         const MachNode *mach = n->as_Mach();

   367         // Sometimes my 2-address ADDs are commuted in a bad way.

   368         // We generally want the USE-DEF register to refer to the

   369         // loop-varying quantity, to avoid a copy.

   370         uint op = mach->ideal_Opcode();

   371         // Check that mach->num_opnds() == 3 to ensure instruction is

   372         // not subsuming constants, effectively excludes addI_cin_imm

   373         // Can NOT swap for instructions like addI_cin_imm since it

   374         // is adding zero to yhi + carry and the second ideal-input

   375         // points to the result of adding low-halves.

   376         // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm

   377         if( (op == Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) &&

   378             n->in(1)->bottom_type()->base() == Type::Int &&

   379             // See if the ADD is involved in a tight data loop the wrong way

   380             n->in(2)->is_Phi() &&

   381             n->in(2)->in(2) == n ) {

   382           Node *tmp = n->in(1);

   383           n->set_req( 1, n->in(2) );

   384           n->set_req( 2, tmp );

   385         }

   386         // Defined value interferes with all inputs

   387         uint lidx = n2lidx(n->in(idx));

   388         for( uint k = 1; k < n->req(); k++ ) {

   389           uint kidx = n2lidx(n->in(k));

   390           if( kidx != lidx )

   391             _ifg->add_edge( r, kidx );

   392         }

   393       }

   394     } // End of forall instructions in block

   395   } // End of forall blocks

   396 }

   397 

   398 //------------------------------count_int_pressure-----------------------------

   399 uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) {

   400   IndexSetIterator elements(liveout);

   401   uint lidx;

   402   uint cnt = 0;

   403   while ((lidx = elements.next()) != 0) {

   404     if( lrgs(lidx).mask().is_UP() &&

   405         lrgs(lidx).mask_size() &&

   406         !lrgs(lidx)._is_float &&

   407         lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) )

   408       cnt += lrgs(lidx).reg_pressure();

   409   }

   410   return cnt;

   411 }

   412 

   413 //------------------------------count_float_pressure---------------------------

   414 uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) {

   415   IndexSetIterator elements(liveout);

   416   uint lidx;

   417   uint cnt = 0;

   418   while ((lidx = elements.next()) != 0) {

   419     if( lrgs(lidx).mask().is_UP() &&

   420         lrgs(lidx).mask_size() &&

   421         lrgs(lidx)._is_float )

   422       cnt += lrgs(lidx).reg_pressure();

   423   }

   424   return cnt;

   425 }

   426 

   427 //------------------------------lower_pressure---------------------------------

   428 // Adjust register pressure down by 1.  Capture last hi-to-low transition,

   429 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {

   430   if( lrg->mask().is_UP() && lrg->mask_size() ) {

   431     if( lrg->_is_float ) {

   432       pressure[1] -= lrg->reg_pressure();

   433       if( pressure[1] == (uint)FLOATPRESSURE ) {

   434         hrp_index[1] = where;

   435 #ifdef EXACT_PRESSURE

   436       if( pressure[1] > b->_freg_pressure )

   437         b->_freg_pressure = pressure[1]+1;

   438 #else

   439         b->_freg_pressure = (uint)FLOATPRESSURE+1;

   440 #endif

   441       }

   442     } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {

   443       pressure[0] -= lrg->reg_pressure();

   444       if( pressure[0] == (uint)INTPRESSURE   ) {

   445         hrp_index[0] = where;

   446 #ifdef EXACT_PRESSURE

   447       if( pressure[0] > b->_reg_pressure )

   448         b->_reg_pressure = pressure[0]+1;

   449 #else

   450         b->_reg_pressure = (uint)INTPRESSURE+1;

   451 #endif

   452       }

   453     }

   454   }

   455 }

   456 

   457 //------------------------------build_ifg_physical-----------------------------

   458 // Build the interference graph using physical registers when available.

   459 // That is, if 2 live ranges are simultaneously alive but in their acceptable

   460 // register sets do not overlap, then they do not interfere.

   461 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {

   462   NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )

   463 

   464   uint spill_reg = LRG::SPILL_REG;

   465   uint must_spill = 0;

   466 

   467   // For all blocks (in any order) do...

   468   for( uint i = 0; i < _cfg._num_blocks; i++ ) {

   469     Block *b = _cfg._blocks[i];

   470     // Clone (rather than smash in place) the liveout info, so it is alive

   471     // for the "collect_gc_info" phase later.

   472     IndexSet liveout(_live->live(b));

   473     uint last_inst = b->end_idx();

   474     // Compute last phi index

   475     uint last_phi;

   476     for( last_phi = 1; last_phi < last_inst; last_phi++ )

   477       if( !b->_nodes[last_phi]->is_Phi() )

   478         break;

   479 

   480     // Reset block's register pressure values for each ifg construction

   481     uint pressure[2], hrp_index[2];

   482     pressure[0] = pressure[1] = 0;

   483     hrp_index[0] = hrp_index[1] = last_inst+1;

   484     b->_reg_pressure = b->_freg_pressure = 0;

   485     // Liveout things are presumed live for the whole block.  We accumulate

   486     // 'area' accordingly.  If they get killed in the block, we'll subtract

   487     // the unused part of the block from the area.

   488     double cost = b->_freq * double(last_inst-last_phi);

   489     assert( cost >= 0, "negative spill cost" );

   490     IndexSetIterator elements(&liveout);

   491     uint lidx;

   492     while ((lidx = elements.next()) != 0) {

   493       LRG &lrg = lrgs(lidx);

   494       lrg._area += cost;

   495       // Compute initial register pressure

   496       if( lrg.mask().is_UP() && lrg.mask_size() ) {

   497         if( lrg._is_float ) {   // Count float pressure

   498           pressure[1] += lrg.reg_pressure();

   499 #ifdef EXACT_PRESSURE

   500           if( pressure[1] > b->_freg_pressure )

   501             b->_freg_pressure = pressure[1];

   502 #endif

   503           // Count int pressure, but do not count the SP, flags

   504         } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {

   505           pressure[0] += lrg.reg_pressure();

   506 #ifdef EXACT_PRESSURE

   507           if( pressure[0] > b->_reg_pressure )

   508             b->_reg_pressure = pressure[0];

   509 #endif

   510         }

   511       }

   512     }

   513     assert( pressure[0] == count_int_pressure  (&liveout), "" );

   514     assert( pressure[1] == count_float_pressure(&liveout), "" );

   515 

   516     // The IFG is built by a single reverse pass over each basic block.

   517     // Starting with the known live-out set, we remove things that get

   518     // defined and add things that become live (essentially executing one

   519     // pass of a standard LIVE analysis).  Just before a Node defines a value

   520     // (and removes it from the live-ness set) that value is certainly live.

   521     // The defined value interferes with everything currently live.  The

   522     // value is then removed from the live-ness set and it's inputs are added

   523     // to the live-ness set.

   524     uint j;

   525     for( j = last_inst + 1; j > 1; j-- ) {

   526       Node *n = b->_nodes[j - 1];

   527 

   528       // Get value being defined

   529       uint r = n2lidx(n);

   530 

   531       // Some special values do not allocate

   532       if( r ) {

   533         // A DEF normally costs block frequency; rematerialized values are

   534         // removed from the DEF sight, so LOWER costs here.

   535         lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq;

   536 

   537         // If it is not live, then this instruction is dead.  Probably caused

   538         // by spilling and rematerialization.  Who cares why, yank this baby.

   539         if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) {

   540           Node *def = n->in(0);

   541           if( !n->is_Proj() ||

   542               // Could also be a flags-projection of a dead ADD or such.

   543               (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) {

   544             b->_nodes.remove(j - 1);

   545             if( lrgs(r)._def == n ) lrgs(r)._def = 0;

   546             n->disconnect_inputs(NULL);

   547             _cfg._bbs.map(n->_idx,NULL);

   548             n->replace_by(C->top());

   549             // Since yanking a Node from block, high pressure moves up one

   550             hrp_index[0]--;

   551             hrp_index[1]--;

   552             continue;

   553           }

   554 

   555           // Fat-projections kill many registers which cannot be used to

   556           // hold live ranges.

   557           if( lrgs(r)._fat_proj ) {

   558             // Count the int-only registers

   559             RegMask itmp = lrgs(r).mask();

   560             itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);

   561             int iregs = itmp.Size();

   562 #ifdef EXACT_PRESSURE

   563             if( pressure[0]+iregs > b->_reg_pressure )

   564               b->_reg_pressure = pressure[0]+iregs;

   565 #endif

   566             if( pressure[0]       <= (uint)INTPRESSURE &&

   567                 pressure[0]+iregs >  (uint)INTPRESSURE ) {

   568 #ifndef EXACT_PRESSURE

   569               b->_reg_pressure = (uint)INTPRESSURE+1;

   570 #endif

   571               hrp_index[0] = j-1;

   572             }

   573             // Count the float-only registers

   574             RegMask ftmp = lrgs(r).mask();

   575             ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);

   576             int fregs = ftmp.Size();

   577 #ifdef EXACT_PRESSURE

   578             if( pressure[1]+fregs > b->_freg_pressure )

   579               b->_freg_pressure = pressure[1]+fregs;

   580 #endif

   581             if( pressure[1]       <= (uint)FLOATPRESSURE &&

   582                 pressure[1]+fregs >  (uint)FLOATPRESSURE ) {

   583 #ifndef EXACT_PRESSURE

   584               b->_freg_pressure = (uint)FLOATPRESSURE+1;

   585 #endif

   586               hrp_index[1] = j-1;

   587             }

   588           }

   589 

   590         } else {                // Else it is live

   591           // A DEF also ends 'area' partway through the block.

   592           lrgs(r)._area -= cost;

   593           assert( lrgs(r)._area >= 0, "negative spill area" );

   594 

   595           // Insure high score for immediate-use spill copies so they get a color

   596           if( n->is_SpillCopy()

   597               && lrgs(r)._def != NodeSentinel     // MultiDef live range can still split

   598               && n->outcnt() == 1              // and use must be in this block

   599               && _cfg._bbs[n->unique_out()->_idx] == b ) {

   600             // All single-use MachSpillCopy(s) that immediately precede their

   601             // use must color early.  If a longer live range steals their

   602             // color, the spill copy will split and may push another spill copy

   603             // further away resulting in an infinite spill-split-retry cycle.

   604             // Assigning a zero area results in a high score() and a good

   605             // location in the simplify list.

   606             //

   607 

   608             Node *single_use = n->unique_out();

   609             assert( b->find_node(single_use) >= j, "Use must be later in block");

   610             // Use can be earlier in block if it is a Phi, but then I should be a MultiDef

   611 

   612             // Find first non SpillCopy 'm' that follows the current instruction

   613             // (j - 1) is index for current instruction 'n'

   614             Node *m = n;

   615             for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; }

   616             if( m == single_use ) {

   617               lrgs(r)._area = 0.0;

   618             }

   619           }

   620 

   621           // Remove from live-out set

   622           if( liveout.remove(r) ) {

   623             // Adjust register pressure.

   624             // Capture last hi-to-lo pressure transition

   625             lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index );

   626             assert( pressure[0] == count_int_pressure  (&liveout), "" );

   627             assert( pressure[1] == count_float_pressure(&liveout), "" );

   628           }

   629 

   630           // Copies do not define a new value and so do not interfere.

   631           // Remove the copies source from the liveout set before interfering.

   632           uint idx = n->is_Copy();

   633           if( idx ) {

   634             uint x = n2lidx(n->in(idx));

   635             if( liveout.remove( x ) ) {

   636               lrgs(x)._area -= cost;

   637               // Adjust register pressure.

   638               lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index );

   639               assert( pressure[0] == count_int_pressure  (&liveout), "" );

   640               assert( pressure[1] == count_float_pressure(&liveout), "" );

   641             }

   642           }

   643         } // End of if live or not

   644 

   645         // Interfere with everything live.  If the defined value must

   646         // go in a particular register, just remove that register from

   647         // all conflicting parties and avoid the interference.

   648 

   649         // Make exclusions for rematerializable defs.  Since rematerializable

   650         // DEFs are not bound but the live range is, some uses must be bound.

   651         // If we spill live range 'r', it can rematerialize at each use site

   652         // according to its bindings.

   653         const RegMask &rmask = lrgs(r).mask();

   654         if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) {

   655           // Smear odd bits; leave only aligned pairs of bits.

   656           RegMask r2mask = rmask;

   657           r2mask.SmearToPairs();

   658           // Check for common case

   659           int r_size = lrgs(r).num_regs();

   660           OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical;

   661 

   662           IndexSetIterator elements(&liveout);

   663           uint l;

   664           while ((l = elements.next()) != 0) {

   665             LRG &lrg = lrgs(l);

   666             // If 'l' must spill already, do not further hack his bits.

   667             // He'll get some interferences and be forced to spill later.

   668             if( lrg._must_spill ) continue;

   669             // Remove bound register(s) from 'l's choices

   670             RegMask old = lrg.mask();

   671             uint old_size = lrg.mask_size();

   672             // Remove the bits from LRG 'r' from LRG 'l' so 'l' no

   673             // longer interferes with 'r'.  If 'l' requires aligned

   674             // adjacent pairs, subtract out bit pairs.

   675             if( lrg.num_regs() == 2 && !lrg._fat_proj ) {

   676               lrg.SUBTRACT( r2mask );

   677               lrg.compute_set_mask_size();

   678             } else if( r_size != 1 ) {

   679               lrg.SUBTRACT( rmask );

   680               lrg.compute_set_mask_size();

   681             } else {            // Common case: size 1 bound removal

   682               if( lrg.mask().Member(r_reg) ) {

   683                 lrg.Remove(r_reg);

   684                 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1);

   685               }

   686             }

   687             // If 'l' goes completely dry, it must spill.

   688             if( lrg.not_free() ) {

   689               // Give 'l' some kind of reasonable mask, so he picks up

   690               // interferences (and will spill later).

   691               lrg.set_mask( old );

   692               lrg.set_mask_size(old_size);

   693               must_spill++;

   694               lrg._must_spill = 1;

   695               lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));

   696             }

   697           }

   698         } // End of if bound

   699 

   700         // Now interference with everything that is live and has

   701         // compatible register sets.

   702         interfere_with_live(r,&liveout);

   703 

   704       } // End of if normal register-allocated value

   705 

   706       cost -= b->_freq;         // Area remaining in the block

   707       if( cost < 0.0 ) cost = 0.0;  // Cost goes negative in the Phi area

   708 

   709       // Make all inputs live

   710       if( !n->is_Phi() ) {      // Phi function uses come from prior block

   711         JVMState* jvms = n->jvms();

   712         uint debug_start = jvms ? jvms->debug_start() : 999999;

   713         // Start loop at 1 (skip control edge) for most Nodes.

   714         // SCMemProj's might be the sole use of a StoreLConditional.

   715         // While StoreLConditionals set memory (the SCMemProj use)

   716         // they also def flags; if that flag def is unused the

   717         // allocator sees a flag-setting instruction with no use of

   718         // the flags and assumes it's dead.  This keeps the (useless)

   719         // flag-setting behavior alive while also keeping the (useful)

   720         // memory update effect.

   721         for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) {

   722           Node *def = n->in(k);

   723           uint x = n2lidx(def);

   724           if( !x ) continue;

   725           LRG &lrg = lrgs(x);

   726           // No use-side cost for spilling debug info

   727           if( k < debug_start )

   728             // A USE costs twice block frequency (once for the Load, once

   729             // for a Load-delay).  Rematerialized uses only cost once.

   730             lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq));

   731           // It is live now

   732           if( liveout.insert( x ) ) {

   733             // Newly live things assumed live from here to top of block

   734             lrg._area += cost;

   735             // Adjust register pressure

   736             if( lrg.mask().is_UP() && lrg.mask_size() ) {

   737               if( lrg._is_float ) {

   738                 pressure[1] += lrg.reg_pressure();

   739 #ifdef EXACT_PRESSURE

   740                 if( pressure[1] > b->_freg_pressure )

   741                   b->_freg_pressure = pressure[1];

   742 #endif

   743               } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {

   744                 pressure[0] += lrg.reg_pressure();

   745 #ifdef EXACT_PRESSURE

   746                 if( pressure[0] > b->_reg_pressure )

   747                   b->_reg_pressure = pressure[0];

   748 #endif

   749               }

   750             }

   751             assert( pressure[0] == count_int_pressure  (&liveout), "" );

   752             assert( pressure[1] == count_float_pressure(&liveout), "" );

   753           }

   754           assert( lrg._area >= 0, "negative spill area" );

   755         }

   756       }

   757     } // End of reverse pass over all instructions in block

   758 

   759     // If we run off the top of the block with high pressure and

   760     // never see a hi-to-low pressure transition, just record that

   761     // the whole block is high pressure.

   762     if( pressure[0] > (uint)INTPRESSURE   ) {

   763       hrp_index[0] = 0;

   764 #ifdef EXACT_PRESSURE

   765       if( pressure[0] > b->_reg_pressure )

   766         b->_reg_pressure = pressure[0];

   767 #else

   768       b->_reg_pressure = (uint)INTPRESSURE+1;

   769 #endif

   770     }

   771     if( pressure[1] > (uint)FLOATPRESSURE ) {

   772       hrp_index[1] = 0;

   773 #ifdef EXACT_PRESSURE

   774       if( pressure[1] > b->_freg_pressure )

   775         b->_freg_pressure = pressure[1];

   776 #else

   777       b->_freg_pressure = (uint)FLOATPRESSURE+1;

   778 #endif

   779     }

   780 

   781     // Compute high pressure indice; avoid landing in the middle of projnodes

   782     j = hrp_index[0];

   783     if( j < b->_nodes.size() && j < b->end_idx()+1 ) {

   784       Node *cur = b->_nodes[j];

   785       while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {

   786         j--;

   787         cur = b->_nodes[j];

   788       }

   789     }

   790     b->_ihrp_index = j;

   791     j = hrp_index[1];

   792     if( j < b->_nodes.size() && j < b->end_idx()+1 ) {

   793       Node *cur = b->_nodes[j];

   794       while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) {

   795         j--;

   796         cur = b->_nodes[j];

   797       }

   798     }

   799     b->_fhrp_index = j;

   800 

   801 #ifndef PRODUCT

   802     // Gather Register Pressure Statistics

   803     if( PrintOptoStatistics ) {

   804       if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE )

   805         _high_pressure++;

   806       else

   807         _low_pressure++;

   808     }

   809 #endif

   810   } // End of for all blocks

   811 

   812   return must_spill;

   813 }