llvm dev - Feb 2017 - RFC: Representing unions in TBAA

Hello all,

I'm new to the llvm community.  I'm learning how things work.  I noticed
that there has been some interest in improving how unions are handled. Bug 
21725 is one example.  I figured it might be a interesting place to start. 
 I discussed this with a couple people, and below is a suggestion on how 
to represent unions.  I would like some comments on how this fits in with 
how things are done in llvm.

Later,
Steven Perron

Motivation
=========
The main motivation for this is functional correctness of code using 
unions.
See https://llvm.org/bugs/show_bug.cgi?id=21725 for one example.  The 
problem is
that the basic alias analysis (or any other alias analysis) will not 
always have
enough information to be able see that the two references definitely 
overlap.
When this happens, the lack of alias information for unions could allow
undesired optimizations.


Current state
============
For this RFC, we are interested in how the type based aliasing is 
represented
for non-scalar data types.  In C/C++, this will be arrays, structs, 
classes, and
unions.  We will not mention classes again because for this purpose they 
are the
exact same as structs.

We will start with structs.  To help with the aliasing of structs, There 
is a
format for the type based aliasing meta data known as the struct-path. 
Here is
example IR:

 %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32 
0, %i32 2), align 4, !tbaa !2
 %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32 
0, %i32 3), align 4, !tbaa !7
 ...
 !2 = !{!3, !6, i64 800}
 !3 = !{!"S", !4, i64 0, !4, i64 400, !6, i64 800, !6, i64 804}
 !4 = !{!"omnipotent char", !5, i64 0}
 !5 = !{!"Simple C/C++ TBAA"}
 !6 = !{!"int", !4, i64 0}
 !7 = !{!3, !6, i64 804}

The two loads are loads of different int members of the same struct.  The 
type
based aliasing gives them different meta data tags (!2 and !7).  This 
allows the
analysis to determine that they are different solely from the type based
aliasing information.  Looking at !2, it points to !3 with offset 800. 
This
offset is used to identify which member of the struct is being accessed.

Next we will consider arrays.  When there is an array access, the type 
based
aliasing views it as an access of the type of the element.  In general, 
this is
not a problem.  For C/C++, there is no real difference between an array
reference and a dereference of a pointer.  However, this causes a lose of
information when accessing arrays that are part of a struct or union.

Here is an example:

  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* 
getelementptr %inbounds (%struct.S, %struct.S* @s, i32 0, i32 0), i64 0, 
i64 %idxprom
  %1 = load i32, i32* %arrayidx, align 4, !tbaa !1
  ...
  !1 = !{!2, !2, i64 0}
  !2 = !{!"int", !3, i64 0}

This is an access to an array of integers in a struct of type S.  Note 
that the
type on the load is "int".  The type bases alias information has lost
that
this
is a reference to a member of a struct.

We finish by considering unions.  Like arrays, an access to a member of a 
union
is treated as if is it type of the type of the member being accessed. Here 
is
an example:

  %4 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 
0, i32 %0), align 4, !tbaa !2
  ...
  !2 = !{!3, !3, i64 0}
  !3 = !{!"int", !4, i64 0}

Here we lose the information that the reference is part of a union, so we 
cannot
tell that this memory may overlap with something of a different type. 
Clang
currently relies on other aliasing analysis like the basic alias analysis 
to
observer that the two references are aliased.

Proposed changes for arrays
==========================
To deal with array references, they should be treated as if all array 
accesses
are accesses to the first member of the array.  For the purpose of type 
based
aliasing, this should be good enough.  The offset in the tag would be the
offset of the start of the array plus, if applicable, the offset needed to
access the member of the array element as if the element was a top-level 
struct
member at offset 0.  Note that the values for the indexing of the array is 
not
included.  Thus, accesses to an element of the last dimension of a
multidimensional array appears the same as an access to a flattened 
version of
the multidimensional array.  Then, in the struct path, the array member's 
offset
will be the starting offset of the array, as it is now.  What will change 
in the
struct path is the type node for the array.  The type node will become the 
type
of the array element instead of "omnipotent char", as it is now.

