1 /* 2 * Copyright (c) 1998, 2012, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "compiler/oopMap.hpp" 27 #include "memory/allocation.inline.hpp" 28 #include "opto/addnode.hpp" 29 #include "opto/block.hpp" 30 #include "opto/callnode.hpp" 31 #include "opto/cfgnode.hpp" 32 #include "opto/chaitin.hpp" 33 #include "opto/coalesce.hpp" 34 #include "opto/connode.hpp" 35 #include "opto/indexSet.hpp" 36 #include "opto/machnode.hpp" 37 #include "opto/memnode.hpp" 38 #include "opto/opcodes.hpp" 39 40 //============================================================================= 41 //------------------------------IFG-------------------------------------------- 42 PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) { 43 } 44 45 //------------------------------init------------------------------------------- 46 void PhaseIFG::init( uint maxlrg ) { 47 _maxlrg = maxlrg; 48 _yanked = new (_arena) VectorSet(_arena); 49 _is_square = false; 50 // Make uninitialized adjacency lists 51 _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg); 52 // Also make empty live range structures 53 _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) ); 54 memset(_lrgs,0,sizeof(LRG)*maxlrg); 55 // Init all to empty 56 for( uint i = 0; i < maxlrg; i++ ) { 57 _adjs[i].initialize(maxlrg); 58 _lrgs[i].Set_All(); 59 } 60 } 61 62 //------------------------------add-------------------------------------------- 63 // Add edge between vertices a & b. These are sorted (triangular matrix), 64 // then the smaller number is inserted in the larger numbered array. 65 int PhaseIFG::add_edge( uint a, uint b ) { 66 lrgs(a).invalid_degree(); 67 lrgs(b).invalid_degree(); 68 // Sort a and b, so that a is bigger 69 assert( !_is_square, "only on triangular" ); 70 if( a < b ) { uint tmp = a; a = b; b = tmp; } 71 return _adjs[a].insert( b ); 72 } 73 74 //------------------------------add_vector------------------------------------- 75 // Add an edge between 'a' and everything in the vector. 76 void PhaseIFG::add_vector( uint a, IndexSet *vec ) { 77 // IFG is triangular, so do the inserts where 'a' < 'b'. 78 assert( !_is_square, "only on triangular" ); 79 IndexSet *adjs_a = &_adjs[a]; 80 if( !vec->count() ) return; 81 82 IndexSetIterator elements(vec); 83 uint neighbor; 84 while ((neighbor = elements.next()) != 0) { 85 add_edge( a, neighbor ); 86 } 87 } 88 89 //------------------------------test------------------------------------------- 90 // Is there an edge between a and b? 91 int PhaseIFG::test_edge( uint a, uint b ) const { 92 // Sort a and b, so that a is larger 93 assert( !_is_square, "only on triangular" ); 94 if( a < b ) { uint tmp = a; a = b; b = tmp; } 95 return _adjs[a].member(b); 96 } 97 98 //------------------------------SquareUp--------------------------------------- 99 // Convert triangular matrix to square matrix 100 void PhaseIFG::SquareUp() { 101 assert( !_is_square, "only on triangular" ); 102 103 // Simple transpose 104 for( uint i = 0; i < _maxlrg; i++ ) { 105 IndexSetIterator elements(&_adjs[i]); 106 uint datum; 107 while ((datum = elements.next()) != 0) { 108 _adjs[datum].insert( i ); 109 } 110 } 111 _is_square = true; 112 } 113 114 //------------------------------Compute_Effective_Degree----------------------- 115 // Compute effective degree in bulk 116 void PhaseIFG::Compute_Effective_Degree() { 117 assert( _is_square, "only on square" ); 118 119 for( uint i = 0; i < _maxlrg; i++ ) 120 lrgs(i).set_degree(effective_degree(i)); 121 } 122 123 //------------------------------test_edge_sq----------------------------------- 124 int PhaseIFG::test_edge_sq( uint a, uint b ) const { 125 assert( _is_square, "only on square" ); 126 // Swap, so that 'a' has the lesser count. Then binary search is on 127 // the smaller of a's list and b's list. 128 if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; } 129 //return _adjs[a].unordered_member(b); 130 return _adjs[a].member(b); 131 } 132 133 //------------------------------Union------------------------------------------ 134 // Union edges of B into A 135 void PhaseIFG::Union( uint a, uint b ) { 136 assert( _is_square, "only on square" ); 137 IndexSet *A = &_adjs[a]; 138 IndexSetIterator b_elements(&_adjs[b]); 139 uint datum; 140 while ((datum = b_elements.next()) != 0) { 141 if(A->insert(datum)) { 142 _adjs[datum].insert(a); 143 lrgs(a).invalid_degree(); 144 lrgs(datum).invalid_degree(); 145 } 146 } 147 } 148 149 //------------------------------remove_node------------------------------------ 150 // Yank a Node and all connected edges from the IFG. Return a 151 // list of neighbors (edges) yanked. 152 IndexSet *PhaseIFG::remove_node( uint a ) { 153 assert( _is_square, "only on square" ); 154 assert( !_yanked->test(a), "" ); 155 _yanked->set(a); 156 157 // I remove the LRG from all neighbors. 158 IndexSetIterator elements(&_adjs[a]); 159 LRG &lrg_a = lrgs(a); 160 uint datum; 161 while ((datum = elements.next()) != 0) { 162 _adjs[datum].remove(a); 163 lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) ); 164 } 165 return neighbors(a); 166 } 167 168 //------------------------------re_insert-------------------------------------- 169 // Re-insert a yanked Node. 170 void PhaseIFG::re_insert( uint a ) { 171 assert( _is_square, "only on square" ); 172 assert( _yanked->test(a), "" ); 173 (*_yanked) >>= a; 174 175 IndexSetIterator elements(&_adjs[a]); 176 uint datum; 177 while ((datum = elements.next()) != 0) { 178 _adjs[datum].insert(a); 179 lrgs(datum).invalid_degree(); 180 } 181 } 182 183 //------------------------------compute_degree--------------------------------- 184 // Compute the degree between 2 live ranges. If both live ranges are 185 // aligned-adjacent powers-of-2 then we use the MAX size. If either is 186 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to 187 // MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 188 // this is so. 189 int LRG::compute_degree( LRG &l ) const { 190 int tmp; 191 int num_regs = _num_regs; 192 int nregs = l.num_regs(); 193 tmp = (_fat_proj || l._fat_proj) // either is a fat-proj? 194 ? (num_regs * nregs) // then use product 195 : MAX2(num_regs,nregs); // else use max 196 return tmp; 197 } 198 199 //------------------------------effective_degree------------------------------- 200 // Compute effective degree for this live range. If both live ranges are 201 // aligned-adjacent powers-of-2 then we use the MAX size. If either is 202 // mis-aligned (or for Fat-Projections, not-adjacent) then we have to 203 // MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 204 // this is so. 205 int PhaseIFG::effective_degree( uint lidx ) const { 206 int eff = 0; 207 int num_regs = lrgs(lidx).num_regs(); 208 int fat_proj = lrgs(lidx)._fat_proj; 209 IndexSet *s = neighbors(lidx); 210 IndexSetIterator elements(s); 211 uint nidx; 212 while((nidx = elements.next()) != 0) { 213 LRG &lrgn = lrgs(nidx); 214 int nregs = lrgn.num_regs(); 215 eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj? 216 ? (num_regs * nregs) // then use product 217 : MAX2(num_regs,nregs); // else use max 218 } 219 return eff; 220 } 221 222 223 #ifndef PRODUCT 224 //------------------------------dump------------------------------------------- 225 void PhaseIFG::dump() const { 226 tty->print_cr("-- Interference Graph --%s--", 227 _is_square ? "square" : "triangular" ); 228 if( _is_square ) { 229 for( uint i = 0; i < _maxlrg; i++ ) { 230 tty->print( (*_yanked)[i] ? "XX " : " "); 231 tty->print("L%d: { ",i); 232 IndexSetIterator elements(&_adjs[i]); 233 uint datum; 234 while ((datum = elements.next()) != 0) { 235 tty->print("L%d ", datum); 236 } 237 tty->print_cr("}"); 238 239 } 240 return; 241 } 242 243 // Triangular 244 for( uint i = 0; i < _maxlrg; i++ ) { 245 uint j; 246 tty->print( (*_yanked)[i] ? "XX " : " "); 247 tty->print("L%d: { ",i); 248 for( j = _maxlrg; j > i; j-- ) 249 if( test_edge(j - 1,i) ) { 250 tty->print("L%d ",j - 1); 251 } 252 tty->print("| "); 253 IndexSetIterator elements(&_adjs[i]); 254 uint datum; 255 while ((datum = elements.next()) != 0) { 256 tty->print("L%d ", datum); 257 } 258 tty->print("}\n"); 259 } 260 tty->print("\n"); 261 } 262 263 //------------------------------stats------------------------------------------ 264 void PhaseIFG::stats() const { 265 ResourceMark rm; 266 int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2); 267 memset( h_cnt, 0, sizeof(int)*_maxlrg*2 ); 268 uint i; 269 for( i = 0; i < _maxlrg; i++ ) { 270 h_cnt[neighbor_cnt(i)]++; 271 } 272 tty->print_cr("--Histogram of counts--"); 273 for( i = 0; i < _maxlrg*2; i++ ) 274 if( h_cnt[i] ) 275 tty->print("%d/%d ",i,h_cnt[i]); 276 tty->print_cr(""); 277 } 278 279 //------------------------------verify----------------------------------------- 280 void PhaseIFG::verify( const PhaseChaitin *pc ) const { 281 // IFG is square, sorted and no need for Find 282 for( uint i = 0; i < _maxlrg; i++ ) { 283 assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" ); 284 IndexSet *set = &_adjs[i]; 285 IndexSetIterator elements(set); 286 uint idx; 287 uint last = 0; 288 while ((idx = elements.next()) != 0) { 289 assert( idx != i, "Must have empty diagonal"); 290 assert( pc->Find_const(idx) == idx, "Must not need Find" ); 291 assert( _adjs[idx].member(i), "IFG not square" ); 292 assert( !(*_yanked)[idx], "No yanked neighbors" ); 293 assert( last < idx, "not sorted increasing"); 294 last = idx; 295 } 296 assert( !lrgs(i)._degree_valid || 297 effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong" ); 298 } 299 } 300 #endif 301 302 //------------------------------interfere_with_live---------------------------- 303 // Interfere this register with everything currently live. Use the RegMasks 304 // to trim the set of possible interferences. Return a count of register-only 305 // interferences as an estimate of register pressure. 306 void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) { 307 uint retval = 0; 308 // Interfere with everything live. 309 const RegMask &rm = lrgs(r).mask(); 310 // Check for interference by checking overlap of regmasks. 311 // Only interfere if acceptable register masks overlap. 312 IndexSetIterator elements(liveout); 313 uint l; 314 while( (l = elements.next()) != 0 ) 315 if( rm.overlap( lrgs(l).mask() ) ) 316 _ifg->add_edge( r, l ); 317 } 318 319 //------------------------------build_ifg_virtual------------------------------ 320 // Actually build the interference graph. Uses virtual registers only, no 321 // physical register masks. This allows me to be very aggressive when 322 // coalescing copies. Some of this aggressiveness will have to be undone 323 // later, but I'd rather get all the copies I can now (since unremoved copies 324 // at this point can end up in bad places). Copies I re-insert later I have 325 // more opportunity to insert them in low-frequency locations. 326 void PhaseChaitin::build_ifg_virtual( ) { 327 328 // For all blocks (in any order) do... 329 for( uint i=0; i<_cfg._num_blocks; i++ ) { 330 Block *b = _cfg._blocks[i]; 331 IndexSet *liveout = _live->live(b); 332 333 // The IFG is built by a single reverse pass over each basic block. 334 // Starting with the known live-out set, we remove things that get 335 // defined and add things that become live (essentially executing one 336 // pass of a standard LIVE analysis). Just before a Node defines a value 337 // (and removes it from the live-ness set) that value is certainly live. 338 // The defined value interferes with everything currently live. The 339 // value is then removed from the live-ness set and it's inputs are 340 // added to the live-ness set. 341 for( uint j = b->end_idx() + 1; j > 1; j-- ) { 342 Node *n = b->_nodes[j-1]; 343 344 // Get value being defined 345 uint r = n2lidx(n); 346 347 // Some special values do not allocate 348 if( r ) { 349 350 // Remove from live-out set 351 liveout->remove(r); 352 353 // Copies do not define a new value and so do not interfere. 354 // Remove the copies source from the liveout set before interfering. 355 uint idx = n->is_Copy(); 356 if( idx ) liveout->remove( n2lidx(n->in(idx)) ); 357 358 // Interfere with everything live 359 interfere_with_live( r, liveout ); 360 } 361 362 // Make all inputs live 363 if( !n->is_Phi() ) { // Phi function uses come from prior block 364 for( uint k = 1; k < n->req(); k++ ) 365 liveout->insert( n2lidx(n->in(k)) ); 366 } 367 368 // 2-address instructions always have the defined value live 369 // on entry to the instruction, even though it is being defined 370 // by the instruction. We pretend a virtual copy sits just prior 371 // to the instruction and kills the src-def'd register. 372 // In other words, for 2-address instructions the defined value 373 // interferes with all inputs. 374 uint idx; 375 if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) { 376 const MachNode *mach = n->as_Mach(); 377 // Sometimes my 2-address ADDs are commuted in a bad way. 378 // We generally want the USE-DEF register to refer to the 379 // loop-varying quantity, to avoid a copy. 380 uint op = mach->ideal_Opcode(); 381 // Check that mach->num_opnds() == 3 to ensure instruction is 382 // not subsuming constants, effectively excludes addI_cin_imm 383 // Can NOT swap for instructions like addI_cin_imm since it 384 // is adding zero to yhi + carry and the second ideal-input 385 // points to the result of adding low-halves. 386 // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm 387 if( (op == Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) && 388 n->in(1)->bottom_type()->base() == Type::Int && 389 // See if the ADD is involved in a tight data loop the wrong way 390 n->in(2)->is_Phi() && 391 n->in(2)->in(2) == n ) { 392 Node *tmp = n->in(1); 393 n->set_req( 1, n->in(2) ); 394 n->set_req( 2, tmp ); 395 } 396 // Defined value interferes with all inputs 397 uint lidx = n2lidx(n->in(idx)); 398 for( uint k = 1; k < n->req(); k++ ) { 399 uint kidx = n2lidx(n->in(k)); 400 if( kidx != lidx ) 401 _ifg->add_edge( r, kidx ); 402 } 403 } 404 } // End of forall instructions in block 405 } // End of forall blocks 406 } 407 408 //------------------------------count_int_pressure----------------------------- 409 uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) { 410 IndexSetIterator elements(liveout); 411 uint lidx; 412 uint cnt = 0; 413 while ((lidx = elements.next()) != 0) { 414 if( lrgs(lidx).mask().is_UP() && 415 lrgs(lidx).mask_size() && 416 !lrgs(lidx)._is_float && 417 !lrgs(lidx)._is_vector && 418 lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) 419 cnt += lrgs(lidx).reg_pressure(); 420 } 421 return cnt; 422 } 423 424 //------------------------------count_float_pressure--------------------------- 425 uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) { 426 IndexSetIterator elements(liveout); 427 uint lidx; 428 uint cnt = 0; 429 while ((lidx = elements.next()) != 0) { 430 if( lrgs(lidx).mask().is_UP() && 431 lrgs(lidx).mask_size() && 432 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector)) 433 cnt += lrgs(lidx).reg_pressure(); 434 } 435 return cnt; 436 } 437 438 //------------------------------lower_pressure--------------------------------- 439 // Adjust register pressure down by 1. Capture last hi-to-low transition, 440 static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) { 441 if (lrg->mask().is_UP() && lrg->mask_size()) { 442 if (lrg->_is_float || lrg->_is_vector) { 443 pressure[1] -= lrg->reg_pressure(); 444 if( pressure[1] == (uint)FLOATPRESSURE ) { 445 hrp_index[1] = where; 446 447 if( pressure[1] > b->_freg_pressure ) 448 b->_freg_pressure = pressure[1]+1; 449 } 450 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 451 pressure[0] -= lrg->reg_pressure(); 452 if( pressure[0] == (uint)INTPRESSURE ) { 453 hrp_index[0] = where; 454 455 if( pressure[0] > b->_reg_pressure ) 456 b->_reg_pressure = pressure[0]+1; 457 } 458 } 459 } 460 } 461 462 //------------------------------build_ifg_physical----------------------------- 463 // Build the interference graph using physical registers when available. 464 // That is, if 2 live ranges are simultaneously alive but in their acceptable 465 // register sets do not overlap, then they do not interfere. 466 uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) { 467 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); ) 468 469 uint spill_reg = LRG::SPILL_REG; 470 uint must_spill = 0; 471 472 // For all blocks (in any order) do... 473 for( uint i = 0; i < _cfg._num_blocks; i++ ) { 474 Block *b = _cfg._blocks[i]; 475 // Clone (rather than smash in place) the liveout info, so it is alive 476 // for the "collect_gc_info" phase later. 477 IndexSet liveout(_live->live(b)); 478 uint last_inst = b->end_idx(); 479 // Compute first nonphi node index 480 uint first_inst; 481 for( first_inst = 1; first_inst < last_inst; first_inst++ ) 482 if( !b->_nodes[first_inst]->is_Phi() ) 483 break; 484 485 // Spills could be inserted before CreateEx node which should be 486 // first instruction in block after Phis. Move CreateEx up. 487 for( uint insidx = first_inst; insidx < last_inst; insidx++ ) { 488 Node *ex = b->_nodes[insidx]; 489 if( ex->is_SpillCopy() ) continue; 490 if( insidx > first_inst && ex->is_Mach() && 491 ex->as_Mach()->ideal_Opcode() == Op_CreateEx ) { 492 // If the CreateEx isn't above all the MachSpillCopies 493 // then move it to the top. 494 b->_nodes.remove(insidx); 495 b->_nodes.insert(first_inst, ex); 496 } 497 // Stop once a CreateEx or any other node is found 498 break; 499 } 500 501 // Reset block's register pressure values for each ifg construction 502 uint pressure[2], hrp_index[2]; 503 pressure[0] = pressure[1] = 0; 504 hrp_index[0] = hrp_index[1] = last_inst+1; 505 b->_reg_pressure = b->_freg_pressure = 0; 506 // Liveout things are presumed live for the whole block. We accumulate 507 // 'area' accordingly. If they get killed in the block, we'll subtract 508 // the unused part of the block from the area. 509 int inst_count = last_inst - first_inst; 510 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); 511 assert(!(cost < 0.0), "negative spill cost" ); 512 IndexSetIterator elements(&liveout); 513 uint lidx; 514 while ((lidx = elements.next()) != 0) { 515 LRG &lrg = lrgs(lidx); 516 lrg._area += cost; 517 // Compute initial register pressure 518 if (lrg.mask().is_UP() && lrg.mask_size()) { 519 if (lrg._is_float || lrg._is_vector) { // Count float pressure 520 pressure[1] += lrg.reg_pressure(); 521 522 if( pressure[1] > b->_freg_pressure ) 523 b->_freg_pressure = pressure[1]; 524 525 // Count int pressure, but do not count the SP, flags 526 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 527 pressure[0] += lrg.reg_pressure(); 528 529 if( pressure[0] > b->_reg_pressure ) 530 b->_reg_pressure = pressure[0]; 531 532 } 533 } 534 } 535 assert( pressure[0] == count_int_pressure (&liveout), "" ); 536 assert( pressure[1] == count_float_pressure(&liveout), "" ); 537 538 // The IFG is built by a single reverse pass over each basic block. 539 // Starting with the known live-out set, we remove things that get 540 // defined and add things that become live (essentially executing one 541 // pass of a standard LIVE analysis). Just before a Node defines a value 542 // (and removes it from the live-ness set) that value is certainly live. 543 // The defined value interferes with everything currently live. The 544 // value is then removed from the live-ness set and it's inputs are added 545 // to the live-ness set. 546 uint j; 547 for( j = last_inst + 1; j > 1; j-- ) { 548 Node *n = b->_nodes[j - 1]; 549 550 // Get value being defined 551 uint r = n2lidx(n); 552 553 // Some special values do not allocate 554 if( r ) { 555 // A DEF normally costs block frequency; rematerialized values are 556 // removed from the DEF sight, so LOWER costs here. 557 lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq; 558 559 // If it is not live, then this instruction is dead. Probably caused 560 // by spilling and rematerialization. Who cares why, yank this baby. 561 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) { 562 Node *def = n->in(0); 563 if( !n->is_Proj() || 564 // Could also be a flags-projection of a dead ADD or such. 565 (n2lidx(def) && !liveout.member(n2lidx(def)) ) ) { 566 b->_nodes.remove(j - 1); 567 if( lrgs(r)._def == n ) lrgs(r)._def = 0; 568 n->disconnect_inputs(NULL, C); 569 _cfg._bbs.map(n->_idx,NULL); 570 n->replace_by(C->top()); 571 // Since yanking a Node from block, high pressure moves up one 572 hrp_index[0]--; 573 hrp_index[1]--; 574 continue; 575 } 576 577 // Fat-projections kill many registers which cannot be used to 578 // hold live ranges. 579 if( lrgs(r)._fat_proj ) { 580 // Count the int-only registers 581 RegMask itmp = lrgs(r).mask(); 582 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); 583 int iregs = itmp.Size(); 584 585 if( pressure[0]+iregs > b->_reg_pressure ) 586 b->_reg_pressure = pressure[0]+iregs; 587 588 if( pressure[0] <= (uint)INTPRESSURE && 589 pressure[0]+iregs > (uint)INTPRESSURE ) { 590 hrp_index[0] = j-1; 591 } 592 // Count the float-only registers 593 RegMask ftmp = lrgs(r).mask(); 594 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]); 595 int fregs = ftmp.Size(); 596 597 if( pressure[1]+fregs > b->_freg_pressure ) 598 b->_freg_pressure = pressure[1]+fregs; 599 600 if( pressure[1] <= (uint)FLOATPRESSURE && 601 pressure[1]+fregs > (uint)FLOATPRESSURE ) { 602 hrp_index[1] = j-1; 603 } 604 } 605 606 } else { // Else it is live 607 // A DEF also ends 'area' partway through the block. 608 lrgs(r)._area -= cost; 609 assert(!(lrgs(r)._area < 0.0), "negative spill area" ); 610 611 // Insure high score for immediate-use spill copies so they get a color 612 if( n->is_SpillCopy() 613 && lrgs(r).is_singledef() // MultiDef live range can still split 614 && n->outcnt() == 1 // and use must be in this block 615 && _cfg._bbs[n->unique_out()->_idx] == b ) { 616 // All single-use MachSpillCopy(s) that immediately precede their 617 // use must color early. If a longer live range steals their 618 // color, the spill copy will split and may push another spill copy 619 // further away resulting in an infinite spill-split-retry cycle. 620 // Assigning a zero area results in a high score() and a good 621 // location in the simplify list. 622 // 623 624 Node *single_use = n->unique_out(); 625 assert( b->find_node(single_use) >= j, "Use must be later in block"); 626 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef 627 628 // Find first non SpillCopy 'm' that follows the current instruction 629 // (j - 1) is index for current instruction 'n' 630 Node *m = n; 631 for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; } 632 if( m == single_use ) { 633 lrgs(r)._area = 0.0; 634 } 635 } 636 637 // Remove from live-out set 638 if( liveout.remove(r) ) { 639 // Adjust register pressure. 640 // Capture last hi-to-lo pressure transition 641 lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index ); 642 assert( pressure[0] == count_int_pressure (&liveout), "" ); 643 assert( pressure[1] == count_float_pressure(&liveout), "" ); 644 } 645 646 // Copies do not define a new value and so do not interfere. 647 // Remove the copies source from the liveout set before interfering. 648 uint idx = n->is_Copy(); 649 if( idx ) { 650 uint x = n2lidx(n->in(idx)); 651 if( liveout.remove( x ) ) { 652 lrgs(x)._area -= cost; 653 // Adjust register pressure. 654 lower_pressure( &lrgs(x), j-1, b, pressure, hrp_index ); 655 assert( pressure[0] == count_int_pressure (&liveout), "" ); 656 assert( pressure[1] == count_float_pressure(&liveout), "" ); 657 } 658 } 659 } // End of if live or not 660 661 // Interfere with everything live. If the defined value must 662 // go in a particular register, just remove that register from 663 // all conflicting parties and avoid the interference. 664 665 // Make exclusions for rematerializable defs. Since rematerializable 666 // DEFs are not bound but the live range is, some uses must be bound. 667 // If we spill live range 'r', it can rematerialize at each use site 668 // according to its bindings. 669 const RegMask &rmask = lrgs(r).mask(); 670 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) { 671 // Check for common case 672 int r_size = lrgs(r).num_regs(); 673 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical; 674 // Smear odd bits 675 IndexSetIterator elements(&liveout); 676 uint l; 677 while ((l = elements.next()) != 0) { 678 LRG &lrg = lrgs(l); 679 // If 'l' must spill already, do not further hack his bits. 680 // He'll get some interferences and be forced to spill later. 681 if( lrg._must_spill ) continue; 682 // Remove bound register(s) from 'l's choices 683 RegMask old = lrg.mask(); 684 uint old_size = lrg.mask_size(); 685 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no 686 // longer interferes with 'r'. If 'l' requires aligned 687 // adjacent pairs, subtract out bit pairs. 688 assert(!lrg._is_vector || !lrg._fat_proj, "sanity"); 689 if (lrg.num_regs() > 1 && !lrg._fat_proj) { 690 RegMask r2mask = rmask; 691 // Leave only aligned set of bits. 692 r2mask.smear_to_sets(lrg.num_regs()); 693 // It includes vector case. 694 lrg.SUBTRACT( r2mask ); 695 lrg.compute_set_mask_size(); 696 } else if( r_size != 1 ) { // fat proj 697 lrg.SUBTRACT( rmask ); 698 lrg.compute_set_mask_size(); 699 } else { // Common case: size 1 bound removal 700 if( lrg.mask().Member(r_reg) ) { 701 lrg.Remove(r_reg); 702 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1); 703 } 704 } 705 // If 'l' goes completely dry, it must spill. 706 if( lrg.not_free() ) { 707 // Give 'l' some kind of reasonable mask, so he picks up 708 // interferences (and will spill later). 709 lrg.set_mask( old ); 710 lrg.set_mask_size(old_size); 711 must_spill++; 712 lrg._must_spill = 1; 713 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); 714 } 715 } 716 } // End of if bound 717 718 // Now interference with everything that is live and has 719 // compatible register sets. 720 interfere_with_live(r,&liveout); 721 722 } // End of if normal register-allocated value 723 724 // Area remaining in the block 725 inst_count--; 726 cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); 727 728 // Make all inputs live 729 if( !n->is_Phi() ) { // Phi function uses come from prior block 730 JVMState* jvms = n->jvms(); 731 uint debug_start = jvms ? jvms->debug_start() : 999999; 732 // Start loop at 1 (skip control edge) for most Nodes. 733 // SCMemProj's might be the sole use of a StoreLConditional. 734 // While StoreLConditionals set memory (the SCMemProj use) 735 // they also def flags; if that flag def is unused the 736 // allocator sees a flag-setting instruction with no use of 737 // the flags and assumes it's dead. This keeps the (useless) 738 // flag-setting behavior alive while also keeping the (useful) 739 // memory update effect. 740 for( uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++ ) { 741 Node *def = n->in(k); 742 uint x = n2lidx(def); 743 if( !x ) continue; 744 LRG &lrg = lrgs(x); 745 // No use-side cost for spilling debug info 746 if( k < debug_start ) 747 // A USE costs twice block frequency (once for the Load, once 748 // for a Load-delay). Rematerialized uses only cost once. 749 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq)); 750 // It is live now 751 if( liveout.insert( x ) ) { 752 // Newly live things assumed live from here to top of block 753 lrg._area += cost; 754 // Adjust register pressure 755 if (lrg.mask().is_UP() && lrg.mask_size()) { 756 if (lrg._is_float || lrg._is_vector) { 757 pressure[1] += lrg.reg_pressure(); 758 759 if( pressure[1] > b->_freg_pressure ) 760 b->_freg_pressure = pressure[1]; 761 762 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 763 pressure[0] += lrg.reg_pressure(); 764 765 if( pressure[0] > b->_reg_pressure ) 766 b->_reg_pressure = pressure[0]; 767 768 } 769 } 770 assert( pressure[0] == count_int_pressure (&liveout), "" ); 771 assert( pressure[1] == count_float_pressure(&liveout), "" ); 772 } 773 assert(!(lrg._area < 0.0), "negative spill area" ); 774 } 775 } 776 } // End of reverse pass over all instructions in block 777 778 // If we run off the top of the block with high pressure and 779 // never see a hi-to-low pressure transition, just record that 780 // the whole block is high pressure. 781 if( pressure[0] > (uint)INTPRESSURE ) { 782 hrp_index[0] = 0; 783 784 if( pressure[0] > b->_reg_pressure ) 785 b->_reg_pressure = pressure[0]; 786 } 787 if( pressure[1] > (uint)FLOATPRESSURE ) { 788 hrp_index[1] = 0; 789 790 if( pressure[1] > b->_freg_pressure ) 791 b->_freg_pressure = pressure[1]; 792 } 793 794 // Compute high pressure indice; avoid landing in the middle of projnodes 795 j = hrp_index[0]; 796 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { 797 Node *cur = b->_nodes[j]; 798 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { 799 j--; 800 cur = b->_nodes[j]; 801 } 802 } 803 b->_ihrp_index = j; 804 j = hrp_index[1]; 805 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { 806 Node *cur = b->_nodes[j]; 807 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { 808 j--; 809 cur = b->_nodes[j]; 810 } 811 } 812 b->_fhrp_index = j; 813 814 #ifndef PRODUCT 815 // Gather Register Pressure Statistics 816 if( PrintOptoStatistics ) { 817 if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE ) 818 _high_pressure++; 819 else 820 _low_pressure++; 821 } 822 #endif 823 } // End of for all blocks 824 825 return must_spill; 826 }