[Bug tree-optimization/29156] New: Misscompilation due to alias analysis

[Bug tree-optimization/29156] New: Misscompilation due to alias analysis

[rakdver at gcc dot gnu dot org]

The testcase below gets misscompiled at -O2.

The alias info looks this way:

Dereferenced pointers

xa, UID 1527, struct test1 *, symbol memory tag: SMT.4, default def: xa_4
xb, UID 1528, struct test2 *, symbol memory tag: SMT.5, default def: xb_3

Symbol memory tags

SMT.4, UID 1547, struct test1, is addressable, is global, call clobbered, may
aliases: { global }
SMT.5, UID 1548, struct test2, is addressable, is global, call clobbered, may
aliases: { global }

The alias sets for SMT.4 and SMT.5 intersect, so everything looks OK here. 
However, access_can_touch_variable (correctly) determines that the dereferences
of xa and xb cannot touch "global"; hence we create the following virual
operands:

  #   SMT.5_8 = V_MAY_DEF <SMT.5_7>;
  xb_3->sub.a = 1;
  #   SMT.4_10 = V_MAY_DEF <SMT.4_9>;
  xa_4->a = 8;
  #   VUSE <SMT.5_8>;
  D.1531_5 = xb_3->sub.a;

The accesses to xa and xb appear to be independent, which leads to a
misscompilation.

struct test1
{
  int a;
  int b;
};
struct test2
{
  float d;
  struct test1 sub;
};

int global;

int bla(struct test1 *xa, struct test2 *xb)
{
  global = 1;
  xb->sub.a = 1;
  xa->a = 8;
  return xb->sub.a;
}

int main(void)
{
  struct test2 pom;

  if (bla (&pom.sub, &pom) != 8)
    abort ();

  return 0;
}


-- 
           Summary: Misscompilation due to alias analysis
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rakdver at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux
  GCC host triplet: i686-pc-linux
GCC target triplet: i686-pc-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation due to struct alias

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-09-20 22:26 -------
Confirmed, a regression.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
  GCC build triplet|i686-pc-linux               |
   GCC host triplet|i686-pc-linux               |
 GCC target triplet|i686-pc-linux               |
   Last reconfirmed|0000-00-00 00:00:00         |2006-09-20 22:26:43
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation due to struct alias

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
      Known to fail|                            |4.2.0
      Known to work|                            |4.1.0
            Summary|Misscompilation due to alias|[4.2 Regression]
                   |analysis                    |Misscompilation due to
                   |                            |struct alias
   Target Milestone|---                         |4.2.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation due to struct alias

[dberlin at gcc dot gnu dot org]

------- Comment #2 from dberlin at gcc dot gnu dot org  2006-09-21 02:32 -------
So, actually, i'm pretty sure they should have the same SMT, because they
should be in the same alias set.
Why do they get different SMT's?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation due to struct alias

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation due to struct alias

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2006-09-21 04:06 -------
Note in 4.1.2, we have two different TMT's here for the variables.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2006-09-21 04:23 -------
may_alias_p returns true
for:
(gdb) p debug_generic_expr (ptr)
xaD.1527
(gdb) p debug_generic_expr (var)
SMT.5D.1548


(In reply to comment #2)
> So, actually, i'm pretty sure they should have the same SMT, because they
> should be in the same alias set.
They are not the exact same aliasing set but conflicting ones.

> Why do they get different SMT's?
Because of this:
  /* To avoid creating unnecessary memory tags, only create one memory tag
     per alias set class.  Note that it may be tempting to group
     memory tags based on conflicting alias sets instead of
     equivalence.  That would be wrong because alias sets are not
     necessarily transitive (as demonstrated by the libstdc++ test
     23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
     such that conflicts (A, B) == true and conflicts (A, C) == true,
     it does not necessarily follow that conflicts (B, C) == true.  */

But I don't see how saying more than one thing conflicts, we get wrong code out
of it.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.2 Regression]            |[4.2 Regression]
                   |Misscompilation due to      |Misscompilation with structs
                   |struct alias                |due to  new struct alias


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[dberlin at dberlin dot org]

------- Comment #5 from dberlin at gcc dot gnu dot org  2006-09-21 12:15 -------
Subject: Re:  [4.2 Regression] Misscompilation with structs due to new struct
alias

