Patchwork Fix a bug in points-to solver

login
register
mail settings
Submitter Xinliang David Li
Date Dec. 3, 2013, 10:54 p.m.
Message ID <CAAkRFZ+zmoGm=v2C4jsiiQgz9gKMdd1pcU5pPeJd+fJHzPU_Rw@mail.gmail.com>
Download mbox | patch
Permalink /patch/296349/
State New
Headers show

Comments

Xinliang David Li - Dec. 3, 2013, 10:54 p.m.
Done. Retested with the suggested change.

Ok for trunk?

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.  */
Richard Guenther - Dec. 4, 2013, 10:32 a.m.
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.  */

Patch

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c	(revision 205643)
+++ tree-ssa-structalias.c	(working copy)
@@ -892,14 +892,16 @@  constraint_vec_find (vec<constraint_t> v
   return found;
 }
 
-/* Union two constraint vectors, TO and FROM.  Put the result in TO.  */
+/* Union two constraint vectors, TO and FROM.  Put the result in TO. 
+   Returns true of TO set is changed.  */
 
-static void
+static bool
 constraint_set_union (vec<constraint_t> *to,
 		      vec<constraint_t> *from)
 {
   int i;
   constraint_t c;
+  bool any_change = false;
 
   FOR_EACH_VEC_ELT (*from, i, c)
     {
@@ -907,8 +909,10 @@  constraint_set_union (vec<constraint_t>
 	{
 	  unsigned int place = to->lower_bound (c, constraint_less);
 	  to->safe_insert (place, c);
+          any_change = true;
 	}
     }
+  return any_change;
 }
 
 /* Expands the solution in SET to all sub-fields of variables included.  */
@@ -1028,22 +1032,24 @@  insert_into_complex (constraint_graph_t
 
 
 /* Condense two variable nodes into a single variable node, by moving
-   all associated info from SRC to TO.  */
+   all associated info from FROM to TO. Returns true if TO node's 
+   constraint set changes after the merge.  */
 
-static void
+static bool
 merge_node_constraints (constraint_graph_t graph, unsigned int to,
 			unsigned int from)
 {
   unsigned int i;
   constraint_t c;
+  bool any_change = false;
 
   gcc_checking_assert (find (from) == to);
 
   /* Move all complex constraints from src node into to node  */
   FOR_EACH_VEC_ELT (graph->complex[from], i, c)
     {
-      /* In complex constraints for node src, we may have either
-	 a = *src, and *src = a, or an offseted constraint which are
+      /* In complex constraints for node FROM, we may have either
+	 a = *FROM, and *FROM = a, or an offseted constraint which are
 	 always added to the rhs node's constraints.  */
 
       if (c->rhs.type == DEREF)
@@ -1052,9 +1058,12 @@  merge_node_constraints (constraint_graph
 	c->lhs.var = to;
       else
 	c->rhs.var = to;
+
     }
-  constraint_set_union (&graph->complex[to], &graph->complex[from]);
+  any_change = constraint_set_union (&graph->complex[to],
+				     &graph->complex[from]);
   graph->complex[from].release ();
+  return any_change;
 }
 
 
@@ -1472,7 +1481,11 @@  unify_nodes (constraint_graph_t graph, u
     stats.unified_vars_static++;
 
   merge_graph_nodes (graph, to, from);
-  merge_node_constraints (graph, to, from);
+  if (merge_node_constraints (graph, to, from))
+    {
+      if (update_changed)
+	bitmap_set_bit (changed, to);
+    }
 
   /* Mark TO as changed if FROM was changed. If TO was already marked
      as changed, decrease the changed count.  */
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 205643)
+++ ChangeLog	(working copy)
@@ -1,3 +1,10 @@ 
+2013-12-03  Xinliang David Li  <davidxl@google.com>
+
+	* tree-ssa-structalias.c (constraint_set_union): Change return type
+	from void to bool.
+	(merge_node_constraints): Ditto.
+	(unify_nodes): Update changed set when constraints set changes.
+
 2013-12-03  Peter Bergner  <bergner@vnet.ibm.com>
 
 	* config/rs6000/htmintrin.h (_TEXASR_INSTRUCTION_FETCH_CONFLICT): Fix