This change is a must to be able to get union aliasing correct because we 
need
to know when an array is part of a union that may overlap with other 
members.



Proposed changes for unions
===========================
To properly deal with unions, there are a few issues that need to be dealt 
with.

1) Unions have to somehow be represented in the TBAA.  As was pointed out 
above,
this information is currently lost.

2) With the struct path TBAA, it is assumed that the length of a member 
extends
to the start of the next.  This will not be true for unions.

3) With the current struct path TBAA, you can determine which member is
reference by looking at the offset.  That is not true with unions because 
every
member starts at offset 0.  We will need another way of doing this for 
unions.

Any solution we come up with will have to get around these three problems.

To deal with unions, we will use the change in bug 21725 (see link above). 
 This
will treat a union as if it is a struct.  However, the important change to 
make
the unions work is that the length of the memory reference will have to be 
taken
into consideration when looking at the type based aliasing.  This should 
be easy
enough because TypeBasedAAResult::alias takes two arguments of type
MemoryLocation, and they contain the size information that is needed. This
should easy take care of the first two problems.

In TypeBasedAAResult::alias, we will also have to deal with the fact that 
unions
have multiple members all at offset 0.  This means that, unlike structs, 
the
compiler will not be able to tell which member of the union the memory 
reference
actually used.  To deal with this, TypeBasedAAResult::alias (and the 
functions
it calls) will have to acts as if all of the unions members could have 
been
accessed.  So the search along the tree will follow all of the member 
instead of
just one as we currently do with structs.  Changes to the algorithm can be 
made
to avoid traversing the same TBAA nodes multiple times.  The section at 
the end
explores the consequences of this decision and a possible alternative.

Examples
=======
Source code for the example
---------------------------

struct S
{
  int b;
  struct T
  {
    int a[10];
  } t;
} s;

struct C
{
  int a;
  int b;
};

struct R
{
  union {
    struct C a[10];
    struct C b[10];
  } u;
  int c;
} r;

union U
{
  int i;
  float f;
} u;

struct Q
{
  int a;
  union U u;
} q;

int foo()
{
  return s.t.a[4] + s.b + r.u.b[3].b + u.i + u.f + q.u.i + q.u.f + q.a + 
r.c;
}

----------------------------
Current llvm-ir
----------------------------

*** IR Dump Before Module Verifier ***
; Function Attrs: nounwind
define signext i32 @foo() #0 {
entry:
  %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, 
i32 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
  %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, 
i32 0, i32 0), align 4, !tbaa !6
  %add = add nsw i32 %0, %1
  %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, 
i32 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
  %add1 = add nsw i32 %add, %2
  %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 
0, i32 0), align 4, !tbaa !2
  %add2 = add nsw i32 %add1, %3
  %conv = sitofp i32 %add2 to float
  %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa 
!11
  %add3 = fadd float %conv, %4
  %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, 
i32 0, i32 1, i32 0), align 4, !tbaa !2
  %conv4 = sitofp i32 %5 to float
  %add5 = fadd float %add3, %conv4
  %6 = load float, float* bitcast (%union.U* getelementptr inbounds 
(%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !11
  %add6 = fadd float %add5, %6
  %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, 
i32 0, i32 0), align 4, !tbaa !13
  %conv7 = sitofp i32 %7 to float
  %add8 = fadd float %add6, %conv7
  %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, 
i32 0, i32 1), align 4, !tbaa !15
  %conv9 = sitofp i32 %8 to float
  %add10 = fadd float %add8, %conv9
  %conv11 = fptosi float %add10 to i32
  ret i32 %conv11
}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (trunk 290896)"}
!2 = !{!3, !3, i64 0}
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!7, !3, i64 0}
!7 = !{!"S", !3, i64 0, !8, i64 4}
!8 = !{!"T", !4, i64 0}
!9 = !{!10, !3, i64 4}
!10 = !{!"C", !3, i64 0, !3, i64 4}
!11 = !{!12, !12, i64 0}
!12 = !{!"float", !4, i64 0}
!13 = !{!14, !3, i64 0}
!14 = !{!"Q", !3, i64 0, !4, i64 4}
!15 = !{!16, !3, i64 80}
!16 = !{!"R", !4, i64 0, !3, i64 80}

