ifg.cpp revision 4514:8373c19be854
1215166Slstewart/* 2215166Slstewart * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved. 3215166Slstewart * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4215166Slstewart * 5215166Slstewart * This code is free software; you can redistribute it and/or modify it 6215166Slstewart * under the terms of the GNU General Public License version 2 only, as 7215166Slstewart * published by the Free Software Foundation. 8215166Slstewart * 9220560Slstewart * This code is distributed in the hope that it will be useful, but WITHOUT 10220560Slstewart * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11220560Slstewart * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12215166Slstewart * version 2 for more details (a copy is included in the LICENSE file that 13215166Slstewart * accompanied this code). 14215166Slstewart * 15215166Slstewart * You should have received a copy of the GNU General Public License version 16215166Slstewart * 2 along with this work; if not, write to the Free Software Foundation, 17215166Slstewart * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18215166Slstewart * 19215166Slstewart * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20215166Slstewart * or visit www.oracle.com if you need additional information or have any 21215166Slstewart * questions. 22215166Slstewart * 23215166Slstewart */ 24215166Slstewart 25215166Slstewart#include "precompiled.hpp" 26215166Slstewart#include "compiler/oopMap.hpp" 27215166Slstewart#include "memory/allocation.inline.hpp" 28215166Slstewart#include "opto/addnode.hpp" 29215166Slstewart#include "opto/block.hpp" 30215166Slstewart#include "opto/callnode.hpp" 31215166Slstewart#include "opto/cfgnode.hpp" 32215166Slstewart#include "opto/chaitin.hpp" 33215166Slstewart#include "opto/coalesce.hpp" 34215166Slstewart#include "opto/connode.hpp" 35215166Slstewart#include "opto/indexSet.hpp" 36215166Slstewart#include "opto/machnode.hpp" 37215166Slstewart#include "opto/memnode.hpp" 38215166Slstewart#include "opto/opcodes.hpp" 39215166Slstewart 40215166Slstewart//============================================================================= 41220560Slstewart//------------------------------IFG-------------------------------------------- 42220560SlstewartPhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) { 43220560Slstewart} 44220560Slstewart 45220560Slstewart//------------------------------init------------------------------------------- 46215166Slstewartvoid PhaseIFG::init( uint maxlrg ) { 47215166Slstewart _maxlrg = maxlrg; 48215166Slstewart _yanked = new (_arena) VectorSet(_arena); 49215166Slstewart _is_square = false; 50215166Slstewart // Make uninitialized adjacency lists 51215166Slstewart _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg); 52215166Slstewart // Also make empty live range structures 53215166Slstewart _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) ); 54215166Slstewart memset(_lrgs,0,sizeof(LRG)*maxlrg); 55215166Slstewart // Init all to empty 56215166Slstewart for( uint i = 0; i < maxlrg; i++ ) { 57215166Slstewart _adjs[i].initialize(maxlrg); 58215166Slstewart _lrgs[i].Set_All(); 59215166Slstewart } 60215166Slstewart} 61215166Slstewart 62215166Slstewart//------------------------------add-------------------------------------------- 63215166Slstewart// Add edge between vertices a & b. These are sorted (triangular matrix), 64215166Slstewart// then the smaller number is inserted in the larger numbered array. 65215166Slstewartint PhaseIFG::add_edge( uint a, uint b ) { 66215166Slstewart lrgs(a).invalid_degree(); 67215166Slstewart lrgs(b).invalid_degree(); 68215166Slstewart // Sort a and b, so that a is bigger 69215166Slstewart assert( !_is_square, "only on triangular" ); 70215166Slstewart if( a < b ) { uint tmp = a; a = b; b = tmp; } 71215166Slstewart return _adjs[a].insert( b ); 72215166Slstewart} 73215166Slstewart 74215166Slstewart//------------------------------add_vector------------------------------------- 75215166Slstewart// Add an edge between 'a' and everything in the vector. 76215166Slstewartvoid PhaseIFG::add_vector( uint a, IndexSet *vec ) { 77215166Slstewart // IFG is triangular, so do the inserts where 'a' < 'b'. 78215166Slstewart assert( !_is_square, "only on triangular" ); 79215166Slstewart IndexSet *adjs_a = &_adjs[a]; 80215166Slstewart if( !vec->count() ) return; 81215166Slstewart 82215166Slstewart IndexSetIterator elements(vec); 83215166Slstewart uint neighbor; 84215166Slstewart while ((neighbor = elements.next()) != 0) { 85215395Slstewart add_edge( a, neighbor ); 86215166Slstewart } 87215166Slstewart} 88215166Slstewart 89215166Slstewart//------------------------------test------------------------------------------- 90215166Slstewart// Is there an edge between a and b? 91215166Slstewartint PhaseIFG::test_edge( uint a, uint b ) const { 92215166Slstewart // Sort a and b, so that a is larger 93215393Slstewart assert( !_is_square, "only on triangular" ); 94215166Slstewart if( a < b ) { uint tmp = a; a = b; b = tmp; } 95273847Shselasky return _adjs[a].member(b); 96215166Slstewart} 97273847Shselasky 98273847Shselasky//------------------------------SquareUp--------------------------------------- 99273847Shselasky// Convert triangular matrix to square matrix 100273847Shselaskyvoid PhaseIFG::SquareUp() { 101215166Slstewart assert( !_is_square, "only on triangular" ); 102273847Shselasky 103215166Slstewart // Simple transpose 104273847Shselasky for( uint i = 0; i < _maxlrg; i++ ) { 105273847Shselasky IndexSetIterator elements(&_adjs[i]); 106273847Shselasky uint datum; 107273847Shselasky while ((datum = elements.next()) != 0) { 108273847Shselasky _adjs[datum].insert( i ); 109273847Shselasky } 110273847Shselasky } 111273847Shselasky _is_square = true; 112273847Shselasky} 113273847Shselasky 114273847Shselasky//------------------------------Compute_Effective_Degree----------------------- 115273847Shselasky// Compute effective degree in bulk 116273847Shselaskyvoid PhaseIFG::Compute_Effective_Degree() { 117273847Shselasky assert( _is_square, "only on square" ); 118215166Slstewart 119273847Shselasky for( uint i = 0; i < _maxlrg; i++ ) 120273847Shselasky lrgs(i).set_degree(effective_degree(i)); 121273847Shselasky} 122215166Slstewart 123215166Slstewart//------------------------------test_edge_sq----------------------------------- 124215166Slstewartint PhaseIFG::test_edge_sq( uint a, uint b ) const { 125215166Slstewart assert( _is_square, "only on square" ); 126215166Slstewart // Swap, so that 'a' has the lesser count. Then binary search is on 127215166Slstewart // the smaller of a's list and b's list. 128215166Slstewart if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; } 129215166Slstewart //return _adjs[a].unordered_member(b); 130215166Slstewart return _adjs[a].member(b); 131215166Slstewart} 132217748Slstewart 133215166Slstewart//------------------------------Union------------------------------------------ 134217748Slstewart// Union edges of B into A 135215166Slstewartvoid PhaseIFG::Union( uint a, uint b ) { 136215166Slstewart assert( _is_square, "only on square" ); 137217748Slstewart IndexSet *A = &_adjs[a]; 138217748Slstewart IndexSetIterator b_elements(&_adjs[b]); 139217748Slstewart uint datum; 140217748Slstewart while ((datum = b_elements.next()) != 0) { 141217748Slstewart if(A->insert(datum)) { 142217748Slstewart _adjs[datum].insert(a); 143217748Slstewart lrgs(a).invalid_degree(); 144217748Slstewart lrgs(datum).invalid_degree(); 145215166Slstewart } 146215166Slstewart } 147215166Slstewart} 148217748Slstewart 149217748Slstewart//------------------------------remove_node------------------------------------ 150217748Slstewart// Yank a Node and all connected edges from the IFG. Return a 151217748Slstewart// list of neighbors (edges) yanked. 152217748SlstewartIndexSet *PhaseIFG::remove_node( uint a ) { 153217748Slstewart assert( _is_square, "only on square" ); 154217748Slstewart assert( !_yanked->test(a), "" ); 155215166Slstewart _yanked->set(a); 156215166Slstewart 157215166Slstewart // I remove the LRG from all neighbors. 158217748Slstewart IndexSetIterator elements(&_adjs[a]); 159217748Slstewart LRG &lrg_a = lrgs(a); 160217748Slstewart uint datum; 161215166Slstewart while ((datum = elements.next()) != 0) { 162217748Slstewart _adjs[datum].remove(a); 163215166Slstewart lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) ); 164215166Slstewart } 165215166Slstewart return neighbors(a); 166215166Slstewart} 167215166Slstewart 168215166Slstewart//------------------------------re_insert-------------------------------------- 169270711Shselasky// Re-insert a yanked Node. 170215166Slstewartvoid PhaseIFG::re_insert( uint a ) { 171215166Slstewart assert( _is_square, "only on square" ); 172215166Slstewart assert( _yanked->test(a), "" ); 173215166Slstewart (*_yanked) >>= a; 174215166Slstewart 175215166Slstewart IndexSetIterator elements(&_adjs[a]); 176215166Slstewart uint datum; 177215395Slstewart while ((datum = elements.next()) != 0) { 178215395Slstewart _adjs[datum].insert(a); 179215395Slstewart lrgs(datum).invalid_degree(); 180215395Slstewart } 181215395Slstewart} 182215395Slstewart 183215395Slstewart//------------------------------compute_degree--------------------------------- 184215395Slstewart// Compute the degree between 2 live ranges. If both live ranges are 185215395Slstewart// aligned-adjacent powers-of-2 then we use the MAX size. If either is 186215395Slstewart// mis-aligned (or for Fat-Projections, not-adjacent) then we have to 187215395Slstewart// MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 188215395Slstewart// this is so. 189215395Slstewartint LRG::compute_degree( LRG &l ) const { 190215395Slstewart int tmp; 191215395Slstewart int num_regs = _num_regs; 192215395Slstewart int nregs = l.num_regs(); 193215395Slstewart tmp = (_fat_proj || l._fat_proj) // either is a fat-proj? 194215395Slstewart ? (num_regs * nregs) // then use product 195215395Slstewart : MAX2(num_regs,nregs); // else use max 196215395Slstewart return tmp; 197215395Slstewart} 198215395Slstewart 199215166Slstewart//------------------------------effective_degree------------------------------- 200215166Slstewart// Compute effective degree for this live range. If both live ranges are 201215377Slstewart// aligned-adjacent powers-of-2 then we use the MAX size. If either is 202215377Slstewart// mis-aligned (or for Fat-Projections, not-adjacent) then we have to 203215166Slstewart// MULTIPLY the sizes. Inspect Brigg's thesis on register pairs to see why 204215166Slstewart// this is so. 205215166Slstewartint PhaseIFG::effective_degree( uint lidx ) const { 206215166Slstewart int eff = 0; 207215166Slstewart int num_regs = lrgs(lidx).num_regs(); 208215166Slstewart int fat_proj = lrgs(lidx)._fat_proj; 209215166Slstewart IndexSet *s = neighbors(lidx); 210215166Slstewart IndexSetIterator elements(s); 211215166Slstewart uint nidx; 212215166Slstewart while((nidx = elements.next()) != 0) { 213215166Slstewart LRG &lrgn = lrgs(nidx); 214215166Slstewart int nregs = lrgn.num_regs(); 215215166Slstewart eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj? 216215166Slstewart ? (num_regs * nregs) // then use product 217215166Slstewart : MAX2(num_regs,nregs); // else use max 218215166Slstewart } 219215166Slstewart return eff; 220215166Slstewart} 221215166Slstewart 222215166Slstewart 223215166Slstewart#ifndef PRODUCT 224215166Slstewart//------------------------------dump------------------------------------------- 225215166Slstewartvoid PhaseIFG::dump() const { 226215166Slstewart tty->print_cr("-- Interference Graph --%s--", 227215395Slstewart _is_square ? "square" : "triangular" ); 228215166Slstewart if( _is_square ) { 229215166Slstewart for( uint i = 0; i < _maxlrg; i++ ) { 230215166Slstewart tty->print( (*_yanked)[i] ? "XX " : " "); 231215166Slstewart tty->print("L%d: { ",i); 232215166Slstewart IndexSetIterator elements(&_adjs[i]); 233215166Slstewart uint datum; 234215393Slstewart while ((datum = elements.next()) != 0) { 235215392Slstewart tty->print("L%d ", datum); 236215166Slstewart } 237215392Slstewart tty->print_cr("}"); 238215392Slstewart 239215392Slstewart } 240215392Slstewart return; 241215166Slstewart } 242215392Slstewart 243215166Slstewart // Triangular 244215166Slstewart for( uint i = 0; i < _maxlrg; i++ ) { 245215166Slstewart uint j; 246215166Slstewart tty->print( (*_yanked)[i] ? "XX " : " "); 247215166Slstewart tty->print("L%d: { ",i); 248215166Slstewart for( j = _maxlrg; j > i; j-- ) 249215166Slstewart if( test_edge(j - 1,i) ) { 250215166Slstewart tty->print("L%d ",j - 1); 251215166Slstewart } 252215166Slstewart tty->print("| "); 253215166Slstewart IndexSetIterator elements(&_adjs[i]); 254215166Slstewart uint datum; 255215166Slstewart while ((datum = elements.next()) != 0) { 256215166Slstewart tty->print("L%d ", datum); 257215166Slstewart } 258215166Slstewart tty->print("}\n"); 259215166Slstewart } 260215166Slstewart tty->print("\n"); 261215166Slstewart} 262215166Slstewart 263215166Slstewart//------------------------------stats------------------------------------------ 264215166Slstewartvoid PhaseIFG::stats() const { 265215166Slstewart ResourceMark rm; 266215166Slstewart int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2); 267215166Slstewart memset( h_cnt, 0, sizeof(int)*_maxlrg*2 ); 268215166Slstewart uint i; 269215166Slstewart for( i = 0; i < _maxlrg; i++ ) { 270215166Slstewart h_cnt[neighbor_cnt(i)]++; 271215166Slstewart } 272215166Slstewart tty->print_cr("--Histogram of counts--"); 273215166Slstewart for( i = 0; i < _maxlrg*2; i++ ) 274215166Slstewart if( h_cnt[i] ) 275215166Slstewart tty->print("%d/%d ",i,h_cnt[i]); 276215166Slstewart tty->print_cr(""); 277215166Slstewart} 278215166Slstewart 279215166Slstewart//------------------------------verify----------------------------------------- 280215166Slstewartvoid PhaseIFG::verify( const PhaseChaitin *pc ) const { 281215166Slstewart // IFG is square, sorted and no need for Find 282215166Slstewart for( uint i = 0; i < _maxlrg; i++ ) { 283215166Slstewart assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" ); 284215166Slstewart IndexSet *set = &_adjs[i]; 285215166Slstewart IndexSetIterator elements(set); 286215166Slstewart uint idx; 287215166Slstewart uint last = 0; 288215166Slstewart while ((idx = elements.next()) != 0) { 289215166Slstewart assert(idx != i, "Must have empty diagonal"); 290215166Slstewart assert(pc->_lrg_map.find_const(idx) == idx, "Must not need Find"); 291215166Slstewart assert(_adjs[idx].member(i), "IFG not square"); 292215166Slstewart assert(!(*_yanked)[idx], "No yanked neighbors"); 293215166Slstewart assert(last < idx, "not sorted increasing"); 294215166Slstewart last = idx; 295215166Slstewart } 296215166Slstewart assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong"); 297215166Slstewart } 298215166Slstewart} 299215166Slstewart#endif 300215166Slstewart 301215166Slstewart//------------------------------interfere_with_live---------------------------- 302215166Slstewart// Interfere this register with everything currently live. Use the RegMasks 303215166Slstewart// to trim the set of possible interferences. Return a count of register-only 304215166Slstewart// interferences as an estimate of register pressure. 305215166Slstewartvoid PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) { 306215166Slstewart uint retval = 0; 307215166Slstewart // Interfere with everything live. 308215166Slstewart const RegMask &rm = lrgs(r).mask(); 309215166Slstewart // Check for interference by checking overlap of regmasks. 310215166Slstewart // Only interfere if acceptable register masks overlap. 311215166Slstewart IndexSetIterator elements(liveout); 312215166Slstewart uint l; 313215166Slstewart while( (l = elements.next()) != 0 ) 314215166Slstewart if( rm.overlap( lrgs(l).mask() ) ) 315215377Slstewart _ifg->add_edge( r, l ); 316215377Slstewart} 317215166Slstewart 318215166Slstewart//------------------------------build_ifg_virtual------------------------------ 319215166Slstewart// Actually build the interference graph. Uses virtual registers only, no 320215166Slstewart// physical register masks. This allows me to be very aggressive when 321215395Slstewart// coalescing copies. Some of this aggressiveness will have to be undone 322215166Slstewart// later, but I'd rather get all the copies I can now (since unremoved copies 323215166Slstewart// at this point can end up in bad places). Copies I re-insert later I have 324215166Slstewart// more opportunity to insert them in low-frequency locations. 325215166Slstewartvoid PhaseChaitin::build_ifg_virtual( ) { 326215166Slstewart 327 // For all blocks (in any order) do... 328 for( uint i=0; i<_cfg._num_blocks; i++ ) { 329 Block *b = _cfg._blocks[i]; 330 IndexSet *liveout = _live->live(b); 331 332 // The IFG is built by a single reverse pass over each basic block. 333 // Starting with the known live-out set, we remove things that get 334 // defined and add things that become live (essentially executing one 335 // pass of a standard LIVE analysis). Just before a Node defines a value 336 // (and removes it from the live-ness set) that value is certainly live. 337 // The defined value interferes with everything currently live. The 338 // value is then removed from the live-ness set and it's inputs are 339 // added to the live-ness set. 340 for( uint j = b->end_idx() + 1; j > 1; j-- ) { 341 Node *n = b->_nodes[j-1]; 342 343 // Get value being defined 344 uint r = _lrg_map.live_range_id(n); 345 346 // Some special values do not allocate 347 if (r) { 348 349 // Remove from live-out set 350 liveout->remove(r); 351 352 // Copies do not define a new value and so do not interfere. 353 // Remove the copies source from the liveout set before interfering. 354 uint idx = n->is_Copy(); 355 if (idx) { 356 liveout->remove(_lrg_map.live_range_id(n->in(idx))); 357 } 358 359 // Interfere with everything live 360 interfere_with_live(r, liveout); 361 } 362 363 // Make all inputs live 364 if (!n->is_Phi()) { // Phi function uses come from prior block 365 for(uint k = 1; k < n->req(); k++) { 366 liveout->insert(_lrg_map.live_range_id(n->in(k))); 367 } 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 = _lrg_map.live_range_id(n->in(idx)); 400 for (uint k = 1; k < n->req(); k++) { 401 uint kidx = _lrg_map.live_range_id(n->in(k)); 402 if (kidx != lidx) { 403 _ifg->add_edge(r, kidx); 404 } 405 } 406 } 407 } // End of forall instructions in block 408 } // End of forall blocks 409} 410 411//------------------------------count_int_pressure----------------------------- 412uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) { 413 IndexSetIterator elements(liveout); 414 uint lidx; 415 uint cnt = 0; 416 while ((lidx = elements.next()) != 0) { 417 if( lrgs(lidx).mask().is_UP() && 418 lrgs(lidx).mask_size() && 419 !lrgs(lidx)._is_float && 420 !lrgs(lidx)._is_vector && 421 lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) 422 cnt += lrgs(lidx).reg_pressure(); 423 } 424 return cnt; 425} 426 427//------------------------------count_float_pressure--------------------------- 428uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) { 429 IndexSetIterator elements(liveout); 430 uint lidx; 431 uint cnt = 0; 432 while ((lidx = elements.next()) != 0) { 433 if( lrgs(lidx).mask().is_UP() && 434 lrgs(lidx).mask_size() && 435 (lrgs(lidx)._is_float || lrgs(lidx)._is_vector)) 436 cnt += lrgs(lidx).reg_pressure(); 437 } 438 return cnt; 439} 440 441//------------------------------lower_pressure--------------------------------- 442// Adjust register pressure down by 1. Capture last hi-to-low transition, 443static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) { 444 if (lrg->mask().is_UP() && lrg->mask_size()) { 445 if (lrg->_is_float || lrg->_is_vector) { 446 pressure[1] -= lrg->reg_pressure(); 447 if( pressure[1] == (uint)FLOATPRESSURE ) { 448 hrp_index[1] = where; 449 if( pressure[1] > b->_freg_pressure ) 450 b->_freg_pressure = pressure[1]+1; 451 } 452 } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 453 pressure[0] -= lrg->reg_pressure(); 454 if( pressure[0] == (uint)INTPRESSURE ) { 455 hrp_index[0] = where; 456 if( pressure[0] > b->_reg_pressure ) 457 b->_reg_pressure = pressure[0]+1; 458 } 459 } 460 } 461} 462 463//------------------------------build_ifg_physical----------------------------- 464// Build the interference graph using physical registers when available. 465// That is, if 2 live ranges are simultaneously alive but in their acceptable 466// register sets do not overlap, then they do not interfere. 467uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) { 468 NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); ) 469 470 uint spill_reg = LRG::SPILL_REG; 471 uint must_spill = 0; 472 473 // For all blocks (in any order) do... 474 for( uint i = 0; i < _cfg._num_blocks; i++ ) { 475 Block *b = _cfg._blocks[i]; 476 // Clone (rather than smash in place) the liveout info, so it is alive 477 // for the "collect_gc_info" phase later. 478 IndexSet liveout(_live->live(b)); 479 uint last_inst = b->end_idx(); 480 // Compute first nonphi node index 481 uint first_inst; 482 for( first_inst = 1; first_inst < last_inst; first_inst++ ) 483 if( !b->_nodes[first_inst]->is_Phi() ) 484 break; 485 486 // Spills could be inserted before CreateEx node which should be 487 // first instruction in block after Phis. Move CreateEx up. 488 for( uint insidx = first_inst; insidx < last_inst; insidx++ ) { 489 Node *ex = b->_nodes[insidx]; 490 if( ex->is_SpillCopy() ) continue; 491 if( insidx > first_inst && ex->is_Mach() && 492 ex->as_Mach()->ideal_Opcode() == Op_CreateEx ) { 493 // If the CreateEx isn't above all the MachSpillCopies 494 // then move it to the top. 495 b->_nodes.remove(insidx); 496 b->_nodes.insert(first_inst, ex); 497 } 498 // Stop once a CreateEx or any other node is found 499 break; 500 } 501 502 // Reset block's register pressure values for each ifg construction 503 uint pressure[2], hrp_index[2]; 504 pressure[0] = pressure[1] = 0; 505 hrp_index[0] = hrp_index[1] = last_inst+1; 506 b->_reg_pressure = b->_freg_pressure = 0; 507 // Liveout things are presumed live for the whole block. We accumulate 508 // 'area' accordingly. If they get killed in the block, we'll subtract 509 // the unused part of the block from the area. 510 int inst_count = last_inst - first_inst; 511 double cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); 512 assert(!(cost < 0.0), "negative spill cost" ); 513 IndexSetIterator elements(&liveout); 514 uint lidx; 515 while ((lidx = elements.next()) != 0) { 516 LRG &lrg = lrgs(lidx); 517 lrg._area += cost; 518 // Compute initial register pressure 519 if (lrg.mask().is_UP() && lrg.mask_size()) { 520 if (lrg._is_float || lrg._is_vector) { // Count float pressure 521 pressure[1] += lrg.reg_pressure(); 522 if( pressure[1] > b->_freg_pressure ) 523 b->_freg_pressure = pressure[1]; 524 // Count int pressure, but do not count the SP, flags 525 } else if( lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 526 pressure[0] += lrg.reg_pressure(); 527 if( pressure[0] > b->_reg_pressure ) 528 b->_reg_pressure = pressure[0]; 529 } 530 } 531 } 532 assert( pressure[0] == count_int_pressure (&liveout), "" ); 533 assert( pressure[1] == count_float_pressure(&liveout), "" ); 534 535 // The IFG is built by a single reverse pass over each basic block. 536 // Starting with the known live-out set, we remove things that get 537 // defined and add things that become live (essentially executing one 538 // pass of a standard LIVE analysis). Just before a Node defines a value 539 // (and removes it from the live-ness set) that value is certainly live. 540 // The defined value interferes with everything currently live. The 541 // value is then removed from the live-ness set and it's inputs are added 542 // to the live-ness set. 543 uint j; 544 for( j = last_inst + 1; j > 1; j-- ) { 545 Node *n = b->_nodes[j - 1]; 546 547 // Get value being defined 548 uint r = _lrg_map.live_range_id(n); 549 550 // Some special values do not allocate 551 if(r) { 552 // A DEF normally costs block frequency; rematerialized values are 553 // removed from the DEF sight, so LOWER costs here. 554 lrgs(r)._cost += n->rematerialize() ? 0 : b->_freq; 555 556 // If it is not live, then this instruction is dead. Probably caused 557 // by spilling and rematerialization. Who cares why, yank this baby. 558 if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) { 559 Node *def = n->in(0); 560 if( !n->is_Proj() || 561 // Could also be a flags-projection of a dead ADD or such. 562 (_lrg_map.live_range_id(def) && !liveout.member(_lrg_map.live_range_id(def)))) { 563 b->_nodes.remove(j - 1); 564 if (lrgs(r)._def == n) { 565 lrgs(r)._def = 0; 566 } 567 n->disconnect_inputs(NULL, C); 568 _cfg._bbs.map(n->_idx,NULL); 569 n->replace_by(C->top()); 570 // Since yanking a Node from block, high pressure moves up one 571 hrp_index[0]--; 572 hrp_index[1]--; 573 continue; 574 } 575 576 // Fat-projections kill many registers which cannot be used to 577 // hold live ranges. 578 if (lrgs(r)._fat_proj) { 579 // Count the int-only registers 580 RegMask itmp = lrgs(r).mask(); 581 itmp.AND(*Matcher::idealreg2regmask[Op_RegI]); 582 int iregs = itmp.Size(); 583 if( pressure[0]+iregs > b->_reg_pressure ) 584 b->_reg_pressure = pressure[0]+iregs; 585 if( pressure[0] <= (uint)INTPRESSURE && 586 pressure[0]+iregs > (uint)INTPRESSURE ) { 587 hrp_index[0] = j-1; 588 } 589 // Count the float-only registers 590 RegMask ftmp = lrgs(r).mask(); 591 ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]); 592 int fregs = ftmp.Size(); 593 if( pressure[1]+fregs > b->_freg_pressure ) 594 b->_freg_pressure = pressure[1]+fregs; 595 if( pressure[1] <= (uint)FLOATPRESSURE && 596 pressure[1]+fregs > (uint)FLOATPRESSURE ) { 597 hrp_index[1] = j-1; 598 } 599 } 600 601 } else { // Else it is live 602 // A DEF also ends 'area' partway through the block. 603 lrgs(r)._area -= cost; 604 assert(!(lrgs(r)._area < 0.0), "negative spill area" ); 605 606 // Insure high score for immediate-use spill copies so they get a color 607 if( n->is_SpillCopy() 608 && lrgs(r).is_singledef() // MultiDef live range can still split 609 && n->outcnt() == 1 // and use must be in this block 610 && _cfg._bbs[n->unique_out()->_idx] == b ) { 611 // All single-use MachSpillCopy(s) that immediately precede their 612 // use must color early. If a longer live range steals their 613 // color, the spill copy will split and may push another spill copy 614 // further away resulting in an infinite spill-split-retry cycle. 615 // Assigning a zero area results in a high score() and a good 616 // location in the simplify list. 617 // 618 619 Node *single_use = n->unique_out(); 620 assert( b->find_node(single_use) >= j, "Use must be later in block"); 621 // Use can be earlier in block if it is a Phi, but then I should be a MultiDef 622 623 // Find first non SpillCopy 'm' that follows the current instruction 624 // (j - 1) is index for current instruction 'n' 625 Node *m = n; 626 for( uint i = j; i <= last_inst && m->is_SpillCopy(); ++i ) { m = b->_nodes[i]; } 627 if( m == single_use ) { 628 lrgs(r)._area = 0.0; 629 } 630 } 631 632 // Remove from live-out set 633 if( liveout.remove(r) ) { 634 // Adjust register pressure. 635 // Capture last hi-to-lo pressure transition 636 lower_pressure( &lrgs(r), j-1, b, pressure, hrp_index ); 637 assert( pressure[0] == count_int_pressure (&liveout), "" ); 638 assert( pressure[1] == count_float_pressure(&liveout), "" ); 639 } 640 641 // Copies do not define a new value and so do not interfere. 642 // Remove the copies source from the liveout set before interfering. 643 uint idx = n->is_Copy(); 644 if (idx) { 645 uint x = _lrg_map.live_range_id(n->in(idx)); 646 if (liveout.remove(x)) { 647 lrgs(x)._area -= cost; 648 // Adjust register pressure. 649 lower_pressure(&lrgs(x), j-1, b, pressure, hrp_index); 650 assert( pressure[0] == count_int_pressure (&liveout), "" ); 651 assert( pressure[1] == count_float_pressure(&liveout), "" ); 652 } 653 } 654 } // End of if live or not 655 656 // Interfere with everything live. If the defined value must 657 // go in a particular register, just remove that register from 658 // all conflicting parties and avoid the interference. 659 660 // Make exclusions for rematerializable defs. Since rematerializable 661 // DEFs are not bound but the live range is, some uses must be bound. 662 // If we spill live range 'r', it can rematerialize at each use site 663 // according to its bindings. 664 const RegMask &rmask = lrgs(r).mask(); 665 if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) { 666 // Check for common case 667 int r_size = lrgs(r).num_regs(); 668 OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical; 669 // Smear odd bits 670 IndexSetIterator elements(&liveout); 671 uint l; 672 while ((l = elements.next()) != 0) { 673 LRG &lrg = lrgs(l); 674 // If 'l' must spill already, do not further hack his bits. 675 // He'll get some interferences and be forced to spill later. 676 if( lrg._must_spill ) continue; 677 // Remove bound register(s) from 'l's choices 678 RegMask old = lrg.mask(); 679 uint old_size = lrg.mask_size(); 680 // Remove the bits from LRG 'r' from LRG 'l' so 'l' no 681 // longer interferes with 'r'. If 'l' requires aligned 682 // adjacent pairs, subtract out bit pairs. 683 assert(!lrg._is_vector || !lrg._fat_proj, "sanity"); 684 if (lrg.num_regs() > 1 && !lrg._fat_proj) { 685 RegMask r2mask = rmask; 686 // Leave only aligned set of bits. 687 r2mask.smear_to_sets(lrg.num_regs()); 688 // It includes vector case. 689 lrg.SUBTRACT( r2mask ); 690 lrg.compute_set_mask_size(); 691 } else if( r_size != 1 ) { // fat proj 692 lrg.SUBTRACT( rmask ); 693 lrg.compute_set_mask_size(); 694 } else { // Common case: size 1 bound removal 695 if( lrg.mask().Member(r_reg) ) { 696 lrg.Remove(r_reg); 697 lrg.set_mask_size(lrg.mask().is_AllStack() ? 65535:old_size-1); 698 } 699 } 700 // If 'l' goes completely dry, it must spill. 701 if( lrg.not_free() ) { 702 // Give 'l' some kind of reasonable mask, so he picks up 703 // interferences (and will spill later). 704 lrg.set_mask( old ); 705 lrg.set_mask_size(old_size); 706 must_spill++; 707 lrg._must_spill = 1; 708 lrg.set_reg(OptoReg::Name(LRG::SPILL_REG)); 709 } 710 } 711 } // End of if bound 712 713 // Now interference with everything that is live and has 714 // compatible register sets. 715 interfere_with_live(r,&liveout); 716 717 } // End of if normal register-allocated value 718 719 // Area remaining in the block 720 inst_count--; 721 cost = (inst_count <= 0) ? 0.0 : b->_freq * double(inst_count); 722 723 // Make all inputs live 724 if( !n->is_Phi() ) { // Phi function uses come from prior block 725 JVMState* jvms = n->jvms(); 726 uint debug_start = jvms ? jvms->debug_start() : 999999; 727 // Start loop at 1 (skip control edge) for most Nodes. 728 // SCMemProj's might be the sole use of a StoreLConditional. 729 // While StoreLConditionals set memory (the SCMemProj use) 730 // they also def flags; if that flag def is unused the 731 // allocator sees a flag-setting instruction with no use of 732 // the flags and assumes it's dead. This keeps the (useless) 733 // flag-setting behavior alive while also keeping the (useful) 734 // memory update effect. 735 for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) { 736 Node *def = n->in(k); 737 uint x = _lrg_map.live_range_id(def); 738 if (!x) { 739 continue; 740 } 741 LRG &lrg = lrgs(x); 742 // No use-side cost for spilling debug info 743 if (k < debug_start) { 744 // A USE costs twice block frequency (once for the Load, once 745 // for a Load-delay). Rematerialized uses only cost once. 746 lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq + b->_freq)); 747 } 748 // It is live now 749 if (liveout.insert(x)) { 750 // Newly live things assumed live from here to top of block 751 lrg._area += cost; 752 // Adjust register pressure 753 if (lrg.mask().is_UP() && lrg.mask_size()) { 754 if (lrg._is_float || lrg._is_vector) { 755 pressure[1] += lrg.reg_pressure(); 756 if( pressure[1] > b->_freg_pressure ) 757 b->_freg_pressure = pressure[1]; 758 } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) { 759 pressure[0] += lrg.reg_pressure(); 760 if( pressure[0] > b->_reg_pressure ) 761 b->_reg_pressure = pressure[0]; 762 } 763 } 764 assert( pressure[0] == count_int_pressure (&liveout), "" ); 765 assert( pressure[1] == count_float_pressure(&liveout), "" ); 766 } 767 assert(!(lrg._area < 0.0), "negative spill area" ); 768 } 769 } 770 } // End of reverse pass over all instructions in block 771 772 // If we run off the top of the block with high pressure and 773 // never see a hi-to-low pressure transition, just record that 774 // the whole block is high pressure. 775 if( pressure[0] > (uint)INTPRESSURE ) { 776 hrp_index[0] = 0; 777 if( pressure[0] > b->_reg_pressure ) 778 b->_reg_pressure = pressure[0]; 779 } 780 if( pressure[1] > (uint)FLOATPRESSURE ) { 781 hrp_index[1] = 0; 782 if( pressure[1] > b->_freg_pressure ) 783 b->_freg_pressure = pressure[1]; 784 } 785 786 // Compute high pressure indice; avoid landing in the middle of projnodes 787 j = hrp_index[0]; 788 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { 789 Node *cur = b->_nodes[j]; 790 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { 791 j--; 792 cur = b->_nodes[j]; 793 } 794 } 795 b->_ihrp_index = j; 796 j = hrp_index[1]; 797 if( j < b->_nodes.size() && j < b->end_idx()+1 ) { 798 Node *cur = b->_nodes[j]; 799 while( cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch() ) { 800 j--; 801 cur = b->_nodes[j]; 802 } 803 } 804 b->_fhrp_index = j; 805 806#ifndef PRODUCT 807 // Gather Register Pressure Statistics 808 if( PrintOptoStatistics ) { 809 if( b->_reg_pressure > (uint)INTPRESSURE || b->_freg_pressure > (uint)FLOATPRESSURE ) 810 _high_pressure++; 811 else 812 _low_pressure++; 813 } 814#endif 815 } // End of for all blocks 816 817 return must_spill; 818} 819