[tree-profiling] Fix profile updating after jump threading
Jan Hubicka
jh@suse.cz
Fri Sep 17 14:39:00 GMT 2004
Hi,
this patch should fix the problem introduced by Jeff's rewrite of jump
threading and also finally allows code sharing in between rtl and tree
implementation. In the case it will fix the perofrmance regression I am
seeing on tree-profiling branch I will commit it into mainline too and
hopefully finish the merge.
Honza
2004-09-17 Jan Hubicka <jh@suse.cz>
* basic-block.h (update_bb_profile_after_threading): Declare.
* cfg.c (update_bb_profile_after_threading): Break out from ...
* cfgcleanup.c (try_forward_edges): ... here; use it.
* tree-ssa-dom.c (thread_across_edge): Use it.
* tree-ssa-threadupdate.c (create_block_for_threading): Zero out
profile of the new BB.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.153.2.46.2.10
diff -c -3 -p -r1.153.2.46.2.10 basic-block.h
*** basic-block.h 9 Sep 2004 10:53:37 -0000 1.153.2.46.2.10
--- basic-block.h 17 Sep 2004 11:41:21 -0000
*************** extern basic_block next_dom_son (enum cd
*** 780,785 ****
--- 780,786 ----
extern edge try_redirect_by_replacing_jump (edge, basic_block, bool);
extern void break_superblocks (void);
extern void check_bb_profile (basic_block, FILE *);
+ extern void update_bb_profile_for_threading (basic_block, int, gcov_type, edge);
#include "cfghooks.h"
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.34.2.23.2.12
diff -c -3 -p -r1.34.2.23.2.12 cfg.c
*** cfg.c 12 Sep 2004 16:38:48 -0000 1.34.2.23.2.12
--- cfg.c 17 Sep 2004 11:41:21 -0000
*************** brief_dump_cfg (FILE *file)
*** 830,832 ****
--- 830,893 ----
dump_cfg_bb_info (file, bb);
}
}
+
+ /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
+ leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be
+ redirected to destiantion of TAKEN_EDGE.
+
+ This function may leave the profile inconsistent in the case TAKEN_EDGE
+ frequency or count is believed to be lower than FREQUENCY or COUNT
+ respectivly. */
+ void
+ update_bb_profile_for_threading (basic_block bb, int edge_frequency,
+ gcov_type count, edge taken_edge)
+ {
+ edge c;
+ int prob;
+
+ bb->count -= count;
+ if (bb->count < 0)
+ bb->count = 0;
+
+ /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
+ Watch for overflows. */
+ if (bb->frequency)
+ prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
+ else
+ prob = 0;
+ if (prob > taken_edge->probability)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Jump threading proved probability of edge "
+ "%i->%i too small (it is %i, should be %i).\n",
+ taken_edge->src->index, taken_edge->dest->index,
+ taken_edge->probability, prob);
+ prob = taken_edge->probability;
+ }
+
+ /* Now rescale the probabilities. */
+ taken_edge->probability -= prob;
+ prob = REG_BR_PROB_BASE - prob;
+ bb->frequency -= edge_frequency;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+ if (prob <= 0)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
+ "frequency of block should end up being 0, it is %i\n",
+ bb->index, bb->frequency);
+ bb->succ->probability = REG_BR_PROB_BASE;
+ for (c = bb->succ->succ_next; c; c = c->succ_next)
+ c->probability = 0;
+ }
+ else
+ for (c = bb->succ; c; c = c->succ_next)
+ c->probability = ((c->probability * REG_BR_PROB_BASE) / (double) prob);
+
+ if (bb != taken_edge->src)
+ abort ();
+ taken_edge->count -= count;
+ if (taken_edge->count < 0)
+ taken_edge->count = 0;
+ }
Index: cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.62.2.21.2.11
diff -c -3 -p -r1.62.2.21.2.11 cfgcleanup.c
*** cfgcleanup.c 12 Sep 2004 16:38:48 -0000 1.62.2.21.2.11
--- cfgcleanup.c 17 Sep 2004 11:41:21 -0000
*************** try_forward_edges (int mode, basic_block
*** 615,655 ****
{
edge t;
- first->count -= edge_count;
- if (first->count < 0)
- first->count = 0;
- first->frequency -= edge_frequency;
- if (first->frequency < 0)
- first->frequency = 0;
if (first->succ->succ_next)
{
- edge e;
- int prob;
-
gcc_assert (n < nthreaded_edges);
t = threaded_edges [n++];
gcc_assert (t->src == first);
! if (first->frequency)
! prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
! else
! prob = 0;
! if (prob > t->probability)
! prob = t->probability;
! t->probability -= prob;
! prob = REG_BR_PROB_BASE - prob;
! if (prob <= 0)
! {
! first->succ->probability = REG_BR_PROB_BASE;
! first->succ->succ_next->probability = 0;
! }
! else
! for (e = first->succ; e; e = e->succ_next)
! e->probability = ((e->probability * REG_BR_PROB_BASE)
! / (double) prob);
update_br_prob_note (first);
}
else
{
/* It is possible that as the result of
threading we've removed edge as it is
threaded to the fallthru edge. Avoid
--- 615,637 ----
{
edge t;
if (first->succ->succ_next)
{
gcc_assert (n < nthreaded_edges);
t = threaded_edges [n++];
gcc_assert (t->src == first);
! update_bb_profile_for_threading (first, edge_frequency,
! edge_count, t);
update_br_prob_note (first);
}
else
{
+ first->count -= edge_count;
+ if (first->count < 0)
+ first->count = 0;
+ first->frequency -= edge_frequency;
+ if (first->frequency < 0)
+ first->frequency = 0;
/* It is possible that as the result of
threading we've removed edge as it is
threaded to the fallthru edge. Avoid
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 1.1.2.135.2.13
diff -c -3 -p -r1.1.2.135.2.13 tree-ssa-dom.c
*** tree-ssa-dom.c 12 Sep 2004 16:39:37 -0000 1.1.2.135.2.13
--- tree-ssa-dom.c 17 Sep 2004 11:41:22 -0000
*************** thread_across_edge (struct dom_walk_data
*** 684,728 ****
bypass the conditional at our original destination. */
if (dest)
{
! int edge_frequency = EDGE_FREQUENCY (e);
! edge c;
! int prob;
!
! e->dest->count -= e->count;
! if (e->dest->count < 0)
! e->dest->count = 0;
!
! /* Compute the probability of TAKEN_EDGE being reached via E.
! Watch for overflows. */
! if (e->dest->frequency)
! prob = edge_frequency * REG_BR_PROB_BASE / e->dest->frequency;
! else
! prob = 0;
! if (prob > taken_edge->probability)
! prob = taken_edge->probability;
!
! /* Now rescale the probabilities. */
! taken_edge->probability -= prob;
! prob = REG_BR_PROB_BASE - prob;
! if (prob <= 0)
! {
! e->dest->succ->probability = REG_BR_PROB_BASE;
! for (c = e->dest->succ->succ_next; c; c = c->succ_next)
! c->probability = 0;
! }
! else
! for (c = e->dest->succ; c; c = c->succ_next)
! c->probability = ((c->probability * REG_BR_PROB_BASE)
! / (double) prob);
! e->dest->frequency -= edge_frequency;
! if (e->dest->frequency < 0)
! e->dest->frequency = 0;
!
! if (e->dest != taken_edge->src)
! abort ();
! taken_edge->count -= e->count;
! if (taken_edge->count < 0)
! taken_edge->count = 0;
e->aux = taken_edge;
bb_ann (e->dest)->incoming_edge_threaded = true;
}
--- 684,691 ----
bypass the conditional at our original destination. */
if (dest)
{
! update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
! e->count, taken_edge);
e->aux = taken_edge;
bb_ann (e->dest)->incoming_edge_threaded = true;
}
Index: tree-ssa-threadupdate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-threadupdate.c,v
retrieving revision 2.4.2.2
diff -c -3 -p -r2.4.2.2 tree-ssa-threadupdate.c
*** tree-ssa-threadupdate.c 12 Sep 2004 16:39:38 -0000 2.4.2.2
--- tree-ssa-threadupdate.c 17 Sep 2004 11:41:22 -0000
*************** static void
*** 172,188 ****
--- 172,196 ----
create_block_for_threading (basic_block bb, struct redirection_data *rd)
{
tree phi;
+ edge e;
/* We can use the generic block duplication code and simply remove
the stuff we do not need. */
rd->dup_block = duplicate_block (bb, NULL);
+ /* Zero out the profile, since the block is unreachable for now. */
+ rd->dup_block->frequency = 0;
+ rd->dup_block->count = 0;
+
/* The call to duplicate_block will copy everything, including the
useless COND_EXPR or SWITCH_EXPR at the end of the block. We just remove
the useless COND_EXPR or SWITCH_EXPR here rather than having a
specialized block copier. */
remove_last_stmt_and_useless_edges (rd->dup_block, rd->outgoing_edge->dest);
+ for (e = rd->dup_block->succ; e; e = e->succ_next)
+ e->count = 0;
+
/* If there are any PHI nodes at the destination of the outgoing edge
from the duplicate block, then we will need to add a new argument
to them. The argument should have the same value as the argument
More information about the Gcc-patches
mailing list