This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[rtlopt] bb-reorder tweek
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org, gcc-pdo at atrey dot karlin dot mff dot cuni dot cz
- Date: Mon, 25 Nov 2002 23:17:16 +0100
- Subject: [rtlopt] bb-reorder tweek
Hi,
when the probabilities of outgoing edges from the last block of the
trace are the same, the longer trace is selected as the continuation.
This should help gzip (and probably other code) without PDO.
Bootstrapped i386.
Josef
Mon Nov 25 23:12:30 CET 2002 Josef Zlomek <zlomj9am@artax.karlin.mff.cuni.cz>
* bb-reorder.c (struct trace): New item "length".
(find_traces_1_round): compute the length of trace.
(connect_traces): when probalities are same, prefer longer trace as
the continuation.
Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.50.2.5
diff -c -3 -p -r1.50.2.5 bb-reorder.c
*** bb-reorder.c 23 Nov 2002 01:27:06 -0000 1.50.2.5
--- bb-reorder.c 25 Nov 2002 18:55:57 -0000
*************** struct trace
*** 110,115 ****
--- 110,118 ----
/* The round of the STC creation which this trace was found in. */
int round;
+
+ /* The length (i.e. the number of basic blocks) of the trace. */
+ int length;
};
/* Maximum frequency and count of one of the entry blocks. */
*************** find_traces_1_round (branch_th, exec_th,
*** 284,289 ****
--- 287,293 ----
trace = traces + *n_traces;
trace->first = bb;
trace->round = round;
+ trace->length = 0;
(*n_traces)++;
do
*************** find_traces_1_round (branch_th, exec_th,
*** 296,301 ****
--- 300,306 ----
best_edge = NULL;
mark_bb_visited (bb, *n_traces);
+ trace->length++;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Basic block %d was visited in trace %d\n",
*************** connect_traces (n_traces, traces)
*** 655,660 ****
--- 660,666 ----
if (!connected[t])
{
edge e, best;
+ int best_len;
connected[t] = true;
*************** connect_traces (n_traces, traces)
*** 662,677 ****
for (t2 = t; t2 > 0;)
{
best = NULL;
for (e = traces[t2].first->pred; e; e = e->pred_next)
{
if (e->src != ENTRY_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
! && e->src->index < original_last_basic_block
! && end_of_trace[e->src->index] >= 0
! && !connected[end_of_trace[e->src->index]]
! && (!best || e->probability > best->probability))
! best = e;
}
if (best)
{
--- 668,692 ----
for (t2 = t; t2 > 0;)
{
best = NULL;
+ best_len = 0;
for (e = traces[t2].first->pred; e; e = e->pred_next)
{
+ int si = e->src->index;
+
if (e->src != ENTRY_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
! && si < original_last_basic_block
! && end_of_trace[si] >= 0
! && !connected[end_of_trace[si]]
! && (!best
! || e->probability > best->probability
! || (e->probability == best->probability
! && traces[end_of_trace[si]].length > best_len)))
! {
! best = e;
! best_len = traces[end_of_trace[si]].length;
! }
}
if (best)
{
*************** connect_traces (n_traces, traces)
*** 697,712 ****
{
/* Find the continuation of the chain. */
best = NULL;
for (e = traces[t].last->succ; e; e = e->succ_next)
{
if (e->dest != EXIT_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
! && e->dest->index < original_last_basic_block
! && start_of_trace[e->dest->index] >= 0
! && !connected[start_of_trace[e->dest->index]]
! && (!best || e->probability > best->probability))
! best = e;
}
if (best)
--- 712,736 ----
{
/* Find the continuation of the chain. */
best = NULL;
+ best_len = 0;
for (e = traces[t].last->succ; e; e = e->succ_next)
{
+ int di = e->dest->index;
+
if (e->dest != EXIT_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
! && di < original_last_basic_block
! && start_of_trace[di] >= 0
! && !connected[start_of_trace[di]]
! && (!best
! || e->probability > best->probability
! || (e->probability == best->probability
! && traces[end_of_trace[di]].length > best_len)))
! {
! best = e;
! best_len = traces[end_of_trace[di]].length;
! }
}
if (best)
*************** connect_traces (n_traces, traces)
*** 727,750 ****
&& (e->flags & EDGE_CAN_FALLTHRU)
&& (EDGE_FREQUENCY (e) >= freq_threshold)
&& (e->count >= count_threshold)
! && (!best || e->probability > best->probability))
{
edge best2 = NULL;
for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
! if (e2->dest == EXIT_BLOCK_PTR
! || ((e2->flags & EDGE_CAN_FALLTHRU)
! && e2->dest->index < original_last_basic_block
! && start_of_trace[e2->dest->index] >= 0
! && !connected[start_of_trace[e2->dest->index]]
! && (EDGE_FREQUENCY (e2) >= freq_threshold)
! && (e2->count >= count_threshold)
! && (!best2
! || e2->probability > best2->probability)))
! {
! best = e;
! best2 = e2;
! next_bb = e2->dest;
! }
}
if (best)
{
--- 751,789 ----
&& (e->flags & EDGE_CAN_FALLTHRU)
&& (EDGE_FREQUENCY (e) >= freq_threshold)
&& (e->count >= count_threshold)
! && (!best
! || e->probability > best->probability))
{
edge best2 = NULL;
+ int best2_len = 0;
+
for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
! {
! int di = e2->dest->index;
!
! if (e2->dest == EXIT_BLOCK_PTR
! || ((e2->flags & EDGE_CAN_FALLTHRU)
! && di < original_last_basic_block
! && start_of_trace[di] >= 0
! && !connected[start_of_trace[di]]
! && (EDGE_FREQUENCY (e2) >= freq_threshold)
! && (e2->count >= count_threshold)
! && (!best2
! || e2->probability > best2->probability
! || (e2->probability
! == best2->probability
! && traces[end_of_trace[di]].length
! > best2_len))))
! {
! best = e;
! best2 = e2;
! if (e2->dest != EXIT_BLOCK_PTR)
! best2_len = traces[start_of_trace[di]].length;
! else
! best2_len = INT_MAX;
! next_bb = e2->dest;
! }
! }
}
if (best)
{