Mercurial > hg > truffle
annotate src/share/vm/opto/block.cpp @ 1721:413ad0331a0c
6977924: Changes for 6975078 produce build error with certain gcc versions
Summary: The changes introduced for 6975078 assign badHeapOopVal to the _allocation field in the ResourceObj class. In 32 bit linux builds with certain versions of gcc this assignment will be flagged as an error while compiling allocation.cpp. In 32 bit builds the constant value badHeapOopVal (which is cast to an intptr_t) is negative. The _allocation field is typed as an unsigned intptr_t and gcc catches this as an error.
Reviewed-by: jcoomes, ysr, phh
| author | johnc |
|---|---|
| date | Wed, 18 Aug 2010 10:59:06 -0700 |
| parents | 0e35fa8ebccd |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
893
diff
changeset
|
2 * Copyright (c) 1997, 2009, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
893
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
893
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
893
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 25 // Optimization - Graph Style | |
| 26 | |
| 27 #include "incls/_precompiled.incl" | |
| 28 #include "incls/_block.cpp.incl" | |
| 29 | |
| 30 | |
| 31 //----------------------------------------------------------------------------- | |
| 32 void Block_Array::grow( uint i ) { | |
| 33 assert(i >= Max(), "must be an overflow"); | |
| 34 debug_only(_limit = i+1); | |
| 35 if( i < _size ) return; | |
| 36 if( !_size ) { | |
| 37 _size = 1; | |
| 38 _blocks = (Block**)_arena->Amalloc( _size * sizeof(Block*) ); | |
| 39 _blocks[0] = NULL; | |
| 40 } | |
| 41 uint old = _size; | |
| 42 while( i >= _size ) _size <<= 1; // Double to fit | |
| 43 _blocks = (Block**)_arena->Arealloc( _blocks, old*sizeof(Block*),_size*sizeof(Block*)); | |
| 44 Copy::zero_to_bytes( &_blocks[old], (_size-old)*sizeof(Block*) ); | |
| 45 } | |
| 46 | |
| 47 //============================================================================= | |
| 48 void Block_List::remove(uint i) { | |
| 49 assert(i < _cnt, "index out of bounds"); | |
| 50 Copy::conjoint_words_to_lower((HeapWord*)&_blocks[i+1], (HeapWord*)&_blocks[i], ((_cnt-i-1)*sizeof(Block*))); | |
| 51 pop(); // shrink list by one block | |
| 52 } | |
| 53 | |
| 54 void Block_List::insert(uint i, Block *b) { | |
| 55 push(b); // grow list by one block | |
| 56 Copy::conjoint_words_to_higher((HeapWord*)&_blocks[i], (HeapWord*)&_blocks[i+1], ((_cnt-i-1)*sizeof(Block*))); | |
| 57 _blocks[i] = b; | |
| 58 } | |
| 59 | |
| 418 | 60 #ifndef PRODUCT |
| 61 void Block_List::print() { | |
| 62 for (uint i=0; i < size(); i++) { | |
| 63 tty->print("B%d ", _blocks[i]->_pre_order); | |
| 64 } | |
| 65 tty->print("size = %d\n", size()); | |
| 66 } | |
| 67 #endif | |
| 0 | 68 |
| 69 //============================================================================= | |
| 70 | |
| 71 uint Block::code_alignment() { | |
| 72 // Check for Root block | |
| 73 if( _pre_order == 0 ) return CodeEntryAlignment; | |
| 74 // Check for Start block | |
| 75 if( _pre_order == 1 ) return InteriorEntryAlignment; | |
| 76 // Check for loop alignment | |
| 418 | 77 if (has_loop_alignment()) return loop_alignment(); |
| 78 | |
| 79 return 1; // no particular alignment | |
| 80 } | |
| 81 | |
| 82 uint Block::compute_loop_alignment() { | |
| 0 | 83 Node *h = head(); |
| 84 if( h->is_Loop() && h->as_Loop()->is_inner_loop() ) { | |
| 85 // Pre- and post-loops have low trip count so do not bother with | |
| 86 // NOPs for align loop head. The constants are hidden from tuning | |
| 87 // but only because my "divide by 4" heuristic surely gets nearly | |
| 88 // all possible gain (a "do not align at all" heuristic has a | |
| 89 // chance of getting a really tiny gain). | |
| 90 if( h->is_CountedLoop() && (h->as_CountedLoop()->is_pre_loop() || | |
| 91 h->as_CountedLoop()->is_post_loop()) ) | |
| 92 return (OptoLoopAlignment > 4) ? (OptoLoopAlignment>>2) : 1; | |
| 93 // Loops with low backedge frequency should not be aligned. | |
| 94 Node *n = h->in(LoopNode::LoopBackControl)->in(0); | |
| 95 if( n->is_MachIf() && n->as_MachIf()->_prob < 0.01 ) { | |
| 96 return 1; // Loop does not loop, more often than not! | |
| 97 } | |
| 98 return OptoLoopAlignment; // Otherwise align loop head | |
| 99 } | |
| 418 | 100 |
| 0 | 101 return 1; // no particular alignment |
| 102 } | |
| 103 | |
| 104 //----------------------------------------------------------------------------- | |
| 105 // Compute the size of first 'inst_cnt' instructions in this block. | |
| 106 // Return the number of instructions left to compute if the block has | |
| 418 | 107 // less then 'inst_cnt' instructions. Stop, and return 0 if sum_size |
| 108 // exceeds OptoLoopAlignment. | |
| 0 | 109 uint Block::compute_first_inst_size(uint& sum_size, uint inst_cnt, |
| 110 PhaseRegAlloc* ra) { | |
| 111 uint last_inst = _nodes.size(); | |
| 112 for( uint j = 0; j < last_inst && inst_cnt > 0; j++ ) { | |
| 113 uint inst_size = _nodes[j]->size(ra); | |
| 114 if( inst_size > 0 ) { | |
| 115 inst_cnt--; | |
| 116 uint sz = sum_size + inst_size; | |
| 117 if( sz <= (uint)OptoLoopAlignment ) { | |
| 118 // Compute size of instructions which fit into fetch buffer only | |
| 119 // since all inst_cnt instructions will not fit even if we align them. | |
| 120 sum_size = sz; | |
| 121 } else { | |
| 122 return 0; | |
| 123 } | |
| 124 } | |
| 125 } | |
| 126 return inst_cnt; | |
| 127 } | |
| 128 | |
| 129 //----------------------------------------------------------------------------- | |
| 130 uint Block::find_node( const Node *n ) const { | |
| 131 for( uint i = 0; i < _nodes.size(); i++ ) { | |
| 132 if( _nodes[i] == n ) | |
| 133 return i; | |
| 134 } | |
| 135 ShouldNotReachHere(); | |
| 136 return 0; | |
| 137 } | |
| 138 | |
| 139 // Find and remove n from block list | |
| 140 void Block::find_remove( const Node *n ) { | |
| 141 _nodes.remove(find_node(n)); | |
| 142 } | |
| 143 | |
| 144 //------------------------------is_Empty--------------------------------------- | |
| 145 // Return empty status of a block. Empty blocks contain only the head, other | |
| 146 // ideal nodes, and an optional trailing goto. | |
| 147 int Block::is_Empty() const { | |
| 148 | |
| 149 // Root or start block is not considered empty | |
| 150 if (head()->is_Root() || head()->is_Start()) { | |
| 151 return not_empty; | |
| 152 } | |
| 153 | |
| 154 int success_result = completely_empty; | |
| 155 int end_idx = _nodes.size()-1; | |
| 156 | |
| 157 // Check for ending goto | |
| 158 if ((end_idx > 0) && (_nodes[end_idx]->is_Goto())) { | |
| 159 success_result = empty_with_goto; | |
| 160 end_idx--; | |
| 161 } | |
| 162 | |
| 163 // Unreachable blocks are considered empty | |
| 164 if (num_preds() <= 1) { | |
| 165 return success_result; | |
| 166 } | |
| 167 | |
| 168 // Ideal nodes are allowable in empty blocks: skip them Only MachNodes | |
| 169 // turn directly into code, because only MachNodes have non-trivial | |
| 170 // emit() functions. | |
| 171 while ((end_idx > 0) && !_nodes[end_idx]->is_Mach()) { | |
| 172 end_idx--; | |
| 173 } | |
| 174 | |
| 175 // No room for any interesting instructions? | |
| 176 if (end_idx == 0) { | |
| 177 return success_result; | |
| 178 } | |
| 179 | |
| 180 return not_empty; | |
| 181 } | |
| 182 | |
| 183 //------------------------------has_uncommon_code------------------------------ | |
| 605 | 184 // Return true if the block's code implies that it is likely to be |
| 0 | 185 // executed infrequently. Check to see if the block ends in a Halt or |
| 186 // a low probability call. | |
| 187 bool Block::has_uncommon_code() const { | |
| 188 Node* en = end(); | |
| 189 | |
| 190 if (en->is_Goto()) | |
| 191 en = en->in(0); | |
| 192 if (en->is_Catch()) | |
| 193 en = en->in(0); | |
| 194 if (en->is_Proj() && en->in(0)->is_MachCall()) { | |
| 195 MachCallNode* call = en->in(0)->as_MachCall(); | |
| 196 if (call->cnt() != COUNT_UNKNOWN && call->cnt() <= PROB_UNLIKELY_MAG(4)) { | |
| 197 // This is true for slow-path stubs like new_{instance,array}, | |
| 198 // slow_arraycopy, complete_monitor_locking, uncommon_trap. | |
| 199 // The magic number corresponds to the probability of an uncommon_trap, | |
| 200 // even though it is a count not a probability. | |
| 201 return true; | |
| 202 } | |
| 203 } | |
| 204 | |
| 205 int op = en->is_Mach() ? en->as_Mach()->ideal_Opcode() : en->Opcode(); | |
| 206 return op == Op_Halt; | |
| 207 } | |
| 208 | |
| 209 //------------------------------is_uncommon------------------------------------ | |
| 210 // True if block is low enough frequency or guarded by a test which | |
| 211 // mostly does not go here. | |
| 212 bool Block::is_uncommon( Block_Array &bbs ) const { | |
| 213 // Initial blocks must never be moved, so are never uncommon. | |
| 214 if (head()->is_Root() || head()->is_Start()) return false; | |
| 215 | |
| 216 // Check for way-low freq | |
| 217 if( _freq < BLOCK_FREQUENCY(0.00001f) ) return true; | |
| 218 | |
| 219 // Look for code shape indicating uncommon_trap or slow path | |
| 220 if (has_uncommon_code()) return true; | |
| 221 | |
| 222 const float epsilon = 0.05f; | |
| 223 const float guard_factor = PROB_UNLIKELY_MAG(4) / (1.f - epsilon); | |
| 224 uint uncommon_preds = 0; | |
| 225 uint freq_preds = 0; | |
| 226 uint uncommon_for_freq_preds = 0; | |
| 227 | |
| 228 for( uint i=1; i<num_preds(); i++ ) { | |
| 229 Block* guard = bbs[pred(i)->_idx]; | |
| 230 // Check to see if this block follows its guard 1 time out of 10000 | |
| 231 // or less. | |
| 232 // | |
| 233 // See list of magnitude-4 unlikely probabilities in cfgnode.hpp which | |
| 234 // we intend to be "uncommon", such as slow-path TLE allocation, | |
| 235 // predicted call failure, and uncommon trap triggers. | |
| 236 // | |
| 237 // Use an epsilon value of 5% to allow for variability in frequency | |
| 238 // predictions and floating point calculations. The net effect is | |
| 239 // that guard_factor is set to 9500. | |
| 240 // | |
| 241 // Ignore low-frequency blocks. | |
| 242 // The next check is (guard->_freq < 1.e-5 * 9500.). | |
| 243 if(guard->_freq*BLOCK_FREQUENCY(guard_factor) < BLOCK_FREQUENCY(0.00001f)) { | |
| 244 uncommon_preds++; | |
| 245 } else { | |
| 246 freq_preds++; | |
| 247 if( _freq < guard->_freq * guard_factor ) { | |
| 248 uncommon_for_freq_preds++; | |
| 249 } | |
| 250 } | |
| 251 } | |
| 252 if( num_preds() > 1 && | |
| 253 // The block is uncommon if all preds are uncommon or | |
| 254 (uncommon_preds == (num_preds()-1) || | |
| 255 // it is uncommon for all frequent preds. | |
| 256 uncommon_for_freq_preds == freq_preds) ) { | |
| 257 return true; | |
| 258 } | |
| 259 return false; | |
| 260 } | |
| 261 | |
| 262 //------------------------------dump------------------------------------------- | |
| 263 #ifndef PRODUCT | |
| 264 void Block::dump_bidx(const Block* orig) const { | |
| 265 if (_pre_order) tty->print("B%d",_pre_order); | |
| 266 else tty->print("N%d", head()->_idx); | |
| 267 | |
| 268 if (Verbose && orig != this) { | |
| 269 // Dump the original block's idx | |
| 270 tty->print(" ("); | |
| 271 orig->dump_bidx(orig); | |
| 272 tty->print(")"); | |
| 273 } | |
| 274 } | |
| 275 | |
| 276 void Block::dump_pred(const Block_Array *bbs, Block* orig) const { | |
| 277 if (is_connector()) { | |
| 278 for (uint i=1; i<num_preds(); i++) { | |
| 279 Block *p = ((*bbs)[pred(i)->_idx]); | |
| 280 p->dump_pred(bbs, orig); | |
| 281 } | |
| 282 } else { | |
| 283 dump_bidx(orig); | |
| 284 tty->print(" "); | |
| 285 } | |
| 286 } | |
| 287 | |
| 288 void Block::dump_head( const Block_Array *bbs ) const { | |
| 289 // Print the basic block | |
| 290 dump_bidx(this); | |
| 291 tty->print(": #\t"); | |
| 292 | |
| 293 // Print the incoming CFG edges and the outgoing CFG edges | |
| 294 for( uint i=0; i<_num_succs; i++ ) { | |
| 295 non_connector_successor(i)->dump_bidx(_succs[i]); | |
| 296 tty->print(" "); | |
| 297 } | |
| 298 tty->print("<- "); | |
| 299 if( head()->is_block_start() ) { | |
| 300 for (uint i=1; i<num_preds(); i++) { | |
| 301 Node *s = pred(i); | |
| 302 if (bbs) { | |
| 303 Block *p = (*bbs)[s->_idx]; | |
| 304 p->dump_pred(bbs, p); | |
| 305 } else { | |
| 306 while (!s->is_block_start()) | |
| 307 s = s->in(0); | |
| 308 tty->print("N%d ", s->_idx ); | |
| 309 } | |
| 310 } | |
| 311 } else | |
| 312 tty->print("BLOCK HEAD IS JUNK "); | |
| 313 | |
| 314 // Print loop, if any | |
| 315 const Block *bhead = this; // Head of self-loop | |
| 316 Node *bh = bhead->head(); | |
| 317 if( bbs && bh->is_Loop() && !head()->is_Root() ) { | |
| 318 LoopNode *loop = bh->as_Loop(); | |
| 319 const Block *bx = (*bbs)[loop->in(LoopNode::LoopBackControl)->_idx]; | |
| 320 while (bx->is_connector()) { | |
| 321 bx = (*bbs)[bx->pred(1)->_idx]; | |
| 322 } | |
| 323 tty->print("\tLoop: B%d-B%d ", bhead->_pre_order, bx->_pre_order); | |
| 324 // Dump any loop-specific bits, especially for CountedLoops. | |
| 325 loop->dump_spec(tty); | |
| 418 | 326 } else if (has_loop_alignment()) { |
| 327 tty->print(" top-of-loop"); | |
| 0 | 328 } |
| 329 tty->print(" Freq: %g",_freq); | |
| 330 if( Verbose || WizardMode ) { | |
| 331 tty->print(" IDom: %d/#%d", _idom ? _idom->_pre_order : 0, _dom_depth); | |
| 332 tty->print(" RegPressure: %d",_reg_pressure); | |
| 333 tty->print(" IHRP Index: %d",_ihrp_index); | |
| 334 tty->print(" FRegPressure: %d",_freg_pressure); | |
| 335 tty->print(" FHRP Index: %d",_fhrp_index); | |
| 336 } | |
| 337 tty->print_cr(""); | |
| 338 } | |
| 339 | |
| 340 void Block::dump() const { dump(0); } | |
| 341 | |
| 342 void Block::dump( const Block_Array *bbs ) const { | |
| 343 dump_head(bbs); | |
| 344 uint cnt = _nodes.size(); | |
| 345 for( uint i=0; i<cnt; i++ ) | |
| 346 _nodes[i]->dump(); | |
| 347 tty->print("\n"); | |
| 348 } | |
| 349 #endif | |
| 350 | |
| 351 //============================================================================= | |
| 352 //------------------------------PhaseCFG--------------------------------------- | |
| 353 PhaseCFG::PhaseCFG( Arena *a, RootNode *r, Matcher &m ) : | |
| 354 Phase(CFG), | |
| 355 _bbs(a), | |
| 1685 | 356 _root(r), |
| 357 _node_latency(NULL) | |
| 0 | 358 #ifndef PRODUCT |
| 359 , _trace_opto_pipelining(TraceOptoPipelining || C->method_has_option("TraceOptoPipelining")) | |
| 360 #endif | |
|
833
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
628
diff
changeset
|
361 #ifdef ASSERT |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
628
diff
changeset
|
362 , _raw_oops(a) |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
628
diff
changeset
|
363 #endif |
| 0 | 364 { |
| 365 ResourceMark rm; | |
| 366 // I'll need a few machine-specific GotoNodes. Make an Ideal GotoNode, | |
| 367 // then Match it into a machine-specific Node. Then clone the machine | |
| 368 // Node on demand. | |
| 369 Node *x = new (C, 1) GotoNode(NULL); | |
| 370 x->init_req(0, x); | |
| 371 _goto = m.match_tree(x); | |
| 372 assert(_goto != NULL, ""); | |
| 373 _goto->set_req(0,_goto); | |
| 374 | |
| 375 // Build the CFG in Reverse Post Order | |
| 376 _num_blocks = build_cfg(); | |
| 377 _broot = _bbs[_root->_idx]; | |
| 378 } | |
| 379 | |
| 380 //------------------------------build_cfg-------------------------------------- | |
| 381 // Build a proper looking CFG. Make every block begin with either a StartNode | |
| 382 // or a RegionNode. Make every block end with either a Goto, If or Return. | |
| 383 // The RootNode both starts and ends it's own block. Do this with a recursive | |
| 384 // backwards walk over the control edges. | |
| 385 uint PhaseCFG::build_cfg() { | |
| 386 Arena *a = Thread::current()->resource_area(); | |
| 387 VectorSet visited(a); | |
| 388 | |
| 389 // Allocate stack with enough space to avoid frequent realloc | |
| 390 Node_Stack nstack(a, C->unique() >> 1); | |
| 391 nstack.push(_root, 0); | |
| 392 uint sum = 0; // Counter for blocks | |
| 393 | |
| 394 while (nstack.is_nonempty()) { | |
| 395 // node and in's index from stack's top | |
| 396 // 'np' is _root (see above) or RegionNode, StartNode: we push on stack | |
| 397 // only nodes which point to the start of basic block (see below). | |
| 398 Node *np = nstack.node(); | |
| 399 // idx > 0, except for the first node (_root) pushed on stack | |
| 400 // at the beginning when idx == 0. | |
| 401 // We will use the condition (idx == 0) later to end the build. | |
| 402 uint idx = nstack.index(); | |
| 403 Node *proj = np->in(idx); | |
| 404 const Node *x = proj->is_block_proj(); | |
| 405 // Does the block end with a proper block-ending Node? One of Return, | |
| 406 // If or Goto? (This check should be done for visited nodes also). | |
| 407 if (x == NULL) { // Does not end right... | |
| 408 Node *g = _goto->clone(); // Force it to end in a Goto | |
| 409 g->set_req(0, proj); | |
| 410 np->set_req(idx, g); | |
| 411 x = proj = g; | |
| 412 } | |
| 413 if (!visited.test_set(x->_idx)) { // Visit this block once | |
| 414 // Skip any control-pinned middle'in stuff | |
| 415 Node *p = proj; | |
| 416 do { | |
| 417 proj = p; // Update pointer to last Control | |
| 418 p = p->in(0); // Move control forward | |
| 419 } while( !p->is_block_proj() && | |
| 420 !p->is_block_start() ); | |
| 421 // Make the block begin with one of Region or StartNode. | |
| 422 if( !p->is_block_start() ) { | |
| 423 RegionNode *r = new (C, 2) RegionNode( 2 ); | |
| 424 r->init_req(1, p); // Insert RegionNode in the way | |
| 425 proj->set_req(0, r); // Insert RegionNode in the way | |
| 426 p = r; | |
| 427 } | |
| 428 // 'p' now points to the start of this basic block | |
| 429 | |
| 430 // Put self in array of basic blocks | |
| 431 Block *bb = new (_bbs._arena) Block(_bbs._arena,p); | |
| 432 _bbs.map(p->_idx,bb); | |
| 433 _bbs.map(x->_idx,bb); | |
| 434 if( x != p ) // Only for root is x == p | |
| 435 bb->_nodes.push((Node*)x); | |
| 436 | |
| 437 // Now handle predecessors | |
| 438 ++sum; // Count 1 for self block | |
| 439 uint cnt = bb->num_preds(); | |
| 440 for (int i = (cnt - 1); i > 0; i-- ) { // For all predecessors | |
| 441 Node *prevproj = p->in(i); // Get prior input | |
| 442 assert( !prevproj->is_Con(), "dead input not removed" ); | |
| 443 // Check to see if p->in(i) is a "control-dependent" CFG edge - | |
| 444 // i.e., it splits at the source (via an IF or SWITCH) and merges | |
| 445 // at the destination (via a many-input Region). | |
| 446 // This breaks critical edges. The RegionNode to start the block | |
| 447 // will be added when <p,i> is pulled off the node stack | |
| 448 if ( cnt > 2 ) { // Merging many things? | |
| 449 assert( prevproj== bb->pred(i),""); | |
| 450 if(prevproj->is_block_proj() != prevproj) { // Control-dependent edge? | |
| 451 // Force a block on the control-dependent edge | |
| 452 Node *g = _goto->clone(); // Force it to end in a Goto | |
| 453 g->set_req(0,prevproj); | |
| 454 p->set_req(i,g); | |
| 455 } | |
| 456 } | |
| 457 nstack.push(p, i); // 'p' is RegionNode or StartNode | |
| 458 } | |
| 459 } else { // Post-processing visited nodes | |
| 460 nstack.pop(); // remove node from stack | |
| 461 // Check if it the fist node pushed on stack at the beginning. | |
| 462 if (idx == 0) break; // end of the build | |
| 463 // Find predecessor basic block | |
| 464 Block *pb = _bbs[x->_idx]; | |
| 465 // Insert into nodes array, if not already there | |
| 466 if( !_bbs.lookup(proj->_idx) ) { | |
| 467 assert( x != proj, "" ); | |
| 468 // Map basic block of projection | |
| 469 _bbs.map(proj->_idx,pb); | |
| 470 pb->_nodes.push(proj); | |
| 471 } | |
| 472 // Insert self as a child of my predecessor block | |
| 473 pb->_succs.map(pb->_num_succs++, _bbs[np->_idx]); | |
| 474 assert( pb->_nodes[ pb->_nodes.size() - pb->_num_succs ]->is_block_proj(), | |
| 475 "too many control users, not a CFG?" ); | |
| 476 } | |
| 477 } | |
| 478 // Return number of basic blocks for all children and self | |
| 479 return sum; | |
| 480 } | |
| 481 | |
| 482 //------------------------------insert_goto_at--------------------------------- | |
| 483 // Inserts a goto & corresponding basic block between | |
| 484 // block[block_no] and its succ_no'th successor block | |
| 485 void PhaseCFG::insert_goto_at(uint block_no, uint succ_no) { | |
| 486 // get block with block_no | |
| 487 assert(block_no < _num_blocks, "illegal block number"); | |
| 488 Block* in = _blocks[block_no]; | |
| 489 // get successor block succ_no | |
| 490 assert(succ_no < in->_num_succs, "illegal successor number"); | |
| 491 Block* out = in->_succs[succ_no]; | |
| 308 | 492 // Compute frequency of the new block. Do this before inserting |
| 493 // new block in case succ_prob() needs to infer the probability from | |
| 494 // surrounding blocks. | |
| 495 float freq = in->_freq * in->succ_prob(succ_no); | |
| 0 | 496 // get ProjNode corresponding to the succ_no'th successor of the in block |
| 497 ProjNode* proj = in->_nodes[in->_nodes.size() - in->_num_succs + succ_no]->as_Proj(); | |
| 498 // create region for basic block | |
| 499 RegionNode* region = new (C, 2) RegionNode(2); | |
| 500 region->init_req(1, proj); | |
| 501 // setup corresponding basic block | |
| 502 Block* block = new (_bbs._arena) Block(_bbs._arena, region); | |
| 503 _bbs.map(region->_idx, block); | |
| 504 C->regalloc()->set_bad(region->_idx); | |
| 505 // add a goto node | |
| 506 Node* gto = _goto->clone(); // get a new goto node | |
| 507 gto->set_req(0, region); | |
| 508 // add it to the basic block | |
| 509 block->_nodes.push(gto); | |
| 510 _bbs.map(gto->_idx, block); | |
| 511 C->regalloc()->set_bad(gto->_idx); | |
| 512 // hook up successor block | |
| 513 block->_succs.map(block->_num_succs++, out); | |
| 514 // remap successor's predecessors if necessary | |
| 515 for (uint i = 1; i < out->num_preds(); i++) { | |
| 516 if (out->pred(i) == proj) out->head()->set_req(i, gto); | |
| 517 } | |
| 518 // remap predecessor's successor to new block | |
| 519 in->_succs.map(succ_no, block); | |
| 308 | 520 // Set the frequency of the new block |
| 521 block->_freq = freq; | |
| 0 | 522 // add new basic block to basic block list |
| 523 _blocks.insert(block_no + 1, block); | |
| 524 _num_blocks++; | |
| 525 } | |
| 526 | |
| 527 //------------------------------no_flip_branch--------------------------------- | |
| 528 // Does this block end in a multiway branch that cannot have the default case | |
| 529 // flipped for another case? | |
| 530 static bool no_flip_branch( Block *b ) { | |
| 531 int branch_idx = b->_nodes.size() - b->_num_succs-1; | |
| 532 if( branch_idx < 1 ) return false; | |
| 533 Node *bra = b->_nodes[branch_idx]; | |
| 418 | 534 if( bra->is_Catch() ) |
| 535 return true; | |
| 0 | 536 if( bra->is_Mach() ) { |
| 418 | 537 if( bra->is_MachNullCheck() ) |
| 538 return true; | |
| 0 | 539 int iop = bra->as_Mach()->ideal_Opcode(); |
| 540 if( iop == Op_FastLock || iop == Op_FastUnlock ) | |
| 541 return true; | |
| 542 } | |
| 543 return false; | |
| 544 } | |
| 545 | |
| 546 //------------------------------convert_NeverBranch_to_Goto-------------------- | |
| 547 // Check for NeverBranch at block end. This needs to become a GOTO to the | |
| 548 // true target. NeverBranch are treated as a conditional branch that always | |
| 549 // goes the same direction for most of the optimizer and are used to give a | |
| 550 // fake exit path to infinite loops. At this late stage they need to turn | |
| 551 // into Goto's so that when you enter the infinite loop you indeed hang. | |
| 552 void PhaseCFG::convert_NeverBranch_to_Goto(Block *b) { | |
| 553 // Find true target | |
| 554 int end_idx = b->end_idx(); | |
| 555 int idx = b->_nodes[end_idx+1]->as_Proj()->_con; | |
| 556 Block *succ = b->_succs[idx]; | |
| 557 Node* gto = _goto->clone(); // get a new goto node | |
| 558 gto->set_req(0, b->head()); | |
| 559 Node *bp = b->_nodes[end_idx]; | |
| 560 b->_nodes.map(end_idx,gto); // Slam over NeverBranch | |
| 561 _bbs.map(gto->_idx, b); | |
| 562 C->regalloc()->set_bad(gto->_idx); | |
| 563 b->_nodes.pop(); // Yank projections | |
| 564 b->_nodes.pop(); // Yank projections | |
| 565 b->_succs.map(0,succ); // Map only successor | |
| 566 b->_num_succs = 1; | |
| 567 // remap successor's predecessors if necessary | |
| 568 uint j; | |
| 569 for( j = 1; j < succ->num_preds(); j++) | |
| 570 if( succ->pred(j)->in(0) == bp ) | |
| 571 succ->head()->set_req(j, gto); | |
| 572 // Kill alternate exit path | |
| 573 Block *dead = b->_succs[1-idx]; | |
| 574 for( j = 1; j < dead->num_preds(); j++) | |
| 575 if( dead->pred(j)->in(0) == bp ) | |
| 576 break; | |
| 577 // Scan through block, yanking dead path from | |
| 578 // all regions and phis. | |
| 579 dead->head()->del_req(j); | |
| 580 for( int k = 1; dead->_nodes[k]->is_Phi(); k++ ) | |
| 581 dead->_nodes[k]->del_req(j); | |
| 582 } | |
| 583 | |
| 418 | 584 //------------------------------move_to_next----------------------------------- |
| 0 | 585 // Helper function to move block bx to the slot following b_index. Return |
| 586 // true if the move is successful, otherwise false | |
| 418 | 587 bool PhaseCFG::move_to_next(Block* bx, uint b_index) { |
| 0 | 588 if (bx == NULL) return false; |
| 589 | |
| 590 // Return false if bx is already scheduled. | |
| 591 uint bx_index = bx->_pre_order; | |
| 592 if ((bx_index <= b_index) && (_blocks[bx_index] == bx)) { | |
| 593 return false; | |
| 594 } | |
| 595 | |
| 596 // Find the current index of block bx on the block list | |
| 597 bx_index = b_index + 1; | |
| 598 while( bx_index < _num_blocks && _blocks[bx_index] != bx ) bx_index++; | |
| 599 assert(_blocks[bx_index] == bx, "block not found"); | |
| 600 | |
| 601 // If the previous block conditionally falls into bx, return false, | |
| 602 // because moving bx will create an extra jump. | |
| 603 for(uint k = 1; k < bx->num_preds(); k++ ) { | |
| 604 Block* pred = _bbs[bx->pred(k)->_idx]; | |
| 605 if (pred == _blocks[bx_index-1]) { | |
| 606 if (pred->_num_succs != 1) { | |
| 607 return false; | |
| 608 } | |
| 609 } | |
| 610 } | |
| 611 | |
| 612 // Reinsert bx just past block 'b' | |
| 613 _blocks.remove(bx_index); | |
| 614 _blocks.insert(b_index + 1, bx); | |
| 615 return true; | |
| 616 } | |
| 617 | |
| 418 | 618 //------------------------------move_to_end------------------------------------ |
| 0 | 619 // Move empty and uncommon blocks to the end. |
| 418 | 620 void PhaseCFG::move_to_end(Block *b, uint i) { |
| 0 | 621 int e = b->is_Empty(); |
| 622 if (e != Block::not_empty) { | |
| 623 if (e == Block::empty_with_goto) { | |
| 624 // Remove the goto, but leave the block. | |
| 625 b->_nodes.pop(); | |
| 626 } | |
| 627 // Mark this block as a connector block, which will cause it to be | |
| 628 // ignored in certain functions such as non_connector_successor(). | |
| 629 b->set_connector(); | |
| 630 } | |
| 631 // Move the empty block to the end, and don't recheck. | |
| 632 _blocks.remove(i); | |
| 633 _blocks.push(b); | |
| 634 } | |
| 635 | |
| 418 | 636 //---------------------------set_loop_alignment-------------------------------- |
| 637 // Set loop alignment for every block | |
| 638 void PhaseCFG::set_loop_alignment() { | |
| 639 uint last = _num_blocks; | |
| 640 assert( _blocks[0] == _broot, "" ); | |
| 641 | |
| 642 for (uint i = 1; i < last; i++ ) { | |
| 643 Block *b = _blocks[i]; | |
| 644 if (b->head()->is_Loop()) { | |
| 645 b->set_loop_alignment(b); | |
| 646 } | |
| 647 } | |
| 648 } | |
| 649 | |
| 650 //-----------------------------remove_empty------------------------------------ | |
| 651 // Make empty basic blocks to be "connector" blocks, Move uncommon blocks | |
| 652 // to the end. | |
| 653 void PhaseCFG::remove_empty() { | |
| 0 | 654 // Move uncommon blocks to the end |
| 655 uint last = _num_blocks; | |
| 656 assert( _blocks[0] == _broot, "" ); | |
| 418 | 657 |
| 658 for (uint i = 1; i < last; i++) { | |
| 0 | 659 Block *b = _blocks[i]; |
| 418 | 660 if (b->is_connector()) break; |
| 0 | 661 |
| 662 // Check for NeverBranch at block end. This needs to become a GOTO to the | |
| 663 // true target. NeverBranch are treated as a conditional branch that | |
| 664 // always goes the same direction for most of the optimizer and are used | |
| 665 // to give a fake exit path to infinite loops. At this late stage they | |
| 666 // need to turn into Goto's so that when you enter the infinite loop you | |
| 667 // indeed hang. | |
| 668 if( b->_nodes[b->end_idx()]->Opcode() == Op_NeverBranch ) | |
| 669 convert_NeverBranch_to_Goto(b); | |
| 670 | |
| 671 // Look for uncommon blocks and move to end. | |
| 418 | 672 if (!C->do_freq_based_layout()) { |
| 673 if( b->is_uncommon(_bbs) ) { | |
| 674 move_to_end(b, i); | |
| 675 last--; // No longer check for being uncommon! | |
| 676 if( no_flip_branch(b) ) { // Fall-thru case must follow? | |
| 677 b = _blocks[i]; // Find the fall-thru block | |
| 678 move_to_end(b, i); | |
| 679 last--; | |
| 680 } | |
| 681 i--; // backup block counter post-increment | |
| 0 | 682 } |
| 683 } | |
| 684 } | |
| 685 | |
| 418 | 686 // Move empty blocks to the end |
| 0 | 687 last = _num_blocks; |
| 418 | 688 for (uint i = 1; i < last; i++) { |
| 0 | 689 Block *b = _blocks[i]; |
| 418 | 690 if (b->is_Empty() != Block::not_empty) { |
| 691 move_to_end(b, i); | |
| 692 last--; | |
| 693 i--; | |
| 0 | 694 } |
| 695 } // End of for all blocks | |
| 418 | 696 } |
| 0 | 697 |
| 418 | 698 //-----------------------------fixup_flow-------------------------------------- |
| 699 // Fix up the final control flow for basic blocks. | |
| 700 void PhaseCFG::fixup_flow() { | |
| 0 | 701 // Fixup final control flow for the blocks. Remove jump-to-next |
| 702 // block. If neither arm of a IF follows the conditional branch, we | |
| 703 // have to add a second jump after the conditional. We place the | |
| 704 // TRUE branch target in succs[0] for both GOTOs and IFs. | |
| 418 | 705 for (uint i=0; i < _num_blocks; i++) { |
| 0 | 706 Block *b = _blocks[i]; |
| 707 b->_pre_order = i; // turn pre-order into block-index | |
| 708 | |
| 709 // Connector blocks need no further processing. | |
| 710 if (b->is_connector()) { | |
| 711 assert((i+1) == _num_blocks || _blocks[i+1]->is_connector(), | |
| 712 "All connector blocks should sink to the end"); | |
| 713 continue; | |
| 714 } | |
| 715 assert(b->is_Empty() != Block::completely_empty, | |
| 716 "Empty blocks should be connectors"); | |
| 717 | |
| 718 Block *bnext = (i < _num_blocks-1) ? _blocks[i+1] : NULL; | |
| 719 Block *bs0 = b->non_connector_successor(0); | |
| 720 | |
| 721 // Check for multi-way branches where I cannot negate the test to | |
| 722 // exchange the true and false targets. | |
| 723 if( no_flip_branch( b ) ) { | |
| 724 // Find fall through case - if must fall into its target | |
| 725 int branch_idx = b->_nodes.size() - b->_num_succs; | |
| 726 for (uint j2 = 0; j2 < b->_num_succs; j2++) { | |
| 727 const ProjNode* p = b->_nodes[branch_idx + j2]->as_Proj(); | |
| 728 if (p->_con == 0) { | |
| 729 // successor j2 is fall through case | |
| 730 if (b->non_connector_successor(j2) != bnext) { | |
| 731 // but it is not the next block => insert a goto | |
| 732 insert_goto_at(i, j2); | |
| 733 } | |
| 734 // Put taken branch in slot 0 | |
| 735 if( j2 == 0 && b->_num_succs == 2) { | |
| 736 // Flip targets in succs map | |
| 737 Block *tbs0 = b->_succs[0]; | |
| 738 Block *tbs1 = b->_succs[1]; | |
| 739 b->_succs.map( 0, tbs1 ); | |
| 740 b->_succs.map( 1, tbs0 ); | |
| 741 } | |
| 742 break; | |
| 743 } | |
| 744 } | |
| 745 // Remove all CatchProjs | |
| 418 | 746 for (uint j1 = 0; j1 < b->_num_succs; j1++) b->_nodes.pop(); |
| 0 | 747 |
| 748 } else if (b->_num_succs == 1) { | |
| 749 // Block ends in a Goto? | |
| 750 if (bnext == bs0) { | |
| 751 // We fall into next block; remove the Goto | |
| 752 b->_nodes.pop(); | |
| 753 } | |
| 754 | |
| 755 } else if( b->_num_succs == 2 ) { // Block ends in a If? | |
| 756 // Get opcode of 1st projection (matches _succs[0]) | |
| 757 // Note: Since this basic block has 2 exits, the last 2 nodes must | |
| 758 // be projections (in any order), the 3rd last node must be | |
| 759 // the IfNode (we have excluded other 2-way exits such as | |
| 760 // CatchNodes already). | |
| 761 MachNode *iff = b->_nodes[b->_nodes.size()-3]->as_Mach(); | |
| 762 ProjNode *proj0 = b->_nodes[b->_nodes.size()-2]->as_Proj(); | |
| 763 ProjNode *proj1 = b->_nodes[b->_nodes.size()-1]->as_Proj(); | |
| 764 | |
| 765 // Assert that proj0 and succs[0] match up. Similarly for proj1 and succs[1]. | |
| 766 assert(proj0->raw_out(0) == b->_succs[0]->head(), "Mismatch successor 0"); | |
| 767 assert(proj1->raw_out(0) == b->_succs[1]->head(), "Mismatch successor 1"); | |
| 768 | |
| 769 Block *bs1 = b->non_connector_successor(1); | |
| 770 | |
| 771 // Check for neither successor block following the current | |
| 772 // block ending in a conditional. If so, move one of the | |
| 773 // successors after the current one, provided that the | |
| 774 // successor was previously unscheduled, but moveable | |
| 775 // (i.e., all paths to it involve a branch). | |
| 418 | 776 if( !C->do_freq_based_layout() && bnext != bs0 && bnext != bs1 ) { |
| 0 | 777 // Choose the more common successor based on the probability |
| 778 // of the conditional branch. | |
| 779 Block *bx = bs0; | |
| 780 Block *by = bs1; | |
| 781 | |
| 782 // _prob is the probability of taking the true path. Make | |
| 783 // p the probability of taking successor #1. | |
| 784 float p = iff->as_MachIf()->_prob; | |
| 785 if( proj0->Opcode() == Op_IfTrue ) { | |
| 786 p = 1.0 - p; | |
| 787 } | |
| 788 | |
| 789 // Prefer successor #1 if p > 0.5 | |
| 790 if (p > PROB_FAIR) { | |
| 791 bx = bs1; | |
| 792 by = bs0; | |
| 793 } | |
| 794 | |
| 795 // Attempt the more common successor first | |
| 418 | 796 if (move_to_next(bx, i)) { |
| 0 | 797 bnext = bx; |
| 418 | 798 } else if (move_to_next(by, i)) { |
| 0 | 799 bnext = by; |
| 800 } | |
| 801 } | |
| 802 | |
| 803 // Check for conditional branching the wrong way. Negate | |
| 804 // conditional, if needed, so it falls into the following block | |
| 805 // and branches to the not-following block. | |
| 806 | |
| 807 // Check for the next block being in succs[0]. We are going to branch | |
| 808 // to succs[0], so we want the fall-thru case as the next block in | |
| 809 // succs[1]. | |
| 810 if (bnext == bs0) { | |
| 811 // Fall-thru case in succs[0], so flip targets in succs map | |
| 812 Block *tbs0 = b->_succs[0]; | |
| 813 Block *tbs1 = b->_succs[1]; | |
| 814 b->_succs.map( 0, tbs1 ); | |
| 815 b->_succs.map( 1, tbs0 ); | |
| 816 // Flip projection for each target | |
| 817 { ProjNode *tmp = proj0; proj0 = proj1; proj1 = tmp; } | |
| 818 | |
| 418 | 819 } else if( bnext != bs1 ) { |
| 820 // Need a double-branch | |
| 0 | 821 // The existing conditional branch need not change. |
| 822 // Add a unconditional branch to the false target. | |
| 823 // Alas, it must appear in its own block and adding a | |
| 824 // block this late in the game is complicated. Sigh. | |
| 825 insert_goto_at(i, 1); | |
| 826 } | |
| 827 | |
| 828 // Make sure we TRUE branch to the target | |
| 418 | 829 if( proj0->Opcode() == Op_IfFalse ) { |
| 0 | 830 iff->negate(); |
| 418 | 831 } |
| 0 | 832 |
| 833 b->_nodes.pop(); // Remove IfFalse & IfTrue projections | |
| 834 b->_nodes.pop(); | |
| 835 | |
| 836 } else { | |
| 837 // Multi-exit block, e.g. a switch statement | |
| 838 // But we don't need to do anything here | |
| 839 } | |
| 840 } // End of for all blocks | |
| 841 } | |
| 842 | |
| 843 | |
| 844 //------------------------------dump------------------------------------------- | |
| 845 #ifndef PRODUCT | |
| 846 void PhaseCFG::_dump_cfg( const Node *end, VectorSet &visited ) const { | |
| 847 const Node *x = end->is_block_proj(); | |
| 848 assert( x, "not a CFG" ); | |
| 849 | |
| 850 // Do not visit this block again | |
| 851 if( visited.test_set(x->_idx) ) return; | |
| 852 | |
| 853 // Skip through this block | |
| 854 const Node *p = x; | |
| 855 do { | |
| 856 p = p->in(0); // Move control forward | |
| 857 assert( !p->is_block_proj() || p->is_Root(), "not a CFG" ); | |
| 858 } while( !p->is_block_start() ); | |
| 859 | |
| 860 // Recursively visit | |
| 861 for( uint i=1; i<p->req(); i++ ) | |
| 862 _dump_cfg(p->in(i),visited); | |
| 863 | |
| 864 // Dump the block | |
| 865 _bbs[p->_idx]->dump(&_bbs); | |
| 866 } | |
| 867 | |
| 868 void PhaseCFG::dump( ) const { | |
| 869 tty->print("\n--- CFG --- %d BBs\n",_num_blocks); | |
| 870 if( _blocks.size() ) { // Did we do basic-block layout? | |
| 871 for( uint i=0; i<_num_blocks; i++ ) | |
| 872 _blocks[i]->dump(&_bbs); | |
| 873 } else { // Else do it with a DFS | |
| 874 VectorSet visited(_bbs._arena); | |
| 875 _dump_cfg(_root,visited); | |
| 876 } | |
| 877 } | |
| 878 | |
| 879 void PhaseCFG::dump_headers() { | |
| 880 for( uint i = 0; i < _num_blocks; i++ ) { | |
| 881 if( _blocks[i] == NULL ) continue; | |
| 882 _blocks[i]->dump_head(&_bbs); | |
| 883 } | |
| 884 } | |
| 885 | |
| 886 void PhaseCFG::verify( ) const { | |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
887 #ifdef ASSERT |
| 0 | 888 // Verify sane CFG |
| 889 for( uint i = 0; i < _num_blocks; i++ ) { | |
| 890 Block *b = _blocks[i]; | |
| 891 uint cnt = b->_nodes.size(); | |
| 892 uint j; | |
| 893 for( j = 0; j < cnt; j++ ) { | |
| 894 Node *n = b->_nodes[j]; | |
| 895 assert( _bbs[n->_idx] == b, "" ); | |
| 896 if( j >= 1 && n->is_Mach() && | |
| 897 n->as_Mach()->ideal_Opcode() == Op_CreateEx ) { | |
| 898 assert( j == 1 || b->_nodes[j-1]->is_Phi(), | |
| 899 "CreateEx must be first instruction in block" ); | |
| 900 } | |
| 901 for( uint k = 0; k < n->req(); k++ ) { | |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
902 Node *def = n->in(k); |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
903 if( def && def != n ) { |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
904 assert( _bbs[def->_idx] || def->is_Con(), |
| 0 | 905 "must have block; constants for debug info ok" ); |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
906 // Verify that instructions in the block is in correct order. |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
907 // Uses must follow their definition if they are at the same block. |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
908 // Mostly done to check that MachSpillCopy nodes are placed correctly |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
909 // when CreateEx node is moved in build_ifg_physical(). |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
910 if( _bbs[def->_idx] == b && |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
911 !(b->head()->is_Loop() && n->is_Phi()) && |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
912 // See (+++) comment in reg_split.cpp |
|
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
913 !(n->jvms() != NULL && n->jvms()->is_monitor_use(k)) ) { |
|
893
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
914 bool is_loop = false; |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
915 if (n->is_Phi()) { |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
916 for( uint l = 1; l < def->req(); l++ ) { |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
917 if (n == def->in(l)) { |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
918 is_loop = true; |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
919 break; // Some kind of loop |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
920 } |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
921 } |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
922 } |
|
dd0a4e1e219b
6851386: assert(b->find_node(def) < j,"uses must follow definitions")
kvn
parents:
833
diff
changeset
|
923 assert( is_loop || b->find_node(def) < j, "uses must follow definitions" ); |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
924 } |
|
601
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
566
diff
changeset
|
925 if( def->is_SafePointScalarObject() ) { |
|
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
566
diff
changeset
|
926 assert(_bbs[def->_idx] == b, "SafePointScalarObject Node should be at the same block as its SafePoint node"); |
|
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
566
diff
changeset
|
927 assert(_bbs[def->_idx] == _bbs[def->in(0)->_idx], "SafePointScalarObject Node should be at the same block as its control edge"); |
|
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
566
diff
changeset
|
928 } |
| 0 | 929 } |
| 930 } | |
| 931 } | |
| 932 | |
| 933 j = b->end_idx(); | |
| 934 Node *bp = (Node*)b->_nodes[b->_nodes.size()-1]->is_block_proj(); | |
| 935 assert( bp, "last instruction must be a block proj" ); | |
| 936 assert( bp == b->_nodes[j], "wrong number of successors for this block" ); | |
| 937 if( bp->is_Catch() ) { | |
| 938 while( b->_nodes[--j]->Opcode() == Op_MachProj ) ; | |
| 939 assert( b->_nodes[j]->is_Call(), "CatchProj must follow call" ); | |
| 940 } | |
| 941 else if( bp->is_Mach() && bp->as_Mach()->ideal_Opcode() == Op_If ) { | |
| 942 assert( b->_num_succs == 2, "Conditional branch must have two targets"); | |
| 943 } | |
| 944 } | |
|
566
91263420e1c6
6791852: assert(b->_nodes[insidx] == n,"got insidx set incorrectly")
kvn
parents:
418
diff
changeset
|
945 #endif |
| 0 | 946 } |
| 947 #endif | |
| 948 | |
| 949 //============================================================================= | |
| 950 //------------------------------UnionFind-------------------------------------- | |
| 951 UnionFind::UnionFind( uint max ) : _cnt(max), _max(max), _indices(NEW_RESOURCE_ARRAY(uint,max)) { | |
| 952 Copy::zero_to_bytes( _indices, sizeof(uint)*max ); | |
| 953 } | |
| 954 | |
| 955 void UnionFind::extend( uint from_idx, uint to_idx ) { | |
| 956 _nesting.check(); | |
| 957 if( from_idx >= _max ) { | |
| 958 uint size = 16; | |
| 959 while( size <= from_idx ) size <<=1; | |
| 960 _indices = REALLOC_RESOURCE_ARRAY( uint, _indices, _max, size ); | |
| 961 _max = size; | |
| 962 } | |
| 963 while( _cnt <= from_idx ) _indices[_cnt++] = 0; | |
| 964 _indices[from_idx] = to_idx; | |
| 965 } | |
| 966 | |
| 967 void UnionFind::reset( uint max ) { | |
| 968 assert( max <= max_uint, "Must fit within uint" ); | |
| 969 // Force the Union-Find mapping to be at least this large | |
| 970 extend(max,0); | |
| 971 // Initialize to be the ID mapping. | |
| 418 | 972 for( uint i=0; i<max; i++ ) map(i,i); |
| 0 | 973 } |
| 974 | |
| 975 //------------------------------Find_compress---------------------------------- | |
| 976 // Straight out of Tarjan's union-find algorithm | |
| 977 uint UnionFind::Find_compress( uint idx ) { | |
| 978 uint cur = idx; | |
| 979 uint next = lookup(cur); | |
| 980 while( next != cur ) { // Scan chain of equivalences | |
| 981 assert( next < cur, "always union smaller" ); | |
| 982 cur = next; // until find a fixed-point | |
| 983 next = lookup(cur); | |
| 984 } | |
| 985 // Core of union-find algorithm: update chain of | |
| 986 // equivalences to be equal to the root. | |
| 987 while( idx != next ) { | |
| 988 uint tmp = lookup(idx); | |
| 989 map(idx, next); | |
| 990 idx = tmp; | |
| 991 } | |
| 992 return idx; | |
| 993 } | |
| 994 | |
| 995 //------------------------------Find_const------------------------------------- | |
| 996 // Like Find above, but no path compress, so bad asymptotic behavior | |
| 997 uint UnionFind::Find_const( uint idx ) const { | |
| 998 if( idx == 0 ) return idx; // Ignore the zero idx | |
| 999 // Off the end? This can happen during debugging dumps | |
| 1000 // when data structures have not finished being updated. | |
| 1001 if( idx >= _max ) return idx; | |
| 1002 uint next = lookup(idx); | |
| 1003 while( next != idx ) { // Scan chain of equivalences | |
| 1004 idx = next; // until find a fixed-point | |
| 1005 next = lookup(idx); | |
| 1006 } | |
| 1007 return next; | |
| 1008 } | |
| 1009 | |
| 1010 //------------------------------Union------------------------------------------ | |
| 1011 // union 2 sets together. | |
| 1012 void UnionFind::Union( uint idx1, uint idx2 ) { | |
| 1013 uint src = Find(idx1); | |
| 1014 uint dst = Find(idx2); | |
| 1015 assert( src, "" ); | |
| 1016 assert( dst, "" ); | |
| 1017 assert( src < _max, "oob" ); | |
| 1018 assert( dst < _max, "oob" ); | |
| 1019 assert( src < dst, "always union smaller" ); | |
| 1020 map(dst,src); | |
| 1021 } | |
| 418 | 1022 |
| 1023 #ifndef PRODUCT | |
| 1024 static void edge_dump(GrowableArray<CFGEdge *> *edges) { | |
| 1025 tty->print_cr("---- Edges ----"); | |
| 1026 for (int i = 0; i < edges->length(); i++) { | |
| 1027 CFGEdge *e = edges->at(i); | |
| 1028 if (e != NULL) { | |
| 1029 edges->at(i)->dump(); | |
| 1030 } | |
| 1031 } | |
| 1032 } | |
| 1033 | |
| 1034 static void trace_dump(Trace *traces[], int count) { | |
| 1035 tty->print_cr("---- Traces ----"); | |
| 1036 for (int i = 0; i < count; i++) { | |
| 1037 Trace *tr = traces[i]; | |
| 1038 if (tr != NULL) { | |
| 1039 tr->dump(); | |
| 1040 } | |
| 1041 } | |
| 1042 } | |
| 1043 | |
| 1044 void Trace::dump( ) const { | |
| 1045 tty->print_cr("Trace (freq %f)", first_block()->_freq); | |
| 1046 for (Block *b = first_block(); b != NULL; b = next(b)) { | |
| 1047 tty->print(" B%d", b->_pre_order); | |
| 1048 if (b->head()->is_Loop()) { | |
| 1049 tty->print(" (L%d)", b->compute_loop_alignment()); | |
| 1050 } | |
| 1051 if (b->has_loop_alignment()) { | |
| 1052 tty->print(" (T%d)", b->code_alignment()); | |
| 1053 } | |
| 1054 } | |
| 1055 tty->cr(); | |
| 1056 } | |
| 1057 | |
| 1058 void CFGEdge::dump( ) const { | |
| 1059 tty->print(" B%d --> B%d Freq: %f out:%3d%% in:%3d%% State: ", | |
| 1060 from()->_pre_order, to()->_pre_order, freq(), _from_pct, _to_pct); | |
| 1061 switch(state()) { | |
| 1062 case connected: | |
| 1063 tty->print("connected"); | |
| 1064 break; | |
| 1065 case open: | |
| 1066 tty->print("open"); | |
| 1067 break; | |
| 1068 case interior: | |
| 1069 tty->print("interior"); | |
| 1070 break; | |
| 1071 } | |
| 1072 if (infrequent()) { | |
| 1073 tty->print(" infrequent"); | |
| 1074 } | |
| 1075 tty->cr(); | |
| 1076 } | |
| 1077 #endif | |
| 1078 | |
| 1079 //============================================================================= | |
| 1080 | |
| 1081 //------------------------------edge_order------------------------------------- | |
| 1082 // Comparison function for edges | |
| 1083 static int edge_order(CFGEdge **e0, CFGEdge **e1) { | |
| 1084 float freq0 = (*e0)->freq(); | |
| 1085 float freq1 = (*e1)->freq(); | |
| 1086 if (freq0 != freq1) { | |
| 1087 return freq0 > freq1 ? -1 : 1; | |
| 1088 } | |
| 1089 | |
| 1090 int dist0 = (*e0)->to()->_rpo - (*e0)->from()->_rpo; | |
| 1091 int dist1 = (*e1)->to()->_rpo - (*e1)->from()->_rpo; | |
| 1092 | |
| 1093 return dist1 - dist0; | |
| 1094 } | |
| 1095 | |
| 1096 //------------------------------trace_frequency_order-------------------------- | |
| 1097 // Comparison function for edges | |
| 1098 static int trace_frequency_order(const void *p0, const void *p1) { | |
| 1099 Trace *tr0 = *(Trace **) p0; | |
| 1100 Trace *tr1 = *(Trace **) p1; | |
| 1101 Block *b0 = tr0->first_block(); | |
| 1102 Block *b1 = tr1->first_block(); | |
| 1103 | |
| 1104 // The trace of connector blocks goes at the end; | |
| 1105 // we only expect one such trace | |
| 1106 if (b0->is_connector() != b1->is_connector()) { | |
| 1107 return b1->is_connector() ? -1 : 1; | |
| 1108 } | |
| 1109 | |
| 1110 // Pull more frequently executed blocks to the beginning | |
| 1111 float freq0 = b0->_freq; | |
| 1112 float freq1 = b1->_freq; | |
| 1113 if (freq0 != freq1) { | |
| 1114 return freq0 > freq1 ? -1 : 1; | |
| 1115 } | |
| 1116 | |
| 1117 int diff = tr0->first_block()->_rpo - tr1->first_block()->_rpo; | |
| 1118 | |
| 1119 return diff; | |
| 1120 } | |
| 1121 | |
| 1122 //------------------------------find_edges------------------------------------- | |
| 1123 // Find edges of interest, i.e, those which can fall through. Presumes that | |
| 1124 // edges which don't fall through are of low frequency and can be generally | |
| 1125 // ignored. Initialize the list of traces. | |
| 1126 void PhaseBlockLayout::find_edges() | |
| 1127 { | |
| 1128 // Walk the blocks, creating edges and Traces | |
| 1129 uint i; | |
| 1130 Trace *tr = NULL; | |
| 1131 for (i = 0; i < _cfg._num_blocks; i++) { | |
| 1132 Block *b = _cfg._blocks[i]; | |
| 1133 tr = new Trace(b, next, prev); | |
| 1134 traces[tr->id()] = tr; | |
| 1135 | |
| 1136 // All connector blocks should be at the end of the list | |
| 1137 if (b->is_connector()) break; | |
| 1138 | |
| 1139 // If this block and the next one have a one-to-one successor | |
| 1140 // predecessor relationship, simply append the next block | |
| 1141 int nfallthru = b->num_fall_throughs(); | |
| 1142 while (nfallthru == 1 && | |
| 1143 b->succ_fall_through(0)) { | |
| 1144 Block *n = b->_succs[0]; | |
| 1145 | |
| 1146 // Skip over single-entry connector blocks, we don't want to | |
| 1147 // add them to the trace. | |
| 1148 while (n->is_connector() && n->num_preds() == 1) { | |
| 1149 n = n->_succs[0]; | |
| 1150 } | |
| 1151 | |
| 1152 // We see a merge point, so stop search for the next block | |
| 1153 if (n->num_preds() != 1) break; | |
| 1154 | |
| 1155 i++; | |
| 1156 assert(n = _cfg._blocks[i], "expecting next block"); | |
| 1157 tr->append(n); | |
| 1158 uf->map(n->_pre_order, tr->id()); | |
| 1159 traces[n->_pre_order] = NULL; | |
| 1160 nfallthru = b->num_fall_throughs(); | |
| 1161 b = n; | |
| 1162 } | |
| 1163 | |
| 1164 if (nfallthru > 0) { | |
| 1165 // Create a CFGEdge for each outgoing | |
| 1166 // edge that could be a fall-through. | |
| 1167 for (uint j = 0; j < b->_num_succs; j++ ) { | |
| 1168 if (b->succ_fall_through(j)) { | |
| 1169 Block *target = b->non_connector_successor(j); | |
| 1170 float freq = b->_freq * b->succ_prob(j); | |
| 1171 int from_pct = (int) ((100 * freq) / b->_freq); | |
| 1172 int to_pct = (int) ((100 * freq) / target->_freq); | |
| 1173 edges->append(new CFGEdge(b, target, freq, from_pct, to_pct)); | |
| 1174 } | |
| 1175 } | |
| 1176 } | |
| 1177 } | |
| 1178 | |
| 1179 // Group connector blocks into one trace | |
| 1180 for (i++; i < _cfg._num_blocks; i++) { | |
| 1181 Block *b = _cfg._blocks[i]; | |
| 1182 assert(b->is_connector(), "connector blocks at the end"); | |
| 1183 tr->append(b); | |
| 1184 uf->map(b->_pre_order, tr->id()); | |
| 1185 traces[b->_pre_order] = NULL; | |
| 1186 } | |
| 1187 } | |
| 1188 | |
| 1189 //------------------------------union_traces---------------------------------- | |
| 1190 // Union two traces together in uf, and null out the trace in the list | |
| 1191 void PhaseBlockLayout::union_traces(Trace* updated_trace, Trace* old_trace) | |
| 1192 { | |
| 1193 uint old_id = old_trace->id(); | |
| 1194 uint updated_id = updated_trace->id(); | |
| 1195 | |
| 1196 uint lo_id = updated_id; | |
| 1197 uint hi_id = old_id; | |
| 1198 | |
| 1199 // If from is greater than to, swap values to meet | |
| 1200 // UnionFind guarantee. | |
| 1201 if (updated_id > old_id) { | |
| 1202 lo_id = old_id; | |
| 1203 hi_id = updated_id; | |
| 1204 | |
| 1205 // Fix up the trace ids | |
| 1206 traces[lo_id] = traces[updated_id]; | |
| 1207 updated_trace->set_id(lo_id); | |
| 1208 } | |
| 1209 | |
| 1210 // Union the lower with the higher and remove the pointer | |
| 1211 // to the higher. | |
| 1212 uf->Union(lo_id, hi_id); | |
| 1213 traces[hi_id] = NULL; | |
| 1214 } | |
| 1215 | |
| 1216 //------------------------------grow_traces------------------------------------- | |
| 1217 // Append traces together via the most frequently executed edges | |
| 1218 void PhaseBlockLayout::grow_traces() | |
| 1219 { | |
| 1220 // Order the edges, and drive the growth of Traces via the most | |
| 1221 // frequently executed edges. | |
| 1222 edges->sort(edge_order); | |
| 1223 for (int i = 0; i < edges->length(); i++) { | |
| 1224 CFGEdge *e = edges->at(i); | |
| 1225 | |
| 1226 if (e->state() != CFGEdge::open) continue; | |
| 1227 | |
| 1228 Block *src_block = e->from(); | |
| 1229 Block *targ_block = e->to(); | |
| 1230 | |
| 1231 // Don't grow traces along backedges? | |
| 1232 if (!BlockLayoutRotateLoops) { | |
| 1233 if (targ_block->_rpo <= src_block->_rpo) { | |
| 1234 targ_block->set_loop_alignment(targ_block); | |
| 1235 continue; | |
| 1236 } | |
| 1237 } | |
| 1238 | |
| 1239 Trace *src_trace = trace(src_block); | |
| 1240 Trace *targ_trace = trace(targ_block); | |
| 1241 | |
| 1242 // If the edge in question can join two traces at their ends, | |
| 1243 // append one trace to the other. | |
| 1244 if (src_trace->last_block() == src_block) { | |
| 1245 if (src_trace == targ_trace) { | |
| 1246 e->set_state(CFGEdge::interior); | |
| 1247 if (targ_trace->backedge(e)) { | |
| 1248 // Reset i to catch any newly eligible edge | |
| 1249 // (Or we could remember the first "open" edge, and reset there) | |
| 1250 i = 0; | |
| 1251 } | |
| 1252 } else if (targ_trace->first_block() == targ_block) { | |
| 1253 e->set_state(CFGEdge::connected); | |
| 1254 src_trace->append(targ_trace); | |
| 1255 union_traces(src_trace, targ_trace); | |
| 1256 } | |
| 1257 } | |
| 1258 } | |
| 1259 } | |
| 1260 | |
| 1261 //------------------------------merge_traces----------------------------------- | |
| 1262 // Embed one trace into another, if the fork or join points are sufficiently | |
| 1263 // balanced. | |
| 1264 void PhaseBlockLayout::merge_traces(bool fall_thru_only) | |
| 1265 { | |
| 1266 // Walk the edge list a another time, looking at unprocessed edges. | |
| 1267 // Fold in diamonds | |
| 1268 for (int i = 0; i < edges->length(); i++) { | |
| 1269 CFGEdge *e = edges->at(i); | |
| 1270 | |
| 1271 if (e->state() != CFGEdge::open) continue; | |
| 1272 if (fall_thru_only) { | |
| 1273 if (e->infrequent()) continue; | |
| 1274 } | |
| 1275 | |
| 1276 Block *src_block = e->from(); | |
| 1277 Trace *src_trace = trace(src_block); | |
| 1278 bool src_at_tail = src_trace->last_block() == src_block; | |
| 1279 | |
| 1280 Block *targ_block = e->to(); | |
| 1281 Trace *targ_trace = trace(targ_block); | |
| 1282 bool targ_at_start = targ_trace->first_block() == targ_block; | |
| 1283 | |
| 1284 if (src_trace == targ_trace) { | |
| 1285 // This may be a loop, but we can't do much about it. | |
| 1286 e->set_state(CFGEdge::interior); | |
| 1287 continue; | |
| 1288 } | |
| 1289 | |
| 1290 if (fall_thru_only) { | |
| 1291 // If the edge links the middle of two traces, we can't do anything. | |
| 1292 // Mark the edge and continue. | |
| 1293 if (!src_at_tail & !targ_at_start) { | |
| 1294 continue; | |
| 1295 } | |
| 1296 | |
| 1297 // Don't grow traces along backedges? | |
| 1298 if (!BlockLayoutRotateLoops && (targ_block->_rpo <= src_block->_rpo)) { | |
| 1299 continue; | |
| 1300 } | |
| 1301 | |
| 1302 // If both ends of the edge are available, why didn't we handle it earlier? | |
| 1303 assert(src_at_tail ^ targ_at_start, "Should have caught this edge earlier."); | |
| 1304 | |
| 1305 if (targ_at_start) { | |
| 1306 // Insert the "targ" trace in the "src" trace if the insertion point | |
| 1307 // is a two way branch. | |
| 1308 // Better profitability check possible, but may not be worth it. | |
| 1309 // Someday, see if the this "fork" has an associated "join"; | |
| 1310 // then make a policy on merging this trace at the fork or join. | |
| 1311 // For example, other things being equal, it may be better to place this | |
| 1312 // trace at the join point if the "src" trace ends in a two-way, but | |
| 1313 // the insertion point is one-way. | |
| 1314 assert(src_block->num_fall_throughs() == 2, "unexpected diamond"); | |
| 1315 e->set_state(CFGEdge::connected); | |
| 1316 src_trace->insert_after(src_block, targ_trace); | |
| 1317 union_traces(src_trace, targ_trace); | |
| 1318 } else if (src_at_tail) { | |
| 1319 if (src_trace != trace(_cfg._broot)) { | |
| 1320 e->set_state(CFGEdge::connected); | |
| 1321 targ_trace->insert_before(targ_block, src_trace); | |
| 1322 union_traces(targ_trace, src_trace); | |
| 1323 } | |
| 1324 } | |
| 1325 } else if (e->state() == CFGEdge::open) { | |
| 1326 // Append traces, even without a fall-thru connection. | |
| 605 | 1327 // But leave root entry at the beginning of the block list. |
| 418 | 1328 if (targ_trace != trace(_cfg._broot)) { |
| 1329 e->set_state(CFGEdge::connected); | |
| 1330 src_trace->append(targ_trace); | |
| 1331 union_traces(src_trace, targ_trace); | |
| 1332 } | |
| 1333 } | |
| 1334 } | |
| 1335 } | |
| 1336 | |
| 1337 //----------------------------reorder_traces----------------------------------- | |
| 1338 // Order the sequence of the traces in some desirable way, and fixup the | |
| 1339 // jumps at the end of each block. | |
| 1340 void PhaseBlockLayout::reorder_traces(int count) | |
| 1341 { | |
| 1342 ResourceArea *area = Thread::current()->resource_area(); | |
| 1343 Trace ** new_traces = NEW_ARENA_ARRAY(area, Trace *, count); | |
| 1344 Block_List worklist; | |
| 1345 int new_count = 0; | |
| 1346 | |
| 1347 // Compact the traces. | |
| 1348 for (int i = 0; i < count; i++) { | |
| 1349 Trace *tr = traces[i]; | |
| 1350 if (tr != NULL) { | |
| 1351 new_traces[new_count++] = tr; | |
| 1352 } | |
| 1353 } | |
| 1354 | |
| 1355 // The entry block should be first on the new trace list. | |
| 1356 Trace *tr = trace(_cfg._broot); | |
| 1357 assert(tr == new_traces[0], "entry trace misplaced"); | |
| 1358 | |
| 1359 // Sort the new trace list by frequency | |
| 1360 qsort(new_traces + 1, new_count - 1, sizeof(new_traces[0]), trace_frequency_order); | |
| 1361 | |
| 1362 // Patch up the successor blocks | |
| 1363 _cfg._blocks.reset(); | |
| 1364 _cfg._num_blocks = 0; | |
| 1365 for (int i = 0; i < new_count; i++) { | |
| 1366 Trace *tr = new_traces[i]; | |
| 1367 if (tr != NULL) { | |
| 1368 tr->fixup_blocks(_cfg); | |
| 1369 } | |
| 1370 } | |
| 1371 } | |
| 1372 | |
| 1373 //------------------------------PhaseBlockLayout------------------------------- | |
| 1374 // Order basic blocks based on frequency | |
| 1375 PhaseBlockLayout::PhaseBlockLayout(PhaseCFG &cfg) : | |
| 1376 Phase(BlockLayout), | |
| 1377 _cfg(cfg) | |
| 1378 { | |
| 1379 ResourceMark rm; | |
| 1380 ResourceArea *area = Thread::current()->resource_area(); | |
| 1381 | |
| 1382 // List of traces | |
| 1383 int size = _cfg._num_blocks + 1; | |
| 1384 traces = NEW_ARENA_ARRAY(area, Trace *, size); | |
| 1385 memset(traces, 0, size*sizeof(Trace*)); | |
| 1386 next = NEW_ARENA_ARRAY(area, Block *, size); | |
| 1387 memset(next, 0, size*sizeof(Block *)); | |
| 1388 prev = NEW_ARENA_ARRAY(area, Block *, size); | |
| 1389 memset(prev , 0, size*sizeof(Block *)); | |
| 1390 | |
| 1391 // List of edges | |
| 1392 edges = new GrowableArray<CFGEdge*>; | |
| 1393 | |
| 1394 // Mapping block index --> block_trace | |
| 1395 uf = new UnionFind(size); | |
| 1396 uf->reset(size); | |
| 1397 | |
| 1398 // Find edges and create traces. | |
| 1399 find_edges(); | |
| 1400 | |
| 1401 // Grow traces at their ends via most frequent edges. | |
| 1402 grow_traces(); | |
| 1403 | |
| 1404 // Merge one trace into another, but only at fall-through points. | |
| 1405 // This may make diamonds and other related shapes in a trace. | |
| 1406 merge_traces(true); | |
| 1407 | |
| 1408 // Run merge again, allowing two traces to be catenated, even if | |
| 1409 // one does not fall through into the other. This appends loosely | |
| 1410 // related traces to be near each other. | |
| 1411 merge_traces(false); | |
| 1412 | |
| 1413 // Re-order all the remaining traces by frequency | |
| 1414 reorder_traces(size); | |
| 1415 | |
| 1416 assert(_cfg._num_blocks >= (uint) (size - 1), "number of blocks can not shrink"); | |
| 1417 } | |
| 1418 | |
| 1419 | |
| 1420 //------------------------------backedge--------------------------------------- | |
| 1421 // Edge e completes a loop in a trace. If the target block is head of the | |
| 1422 // loop, rotate the loop block so that the loop ends in a conditional branch. | |
| 1423 bool Trace::backedge(CFGEdge *e) { | |
| 1424 bool loop_rotated = false; | |
| 1425 Block *src_block = e->from(); | |
| 1426 Block *targ_block = e->to(); | |
| 1427 | |
| 1428 assert(last_block() == src_block, "loop discovery at back branch"); | |
| 1429 if (first_block() == targ_block) { | |
| 1430 if (BlockLayoutRotateLoops && last_block()->num_fall_throughs() < 2) { | |
| 1431 // Find the last block in the trace that has a conditional | |
| 1432 // branch. | |
| 1433 Block *b; | |
| 1434 for (b = last_block(); b != NULL; b = prev(b)) { | |
| 1435 if (b->num_fall_throughs() == 2) { | |
| 1436 break; | |
| 1437 } | |
| 1438 } | |
| 1439 | |
| 1440 if (b != last_block() && b != NULL) { | |
| 1441 loop_rotated = true; | |
| 1442 | |
| 1443 // Rotate the loop by doing two-part linked-list surgery. | |
| 1444 append(first_block()); | |
| 1445 break_loop_after(b); | |
| 1446 } | |
| 1447 } | |
| 1448 | |
| 1449 // Backbranch to the top of a trace | |
| 605 | 1450 // Scroll forward through the trace from the targ_block. If we find |
| 418 | 1451 // a loop head before another loop top, use the the loop head alignment. |
| 1452 for (Block *b = targ_block; b != NULL; b = next(b)) { | |
| 1453 if (b->has_loop_alignment()) { | |
| 1454 break; | |
| 1455 } | |
| 1456 if (b->head()->is_Loop()) { | |
| 1457 targ_block = b; | |
| 1458 break; | |
| 1459 } | |
| 1460 } | |
| 1461 | |
| 1462 first_block()->set_loop_alignment(targ_block); | |
| 1463 | |
| 1464 } else { | |
| 1465 // Backbranch into the middle of a trace | |
| 1466 targ_block->set_loop_alignment(targ_block); | |
| 1467 } | |
| 1468 | |
| 1469 return loop_rotated; | |
| 1470 } | |
| 1471 | |
| 1472 //------------------------------fixup_blocks----------------------------------- | |
| 1473 // push blocks onto the CFG list | |
| 1474 // ensure that blocks have the correct two-way branch sense | |
| 1475 void Trace::fixup_blocks(PhaseCFG &cfg) { | |
| 1476 Block *last = last_block(); | |
| 1477 for (Block *b = first_block(); b != NULL; b = next(b)) { | |
| 1478 cfg._blocks.push(b); | |
| 1479 cfg._num_blocks++; | |
| 1480 if (!b->is_connector()) { | |
| 1481 int nfallthru = b->num_fall_throughs(); | |
| 1482 if (b != last) { | |
| 1483 if (nfallthru == 2) { | |
| 1484 // Ensure that the sense of the branch is correct | |
| 1485 Block *bnext = next(b); | |
| 1486 Block *bs0 = b->non_connector_successor(0); | |
| 1487 | |
| 1488 MachNode *iff = b->_nodes[b->_nodes.size()-3]->as_Mach(); | |
| 1489 ProjNode *proj0 = b->_nodes[b->_nodes.size()-2]->as_Proj(); | |
| 1490 ProjNode *proj1 = b->_nodes[b->_nodes.size()-1]->as_Proj(); | |
| 1491 | |
| 1492 if (bnext == bs0) { | |
| 1493 // Fall-thru case in succs[0], should be in succs[1] | |
| 1494 | |
| 1495 // Flip targets in _succs map | |
| 1496 Block *tbs0 = b->_succs[0]; | |
| 1497 Block *tbs1 = b->_succs[1]; | |
| 1498 b->_succs.map( 0, tbs1 ); | |
| 1499 b->_succs.map( 1, tbs0 ); | |
| 1500 | |
| 1501 // Flip projections to match targets | |
| 1502 b->_nodes.map(b->_nodes.size()-2, proj1); | |
| 1503 b->_nodes.map(b->_nodes.size()-1, proj0); | |
| 1504 } | |
| 1505 } | |
| 1506 } | |
| 1507 } | |
| 1508 } | |
| 1509 } |