[PATCH] Fix PR41101
Richard Guenther
rguenther@suse.de
Wed Sep 9 15:02:00 GMT 2009
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
More information about the Gcc-patches
mailing list