Mercurial > hg > graal-compiler
annotate src/share/vm/opto/block.hpp @ 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 | f6f3bb0ee072 |
| children | f03a3c8bd5e5 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 3939 | 2 * Copyright (c) 1997, 2011, 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:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
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:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_OPTO_BLOCK_HPP |
| 26 #define SHARE_VM_OPTO_BLOCK_HPP | |
| 27 | |
| 28 #include "opto/multnode.hpp" | |
| 29 #include "opto/node.hpp" | |
| 30 #include "opto/phase.hpp" | |
| 31 | |
| 0 | 32 // Optimization - Graph Style |
| 33 | |
| 34 class Block; | |
| 35 class CFGLoop; | |
| 36 class MachCallNode; | |
| 37 class Matcher; | |
| 38 class RootNode; | |
| 39 class VectorSet; | |
| 40 struct Tarjan; | |
| 41 | |
| 42 //------------------------------Block_Array------------------------------------ | |
| 43 // Map dense integer indices to Blocks. Uses classic doubling-array trick. | |
| 44 // Abstractly provides an infinite array of Block*'s, initialized to NULL. | |
| 45 // Note that the constructor just zeros things, and since I use Arena | |
| 46 // allocation I do not need a destructor to reclaim storage. | |
| 47 class Block_Array : public ResourceObj { | |
| 3939 | 48 friend class VMStructs; |
| 0 | 49 uint _size; // allocated size, as opposed to formal limit |
| 50 debug_only(uint _limit;) // limit to formal domain | |
| 51 protected: | |
| 52 Block **_blocks; | |
| 53 void grow( uint i ); // Grow array node to fit | |
| 54 | |
| 55 public: | |
| 56 Arena *_arena; // Arena to allocate in | |
| 57 | |
| 58 Block_Array(Arena *a) : _arena(a), _size(OptoBlockListSize) { | |
| 59 debug_only(_limit=0); | |
| 60 _blocks = NEW_ARENA_ARRAY( a, Block *, OptoBlockListSize ); | |
| 61 for( int i = 0; i < OptoBlockListSize; i++ ) { | |
| 62 _blocks[i] = NULL; | |
| 63 } | |
| 64 } | |
| 65 Block *lookup( uint i ) const // Lookup, or NULL for not mapped | |
| 66 { return (i<Max()) ? _blocks[i] : (Block*)NULL; } | |
| 67 Block *operator[] ( uint i ) const // Lookup, or assert for not mapped | |
| 68 { assert( i < Max(), "oob" ); return _blocks[i]; } | |
| 69 // Extend the mapping: index i maps to Block *n. | |
| 70 void map( uint i, Block *n ) { if( i>=Max() ) grow(i); _blocks[i] = n; } | |
| 71 uint Max() const { debug_only(return _limit); return _size; } | |
| 72 }; | |
| 73 | |
| 74 | |
| 75 class Block_List : public Block_Array { | |
| 3939 | 76 friend class VMStructs; |
| 0 | 77 public: |
| 78 uint _cnt; | |
| 79 Block_List() : Block_Array(Thread::current()->resource_area()), _cnt(0) {} | |
| 80 void push( Block *b ) { map(_cnt++,b); } | |
| 81 Block *pop() { return _blocks[--_cnt]; } | |
| 82 Block *rpop() { Block *b = _blocks[0]; _blocks[0]=_blocks[--_cnt]; return b;} | |
| 83 void remove( uint i ); | |
| 84 void insert( uint i, Block *n ); | |
| 85 uint size() const { return _cnt; } | |
| 86 void reset() { _cnt = 0; } | |
| 418 | 87 void print(); |
| 0 | 88 }; |
| 89 | |
| 90 | |
| 91 class CFGElement : public ResourceObj { | |
| 3939 | 92 friend class VMStructs; |
| 0 | 93 public: |
| 94 float _freq; // Execution frequency (estimate) | |
| 95 | |
| 96 CFGElement() : _freq(0.0f) {} | |
| 97 virtual bool is_block() { return false; } | |
| 98 virtual bool is_loop() { return false; } | |
| 99 Block* as_Block() { assert(is_block(), "must be block"); return (Block*)this; } | |
| 100 CFGLoop* as_CFGLoop() { assert(is_loop(), "must be loop"); return (CFGLoop*)this; } | |
| 101 }; | |
| 102 | |
| 103 //------------------------------Block------------------------------------------ | |
| 104 // This class defines a Basic Block. | |
| 105 // Basic blocks are used during the output routines, and are not used during | |
| 106 // any optimization pass. They are created late in the game. | |
| 107 class Block : public CFGElement { | |
| 3939 | 108 friend class VMStructs; |
| 0 | 109 public: |
| 110 // Nodes in this block, in order | |
| 111 Node_List _nodes; | |
| 112 | |
| 113 // Basic blocks have a Node which defines Control for all Nodes pinned in | |
| 114 // this block. This Node is a RegionNode. Exception-causing Nodes | |
| 115 // (division, subroutines) and Phi functions are always pinned. Later, | |
| 116 // every Node will get pinned to some block. | |
| 117 Node *head() const { return _nodes[0]; } | |
| 118 | |
| 119 // CAUTION: num_preds() is ONE based, so that predecessor numbers match | |
| 120 // input edges to Regions and Phis. | |
| 121 uint num_preds() const { return head()->req(); } | |
| 122 Node *pred(uint i) const { return head()->in(i); } | |
| 123 | |
| 124 // Array of successor blocks, same size as projs array | |
| 125 Block_Array _succs; | |
| 126 | |
| 127 // Basic blocks have some number of Nodes which split control to all | |
| 128 // following blocks. These Nodes are always Projections. The field in | |
| 129 // the Projection and the block-ending Node determine which Block follows. | |
| 130 uint _num_succs; | |
| 131 | |
| 132 // Basic blocks also carry all sorts of good old fashioned DFS information | |
| 133 // used to find loops, loop nesting depth, dominators, etc. | |
| 134 uint _pre_order; // Pre-order DFS number | |
| 135 | |
| 136 // Dominator tree | |
| 137 uint _dom_depth; // Depth in dominator tree for fast LCA | |
| 138 Block* _idom; // Immediate dominator block | |
| 139 | |
| 140 CFGLoop *_loop; // Loop to which this block belongs | |
| 141 uint _rpo; // Number in reverse post order walk | |
| 142 | |
| 143 virtual bool is_block() { return true; } | |
| 418 | 144 float succ_prob(uint i); // return probability of i'th successor |
| 145 int num_fall_throughs(); // How many fall-through candidate this block has | |
| 146 void update_uncommon_branch(Block* un); // Lower branch prob to uncommon code | |
| 147 bool succ_fall_through(uint i); // Is successor "i" is a fall-through candidate | |
| 148 Block* lone_fall_through(); // Return lone fall-through Block or null | |
| 0 | 149 |
| 150 Block* dom_lca(Block* that); // Compute LCA in dominator tree. | |
| 151 #ifdef ASSERT | |
| 152 bool dominates(Block* that) { | |
| 153 int dom_diff = this->_dom_depth - that->_dom_depth; | |
| 154 if (dom_diff > 0) return false; | |
| 155 for (; dom_diff < 0; dom_diff++) that = that->_idom; | |
| 156 return this == that; | |
| 157 } | |
| 158 #endif | |
| 159 | |
| 160 // Report the alignment required by this block. Must be a power of 2. | |
| 161 // The previous block will insert nops to get this alignment. | |
| 162 uint code_alignment(); | |
| 418 | 163 uint compute_loop_alignment(); |
| 0 | 164 |
| 165 // BLOCK_FREQUENCY is a sentinel to mark uses of constant block frequencies. | |
| 166 // It is currently also used to scale such frequencies relative to | |
| 167 // FreqCountInvocations relative to the old value of 1500. | |
| 168 #define BLOCK_FREQUENCY(f) ((f * (float) 1500) / FreqCountInvocations) | |
| 169 | |
| 170 // Register Pressure (estimate) for Splitting heuristic | |
| 171 uint _reg_pressure; | |
| 172 uint _ihrp_index; | |
| 173 uint _freg_pressure; | |
| 174 uint _fhrp_index; | |
| 175 | |
| 176 // Mark and visited bits for an LCA calculation in insert_anti_dependences. | |
| 177 // Since they hold unique node indexes, they do not need reinitialization. | |
| 178 node_idx_t _raise_LCA_mark; | |
| 179 void set_raise_LCA_mark(node_idx_t x) { _raise_LCA_mark = x; } | |
| 180 node_idx_t raise_LCA_mark() const { return _raise_LCA_mark; } | |
| 181 node_idx_t _raise_LCA_visited; | |
| 182 void set_raise_LCA_visited(node_idx_t x) { _raise_LCA_visited = x; } | |
| 183 node_idx_t raise_LCA_visited() const { return _raise_LCA_visited; } | |
| 184 | |
| 185 // Estimated size in bytes of first instructions in a loop. | |
| 186 uint _first_inst_size; | |
| 187 uint first_inst_size() const { return _first_inst_size; } | |
| 188 void set_first_inst_size(uint s) { _first_inst_size = s; } | |
| 189 | |
| 190 // Compute the size of first instructions in this block. | |
| 191 uint compute_first_inst_size(uint& sum_size, uint inst_cnt, PhaseRegAlloc* ra); | |
| 192 | |
| 193 // Compute alignment padding if the block needs it. | |
| 194 // Align a loop if loop's padding is less or equal to padding limit | |
| 195 // or the size of first instructions in the loop > padding. | |
| 196 uint alignment_padding(int current_offset) { | |
| 197 int block_alignment = code_alignment(); | |
| 198 int max_pad = block_alignment-relocInfo::addr_unit(); | |
| 199 if( max_pad > 0 ) { | |
| 200 assert(is_power_of_2(max_pad+relocInfo::addr_unit()), ""); | |
| 201 int current_alignment = current_offset & max_pad; | |
| 202 if( current_alignment != 0 ) { | |
| 203 uint padding = (block_alignment-current_alignment) & max_pad; | |
| 418 | 204 if( has_loop_alignment() && |
| 205 padding > (uint)MaxLoopPad && | |
| 206 first_inst_size() <= padding ) { | |
| 207 return 0; | |
| 0 | 208 } |
| 418 | 209 return padding; |
| 0 | 210 } |
| 211 } | |
| 212 return 0; | |
| 213 } | |
| 214 | |
| 215 // Connector blocks. Connector blocks are basic blocks devoid of | |
| 216 // instructions, but may have relevant non-instruction Nodes, such as | |
| 217 // Phis or MergeMems. Such blocks are discovered and marked during the | |
| 218 // RemoveEmpty phase, and elided during Output. | |
| 219 bool _connector; | |
| 220 void set_connector() { _connector = true; } | |
| 221 bool is_connector() const { return _connector; }; | |
| 222 | |
| 418 | 223 // Loop_alignment will be set for blocks which are at the top of loops. |
| 224 // The block layout pass may rotate loops such that the loop head may not | |
| 225 // be the sequentially first block of the loop encountered in the linear | |
| 226 // list of blocks. If the layout pass is not run, loop alignment is set | |
| 227 // for each block which is the head of a loop. | |
| 228 uint _loop_alignment; | |
| 229 void set_loop_alignment(Block *loop_top) { | |
| 230 uint new_alignment = loop_top->compute_loop_alignment(); | |
| 231 if (new_alignment > _loop_alignment) { | |
| 232 _loop_alignment = new_alignment; | |
| 233 } | |
| 234 } | |
| 235 uint loop_alignment() const { return _loop_alignment; } | |
| 236 bool has_loop_alignment() const { return loop_alignment() > 0; } | |
| 237 | |
| 0 | 238 // Create a new Block with given head Node. |
| 239 // Creates the (empty) predecessor arrays. | |
| 240 Block( Arena *a, Node *headnode ) | |
| 241 : CFGElement(), | |
| 242 _nodes(a), | |
| 243 _succs(a), | |
| 244 _num_succs(0), | |
| 245 _pre_order(0), | |
| 246 _idom(0), | |
| 247 _loop(NULL), | |
| 248 _reg_pressure(0), | |
| 249 _ihrp_index(1), | |
| 250 _freg_pressure(0), | |
| 251 _fhrp_index(1), | |
| 252 _raise_LCA_mark(0), | |
| 253 _raise_LCA_visited(0), | |
| 254 _first_inst_size(999999), | |
| 418 | 255 _connector(false), |
| 256 _loop_alignment(0) { | |
| 0 | 257 _nodes.push(headnode); |
| 258 } | |
| 259 | |
| 260 // Index of 'end' Node | |
| 261 uint end_idx() const { | |
| 262 // %%%%% add a proj after every goto | |
| 263 // so (last->is_block_proj() != last) always, then simplify this code | |
| 264 // This will not give correct end_idx for block 0 when it only contains root. | |
| 265 int last_idx = _nodes.size() - 1; | |
| 266 Node *last = _nodes[last_idx]; | |
| 267 assert(last->is_block_proj() == last || last->is_block_proj() == _nodes[last_idx - _num_succs], ""); | |
| 268 return (last->is_block_proj() == last) ? last_idx : (last_idx - _num_succs); | |
| 269 } | |
| 270 | |
| 271 // Basic blocks have a Node which ends them. This Node determines which | |
| 272 // basic block follows this one in the program flow. This Node is either an | |
| 273 // IfNode, a GotoNode, a JmpNode, or a ReturnNode. | |
| 274 Node *end() const { return _nodes[end_idx()]; } | |
| 275 | |
| 276 // Add an instruction to an existing block. It must go after the head | |
| 277 // instruction and before the end instruction. | |
| 278 void add_inst( Node *n ) { _nodes.insert(end_idx(),n); } | |
| 279 // Find node in block | |
| 280 uint find_node( const Node *n ) const; | |
| 281 // Find and remove n from block list | |
| 282 void find_remove( const Node *n ); | |
| 283 | |
| 284 // Schedule a call next in the block | |
| 285 uint sched_call(Matcher &matcher, Block_Array &bbs, uint node_cnt, Node_List &worklist, int *ready_cnt, MachCallNode *mcall, VectorSet &next_call); | |
| 286 | |
| 287 // Perform basic-block local scheduling | |
| 288 Node *select(PhaseCFG *cfg, Node_List &worklist, int *ready_cnt, VectorSet &next_call, uint sched_slot); | |
| 289 void set_next_call( Node *n, VectorSet &next_call, Block_Array &bbs ); | |
| 290 void needed_for_next_call(Node *this_call, VectorSet &next_call, Block_Array &bbs); | |
| 291 bool schedule_local(PhaseCFG *cfg, Matcher &m, int *ready_cnt, VectorSet &next_call); | |
| 292 // Cleanup if any code lands between a Call and his Catch | |
| 293 void call_catch_cleanup(Block_Array &bbs); | |
| 294 // Detect implicit-null-check opportunities. Basically, find NULL checks | |
| 295 // with suitable memory ops nearby. Use the memory op to do the NULL check. | |
| 296 // I can generate a memory op if there is not one nearby. | |
| 297 void implicit_null_check(PhaseCFG *cfg, Node *proj, Node *val, int allowed_reasons); | |
| 298 | |
| 299 // Return the empty status of a block | |
| 300 enum { not_empty, empty_with_goto, completely_empty }; | |
| 301 int is_Empty() const; | |
| 302 | |
| 303 // Forward through connectors | |
| 304 Block* non_connector() { | |
| 305 Block* s = this; | |
| 306 while (s->is_connector()) { | |
| 307 s = s->_succs[0]; | |
| 308 } | |
| 309 return s; | |
| 310 } | |
| 311 | |
| 418 | 312 // Return true if b is a successor of this block |
| 313 bool has_successor(Block* b) const { | |
| 314 for (uint i = 0; i < _num_succs; i++ ) { | |
| 315 if (non_connector_successor(i) == b) { | |
| 316 return true; | |
| 317 } | |
| 318 } | |
| 319 return false; | |
| 320 } | |
| 321 | |
| 0 | 322 // Successor block, after forwarding through connectors |
| 323 Block* non_connector_successor(int i) const { | |
| 324 return _succs[i]->non_connector(); | |
| 325 } | |
| 326 | |
| 327 // Examine block's code shape to predict if it is not commonly executed. | |
| 328 bool has_uncommon_code() const; | |
| 329 | |
| 330 // Use frequency calculations and code shape to predict if the block | |
| 331 // is uncommon. | |
| 332 bool is_uncommon( Block_Array &bbs ) const; | |
| 333 | |
| 334 #ifndef PRODUCT | |
| 335 // Debugging print of basic block | |
| 3851 | 336 void dump_bidx(const Block* orig, outputStream* st = tty) const; |
| 337 void dump_pred(const Block_Array *bbs, Block* orig, outputStream* st = tty) const; | |
| 338 void dump_head( const Block_Array *bbs, outputStream* st = tty ) const; | |
| 339 void dump() const; | |
| 0 | 340 void dump( const Block_Array *bbs ) const; |
| 341 #endif | |
| 342 }; | |
| 343 | |
| 344 | |
| 345 //------------------------------PhaseCFG--------------------------------------- | |
| 346 // Build an array of Basic Block pointers, one per Node. | |
| 347 class PhaseCFG : public Phase { | |
| 3939 | 348 friend class VMStructs; |
| 0 | 349 private: |
| 350 // Build a proper looking cfg. Return count of basic blocks | |
| 351 uint build_cfg(); | |
| 352 | |
| 353 // Perform DFS search. | |
| 354 // Setup 'vertex' as DFS to vertex mapping. | |
| 355 // Setup 'semi' as vertex to DFS mapping. | |
| 356 // Set 'parent' to DFS parent. | |
| 357 uint DFS( Tarjan *tarjan ); | |
| 358 | |
| 359 // Helper function to insert a node into a block | |
| 360 void schedule_node_into_block( Node *n, Block *b ); | |
| 361 | |
| 604 | 362 void replace_block_proj_ctrl( Node *n ); |
|
601
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
470
diff
changeset
|
363 |
| 0 | 364 // Set the basic block for pinned Nodes |
| 365 void schedule_pinned_nodes( VectorSet &visited ); | |
| 366 | |
| 367 // I'll need a few machine-specific GotoNodes. Clone from this one. | |
| 368 MachNode *_goto; | |
| 369 | |
| 370 Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false); | |
| 371 void verify_anti_dependences(Block* LCA, Node* load) { | |
| 372 assert(LCA == _bbs[load->_idx], "should already be scheduled"); | |
| 373 insert_anti_dependences(LCA, load, true); | |
| 374 } | |
| 375 | |
| 376 public: | |
| 377 PhaseCFG( Arena *a, RootNode *r, Matcher &m ); | |
| 378 | |
| 379 uint _num_blocks; // Count of basic blocks | |
| 380 Block_List _blocks; // List of basic blocks | |
| 381 RootNode *_root; // Root of whole program | |
| 382 Block_Array _bbs; // Map Nodes to owning Basic Block | |
| 383 Block *_broot; // Basic block of root | |
| 384 uint _rpo_ctr; | |
| 385 CFGLoop* _root_loop; | |
| 673 | 386 float _outer_loop_freq; // Outmost loop frequency |
| 0 | 387 |
| 388 // Per node latency estimation, valid only during GCM | |
| 1685 | 389 GrowableArray<uint> *_node_latency; |
| 0 | 390 |
| 391 #ifndef PRODUCT | |
| 392 bool _trace_opto_pipelining; // tracing flag | |
| 393 #endif | |
| 394 | |
|
833
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
395 #ifdef ASSERT |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
396 Unique_Node_List _raw_oops; |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
397 #endif |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
398 |
| 0 | 399 // Build dominators |
| 400 void Dominators(); | |
| 401 | |
| 402 // Estimate block frequencies based on IfNode probabilities | |
| 403 void Estimate_Block_Frequency(); | |
| 404 | |
| 405 // Global Code Motion. See Click's PLDI95 paper. Place Nodes in specific | |
| 406 // basic blocks; i.e. _bbs now maps _idx for all Nodes to some Block. | |
| 407 void GlobalCodeMotion( Matcher &m, uint unique, Node_List &proj_list ); | |
| 408 | |
| 409 // Compute the (backwards) latency of a node from the uses | |
| 410 void latency_from_uses(Node *n); | |
| 411 | |
| 412 // Compute the (backwards) latency of a node from a single use | |
| 413 int latency_from_use(Node *n, const Node *def, Node *use); | |
| 414 | |
| 415 // Compute the (backwards) latency of a node from the uses of this instruction | |
| 416 void partial_latency_of_defs(Node *n); | |
| 417 | |
| 418 // Schedule Nodes early in their basic blocks. | |
| 419 bool schedule_early(VectorSet &visited, Node_List &roots); | |
| 420 | |
| 421 // For each node, find the latest block it can be scheduled into | |
| 422 // and then select the cheapest block between the latest and earliest | |
| 423 // block to place the node. | |
| 424 void schedule_late(VectorSet &visited, Node_List &stack); | |
| 425 | |
| 426 // Pick a block between early and late that is a cheaper alternative | |
| 427 // to late. Helper for schedule_late. | |
| 428 Block* hoist_to_cheaper_block(Block* LCA, Block* early, Node* self); | |
| 429 | |
| 430 // Compute the instruction global latency with a backwards walk | |
| 431 void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack); | |
| 432 | |
| 418 | 433 // Set loop alignment |
| 434 void set_loop_alignment(); | |
| 435 | |
| 0 | 436 // Remove empty basic blocks |
| 418 | 437 void remove_empty(); |
| 438 void fixup_flow(); | |
| 439 bool move_to_next(Block* bx, uint b_index); | |
| 440 void move_to_end(Block* bx, uint b_index); | |
| 441 void insert_goto_at(uint block_no, uint succ_no); | |
| 0 | 442 |
| 443 // Check for NeverBranch at block end. This needs to become a GOTO to the | |
| 444 // true target. NeverBranch are treated as a conditional branch that always | |
| 445 // goes the same direction for most of the optimizer and are used to give a | |
| 446 // fake exit path to infinite loops. At this late stage they need to turn | |
| 447 // into Goto's so that when you enter the infinite loop you indeed hang. | |
| 448 void convert_NeverBranch_to_Goto(Block *b); | |
| 449 | |
| 450 CFGLoop* create_loop_tree(); | |
| 451 | |
| 452 // Insert a node into a block, and update the _bbs | |
| 453 void insert( Block *b, uint idx, Node *n ) { | |
| 454 b->_nodes.insert( idx, n ); | |
| 455 _bbs.map( n->_idx, b ); | |
| 456 } | |
| 457 | |
| 458 #ifndef PRODUCT | |
| 459 bool trace_opto_pipelining() const { return _trace_opto_pipelining; } | |
| 460 | |
| 461 // Debugging print of CFG | |
| 462 void dump( ) const; // CFG only | |
| 463 void _dump_cfg( const Node *end, VectorSet &visited ) const; | |
| 464 void verify() const; | |
| 465 void dump_headers(); | |
| 466 #else | |
| 467 bool trace_opto_pipelining() const { return false; } | |
| 468 #endif | |
| 469 }; | |
| 470 | |
| 471 | |
| 418 | 472 //------------------------------UnionFind-------------------------------------- |
| 0 | 473 // Map Block indices to a block-index for a cfg-cover. |
| 474 // Array lookup in the optimized case. | |
| 475 class UnionFind : public ResourceObj { | |
| 476 uint _cnt, _max; | |
| 477 uint* _indices; | |
| 478 ReallocMark _nesting; // assertion check for reallocations | |
| 479 public: | |
| 480 UnionFind( uint max ); | |
| 481 void reset( uint max ); // Reset to identity map for [0..max] | |
| 482 | |
| 483 uint lookup( uint nidx ) const { | |
| 484 return _indices[nidx]; | |
| 485 } | |
| 486 uint operator[] (uint nidx) const { return lookup(nidx); } | |
| 487 | |
| 488 void map( uint from_idx, uint to_idx ) { | |
| 489 assert( from_idx < _cnt, "oob" ); | |
| 490 _indices[from_idx] = to_idx; | |
| 491 } | |
| 492 void extend( uint from_idx, uint to_idx ); | |
| 493 | |
| 494 uint Size() const { return _cnt; } | |
| 495 | |
| 496 uint Find( uint idx ) { | |
| 497 assert( idx < 65536, "Must fit into uint"); | |
| 498 uint uf_idx = lookup(idx); | |
| 499 return (uf_idx == idx) ? uf_idx : Find_compress(idx); | |
| 500 } | |
| 501 uint Find_compress( uint idx ); | |
| 502 uint Find_const( uint idx ) const; | |
| 503 void Union( uint idx1, uint idx2 ); | |
| 504 | |
| 505 }; | |
| 506 | |
| 507 //----------------------------BlockProbPair--------------------------- | |
| 508 // Ordered pair of Node*. | |
| 509 class BlockProbPair VALUE_OBJ_CLASS_SPEC { | |
| 510 protected: | |
| 511 Block* _target; // block target | |
| 512 float _prob; // probability of edge to block | |
| 513 public: | |
| 514 BlockProbPair() : _target(NULL), _prob(0.0) {} | |
| 515 BlockProbPair(Block* b, float p) : _target(b), _prob(p) {} | |
| 516 | |
| 517 Block* get_target() const { return _target; } | |
| 518 float get_prob() const { return _prob; } | |
| 519 }; | |
| 520 | |
| 521 //------------------------------CFGLoop------------------------------------------- | |
| 522 class CFGLoop : public CFGElement { | |
| 3939 | 523 friend class VMStructs; |
| 0 | 524 int _id; |
| 525 int _depth; | |
| 526 CFGLoop *_parent; // root of loop tree is the method level "pseudo" loop, it's parent is null | |
| 527 CFGLoop *_sibling; // null terminated list | |
| 528 CFGLoop *_child; // first child, use child's sibling to visit all immediately nested loops | |
| 529 GrowableArray<CFGElement*> _members; // list of members of loop | |
| 530 GrowableArray<BlockProbPair> _exits; // list of successor blocks and their probabilities | |
| 531 float _exit_prob; // probability any loop exit is taken on a single loop iteration | |
| 532 void update_succ_freq(Block* b, float freq); | |
| 533 | |
| 534 public: | |
| 535 CFGLoop(int id) : | |
| 536 CFGElement(), | |
| 537 _id(id), | |
| 538 _depth(0), | |
| 539 _parent(NULL), | |
| 540 _sibling(NULL), | |
| 541 _child(NULL), | |
| 542 _exit_prob(1.0f) {} | |
| 543 CFGLoop* parent() { return _parent; } | |
| 544 void push_pred(Block* blk, int i, Block_List& worklist, Block_Array& node_to_blk); | |
| 545 void add_member(CFGElement *s) { _members.push(s); } | |
| 546 void add_nested_loop(CFGLoop* cl); | |
| 547 Block* head() { | |
| 548 assert(_members.at(0)->is_block(), "head must be a block"); | |
| 549 Block* hd = _members.at(0)->as_Block(); | |
| 550 assert(hd->_loop == this, "just checking"); | |
| 551 assert(hd->head()->is_Loop(), "must begin with loop head node"); | |
| 552 return hd; | |
| 553 } | |
| 554 Block* backedge_block(); // Return the block on the backedge of the loop (else NULL) | |
| 555 void compute_loop_depth(int depth); | |
| 556 void compute_freq(); // compute frequency with loop assuming head freq 1.0f | |
| 557 void scale_freq(); // scale frequency by loop trip count (including outer loops) | |
| 673 | 558 float outer_loop_freq() const; // frequency of outer loop |
| 0 | 559 bool in_loop_nest(Block* b); |
| 560 float trip_count() const { return 1.0f / _exit_prob; } | |
| 561 virtual bool is_loop() { return true; } | |
| 562 int id() { return _id; } | |
| 563 | |
| 564 #ifndef PRODUCT | |
| 565 void dump( ) const; | |
| 566 void dump_tree() const; | |
| 567 #endif | |
| 568 }; | |
| 418 | 569 |
| 570 | |
| 571 //----------------------------------CFGEdge------------------------------------ | |
| 572 // A edge between two basic blocks that will be embodied by a branch or a | |
| 573 // fall-through. | |
| 574 class CFGEdge : public ResourceObj { | |
| 3939 | 575 friend class VMStructs; |
| 418 | 576 private: |
| 577 Block * _from; // Source basic block | |
| 578 Block * _to; // Destination basic block | |
| 579 float _freq; // Execution frequency (estimate) | |
| 580 int _state; | |
| 581 bool _infrequent; | |
| 582 int _from_pct; | |
| 583 int _to_pct; | |
| 584 | |
| 585 // Private accessors | |
| 586 int from_pct() const { return _from_pct; } | |
| 587 int to_pct() const { return _to_pct; } | |
| 588 int from_infrequent() const { return from_pct() < BlockLayoutMinDiamondPercentage; } | |
| 589 int to_infrequent() const { return to_pct() < BlockLayoutMinDiamondPercentage; } | |
| 590 | |
| 591 public: | |
| 592 enum { | |
| 593 open, // initial edge state; unprocessed | |
| 594 connected, // edge used to connect two traces together | |
| 595 interior // edge is interior to trace (could be backedge) | |
| 596 }; | |
| 597 | |
| 598 CFGEdge(Block *from, Block *to, float freq, int from_pct, int to_pct) : | |
| 599 _from(from), _to(to), _freq(freq), | |
| 600 _from_pct(from_pct), _to_pct(to_pct), _state(open) { | |
| 601 _infrequent = from_infrequent() || to_infrequent(); | |
| 602 } | |
| 603 | |
| 604 float freq() const { return _freq; } | |
| 605 Block* from() const { return _from; } | |
| 606 Block* to () const { return _to; } | |
| 607 int infrequent() const { return _infrequent; } | |
| 608 int state() const { return _state; } | |
| 609 | |
| 610 void set_state(int state) { _state = state; } | |
| 611 | |
| 612 #ifndef PRODUCT | |
| 613 void dump( ) const; | |
| 614 #endif | |
| 615 }; | |
| 616 | |
| 617 | |
| 618 //-----------------------------------Trace------------------------------------- | |
| 619 // An ordered list of basic blocks. | |
| 620 class Trace : public ResourceObj { | |
| 621 private: | |
| 622 uint _id; // Unique Trace id (derived from initial block) | |
| 623 Block ** _next_list; // Array mapping index to next block | |
| 624 Block ** _prev_list; // Array mapping index to previous block | |
| 625 Block * _first; // First block in the trace | |
| 626 Block * _last; // Last block in the trace | |
| 627 | |
| 628 // Return the block that follows "b" in the trace. | |
| 629 Block * next(Block *b) const { return _next_list[b->_pre_order]; } | |
| 630 void set_next(Block *b, Block *n) const { _next_list[b->_pre_order] = n; } | |
| 631 | |
| 605 | 632 // Return the block that precedes "b" in the trace. |
| 418 | 633 Block * prev(Block *b) const { return _prev_list[b->_pre_order]; } |
| 634 void set_prev(Block *b, Block *p) const { _prev_list[b->_pre_order] = p; } | |
| 635 | |
| 636 // We've discovered a loop in this trace. Reset last to be "b", and first as | |
| 637 // the block following "b | |
| 638 void break_loop_after(Block *b) { | |
| 639 _last = b; | |
| 640 _first = next(b); | |
| 641 set_prev(_first, NULL); | |
| 642 set_next(_last, NULL); | |
| 643 } | |
| 644 | |
| 645 public: | |
| 646 | |
| 647 Trace(Block *b, Block **next_list, Block **prev_list) : | |
| 648 _first(b), | |
| 649 _last(b), | |
| 650 _next_list(next_list), | |
| 651 _prev_list(prev_list), | |
| 652 _id(b->_pre_order) { | |
| 653 set_next(b, NULL); | |
| 654 set_prev(b, NULL); | |
| 655 }; | |
| 656 | |
| 657 // Return the id number | |
| 658 uint id() const { return _id; } | |
| 659 void set_id(uint id) { _id = id; } | |
| 660 | |
| 661 // Return the first block in the trace | |
| 662 Block * first_block() const { return _first; } | |
| 663 | |
| 664 // Return the last block in the trace | |
| 665 Block * last_block() const { return _last; } | |
| 666 | |
| 667 // Insert a trace in the middle of this one after b | |
| 668 void insert_after(Block *b, Trace *tr) { | |
| 669 set_next(tr->last_block(), next(b)); | |
| 670 if (next(b) != NULL) { | |
| 671 set_prev(next(b), tr->last_block()); | |
| 672 } | |
| 673 | |
| 674 set_next(b, tr->first_block()); | |
| 675 set_prev(tr->first_block(), b); | |
| 676 | |
| 677 if (b == _last) { | |
| 678 _last = tr->last_block(); | |
| 679 } | |
| 680 } | |
| 681 | |
| 682 void insert_before(Block *b, Trace *tr) { | |
| 683 Block *p = prev(b); | |
| 684 assert(p != NULL, "use append instead"); | |
| 685 insert_after(p, tr); | |
| 686 } | |
| 687 | |
| 688 // Append another trace to this one. | |
| 689 void append(Trace *tr) { | |
| 690 insert_after(_last, tr); | |
| 691 } | |
| 692 | |
| 693 // Append a block at the end of this trace | |
| 694 void append(Block *b) { | |
| 695 set_next(_last, b); | |
| 696 set_prev(b, _last); | |
| 697 _last = b; | |
| 698 } | |
| 699 | |
| 700 // Adjust the the blocks in this trace | |
| 701 void fixup_blocks(PhaseCFG &cfg); | |
| 702 bool backedge(CFGEdge *e); | |
| 703 | |
| 704 #ifndef PRODUCT | |
| 705 void dump( ) const; | |
| 706 #endif | |
| 707 }; | |
| 708 | |
| 709 //------------------------------PhaseBlockLayout------------------------------- | |
| 710 // Rearrange blocks into some canonical order, based on edges and their frequencies | |
| 711 class PhaseBlockLayout : public Phase { | |
| 3939 | 712 friend class VMStructs; |
| 418 | 713 PhaseCFG &_cfg; // Control flow graph |
| 714 | |
| 715 GrowableArray<CFGEdge *> *edges; | |
| 716 Trace **traces; | |
| 717 Block **next; | |
| 718 Block **prev; | |
| 719 UnionFind *uf; | |
| 720 | |
| 721 // Given a block, find its encompassing Trace | |
| 722 Trace * trace(Block *b) { | |
| 723 return traces[uf->Find_compress(b->_pre_order)]; | |
| 724 } | |
| 725 public: | |
| 726 PhaseBlockLayout(PhaseCFG &cfg); | |
| 727 | |
| 728 void find_edges(); | |
| 729 void grow_traces(); | |
| 730 void merge_traces(bool loose_connections); | |
| 731 void reorder_traces(int count); | |
| 732 void union_traces(Trace* from, Trace* to); | |
| 733 }; | |
| 1972 | 734 |
| 735 #endif // SHARE_VM_OPTO_BLOCK_HPP |