Mercurial > hg > truffle
annotate src/share/vm/opto/ifg.cpp @ 452:00b023ae2d78
6722113: CMS: Incorrect overflow handling during precleaning of Reference lists
Summary: When we encounter marking stack overflow during precleaning of Reference lists, we were using the overflow list mechanism, which can cause problems on account of mutating the mark word of the header because of conflicts with mutator accesses and updates of that field. Instead we should use the usual mechanism for overflow handling in concurrent phases, namely dirtying of the card on which the overflowed object lies. Since precleaning effectively does a form of discovered list processing, albeit with discovery enabled, we needed to adjust some code to be correct in the face of interleaved processing and discovery.
Reviewed-by: apetrusenko, jcoomes
| author | ysr |
|---|---|
| date | Thu, 20 Nov 2008 12:27:41 -0800 |
| parents | eb28cf662f56 |
| children | 91263420e1c6 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 337 | 2 * Copyright 1998-2008 Sun Microsystems, Inc. All Rights Reserved. |
| 0 | 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. | |
|
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
488 int inst_count = last_inst - last_phi; |
|
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
489 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); |
|
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
490 assert(!(cost < 0.0), "negative spill cost" ); |
| 0 | 491 IndexSetIterator elements(&liveout); |
| 492 uint lidx; | |
| 493 while ((lidx = elements.next()) != 0) { | |
| 494 LRG &lrg = lrgs(lidx); | |
| 495 lrg._area += cost; | |
| 496 // Compute initial register pressure | |
| 497 if( lrg.mask().is_UP() && lrg.mask_size() ) { | |
| 498 if( lrg._is_float ) { // Count float pressure | |
| 499 pressure[1] += lrg.reg_pressure(); | |
| 500 #ifdef EXACT_PRESSURE | |
| 501 if( pressure[1] > b->_freg_pressure ) | |
| 502 b->_freg_pressure = pressure[1]; | |
| 503 #endif | |
| 504 // Count int pressure, but do not count the SP, flags | |
| 505 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
| 506 pressure[0] += lrg.reg_pressure(); | |
| 507 #ifdef EXACT_PRESSURE | |
| 508 if( pressure[0] > b->_reg_pressure ) | |
| 509 b->_reg_pressure = pressure[0]; | |
| 510 #endif | |
| 511 } | |
| 512 } | |
| 513 } | |
| 514 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
| 515 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
| 516 | |
| 517 // The IFG is built by a single reverse pass over each basic block. | |
| 518 // Starting with the known live-out set, we remove things that get | |
| 519 // defined and add things that become live (essentially executing one | |
| 520 // pass of a standard LIVE analysis). Just before a Node defines a value | |
| 521 // (and removes it from the live-ness set) that value is certainly live. | |
| 522 // The defined value interferes with everything currently live. The | |
| 523 // value is then removed from the live-ness set and it's inputs are added | |
| 524 // to the live-ness set. | |
| 525 uint j; | |
| 526 for( j = last_inst + 1; j > 1; j-- ) { | |
| 527 Node *n = b->_nodes[j - 1]; | |
| 528 | |
| 529 // Get value being defined | |
| 530 uint r = n2lidx(n); | |
| 531 | |
| 532 // Some special values do not allocate | |
| 533 if( r ) { | |
| 534 // A DEF normally costs block frequency; rematerialized values are | |
| 535 // removed from the DEF sight, so LOWER costs here. | |
| 536 lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq; | |
| 537 | |
| 538 // If it is not live, then this instruction is dead. Probably caused | |
| 539 // by spilling and rematerialization. Who cares why, yank this baby. | |
| 540 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) { | |
| 541 Node *def = n->in(0); | |
| 542 if( !n->is_Proj() || | |
| 543 // Could also be a flags-projection of a dead ADD or such. | |
| 544 (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) { | |
| 545 b->_nodes.remove(j - 1); | |
| 546 if( lrgs(r)._def == n ) lrgs(r)._def = 0; | |
| 547 n->disconnect_inputs(NULL); | |
| 548 _cfg._bbs.map(n->_idx,NULL); | |
| 549 n->replace_by(C->top()); | |
| 550 // Since yanking a Node from block, high pressure moves up one | |
| 551 hrp_index[0]--; | |
| 552 hrp_index[1]--; | |
| 553 continue; | |
| 554 } | |
| 555 | |
| 556 // Fat-projections kill many registers which cannot be used to | |
| 557 // hold live ranges. | |
| 558 if( lrgs(r)._fat_proj ) { | |
| 559 // Count the int-only registers | |
| 560 RegMask itmp = lrgs(r).mask(); | |
| 561 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); | |
| 562 int iregs = itmp.Size(); | |
| 563 #ifdef EXACT_PRESSURE | |
| 564 if( pressure[0]+iregs > b->_reg_pressure ) | |
| 565 b->_reg_pressure = pressure[0]+iregs; | |
| 566 #endif | |
| 567 if( pressure[0] <= (uint)INTPRESSURE && | |
| 568 pressure[0]+iregs > (uint)INTPRESSURE ) { | |
| 569 #ifndef EXACT_PRESSURE | |
| 570 b->_reg_pressure = (uint)INTPRESSURE+1; | |
| 571 #endif | |
| 572 hrp_index[0] = j-1; | |
| 573 } | |
| 574 // Count the float-only registers | |
| 575 RegMask ftmp = lrgs(r).mask(); | |
| 576 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]); | |
| 577 int fregs = ftmp.Size(); | |
| 578 #ifdef EXACT_PRESSURE | |
| 579 if( pressure[1]+fregs > b->_freg_pressure ) | |
| 580 b->_freg_pressure = pressure[1]+fregs; | |
| 581 #endif | |
| 582 if( pressure[1] <= (uint)FLOATPRESSURE && | |
| 583 pressure[1]+fregs > (uint)FLOATPRESSURE ) { | |
| 584 #ifndef EXACT_PRESSURE | |
| 585 b->_freg_pressure = (uint)FLOATPRESSURE+1; | |
| 586 #endif | |
| 587 hrp_index[1] = j-1; | |
| 588 } | |
| 589 } | |
| 590 | |
| 591 } else { // Else it is live | |
| 592 // A DEF also ends 'area' partway through the block. | |
| 593 lrgs(r)._area -= cost; | |
|
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
594 assert(!(lrgs(r)._area < 0.0), "negative spill area" ); |
| 0 | 595 |
| 596 // Insure high score for immediate-use spill copies so they get a color | |
| 597 if( n->is_SpillCopy() | |
|
295
ea18057223c4
6732194: Data corruption dependent on -server/-client/-Xbatch
never
parents:
0
diff
changeset
|
598 && lrgs(r).is_singledef() // MultiDef live range can still split |
| 0 | 599 && n->outcnt() == 1 // and use must be in this block |
| 600 && _cfg._bbs[n->unique_out()->_idx] == b ) { | |
| 601 // All single-use MachSpillCopy(s) that immediately precede their | |
| 602 // use must color early. If a longer live range steals their | |
| 603 // color, the spill copy will split and may push another spill copy | |
| 604 // further away resulting in an infinite spill-split-retry cycle. | |
| 605 // Assigning a zero area results in a high score() and a good | |
| 606 // location in the simplify list. | |
| 607 // | |
| 608 | |
| 609 Node *single_use = n->unique_out(); | |
| 610 assert( b->find_node(single_use) >= j, "Use must be later in block"); | |
| 611 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef | |
| 612 | |
| 613 // Find first non SpillCopy 'm' that follows the current instruction | |
| 614 // (j - 1) is index for current instruction 'n' | |
| 615 Node *m = n; | |
| 616 for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; } | |
| 617 if( m == single_use ) { | |
| 618 lrgs(r)._area = 0.0; | |
| 619 } | |
| 620 } | |
| 621 | |
| 622 // Remove from live-out set | |
| 623 if( liveout.remove(r) ) { | |
| 624 // Adjust register pressure. | |
| 625 // Capture last hi-to-lo pressure transition | |
| 626 lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index ); | |
| 627 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
| 628 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
| 629 } | |
| 630 | |
| 631 // Copies do not define a new value and so do not interfere. | |
| 632 // Remove the copies source from the liveout set before interfering. | |
| 633 uint idx = n->is_Copy(); | |
| 634 if( idx ) { | |
| 635 uint x = n2lidx(n->in(idx)); | |
| 636 if( liveout.remove( x ) ) { | |
| 637 lrgs(x)._area -= cost; | |
| 638 // Adjust register pressure. | |
| 639 lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index ); | |
| 640 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
| 641 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
| 642 } | |
| 643 } | |
| 644 } // End of if live or not | |
| 645 | |
| 646 // Interfere with everything live. If the defined value must | |
| 647 // go in a particular register, just remove that register from | |
| 648 // all conflicting parties and avoid the interference. | |
| 649 | |
| 650 // Make exclusions for rematerializable defs. Since rematerializable | |
| 651 // DEFs are not bound but the live range is, some uses must be bound. | |
| 652 // If we spill live range 'r', it can rematerialize at each use site | |
| 653 // according to its bindings. | |
| 654 const RegMask &rmask = lrgs(r).mask(); | |
| 655 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) { | |
| 656 // Smear odd bits; leave only aligned pairs of bits. | |
| 657 RegMask r2mask = rmask; | |
| 658 r2mask.SmearToPairs(); | |
| 659 // Check for common case | |
| 660 int r_size = lrgs(r).num_regs(); | |
| 661 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical; | |
| 662 | |
| 663 IndexSetIterator elements(&liveout); | |
| 664 uint l; | |
| 665 while ((l = elements.next()) != 0) { | |
| 666 LRG &lrg = lrgs(l); | |
| 667 // If 'l' must spill already, do not further hack his bits. | |
| 668 // He'll get some interferences and be forced to spill later. | |
| 669 if( lrg._must_spill ) continue; | |
| 670 // Remove bound register(s) from 'l's choices | |
| 671 RegMask old = lrg.mask(); | |
| 672 uint old_size = lrg.mask_size(); | |
| 673 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no | |
| 674 // longer interferes with 'r'. If 'l' requires aligned | |
| 675 // adjacent pairs, subtract out bit pairs. | |
| 676 if( lrg.num_regs() == 2 && !lrg._fat_proj ) { | |
| 677 lrg.SUBTRACT( r2mask ); | |
| 678 lrg.compute_set_mask_size(); | |
| 679 } else if( r_size != 1 ) { | |
| 680 lrg.SUBTRACT( rmask ); | |
| 681 lrg.compute_set_mask_size(); | |
| 682 } else { // Common case: size 1 bound removal | |
| 683 if( lrg.mask().Member(r_reg) ) { | |
| 684 lrg.Remove(r_reg); | |
| 685 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1); | |
| 686 } | |
| 687 } | |
| 688 // If 'l' goes completely dry, it must spill. | |
| 689 if( lrg.not_free() ) { | |
| 690 // Give 'l' some kind of reasonable mask, so he picks up | |
| 691 // interferences (and will spill later). | |
| 692 lrg.set_mask( old ); | |
| 693 lrg.set_mask_size(old_size); | |
| 694 must_spill++; | |
| 695 lrg._must_spill = 1; | |
| 696 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); | |
| 697 } | |
| 698 } | |
| 699 } // End of if bound | |
| 700 | |
| 701 // Now interference with everything that is live and has | |
| 702 // compatible register sets. | |
| 703 interfere_with_live(r,&liveout); | |
| 704 | |
| 705 } // End of if normal register-allocated value | |
| 706 | |
|
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
707 // Area remaining in the block |
|
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
708 inst_count--; |
|
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
709 cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); |
| 0 | 710 |
| 711 // Make all inputs live | |
| 712 if( !n->is_Phi() ) { // Phi function uses come from prior block | |
| 713 JVMState* jvms = n->jvms(); | |
| 714 uint debug_start = jvms ? jvms->debug_start() : 999999; | |
| 715 // Start loop at 1 (skip control edge) for most Nodes. | |
| 716 // SCMemProj's might be the sole use of a StoreLConditional. | |
| 717 // While StoreLConditionals set memory (the SCMemProj use) | |
| 718 // they also def flags; if that flag def is unused the | |
| 719 // allocator sees a flag-setting instruction with no use of | |
| 720 // the flags and assumes it's dead. This keeps the (useless) | |
| 721 // flag-setting behavior alive while also keeping the (useful) | |
| 722 // memory update effect. | |
| 723 for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) { | |
| 724 Node *def = n->in(k); | |
| 725 uint x = n2lidx(def); | |
| 726 if( !x ) continue; | |
| 727 LRG &lrg = lrgs(x); | |
| 728 // No use-side cost for spilling debug info | |
| 729 if( k < debug_start ) | |
| 730 // A USE costs twice block frequency (once for the Load, once | |
| 731 // for a Load-delay). Rematerialized uses only cost once. | |
| 732 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq)); | |
| 733 // It is live now | |
| 734 if( liveout.insert( x ) ) { | |
| 735 // Newly live things assumed live from here to top of block | |
| 736 lrg._area += cost; | |
| 737 // Adjust register pressure | |
| 738 if( lrg.mask().is_UP() && lrg.mask_size() ) { | |
| 739 if( lrg._is_float ) { | |
| 740 pressure[1] += lrg.reg_pressure(); | |
| 741 #ifdef EXACT_PRESSURE | |
| 742 if( pressure[1] > b->_freg_pressure ) | |
| 743 b->_freg_pressure = pressure[1]; | |
| 744 #endif | |
| 745 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { | |
| 746 pressure[0] += lrg.reg_pressure(); | |
| 747 #ifdef EXACT_PRESSURE | |
| 748 if( pressure[0] > b->_reg_pressure ) | |
| 749 b->_reg_pressure = pressure[0]; | |
| 750 #endif | |
| 751 } | |
| 752 } | |
| 753 assert( pressure[0] == count_int_pressure (&liveout), "" ); | |
| 754 assert( pressure[1] == count_float_pressure(&liveout), "" ); | |
| 755 } | |
|
369
5f85534046c2
6750588: assert(lrg._area >= 0,"negative spill area") running NSK stmp0101 test
rasbold
parents:
295
diff
changeset
|
756 assert(!(lrg._area < 0.0), "negative spill area" ); |
| 0 | 757 } |
| 758 } | |
| 759 } // End of reverse pass over all instructions in block | |
| 760 | |
| 761 // If we run off the top of the block with high pressure and | |
| 762 // never see a hi-to-low pressure transition, just record that | |
| 763 // the whole block is high pressure. | |
| 764 if( pressure[0] > (uint)INTPRESSURE ) { | |
| 765 hrp_index[0] = 0; | |
| 766 #ifdef EXACT_PRESSURE | |
| 767 if( pressure[0] > b->_reg_pressure ) | |
| 768 b->_reg_pressure = pressure[0]; | |
| 769 #else | |
| 770 b->_reg_pressure = (uint)INTPRESSURE+1; | |
| 771 #endif | |
| 772 } | |
| 773 if( pressure[1] > (uint)FLOATPRESSURE ) { | |
| 774 hrp_index[1] = 0; | |
| 775 #ifdef EXACT_PRESSURE | |
| 776 if( pressure[1] > b->_freg_pressure ) | |
| 777 b->_freg_pressure = pressure[1]; | |
| 778 #else | |
| 779 b->_freg_pressure = (uint)FLOATPRESSURE+1; | |
| 780 #endif | |
| 781 } | |
| 782 | |
| 783 // Compute high pressure indice; avoid landing in the middle of projnodes | |
| 784 j = hrp_index[0]; | |
| 785 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { | |
| 786 Node *cur = b->_nodes[j]; | |
| 787 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { | |
| 788 j--; | |
| 789 cur = b->_nodes[j]; | |
| 790 } | |
| 791 } | |
| 792 b->_ihrp_index = j; | |
| 793 j = hrp_index[1]; | |
| 794 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { | |
| 795 Node *cur = b->_nodes[j]; | |
| 796 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { | |
| 797 j--; | |
| 798 cur = b->_nodes[j]; | |
| 799 } | |
| 800 } | |
| 801 b->_fhrp_index = j; | |
| 802 | |
| 803 #ifndef PRODUCT | |
| 804 // Gather Register Pressure Statistics | |
| 805 if( PrintOptoStatistics ) { | |
| 806 if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE ) | |
| 807 _high_pressure++; | |
| 808 else | |
| 809 _low_pressure++; | |
| 810 } | |
| 811 #endif | |
| 812 } // End of for all blocks | |
| 813 | |
| 814 return must_spill; | |
| 815 } |