On 21 Sep 2006 04:23:24 -0000, pinskia at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #4 from pinskia at gcc dot gnu dot org  2006-09-21 04:23 -------
> may_alias_p returns true
> for:
> (gdb) p debug_generic_expr (ptr)
> xaD.1527
> (gdb) p debug_generic_expr (var)
> SMT.5D.1548
>
>
> (In reply to comment #2)
> > So, actually, i'm pretty sure they should have the same SMT, because they
> > should be in the same alias set.
> They are not the exact same aliasing set but conflicting ones.

actually, they aren't just conflicting, one is a complete subset of another.

> > Why do they get different SMT's?
> Because of this:
>   /* To avoid creating unnecessary memory tags, only create one memory tag
>      per alias set class.  Note that it may be tempting to group
>      memory tags based on conflicting alias sets instead of
>      equivalence.
>  That would be wrong because alias sets are not
>      necessarily transitive (as demonstrated by the libstdc++ test
>      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
>      such that conflicts (A, B) == true and conflicts (A, C) == true,
>      it does not necessarily follow that conflicts (B, C) == true.  */

Yeah, but then you run into the situation we have here where there are
no "real" variables to hold these two sets together.  In other words,
this won't work if you have no addressable variables in your function
that could conflict with both.

Diego, pruning isn't doing anything wrong here.
One thing that would work properly is to create fake non-local
variables for each parameter's pointed to type.  Then one of the SMT's
will end up with both parameter symbols in it's alias sets, and
everything will work.
Otherwise, there are no addressable variables that will cause these
two sets to be believed to be the same.

I will implement this solution.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #6 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-09-21 12:22 -------
Subject: Re:  [4.2 Regression] Misscompilation with structs due to  new struct
alias

> > > Why do they get different SMT's?
> > Because of this:
> >   /* To avoid creating unnecessary memory tags, only create one memory tag
> >      per alias set class.  Note that it may be tempting to group
> >      memory tags based on conflicting alias sets instead of
> >      equivalence.
> >  That would be wrong because alias sets are not
> >      necessarily transitive (as demonstrated by the libstdc++ test
> >      23_containers/vector/cons/4.cc).  Given three alias sets A, B, C
> >      such that conflicts (A, B) == true and conflicts (A, C) == true,
> >      it does not necessarily follow that conflicts (B, C) == true.  */
> 
> Yeah, but then you run into the situation we have here where there are
> no "real" variables to hold these two sets together.  In other words,
> this won't work if you have no addressable variables in your function
> that could conflict with both.
> 
> Diego, pruning isn't doing anything wrong here.
> One thing that would work properly is to create fake non-local
> variables for each parameter's pointed to type.  Then one of the SMT's
> will end up with both parameter symbols in it's alias sets, and
> everything will work.
> Otherwise, there are no addressable variables that will cause these
> two sets to be believed to be the same.

it is probably not enough to consider just types of the parameters.
I wrote the testcase this way since it is simpler, but it should fail
exactly the same way with

struct test1 *out_of_nowhere_1 (void);
struct test2 *out_of_nowhere_2 (void);

int bla(void)
{
  struct test1 *xa = out_of_nowhere_1 ();
  struct test2 *xb = out_of_nowhere_2 ();
  global = 1;
  xb->sub.a = 1;
  xa->a = 8;
  return xb->sub.a;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[dberlin at gcc dot gnu dot org]

------- Comment #7 from dberlin at gcc dot gnu dot org  2006-10-13 17:51 -------
Mine


-- 

dberlin at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dberlin at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2006-09-20 22:26:43         |2006-10-13 17:51:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[dberlin at gcc dot gnu dot org]

------- Comment #8 from dberlin at gcc dot gnu dot org  2006-10-19 23:06 -------
Subject: Bug 29156

Author: dberlin
Date: Thu Oct 19 23:05:53 2006
New Revision: 117891

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117891
Log:
2006-10-19  Daniel Berlin  <dberlin@dberlin.org>

        Fix PR tree-optimization/28778
        Fix PR tree-optimization/29156
        Fix PR tree-optimization/29415
        * tree.h (DECL_PTA_ARTIFICIAL): New macro.
        (tree_decl_with_vis): Add artificial_pta_var flag.
        * tree-ssa-alias.c (is_escape_site): Remove alias info argument,
        pushed into callers.
        * tree-ssa-structalias.c (nonlocal_for_type): New variable.
        (nonlocal_all): Ditto.
        (struct variable_info): Add directly_dereferenced member.
        (var_escaped_vars): New variable.
        (escaped_vars_tree): Ditto.
        (escaped_vars_id): Ditto.
        (nonlocal_vars_id): Ditto.
        (new_var_info): Set directly_dereferenced.
        (graph_size): New variable
        (build_constraint_graph): Use graph_size.
        (solve_graph): Don't process constraints that cannot change the
        solution, don't try to propagate an empty solution to our
        successors.
        (process_constraint): Set directly_dereferenced.
        (could_have_pointers): New function.
        (get_constraint_for_component_ref): Don't process STRING_CST.
        (nonlocal_lookup): New function.
        (nonlocal_insert): Ditto.
        (create_nonlocal_var): Ditto.
        (get_nonlocal_id_for_type): Ditto.
        (get_constraint_for): Allow results vector to be empty in the case
        of string constants.
        Handle results of calls properly.
        (update_alias_info): Update alias info stats on number and type of
        calls.
        (find_func_aliases): Use could_have_pointers.
        (make_constraint_from_escaped): Renamed from
        make_constraint_to_anything, and changed to make constraints from
        escape variable.
        (make_constraint_to_escaped): New function.
        (find_global_initializers): Ditto.
        (create_variable_info_for): Make constraint from escaped to any
        global variable, and from any global variable to the set of
        escaped vars.
        (intra_create_variable_infos): Deal with escaped instead of
        pointing to anything.
        (set_uids_in_ptset): Do type pruning on directly dereferenced
        variables.
        (find_what_p_points_to): Adjust call to set_uids_with_ptset.
        (init_base_vars): Fix comment, and initialize escaped_vars.
        (need_to_solve): Removed.
        (find_escape_constraints): New function.
        (expand_nonlocal_solutions): Ditto.
        (compute_points_to_sets): Call find_escape_constraints and
        expand_nonlocal_solutions.
        (delete_points_to_sets): Don't fall off the end of the graph.
        (init_alias_heapvars): Initialize nonlocal_for_type and
        nonlocal_all.
        (delete_alias_heapvars): Free nonlocal_for_type and null out
        nonlocal_all. 


Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr28778.c
    trunk/gcc/testsuite/gcc.c-torture/execute/pr29156.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/gcc/tree-ssa-structalias.h
    trunk/gcc/tree.h


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156

[Bug tree-optimization/29156] [4.2 Regression] Misscompilation with structs due to new struct alias

[dberlin at gcc dot gnu dot org]

------- Comment #9 from dberlin at gcc dot gnu dot org  2006-10-19 23:07 -------
Fixed.


-- 

dberlin at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29156