1 /* 2 * Copyright (c) 1997, 2017, 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 "memory/allocation.inline.hpp" 27 #include "memory/resourceArea.hpp" 28 #include "opto/callnode.hpp" 29 #include "opto/chaitin.hpp" 30 #include "opto/live.hpp" 31 #include "opto/machnode.hpp" 32 33 34 // Compute live-in/live-out. We use a totally incremental algorithm. The LIVE 35 // problem is monotonic. The steady-state solution looks like this: pull a 36 // block from the worklist. It has a set of delta's - values which are newly 37 // live-in from the block. Push these to the live-out sets of all predecessor 38 // blocks. At each predecessor, the new live-out values are ANDed with what is 39 // already live-out (extra stuff is added to the live-out sets). Then the 40 // remaining new live-out values are ANDed with what is locally defined. 41 // Leftover bits become the new live-in for the predecessor block, and the pred 42 // block is put on the worklist. 43 // The locally live-in stuff is computed once and added to predecessor 44 // live-out sets. This separate compilation is done in the outer loop below. 45 PhaseLive::PhaseLive(const PhaseCFG &cfg, const LRG_List &names, Arena *arena, bool keep_deltas) 46 : Phase(LIVE), 47 _live(0), 48 _livein(0), 49 _cfg(cfg), 50 _names(names), 51 _arena(arena), 52 _keep_deltas(keep_deltas) { 53 } 54 55 void PhaseLive::compute(uint maxlrg) { 56 _maxlrg = maxlrg; 57 _worklist = new (_arena) Block_List(); 58 59 // Init the sparse live arrays. This data is live on exit from here! 60 // The _live info is the live-out info. 61 _live = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks()); 62 uint i; 63 for (i = 0; i < _cfg.number_of_blocks(); i++) { 64 _live[i].initialize(_maxlrg); 65 } 66 67 if (_keep_deltas) { 68 _livein = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks()); 69 for (i = 0; i < _cfg.number_of_blocks(); i++) { 70 _livein[i].initialize(_maxlrg); 71 } 72 } 73 74 // Init the sparse arrays for delta-sets. 75 ResourceMark rm; // Nuke temp storage on exit 76 77 // Does the memory used by _defs and _deltas get reclaimed? Does it matter? TT 78 79 // Array of values defined locally in blocks 80 _defs = NEW_RESOURCE_ARRAY(IndexSet,_cfg.number_of_blocks()); 81 for (i = 0; i < _cfg.number_of_blocks(); i++) { 82 _defs[i].initialize(_maxlrg); 83 } 84 85 // Array of delta-set pointers, indexed by block pre_order-1. 86 _deltas = NEW_RESOURCE_ARRAY(IndexSet*,_cfg.number_of_blocks()); 87 memset( _deltas, 0, sizeof(IndexSet*)* _cfg.number_of_blocks()); 88 89 _free_IndexSet = NULL; 90 91 // Blocks having done pass-1 92 VectorSet first_pass(Thread::current()->resource_area()); 93 94 // Outer loop: must compute local live-in sets and push into predecessors. 95 for (uint j = _cfg.number_of_blocks(); j > 0; j--) { 96 Block* block = _cfg.get_block(j - 1); 97 98 // Compute the local live-in set. Start with any new live-out bits. 99 IndexSet* use = getset(block); 100 IndexSet* def = &_defs[block->_pre_order-1]; 101 DEBUG_ONLY(IndexSet *def_outside = getfreeset();) 102 uint i; 103 for (i = block->number_of_nodes(); i > 1; i--) { 104 Node* n = block->get_node(i-1); 105 if (n->is_Phi()) { 106 break; 107 } 108 109 uint r = _names.at(n->_idx); 110 assert(!def_outside->member(r), "Use of external LRG overlaps the same LRG defined in this block"); 111 def->insert( r ); 112 use->remove( r ); 113 uint cnt = n->req(); 114 for (uint k = 1; k < cnt; k++) { 115 Node *nk = n->in(k); 116 uint nkidx = nk->_idx; 117 if (_cfg.get_block_for_node(nk) != block) { 118 uint u = _names.at(nkidx); 119 use->insert(u); 120 DEBUG_ONLY(def_outside->insert(u);) 121 } 122 } 123 } 124 #ifdef ASSERT 125 def_outside->set_next(_free_IndexSet); 126 _free_IndexSet = def_outside; // Drop onto free list 127 #endif 128 // Remove anything defined by Phis and the block start instruction 129 for (uint k = i; k > 0; k--) { 130 uint r = _names.at(block->get_node(k - 1)->_idx); 131 def->insert(r); 132 use->remove(r); 133 } 134 135 // Push these live-in things to predecessors 136 for (uint l = 1; l < block->num_preds(); l++) { 137 Block* p = _cfg.get_block_for_node(block->pred(l)); 138 add_liveout(p, use, first_pass); 139 140 // PhiNode uses go in the live-out set of prior blocks. 141 for (uint k = i; k > 0; k--) { 142 Node *phi = block->get_node(k - 1); 143 if (l < phi->req()) { 144 add_liveout(p, _names.at(phi->in(l)->_idx), first_pass); 145 } 146 } 147 } 148 freeset(block); 149 first_pass.set(block->_pre_order); 150 151 // Inner loop: blocks that picked up new live-out values to be propagated 152 while (_worklist->size()) { 153 Block* block = _worklist->pop(); 154 IndexSet *delta = getset(block); 155 assert( delta->count(), "missing delta set" ); 156 157 // Add new-live-in to predecessors live-out sets 158 for (uint l = 1; l < block->num_preds(); l++) { 159 Block* predecessor = _cfg.get_block_for_node(block->pred(l)); 160 add_liveout(predecessor, delta, first_pass); 161 } 162 163 freeset(block); 164 } // End of while-worklist-not-empty 165 166 } // End of for-all-blocks-outer-loop 167 168 // We explicitly clear all of the IndexSets which we are about to release. 169 // This allows us to recycle their internal memory into IndexSet's free list. 170 171 for (i = 0; i < _cfg.number_of_blocks(); i++) { 172 _defs[i].clear(); 173 if (_deltas[i]) { 174 // Is this always true? 175 _deltas[i]->clear(); 176 } 177 } 178 IndexSet *free = _free_IndexSet; 179 while (free != NULL) { 180 IndexSet *temp = free; 181 free = free->next(); 182 temp->clear(); 183 } 184 185 } 186 187 #ifndef PRODUCT 188 void PhaseLive::stats(uint iters) const { 189 } 190 #endif 191 192 // Get an IndexSet for a block. Return existing one, if any. Make a new 193 // empty one if a prior one does not exist. 194 IndexSet *PhaseLive::getset( Block *p ) { 195 IndexSet *delta = _deltas[p->_pre_order-1]; 196 if( !delta ) // Not on worklist? 197 // Get a free set; flag as being on worklist 198 delta = _deltas[p->_pre_order-1] = getfreeset(); 199 return delta; // Return set of new live-out items 200 } 201 202 // Pull from free list, or allocate. Internal allocation on the returned set 203 // is always from thread local storage. 204 IndexSet *PhaseLive::getfreeset( ) { 205 IndexSet *f = _free_IndexSet; 206 if( !f ) { 207 f = new IndexSet; 208 // f->set_arena(Thread::current()->resource_area()); 209 f->initialize(_maxlrg, Thread::current()->resource_area()); 210 } else { 211 // Pull from free list 212 _free_IndexSet = f->next(); 213 //f->_cnt = 0; // Reset to empty 214 // f->set_arena(Thread::current()->resource_area()); 215 f->initialize(_maxlrg, Thread::current()->resource_area()); 216 } 217 return f; 218 } 219 220 // Free an IndexSet from a block. 221 void PhaseLive::freeset( Block *p ) { 222 IndexSet *f = _deltas[p->_pre_order-1]; 223 if ( _keep_deltas ) { 224 add_livein(p, f); 225 } 226 f->set_next(_free_IndexSet); 227 _free_IndexSet = f; // Drop onto free list 228 _deltas[p->_pre_order-1] = NULL; 229 } 230 231 // Add a live-out value to a given blocks live-out set. If it is new, then 232 // also add it to the delta set and stick the block on the worklist. 233 void PhaseLive::add_liveout( Block *p, uint r, VectorSet &first_pass ) { 234 IndexSet *live = &_live[p->_pre_order-1]; 235 if( live->insert(r) ) { // If actually inserted... 236 // We extended the live-out set. See if the value is generated locally. 237 // If it is not, then we must extend the live-in set. 238 if( !_defs[p->_pre_order-1].member( r ) ) { 239 if( !_deltas[p->_pre_order-1] && // Not on worklist? 240 first_pass.test(p->_pre_order) ) 241 _worklist->push(p); // Actually go on worklist if already 1st pass 242 getset(p)->insert(r); 243 } 244 } 245 } 246 247 // Add a vector of live-out values to a given blocks live-out set. 248 void PhaseLive::add_liveout( Block *p, IndexSet *lo, VectorSet &first_pass ) { 249 IndexSet *live = &_live[p->_pre_order-1]; 250 IndexSet *defs = &_defs[p->_pre_order-1]; 251 IndexSet *on_worklist = _deltas[p->_pre_order-1]; 252 IndexSet *delta = on_worklist ? on_worklist : getfreeset(); 253 254 IndexSetIterator elements(lo); 255 uint r; 256 while ((r = elements.next()) != 0) { 257 if( live->insert(r) && // If actually inserted... 258 !defs->member( r ) ) // and not defined locally 259 delta->insert(r); // Then add to live-in set 260 } 261 262 if( delta->count() ) { // If actually added things 263 _deltas[p->_pre_order-1] = delta; // Flag as on worklist now 264 if( !on_worklist && // Not on worklist? 265 first_pass.test(p->_pre_order) ) 266 _worklist->push(p); // Actually go on worklist if already 1st pass 267 } else { // Nothing there; just free it 268 delta->set_next(_free_IndexSet); 269 _free_IndexSet = delta; // Drop onto free list 270 } 271 } 272 273 // Add a vector of live-in values to a given blocks live-in set. 274 void PhaseLive::add_livein(Block *p, IndexSet *lo) { 275 IndexSet *livein = &_livein[p->_pre_order-1]; 276 IndexSetIterator elements(lo); 277 uint r; 278 while ((r = elements.next()) != 0) { 279 livein->insert(r); // Then add to live-in set 280 } 281 } 282 283 #ifndef PRODUCT 284 // Dump the live-out set for a block 285 void PhaseLive::dump( const Block *b ) const { 286 tty->print("Block %d: ",b->_pre_order); 287 if ( _keep_deltas ) { 288 tty->print("LiveIn: "); _livein[b->_pre_order-1].dump(); 289 } 290 tty->print("LiveOut: "); _live[b->_pre_order-1].dump(); 291 uint cnt = b->number_of_nodes(); 292 for( uint i=0; i<cnt; i++ ) { 293 tty->print("L%d/", _names.at(b->get_node(i)->_idx)); 294 b->get_node(i)->dump(); 295 } 296 tty->print("\n"); 297 } 298 299 // Verify that base pointers and derived pointers are still sane. 300 void PhaseChaitin::verify_base_ptrs( ResourceArea *a ) const { 301 #ifdef ASSERT 302 Unique_Node_List worklist(a); 303 for (uint i = 0; i < _cfg.number_of_blocks(); i++) { 304 Block* block = _cfg.get_block(i); 305 for (uint j = block->end_idx() + 1; j > 1; j--) { 306 Node* n = block->get_node(j-1); 307 if (n->is_Phi()) { 308 break; 309 } 310 // Found a safepoint? 311 if (n->is_MachSafePoint()) { 312 MachSafePointNode *sfpt = n->as_MachSafePoint(); 313 JVMState* jvms = sfpt->jvms(); 314 if (jvms != NULL) { 315 // Now scan for a live derived pointer 316 if (jvms->oopoff() < sfpt->req()) { 317 // Check each derived/base pair 318 for (uint idx = jvms->oopoff(); idx < sfpt->req(); idx++) { 319 Node *check = sfpt->in(idx); 320 bool is_derived = ((idx - jvms->oopoff()) & 1) == 0; 321 // search upwards through spills and spill phis for AddP 322 worklist.clear(); 323 worklist.push(check); 324 uint k = 0; 325 while( k < worklist.size() ) { 326 check = worklist.at(k); 327 assert(check,"Bad base or derived pointer"); 328 // See PhaseChaitin::find_base_for_derived() for all cases. 329 int isc = check->is_Copy(); 330 if( isc ) { 331 worklist.push(check->in(isc)); 332 } else if( check->is_Phi() ) { 333 for (uint m = 1; m < check->req(); m++) 334 worklist.push(check->in(m)); 335 } else if( check->is_Con() ) { 336 if (is_derived) { 337 // Derived is NULL+offset 338 assert(!is_derived || check->bottom_type()->is_ptr()->ptr() == TypePtr::Null,"Bad derived pointer"); 339 } else { 340 assert(check->bottom_type()->is_ptr()->offset() == 0,"Bad base pointer"); 341 // Base either ConP(NULL) or loadConP 342 if (check->is_Mach()) { 343 assert(check->as_Mach()->ideal_Opcode() == Op_ConP,"Bad base pointer"); 344 } else { 345 assert(check->Opcode() == Op_ConP && 346 check->bottom_type()->is_ptr()->ptr() == TypePtr::Null,"Bad base pointer"); 347 } 348 } 349 } else if (check->bottom_type()->is_ptr()->offset() == 0) { 350 if(check->is_Proj() || (check->is_Mach() && 351 (check->as_Mach()->ideal_Opcode() == Op_CreateEx || 352 check->as_Mach()->ideal_Opcode() == Op_ThreadLocal || 353 check->as_Mach()->ideal_Opcode() == Op_CMoveP || 354 check->as_Mach()->ideal_Opcode() == Op_CheckCastPP || 355 #ifdef _LP64 356 (UseCompressedOops && check->as_Mach()->ideal_Opcode() == Op_CastPP) || 357 (UseCompressedOops && check->as_Mach()->ideal_Opcode() == Op_DecodeN) || 358 (UseCompressedClassPointers && check->as_Mach()->ideal_Opcode() == Op_DecodeNKlass) || 359 #endif 360 check->as_Mach()->ideal_Opcode() == Op_LoadP || 361 check->as_Mach()->ideal_Opcode() == Op_LoadKlass))) { 362 // Valid nodes 363 } else { 364 check->dump(); 365 assert(false,"Bad base or derived pointer"); 366 } 367 } else { 368 assert(is_derived,"Bad base pointer"); 369 assert(check->is_Mach() && check->as_Mach()->ideal_Opcode() == Op_AddP,"Bad derived pointer"); 370 } 371 k++; 372 assert(k < 100000,"Derived pointer checking in infinite loop"); 373 } // End while 374 } 375 } // End of check for derived pointers 376 } // End of Kcheck for debug info 377 } // End of if found a safepoint 378 } // End of forall instructions in block 379 } // End of forall blocks 380 #endif 381 } 382 383 // Verify that graphs and base pointers are still sane. 384 void PhaseChaitin::verify( ResourceArea *a, bool verify_ifg ) const { 385 #ifdef ASSERT 386 if( VerifyOpto || VerifyRegisterAllocator ) { 387 _cfg.verify(); 388 verify_base_ptrs(a); 389 if(verify_ifg) 390 _ifg->verify(this); 391 } 392 #endif 393 } 394 395 #endif