Re: [PATCH] Fix PR41101

[Richard Guenther <rguenther at suse dot de>]

On Wed, 9 Sep 2009, Daniel Berlin wrote:

> This is fine by me. The maximal set was always slow to work with
> anyway.  I assume it's not possible to get into situations where we
> can't make progress because we've deferred all the blocks, right?

Yes - to ensure this we add fake edges to exit for infinite loops and
bbs without successors.  The exit BB is marked as visited at the
beginning.

> Anyway, thanks for doing this.
> Go ahead and commit it.

Done.

Richard.

> On Wed, Sep 9, 2009 at 10:41 AM, Richard Guenther<rguenther@suse.de> wrote:
> >
> > This fixes PR41101 - another case where the maximal set is being computed
> > as too small. ?The fix is to no longer explicitly compute it but instead
> > take it as containing all expressions. ?This means we have to defer
> > all blocks where we didn't visit at least one successor.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for trunk
> > and the 4.4 branch?
> >
> > It exposes PR41316 which is being worked on.
> >
> > Thanks,
> > Richard.
> >
> > 2009-09-09 ?Richard Guenther ?<rguenther@suse.de>
> >
> > ? ? ? ?PR tree-optimization/41101
> > ? ? ? ?* tree-ssa-pre.c (maximal_set): Remove.
> > ? ? ? ?(compute_antic_aux): Treat the maximal set as implicitly all ones.
> > ? ? ? ?Defer all blocks we didn't visit at least one successor.
> > ? ? ? ?(add_to_exp_gen): Do not add to the maximal set.
> > ? ? ? ?(make_values_for_phi): Likewise.
> > ? ? ? ?(compute_avail): Likewise.
> > ? ? ? ?(init_pre): Do not allocate the maximal set.
> > ? ? ? ?(execute_pre): Do not dump it.
> >
> > ? ? ? ?* gcc.c-torture/compile/pr41101.c: New testcase.
> >
> > Index: gcc/tree-ssa-pre.c
> > ===================================================================
> > *** gcc/tree-ssa-pre.c.orig ? ? 2009-09-09 11:36:20.000000000 +0200
> > --- gcc/tree-ssa-pre.c ?2009-09-09 11:37:06.000000000 +0200
> > *************** typedef struct bb_bitmap_sets
> > *** 401,410 ****
> > ?#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
> >
> >
> > - /* Maximal set of values, used to initialize the ANTIC problem, which
> > - ? ?is an intersection problem. ?*/
> > - static bitmap_set_t maximal_set;
> > -
> > ?/* Basic block list in postorder. ?*/
> > ?static int *postorder;
> >
> > --- 401,406 ----
> > *************** compute_antic_aux (basic_block block, bo
> > *** 2201,2249 ****
> > ? ? ?{
> > ? ? ? ?VEC(basic_block, heap) * worklist;
> > ? ? ? ?size_t i;
> > ! ? ? ? basic_block bprime, first;
> >
> > ? ? ? ?worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
> > ? ? ? ?FOR_EACH_EDGE (e, ei, block->succs)
> > - ? ? ? VEC_quick_push (basic_block, worklist, e->dest);
> > - ? ? ? first = VEC_index (basic_block, worklist, 0);
> > -
> > - ? ? ? if (phi_nodes (first))
> > ? ? ? ?{
> > ! ? ? ? ? bitmap_set_t from = ANTIC_IN (first);
> >
> > ! ? ? ? ? if (!BB_VISITED (first))
> > ! ? ? ? ? ? from = maximal_set;
> > ! ? ? ? ? phi_translate_set (ANTIC_OUT, from, block, first);
> > ? ? ? ?}
> > ? ? ? ?else
> > ! ? ? ? {
> > ! ? ? ? ? if (!BB_VISITED (first))
> > ! ? ? ? ? ? bitmap_set_copy (ANTIC_OUT, maximal_set);
> > ! ? ? ? ? else
> > ! ? ? ? ? ? bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
> > ! ? ? ? }
> >
> > ! ? ? ? for (i = 1; VEC_iterate (basic_block, worklist, i, bprime); i++)
> > ? ? ? ?{
> > ? ? ? ? ?if (phi_nodes (bprime))
> > ? ? ? ? ? ?{
> > ? ? ? ? ? ? ?bitmap_set_t tmp = bitmap_set_new ();
> > ! ? ? ? ? ? ? bitmap_set_t from = ANTIC_IN (bprime);
> > !
> > ! ? ? ? ? ? ? if (!BB_VISITED (bprime))
> > ! ? ? ? ? ? ? ? from = maximal_set;
> > ! ? ? ? ? ? ? phi_translate_set (tmp, from, block, bprime);
> > ? ? ? ? ? ? ?bitmap_set_and (ANTIC_OUT, tmp);
> > ? ? ? ? ? ? ?bitmap_set_free (tmp);
> > ? ? ? ? ? ?}
> > ? ? ? ? ?else
> > ! ? ? ? ? ? {
> > ! ? ? ? ? ? ? if (!BB_VISITED (bprime))
> > ! ? ? ? ? ? ? ? bitmap_set_and (ANTIC_OUT, maximal_set);
> > ! ? ? ? ? ? ? else
> > ! ? ? ? ? ? ? ? bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
> > ! ? ? ? ? ? }
> > ? ? ? ?}
> > ? ? ? ?VEC_free (basic_block, heap, worklist);
> > ? ? ?}
> > --- 2197,2241 ----
> > ? ? ?{
> > ? ? ? ?VEC(basic_block, heap) * worklist;
> > ? ? ? ?size_t i;
> > ! ? ? ? basic_block bprime, first = NULL;
> >
> > ? ? ? ?worklist = VEC_alloc (basic_block, heap, EDGE_COUNT (block->succs));
> > ? ? ? ?FOR_EACH_EDGE (e, ei, block->succs)
> > ? ? ? ?{
> > ! ? ? ? ? if (!first
> > ! ? ? ? ? ? ? && BB_VISITED (e->dest))
> > ! ? ? ? ? ? first = e->dest;
> > ! ? ? ? ? else if (BB_VISITED (e->dest))
> > ! ? ? ? ? ? VEC_quick_push (basic_block, worklist, e->dest);
> > ! ? ? ? }
> >
> > ! ? ? ? /* Of multiple successors we have to have visited one already. ?*/
> > ! ? ? ? if (!first)
> > ! ? ? ? {
> > ! ? ? ? ? SET_BIT (changed_blocks, block->index);
> > ! ? ? ? ? BB_VISITED (block) = 0;
> > ! ? ? ? ? BB_DEFERRED (block) = 1;
> > ! ? ? ? ? changed = true;
> > ! ? ? ? ? VEC_free (basic_block, heap, worklist);
> > ! ? ? ? ? goto maybe_dump_sets;
> > ? ? ? ?}
> > +
> > + ? ? ? if (phi_nodes (first))
> > + ? ? ? phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
> > ? ? ? ?else
> > ! ? ? ? bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
> >
> > ! ? ? ? for (i = 0; VEC_iterate (basic_block, worklist, i, bprime); i++)
> > ? ? ? ?{
> > ? ? ? ? ?if (phi_nodes (bprime))
> > ? ? ? ? ? ?{
> > ? ? ? ? ? ? ?bitmap_set_t tmp = bitmap_set_new ();
> > ! ? ? ? ? ? ? phi_translate_set (tmp, ANTIC_IN (bprime), block, bprime);
> > ? ? ? ? ? ? ?bitmap_set_and (ANTIC_OUT, tmp);
> > ? ? ? ? ? ? ?bitmap_set_free (tmp);
> > ? ? ? ? ? ?}
> > ? ? ? ? ?else
> > ! ? ? ? ? ? bitmap_set_and (ANTIC_OUT, ANTIC_IN (bprime));
> > ? ? ? ?}
> > ? ? ? ?VEC_free (basic_block, heap, worklist);
> > ? ? ?}
> > *************** add_to_exp_gen (basic_block block, tree
> > *** 3711,3717 ****
> > ? ? ? ?return;
> > ? ? ? ?result = get_or_alloc_expr_for_name (op);
> > ? ? ? ?bitmap_value_insert_into_set (EXP_GEN (block), result);
> > - ? ? ? bitmap_value_insert_into_set (maximal_set, result);
> > ? ? ?}
> > ?}
> >
> > --- 3703,3708 ----
> > *************** make_values_for_phi (gimple phi, basic_b
> > *** 3740,3746 ****
> > ? ? ? ? ? ? ? ?{
> > ? ? ? ? ? ? ? ? ?e = get_or_alloc_expr_for_name (arg);
> > ? ? ? ? ? ? ? ? ?add_to_value (get_expr_value_id (e), e);
> > - ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (maximal_set, e);
> > ? ? ? ? ? ? ? ?}
> > ? ? ? ? ? ?}
> > ? ? ? ?}
> > --- 3731,3736 ----
> > *************** compute_avail (void)
> > *** 3781,3790 ****
> > ? ? ? ?e = get_or_alloc_expr_for_name (name);
> > ? ? ? ?add_to_value (get_expr_value_id (e), e);
> > ? ? ? ?if (!in_fre)
> > ! ? ? ? {
> > ! ? ? ? ? bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
> > ! ? ? ? ? bitmap_value_insert_into_set (maximal_set, e);
> > ! ? ? ? }
> > ? ? ? ?bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
> > ? ? ?}
> >
> > --- 3771,3777 ----
> > ? ? ? ?e = get_or_alloc_expr_for_name (name);
> > ? ? ? ?add_to_value (get_expr_value_id (e), e);
> > ? ? ? ?if (!in_fre)
> > ! ? ? ? bitmap_insert_into_set (TMP_GEN (ENTRY_BLOCK_PTR), e);
> > ? ? ? ?bitmap_value_insert_into_set (AVAIL_OUT (ENTRY_BLOCK_PTR), e);
> > ? ? ?}
> >
> > *************** compute_avail (void)
> > *** 3888,3898 ****
> > ? ? ? ? ? ? ? ?get_or_alloc_expression_id (result);
> > ? ? ? ? ? ? ? ?add_to_value (get_expr_value_id (result), result);
> > ? ? ? ? ? ? ? ?if (!in_fre)
> > ! ? ? ? ? ? ? ? ? {
> > ! ? ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (EXP_GEN (block),
> > ! ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? result);
> > ! ? ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (maximal_set, result);
> > ! ? ? ? ? ? ? ? ? }
> > ? ? ? ? ? ? ? ?continue;
> > ? ? ? ? ? ? ?}
> >
> > --- 3875,3881 ----
> > ? ? ? ? ? ? ? ?get_or_alloc_expression_id (result);
> > ? ? ? ? ? ? ? ?add_to_value (get_expr_value_id (result), result);
> > ? ? ? ? ? ? ? ?if (!in_fre)
> > ! ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (EXP_GEN (block), result);
> > ? ? ? ? ? ? ? ?continue;
> > ? ? ? ? ? ? ?}
> >
> > *************** compute_avail (void)
> > *** 3974,3983 ****
> > ? ? ? ? ? ? ? ?get_or_alloc_expression_id (result);
> > ? ? ? ? ? ? ? ?add_to_value (get_expr_value_id (result), result);
> > ? ? ? ? ? ? ? ?if (!in_fre)
> > ! ? ? ? ? ? ? ? ? {
> > ! ? ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (EXP_GEN (block), result);
> > ! ? ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (maximal_set, result);
> > ! ? ? ? ? ? ? ? ? }
> >
> > ? ? ? ? ? ? ? ?continue;
> > ? ? ? ? ? ? ?}
> > --- 3957,3963 ----
> > ? ? ? ? ? ? ? ?get_or_alloc_expression_id (result);
> > ? ? ? ? ? ? ? ?add_to_value (get_expr_value_id (result), result);
> > ? ? ? ? ? ? ? ?if (!in_fre)
> > ! ? ? ? ? ? ? ? ? bitmap_value_insert_into_set (EXP_GEN (block), result);
> >
> > ? ? ? ? ? ? ? ?continue;
> > ? ? ? ? ? ? ?}
> > *************** init_pre (bool do_fre)
> > *** 4515,4521 ****
> > ? ? ? ?TMP_GEN (bb) = bitmap_set_new ();
> > ? ? ? ?AVAIL_OUT (bb) = bitmap_set_new ();
> > ? ? ?}
> > - ? maximal_set = in_fre ? NULL : bitmap_set_new ();
> >
> > ? ?need_eh_cleanup = BITMAP_ALLOC (NULL);
> > ?}
> > --- 4495,4500 ----
> > *************** execute_pre (bool do_fre ATTRIBUTE_UNUSE
> > *** 4601,4608 ****
> > ? ? ? ? ?print_bitmap_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
> > ? ? ? ? ?print_bitmap_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
> > ? ? ? ?}
> > -
> > - ? ? ? print_bitmap_set (dump_file, maximal_set, "maximal", 0);
> > ? ? ?}
> >
> > ? ?/* Insert can get quite slow on an incredibly large number of basic
> > --- 4580,4585 ----
> > Index: gcc/testsuite/gcc.c-torture/compile/pr41101.c
> > ===================================================================
> > *** /dev/null ? 1970-01-01 00:00:00.000000000 +0000
> > --- gcc/testsuite/gcc.c-torture/compile/pr41101.c ? ? ? 2009-09-09 11:36:27.000000000 +0200
> > ***************
> > *** 0 ****
> > --- 1,19 ----
> > + int func(int);
> > +
> > + void
> > + bug(int* x, int* y, unsigned long int N)
> > + {
> > + ? unsigned long int i;
> > + ? int* t;
> > +
> > + ? while (1)
> > + ? ? {
> > + ? ? ? for (i=1; i<=N; i++)
> > + ? ? ? {
> > + ? ? ? ? y[i] = func(x[i] - x[1]);
> > + ? ? ? ? if (y[i])
> > + ? ? ? ? ? return;
> > + ? ? ? }
> > + ? ? ? t=x; x=y; y=t;
> > + ? ? }
> > + }
> >
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex