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