Re: Fix a bug in points-to solver

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Dec 2, 2013 at 6:38 PM, Xinliang David Li <davidxl@google.com> wrote:
> Points to solver has a bug that can cause complex constraints to be
> skipped leading to wrong points-to results. In the case that exposed
> the problem, there is sd constraint: x = *y which is never processed.
> 'y''s final points to set is { NULL READONLY ESCAPED NOLOCAL}, but 'x'
> points-to set is {}.
>
> What happens is before 'y'' is processed, it is merged with another
> node 'z' during cycle elimination (the complex constraints get
> transferred to 'z'), but 'z' is not marked as 'changed' so it is
> skipped in a later iteration.
>
> The attached patch fixed the problem. The problem is exposed by a
> large program built with -fprofile-generate in LIPO mode -- so there
> is no small testcase attached.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu, OK for trunk?

Hmm, the unify_nodes call in eliminate_indirect_cycles is supposed to
set the changed bit...  which in this special case (updating of complex
constraints, not the solution!) doesn't happen because unify_nodes doesn't
consider this as a change.  Which needs to change.

So, can you please update your patch to return a bool from
merge_node_constraints (any change happened?) and update changed
accordingly in unify_nodes?

Thanks,
Richard.

> Index: ChangeLog
> ===================================================================
> --- ChangeLog   (revision 205579)
> +++ ChangeLog   (working copy)
> @@ -1,3 +1,8 @@
> +2013-12-02  Xinliang David Li  <davidxl@google.com>
> +
> +       * tree-ssa-structalias.c (solve_graph): Mark rep node changed
> +       after cycle elimination.
> +
>  2013-12-01  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * config/i386/winnt.c (i386_pe_asm_named_section): Be prepared for an
> Index: tree-ssa-structalias.c
> ===================================================================
> --- tree-ssa-structalias.c      (revision 205579)
> +++ tree-ssa-structalias.c      (working copy)
> @@ -2655,8 +2655,13 @@ solve_graph (constraint_graph_t graph)
>
>           /* In certain indirect cycle cases, we may merge this
>              variable to another.  */
> -         if (eliminate_indirect_cycles (i) && find (i) != i)
> -           continue;
> +         if (eliminate_indirect_cycles (i))
> +            {
> +             unsigned int rep = find (i);
> +             bitmap_set_bit (changed, rep);
> +             if (i != rep)
> +               continue;
> +            }
>
>           /* If the node has changed, we need to process the
>              complex constraints and outgoing edges again.  */