diff -r cd3234c89e59 -r 346bf226078e hotspot/src/share/vm/opto/block.hpp --- a/hotspot/src/share/vm/opto/block.hpp Thu Oct 30 17:08:48 2008 -0700 +++ b/hotspot/src/share/vm/opto/block.hpp Thu Nov 06 14:59:10 2008 -0800 @@ -75,6 +75,7 @@ void insert( uint i, Block *n ); uint size() const { return _cnt; } void reset() { _cnt = 0; } + void print(); }; @@ -129,7 +130,11 @@ uint _rpo; // Number in reverse post order walk virtual bool is_block() { return true; } - float succ_prob(uint i); // return probability of i'th successor + float succ_prob(uint i); // return probability of i'th successor + int num_fall_throughs(); // How many fall-through candidate this block has + void update_uncommon_branch(Block* un); // Lower branch prob to uncommon code + bool succ_fall_through(uint i); // Is successor "i" is a fall-through candidate + Block* lone_fall_through(); // Return lone fall-through Block or null Block* dom_lca(Block* that); // Compute LCA in dominator tree. #ifdef ASSERT @@ -144,6 +149,7 @@ // Report the alignment required by this block. Must be a power of 2. // The previous block will insert nops to get this alignment. uint code_alignment(); + uint compute_loop_alignment(); // BLOCK_FREQUENCY is a sentinel to mark uses of constant block frequencies. // It is currently also used to scale such frequencies relative to @@ -184,11 +190,12 @@ int current_alignment = current_offset & max_pad; if( current_alignment != 0 ) { uint padding = (block_alignment-current_alignment) & max_pad; - if( !head()->is_Loop() || - padding <= (uint)MaxLoopPad || - first_inst_size() > padding ) { - return padding; + if( has_loop_alignment() && + padding > (uint)MaxLoopPad && + first_inst_size() <= padding ) { + return 0; } + return padding; } } return 0; @@ -202,6 +209,21 @@ void set_connector() { _connector = true; } bool is_connector() const { return _connector; }; + // Loop_alignment will be set for blocks which are at the top of loops. + // The block layout pass may rotate loops such that the loop head may not + // be the sequentially first block of the loop encountered in the linear + // list of blocks. If the layout pass is not run, loop alignment is set + // for each block which is the head of a loop. + uint _loop_alignment; + void set_loop_alignment(Block *loop_top) { + uint new_alignment = loop_top->compute_loop_alignment(); + if (new_alignment > _loop_alignment) { + _loop_alignment = new_alignment; + } + } + uint loop_alignment() const { return _loop_alignment; } + bool has_loop_alignment() const { return loop_alignment() > 0; } + // Create a new Block with given head Node. // Creates the (empty) predecessor arrays. Block( Arena *a, Node *headnode ) @@ -219,7 +241,8 @@ _raise_LCA_mark(0), _raise_LCA_visited(0), _first_inst_size(999999), - _connector(false) { + _connector(false), + _loop_alignment(0) { _nodes.push(headnode); } @@ -275,6 +298,16 @@ return s; } + // Return true if b is a successor of this block + bool has_successor(Block* b) const { + for (uint i = 0; i < _num_succs; i++ ) { + if (non_connector_successor(i) == b) { + return true; + } + } + return false; + } + // Successor block, after forwarding through connectors Block* non_connector_successor(int i) const { return _succs[i]->non_connector(); @@ -319,7 +352,6 @@ // I'll need a few machine-specific GotoNodes. Clone from this one. MachNode *_goto; - void insert_goto_at(uint block_no, uint succ_no); Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false); void verify_anti_dependences(Block* LCA, Node* load) { @@ -379,10 +411,15 @@ // Compute the instruction global latency with a backwards walk void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack); + // Set loop alignment + void set_loop_alignment(); + // Remove empty basic blocks - void RemoveEmpty(); - bool MoveToNext(Block* bx, uint b_index); - void MoveToEnd(Block* bx, uint b_index); + void remove_empty(); + void fixup_flow(); + bool move_to_next(Block* bx, uint b_index); + void move_to_end(Block* bx, uint b_index); + void insert_goto_at(uint block_no, uint succ_no); // Check for NeverBranch at block end. This needs to become a GOTO to the // true target. NeverBranch are treated as a conditional branch that always @@ -413,7 +450,7 @@ }; -//------------------------------UnionFindInfo---------------------------------- +//------------------------------UnionFind-------------------------------------- // Map Block indices to a block-index for a cfg-cover. // Array lookup in the optimized case. class UnionFind : public ResourceObj { @@ -508,3 +545,166 @@ void dump_tree() const; #endif }; + + +//----------------------------------CFGEdge------------------------------------ +// A edge between two basic blocks that will be embodied by a branch or a +// fall-through. +class CFGEdge : public ResourceObj { + private: + Block * _from; // Source basic block + Block * _to; // Destination basic block + float _freq; // Execution frequency (estimate) + int _state; + bool _infrequent; + int _from_pct; + int _to_pct; + + // Private accessors + int from_pct() const { return _from_pct; } + int to_pct() const { return _to_pct; } + int from_infrequent() const { return from_pct() < BlockLayoutMinDiamondPercentage; } + int to_infrequent() const { return to_pct() < BlockLayoutMinDiamondPercentage; } + + public: + enum { + open, // initial edge state; unprocessed + connected, // edge used to connect two traces together + interior // edge is interior to trace (could be backedge) + }; + + CFGEdge(Block *from, Block *to, float freq, int from_pct, int to_pct) : + _from(from), _to(to), _freq(freq), + _from_pct(from_pct), _to_pct(to_pct), _state(open) { + _infrequent = from_infrequent() || to_infrequent(); + } + + float freq() const { return _freq; } + Block* from() const { return _from; } + Block* to () const { return _to; } + int infrequent() const { return _infrequent; } + int state() const { return _state; } + + void set_state(int state) { _state = state; } + +#ifndef PRODUCT + void dump( ) const; +#endif +}; + + +//-----------------------------------Trace------------------------------------- +// An ordered list of basic blocks. +class Trace : public ResourceObj { + private: + uint _id; // Unique Trace id (derived from initial block) + Block ** _next_list; // Array mapping index to next block + Block ** _prev_list; // Array mapping index to previous block + Block * _first; // First block in the trace + Block * _last; // Last block in the trace + + // Return the block that follows "b" in the trace. + Block * next(Block *b) const { return _next_list[b->_pre_order]; } + void set_next(Block *b, Block *n) const { _next_list[b->_pre_order] = n; } + + // Return the block that preceeds "b" in the trace. + Block * prev(Block *b) const { return _prev_list[b->_pre_order]; } + void set_prev(Block *b, Block *p) const { _prev_list[b->_pre_order] = p; } + + // We've discovered a loop in this trace. Reset last to be "b", and first as + // the block following "b + void break_loop_after(Block *b) { + _last = b; + _first = next(b); + set_prev(_first, NULL); + set_next(_last, NULL); + } + + public: + + Trace(Block *b, Block **next_list, Block **prev_list) : + _first(b), + _last(b), + _next_list(next_list), + _prev_list(prev_list), + _id(b->_pre_order) { + set_next(b, NULL); + set_prev(b, NULL); + }; + + // Return the id number + uint id() const { return _id; } + void set_id(uint id) { _id = id; } + + // Return the first block in the trace + Block * first_block() const { return _first; } + + // Return the last block in the trace + Block * last_block() const { return _last; } + + // Insert a trace in the middle of this one after b + void insert_after(Block *b, Trace *tr) { + set_next(tr->last_block(), next(b)); + if (next(b) != NULL) { + set_prev(next(b), tr->last_block()); + } + + set_next(b, tr->first_block()); + set_prev(tr->first_block(), b); + + if (b == _last) { + _last = tr->last_block(); + } + } + + void insert_before(Block *b, Trace *tr) { + Block *p = prev(b); + assert(p != NULL, "use append instead"); + insert_after(p, tr); + } + + // Append another trace to this one. + void append(Trace *tr) { + insert_after(_last, tr); + } + + // Append a block at the end of this trace + void append(Block *b) { + set_next(_last, b); + set_prev(b, _last); + _last = b; + } + + // Adjust the the blocks in this trace + void fixup_blocks(PhaseCFG &cfg); + bool backedge(CFGEdge *e); + +#ifndef PRODUCT + void dump( ) const; +#endif +}; + +//------------------------------PhaseBlockLayout------------------------------- +// Rearrange blocks into some canonical order, based on edges and their frequencies +class PhaseBlockLayout : public Phase { + PhaseCFG &_cfg; // Control flow graph + + GrowableArray *edges; + Trace **traces; + Block **next; + Block **prev; + UnionFind *uf; + + // Given a block, find its encompassing Trace + Trace * trace(Block *b) { + return traces[uf->Find_compress(b->_pre_order)]; + } + public: + PhaseBlockLayout(PhaseCFG &cfg); + + void find_edges(); + void grow_traces(); + void merge_traces(bool loose_connections); + void reorder_traces(int count); + void union_traces(Trace* from, Trace* to); +};