This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for one of problems in PR28364
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Cc: zackw at panix dot com, jh at suse dot cz
- Date: Fri, 21 Jul 2006 13:48:47 +0200
- Subject: [patch] for one of problems in PR28364
Hello,
one of the problems in this PR is a weird code placement with
-no-tree-loop-ch -- we end up with the return in the middle of the loop,
causing us to jump around it each time. This turns out to be caused by
the deficiences in the updating of edge probabilities and frequencies
during tree->rtl expansion. In this particular testcase, we have
while (1)
{
...
if (cond1 || cond2)
break;
...
}
The exit is estimated to be taken with 4% probability. The if condition is expanded to
just one block, that is later split in find_many_sub_basic_blocks. To
get the probabilities of the created branches, we use
compute_outgoing_frequencies, that however estimates the frequencies on
purely local basis (using guess_outgoing_edge_probabilities), making us
believe that the two exits are taken with 50% and 30% probabilities.
This makes all the frequencies hopelessly wrong, confusing bb-reorder
and making it choose nonsensical order of blocks.
This patch tries to improve this. Instead of using
guess_outgoing_edge_probabilities, it makes us redistribute the
frequencies evenly, so the outgoing edges have ~2% probability each,
and the frequencies sum correctly.
Bootstrapped & regtested on i686 and ppc-linux.
Zdenek
PR tree-optimization/28364
* cfganal.c (pre_and_rev_post_order_compute): Add possibility to
work on reversed cfg and to ignore back edges.
* cfgbuild.c (struct split_data): New.
(make_edges, find_basic_blocks, mark_tablejump_edge,
purge_dead_tablejump_edges): Use struct split_data fields.
(init_new_bb, cmp_dfs_num, determine_probabilities_in_subblocks):
New functions.
(find_bb_boundaries): Initialize info for the new blocks.
(find_many_sub_basic_blocks): Use determine_probabilities_in_subblocks.
* tree-ssa-pre.c (compute_rvuse_and_antic_safe): Pass flags to
pre_and_rev_post_order_compute.
* var-tracking.c (vt_find_locations): Ditto.
* cfgloop.c (flow_loops_find): Ditto.
* tree-ssa-reassoc.c (init_reassoc): Ditto.
* reg-stack.c (convert_regs): Free the aux fields instead of
clearing them.
(reg_to_stack): Do not free the aux fields here.
* basic-block.h (pre_and_rev_post_order_compute): Declaration
changed.
(enum parpoc_flags): New.
Index: cfganal.c
===================================================================
*** cfganal.c (revision 115610)
--- cfganal.c (working copy)
*************** post_order_compute (int *post_order, boo
*** 717,755 ****
}
/* Compute the depth first search order and store in the array
! PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
! REV_POST_ORDER is nonzero, return the reverse completion number for each
! node. Returns the number of nodes visited. A depth first search
! tries to get as far away from the starting point as quickly as
! possible.
!
! pre_order is a really a preorder numbering of the graph.
! rev_post_order is really a reverse postorder numbering of the graph.
! */
int
pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
! bool include_entry_exit)
{
edge_iterator *stack;
int sp;
int pre_order_num = 0;
int rev_post_order_num = n_basic_blocks - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
! if (include_entry_exit)
! {
! if (pre_order)
! pre_order[pre_order_num] = ENTRY_BLOCK;
! pre_order_num++;
! if (rev_post_order)
! rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
! }
! else
rev_post_order_num -= NUM_FIXED_BLOCKS;
/* Allocate bitmap to track nodes that have been visited. */
--- 717,760 ----
}
/* Compute the depth first search order and store in the array
! PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
! reverse completion number for each node. Returns the number of
! nodes visited. A depth first search tries to get as far away
! from the starting point as quickly as possible.
!
! pre_order is a really a preorder numbering of the graph.
! rev_post_order is really a reverse postorder numbering of the graph.
!
! FLAGS affect the behavior of pre_and_rev_post_order_compute:
! if FLAGS & PARPOC_INCLUDE_ENTRY_EXIT, also entry and exit blocks are
! included in the results.
! if FLAGS & PARPOC_ALL_REACHABLE, we assert that all blocks are
! reachable from the starting point of the search.
! if FLAGS & PARPOC_REVERSE_CFG, we work on reversed cfg.
! if FLAGS & PARPOC_IGNORE_BACK_EDGES, the edges marked with EDGE_DFS_BACK
! are ignored. */
int
pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
! unsigned flags)
{
edge_iterator *stack;
+ basic_block first_unvisited;
int sp;
int pre_order_num = 0;
int rev_post_order_num = n_basic_blocks - 1;
sbitmap visited;
+ bool include_entry_exit = (flags & PARPOC_INCLUDE_ENTRY_EXIT) != 0;
+ bool all_reachable = (flags & PARPOC_ALL_REACHABLE) != 0;
+ bool reverse = (flags & PARPOC_REVERSE_CFG) != 0;
+ bool ignore_back_edges = (flags & PARPOC_IGNORE_BACK_EDGES) != 0;
+ bool first = true;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
! if (!include_entry_exit)
rev_post_order_num -= NUM_FIXED_BLOCKS;
/* Allocate bitmap to track nodes that have been visited. */
*************** pre_and_rev_post_order_compute (int *pre
*** 758,825 ****
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
! /* Push the first edge on to the stack. */
! stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
!
! while (sp)
{
! edge_iterator ei;
! basic_block src;
! basic_block dest;
! /* Look at the edge on the top of the stack. */
! ei = stack[sp - 1];
! src = ei_edge (ei)->src;
! dest = ei_edge (ei)->dest;
! /* Check if the edge destination has been visited yet. */
! if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
- /* Mark that we have visited the destination. */
- SET_BIT (visited, dest->index);
-
if (pre_order)
! pre_order[pre_order_num] = dest->index;
!
pre_order_num++;
! if (EDGE_COUNT (dest->succs) > 0)
! /* Since the DEST node has been visited for the first
! time, check its successors. */
! stack[sp++] = ei_start (dest->succs);
! else if (rev_post_order)
! /* There are no successors for the DEST node so assign
! its reverse completion number. */
! rev_post_order[rev_post_order_num--] = dest->index;
}
! else
{
! if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
! && rev_post_order)
! /* There are no more successors for the SRC node
! so assign its reverse completion number. */
! rev_post_order[rev_post_order_num--] = src->index;
! if (!ei_one_before_end_p (ei))
! ei_next (&stack[sp - 1]);
else
! sp--;
}
}
free (stack);
sbitmap_free (visited);
if (include_entry_exit)
! {
! if (pre_order)
! pre_order[pre_order_num] = EXIT_BLOCK;
! pre_order_num++;
! if (rev_post_order)
! rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
! /* The number of nodes visited should be the number of blocks. */
! gcc_assert (pre_order_num == n_basic_blocks);
! }
else
/* The number of nodes visited should be the number of blocks minus
the entry and exit blocks which are not visited here. */
--- 763,881 ----
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
! for (first_unvisited = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
! first_unvisited != NULL;
! first_unvisited = (reverse
! ? first_unvisited->prev_bb
! : first_unvisited->next_bb))
{
! if (TEST_BIT (visited, first_unvisited->index))
! continue;
! gcc_assert (first
! || !all_reachable
! /* Even if all the blocks are supposed to be reachable,
! there does not have to be an edge to the exit block. */
! || first_unvisited->index < NUM_FIXED_BLOCKS);
! first = false;
! if (include_entry_exit
! || first_unvisited->index >= NUM_FIXED_BLOCKS)
{
if (pre_order)
! pre_order[pre_order_num] = first_unvisited->index;
pre_order_num++;
+ }
+ SET_BIT (visited, first_unvisited->index);
! /* Push the first edge on to the stack, if there is any. */
! if (EDGE_COUNT (reverse
! ? first_unvisited->preds
! : first_unvisited->succs) == 0)
! {
! if (include_entry_exit
! || first_unvisited->index >= NUM_FIXED_BLOCKS)
! {
! if (rev_post_order)
! rev_post_order[rev_post_order_num] = first_unvisited->index;
! rev_post_order_num--;
! }
! continue;
}
! stack[sp++] = (reverse
! ? ei_start (first_unvisited->preds)
! : ei_start (first_unvisited->succs));
! while (sp)
{
! edge_iterator ei;
! basic_block src;
! basic_block dest;
!
! /* Look at the edge on the top of the stack. */
! ei = stack[sp - 1];
! src = reverse ? ei_edge (ei)->dest : ei_edge (ei)->src;
! dest = reverse ? ei_edge (ei)->src : ei_edge (ei)->dest;
!
! /* Check if the edge destination has been visited yet. */
! if ((!ignore_back_edges
! || (ei_edge (ei)->flags & EDGE_DFS_BACK) == 0)
! && !TEST_BIT (visited, dest->index))
! {
! /* Mark that we have visited the destination. */
! SET_BIT (visited, dest->index);
! if (include_entry_exit
! || dest->index >= NUM_FIXED_BLOCKS)
! {
! if (pre_order)
! pre_order[pre_order_num] = dest->index;
!
! pre_order_num++;
! }
!
! if (EDGE_COUNT (reverse ? dest->preds : dest->succs) > 0)
! /* Since the DEST node has been visited for the first
! time, check its successors. */
! stack[sp++] = (reverse
! ? ei_start (dest->preds)
! : ei_start (dest->succs));
! else if (include_entry_exit
! || dest->index >= NUM_FIXED_BLOCKS)
! {
! /* There are no successors for the DEST node so assign
! its reverse completion number. */
! if (rev_post_order)
! rev_post_order[rev_post_order_num] = dest->index;
! rev_post_order_num--;
! }
! }
else
! {
! if (ei_one_before_end_p (ei)
! && (include_entry_exit || src->index >= NUM_FIXED_BLOCKS))
! {
! /* There are no successors for the SRC node so assign
! its reverse completion number. */
! if (rev_post_order)
! rev_post_order[rev_post_order_num] = src->index;
! rev_post_order_num--;
! }
!
! if (!ei_one_before_end_p (ei))
! ei_next (&stack[sp - 1]);
! else
! sp--;
! }
}
}
free (stack);
sbitmap_free (visited);
+ gcc_assert (rev_post_order_num == -1);
if (include_entry_exit)
! /* The number of nodes visited should be the number of blocks. */
! gcc_assert (pre_order_num == n_basic_blocks);
else
/* The number of nodes visited should be the number of blocks minus
the entry and exit blocks which are not visited here. */
Index: cfgbuild.c
===================================================================
*** cfgbuild.c (revision 115610)
--- cfgbuild.c (working copy)
*************** enum state {
*** 229,240 ****
BLOCK_TO_SPLIT
};
! #define STATE(BB) (enum state) ((size_t) (BB)->aux)
! #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
! /* Used internally by purge_dead_tablejump_edges, ORed into state. */
! #define BLOCK_USED_BY_TABLEJUMP 32
! #define FULL_STATE(BB) ((size_t) (BB)->aux)
/* Identify the edges going out of basic blocks between MIN and MAX,
inclusive, that have their states set to BLOCK_NEW or
--- 229,258 ----
BLOCK_TO_SPLIT
};
! struct split_data
! {
! /* Subblocks of a block. */
! bitmap subblocks;
!
! /* Number of the block in the postorder numbering of the reversed cfg. */
! int dfs_num;
!
! /* State of the block. */
! enum state state;
!
! /* Frequencies of the fallthru and the branch edge. */
! unsigned fall_freq;
! unsigned branch_freq;
! /* Used internally by purge_dead_tablejump_edges. */
! unsigned used_by_tablejump : 1;
!
! /* The blocks reachable from the original one are marked here in
! determine_probabilities_in_subblocks. */
! unsigned reachable : 1;
! } test;
!
! #define INFO(BB) ((struct split_data *) (BB)->aux)
/* Identify the edges going out of basic blocks between MIN and MAX,
inclusive, that have their states set to BLOCK_NEW or
*************** make_edges (basic_block min, basic_block
*** 267,273 ****
edge e;
edge_iterator ei;
! if (STATE (bb) == BLOCK_ORIGINAL)
continue;
/* If we have an edge cache, cache edges going out of BB. */
--- 285,291 ----
edge e;
edge_iterator ei;
! if (INFO (bb)->state == BLOCK_ORIGINAL)
continue;
/* If we have an edge cache, cache edges going out of BB. */
*************** find_basic_blocks (rtx f)
*** 555,561 ****
/* Tell make_edges to examine every block for out-going edges. */
FOR_EACH_BB (bb)
! SET_STATE (bb, BLOCK_NEW);
/* Discover the edges of our cfg. */
make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
--- 573,579 ----
/* Tell make_edges to examine every block for out-going edges. */
FOR_EACH_BB (bb)
! INFO (bb)->state = BLOCK_NEW;
/* Discover the edges of our cfg. */
make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
*************** mark_tablejump_edge (rtx label)
*** 580,586 ****
if (INSN_UID (label) == 0)
return;
bb = BLOCK_FOR_INSN (label);
! SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
}
static void
--- 598,604 ----
if (INSN_UID (label) == 0)
return;
bb = BLOCK_FOR_INSN (label);
! INFO (bb)->used_by_tablejump = 1;
}
static void
*************** purge_dead_tablejump_edges (basic_block
*** 611,619 ****
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
! if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
! SET_STATE (e->dest, FULL_STATE (e->dest)
! & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
{
remove_edge (e);
--- 629,636 ----
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
! if (INFO (e->dest)->used_by_tablejump)
! INFO (e->dest)->used_by_tablejump = 0;
else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
{
remove_edge (e);
*************** purge_dead_tablejump_edges (basic_block
*** 623,628 ****
--- 640,658 ----
}
}
+ /* Initialize basic block NW split of the basic block ORIG. */
+
+ static void
+ init_new_bb (basic_block orig, basic_block nw)
+ {
+ gcc_assert (INFO (orig)->state == BLOCK_TO_SPLIT);
+ alloc_aux_for_block (nw, sizeof (struct split_data));
+
+ if (!INFO (orig)->subblocks)
+ INFO (orig)->subblocks = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (INFO (orig)->subblocks, nw->index);
+ }
+
/* Scan basic block BB for possible BB boundaries inside the block
and create new basic blocks in the progress. */
*************** find_bb_boundaries (basic_block bb)
*** 651,656 ****
--- 681,687 ----
if (code == CODE_LABEL)
{
fallthru = split_block (bb, PREV_INSN (insn));
+ init_new_bb (orig_bb, fallthru->dest);
if (flow_transfer_insn)
BB_END (bb) = flow_transfer_insn;
*************** find_bb_boundaries (basic_block bb)
*** 666,671 ****
--- 697,703 ----
if (flow_transfer_insn && inside_basic_block_p (insn))
{
fallthru = split_block (bb, PREV_INSN (insn));
+ init_new_bb (orig_bb, fallthru->dest);
BB_END (bb) = flow_transfer_insn;
bb = fallthru->dest;
remove_edge (fallthru);
*************** compute_outgoing_frequencies (basic_bloc
*** 738,743 ****
--- 770,1015 ----
/ REG_BR_PROB_BASE);
}
+ /* Comparison function for qsort, compares A and B by DFS_NUM. */
+
+ static int
+ cmp_dfs_num (const void *a, const void *b)
+ {
+ basic_block *bb_a = (basic_block *) a;
+ basic_block *bb_b = (basic_block *) b;
+
+ return (INFO (*bb_a)->dfs_num - INFO (*bb_b)->dfs_num);
+ }
+
+ #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+
+ /* Determine the probabilities in subblocks created by splitting
+ basic block BB. */
+
+ static void
+ determine_probabilities_in_subblocks (basic_block bb)
+ {
+ bitmap sub = INFO (bb)->subblocks, targets;
+ bitmap_iterator bi;
+ basic_block abb;
+ unsigned i, act_to, n;
+ edge e;
+ edge_iterator ei;
+ rtx last;
+ basic_block *top_order;
+ unsigned tgt_freq, tgt_num, prob;
+
+ if (!sub)
+ return;
+
+ /* BB was not visited yet. */
+ gcc_assert (INFO (bb)->state == BLOCK_TO_SPLIT);
+ gcc_assert (INFO (bb)->fall_freq == 0);
+ gcc_assert (INFO (bb)->branch_freq == 0);
+ gcc_assert (!INFO (bb)->reachable);
+
+ /* Verify that:
+
+ 1) the only entry to the subblocks is through BB.
+ 2) the subblocks + BB form an acyclic region, except possibly
+ for edges back to BB.
+ 3) all the blocks end with a simple jump without a REG_BR_PROB
+ note (except possibly for BB). */
+
+ if (EDGE_COUNT (bb->succs) > 2)
+ return;
+
+ if (!single_succ_p (bb)
+ && !any_condjump_p (BB_END (bb)))
+ return;
+
+ EXECUTE_IF_SET_IN_BITMAP (sub, 0, i, bi)
+ {
+ abb = BASIC_BLOCK (i);
+
+ if (EDGE_COUNT (abb->succs) > 2)
+ return;
+
+ last = BB_END (abb);
+ if (!single_succ_p (abb)
+ && !any_condjump_p (last))
+ return;
+ if (find_reg_note (last, REG_BR_PROB, 0))
+ return;
+
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (e->src != bb
+ && !bitmap_bit_p (sub, e->src->index))
+ return;
+ }
+
+ FOR_EACH_EDGE (e, ei, abb->succs)
+ {
+ if (e->dest == bb
+ || !bitmap_bit_p (sub, e->dest->index))
+ continue;
+
+ if ((e->flags & EDGE_DFS_BACK) != 0)
+ return;
+ }
+
+ /* The block was not visited yet, and it does not have subblocks. */
+ gcc_assert (INFO (abb)->subblocks == NULL);
+ gcc_assert (INFO (abb)->state == BLOCK_NEW);
+ gcc_assert (INFO (abb)->fall_freq == 0);
+ gcc_assert (INFO (abb)->branch_freq == 0);
+ gcc_assert (!INFO (abb)->reachable);
+ }
+
+ /* Get the blocks in the topological order, and find the reachable ones. */
+ n = bitmap_count_bits (sub) + 1;
+ top_order = XNEWVEC (basic_block, n);
+ top_order[0] = bb;
+ act_to = 1;
+ EXECUTE_IF_SET_IN_BITMAP (sub, 0, i, bi)
+ {
+ abb = BASIC_BLOCK (i);
+ top_order[act_to++] = abb;
+ }
+ /* Avoid including BB in the sort. If there are unreachable blocks split of
+ it, they may have smaller dfs_num. */
+ qsort (top_order + 1, n - 1, sizeof (basic_block), cmp_dfs_num);
+ gcc_assert (top_order[0] == bb);
+
+ INFO (bb)->reachable = 1;
+ for (i = 1; i < n; i++)
+ {
+ abb = top_order[i];
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (INFO (e->src)->reachable)
+ {
+ INFO (abb)->reachable = 1;
+ break;
+ }
+ }
+ }
+
+ /* Find the targets of the outgoing edges, and for each of them,
+ redistribute the frequencies. */
+ targets = BITMAP_ALLOC (NULL);
+ for (i = 0; i < n; i++)
+ {
+ abb = top_order[i];
+ FOR_EACH_EDGE (e, ei, abb->succs)
+ {
+ if (e->dest == bb
+ || !bitmap_bit_p (sub, e->dest->index))
+ bitmap_set_bit (targets, e->dest->index);
+ }
+ }
+ EXECUTE_IF_SET_IN_BITMAP (targets, 0, i, bi)
+ {
+ abb = BASIC_BLOCK (i);
+ tgt_freq = 0;
+ tgt_num = 0;
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (e->src != bb
+ && !bitmap_bit_p (sub, e->src->index))
+ continue;
+
+ tgt_freq += EDGE_FREQUENCY (e);
+ if (INFO (e->src)->reachable)
+ tgt_num++;
+ }
+
+ if (tgt_num == 0)
+ continue;
+
+ /* We assume that the same number of executions comes through each edge.
+ This is an oversimplification, but it is hard to do better. */
+ tgt_freq /= tgt_num;
+
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (e->src != bb
+ && !bitmap_bit_p (sub, e->src->index))
+ continue;
+ if (!INFO (e->src)->reachable)
+ continue;
+
+ if (e->flags & EDGE_FALLTHRU)
+ INFO (e->src)->fall_freq += tgt_freq;
+ else
+ INFO (e->src)->branch_freq += tgt_freq;
+ }
+ }
+ BITMAP_FREE (targets);
+
+ /* Propagate the frequencies back through subblocks. */
+ for (i = n - 1; i > 0; i--)
+ {
+ abb = top_order[i];
+ tgt_freq = INFO (abb)->fall_freq + INFO (abb)->branch_freq;
+ tgt_num = 0;
+
+ if (!INFO (abb)->reachable)
+ {
+ gcc_assert (tgt_freq == 0);
+ continue;
+ }
+
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (INFO (e->src)->reachable)
+ tgt_num++;
+ }
+ tgt_freq /= tgt_num;
+ FOR_EACH_EDGE (e, ei, abb->preds)
+ {
+ if (!INFO (e->src)->reachable)
+ continue;
+
+ if (e->flags & EDGE_FALLTHRU)
+ INFO (e->src)->fall_freq += tgt_freq;
+ else
+ INFO (e->src)->branch_freq += tgt_freq;
+ }
+ }
+
+ /* Use the frequencies to determine the probabilities. */
+ for (i = 0; i < n; i++)
+ {
+ abb = top_order[i];
+ if (!INFO (abb)->reachable
+ || single_succ_p (abb))
+ continue;
+
+ last = BB_END (abb);
+
+ if (abb == bb)
+ {
+ /* There may be a REG_BR_PROB note in BB. In that case,
+ we do not want to change it. */
+ if (find_reg_note (last, REG_BR_PROB, 0))
+ continue;
+ }
+ else
+ gcc_assert (!find_reg_note (last, REG_BR_PROB, 0));
+
+ tgt_freq = INFO (abb)->fall_freq + INFO (abb)->branch_freq;
+ if (tgt_freq)
+ prob = (INFO (abb)->branch_freq * REG_BR_PROB_BASE) / tgt_freq;
+ else
+ prob = REG_BR_PROB_BASE / 2;
+ REG_NOTES (last)
+ = gen_rtx_EXPR_LIST (REG_BR_PROB,
+ GEN_INT (prob), REG_NOTES (last));
+ BRANCH_EDGE (abb)->probability = prob;
+ FALLTHRU_EDGE (abb)->probability = REG_BR_PROB_BASE - prob;
+ abb->frequency = tgt_freq;
+ }
+
+ free (top_order);
+ }
+
/* Assume that some pass has inserted labels or control flow
instructions within a basic block. Split basic blocks as needed
and create edges. */
*************** void
*** 746,767 ****
find_many_sub_basic_blocks (sbitmap blocks)
{
basic_block bb, min, max;
FOR_EACH_BB (bb)
! SET_STATE (bb,
! TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
FOR_EACH_BB (bb)
! if (STATE (bb) == BLOCK_TO_SPLIT)
find_bb_boundaries (bb);
FOR_EACH_BB (bb)
! if (STATE (bb) != BLOCK_ORIGINAL)
break;
min = max = bb;
for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
! if (STATE (bb) != BLOCK_ORIGINAL)
max = bb;
/* Now re-scan and wire in all edges. This expect simple (conditional)
--- 1018,1043 ----
find_many_sub_basic_blocks (sbitmap blocks)
{
basic_block bb, min, max;
+ int *rev_post_order, ai, n;
+ unsigned freq, loop_prob;
+
+ alloc_aux_for_blocks (sizeof (struct split_data));
FOR_EACH_BB (bb)
! INFO (bb)->state = (TEST_BIT (blocks, bb->index)
! ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
FOR_EACH_BB (bb)
! if (INFO (bb)->state == BLOCK_TO_SPLIT)
find_bb_boundaries (bb);
FOR_EACH_BB (bb)
! if (INFO (bb)->state != BLOCK_ORIGINAL)
break;
min = max = bb;
for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
! if (INFO (bb)->state != BLOCK_ORIGINAL)
max = bb;
/* Now re-scan and wire in all edges. This expect simple (conditional)
*************** find_many_sub_basic_blocks (sbitmap bloc
*** 771,797 ****
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
if (profile_status != PROFILE_ABSENT)
! FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
! {
! edge e;
! edge_iterator ei;
! if (STATE (bb) == BLOCK_ORIGINAL)
! continue;
! if (STATE (bb) == BLOCK_NEW)
! {
! bb->count = 0;
! bb->frequency = 0;
! FOR_EACH_EDGE (e, ei, bb->preds)
! {
! bb->count += e->count;
! bb->frequency += EDGE_FREQUENCY (e);
! }
! }
! compute_outgoing_frequencies (bb);
! }
FOR_EACH_BB (bb)
! SET_STATE (bb, 0);
}
--- 1047,1114 ----
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
if (profile_status != PROFILE_ABSENT)
! {
! mark_dfs_back_edges ();
! rev_post_order = XNEWVEC (int, n_basic_blocks);
! n = pre_and_rev_post_order_compute (NULL, rev_post_order,
! (PARPOC_REVERSE_CFG
! | PARPOC_IGNORE_BACK_EDGES));
! gcc_assert (n == n_basic_blocks - NUM_FIXED_BLOCKS);
! for (ai = 0; ai < n; ai++)
! INFO (BASIC_BLOCK (rev_post_order[ai]))->dfs_num = n - ai - 1;
!
! /* In the first pass, we find blocks that got expanded into acyclic
! single-entry regions, and we try to be a bit clever about propagating
! the frequencies through them; we set the REG_BR_PROB notes at the
! jumps accordingly. */
! FOR_EACH_BB (bb)
! {
! if (INFO (bb)->state == BLOCK_TO_SPLIT)
! determine_probabilities_in_subblocks (bb);
! }
! /* Fix up the frequencies according to the probabilities. Process the
! blocks in post-order dfs in the reverse graph, so that the
! predecessors of block are processed before the successors. */
! for (ai = n - 1; ai >= 0; ai--)
! {
! edge e;
! edge_iterator ei;
!
! bb = BASIC_BLOCK (rev_post_order[ai]);
! if (INFO (bb)->state == BLOCK_ORIGINAL)
! continue;
!
! freq = 0;
! loop_prob = REG_BR_PROB_BASE;
! bb->count = 0;
! FOR_EACH_EDGE (e, ei, bb->preds)
! {
! bb->count += e->count;
! if (e->src == bb)
! loop_prob = REG_BR_PROB_BASE - e->probability;
! else
! freq += EDGE_FREQUENCY (e);
! }
! if (loop_prob != REG_BR_PROB_BASE)
! {
! if (!loop_prob)
! loop_prob = 1;
! freq = RDIV (REG_BR_PROB_BASE * freq, loop_prob);
! if (freq > REG_BR_PROB_BASE)
! freq = REG_BR_PROB_BASE;
! }
! bb->frequency = freq;
! compute_outgoing_frequencies (bb);
! }
! free (rev_post_order);
! }
FOR_EACH_BB (bb)
! {
! if (INFO (bb)->subblocks)
! BITMAP_FREE (INFO (bb)->subblocks);
! }
! free_aux_for_blocks ();
}
Index: tree-ssa-pre.c
===================================================================
*** tree-ssa-pre.c (revision 115610)
--- tree-ssa-pre.c (working copy)
*************** compute_rvuse_and_antic_safe (void)
*** 2036,2042 ****
RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
*/
postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
! pre_and_rev_post_order_compute (NULL, postorder, false);
changed = true;
while (changed)
--- 2036,2042 ----
RVUSE_OUT[BB] = RVUSE_GEN[BB] U (RVUSE_IN[BB] - RVUSE_KILL[BB])
*/
postorder = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
! pre_and_rev_post_order_compute (NULL, postorder, PARPOC_ALL_REACHABLE);
changed = true;
while (changed)
Index: var-tracking.c
===================================================================
*** var-tracking.c (revision 115610)
--- var-tracking.c (working copy)
*************** vt_find_locations (void)
*** 1677,1683 ****
so that the data-flow runs faster. */
rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
bb_order = XNEWVEC (int, last_basic_block);
! pre_and_rev_post_order_compute (NULL, rc_order, false);
for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
bb_order[rc_order[i]] = i;
free (rc_order);
--- 1677,1683 ----
so that the data-flow runs faster. */
rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
bb_order = XNEWVEC (int, last_basic_block);
! pre_and_rev_post_order_compute (NULL, rc_order, PARPOC_ALL_REACHABLE);
for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
bb_order[rc_order[i]] = i;
free (rc_order);
Index: cfgloop.c
===================================================================
*** cfgloop.c (revision 115610)
--- cfgloop.c (working copy)
*************** flow_loops_find (struct loops *loops)
*** 695,701 ****
natural loops will be found before inner natural loops. */
dfs_order = XNEWVEC (int, n_basic_blocks);
rc_order = XNEWVEC (int, n_basic_blocks);
! pre_and_rev_post_order_compute (dfs_order, rc_order, false);
/* Save CFG derived information to avoid recomputing it. */
loops->cfg.dfs_order = dfs_order;
--- 695,701 ----
natural loops will be found before inner natural loops. */
dfs_order = XNEWVEC (int, n_basic_blocks);
rc_order = XNEWVEC (int, n_basic_blocks);
! pre_and_rev_post_order_compute (dfs_order, rc_order, PARPOC_ALL_REACHABLE);
/* Save CFG derived information to avoid recomputing it. */
loops->cfg.dfs_order = dfs_order;
Index: reg-stack.c
===================================================================
*** reg-stack.c (revision 115610)
--- reg-stack.c (working copy)
*************** convert_regs (void)
*** 3028,3034 ****
inserted |= compensate_edges ();
! clear_aux_for_blocks ();
fixup_abnormal_edges ();
if (inserted)
--- 3028,3034 ----
inserted |= compensate_edges ();
! free_aux_for_blocks ();
fixup_abnormal_edges ();
if (inserted)
*************** reg_to_stack (void)
*** 3144,3150 ****
convert_regs ();
- free_aux_for_blocks ();
return true;
}
#endif /* STACK_REGS */
--- 3144,3149 ----
Index: basic-block.h
===================================================================
*** basic-block.h (revision 115610)
--- basic-block.h (working copy)
*************** extern void redirect_edge_pred (edge, ba
*** 505,511 ****
extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
extern void clear_bb_flags (void);
extern int post_order_compute (int *, bool);
! extern int pre_and_rev_post_order_compute (int *, int *, bool);
extern int dfs_enumerate_from (basic_block, int,
bool (*)(basic_block, void *),
basic_block *, int, void *);
--- 505,526 ----
extern basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block);
extern void clear_bb_flags (void);
extern int post_order_compute (int *, bool);
! /* Flags for pre_and_rev_post_order_compute. */
! enum parpoc_flags
! {
! /* Include also entry and exit blocks. */
! PARPOC_INCLUDE_ENTRY_EXIT = 1,
!
! /* Expect all blocks to be reachable. */
! PARPOC_ALL_REACHABLE = 2,
!
! /* Work on reversed cfg. */
! PARPOC_REVERSE_CFG = 4,
!
! /* Ignore edges marked with EDGE_DFS_BACK. */
! PARPOC_IGNORE_BACK_EDGES = 8
! };
! extern int pre_and_rev_post_order_compute (int *, int *, unsigned);
extern int dfs_enumerate_from (basic_block, int,
bool (*)(basic_block, void *),
basic_block *, int, void *);
Index: tree-ssa-reassoc.c
===================================================================
*** tree-ssa-reassoc.c (revision 115610)
--- tree-ssa-reassoc.c (working copy)
*************** init_reassoc (void)
*** 1424,1430 ****
/* Reverse RPO (Reverse Post Order) will give us something where
deeper loops come later. */
! pre_and_rev_post_order_compute (NULL, bbs, false);
bb_rank = XCNEWVEC (unsigned int, last_basic_block + 1);
operand_rank = htab_create (511, operand_entry_hash,
--- 1424,1430 ----
/* Reverse RPO (Reverse Post Order) will give us something where
deeper loops come later. */
! pre_and_rev_post_order_compute (NULL, bbs, PARPOC_ALL_REACHABLE);
bb_rank = XCNEWVEC (unsigned int, last_basic_block + 1);
operand_rank = htab_create (511, operand_entry_hash,