Re: Fix a bug in points-to solver

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

On Tue, Dec 3, 2013 at 11:54 PM, Xinliang David Li <davidxl@google.com> wrote:
> Done. Retested with the suggested change.
>
> Ok for trunk?

Ok.

Thanks,
Richard.

> thanks,
>
> David
>
> On Tue, Dec 3, 2013 at 2:13 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> 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.  */