This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[rtlopt] bb-reorder: better loop rotating
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 4 Dec 2002 13:29:40 +0100
- Subject: [rtlopt] bb-reorder: better loop rotating
Hello,
when bb-reorder finds a loop it selects the most probable edge going out
from the hot trace of the loop. The loop is then rotated so that the
source block of the selected edge is the last block of the loop.
The previous version rotated the loop so that the loop header was placed
last.
for example, when edge to X is selected:
P P
| /
^->A is rotated to / C -> Y
^ | | |\
^ B -> X \ D \
^ | \| \
^ C -> Y A ^
^ | | ^
<- D B ->^
|
X
Bootstrapped i386.
Josef
Wed Dec 4 13:25:25 CET 2002 Josef Zlomek <zlomj9am@artax.karlin.mff.cuni,cz>
* bb-reorder.c (rotate_loop): New function.
(find_traces_1_round): Better loop rotating.
*** gcc-old/gcc/bb-reorder.c 2002-12-04 10:57:57.000000000 +0100
--- gcc/gcc/bb-reorder.c 2002-12-04 10:49:17.000000000 +0100
*************** gcov_type max_entry_count;
*** 121,126 ****
--- 121,127 ----
/* Local function prototypes. */
static void find_traces PARAMS ((int *, struct trace *));
+ static basic_block rotate_loop PARAMS ((edge, struct trace *, int));
static void mark_bb_visited PARAMS ((basic_block, int));
static void find_traces_1_round PARAMS ((int, int, gcov_type,
struct trace *, int *, int,
*************** find_traces (n_traces, traces)
*** 215,220 ****
--- 216,325 ----
}
}
+ /* Rotate loop in the tail of trace (with sequential number TRACE) beginning in
+ basic block BB. */
+
+ static basic_block
+ rotate_loop (back_edge, trace, trace_n)
+ edge back_edge;
+ struct trace *trace;
+ int trace_n;
+ {
+ basic_block bb;
+
+ /* Information about the best end (end after rotation) of the loop. */
+ basic_block best_bb = NULL;
+ edge best_edge = NULL;
+ int best_freq = -1;
+ gcov_type best_count = -1;
+ /* The best edge is preferred when its destination is not visited yet
+ or is a start block of some trace. */
+ bool is_preferred = false;
+
+ /* Find the most frequent edge that goes out from current trace. */
+ bb = back_edge->dest;
+ do
+ {
+ edge e;
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest != EXIT_BLOCK_PTR
+ && RBI (e->dest)->visited != trace_n
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX))
+ {
+ if (is_preferred)
+ {
+ /* The best edge is preferred. */
+ if (!RBI (e->dest)->visited
+ || start_of_trace[e->dest->index] >= 0)
+ {
+ /* The current edge E is also preferred. */
+ int freq = EDGE_FREQUENCY (e);
+ if (freq > best_freq || e->count > best_count)
+ {
+ best_freq = freq;
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
+ }
+ }
+ else
+ {
+ if (!RBI (e->dest)->visited
+ || start_of_trace[e->dest->index] >= 0)
+ {
+ /* The current edge E is preferred. */
+ is_preferred = true;
+ best_freq = EDGE_FREQUENCY (e);
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
+ else
+ {
+ int freq = EDGE_FREQUENCY (e);
+ if (!best_edge || freq > best_freq || e->count > best_count)
+ {
+ best_freq = freq;
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
+ }
+ }
+ }
+ bb = RBI (bb)->next;
+ }
+ while (bb != back_edge->dest);
+
+ if (best_bb)
+ {
+ /* Rotate the loop so that the BEST_EDGE goes out from the last block of
+ the trace. */
+ if (back_edge->dest == trace->first)
+ {
+ trace->first = RBI (best_bb)->next;
+ }
+ else
+ {
+ basic_block prev_bb;
+ for (prev_bb = trace->first;
+ RBI (prev_bb)->next != back_edge->dest;
+ prev_bb = RBI (prev_bb)->next)
+ ;
+ RBI (prev_bb)->next = RBI (best_bb)->next;
+ }
+ }
+ else
+ {
+ /* We have not found suitable loop tail so do no rotation. */
+ best_bb = back_edge->src;
+ }
+ RBI (best_bb)->next = NULL;
+ return best_bb;
+ }
+
/* This function marks BB that it was visited in trace number TRACE. */
static void
*************** find_traces_1_round (branch_th, exec_th,
*** 396,460 ****
{
if (RBI (best_edge->dest)->visited == *n_traces)
{
! edge other_edge;
! for (other_edge = bb->succ; other_edge;
! other_edge = other_edge->succ_next)
! if ((other_edge->flags & EDGE_CAN_FALLTHRU)
! && other_edge != best_edge)
! break;
!
! /* In the case the edge is already not a fallthru, or there
! is other edge we can make fallhtru, we are happy. */
! if (!(best_edge->flags & EDGE_FALLTHRU) || other_edge)
! ;
! else if (best_edge->dest != bb
! && best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
! {
! if (EDGE_FREQUENCY (best_edge)
! > 4 * best_edge->dest->frequency / 5)
! {
! /* The loop has at least 4 iterations. */
! edge e;
!
! /* Check whether the loop has not been rotated yet. */
! for (e = best_edge->dest->succ; e; e = e->succ_next)
! if (e->dest == RBI (best_edge->dest)->next)
! break;
! if (e)
! /* The loop has not been rotated yet. */
! {
! /* Rotate the loop. */
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file,
! "Rotating loop %d - %d\n",
! best_edge->dest->index, bb->index);
!
! /* ??? we need to find the basic block
! that is sensible end of the loop,
! not rotate to random one. */
! if (best_edge->dest == trace->first)
! {
! RBI (bb)->next = trace->first;
! trace->first = RBI (trace->first)->next;
! RBI (best_edge->dest)->next = NULL;
! bb = best_edge->dest;
! }
! else
! {
! basic_block temp;
!
! for (temp = trace->first;
! RBI (temp)->next != best_edge->dest;
! temp = RBI (temp)->next);
! RBI (temp)->next
! = RBI (best_edge->dest)->next;
! RBI (bb)->next = best_edge->dest;
! RBI (best_edge->dest)->next = NULL;
! bb = best_edge->dest;
! }
! }
! }
}
/* Terminate the trace. */
--- 501,519 ----
{
if (RBI (best_edge->dest)->visited == *n_traces)
{
! if (best_edge->dest != bb
! && best_edge->dest != ENTRY_BLOCK_PTR->next_bb
! && (EDGE_FREQUENCY (best_edge)
! > 4 * best_edge->dest->frequency / 5))
! {
! /* The loop has at least 4 iterations. */
! if (rtl_dump_file)
! {
! fprintf (rtl_dump_file, "Rotating loop %d - %d\n",
! best_edge->dest->index, bb->index);
! }
! RBI (bb)->next = best_edge->dest;
! bb = rotate_loop (best_edge, trace, *n_traces);
}
/* Terminate the trace. */