[llvm-dev] RFC: Representing unions in TBAA

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
93 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
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=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 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.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
Hi Steven,

On Sun, Feb 12, 2017 at 8:01 PM, Steven Perron via llvm-dev
<[hidden email]> 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
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via 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 :)




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin via llvm-dev <[hidden email]> wrote:

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 :)
C11 subclause 6.5.2.3 paragraph 3, has in footnote 95:
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

So, the intent is at least that the use of the . operator or the -> operator to access a member of a union would "safely" perform type punning.
 




_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev


On Mon, Feb 13, 2017 at 10:07 AM, Hubert Tong <[hidden email]> wrote:
On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin via llvm-dev <[hidden email]> wrote:

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 :)
C11 subclause 6.5.2.3 paragraph 3, has in footnote 95:
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

So, the intent is at least that the use of the . operator or the -> operator to access a member of a union would "safely" perform type punning.
 
Certainly, if you can quote this, you know this is new to C11 (and newer versions of C++).
:)

It was explicitly *not* true in earlier versions.

They've also slowly cleaned up the aliasing rules, but, honestly, still a mess.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
On Mon, Feb 13, 2017 at 10:39 PM, Daniel Berlin <[hidden email]> wrote:


On Mon, Feb 13, 2017 at 10:07 AM, Hubert Tong <[hidden email]> wrote:
On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin via llvm-dev <[hidden email]> wrote:

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 :)
C11 subclause 6.5.2.3 paragraph 3, has in footnote 95:
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

So, the intent is at least that the use of the . operator or the -> operator to access a member of a union would "safely" perform type punning.
 
Certainly, if you can quote this, you know this is new to C11 (and newer versions of C++).
:)
Yes, this is new to C11; however, the question for us here is whether, and under what options, we would support such intended use of the language.
As for C++, the safe type punning aspect does not appear to hold, and I am not aware of committee consensus to introduce it.
 

It was explicitly *not* true in earlier versions.

They've also slowly cleaned up the aliasing rules, but, honestly, still a mess.
Yes, I know of at least one instance where colourful metaphors ended up in the C committee meeting minutes in relation to aliasing-related discussion.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev


On Tue, Feb 14, 2017 at 5:51 AM, Hubert Tong <[hidden email]> wrote:
On Mon, Feb 13, 2017 at 10:39 PM, Daniel Berlin <[hidden email]> wrote:


On Mon, Feb 13, 2017 at 10:07 AM, Hubert Tong <[hidden email]> wrote:
On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin via llvm-dev <[hidden email]> wrote:

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 :)
C11 subclause 6.5.2.3 paragraph 3, has in footnote 95:
If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

So, the intent is at least that the use of the . operator or the -> operator to access a member of a union would "safely" perform type punning.
 
Certainly, if you can quote this, you know this is new to C11 (and newer versions of C++).
:)
Yes, this is new to C11; however, the question for us here is whether, and under what options, we would support such intended use of the language.

I was on board with it :)
 I remember pointing out most of the cases we have bugs for when struct-path TBAA was designed (on a whiteboard, in fact) and the consensus answer i got back was basically "we'll just punt on unions for now".  I did say i suspected this would not work out well, soundness wise, but the clear consensus was against me, so here we are :)
In any case, reading this in detail:
1. "In 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."

Staring at the langref, i don't see where it assumes this.
it is just offset, size, tbaa type, which seems correct to me.

If you mean "the implementation assumes", then yeah, the implementation should just be fixed.

"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. "

Actually, for correctness, it just has to give a conservative answer of "may-alias"

This is papering over the fact that if it does that, basicaa overrides it.
That we should just fix that, not rely on making TBAA work harder to be correct (working harder to optimize is fine).

That is, say "these are may-alias, this is a final answer" instead of "these are may-alias, maybe you can do better?"

