This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: even faster propagate_freq
> On Sat, Aug 18, 2001 at 03:02:41PM +0200, Jan Hubicka wrote:
> > I see why it is confusing. Perhaps the visited should be named better to
> > represent this functionality. Maybe reverse the meaning and call it tovisit?
>
> Either that or document why it wouldn't be zero at the
> very beginning of the funciton.
Hi,
this patch does mixture of both. Hope it will help to avoid confusion
in future.
Regtesting bootstrapping i586 together with the previous patch.
OK if it suceeds?
* predict.c (block_info_def): Add npredecesors, remove nvisited;
change visited to tovisit.
(propagate_freq): Use faster traversing algorithm.
(estimate_loops_at_level, estimate_bb_frequencies): Change visited
to tovisit; reverse meaning.
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.30
diff -c -3 -p -r1.30 predict.c
*** predict.c 2001/07/30 18:04:32 1.30
--- predict.c 2001/08/18 21:02:36
*************** typedef struct block_info_def
*** 572,583 ****
/* To keep queue of basic blocks to process. */
basic_block next;
! /* True if block already converted. */
! int visited:1;
! /* Number of block proceeded before adding basic block to the queue. Used
! to recognize irregular regions. */
! int nvisited;
} *block_info;
/* Similar information for edges. */
--- 572,582 ----
/* To keep queue of basic blocks to process. */
basic_block next;
! /* True if block needs to be visited in prop_freqency. */
! int tovisit:1;
! /* Number of predecesors we need to visit first. */
! int npredecesors;
} *block_info;
/* Similar information for edges. */
*************** propagate_freq (head)
*** 604,611 ****
basic_block last = bb;
edge e;
basic_block nextbb;
! int nvisited = 0;
BLOCK_INFO (head)->frequency = 1;
for (; bb; bb = nextbb)
{
--- 603,630 ----
basic_block last = bb;
edge e;
basic_block nextbb;
! int n;
+ /* For each basic block we need to visit count number of his predecesors
+ we need to visit first. */
+ for (n = 0; n < n_basic_blocks; n++)
+ {
+ basic_block bb = BASIC_BLOCK (n);
+ if (BLOCK_INFO (bb)->tovisit)
+ {
+ int count = 0;
+ for (e = bb->pred; e; e = e->pred_next)
+ if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
+ count++;
+ else if (BLOCK_INFO (e->src)->tovisit
+ && rtl_dump_file && !EDGE_INFO (e)->back_edge)
+ fprintf (rtl_dump_file,
+ "Irreducible region hit, ignoring edge to %i->%i\n",
+ e->src->index, bb->index);
+ BLOCK_INFO (bb)->npredecesors = count;
+ }
+ }
+
BLOCK_INFO (head)->frequency = 1;
for (; bb; bb = nextbb)
{
*************** propagate_freq (head)
*** 617,660 ****
/* Compute frequency of basic block. */
if (bb != head)
{
for (e = bb->pred; e; e = e->pred_next)
! if (!BLOCK_INFO (e->src)->visited && !EDGE_INFO (e)->back_edge)
! break;
!
! /* We haven't proceeded all predecessors of edge e yet.
! These may be waiting in the queue or we may hit an
! irreducible region.
!
! To avoid infinite looping on irrecudible regions, count
! the number of blocks proceeded at the time the basic
! block has been queued. In the case the number doesn't
! change, we've hit an irreducible region and we can forget
! the backward edge. This can increase the time complexity
! by the number of irreducible blocks, but in the same way
! the standard the loop does, so it should not result in a
! noticeable slowdown.
!
! Alternatively we may distinguish backward and cross edges
! in the DFS tree by the preprocessing pass and ignore the
! existence of non-loop backward edges. */
! if (e && BLOCK_INFO (bb)->nvisited != nvisited)
! {
! if (!nextbb)
! nextbb = e->dest;
! else
! BLOCK_INFO (last)->next = e->dest;
! BLOCK_INFO (last)->nvisited = nvisited;
! last = e->dest;
! continue;
! }
! else if (e && rtl_dump_file)
! fprintf (rtl_dump_file, "Irreducible region hit, ignoring edge to bb %i\n",
! bb->index);
for (e = bb->pred; e; e = e->pred_next)
if (EDGE_INFO (e)->back_edge)
cyclic_probability += EDGE_INFO (e)->back_edge_prob;
! else if (BLOCK_INFO (e->src)->visited)
frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE);
--- 636,651 ----
/* Compute frequency of basic block. */
if (bb != head)
{
+ #ifdef ENABLE_CHECKING
for (e = bb->pred; e; e = e->pred_next)
! if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
! abort ();
! #endif
for (e = bb->pred; e; e = e->pred_next)
if (EDGE_INFO (e)->back_edge)
cyclic_probability += EDGE_INFO (e)->back_edge_prob;
! else if (!(e->flags & EDGE_DFS_BACK))
frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE);
*************** propagate_freq (head)
*** 665,671 ****
BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability);
}
! BLOCK_INFO (bb)->visited = 1;
/* Compute back edge frequencies. */
for (e = bb->succ; e; e = e->succ_next)
--- 656,662 ----
BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability);
}
! BLOCK_INFO (bb)->tovisit = 0;
/* Compute back edge frequencies. */
for (e = bb->succ; e; e = e->succ_next)
*************** propagate_freq (head)
*** 676,693 ****
/* Propagate to successor blocks. */
for (e = bb->succ; e; e = e->succ_next)
! if (!EDGE_INFO (e)->back_edge
! && !BLOCK_INFO (e->dest)->visited
! && !BLOCK_INFO (e->dest)->next && e->dest != last)
{
! if (!nextbb)
! nextbb = e->dest;
! else
! BLOCK_INFO (last)->next = e->dest;
! BLOCK_INFO (last)->nvisited = nvisited;
! last = e->dest;
}
- nvisited ++;
}
}
--- 667,685 ----
/* Propagate to successor blocks. */
for (e = bb->succ; e; e = e->succ_next)
! if (!(e->flags & EDGE_DFS_BACK)
! && BLOCK_INFO (e->dest)->npredecesors)
{
! BLOCK_INFO (e->dest)->npredecesors--;
! if (!BLOCK_INFO (e->dest)->npredecesors)
! {
! if (!nextbb)
! nextbb = e->dest;
! else
! BLOCK_INFO (last)->next = e->dest;
! last = e->dest;
! }
}
}
}
*************** estimate_loops_at_level (first_loop)
*** 725,732 ****
for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
if (loop->header == l->header)
EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
! BLOCK_INFO (BASIC_BLOCK (n))->visited =
! 0);
propagate_freq (loop->header);
}
}
--- 717,724 ----
for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
if (loop->header == l->header)
EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
! BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
! );
propagate_freq (loop->header);
}
}
*************** estimate_bb_frequencies (loops)
*** 767,772 ****
--- 759,765 ----
int i;
double freq_max = 0;
+ mark_dfs_back_edges ();
if (flag_branch_probabilities)
{
counts_to_freqs ();
*************** estimate_bb_frequencies (loops)
*** 833,839 ****
else
bb = BASIC_BLOCK (i);
bb->aux = bi + i + 2;
! BLOCK_INFO (bb)->visited = 1;
for (e = bb->succ; e; e = e->succ_next)
{
e->aux = ei + edgenum, edgenum++;
--- 826,832 ----
else
bb = BASIC_BLOCK (i);
bb->aux = bi + i + 2;
! BLOCK_INFO (bb)->tovisit = 0;
for (e = bb->succ; e; e = e->succ_next)
{
e->aux = ei + edgenum, edgenum++;
*************** estimate_bb_frequencies (loops)
*** 847,855 ****
/* Now fake loop around whole function to finalize probabilities. */
for (i = 0; i < n_basic_blocks; i++)
! BLOCK_INFO (BASIC_BLOCK (i))->visited = 0;
! BLOCK_INFO (ENTRY_BLOCK_PTR)->visited = 0;
! BLOCK_INFO (EXIT_BLOCK_PTR)->visited = 0;
propagate_freq (ENTRY_BLOCK_PTR);
for (i = 0; i < n_basic_blocks; i++)
--- 840,848 ----
/* Now fake loop around whole function to finalize probabilities. */
for (i = 0; i < n_basic_blocks; i++)
! BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
! BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
! BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
propagate_freq (ENTRY_BLOCK_PTR);
for (i = 0; i < n_basic_blocks; i++)