Mercurial > hg > truffle
annotate src/share/vm/opto/block.hpp @ 4710:41406797186b
7113012: G1: rename not-fully-young GCs as "mixed"
Summary: Renamed partially-young GCs as mixed and fully-young GCs as young. Change all external output that includes those terms (GC log and GC ergo log) as well as any comments, fields, methods, etc. The changeset also includes very minor code tidying up (added some curly brackets).
Reviewed-by: johnc, brutisso
| author | tonyp |
|---|---|
| date | Fri, 16 Dec 2011 02:14:27 -0500 |
| parents | f03a3c8bd5e5 |
| children | cf407b7d3d78 |
| 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 | |
|
4120
f03a3c8bd5e5
7077312: Provide a CALL effect for instruct declaration in the ad file
roland
parents:
3939
diff
changeset
|
284 // helper function that adds caller save registers to MachProjNode |
|
f03a3c8bd5e5
7077312: Provide a CALL effect for instruct declaration in the ad file
roland
parents:
3939
diff
changeset
|
285 void add_call_kills(MachProjNode *proj, RegMask& regs, const char* save_policy, bool exclude_soe); |
| 0 | 286 // Schedule a call next in the block |
| 287 uint sched_call(Matcher &matcher, Block_Array &bbs, uint node_cnt, Node_List &worklist, int *ready_cnt, MachCallNode *mcall, VectorSet &next_call); | |
| 288 | |
| 289 // Perform basic-block local scheduling | |
| 290 Node *select(PhaseCFG *cfg, Node_List &worklist, int *ready_cnt, VectorSet &next_call, uint sched_slot); | |
| 291 void set_next_call( Node *n, VectorSet &next_call, Block_Array &bbs ); | |
| 292 void needed_for_next_call(Node *this_call, VectorSet &next_call, Block_Array &bbs); | |
| 293 bool schedule_local(PhaseCFG *cfg, Matcher &m, int *ready_cnt, VectorSet &next_call); | |
| 294 // Cleanup if any code lands between a Call and his Catch | |
| 295 void call_catch_cleanup(Block_Array &bbs); | |
| 296 // Detect implicit-null-check opportunities. Basically, find NULL checks | |
| 297 // with suitable memory ops nearby. Use the memory op to do the NULL check. | |
| 298 // I can generate a memory op if there is not one nearby. | |
| 299 void implicit_null_check(PhaseCFG *cfg, Node *proj, Node *val, int allowed_reasons); | |
| 300 | |
| 301 // Return the empty status of a block | |
| 302 enum { not_empty, empty_with_goto, completely_empty }; | |
| 303 int is_Empty() const; | |
| 304 | |
| 305 // Forward through connectors | |
| 306 Block* non_connector() { | |
| 307 Block* s = this; | |
| 308 while (s->is_connector()) { | |
| 309 s = s->_succs[0]; | |
| 310 } | |
| 311 return s; | |
| 312 } | |
| 313 | |
| 418 | 314 // Return true if b is a successor of this block |
| 315 bool has_successor(Block* b) const { | |
| 316 for (uint i = 0; i < _num_succs; i++ ) { | |
| 317 if (non_connector_successor(i) == b) { | |
| 318 return true; | |
| 319 } | |
| 320 } | |
| 321 return false; | |
| 322 } | |
| 323 | |
| 0 | 324 // Successor block, after forwarding through connectors |
| 325 Block* non_connector_successor(int i) const { | |
| 326 return _succs[i]->non_connector(); | |
| 327 } | |
| 328 | |
| 329 // Examine block's code shape to predict if it is not commonly executed. | |
| 330 bool has_uncommon_code() const; | |
| 331 | |
| 332 // Use frequency calculations and code shape to predict if the block | |
| 333 // is uncommon. | |
| 334 bool is_uncommon( Block_Array &bbs ) const; | |
| 335 | |
| 336 #ifndef PRODUCT | |
| 337 // Debugging print of basic block | |
| 3851 | 338 void dump_bidx(const Block* orig, outputStream* st = tty) const; |
| 339 void dump_pred(const Block_Array *bbs, Block* orig, outputStream* st = tty) const; | |
| 340 void dump_head( const Block_Array *bbs, outputStream* st = tty ) const; | |
| 341 void dump() const; | |
| 0 | 342 void dump( const Block_Array *bbs ) const; |
| 343 #endif | |
| 344 }; | |
| 345 | |
| 346 | |
| 347 //------------------------------PhaseCFG--------------------------------------- | |
| 348 // Build an array of Basic Block pointers, one per Node. | |
| 349 class PhaseCFG : public Phase { | |
| 3939 | 350 friend class VMStructs; |
| 0 | 351 private: |
| 352 // Build a proper looking cfg. Return count of basic blocks | |
| 353 uint build_cfg(); | |
| 354 | |
| 355 // Perform DFS search. | |
| 356 // Setup 'vertex' as DFS to vertex mapping. | |
| 357 // Setup 'semi' as vertex to DFS mapping. | |
| 358 // Set 'parent' to DFS parent. | |
| 359 uint DFS( Tarjan *tarjan ); | |
| 360 | |
| 361 // Helper function to insert a node into a block | |
| 362 void schedule_node_into_block( Node *n, Block *b ); | |
| 363 | |
| 604 | 364 void replace_block_proj_ctrl( Node *n ); |
|
601
523ded093c31
6809798: SafePointScalarObject node placed into incorrect block during GCM
kvn
parents:
470
diff
changeset
|
365 |
| 0 | 366 // Set the basic block for pinned Nodes |
| 367 void schedule_pinned_nodes( VectorSet &visited ); | |
| 368 | |
| 369 // I'll need a few machine-specific GotoNodes. Clone from this one. | |
| 370 MachNode *_goto; | |
| 371 | |
| 372 Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false); | |
| 373 void verify_anti_dependences(Block* LCA, Node* load) { | |
| 374 assert(LCA == _bbs[load->_idx], "should already be scheduled"); | |
| 375 insert_anti_dependences(LCA, load, true); | |
| 376 } | |
| 377 | |
| 378 public: | |
| 379 PhaseCFG( Arena *a, RootNode *r, Matcher &m ); | |
| 380 | |
| 381 uint _num_blocks; // Count of basic blocks | |
| 382 Block_List _blocks; // List of basic blocks | |
| 383 RootNode *_root; // Root of whole program | |
| 384 Block_Array _bbs; // Map Nodes to owning Basic Block | |
| 385 Block *_broot; // Basic block of root | |
| 386 uint _rpo_ctr; | |
| 387 CFGLoop* _root_loop; | |
| 673 | 388 float _outer_loop_freq; // Outmost loop frequency |
| 0 | 389 |
| 390 // Per node latency estimation, valid only during GCM | |
| 1685 | 391 GrowableArray<uint> *_node_latency; |
| 0 | 392 |
| 393 #ifndef PRODUCT | |
| 394 bool _trace_opto_pipelining; // tracing flag | |
| 395 #endif | |
| 396 | |
|
833
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
397 #ifdef ASSERT |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
398 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
|
399 #endif |
|
acba6af809c8
6840775: Multiple JVM crashes seen with 1.6.0_10 through 1.6.0_14
kvn
parents:
673
diff
changeset
|
400 |
| 0 | 401 // Build dominators |
| 402 void Dominators(); | |
| 403 | |
| 404 // Estimate block frequencies based on IfNode probabilities | |
| 405 void Estimate_Block_Frequency(); | |
| 406 | |
| 407 // Global Code Motion. See Click's PLDI95 paper. Place Nodes in specific | |
| 408 // basic blocks; i.e. _bbs now maps _idx for all Nodes to some Block. | |
| 409 void GlobalCodeMotion( Matcher &m, uint unique, Node_List &proj_list ); | |
| 410 | |
| 411 // Compute the (backwards) latency of a node from the uses | |
| 412 void latency_from_uses(Node *n); | |
| 413 | |
| 414 // Compute the (backwards) latency of a node from a single use | |
| 415 int latency_from_use(Node *n, const Node *def, Node *use); | |
| 416 | |
| 417 // Compute the (backwards) latency of a node from the uses of this instruction | |
| 418 void partial_latency_of_defs(Node *n); | |
| 419 | |
| 420 // Schedule Nodes early in their basic blocks. | |
| 421 bool schedule_early(VectorSet &visited, Node_List &roots); | |
| 422 | |
| 423 // For each node, find the latest block it can be scheduled into | |
| 424 // and then select the cheapest block between the latest and earliest | |
| 425 // block to place the node. | |
| 426 void schedule_late(VectorSet &visited, Node_List &stack); | |
| 427 | |
| 428 // Pick a block between early and late that is a cheaper alternative | |
| 429 // to late. Helper for schedule_late. | |
| 430 Block* hoist_to_cheaper_block(Block* LCA, Block* early, Node* self); | |
| 431 | |
| 432 // Compute the instruction global latency with a backwards walk | |
| 433 void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack); | |
| 434 | |
| 418 | 435 // Set loop alignment |
| 436 void set_loop_alignment(); | |
| 437 | |
| 0 | 438 // Remove empty basic blocks |
| 418 | 439 void remove_empty(); |
| 440 void fixup_flow(); | |
| 441 bool move_to_next(Block* bx, uint b_index); | |
| 442 void move_to_end(Block* bx, uint b_index); | |
| 443 void insert_goto_at(uint block_no, uint succ_no); | |
| 0 | 444 |
| 445 // Check for NeverBranch at block end. This needs to become a GOTO to the | |
| 446 // true target. NeverBranch are treated as a conditional branch that always | |
| 447 // goes the same direction for most of the optimizer and are used to give a | |
| 448 // fake exit path to infinite loops. At this late stage they need to turn | |
| 449 // into Goto's so that when you enter the infinite loop you indeed hang. | |
| 450 void convert_NeverBranch_to_Goto(Block *b); | |
| 451 | |
| 452 CFGLoop* create_loop_tree(); | |
| 453 | |
| 454 // Insert a node into a block, and update the _bbs | |
| 455 void insert( Block *b, uint idx, Node *n ) { | |
| 456 b->_nodes.insert( idx, n ); | |
| 457 _bbs.map( n->_idx, b ); | |
| 458 } | |
| 459 | |
| 460 #ifndef PRODUCT | |
| 461 bool trace_opto_pipelining() const { return _trace_opto_pipelining; } | |
| 462 | |
| 463 // Debugging print of CFG | |
| 464 void dump( ) const; // CFG only | |
| 465 void _dump_cfg( const Node *end, VectorSet &visited ) const; | |
| 466 void verify() const; | |
| 467 void dump_headers(); | |
| 468 #else | |
| 469 bool trace_opto_pipelining() const { return false; } | |
| 470 #endif | |
| 471 }; | |
| 472 | |
| 473 | |
| 418 | 474 //------------------------------UnionFind-------------------------------------- |
| 0 | 475 // Map Block indices to a block-index for a cfg-cover. |
| 476 // Array lookup in the optimized case. | |
| 477 class UnionFind : public ResourceObj { | |
| 478 uint _cnt, _max; | |
| 479 uint* _indices; | |
| 480 ReallocMark _nesting; // assertion check for reallocations | |
| 481 public: | |
| 482 UnionFind( uint max ); | |
| 483 void reset( uint max ); // Reset to identity map for [0..max] | |
| 484 | |
| 485 uint lookup( uint nidx ) const { | |
| 486 return _indices[nidx]; | |
| 487 } | |
| 488 uint operator[] (uint nidx) const { return lookup(nidx); } | |
| 489 | |
| 490 void map( uint from_idx, uint to_idx ) { | |
| 491 assert( from_idx < _cnt, "oob" ); | |
| 492 _indices[from_idx] = to_idx; | |
| 493 } | |
| 494 void extend( uint from_idx, uint to_idx ); | |
| 495 | |
| 496 uint Size() const { return _cnt; } | |
| 497 | |
| 498 uint Find( uint idx ) { | |
| 499 assert( idx < 65536, "Must fit into uint"); | |
| 500 uint uf_idx = lookup(idx); | |
| 501 return (uf_idx == idx) ? uf_idx : Find_compress(idx); | |
| 502 } | |
| 503 uint Find_compress( uint idx ); | |
| 504 uint Find_const( uint idx ) const; | |
| 505 void Union( uint idx1, uint idx2 ); | |
| 506 | |
| 507 }; | |
| 508 | |
| 509 //----------------------------BlockProbPair--------------------------- | |
| 510 // Ordered pair of Node*. | |
| 511 class BlockProbPair VALUE_OBJ_CLASS_SPEC { | |
| 512 protected: | |
| 513 Block* _target; // block target | |
| 514 float _prob; // probability of edge to block | |
| 515 public: | |
| 516 BlockProbPair() : _target(NULL), _prob(0.0) {} | |
| 517 BlockProbPair(Block* b, float p) : _target(b), _prob(p) {} | |
| 518 | |
| 519 Block* get_target() const { return _target; } | |
| 520 float get_prob() const { return _prob; } | |
| 521 }; | |
| 522 | |
| 523 //------------------------------CFGLoop------------------------------------------- | |
| 524 class CFGLoop : public CFGElement { | |
| 3939 | 525 friend class VMStructs; |
| 0 | 526 int _id; |
| 527 int _depth; | |
| 528 CFGLoop *_parent; // root of loop tree is the method level "pseudo" loop, it's parent is null | |
| 529 CFGLoop *_sibling; // null terminated list | |
| 530 CFGLoop *_child; // first child, use child's sibling to visit all immediately nested loops | |
| 531 GrowableArray<CFGElement*> _members; // list of members of loop | |
| 532 GrowableArray<BlockProbPair> _exits; // list of successor blocks and their probabilities | |
| 533 float _exit_prob; // probability any loop exit is taken on a single loop iteration | |
| 534 void update_succ_freq(Block* b, float freq); | |
| 535 | |
| 536 public: | |
| 537 CFGLoop(int id) : | |
| 538 CFGElement(), | |
| 539 _id(id), | |
| 540 _depth(0), | |
| 541 _parent(NULL), | |
| 542 _sibling(NULL), | |
| 543 _child(NULL), | |
| 544 _exit_prob(1.0f) {} | |
| 545 CFGLoop* parent() { return _parent; } | |
| 546 void push_pred(Block* blk, int i, Block_List& worklist, Block_Array& node_to_blk); | |
| 547 void add_member(CFGElement *s) { _members.push(s); } | |
| 548 void add_nested_loop(CFGLoop* cl); | |
| 549 Block* head() { | |
| 550 assert(_members.at(0)->is_block(), "head must be a block"); | |
| 551 Block* hd = _members.at(0)->as_Block(); | |
| 552 assert(hd->_loop == this, "just checking"); | |
| 553 assert(hd->head()->is_Loop(), "must begin with loop head node"); | |
| 554 return hd; | |
| 555 } | |
| 556 Block* backedge_block(); // Return the block on the backedge of the loop (else NULL) | |
| 557 void compute_loop_depth(int depth); | |
| 558 void compute_freq(); // compute frequency with loop assuming head freq 1.0f | |
| 559 void scale_freq(); // scale frequency by loop trip count (including outer loops) | |
| 673 | 560 float outer_loop_freq() const; // frequency of outer loop |
| 0 | 561 bool in_loop_nest(Block* b); |
| 562 float trip_count() const { return 1.0f / _exit_prob; } | |
| 563 virtual bool is_loop() { return true; } | |
| 564 int id() { return _id; } | |
| 565 | |
| 566 #ifndef PRODUCT | |
| 567 void dump( ) const; | |
| 568 void dump_tree() const; | |
| 569 #endif | |
| 570 }; | |
| 418 | 571 |
| 572 | |
| 573 //----------------------------------CFGEdge------------------------------------ | |
| 574 // A edge between two basic blocks that will be embodied by a branch or a | |
| 575 // fall-through. | |
| 576 class CFGEdge : public ResourceObj { | |
| 3939 | 577 friend class VMStructs; |
| 418 | 578 private: |
| 579 Block * _from; // Source basic block | |
| 580 Block * _to; // Destination basic block | |
| 581 float _freq; // Execution frequency (estimate) | |
| 582 int _state; | |
| 583 bool _infrequent; | |
| 584 int _from_pct; | |
| 585 int _to_pct; | |
| 586 | |
| 587 // Private accessors | |
| 588 int from_pct() const { return _from_pct; } | |
| 589 int to_pct() const { return _to_pct; } | |
| 590 int from_infrequent() const { return from_pct() < BlockLayoutMinDiamondPercentage; } | |
| 591 int to_infrequent() const { return to_pct() < BlockLayoutMinDiamondPercentage; } | |
| 592 | |
| 593 public: | |
| 594 enum { | |
| 595 open, // initial edge state; unprocessed | |
| 596 connected, // edge used to connect two traces together | |
| 597 interior // edge is interior to trace (could be backedge) | |
| 598 }; | |
| 599 | |
| 600 CFGEdge(Block *from, Block *to, float freq, int from_pct, int to_pct) : | |
| 601 _from(from), _to(to), _freq(freq), | |
| 602 _from_pct(from_pct), _to_pct(to_pct), _state(open) { | |
| 603 _infrequent = from_infrequent() || to_infrequent(); | |
| 604 } | |
| 605 | |
| 606 float freq() const { return _freq; } | |
| 607 Block* from() const { return _from; } | |
| 608 Block* to () const { return _to; } | |
| 609 int infrequent() const { return _infrequent; } | |
| 610 int state() const { return _state; } | |
| 611 | |
| 612 void set_state(int state) { _state = state; } | |
| 613 | |
| 614 #ifndef PRODUCT | |
| 615 void dump( ) const; | |
| 616 #endif | |
| 617 }; | |
| 618 | |
| 619 | |
| 620 //-----------------------------------Trace------------------------------------- | |
| 621 // An ordered list of basic blocks. | |
| 622 class Trace : public ResourceObj { | |
| 623 private: | |
| 624 uint _id; // Unique Trace id (derived from initial block) | |
| 625 Block ** _next_list; // Array mapping index to next block | |
| 626 Block ** _prev_list; // Array mapping index to previous block | |
| 627 Block * _first; // First block in the trace | |
| 628 Block * _last; // Last block in the trace | |
| 629 | |
| 630 // Return the block that follows "b" in the trace. | |
| 631 Block * next(Block *b) const { return _next_list[b->_pre_order]; } | |
| 632 void set_next(Block *b, Block *n) const { _next_list[b->_pre_order] = n; } | |
| 633 | |
| 605 | 634 // Return the block that precedes "b" in the trace. |
| 418 | 635 Block * prev(Block *b) const { return _prev_list[b->_pre_order]; } |
| 636 void set_prev(Block *b, Block *p) const { _prev_list[b->_pre_order] = p; } | |
| 637 | |
| 638 // We've discovered a loop in this trace. Reset last to be "b", and first as | |
| 639 // the block following "b | |
| 640 void break_loop_after(Block *b) { | |
| 641 _last = b; | |
| 642 _first = next(b); | |
| 643 set_prev(_first, NULL); | |
| 644 set_next(_last, NULL); | |
| 645 } | |
| 646 | |
| 647 public: | |
| 648 | |
| 649 Trace(Block *b, Block **next_list, Block **prev_list) : | |
| 650 _first(b), | |
| 651 _last(b), | |
| 652 _next_list(next_list), | |
| 653 _prev_list(prev_list), | |
| 654 _id(b->_pre_order) { | |
| 655 set_next(b, NULL); | |
| 656 set_prev(b, NULL); | |
| 657 }; | |
| 658 | |
| 659 // Return the id number | |
| 660 uint id() const { return _id; } | |
| 661 void set_id(uint id) { _id = id; } | |
| 662 | |
| 663 // Return the first block in the trace | |
| 664 Block * first_block() const { return _first; } | |
| 665 | |
| 666 // Return the last block in the trace | |
| 667 Block * last_block() const { return _last; } | |
| 668 | |
| 669 // Insert a trace in the middle of this one after b | |
| 670 void insert_after(Block *b, Trace *tr) { | |
| 671 set_next(tr->last_block(), next(b)); | |
| 672 if (next(b) != NULL) { | |
| 673 set_prev(next(b), tr->last_block()); | |
| 674 } | |
| 675 | |
| 676 set_next(b, tr->first_block()); | |
| 677 set_prev(tr->first_block(), b); | |
| 678 | |
| 679 if (b == _last) { | |
| 680 _last = tr->last_block(); | |
| 681 } | |
| 682 } | |
| 683 | |
| 684 void insert_before(Block *b, Trace *tr) { | |
| 685 Block *p = prev(b); | |
| 686 assert(p != NULL, "use append instead"); | |
| 687 insert_after(p, tr); | |
| 688 } | |
| 689 | |
| 690 // Append another trace to this one. | |
| 691 void append(Trace *tr) { | |
| 692 insert_after(_last, tr); | |
| 693 } | |
| 694 | |
| 695 // Append a block at the end of this trace | |
| 696 void append(Block *b) { | |
| 697 set_next(_last, b); | |
| 698 set_prev(b, _last); | |
| 699 _last = b; | |
| 700 } | |
| 701 | |
| 702 // Adjust the the blocks in this trace | |
| 703 void fixup_blocks(PhaseCFG &cfg); | |
| 704 bool backedge(CFGEdge *e); | |
| 705 | |
| 706 #ifndef PRODUCT | |
| 707 void dump( ) const; | |
| 708 #endif | |
| 709 }; | |
| 710 | |
| 711 //------------------------------PhaseBlockLayout------------------------------- | |
| 712 // Rearrange blocks into some canonical order, based on edges and their frequencies | |
| 713 class PhaseBlockLayout : public Phase { | |
| 3939 | 714 friend class VMStructs; |
| 418 | 715 PhaseCFG &_cfg; // Control flow graph |
| 716 | |
| 717 GrowableArray<CFGEdge *> *edges; | |
| 718 Trace **traces; | |
| 719 Block **next; | |
| 720 Block **prev; | |
| 721 UnionFind *uf; | |
| 722 | |
| 723 // Given a block, find its encompassing Trace | |
| 724 Trace * trace(Block *b) { | |
| 725 return traces[uf->Find_compress(b->_pre_order)]; | |
| 726 } | |
| 727 public: | |
| 728 PhaseBlockLayout(PhaseCFG &cfg); | |
| 729 | |
| 730 void find_edges(); | |
| 731 void grow_traces(); | |
| 732 void merge_traces(bool loose_connections); | |
| 733 void reorder_traces(int count); | |
| 734 void union_traces(Trace* from, Trace* to); | |
| 735 }; | |
| 1972 | 736 |
| 737 #endif // SHARE_VM_OPTO_BLOCK_HPP |