But yes, if you are trying to optimize unions harder (and i don't know why you would :P), yes, you'd have to follow all intersecting members.
In gcc we just sort the list, and use offset, size info to see what  fields it overlaps with.

But note: Your correctness still depends on being able to tell these are union accesses.
That's bad, because as sanjoy says, we do transforms that may cause this to be non-recoverable.

If you can't have TBAA say "may-alias, final answer", you lose.

(Note, while you are improving this, i'll note the info should also be used to differentiate structure fields and solve the issue discussed here:

The offset, size info is useful and should be used to differentiate struct accesses *regardless of type* in cases where we can.
It doesn't actually matter if one field is an int and the other a float. If they are different fields, and we can prove it, they can't alias anyway)





_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
Thanks Daniel and Sanjoy for you comments.  I'll try to list the issues I need to respond to, and double check my understand.

1) Sometimes I think of things a certain way, and I assume other people think the same way.  When I say that I do not want to rely on basic alias analysis to override the TBAA, I do not consider "may-alias" an answer.  I want to avoid the situation where TBAA says "no-alias, but that might be wrong", at least for legal code.  In the same spirit, I primarily work on optimizing code, so, when I say the main point is functional correctness, I really mean to make things functionally correct while still being able to optimize as much as possible.

2) Any function that deals with the TBAA nodes directly must be updated to handle the new form, a struct-path with multiple member at offset 0.  One example is getMostGenericTBAA.  I'll look into that function and see what we can do about it.  I'll need to look for other.  However, I do not consider this something that should stop us from implementing something like this.  I believe they can all be handled in a reasonable way.  "getMostGenericTBAA" could be handled by Making recursive calls with each member of the union, or something equivalent.

3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.

Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.  This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.

4) Sonjoy asked a question about how I would be using length information:

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.


The answer is no, I will not be trying to infer length information from the access type.  The idea is if I have two references to the same union.  One if offset o1 and size s1, the other with offset o2 and size s2.  Suppose without lose of generality that o1 <= o2.  Then if o1+s1 <= o2, then the references do not alias.  Otherwise they may alias.  There may be a few case where a size is not available.  When dealing with call site for example.  In this case, we have to treat the size as "infinite" pessimizing the aliasing.

Again thanks for your comments.

Later,
Steven Perron

Daniel Berlin <[hidden email]> wrote on 2017/02/14 10:05:29 AM:

> From: Daniel Berlin <[hidden email]>

> To: Hubert Tong <[hidden email]>
> Cc: Sanjoy Das <[hidden email]>, Steven Perron/
> Toronto/IBM@IBMCA, llvm-dev <[hidden email]>

> Date: 2017/02/14 10:05 AM
> Subject: Re: [llvm-dev] RFC: Representing unions in TBAA
>
> On Tue, Feb 14, 2017 at 5:51 AM, Hubert Tong <[hidden email]
> > wrote:

> On Mon, Feb 13, 2017 at 10:39 PM, Daniel Berlin <[hidden email]> wrote:
>
> On Mon, Feb 13, 2017 at 10:07 AM, Hubert Tong <
> [hidden email]> wrote:

> On Mon, Feb 13, 2017 at 2:23 AM, Daniel Berlin via llvm-dev <llvm-
> [hidden email]> wrote:

>

> 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 :)

> C11 subclause 6.5.2.3 paragraph 3, has in footnote 95:
> If the member used to read the contents of a union object is not the
> same as the member last used to store a value in the object, the
> appropriate part of the object representation of the value is
> reinterpreted as an object representation in the new type as
> described in 6.2.6 (a process sometimes called "type punning"). This
> might be a trap representation.

> So, the intent is at least that the use of the . operator or the ->
> operator to access a member of a union would "safely" perform type punning.

>  
> Certainly, if you can quote this, you know this is new to C11 (and
> newer versions of C++).

> :)
> Yes, this is new to C11; however, the question for us here is
> whether, and under what options, we would support such intended use
> of the language.

>
> I was on board with it :)

>  I remember pointing out most of the cases we have bugs for when
> struct-path TBAA was designed (on a whiteboard, in fact) and the
> consensus answer i got back was basically "we'll just punt on unions
> for now".  I did say i suspected this would not work out well,
> soundness wise, but the clear consensus was against me, so here we are :)

> In any case, reading this in detail:
> 1. "In 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."
>
> Staring at the langref, i don't see where it assumes this.

> it is just offset, size, tbaa type, which seems correct to me.
>
> If you mean "the implementation assumes", then yeah, the
> implementation should just be fixed.

>
> "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 thefunctions
> it calls) will have to acts as if all of the unions members could have been
> accessed. "

>
> Actually, for correctness, it just has to give a conservative answer
> of "may-alias"