----------------------------
Suggested new llvm-ir
----------------------------

*** IR Dump Before Module Verifier ***
; Function Attrs: nounwind
define signext i32 @foo() #0 {
entry:
  %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, 
i32 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
  %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, 
i32 0, i32 0), align 4, !tbaa !6
  %add = add nsw i32 %0, %1
  %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, 
i32 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
  %add1 = add nsw i32 %add, %2
  %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 
0, i32 0), align 4, !tbaa !18                         // Need to change to 
reference the union "U", not just the scalar.
  %add2 = add nsw i32 %add1, %3
  %conv = sitofp i32 %add2 to float
  %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa 
!11
  %add3 = fadd float %conv, %4
  %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, 
i32 0, i32 1, i32 0), align 4, !tbaa !19                // Need to 
reference the top level struct "Q", and not just the scalar.
  %conv4 = sitofp i32 %5 to float
  %add5 = fadd float %add3, %conv4
  %6 = load float, float* bitcast (%union.U* getelementptr inbounds 
(%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !20  
// Need to reference the struct "Q".
  %add6 = fadd float %add5, %6
  %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, 
i32 0, i32 0), align 4, !tbaa !13
  %conv7 = sitofp i32 %7 to float
  %add8 = fadd float %add6, %conv7
  %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, 
i32 0, i32 1), align 4, !tbaa !15
  %conv9 = sitofp i32 %8 to float
  %add10 = fadd float %add8, %conv9
  %conv11 = fptosi float %add10 to i32
  ret i32 %conv11
}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (trunk 290896)"}
!2 = !{!7, !3, i64 4}                                   // Need to change 
to point to the struct "S" with the starting offset of the array.
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!7, !3, i64 0}
!7 = !{!"S", !3, i64 0, !8, i64 4}
!8 = !{!"T", !3, i64 0}                                 // Use
"int" for
the type of the array instead of "omnipotent char.".
!9 = !{!16, !3, i64 44}                                 // Point to the 
outermost struct "R" instead of "C".  Add the offset of the
array in "R"
and the offset of the member in "C".
!10 = !{!"C", !3, i64 0, !3, i64 4}
!11 = !{!17, !12, i64 0}                                // Need to point 
to the union "U" instead of using the scalar.
!12 = !{!"float", !4, i64 0}
!13 = !{!14, !3, i64 0}
!14 = !{!"Q", !3, i64 0, !17, i64 4}                    // Use the
union
"U" as the type for the member.
!15 = !{!16, !3, i64 80}
!16 = !{!"R", !21, i64 0, !3, i64 80}                   // Have the
first
member point to the union "R.u".
!17 = !{!"U", !3, i64 0, !12, i64 0}                    // Introduce
the
struct path for the union.
!18 = !{!17, !3, i64 0}                                 // Tag for a union 
reference goes through the union.
!19 = !{!14, !3, i64 4}                                 // Tag for a union 
reference inside a struct points to the top level struct.
!20 = !{!14, !11, i64 4}                                // Same as !19 
except for the float.
!21 = !{!"R.u", !10, i64 0, !10, i64 0}                 // Add a
struct
path for the union defined in "R". 


Multiple members at the same offset
==================================
Consider the following example:

union U {
  int a;
  float b;
};

int foo( U * u, int * i, float * f )
{
  *i = 0;
  *f = 100.0;
  return u->a;
}

With the changes I described above, the reference "u->a" will alias
both
"*i"
and "*f" because, when we see the struct-path for the union, we will 
follow path
for "a" and "b".  This may be more conservative than we
want.  It might
also be
exactly what we want.

The difficulty in being more precise is that, in general, we cannot know 
which
member of the union was access with the current information in the 
llvm-ir.  If
we want to fix this we can create a new scalar to represent the members
which will be used as the scalar meta data in the tag.  Then, when a 
struct-path
node for a union is reached, we will have to search each possible path to 
see if
it reaches the scalar node on the tag.  If it does, that is the path we 
follow.

