127 |
128 |
128 CFGLoop *_loop; // Loop to which this block belongs |
129 CFGLoop *_loop; // Loop to which this block belongs |
129 uint _rpo; // Number in reverse post order walk |
130 uint _rpo; // Number in reverse post order walk |
130 |
131 |
131 virtual bool is_block() { return true; } |
132 virtual bool is_block() { return true; } |
132 float succ_prob(uint i); // return probability of i'th successor |
133 float succ_prob(uint i); // return probability of i'th successor |
|
134 int num_fall_throughs(); // How many fall-through candidate this block has |
|
135 void update_uncommon_branch(Block* un); // Lower branch prob to uncommon code |
|
136 bool succ_fall_through(uint i); // Is successor "i" is a fall-through candidate |
|
137 Block* lone_fall_through(); // Return lone fall-through Block or null |
133 |
138 |
134 Block* dom_lca(Block* that); // Compute LCA in dominator tree. |
139 Block* dom_lca(Block* that); // Compute LCA in dominator tree. |
135 #ifdef ASSERT |
140 #ifdef ASSERT |
136 bool dominates(Block* that) { |
141 bool dominates(Block* that) { |
137 int dom_diff = this->_dom_depth - that->_dom_depth; |
142 int dom_diff = this->_dom_depth - that->_dom_depth; |
199 // Phis or MergeMems. Such blocks are discovered and marked during the |
206 // Phis or MergeMems. Such blocks are discovered and marked during the |
200 // RemoveEmpty phase, and elided during Output. |
207 // RemoveEmpty phase, and elided during Output. |
201 bool _connector; |
208 bool _connector; |
202 void set_connector() { _connector = true; } |
209 void set_connector() { _connector = true; } |
203 bool is_connector() const { return _connector; }; |
210 bool is_connector() const { return _connector; }; |
|
211 |
|
212 // Loop_alignment will be set for blocks which are at the top of loops. |
|
213 // The block layout pass may rotate loops such that the loop head may not |
|
214 // be the sequentially first block of the loop encountered in the linear |
|
215 // list of blocks. If the layout pass is not run, loop alignment is set |
|
216 // for each block which is the head of a loop. |
|
217 uint _loop_alignment; |
|
218 void set_loop_alignment(Block *loop_top) { |
|
219 uint new_alignment = loop_top->compute_loop_alignment(); |
|
220 if (new_alignment > _loop_alignment) { |
|
221 _loop_alignment = new_alignment; |
|
222 } |
|
223 } |
|
224 uint loop_alignment() const { return _loop_alignment; } |
|
225 bool has_loop_alignment() const { return loop_alignment() > 0; } |
204 |
226 |
205 // Create a new Block with given head Node. |
227 // Create a new Block with given head Node. |
206 // Creates the (empty) predecessor arrays. |
228 // Creates the (empty) predecessor arrays. |
207 Block( Arena *a, Node *headnode ) |
229 Block( Arena *a, Node *headnode ) |
208 : CFGElement(), |
230 : CFGElement(), |
317 // Set the basic block for pinned Nodes |
350 // Set the basic block for pinned Nodes |
318 void schedule_pinned_nodes( VectorSet &visited ); |
351 void schedule_pinned_nodes( VectorSet &visited ); |
319 |
352 |
320 // I'll need a few machine-specific GotoNodes. Clone from this one. |
353 // I'll need a few machine-specific GotoNodes. Clone from this one. |
321 MachNode *_goto; |
354 MachNode *_goto; |
322 void insert_goto_at(uint block_no, uint succ_no); |
|
323 |
355 |
324 Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false); |
356 Block* insert_anti_dependences(Block* LCA, Node* load, bool verify = false); |
325 void verify_anti_dependences(Block* LCA, Node* load) { |
357 void verify_anti_dependences(Block* LCA, Node* load) { |
326 assert(LCA == _bbs[load->_idx], "should already be scheduled"); |
358 assert(LCA == _bbs[load->_idx], "should already be scheduled"); |
327 insert_anti_dependences(LCA, load, true); |
359 insert_anti_dependences(LCA, load, true); |
377 Block* hoist_to_cheaper_block(Block* LCA, Block* early, Node* self); |
409 Block* hoist_to_cheaper_block(Block* LCA, Block* early, Node* self); |
378 |
410 |
379 // Compute the instruction global latency with a backwards walk |
411 // Compute the instruction global latency with a backwards walk |
380 void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack); |
412 void ComputeLatenciesBackwards(VectorSet &visited, Node_List &stack); |
381 |
413 |
|
414 // Set loop alignment |
|
415 void set_loop_alignment(); |
|
416 |
382 // Remove empty basic blocks |
417 // Remove empty basic blocks |
383 void RemoveEmpty(); |
418 void remove_empty(); |
384 bool MoveToNext(Block* bx, uint b_index); |
419 void fixup_flow(); |
385 void MoveToEnd(Block* bx, uint b_index); |
420 bool move_to_next(Block* bx, uint b_index); |
|
421 void move_to_end(Block* bx, uint b_index); |
|
422 void insert_goto_at(uint block_no, uint succ_no); |
386 |
423 |
387 // Check for NeverBranch at block end. This needs to become a GOTO to the |
424 // Check for NeverBranch at block end. This needs to become a GOTO to the |
388 // true target. NeverBranch are treated as a conditional branch that always |
425 // true target. NeverBranch are treated as a conditional branch that always |
389 // goes the same direction for most of the optimizer and are used to give a |
426 // goes the same direction for most of the optimizer and are used to give a |
390 // fake exit path to infinite loops. At this late stage they need to turn |
427 // fake exit path to infinite loops. At this late stage they need to turn |
506 #ifndef PRODUCT |
543 #ifndef PRODUCT |
507 void dump( ) const; |
544 void dump( ) const; |
508 void dump_tree() const; |
545 void dump_tree() const; |
509 #endif |
546 #endif |
510 }; |
547 }; |
|
548 |
|
549 |
|
550 //----------------------------------CFGEdge------------------------------------ |
|
551 // A edge between two basic blocks that will be embodied by a branch or a |
|
552 // fall-through. |
|
553 class CFGEdge : public ResourceObj { |
|
554 private: |
|
555 Block * _from; // Source basic block |
|
556 Block * _to; // Destination basic block |
|
557 float _freq; // Execution frequency (estimate) |
|
558 int _state; |
|
559 bool _infrequent; |
|
560 int _from_pct; |
|
561 int _to_pct; |
|
562 |
|
563 // Private accessors |
|
564 int from_pct() const { return _from_pct; } |
|
565 int to_pct() const { return _to_pct; } |
|
566 int from_infrequent() const { return from_pct() < BlockLayoutMinDiamondPercentage; } |
|
567 int to_infrequent() const { return to_pct() < BlockLayoutMinDiamondPercentage; } |
|
568 |
|
569 public: |
|
570 enum { |
|
571 open, // initial edge state; unprocessed |
|
572 connected, // edge used to connect two traces together |
|
573 interior // edge is interior to trace (could be backedge) |
|
574 }; |
|
575 |
|
576 CFGEdge(Block *from, Block *to, float freq, int from_pct, int to_pct) : |
|
577 _from(from), _to(to), _freq(freq), |
|
578 _from_pct(from_pct), _to_pct(to_pct), _state(open) { |
|
579 _infrequent = from_infrequent() || to_infrequent(); |
|
580 } |
|
581 |
|
582 float freq() const { return _freq; } |
|
583 Block* from() const { return _from; } |
|
584 Block* to () const { return _to; } |
|
585 int infrequent() const { return _infrequent; } |
|
586 int state() const { return _state; } |
|
587 |
|
588 void set_state(int state) { _state = state; } |
|
589 |
|
590 #ifndef PRODUCT |
|
591 void dump( ) const; |
|
592 #endif |
|
593 }; |
|
594 |
|
595 |
|
596 //-----------------------------------Trace------------------------------------- |
|
597 // An ordered list of basic blocks. |
|
598 class Trace : public ResourceObj { |
|
599 private: |
|
600 uint _id; // Unique Trace id (derived from initial block) |
|
601 Block ** _next_list; // Array mapping index to next block |
|
602 Block ** _prev_list; // Array mapping index to previous block |
|
603 Block * _first; // First block in the trace |
|
604 Block * _last; // Last block in the trace |
|
605 |
|
606 // Return the block that follows "b" in the trace. |
|
607 Block * next(Block *b) const { return _next_list[b->_pre_order]; } |
|
608 void set_next(Block *b, Block *n) const { _next_list[b->_pre_order] = n; } |
|
609 |
|
610 // Return the block that preceeds "b" in the trace. |
|
611 Block * prev(Block *b) const { return _prev_list[b->_pre_order]; } |
|
612 void set_prev(Block *b, Block *p) const { _prev_list[b->_pre_order] = p; } |
|
613 |
|
614 // We've discovered a loop in this trace. Reset last to be "b", and first as |
|
615 // the block following "b |
|
616 void break_loop_after(Block *b) { |
|
617 _last = b; |
|
618 _first = next(b); |
|
619 set_prev(_first, NULL); |
|
620 set_next(_last, NULL); |
|
621 } |
|
622 |
|
623 public: |
|
624 |
|
625 Trace(Block *b, Block **next_list, Block **prev_list) : |
|
626 _first(b), |
|
627 _last(b), |
|
628 _next_list(next_list), |
|
629 _prev_list(prev_list), |
|
630 _id(b->_pre_order) { |
|
631 set_next(b, NULL); |
|
632 set_prev(b, NULL); |
|
633 }; |
|
634 |
|
635 // Return the id number |
|
636 uint id() const { return _id; } |
|
637 void set_id(uint id) { _id = id; } |
|
638 |
|
639 // Return the first block in the trace |
|
640 Block * first_block() const { return _first; } |
|
641 |
|
642 // Return the last block in the trace |
|
643 Block * last_block() const { return _last; } |
|
644 |
|
645 // Insert a trace in the middle of this one after b |
|
646 void insert_after(Block *b, Trace *tr) { |
|
647 set_next(tr->last_block(), next(b)); |
|
648 if (next(b) != NULL) { |
|
649 set_prev(next(b), tr->last_block()); |
|
650 } |
|
651 |
|
652 set_next(b, tr->first_block()); |
|
653 set_prev(tr->first_block(), b); |
|
654 |
|
655 if (b == _last) { |
|
656 _last = tr->last_block(); |
|
657 } |
|
658 } |
|
659 |
|
660 void insert_before(Block *b, Trace *tr) { |
|
661 Block *p = prev(b); |
|
662 assert(p != NULL, "use append instead"); |
|
663 insert_after(p, tr); |
|
664 } |
|
665 |
|
666 // Append another trace to this one. |
|
667 void append(Trace *tr) { |
|
668 insert_after(_last, tr); |
|
669 } |
|
670 |
|
671 // Append a block at the end of this trace |
|
672 void append(Block *b) { |
|
673 set_next(_last, b); |
|
674 set_prev(b, _last); |
|
675 _last = b; |
|
676 } |
|
677 |
|
678 // Adjust the the blocks in this trace |
|
679 void fixup_blocks(PhaseCFG &cfg); |
|
680 bool backedge(CFGEdge *e); |
|
681 |
|
682 #ifndef PRODUCT |
|
683 void dump( ) const; |
|
684 #endif |
|
685 }; |
|
686 |
|
687 //------------------------------PhaseBlockLayout------------------------------- |
|
688 // Rearrange blocks into some canonical order, based on edges and their frequencies |
|
689 class PhaseBlockLayout : public Phase { |
|
690 PhaseCFG &_cfg; // Control flow graph |
|
691 |
|
692 GrowableArray<CFGEdge *> *edges; |
|
693 Trace **traces; |
|
694 Block **next; |
|
695 Block **prev; |
|
696 UnionFind *uf; |
|
697 |
|
698 // Given a block, find its encompassing Trace |
|
699 Trace * trace(Block *b) { |
|
700 return traces[uf->Find_compress(b->_pre_order)]; |
|
701 } |
|
702 public: |
|
703 PhaseBlockLayout(PhaseCFG &cfg); |
|
704 |
|
705 void find_edges(); |
|
706 void grow_traces(); |
|
707 void merge_traces(bool loose_connections); |
|
708 void reorder_traces(int count); |
|
709 void union_traces(Trace* from, Trace* to); |
|
710 }; |