>
> This is papering over the fact that if it does that, basicaa overrides it.

> That we should just fix that, not rely on making TBAA work harder to
> be correct (working harder to optimize is fine).

>
> That is, say "these are may-alias, this is a final answer" instead
> of "these are may-alias, maybe you can do better?"

>
> But yes, if you are trying to optimize unions harder (and i don't
> know why you would :P), yes, you'd have to follow all intersecting members.

> In gcc we just sort the list, and use offset, size info to see what
>  fields it overlaps with.

>
> But note: Your correctness still depends on being able to tell these
> are union accesses.

> That's bad, because as sanjoy says, we do transforms that may cause
> this to be non-recoverable.

>
> If you can't have TBAA say "may-alias, final answer", you lose.

>
> (Note, while you are improving this, i'll note the info should also
> be used to differentiate structure fields and solve the issue discussed here:

> http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160523/date.html
>
> The offset, size info is useful and should be used to differentiate
> struct accesses *regardless of type* in cases where we can.

> It doesn't actually matter if one field is an int and the other a
> float. If they are different fields, and we can prove it, they can't
> alias anyway)


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.

Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.
From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <perrons@...> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.





_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.






_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
Pardon my exclamation, are you saying TBAA will return NoAlias between union members under current implementation?
If so, this is definitely a concern.

Kevin

On Wed, Mar 1, 2017 at 3:30 PM, Daniel Berlin via llvm-dev <[hidden email]> wrote:
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.






_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
Yes.
Clang generates tbaa trees that are not conservatively correct in the face of unions, for any definition of correct you have :)

We mostly rely on basicaa to say things are must-alias, but if it says may-alias, in the case of unions, tbaa will often say "noalias".



On Wed, Mar 1, 2017, 4:00 PM Flamedoge <[hidden email]> wrote:
Pardon my exclamation, are you saying TBAA will return NoAlias between union members under current implementation?
If so, this is definitely a concern.

Kevin

On Wed, Mar 1, 2017 at 3:30 PM, Daniel Berlin via llvm-dev <[hidden email]> wrote:
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.






_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
In reply to this post by Matthias Braun via llvm-dev
And, fwiw, the path walking issues are easy to fix.
What we did in GCC, and could be done here, is to generate the transitive closure of the children (or parents) as we saw them.
The height of the TBAA tree is not that large.
For scalar type nodes, this answers queries in O(1) time.
Even in offset land, you can use this, because if none of your children (parents) have that type, it can't alias, no matter what.
So it will cut off the query at the first point it is possible to discover that your path does not contain the type.
The worst case is that the exact path does contain the type, in which case you just made a few wasted queries.



On Wed, Mar 1, 2017 at 3:30 PM, Daniel Berlin <[hidden email]> wrote:
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.







_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
In reply to this post by Matthias Braun via llvm-dev

On 03/01/2017 05:30 PM, Daniel Berlin via llvm-dev wrote:
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

You mean making a 'scalar type node', because those represent 'or'?

 -Hal


