Mercurial > hg > graal-compiler
view src/share/vm/opto/domgraph.cpp @ 5839:58a607307306
renaming in native code for CiTargetMethod -> CompilationResult
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Mon, 16 Jul 2012 15:18:38 +0200 |
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