With this change, the llvm-ir for the example would be:

define signext i32 @foo(%union.U* %u, i32* %i, float* %f) #0 {
entry:
  store i32 0, i32* %i, align 4, !tbaa !2
  store float 1.000000e+02, float* %f, align 4, !tbaa !6
  %a = bitcast %union.U* %u to i32*
  %0 = load i32, i32* %a, align 4, !tbaa !11            // Use the new tag
  ret i32 %0
}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"clang version 4.0.0 (trunk 290896)"}
!2 = !{!3, !3, i64 0}
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C/C++ TBAA"}
!6 = !{!7, !7, i64 0}
!7 = !{!"float", !4, i64 0}
!8 = !{!"U", !9, i64 0, !10, i64 0}     // The struct path for the
union
with special members.
!9 = !{!"U.a", !3, 0}                   // The member of the union.
!10 = !{!"U.b", !7, 0}                  // The member of the union.
!11 = !{!8, !9, 0}                      // The new tag where the scalar is 
the union member instead of the generic "int".



Read versus write aliasing
=========================
It has come to my attention that there is a question about whether the 
read
versus write aliasing matters for union aliasing.  Maybe there is 
something in
the C/C++ specification I am missing, but I believe we need to handle this 
as
well.  Suppose we take an example similar to the one in defect 21725:

#include <stdio.h>

union U {
        short s;
        int i;
} u;

int v = 987;
union U* up = &u;

int foo()
{
        int temp = u.s;
        up->i = 123;     // 123
        printf("%d\n", up->i);
        printf("%hd\n", temp);
        return 0;
}

In this case, if the read of "u.s" is not aliased to the write of
"up->i"
and
they are reordered, then "temp" could get the wrong value.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170212/eee6b331/attachment.html>

Hi Steven,

