Fix and speedup IDF pruning by dominator
Checks
Commit Message
When insert_updated_phi_nodes_for tries to skip pruning the IDF to
blocks dominated by the nearest common dominator of the set of
definition blocks it compares against ENTRY_BLOCK but that's never
going to be the common dominator. In fact if it ever were the code
fails to copy IDF to PRUNED_IDF, leading to wrong code.
The following fixes that by avoiding the copy and pruning from the
IDF in-place as well as using the more approprate check against
the single successor of the ENTRY_BLOCK.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
I've tried to split the patch but that runs into the pre-existing
issue, appearantly I had never tested the two patches separately
so now here's the squashed variant. Pushed.
* tree-into-ssa.cc (insert_updated_phi_nodes_for): Skip
pruning when the nearest common dominator is the successor
of ENTRY_BLOCK. Do not copy IDF but prune it directly.
---
gcc/tree-into-ssa.cc | 47 +++++++++++++++++++++++---------------------
1 file changed, 25 insertions(+), 22 deletions(-)
@@ -3233,7 +3233,7 @@ insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
{
basic_block entry;
def_blocks *db;
- bitmap idf, pruned_idf;
+ bitmap pruned_idf;
bitmap_iterator bi;
unsigned i;
@@ -3250,8 +3250,7 @@ insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
return;
/* Compute the initial iterated dominance frontier. */
- idf = compute_idf (db->def_blocks, dfs);
- pruned_idf = BITMAP_ALLOC (NULL);
+ pruned_idf = compute_idf (db->def_blocks, dfs);
if (TREE_CODE (var) == SSA_NAME)
{
@@ -3262,27 +3261,32 @@ insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
common dominator of all the definition blocks. */
entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
db->def_blocks);
- if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
- EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
- if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
- && dominated_by_p (CDI_DOMINATORS,
- BASIC_BLOCK_FOR_FN (cfun, i), entry))
- bitmap_set_bit (pruned_idf, i);
+ if (entry != single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
+ {
+ unsigned to_remove = ~0U;
+ EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
+ {
+ if (to_remove != ~0U)
+ {
+ bitmap_clear_bit (pruned_idf, to_remove);
+ to_remove = ~0U;
+ }
+ if (BASIC_BLOCK_FOR_FN (cfun, i) == entry
+ || !dominated_by_p (CDI_DOMINATORS,
+ BASIC_BLOCK_FOR_FN (cfun, i), entry))
+ to_remove = i;
+ }
+ if (to_remove != ~0U)
+ bitmap_clear_bit (pruned_idf, to_remove);
+ }
}
else
- {
- /* Otherwise, do not prune the IDF for VAR. */
- gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
- bitmap_copy (pruned_idf, idf);
- }
- }
- else
- {
- /* Otherwise, VAR is a symbol that needs to be put into SSA form
- for the first time, so we need to compute the full IDF for
- it. */
- bitmap_copy (pruned_idf, idf);
+ /* Otherwise, do not prune the IDF for VAR. */
+ gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
}
+ /* Otherwise, VAR is a symbol that needs to be put into SSA form
+ for the first time, so we need to compute the full IDF for
+ it. */
if (!bitmap_empty_p (pruned_idf))
{
@@ -3309,7 +3313,6 @@ insert_updated_phi_nodes_for (tree var, bitmap_head *dfs,
}
BITMAP_FREE (pruned_idf);
- BITMAP_FREE (idf);
}
/* Sort symbols_to_rename after their DECL_UID. */