1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/live.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,361 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "memory/allocation.inline.hpp"
1.30 +#include "opto/callnode.hpp"
1.31 +#include "opto/chaitin.hpp"
1.32 +#include "opto/live.hpp"
1.33 +#include "opto/machnode.hpp"
1.34 +
1.35 +
1.36 +// Compute live-in/live-out. We use a totally incremental algorithm. The LIVE
1.37 +// problem is monotonic. The steady-state solution looks like this: pull a
1.38 +// block from the worklist. It has a set of delta's - values which are newly
1.39 +// live-in from the block. Push these to the live-out sets of all predecessor
1.40 +// blocks. At each predecessor, the new live-out values are ANDed with what is
1.41 +// already live-out (extra stuff is added to the live-out sets). Then the
1.42 +// remaining new live-out values are ANDed with what is locally defined.
1.43 +// Leftover bits become the new live-in for the predecessor block, and the pred
1.44 +// block is put on the worklist.
1.45 +// The locally live-in stuff is computed once and added to predecessor
1.46 +// live-out sets. This separate compilation is done in the outer loop below.
1.47 +PhaseLive::PhaseLive( const PhaseCFG &cfg, const LRG_List &names, Arena *arena ) : Phase(LIVE), _cfg(cfg), _names(names), _arena(arena), _live(0) {
1.48 +}
1.49 +
1.50 +void PhaseLive::compute(uint maxlrg) {
1.51 + _maxlrg = maxlrg;
1.52 + _worklist = new (_arena) Block_List();
1.53 +
1.54 + // Init the sparse live arrays. This data is live on exit from here!
1.55 + // The _live info is the live-out info.
1.56 + _live = (IndexSet*)_arena->Amalloc(sizeof(IndexSet) * _cfg.number_of_blocks());
1.57 + uint i;
1.58 + for (i = 0; i < _cfg.number_of_blocks(); i++) {
1.59 + _live[i].initialize(_maxlrg);
1.60 + }
1.61 +
1.62 + // Init the sparse arrays for delta-sets.
1.63 + ResourceMark rm; // Nuke temp storage on exit
1.64 +
1.65 + // Does the memory used by _defs and _deltas get reclaimed? Does it matter? TT
1.66 +
1.67 + // Array of values defined locally in blocks
1.68 + _defs = NEW_RESOURCE_ARRAY(IndexSet,_cfg.number_of_blocks());
1.69 + for (i = 0; i < _cfg.number_of_blocks(); i++) {
1.70 + _defs[i].initialize(_maxlrg);
1.71 + }
1.72 +
1.73 + // Array of delta-set pointers, indexed by block pre_order-1.
1.74 + _deltas = NEW_RESOURCE_ARRAY(IndexSet*,_cfg.number_of_blocks());
1.75 + memset( _deltas, 0, sizeof(IndexSet*)* _cfg.number_of_blocks());
1.76 +
1.77 + _free_IndexSet = NULL;
1.78 +
1.79 + // Blocks having done pass-1
1.80 + VectorSet first_pass(Thread::current()->resource_area());
1.81 +
1.82 + // Outer loop: must compute local live-in sets and push into predecessors.
1.83 + for (uint j = _cfg.number_of_blocks(); j > 0; j--) {
1.84 + Block* block = _cfg.get_block(j - 1);
1.85 +
1.86 + // Compute the local live-in set. Start with any new live-out bits.
1.87 + IndexSet* use = getset(block);
1.88 + IndexSet* def = &_defs[block->_pre_order-1];
1.89 + DEBUG_ONLY(IndexSet *def_outside = getfreeset();)
1.90 + uint i;
1.91 + for (i = block->number_of_nodes(); i > 1; i--) {
1.92 + Node* n = block->get_node(i-1);
1.93 + if (n->is_Phi()) {
1.94 + break;
1.95 + }
1.96 +
1.97 + uint r = _names.at(n->_idx);
1.98 + assert(!def_outside->member(r), "Use of external LRG overlaps the same LRG defined in this block");
1.99 + def->insert( r );
1.100 + use->remove( r );
1.101 + uint cnt = n->req();
1.102 + for (uint k = 1; k < cnt; k++) {
1.103 + Node *nk = n->in(k);
1.104 + uint nkidx = nk->_idx;
1.105 + if (_cfg.get_block_for_node(nk) != block) {
1.106 + uint u = _names.at(nkidx);
1.107 + use->insert(u);
1.108 + DEBUG_ONLY(def_outside->insert(u);)
1.109 + }
1.110 + }
1.111 + }
1.112 +#ifdef ASSERT
1.113 + def_outside->set_next(_free_IndexSet);
1.114 + _free_IndexSet = def_outside; // Drop onto free list
1.115 +#endif
1.116 + // Remove anything defined by Phis and the block start instruction
1.117 + for (uint k = i; k > 0; k--) {
1.118 + uint r = _names.at(block->get_node(k - 1)->_idx);
1.119 + def->insert(r);
1.120 + use->remove(r);
1.121 + }
1.122 +
1.123 + // Push these live-in things to predecessors
1.124 + for (uint l = 1; l < block->num_preds(); l++) {
1.125 + Block* p = _cfg.get_block_for_node(block->pred(l));
1.126 + add_liveout(p, use, first_pass);
1.127 +
1.128 + // PhiNode uses go in the live-out set of prior blocks.
1.129 + for (uint k = i; k > 0; k--) {
1.130 + add_liveout(p, _names.at(block->get_node(k-1)->in(l)->_idx), first_pass);
1.131 + }
1.132 + }
1.133 + freeset(block);
1.134 + first_pass.set(block->_pre_order);
1.135 +
1.136 + // Inner loop: blocks that picked up new live-out values to be propagated
1.137 + while (_worklist->size()) {
1.138 + Block* block = _worklist->pop();
1.139 + IndexSet *delta = getset(block);
1.140 + assert( delta->count(), "missing delta set" );
1.141 +
1.142 + // Add new-live-in to predecessors live-out sets
1.143 + for (uint l = 1; l < block->num_preds(); l++) {
1.144 + Block* predecessor = _cfg.get_block_for_node(block->pred(l));
1.145 + add_liveout(predecessor, delta, first_pass);
1.146 + }
1.147 +
1.148 + freeset(block);
1.149 + } // End of while-worklist-not-empty
1.150 +
1.151 + } // End of for-all-blocks-outer-loop
1.152 +
1.153 + // We explicitly clear all of the IndexSets which we are about to release.
1.154 + // This allows us to recycle their internal memory into IndexSet's free list.
1.155 +
1.156 + for (i = 0; i < _cfg.number_of_blocks(); i++) {
1.157 + _defs[i].clear();
1.158 + if (_deltas[i]) {
1.159 + // Is this always true?
1.160 + _deltas[i]->clear();
1.161 + }
1.162 + }
1.163 + IndexSet *free = _free_IndexSet;
1.164 + while (free != NULL) {
1.165 + IndexSet *temp = free;
1.166 + free = free->next();
1.167 + temp->clear();
1.168 + }
1.169 +
1.170 +}
1.171 +
1.172 +#ifndef PRODUCT
1.173 +void PhaseLive::stats(uint iters) const {
1.174 +}
1.175 +#endif
1.176 +
1.177 +// Get an IndexSet for a block. Return existing one, if any. Make a new
1.178 +// empty one if a prior one does not exist.
1.179 +IndexSet *PhaseLive::getset( Block *p ) {
1.180 + IndexSet *delta = _deltas[p->_pre_order-1];
1.181 + if( !delta ) // Not on worklist?
1.182 + // Get a free set; flag as being on worklist
1.183 + delta = _deltas[p->_pre_order-1] = getfreeset();
1.184 + return delta; // Return set of new live-out items
1.185 +}
1.186 +
1.187 +// Pull from free list, or allocate. Internal allocation on the returned set
1.188 +// is always from thread local storage.
1.189 +IndexSet *PhaseLive::getfreeset( ) {
1.190 + IndexSet *f = _free_IndexSet;
1.191 + if( !f ) {
1.192 + f = new IndexSet;
1.193 +// f->set_arena(Thread::current()->resource_area());
1.194 + f->initialize(_maxlrg, Thread::current()->resource_area());
1.195 + } else {
1.196 + // Pull from free list
1.197 + _free_IndexSet = f->next();
1.198 + //f->_cnt = 0; // Reset to empty
1.199 +// f->set_arena(Thread::current()->resource_area());
1.200 + f->initialize(_maxlrg, Thread::current()->resource_area());
1.201 + }
1.202 + return f;
1.203 +}
1.204 +
1.205 +// Free an IndexSet from a block.
1.206 +void PhaseLive::freeset( const Block *p ) {
1.207 + IndexSet *f = _deltas[p->_pre_order-1];
1.208 + f->set_next(_free_IndexSet);
1.209 + _free_IndexSet = f; // Drop onto free list
1.210 + _deltas[p->_pre_order-1] = NULL;
1.211 +}
1.212 +
1.213 +// Add a live-out value to a given blocks live-out set. If it is new, then
1.214 +// also add it to the delta set and stick the block on the worklist.
1.215 +void PhaseLive::add_liveout( Block *p, uint r, VectorSet &first_pass ) {
1.216 + IndexSet *live = &_live[p->_pre_order-1];
1.217 + if( live->insert(r) ) { // If actually inserted...
1.218 + // We extended the live-out set. See if the value is generated locally.
1.219 + // If it is not, then we must extend the live-in set.
1.220 + if( !_defs[p->_pre_order-1].member( r ) ) {
1.221 + if( !_deltas[p->_pre_order-1] && // Not on worklist?
1.222 + first_pass.test(p->_pre_order) )
1.223 + _worklist->push(p); // Actually go on worklist if already 1st pass
1.224 + getset(p)->insert(r);
1.225 + }
1.226 + }
1.227 +}
1.228 +
1.229 +// Add a vector of live-out values to a given blocks live-out set.
1.230 +void PhaseLive::add_liveout( Block *p, IndexSet *lo, VectorSet &first_pass ) {
1.231 + IndexSet *live = &_live[p->_pre_order-1];
1.232 + IndexSet *defs = &_defs[p->_pre_order-1];
1.233 + IndexSet *on_worklist = _deltas[p->_pre_order-1];
1.234 + IndexSet *delta = on_worklist ? on_worklist : getfreeset();
1.235 +
1.236 + IndexSetIterator elements(lo);
1.237 + uint r;
1.238 + while ((r = elements.next()) != 0) {
1.239 + if( live->insert(r) && // If actually inserted...
1.240 + !defs->member( r ) ) // and not defined locally
1.241 + delta->insert(r); // Then add to live-in set
1.242 + }
1.243 +
1.244 + if( delta->count() ) { // If actually added things
1.245 + _deltas[p->_pre_order-1] = delta; // Flag as on worklist now
1.246 + if( !on_worklist && // Not on worklist?
1.247 + first_pass.test(p->_pre_order) )
1.248 + _worklist->push(p); // Actually go on worklist if already 1st pass
1.249 + } else { // Nothing there; just free it
1.250 + delta->set_next(_free_IndexSet);
1.251 + _free_IndexSet = delta; // Drop onto free list
1.252 + }
1.253 +}
1.254 +
1.255 +#ifndef PRODUCT
1.256 +// Dump the live-out set for a block
1.257 +void PhaseLive::dump( const Block *b ) const {
1.258 + tty->print("Block %d: ",b->_pre_order);
1.259 + tty->print("LiveOut: "); _live[b->_pre_order-1].dump();
1.260 + uint cnt = b->number_of_nodes();
1.261 + for( uint i=0; i<cnt; i++ ) {
1.262 + tty->print("L%d/", _names.at(b->get_node(i)->_idx));
1.263 + b->get_node(i)->dump();
1.264 + }
1.265 + tty->print("\n");
1.266 +}
1.267 +
1.268 +// Verify that base pointers and derived pointers are still sane.
1.269 +void PhaseChaitin::verify_base_ptrs( ResourceArea *a ) const {
1.270 +#ifdef ASSERT
1.271 + Unique_Node_List worklist(a);
1.272 + for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
1.273 + Block* block = _cfg.get_block(i);
1.274 + for (uint j = block->end_idx() + 1; j > 1; j--) {
1.275 + Node* n = block->get_node(j-1);
1.276 + if (n->is_Phi()) {
1.277 + break;
1.278 + }
1.279 + // Found a safepoint?
1.280 + if (n->is_MachSafePoint()) {
1.281 + MachSafePointNode *sfpt = n->as_MachSafePoint();
1.282 + JVMState* jvms = sfpt->jvms();
1.283 + if (jvms != NULL) {
1.284 + // Now scan for a live derived pointer
1.285 + if (jvms->oopoff() < sfpt->req()) {
1.286 + // Check each derived/base pair
1.287 + for (uint idx = jvms->oopoff(); idx < sfpt->req(); idx++) {
1.288 + Node *check = sfpt->in(idx);
1.289 + bool is_derived = ((idx - jvms->oopoff()) & 1) == 0;
1.290 + // search upwards through spills and spill phis for AddP
1.291 + worklist.clear();
1.292 + worklist.push(check);
1.293 + uint k = 0;
1.294 + while( k < worklist.size() ) {
1.295 + check = worklist.at(k);
1.296 + assert(check,"Bad base or derived pointer");
1.297 + // See PhaseChaitin::find_base_for_derived() for all cases.
1.298 + int isc = check->is_Copy();
1.299 + if( isc ) {
1.300 + worklist.push(check->in(isc));
1.301 + } else if( check->is_Phi() ) {
1.302 + for (uint m = 1; m < check->req(); m++)
1.303 + worklist.push(check->in(m));
1.304 + } else if( check->is_Con() ) {
1.305 + if (is_derived) {
1.306 + // Derived is NULL+offset
1.307 + assert(!is_derived || check->bottom_type()->is_ptr()->ptr() == TypePtr::Null,"Bad derived pointer");
1.308 + } else {
1.309 + assert(check->bottom_type()->is_ptr()->_offset == 0,"Bad base pointer");
1.310 + // Base either ConP(NULL) or loadConP
1.311 + if (check->is_Mach()) {
1.312 + assert(check->as_Mach()->ideal_Opcode() == Op_ConP,"Bad base pointer");
1.313 + } else {
1.314 + assert(check->Opcode() == Op_ConP &&
1.315 + check->bottom_type()->is_ptr()->ptr() == TypePtr::Null,"Bad base pointer");
1.316 + }
1.317 + }
1.318 + } else if( check->bottom_type()->is_ptr()->_offset == 0 ) {
1.319 + if(check->is_Proj() || check->is_Mach() &&
1.320 + (check->as_Mach()->ideal_Opcode() == Op_CreateEx ||
1.321 + check->as_Mach()->ideal_Opcode() == Op_ThreadLocal ||
1.322 + check->as_Mach()->ideal_Opcode() == Op_CMoveP ||
1.323 + check->as_Mach()->ideal_Opcode() == Op_CheckCastPP ||
1.324 +#ifdef _LP64
1.325 + UseCompressedOops && check->as_Mach()->ideal_Opcode() == Op_CastPP ||
1.326 + UseCompressedOops && check->as_Mach()->ideal_Opcode() == Op_DecodeN ||
1.327 + UseCompressedClassPointers && check->as_Mach()->ideal_Opcode() == Op_DecodeNKlass ||
1.328 +#endif
1.329 + check->as_Mach()->ideal_Opcode() == Op_LoadP ||
1.330 + check->as_Mach()->ideal_Opcode() == Op_LoadKlass)) {
1.331 + // Valid nodes
1.332 + } else {
1.333 + check->dump();
1.334 + assert(false,"Bad base or derived pointer");
1.335 + }
1.336 + } else {
1.337 + assert(is_derived,"Bad base pointer");
1.338 + assert(check->is_Mach() && check->as_Mach()->ideal_Opcode() == Op_AddP,"Bad derived pointer");
1.339 + }
1.340 + k++;
1.341 + assert(k < 100000,"Derived pointer checking in infinite loop");
1.342 + } // End while
1.343 + }
1.344 + } // End of check for derived pointers
1.345 + } // End of Kcheck for debug info
1.346 + } // End of if found a safepoint
1.347 + } // End of forall instructions in block
1.348 + } // End of forall blocks
1.349 +#endif
1.350 +}
1.351 +
1.352 +// Verify that graphs and base pointers are still sane.
1.353 +void PhaseChaitin::verify( ResourceArea *a, bool verify_ifg ) const {
1.354 +#ifdef ASSERT
1.355 + if( VerifyOpto || VerifyRegisterAllocator ) {
1.356 + _cfg.verify();
1.357 + verify_base_ptrs(a);
1.358 + if(verify_ifg)
1.359 + _ifg->verify(this);
1.360 + }
1.361 +#endif
1.362 +}
1.363 +
1.364 +#endif
