This is a first patch towards fixing PR62291 - it removes the
need of having AVAIL_OUT computed for all blocks during
compute_[partial_]antic_aux (or 'clean'). NAMEs are
available by construction and there is no need to check that
(changing the code to an assert passes bootstrap as expected).
I've noticed that sorted_array_from_bitmap_set can be sped up
so I've sneaked that change in with this patch.
Boostrapped (the version with the assert) on x86_64-unknown-linux-gnu,
bootstrap and regtest ongoing for this final variant.
The second patch (once done) will refactor insertion phase
to do a dominator walk similar to what elimination does
computing AVAIL_OUT on-the-fly (and only keeping it live
for a single block). It's a bit more complicated than
for elimination as insertion looks at a block and all its
predecessors, it's also a bit more costly as we iterate
insertion. It's also more costly because computing
AVAIL_OUT on-the-fly requires looking at all statements
which insertion currently doesn't do at all.
So I've not yet settled on a final idea how to best re-factor it,
eventually insertion and elimination can be merged (and then
still iterate(?)).
Ideas welcome ;)
Meanwhile the following patch is a strict improvement to
at least compile-time.
Thanks,
Richard.
2014-08-29 Richard Biener <rguent...@suse.de>
PR tree-optimization/62291
* tree-ssa-pre.c (sorted_array_from_bitmap_set): Reserve
exactly the vector size needed and use quick_push.
(phi_translate_1): Adjust comment.
(valid_in_sets): Remove block argument and remove pointless
checking of NAMEs.
(dependent_clean): Adjust for removal of block argument.
(clean): Likewise.
(compute_antic_aux): Likewise.
(compute_partial_antic_aux): Likewise.
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c (revision 214680)
+++ gcc/tree-ssa-pre.c (working copy)
@@ -719,8 +719,8 @@ sorted_array_from_bitmap_set (bitmap_set
bitmap_iterator bi, bj;
vec<pre_expr> result;
- /* Pre-allocate roughly enough space for the array. */
- result.create (bitmap_count_bits (&set->values));
+ /* Pre-allocate enough space for the array. */
+ result.create (bitmap_count_bits (&set->expressions));
FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
{
@@ -738,7 +738,7 @@ sorted_array_from_bitmap_set (bitmap_set
EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
{
if (bitmap_bit_p (&set->expressions, j))
- result.safe_push (expression_for_id (j));
+ result.quick_push (expression_for_id (j));
}
}
@@ -1736,8 +1736,9 @@ phi_translate_1 (pre_expr expr, bitmap_s
return get_or_alloc_expr_for_name (def);
}
- /* Otherwise return it unchanged - it will get cleaned if its
- value is not available in PREDs AVAIL_OUT set of expressions. */
+ /* Otherwise return it unchanged - it will get removed if its
+ value is not available in PREDs AVAIL_OUT set of expressions
+ by the subtraction of TMP_GEN. */
return expr;
}
@@ -1976,14 +1977,14 @@ op_valid_in_sets (bitmap_set_t set1, bit
For loads/calls, we also see if the vuse is killed in this block. */
static bool
-valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
- basic_block block)
+valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
{
switch (expr->kind)
{
case NAME:
- return bitmap_find_leader (AVAIL_OUT (block),
- get_expr_value_id (expr)) != NULL;
+ /* By construction all NAMEs are available. Non-available
+ NAMEs are removed by subtracting TMP_GEN from the sets. */
+ return true;
case NARY:
{
unsigned int i;
@@ -2021,7 +2022,7 @@ valid_in_sets (bitmap_set_t set1, bitmap
PA_IN. */
static void
-dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
+dependent_clean (bitmap_set_t set1, bitmap_set_t set2)
{
vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
pre_expr expr;
@@ -2029,7 +2030,7 @@ dependent_clean (bitmap_set_t set1, bitm
FOR_EACH_VEC_ELT (exprs, i, expr)
{
- if (!valid_in_sets (set1, set2, expr, block))
+ if (!valid_in_sets (set1, set2, expr))
bitmap_remove_from_set (set1, expr);
}
exprs.release ();
@@ -2040,7 +2041,7 @@ dependent_clean (bitmap_set_t set1, bitm
in SET. */
static void
-clean (bitmap_set_t set, basic_block block)
+clean (bitmap_set_t set)
{
vec<pre_expr> exprs = sorted_array_from_bitmap_set (set);
pre_expr expr;
@@ -2048,7 +2049,7 @@ clean (bitmap_set_t set, basic_block blo
FOR_EACH_VEC_ELT (exprs, i, expr)
{
- if (!valid_in_sets (set, NULL, expr, block))
+ if (!valid_in_sets (set, NULL, expr))
bitmap_remove_from_set (set, expr);
}
exprs.release ();
@@ -2250,7 +2251,7 @@ compute_antic_aux (basic_block block, bo
bitmap_value_insert_into_set (ANTIC_IN (block),
expression_for_id (bii));
- clean (ANTIC_IN (block), block);
+ clean (ANTIC_IN (block));
if (!bitmap_set_equal (old, ANTIC_IN (block)))
{
@@ -2405,7 +2406,7 @@ compute_partial_antic_aux (basic_block b
/* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
- dependent_clean (PA_IN (block), ANTIC_IN (block), block);
+ dependent_clean (PA_IN (block), ANTIC_IN (block));
if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
{
