1.1 --- a/src/share/vm/opto/block.hpp Thu Oct 30 17:08:48 2008 -0700
1.2 +++ b/src/share/vm/opto/block.hpp Thu Nov 06 14:59:10 2008 -0800
1.3 @@ -75,6 +75,7 @@
1.4 void insert( uint i, Block *n );
1.5 uint size() const { return _cnt; }
1.6 void reset() { _cnt = 0; }
1.7 + void print();
1.8 };
1.9
1.10
1.11 @@ -129,7 +130,11 @@
1.12 uint _rpo; // Number in reverse post order walk
1.13
1.14 virtual bool is_block() { return true; }
1.15 - float succ_prob(uint i); // return probability of i'th successor
1.16 + float succ_prob(uint i); // return probability of i'th successor
1.17 + int num_fall_throughs(); // How many fall-through candidate this block has
1.18 + void update_uncommon_branch(Block* un); // Lower branch prob to uncommon code
1.19 + bool succ_fall_through(uint i); // Is successor "i" is a fall-through candidate
1.20 + Block* lone_fall_through(); // Return lone fall-through Block or null
1.21
1.22 Block* dom_lca(Block* that); // Compute LCA in dominator tree.
1.23 #ifdef ASSERT
1.24 @@ -144,6 +149,7 @@
1.25 // Report the alignment required by this block. Must be a power of 2.
1.26 // The previous block will insert nops to get this alignment.
1.27 uint code_alignment();
1.28 + uint compute_loop_alignment();
1.29
1.30 // BLOCK_FREQUENCY is a sentinel to mark uses of constant block frequencies.
1.31 // It is currently also used to scale such frequencies relative to
1.32 @@ -184,11 +190,12 @@
1.33 int current_alignment = current_offset & max_pad;
1.34 if( current_alignment != 0 ) {
1.35 uint padding = (block_alignment-current_alignment) & max_pad;
1.36 - if( !head()->is_Loop() ||
1.37 - padding <= (uint)MaxLoopPad ||
1.38 - first_inst_size() > padding ) {
1.39 - return padding;
1.40 + if( has_loop_alignment() &&
1.41 + padding > (uint)MaxLoopPad &&
1.42 + first_inst_size() <= padding ) {
1.43 + return 0;
1.44 }
1.45 + return padding;
1.46 }
1.47 }
1.48 return 0;
1.49 @@ -202,6 +209,21 @@
1.50 void set_connector() { _connector = true; }
1.51 bool is_connector() const { return _connector; };
1.52
1.53 + // Loop_alignment will be set for blocks which are at the top of loops.
1.54 + // The block layout pass may rotate loops such that the loop head may not
1.55 + // be the sequentially first block of the loop encountered in the linear
1.56 + // list of blocks. If the layout pass is not run, loop alignment is set
1.57 + // for each block which is the head of a loop.
1.58 + uint _loop_alignment;
1.59 + void set_loop_alignment(Block *loop_top) {
1.60 + uint new_alignment = loop_top->compute_loop_alignment();
1.61 + if (new_alignment > _loop_alignment) {
1.62 + _loop_alignment = new_alignment;
1.63 + }
1.64 + }
1.65 + uint loop_alignment() const { return _loop_alignment; }
1.66 + bool has_loop_alignment() const { return loop_alignment() > 0; }
1.67 +
1.68 // Create a new Block with given head Node.
1.69 // Creates the (empty) predecessor arrays.
1.70 Block( Arena *a, Node *headnode )
1.71 @@ -219,7 +241,8 @@
1.72 _raise_LCA_mark(0),
1.73 _raise_LCA_visited(0),
1.74 _first_inst_size(999999),
1.75 - _connector(false) {
1.76 + _connector(false),
1.77 + _loop_alignment(0) {
1.78 _nodes.push(headnode);
1.79 }
1.80
1.81 @@ -275,6 +298,16 @@
1.82 return s;
1.83 }
1.84
1.85 + // Return true if b is a successor of this block
1.86 + bool has_successor(Block* b) const {
1.87 + for (uint i = 0; i < _num_succs; i++ ) {
1.88 + if (non_connector_successor(i) == b) {
1.89 + return true;
1.90 + }
1.91 + }
1.92 + return false;
1.93 + }
1.94 +
1.95 // Successor block, after forwarding through connectors
1.96 Block* non_connector_successor(int i) const {
1.97 return _succs[i]->non_connector();
1.98 @@ -319,7 +352,6 @@
1.99
1.100 // I'll need a few machine-specific GotoNodes. Clone from this one.
1.101 MachNode *_goto;
1.102 - void insert_goto_at(uint block_no, uint succ_no);
1.103
1.104 Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false);
1.105 void verify_anti_dependences(Block* LCA, Node* load) {
1.106 @@ -379,10 +411,15 @@
1.107 // Compute the instruction global latency with a backwards walk
1.108 void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack);
1.109
1.110 + // Set loop alignment
1.111 + void set_loop_alignment();
1.112 +
1.113 // Remove empty basic blocks
1.114 - void RemoveEmpty();
1.115 - bool MoveToNext(Block* bx, uint b_index);
1.116 - void MoveToEnd(Block* bx, uint b_index);
1.117 + void remove_empty();
1.118 + void fixup_flow();
1.119 + bool move_to_next(Block* bx, uint b_index);
1.120 + void move_to_end(Block* bx, uint b_index);
1.121 + void insert_goto_at(uint block_no, uint succ_no);
1.122
1.123 // Check for NeverBranch at block end. This needs to become a GOTO to the
1.124 // true target. NeverBranch are treated as a conditional branch that always
1.125 @@ -413,7 +450,7 @@
1.126 };
1.127
1.128
1.129 -//------------------------------UnionFindInfo----------------------------------
1.130 +//------------------------------UnionFind--------------------------------------
1.131 // Map Block indices to a block-index for a cfg-cover.
1.132 // Array lookup in the optimized case.
1.133 class UnionFind : public ResourceObj {
1.134 @@ -508,3 +545,166 @@
1.135 void dump_tree() const;
1.136 #endif
1.137 };
1.138 +
1.139 +
1.140 +//----------------------------------CFGEdge------------------------------------
1.141 +// A edge between two basic blocks that will be embodied by a branch or a
1.142 +// fall-through.
1.143 +class CFGEdge : public ResourceObj {
1.144 + private:
1.145 + Block * _from; // Source basic block
1.146 + Block * _to; // Destination basic block
1.147 + float _freq; // Execution frequency (estimate)
1.148 + int _state;
1.149 + bool _infrequent;
1.150 + int _from_pct;
1.151 + int _to_pct;
1.152 +
1.153 + // Private accessors
1.154 + int from_pct() const { return _from_pct; }
1.155 + int to_pct() const { return _to_pct; }
1.156 + int from_infrequent() const { return from_pct() < BlockLayoutMinDiamondPercentage; }
1.157 + int to_infrequent() const { return to_pct() < BlockLayoutMinDiamondPercentage; }
1.158 +
1.159 + public:
1.160 + enum {
1.161 + open, // initial edge state; unprocessed
1.162 + connected, // edge used to connect two traces together
1.163 + interior // edge is interior to trace (could be backedge)
1.164 + };
1.165 +
1.166 + CFGEdge(Block *from, Block *to, float freq, int from_pct, int to_pct) :
1.167 + _from(from), _to(to), _freq(freq),
1.168 + _from_pct(from_pct), _to_pct(to_pct), _state(open) {
1.169 + _infrequent = from_infrequent() || to_infrequent();
1.170 + }
1.171 +
1.172 + float freq() const { return _freq; }
1.173 + Block* from() const { return _from; }
1.174 + Block* to () const { return _to; }
1.175 + int infrequent() const { return _infrequent; }
1.176 + int state() const { return _state; }
1.177 +
1.178 + void set_state(int state) { _state = state; }
1.179 +
1.180 +#ifndef PRODUCT
1.181 + void dump( ) const;
1.182 +#endif
1.183 +};
1.184 +
1.185 +
1.186 +//-----------------------------------Trace-------------------------------------
1.187 +// An ordered list of basic blocks.
1.188 +class Trace : public ResourceObj {
1.189 + private:
1.190 + uint _id; // Unique Trace id (derived from initial block)
1.191 + Block ** _next_list; // Array mapping index to next block
1.192 + Block ** _prev_list; // Array mapping index to previous block
1.193 + Block * _first; // First block in the trace
1.194 + Block * _last; // Last block in the trace
1.195 +
1.196 + // Return the block that follows "b" in the trace.
1.197 + Block * next(Block *b) const { return _next_list[b->_pre_order]; }
1.198 + void set_next(Block *b, Block *n) const { _next_list[b->_pre_order] = n; }
1.199 +
1.200 + // Return the block that preceeds "b" in the trace.
1.201 + Block * prev(Block *b) const { return _prev_list[b->_pre_order]; }
1.202 + void set_prev(Block *b, Block *p) const { _prev_list[b->_pre_order] = p; }
1.203 +
1.204 + // We've discovered a loop in this trace. Reset last to be "b", and first as
1.205 + // the block following "b
1.206 + void break_loop_after(Block *b) {
1.207 + _last = b;
1.208 + _first = next(b);
1.209 + set_prev(_first, NULL);
1.210 + set_next(_last, NULL);
1.211 + }
1.212 +
1.213 + public:
1.214 +
1.215 + Trace(Block *b, Block **next_list, Block **prev_list) :
1.216 + _first(b),
1.217 + _last(b),
1.218 + _next_list(next_list),
1.219 + _prev_list(prev_list),
1.220 + _id(b->_pre_order) {
1.221 + set_next(b, NULL);
1.222 + set_prev(b, NULL);
1.223 + };
1.224 +
1.225 + // Return the id number
1.226 + uint id() const { return _id; }
1.227 + void set_id(uint id) { _id = id; }
1.228 +
1.229 + // Return the first block in the trace
1.230 + Block * first_block() const { return _first; }
1.231 +
1.232 + // Return the last block in the trace
1.233 + Block * last_block() const { return _last; }
1.234 +
1.235 + // Insert a trace in the middle of this one after b
1.236 + void insert_after(Block *b, Trace *tr) {
1.237 + set_next(tr->last_block(), next(b));
1.238 + if (next(b) != NULL) {
1.239 + set_prev(next(b), tr->last_block());
1.240 + }
1.241 +
1.242 + set_next(b, tr->first_block());
1.243 + set_prev(tr->first_block(), b);
1.244 +
1.245 + if (b == _last) {
1.246 + _last = tr->last_block();
1.247 + }
1.248 + }
1.249 +
1.250 + void insert_before(Block *b, Trace *tr) {
1.251 + Block *p = prev(b);
1.252 + assert(p != NULL, "use append instead");
1.253 + insert_after(p, tr);
1.254 + }
1.255 +
1.256 + // Append another trace to this one.
1.257 + void append(Trace *tr) {
1.258 + insert_after(_last, tr);
1.259 + }
1.260 +
1.261 + // Append a block at the end of this trace
1.262 + void append(Block *b) {
1.263 + set_next(_last, b);
1.264 + set_prev(b, _last);
1.265 + _last = b;
1.266 + }
1.267 +
1.268 + // Adjust the the blocks in this trace
1.269 + void fixup_blocks(PhaseCFG &cfg);
1.270 + bool backedge(CFGEdge *e);
1.271 +
1.272 +#ifndef PRODUCT
1.273 + void dump( ) const;
1.274 +#endif
1.275 +};
1.276 +
1.277 +//------------------------------PhaseBlockLayout-------------------------------
1.278 +// Rearrange blocks into some canonical order, based on edges and their frequencies
1.279 +class PhaseBlockLayout : public Phase {
1.280 + PhaseCFG &_cfg; // Control flow graph
1.281 +
1.282 + GrowableArray<CFGEdge *> *edges;
1.283 + Trace **traces;
1.284 + Block **next;
1.285 + Block **prev;
1.286 + UnionFind *uf;
1.287 +
1.288 + // Given a block, find its encompassing Trace
1.289 + Trace * trace(Block *b) {
1.290 + return traces[uf->Find_compress(b->_pre_order)];
1.291 + }
1.292 + public:
1.293 + PhaseBlockLayout(PhaseCFG &cfg);
1.294 +
1.295 + void find_edges();
1.296 + void grow_traces();
1.297 + void merge_traces(bool loose_connections);
1.298 + void reorder_traces(int count);
1.299 + void union_traces(Trace* from, Trace* to);
1.300 +};