(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.







_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
I could make something like Daniel's suggestion work.  The main question I still have is how we tell the difference between the "old-style" DAG and the "new-style" DAG?  I don't know if there is some standard way of doing this.  Do we just base it on the version of llvm-ir?
 
Would there be a need to maintain different code for both type of DAG?  If we change clang to generate the new-style DAG, things will be fine for C/C++.  However, will this force other components that generate llvm-ir to change?
 
In general, what kind of backwards compatibility do we need to keep?
 
Later,
Steven Perron


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
As far as my limited understanding goes, this should be a bugfix (correctness) and it should trump backward compatibility requirement. It makes no sense to me to continue backward compatible incorrectness.

Kevin

On Thu, Mar 9, 2017 at 10:21 AM, Steven Perron via llvm-dev <[hidden email]> wrote:
I could make something like Daniel's suggestion work.  The main question I still have is how we tell the difference between the "old-style" DAG and the "new-style" DAG?  I don't know if there is some standard way of doing this.  Do we just base it on the version of llvm-ir?
 
Would there be a need to maintain different code for both type of DAG?  If we change clang to generate the new-style DAG, things will be fine for C/C++.  However, will this force other components that generate llvm-ir to change?
 
In general, what kind of backwards compatibility do we need to keep?
 
Later,
Steven Perron


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
In reply to this post by Matthias Braun via llvm-dev


On 03/09/2017 12:21 PM, Steven Perron wrote:
I could make something like Daniel's suggestion work.  The main question I still have is how we tell the difference between the "old-style" DAG and the "new-style" DAG?  I don't know if there is some standard way of doing this.  Do we just base it on the version of llvm-ir?

We don't generally use IR version like that. Either make the format incompatible so that you can tell them apart, or we'll add a separate tag type (!tbaa2 or whatever).

 
Would there be a need to maintain different code for both type of DAG?  If we change clang to generate the new-style DAG, things will be fine for C/C++.  However, will this force other components that generate llvm-ir to change?
 
In general, what kind of backwards compatibility do we need to keep?

There are other frontends that generate TBAA, and there might not be a clear reason to make them change. The existing format is well defined, it just does not match C/C++ semantics well enough for our needs. On the other hand, if the new format subsumes the old one, we might just expect people to migrate. Let's make that decision separately. Assume for now that we'll have both at the same time and we'll change what Clang does.

 -Hal

 
Later,
Steven Perron


-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
In reply to this post by Matthias Braun via llvm-dev


On Thu, Mar 9, 2017 at 9:57 AM, Hal Finkel <[hidden email]> wrote:

On 03/01/2017 05:30 PM, Daniel Berlin via llvm-dev wrote:
So, https://bugs.llvm.org/show_bug.cgi?id=32056 is an example showing our current TBAA tree for union generation is definitely irretrievably broken.
I'll be honest here. I'm pretty sure your proposal doesn't go far enough.
But truthfully,  I would rather see us come closer to a representation we know works, which is GCC's.
Let me try to simplify what you are suggesting, and what we have.
Our current representation is basically inverted from GCC, but we don't allow things that would enable it to work.

Given
union {int a, short b};

GCC's will be:

 union
  /   \
short int


Everything is implicitly a subset of alias set 0 (which for C/C++ is char) just to avoid representing it.

Our metadata has no child links, and only a single parent link.

You can't represent the above form because you can't make a single short node a child  of every union/struct it needs to be (lack of multiple parents means you can't just frob them all to offset zero).

Your suggestion is to invert this as a struct

short  int
   |    / 
union

We don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special casing union-type nodes somehow

Let me suggest something different:

We know the current structure fails us in a number of ways.
Instead of trying to shoehorn this into our current structure, I suggest: we stop messing around and just have a GCC style tree, and represent the children instead of the parents.
We make contained types descendants instead of ancestors.
We allow multiple children at each offset and for scalar type nodes.x`

We could do that without changing to children, but honestly,  i strongly believe nobody who ever looks at this really understands it right now.
(If someone really does like the ancestor form, i'd love to understand why :P)

So if we are going to change it, we should change it to something that is easier to understand.

something like:

scalar type node -> {name, children nodes} 
struct node -> {name, array of {offset, child node} }

Paths are separate from the tbaa tree itself, and are just:
path node -> {struct node, offset} or whatever.

unions are just scalar type nodes with multiple children, not struct nodes with special-cased offset zero.

This also has a well-defined upgrade path.

For "old-style" DAGs, like exist now, we know we have to regen the metadata, and that it is wrong (So we could, for example, simply disable it for correctness reasons)
.
Anything with a "new-style" DAG, we know is usable.

In this representation, the most generic tbaa node is just the one that contains the other.
If neither contains the other, you can just make one that has both as children and use that.
(instead of now, where you'd have to have multiple parents again).

You mean making a 'scalar type node', because those represent 'or'?

Yes.
I would probably stop calling them scalar type nodes and struct type nodes too, while we are bike-shedding a bit :)

The terminology seems to be based on what we think a type system that generates those kinds of nodes look like.
But uh
1. That's wrong a lot of the time, because each frontend may want to use different types of nodes to be conservatively correct, and because different things can be represented, correctly, in multiple ways (IE, as a stupid example, you could represent any type as a struct node where all pieces go to the same place).

In fact, it's not even true for the few things that do generate TBAA trees right now.

2. It gives you no idea what they do in LLVM, which is, IMHO, what anyone reading those docs cares about.

I'd probably call them based on something related to their actual semantic in llvm's tbaa tree is.

IE i'd call scalar type nodes "or-type nodes" or "any of" nodes or something that gives people an idea that it means the aliasing result is may-alias if any path from that node is may-alias.
I'd call struct type nodes "offset-based nodes", becuase that's really what they are.

(access-path nodes are actually access paths, so that seems find)




 -Hal


(The above also may be better for other languages)

--Dan




On Tue, Feb 28, 2017 at 4:44 PM, Steven Perron <[hidden email]> wrote:
Seems like the comments have stopped.  I'll try to get a patch together.  Then we can continue the discussion from there.  

Hubert, as for the issue with the llvm optimizations losing the TBAA information, it should be the responsibility to make sure the aliasing is changed in the correct way.  One function related to this has already been mentioned:  getMostGenericTBAA.

Later,
Steven Perron



From:        Hubert Tong <[hidden email]>
To:        Steven Perron/Toronto/IBM@IBMCA
Cc:        Daniel Berlin <[hidden email]>, llvm-dev <[hidden email]>, Sanjoy Das <[hidden email]>
Date:        2017/02/15 07:44 AM
Subject:        Re: [llvm-dev] RFC: Representing unions in TBAA




On Tue, Feb 14, 2017 at 11:22 PM, Steven Perron <[hidden email]> wrote:
3) How should we handle a reference directly through a union, and a reference that is not through the union?  

My solution was to look for each member of the union overlaps the given offset, and see if any of those members aliased the other reference.  If no member aliases the other reference, then the answer is no alias.  Otherwise the answer is may alias.  The run time for this would be proportional to  "distance to the root" * "number of overlapping members".  This could be slow if there are unions with many members or many unions of unions.


Another option is to say that they do not alias.  This would mean that all references to unions must be explicitly through the union.

From what I gather from the thread so far, the access through the union may be lost because of LLVM transformations. I am not sure how, in the face of that, TBAA could indicate NoAlias safely (without the risk of functional-correctness issues in correct programs) between types which overlap within any union (within some portion of the program).

As for the standards, it is definitely not true that all references to unions must be explicitly through the union. However, if you are trying to perform union-based type punning (under C11), then it appears that it is intended that the read must be through the union.
 
This would be the least restrictive aliasing allowing the most optimization.  The implementation would be simple.  I believe we make the parent of the TBAA node for the union to be "omnipotent char".  This might be similar to treating the union TBAA node more like a scalar node instead of a struct-path.  Then the traversal of the TBAA nodes will be quick.  I'll have to work this out a bit more, but, if this is good enough to meet the requirements of the standard, I can try to think this through a little more.  I'll need Hubert and Daniel to comment on that since I am no expert on the C and C++ standards.

The third option is to be pessimistic and say "may alias" all of the time (conservatively correct), and rely on other alias analysis to improve it.  This will have good compile time, but could hinder optimization.  Personally I do not like this option.  Most of the time it will not have a negative effect, but there will be a reasonable number of programs where this will hurt optimization more that it needs to.







_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Representing unions in TBAA

Matthias Braun via llvm-dev
In reply to this post by Matthias Braun via llvm-dev


On 03/09/2017 12:58 PM, Flamedoge wrote:
As far as my limited understanding goes, this should be a bugfix (correctness) and it should trump backward compatibility requirement. It makes no sense to me to continue backward compatible incorrectness.

The TBAA scheme is internally self-consistent and there are other (non-C/C++) frontends that are using it in a completely well-defined way. The bug, as such, is in the mapping between C/C++ and the TBAA metadata. That, indeed, we'll just change once we have something to target that can correctly represent the required semantics.

 -Hal


Kevin

On Thu, Mar 9, 2017 at 10:21 AM, Steven Perron via llvm-dev <[hidden email]> wrote:
I could make something like Daniel's suggestion work.  The main question I still have is how we tell the difference between the "old-style" DAG and the "new-style" DAG?  I don't know if there is some standard way of doing this.  Do we just base it on the version of llvm-ir?
 
Would there be a need to maintain different code for both type of DAG?  If we change clang to generate the new-style DAG, things will be fine for C/C++.  However, will this force other components that generate llvm-ir to change?
 
In general, what kind of backwards compatibility do we need to keep?
 
Later,
Steven Perron


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
12345