Mercurial > hg > graal-compiler
view src/share/vm/opto/domgraph.cpp @ 3992:d1bdeef3e3e2
7098282: G1: assert(interval >= 0) failed: Sanity check, referencePolicy.cpp: 76
Summary: There is a race between one thread successfully forwarding and copying the klass mirror for the SoftReference class (including the static master clock) and another thread attempting to use the master clock while attempting to discover a soft reference object. Maintain a shadow copy of the soft reference master clock and use the shadow during reference discovery and reference processing.
Reviewed-by: tonyp, brutisso, ysr
author | johnc |
---|---|
date | Wed, 12 Oct 2011 10:25:51 -0700 |
parents | f95d63e2154a |
children | 5e990493719e |
line wrap: on
line source
/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #include "precompiled.hpp" #include "libadt/vectset.hpp" #include "memory/allocation.hpp" #include "opto/block.hpp" #include "opto/machnode.hpp" #include "opto/phaseX.hpp" #include "opto/rootnode.hpp" // Portions of code courtesy of Clifford Click // Optimization - Graph Style //------------------------------Tarjan----------------------------------------- // A data structure that holds all the information needed to find dominators. struct Tarjan { Block *_block; // Basic block for this info uint _semi; // Semi-dominators uint _size; // Used for faster LINK and EVAL Tarjan *_parent; // Parent in DFS Tarjan *_label; // Used for LINK and EVAL Tarjan *_ancestor; // Used for LINK and EVAL Tarjan *_child; // Used for faster LINK and EVAL Tarjan *_dom; // Parent in dominator tree (immediate dom) Tarjan *_bucket; // Set of vertices with given semidominator Tarjan *_dom_child; // Child in dominator tree Tarjan *_dom_next; // Next in dominator tree // Fast union-find work void COMPRESS(); Tarjan *EVAL(void); void LINK( Tarjan *w, Tarjan *tarjan0 ); void setdepth( uint size ); }; //------------------------------Dominator-------------------------------------- // Compute the dominator tree of the CFG. The CFG must already have been // constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm. void PhaseCFG::Dominators( ) { // Pre-grow the blocks array, prior to the ResourceMark kicking in _blocks.map(_num_blocks,0); ResourceMark rm; // Setup mappings from my Graph to Tarjan's stuff and back // Note: Tarjan uses 1-based arrays Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1); // Tarjan's algorithm, almost verbatim: // Step 1: _rpo_ctr = _num_blocks; uint dfsnum = DFS( tarjan ); if( dfsnum-1 != _num_blocks ) {// Check for unreachable loops! // If the returned dfsnum does not match the number of blocks, then we // must have some unreachable loops. These can be made at any time by // IterGVN. They are cleaned up by CCP or the loop opts, but the last // IterGVN can always make more that are not cleaned up. Highly unlikely // except in ZKM.jar, where endless irreducible loops cause the loop opts // to not get run. // // Having found unreachable loops, we have made a bad RPO _block layout. // We can re-run the above DFS pass with the correct number of blocks, // and hack the Tarjan algorithm below to be robust in the presence of // such dead loops (as was done for the NTarjan code farther below). // Since this situation is so unlikely, instead I've decided to bail out. // CNC 7/24/2001 C->record_method_not_compilable("unreachable loop"); return; } _blocks._cnt = _num_blocks; // Tarjan is using 1-based arrays, so these are some initialize flags tarjan[0]._size = tarjan[0]._semi = 0; tarjan[0]._label = &tarjan[0]; uint i; for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order Tarjan *w = &tarjan[i]; // Get vertex from DFS // Step 2: Node *whead = w->_block->head(); for( uint j=1; j < whead->req(); j++ ) { Block *b = _bbs[whead->in(j)->_idx]; Tarjan *vx = &tarjan[b->_pre_order]; Tarjan *u = vx->EVAL(); if( u->_semi < w->_semi ) w->_semi = u->_semi; } // w is added to a bucket here, and only here. // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). // Thus bucket can be a linked list. // Thus we do not need a small integer name for each Block. w->_bucket = tarjan[w->_semi]._bucket; tarjan[w->_semi]._bucket = w; w->_parent->LINK( w, &tarjan[0] ); // Step 3: for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { Tarjan *u = vx->EVAL(); vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; } } // Step 4: for( i=2; i <= _num_blocks; i++ ) { Tarjan *w = &tarjan[i]; if( w->_dom != &tarjan[w->_semi] ) w->_dom = w->_dom->_dom; w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later } // No immediate dominator for the root Tarjan *w = &tarjan[_broot->_pre_order]; w->_dom = NULL; w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later // Convert the dominator tree array into my kind of graph for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices Tarjan *t = &tarjan[i]; // Handy access Tarjan *tdom = t->_dom; // Handy access to immediate dominator if( tdom ) { // Root has no immediate dominator t->_block->_idom = tdom->_block; // Set immediate dominator t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child tdom->_dom_child = t; // Make me a child of my parent } else t->_block->_idom = NULL; // Root } w->setdepth( _num_blocks+1 ); // Set depth in dominator tree } //----------------------------Block_Stack-------------------------------------- class Block_Stack { private: struct Block_Descr { Block *block; // Block int index; // Index of block's successor pushed on stack int freq_idx; // Index of block's most frequent successor }; Block_Descr *_stack_top; Block_Descr *_stack_max; Block_Descr *_stack; Tarjan *_tarjan; uint most_frequent_successor( Block *b ); public: Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) { _stack = NEW_RESOURCE_ARRAY(Block_Descr, size); _stack_max = _stack + size; _stack_top = _stack - 1; // stack is empty } void push(uint pre_order, Block *b) { Tarjan *t = &_tarjan[pre_order]; // Fast local access b->_pre_order = pre_order; // Flag as visited t->_block = b; // Save actual block t->_semi = pre_order; // Block to DFS map t->_label = t; // DFS to vertex map t->_ancestor = NULL; // Fast LINK & EVAL setup t->_child = &_tarjan[0]; // Sentenial t->_size = 1; t->_bucket = NULL; if (pre_order == 1) t->_parent = NULL; // first block doesn't have parent else { // Save parent (current top block on stack) in DFS t->_parent = &_tarjan[_stack_top->block->_pre_order]; } // Now put this block on stack ++_stack_top; assert(_stack_top < _stack_max, ""); // assert if stack have to grow _stack_top->block = b; _stack_top->index = -1; // Find the index into b->succs[] array of the most frequent successor. _stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0 } Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; } bool is_nonempty() { return (_stack_top >= _stack); } bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); } Block* next_successor() { int i = _stack_top->index; i++; if (i == _stack_top->freq_idx) i++; if (i >= (int)(_stack_top->block->_num_succs)) { i = _stack_top->freq_idx; // process most frequent successor last } _stack_top->index = i; return _stack_top->block->_succs[ i ]; } }; //-------------------------most_frequent_successor----------------------------- // Find the index into the b->succs[] array of the most frequent successor. uint Block_Stack::most_frequent_successor( Block *b ) { uint freq_idx = 0; int eidx = b->end_idx(); Node *n = b->_nodes[eidx]; int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode(); switch( op ) { case Op_CountedLoopEnd: case Op_If: { // Split frequency amongst children float prob = n->as_MachIf()->_prob; // Is succ[0] the TRUE branch or the FALSE branch? if( b->_nodes[eidx+1]->Opcode() == Op_IfFalse ) prob = 1.0f - prob; freq_idx = prob < PROB_FAIR; // freq=1 for succ[0] < 0.5 prob break; } case Op_Catch: // Split frequency amongst children for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ ) if( b->_nodes[eidx+1+freq_idx]->as_CatchProj()->_con == CatchProjNode::fall_through_index ) break; // Handle case of no fall-thru (e.g., check-cast MUST throw an exception) if( freq_idx == b->_num_succs ) freq_idx = 0; break; // Currently there is no support for finding out the most // frequent successor for jumps, so lets just make it the first one case Op_Jump: case Op_Root: case Op_Goto: case Op_NeverBranch: freq_idx = 0; // fall thru break; case Op_TailCall: case Op_TailJump: case Op_Return: case Op_Halt: case Op_Rethrow: break; default: ShouldNotReachHere(); } return freq_idx; } //------------------------------DFS-------------------------------------------- // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. uint PhaseCFG::DFS( Tarjan *tarjan ) { Block *b = _broot; uint pre_order = 1; // Allocate stack of size _num_blocks+1 to avoid frequent realloc Block_Stack bstack(tarjan, _num_blocks+1); // Push on stack the state for the first block bstack.push(pre_order, b); ++pre_order; while (bstack.is_nonempty()) { if (!bstack.last_successor()) { // Walk over all successors in pre-order (DFS). Block *s = bstack.next_successor(); if (s->_pre_order == 0) { // Check for no-pre-order, not-visited // Push on stack the state of successor bstack.push(pre_order, s); ++pre_order; } } else { // Build a reverse post-order in the CFG _blocks array Block *stack_top = bstack.pop(); stack_top->_rpo = --_rpo_ctr; _blocks.map(stack_top->_rpo, stack_top); } } return pre_order; } //------------------------------COMPRESS--------------------------------------- void Tarjan::COMPRESS() { assert( _ancestor != 0, "" ); if( _ancestor->_ancestor != 0 ) { _ancestor->COMPRESS( ); if( _ancestor->_label->_semi < _label->_semi ) _label = _ancestor->_label; _ancestor = _ancestor->_ancestor; } } //------------------------------EVAL------------------------------------------- Tarjan *Tarjan::EVAL() { if( !_ancestor ) return _label; COMPRESS(); return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label; } //------------------------------LINK------------------------------------------- void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) { Tarjan *s = w; while( w->_label->_semi < s->_child->_label->_semi ) { if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) { s->_child->_ancestor = s; s->_child = s->_child->_child; } else { s->_child->_size = s->_size; s = s->_ancestor = s->_child; } } s->_label = w->_label; _size += w->_size; if( _size < (w->_size << 1) ) { Tarjan *tmp = s; s = _child; _child = tmp; } while( s != tarjan0 ) { s->_ancestor = this; s = s->_child; } } //------------------------------setdepth--------------------------------------- void Tarjan::setdepth( uint stack_size ) { Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size); Tarjan **next = top; Tarjan **last; uint depth = 0; *top = this; ++top; do { // next level ++depth; last = top; do { // Set current depth for all tarjans on this level Tarjan *t = *next; // next tarjan from stack ++next; do { t->_block->_dom_depth = depth; // Set depth in dominator tree Tarjan *dom_child = t->_dom_child; t = t->_dom_next; // next tarjan if (dom_child != NULL) { *top = dom_child; // save child on stack ++top; } } while (t != NULL); } while (next < last); } while (last < top); } //*********************** DOMINATORS ON THE SEA OF NODES*********************** //------------------------------NTarjan---------------------------------------- // A data structure that holds all the information needed to find dominators. struct NTarjan { Node *_control; // Control node associated with this info uint _semi; // Semi-dominators uint _size; // Used for faster LINK and EVAL NTarjan *_parent; // Parent in DFS NTarjan *_label; // Used for LINK and EVAL NTarjan *_ancestor; // Used for LINK and EVAL NTarjan *_child; // Used for faster LINK and EVAL NTarjan *_dom; // Parent in dominator tree (immediate dom) NTarjan *_bucket; // Set of vertices with given semidominator NTarjan *_dom_child; // Child in dominator tree NTarjan *_dom_next; // Next in dominator tree // Perform DFS search. // Setup 'vertex' as DFS to vertex mapping. // Setup 'semi' as vertex to DFS mapping. // Set 'parent' to DFS parent. static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder ); void setdepth( uint size, uint *dom_depth ); // Fast union-find work void COMPRESS(); NTarjan *EVAL(void); void LINK( NTarjan *w, NTarjan *ntarjan0 ); #ifndef PRODUCT void dump(int offset) const; #endif }; //------------------------------Dominator-------------------------------------- // Compute the dominator tree of the sea of nodes. This version walks all CFG // nodes (using the is_CFG() call) and places them in a dominator tree. Thus, // it needs a count of the CFG nodes for the mapping table. This is the // Lengauer & Tarjan O(E-alpha(E,V)) algorithm. void PhaseIdealLoop::Dominators() { ResourceMark rm; // Setup mappings from my Graph to Tarjan's stuff and back // Note: Tarjan uses 1-based arrays NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1); // Initialize _control field for fast reference int i; for( i= C->unique()-1; i>=0; i-- ) ntarjan[i]._control = NULL; // Store the DFS order for the main loop uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1); memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint)); // Tarjan's algorithm, almost verbatim: // Step 1: VectorSet visited(Thread::current()->resource_area()); int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder); // Tarjan is using 1-based arrays, so these are some initialize flags ntarjan[0]._size = ntarjan[0]._semi = 0; ntarjan[0]._label = &ntarjan[0]; for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order NTarjan *w = &ntarjan[i]; // Get Node from DFS assert(w->_control != NULL,"bad DFS walk"); // Step 2: Node *whead = w->_control; for( uint j=0; j < whead->req(); j++ ) { // For each predecessor if( whead->in(j) == NULL || !whead->in(j)->is_CFG() ) continue; // Only process control nodes uint b = dfsorder[whead->in(j)->_idx]; if(b == max_uint) continue; NTarjan *vx = &ntarjan[b]; NTarjan *u = vx->EVAL(); if( u->_semi < w->_semi ) w->_semi = u->_semi; } // w is added to a bucket here, and only here. // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). // Thus bucket can be a linked list. w->_bucket = ntarjan[w->_semi]._bucket; ntarjan[w->_semi]._bucket = w; w->_parent->LINK( w, &ntarjan[0] ); // Step 3: for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { NTarjan *u = vx->EVAL(); vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; } // Cleanup any unreachable loops now. Unreachable loops are loops that // flow into the main graph (and hence into ROOT) but are not reachable // from above. Such code is dead, but requires a global pass to detect // it; this global pass was the 'build_loop_tree' pass run just prior. if( !_verify_only && whead->is_Region() ) { for( uint i = 1; i < whead->req(); i++ ) { if (!has_node(whead->in(i))) { // Kill dead input path assert( !visited.test(whead->in(i)->_idx), "input with no loop must be dead" ); _igvn.hash_delete(whead); whead->del_req(i); _igvn._worklist.push(whead); for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) { Node* p = whead->fast_out(j); if( p->is_Phi() ) { _igvn.hash_delete(p); p->del_req(i); _igvn._worklist.push(p); } } i--; // Rerun same iteration } // End of if dead input path } // End of for all input paths } // End if if whead is a Region } // End of for all Nodes in reverse DFS order // Step 4: for( i=2; i < dfsnum; i++ ) { // DFS order NTarjan *w = &ntarjan[i]; assert(w->_control != NULL,"Bad DFS walk"); if( w->_dom != &ntarjan[w->_semi] ) w->_dom = w->_dom->_dom; w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later } // No immediate dominator for the root NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]]; w->_dom = NULL; w->_parent = NULL; w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later // Convert the dominator tree array into my kind of graph for( i=1; i<dfsnum; i++ ) { // For all Tarjan vertices NTarjan *t = &ntarjan[i]; // Handy access assert(t->_control != NULL,"Bad DFS walk"); NTarjan *tdom = t->_dom; // Handy access to immediate dominator if( tdom ) { // Root has no immediate dominator _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child tdom->_dom_child = t; // Make me a child of my parent } else _idom[C->root()->_idx] = NULL; // Root } w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree // Pick up the 'top' node as well _idom [C->top()->_idx] = C->root(); _dom_depth[C->top()->_idx] = 1; // Debug Print of Dominator tree if( PrintDominators ) { #ifndef PRODUCT w->dump(0); #endif } } //------------------------------DFS-------------------------------------------- // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) { // Allocate stack of size C->unique()/8 to avoid frequent realloc GrowableArray <Node *> dfstack(pil->C->unique() >> 3); Node *b = pil->C->root(); int dfsnum = 1; dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use dfstack.push(b); while (dfstack.is_nonempty()) { b = dfstack.pop(); if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited NTarjan *w = &ntarjan[dfsnum]; // Only fully process control nodes w->_control = b; // Save actual node // Use parent's cached dfsnum to identify "Parent in DFS" w->_parent = &ntarjan[dfsorder[b->_idx]]; dfsorder[b->_idx] = dfsnum; // Save DFS order info w->_semi = dfsnum; // Node to DFS map w->_label = w; // DFS to vertex map w->_ancestor = NULL; // Fast LINK & EVAL setup w->_child = &ntarjan[0]; // Sentinal w->_size = 1; w->_bucket = NULL; // Need DEF-USE info for this pass for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards Node* s = b->raw_out(i); // Get a use // CFG nodes only and not dead stuff if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) { dfsorder[s->_idx] = dfsnum; // Cache parent's dfsnum for a later use dfstack.push(s); } } dfsnum++; // update after parent's dfsnum has been cached. } } return dfsnum; } //------------------------------COMPRESS--------------------------------------- void NTarjan::COMPRESS() { assert( _ancestor != 0, "" ); if( _ancestor->_ancestor != 0 ) { _ancestor->COMPRESS( ); if( _ancestor->_label->_semi < _label->_semi ) _label = _ancestor->_label; _ancestor = _ancestor->_ancestor; } } //------------------------------EVAL------------------------------------------- NTarjan *NTarjan::EVAL() { if( !_ancestor ) return _label; COMPRESS(); return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label; } //------------------------------LINK------------------------------------------- void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) { NTarjan *s = w; while( w->_label->_semi < s->_child->_label->_semi ) { if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) { s->_child->_ancestor = s; s->_child = s->_child->_child; } else { s->_child->_size = s->_size; s = s->_ancestor = s->_child; } } s->_label = w->_label; _size += w->_size; if( _size < (w->_size << 1) ) { NTarjan *tmp = s; s = _child; _child = tmp; } while( s != ntarjan0 ) { s->_ancestor = this; s = s->_child; } } //------------------------------setdepth--------------------------------------- void NTarjan::setdepth( uint stack_size, uint *dom_depth ) { NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size); NTarjan **next = top; NTarjan **last; uint depth = 0; *top = this; ++top; do { // next level ++depth; last = top; do { // Set current depth for all tarjans on this level NTarjan *t = *next; // next tarjan from stack ++next; do { dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree NTarjan *dom_child = t->_dom_child; t = t->_dom_next; // next tarjan if (dom_child != NULL) { *top = dom_child; // save child on stack ++top; } } while (t != NULL); } while (next < last); } while (last < top); } //------------------------------dump------------------------------------------- #ifndef PRODUCT void NTarjan::dump(int offset) const { // Dump the data from this node int i; for(i = offset; i >0; i--) // Use indenting for tree structure tty->print(" "); tty->print("Dominator Node: "); _control->dump(); // Control node for this dom node tty->print("\n"); for(i = offset; i >0; i--) // Use indenting for tree structure tty->print(" "); tty->print("semi:%d, size:%d\n",_semi, _size); for(i = offset; i >0; i--) // Use indenting for tree structure tty->print(" "); tty->print("DFS Parent: "); if(_parent != NULL) _parent->_control->dump(); // Parent in DFS tty->print("\n"); for(i = offset; i >0; i--) // Use indenting for tree structure tty->print(" "); tty->print("Dom Parent: "); if(_dom != NULL) _dom->_control->dump(); // Parent in Dominator Tree tty->print("\n"); // Recurse over remaining tree if( _dom_child ) _dom_child->dump(offset+2); // Children in dominator tree if( _dom_next ) _dom_next ->dump(offset ); // Siblings in dominator tree } #endif