On Sun, Feb 12, 2017 at 8:01 PM, Steven Perron via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I'm new to the llvm community.  I'm learning how things work.  I
noticed
> that there has been some interest in improving how unions are handled.  Bug
> 21725 is one example.  I figured it might be a interesting place to start.
> I discussed this with a couple people, and below is a suggestion on how to
> represent unions.  I would like some comments on how this fits in with how
> things are done in llvm.
>
> Later,
> Steven Perron
>
> Motivation
> =========>
> The main motivation for this is functional correctness of code using
unions.
> See https://llvm.org/bugs/show_bug.cgi?id=21725for one example.  The
problem
> is
> that the basic alias analysis (or any other alias analysis) will not always
> have
> enough information to be able see that the two references definitely
> overlap.
> When this happens, the lack of alias information for unions could allow
> undesired optimizations.
>
> Current state
> ============>
> For this RFC, we are interested in how the type based aliasing is
> represented
> for non-scalar data types.  In C/C++, this will be arrays, structs,
classes,
> and
> unions.  We will not mention classes again because for this purpose they
are
> the
> exact same as structs.
>
> We will start with structs.  To help with the aliasing of structs, There is
> a
> format for the type based aliasing meta data known as the struct-path. 
Here
> is
> example IR:
>
>  %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, %i32 2), align 4, !tbaa !2
>  %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, %i32 3), align 4, !tbaa !7
>  ...
>  !2 = !{!3, !6, i64 800}
>  !3 = !{!"S", !4, i64 0, !4, i64 400, !6, i64 800, !6, i64 804}
>  !4 = !{!"omnipotent char", !5, i64 0}
>  !5 = !{!"Simple C/C++ TBAA"}
>  !6 = !{!"int", !4, i64 0}
>  !7 = !{!3, !6, i64 804}
>
> The two loads are loads of different int members of the same struct.  The
> type
> based aliasing gives them different meta data tags (!2 and !7).  This
allows
> the
> analysis to determine that they are different solely from the type based
> aliasing information.  Looking at !2, it points to !3 with offset 800. 
This
> offset is used to identify which member of the struct is being accessed.
>
> Next we will consider arrays.  When there is an array access, the type
based
> aliasing views it as an access of the type of the element.  In general,
this
> is
> not a problem.  For C/C++, there is no real difference between an array
> reference and a dereference of a pointer.  However, this causes a lose of
> information when accessing arrays that are part of a struct or union.
>
> Here is an example:
>
>   %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]*
getelementptr
> %inbounds (%struct.S, %struct.S* @s, i32 0, i32 0), i64 0, i64 %idxprom
>   %1 = load i32, i32* %arrayidx, align 4, !tbaa !1
>   ...
>   !1 = !{!2, !2, i64 0}
>   !2 = !{!"int", !3, i64 0}
>
> This is an access to an array of integers in a struct of type S.  Note that
> the
> type on the load is "int".  The type bases alias information has
lost that
> this
> is a reference to a member of a struct.
>
> We finish by considering unions.  Like arrays, an access to a member of a
> union
> is treated as if is it type of the type of the member being accessed.  Here
> is
> an example:
>
>   %4 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32
0,
> i32 %0), align 4, !tbaa !2
>   ...
>   !2 = !{!3, !3, i64 0}
>   !3 = !{!"int", !4, i64 0}
>
> Here we lose the information that the reference is part of a union, so we
> cannot
> tell that this memory may overlap with something of a different type. 
Clang
> currently relies on other aliasing analysis like the basic alias analysis
to
> observer that the two references are aliased.
>
> Proposed changes for arrays
> ==========================>
> To deal with array references, they should be treated as if all array
> accesses
> are accesses to the first member of the array.  For the purpose of type
> based
> aliasing, this should be good enough.  The offset in the tag would be the
> offset of the start of the array plus, if applicable, the offset needed to
> access the member of the array element as if the element was a top-level
> struct
> member at offset 0.  Note that the values for the indexing of the array is
> not
> included.  Thus, accesses to an element of the last dimension of a
> multidimensional array appears the same as an access to a flattened version
> of
> the multidimensional array.  Then, in the struct path, the array
member's
> offset
> will be the starting offset of the array, as it is now.  What will change
in
> the
> struct path is the type node for the array.  The type node will become the
> type
> of the array element instead of "omnipotent char", as it is now.
>
> This change is a must to be able to get union aliasing correct because we
> need
> to know when an array is part of a union that may overlap with other
> members.
>
>
>
> Proposed changes for unions
> ===========================>
> To properly deal with unions, there are a few issues that need to be dealt
> with.
>
> 1) Unions have to somehow be represented in the TBAA.  As was pointed out
> above,
> this information is currently lost.
>
> 2) With the struct path TBAA, it is assumed that the length of a member
> extends
> to the start of the next.  This will not be true for unions.
>
> 3) With the current struct path TBAA, you can determine which member is
> reference by looking at the offset.  That is not true with unions because
> every
> member starts at offset 0.  We will need another way of doing this for
> unions.
>
> Any solution we come up with will have to get around these three problems.
>
> To deal with unions, we will use the change in bug 21725 (see link above).
> This
> will treat a union as if it is a struct.  However, the important change to
> make
> the unions work is that the length of the memory reference will have to be
> taken
> into consideration when looking at the type based aliasing.  This should be
It was not clear how you'll take the length into consideration.  Are
you talking about inferences like "I know the access was 4 bytes long,
so it can't be accessing the `short` field"?  If so, we'd need to
verify (and maintain) that no passes ask AA about a subsegment of a
memory access (i.e. "does that store alias the first two bytes of this
i32 load"); or at least prevent them from using TBAA when they refine
their queries this way.
> easy
> enough because TypeBasedAAResult::alias takes two arguments of type
> MemoryLocation, and they contain the size information that is needed.  This
> should easy take care of the first two problems.
>
> In TypeBasedAAResult::alias, we will also have to deal with the fact that
> unions
> have multiple members all at offset 0.  This means that, unlike structs,
the
> compiler will not be able to tell which member of the union the memory
> reference
> actually used.  To deal with this, TypeBasedAAResult::alias (and the
> functions
> it calls) will have to acts as if all of the unions members could have been
> accessed.  So the search along the tree will follow all of the member
> instead of
> just one as we currently do with structs.  Changes to the algorithm can be
> made
> to avoid traversing the same TBAA nodes multiple times.  The section at the
> end
> explores the consequences of this decision and a possible alternative.
I don't think this fully solves the problem -- you'll also need to fix
getMostGenericTBAA.  That is, even if you implement the above scheme,
say you started out with:

union U {
  int i;
  float f;
};

float f(union U *u, int *ii, float *ff, bool c) {
  if (c) {
    *ii = 10;
    *ff = 10.0;
  } else {
    u->i = 10;    // S0
    u->f = 10.0;  // S1
  }
  return u->f;
}

(I presume you're trying to avoid reordering S0 and S1?)

SimplifyCFG or some other such pass may transform f to:

float f(union U *u, int *ii, float *ff, bool c) {
  int *iptr = c ? ii : &(u->i);
  int *fptr = c ? ff : &(u->f);
  *iptr = 10;     // S2
  *fptr = 10.0;   // S3
  return u->f;
}

then getMostGenericTBAA will infer scalar "int" TBAA for S2 and scalar
"float" TBAA for S3, which will be NoAlias and allow the reordering
you were trying to avoid.

-- Sanjoy
>
> Examples
> =======>
> Source code for the example
> ---------------------------
>
> struct S
> {
>   int b;
>   struct T
>   {
>     int a[10];
>   } t;
> } s;
>
> struct C
> {
>   int a;
>   int b;
> };
>
> struct R
> {
>   union {
>     struct C a[10];
>     struct C b[10];
>   } u;
>   int c;
> } r;
>
> union U
> {
>   int i;
>   float f;
> } u;
>
> struct Q
> {
>   int a;
>   union U u;
> } q;
>
> int foo()
> {
>   return s.t.a[4] + s.b + r.u.b[3].b + u.i + u.f + q.u.i + q.u.f + q.a +
> r.c;
> }
>
> ----------------------------
> Current llvm-ir
> ----------------------------
>
> *** IR Dump Before Module Verifier ***
> ; Function Attrs: nounwind
> define signext i32 @foo() #0 {
> entry:
>   %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
>   %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 0), align 4, !tbaa !6
>   %add = add nsw i32 %0, %1
>   %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
>   %add1 = add nsw i32 %add, %2
>   %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32
0,
> i32 0), align 4, !tbaa !2
>   %add2 = add nsw i32 %add1, %3
>   %conv = sitofp i32 %add2 to float
>   %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa
> !11
>   %add3 = fadd float %conv, %4
>   %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 1, i32 0), align 4, !tbaa !2
>   %conv4 = sitofp i32 %5 to float
>   %add5 = fadd float %add3, %conv4
>   %6 = load float, float* bitcast (%union.U* getelementptr inbounds
> (%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !11
>   %add6 = fadd float %add5, %6
>   %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 0), align 4, !tbaa !13
>   %conv7 = sitofp i32 %7 to float
>   %add8 = fadd float %add6, %conv7
>   %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 1), align 4, !tbaa !15
>   %conv9 = sitofp i32 %8 to float
>   %add10 = fadd float %add8, %conv9
>   %conv11 = fptosi float %add10 to i32
>   ret i32 %conv11
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !3, i64 0}
> !7 = !{!"S", !3, i64 0, !8, i64 4}
> !8 = !{!"T", !4, i64 0}
> !9 = !{!10, !3, i64 4}
> !10 = !{!"C", !3, i64 0, !3, i64 4}
> !11 = !{!12, !12, i64 0}
> !12 = !{!"float", !4, i64 0}
> !13 = !{!14, !3, i64 0}
> !14 = !{!"Q", !3, i64 0, !4, i64 4}
> !15 = !{!16, !3, i64 80}
> !16 = !{!"R", !4, i64 0, !3, i64 80}
>
> ----------------------------
> Suggested new llvm-ir
> ----------------------------
>
> *** IR Dump Before Module Verifier ***
> ; Function Attrs: nounwind
> define signext i32 @foo() #0 {
> entry:
>   %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
>   %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 0), align 4, !tbaa !6
>   %add = add nsw i32 %0, %1
>   %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
>   %add1 = add nsw i32 %add, %2
>   %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32
0,
> i32 0), align 4, !tbaa !18                         // Need to change to
> reference the union "U", not just the scalar.
>   %add2 = add nsw i32 %add1, %3
>   %conv = sitofp i32 %add2 to float
>   %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa
> !11
>   %add3 = fadd float %conv, %4
>   %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 1, i32 0), align 4, !tbaa !19                // Need to reference
the
> top level struct "Q", and not just the scalar.
>   %conv4 = sitofp i32 %5 to float
>   %add5 = fadd float %add3, %conv4
>   %6 = load float, float* bitcast (%union.U* getelementptr inbounds
> (%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !20
> // Need to reference the struct "Q".
>   %add6 = fadd float %add5, %6
>   %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 0), align 4, !tbaa !13
>   %conv7 = sitofp i32 %7 to float
>   %add8 = fadd float %add6, %conv7
>   %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 1), align 4, !tbaa !15
>   %conv9 = sitofp i32 %8 to float
>   %add10 = fadd float %add8, %conv9
>   %conv11 = fptosi float %add10 to i32
>   ret i32 %conv11
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!7, !3, i64 4}                                   // Need to change
to
> point to the struct "S" with the starting offset of the array.
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !3, i64 0}
> !7 = !{!"S", !3, i64 0, !8, i64 4}
> !8 = !{!"T", !3, i64 0}                                 // Use
"int" for the
> type of the array instead of "omnipotent char.".
> !9 = !{!16, !3, i64 44}                                 // Point to the
> outermost struct "R" instead of "C".  Add the offset of
the array in "R" and
> the offset of the member in "C".
> !10 = !{!"C", !3, i64 0, !3, i64 4}
> !11 = !{!17, !12, i64 0}                                // Need to point to
> the union "U" instead of using the scalar.
> !12 = !{!"float", !4, i64 0}
> !13 = !{!14, !3, i64 0}
> !14 = !{!"Q", !3, i64 0, !17, i64 4}                    // Use
the union "U"
> as the type for the member.
> !15 = !{!16, !3, i64 80}
> !16 = !{!"R", !21, i64 0, !3, i64 80}                   // Have
the first
> member point to the union "R.u".
> !17 = !{!"U", !3, i64 0, !12, i64 0}                    //
Introduce the
> struct path for the union.
> !18 = !{!17, !3, i64 0}                                 // Tag for a union
> reference goes through the union.
> !19 = !{!14, !3, i64 4}                                 // Tag for a union
> reference inside a struct points to the top level struct.
> !20 = !{!14, !11, i64 4}                                // Same as !19
> except for the float.
> !21 = !{!"R.u", !10, i64 0, !10, i64 0}                 // Add a
struct path
> for the union defined in "R".
>
>
> Multiple members at the same offset
> ==================================>
> Consider the following example:
>
> union U {
>   int a;
>   float b;
> };
>
> int foo( U * u, int * i, float * f )
> {
>   *i = 0;
>   *f = 100.0;
>   return u->a;
> }
>
> With the changes I described above, the reference "u->a" will
alias both
> "*i"
> and "*f" because, when we see the struct-path for the union, we
will follow
> path
> for "a" and "b".  This may be more conservative than we
want.  It might also
> be
> exactly what we want.
>
> The difficulty in being more precise is that, in general, we cannot know
> which
> member of the union was access with the current information in the llvm-ir.
> If
> we want to fix this we can create a new scalar to represent the members
> which will be used as the scalar meta data in the tag.  Then, when a
> struct-path
> node for a union is reached, we will have to search each possible path to
> see if
> it reaches the scalar node on the tag.  If it does, that is the path we
> follow.
>
> With this change, the llvm-ir for the example would be:
>
> define signext i32 @foo(%union.U* %u, i32* %i, float* %f) #0 {
> entry:
>   store i32 0, i32* %i, align 4, !tbaa !2
>   store float 1.000000e+02, float* %f, align 4, !tbaa !6
>   %a = bitcast %union.U* %u to i32*
>   %0 = load i32, i32* %a, align 4, !tbaa !11            // Use the new tag
>   ret i32 %0
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !7, i64 0}
> !7 = !{!"float", !4, i64 0}
> !8 = !{!"U", !9, i64 0, !10, i64 0}     // The struct path for
the union
> with special members.
> !9 = !{!"U.a", !3, 0}                   // The member of the
union.
> !10 = !{!"U.b", !7, 0}                  // The member of the
union.
> !11 = !{!8, !9, 0}                      // The new tag where the scalar is
> the union member instead of the generic "int".
>
>
>
> Read versus write aliasing
> =========================>
> It has come to my attention that there is a question about whether the read
> versus write aliasing matters for union aliasing.  Maybe there is something
> in
> the C/C++ specification I am missing, but I believe we need to handle this
> as
> well.  Suppose we take an example similar to the one in defect 21725:
>
> #include <stdio.h>
>
> union U {
>         short s;
>         int i;
> } u;
>
> int v = 987;
> union U* up = &u;
>
> int foo()
> {
>         int temp = u.s;
>         up->i = 123;     // 123
>         printf("%d\n", up->i);
>         printf("%hd\n", temp);
>         return 0;
> }
>
> In this case, if the read of "u.s" is not aliased to the write of
"up->i"
> and
> they are reordered, then "temp" could get the wrong value.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

>
>
> I don't think this fully solves the problem -- you'll also need to
fix
> getMostGenericTBAA.  That is, even if you implement the above scheme,
> say you started out with:
>
> union U {
>   int i;
>   float f;
> };
>
> float f(union U *u, int *ii, float *ff, bool c) {
>   if (c) {
>     *ii = 10;
>     *ff = 10.0;
>   } else {
>     u->i = 10;    // S0
>     u->f = 10.0;  // S1
>   }
>   return u->f;
> }
>
> (I presume you're trying to avoid reordering S0 and S1?)
>
> SimplifyCFG or some other such pass may transform f to:
>
> float f(union U *u, int *ii, float *ff, bool c) {
>   int *iptr = c ? ii : &(u->i);
>   int *fptr = c ? ff : &(u->f);
>   *iptr = 10;     // S2
>   *fptr = 10.0;   // S3
>   return u->f;
> }
>
> then getMostGenericTBAA will infer scalar "int" TBAA for S2 and
scalar
> "float" TBAA for S3, which will be NoAlias and allow the
reordering
> you were trying to avoid.
>
FWIW, i have to read this in detail, but a few things pop out at me.

1. We would like to live in a world where we don't depend on TBAA
overriding BasicAA to get correct answers.  We do now, but don't want to.
Hopefully this proposal does not make that impossible.

2.  Literally the only way that GCC ends up getting this right is two fold:
It only guarantees things about direct access through union.
If you take the address of the union member (like the transform above), it
knows it will get a wrong answer.
So what it does is it finds the type it has to stop at (here, the union) to
keep the TBAA set the same, and makes the transform end there.
So the above would not occur.


3. A suggestion that TBAA follow all possible paths seems .. very slow.

4. "The main motivation for this is functional correctness of code using
unions".  I believe you mean "with tbaa and strict-aliasing on".
If not,functional correctness for unions should not be in any way related
to requiring TBAA.

5. Unions are among the worst area of the standard in terms of "nobody has
really thought super-hard about the interaction of aliasing and unions in a
way that is coherent".
So when you say things like 'necessary for functional correctness of
unions', just note that this is pretty much wrong.  You probably mean
"necessary for a reasonable interpretation" or something.

Because we would be *functionally correct* by the standard by destroying
the program  if you ever read the member you didn't set :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170212/2ef819c3/attachment.html>