[llvm-dev] RFC: Representing unions in TBAA
Sanjoy Das via llvm-dev
llvm-dev at lists.llvm.org
Sun Feb 12 22:50:13 PST 2017
Hi Steven,
On Sun, Feb 12, 2017 at 8:01 PM, Steven Perron via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I'm new to the llvm community. I'm learning how things work. I noticed
> that there has been some interest in improving how unions are handled. Bug
> 21725 is one example. I figured it might be a interesting place to start.
> I discussed this with a couple people, and below is a suggestion on how to
> represent unions. I would like some comments on how this fits in with how
> things are done in llvm.
>
> Later,
> Steven Perron
>
> Motivation
> ==========
>
> The main motivation for this is functional correctness of code using unions.
> See https://llvm.org/bugs/show_bug.cgi?id=21725for one example. The problem
> is
> that the basic alias analysis (or any other alias analysis) will not always
> have
> enough information to be able see that the two references definitely
> overlap.
> When this happens, the lack of alias information for unions could allow
> undesired optimizations.
>
> Current state
> =============
>
> For this RFC, we are interested in how the type based aliasing is
> represented
> for non-scalar data types. In C/C++, this will be arrays, structs, classes,
> and
> unions. We will not mention classes again because for this purpose they are
> the
> exact same as structs.
>
> We will start with structs. To help with the aliasing of structs, There is
> a
> format for the type based aliasing meta data known as the struct-path. Here
> is
> example IR:
>
> %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, %i32 2), align 4, !tbaa !2
> %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, %i32 3), align 4, !tbaa !7
> ...
> !2 = !{!3, !6, i64 800}
> !3 = !{!"S", !4, i64 0, !4, i64 400, !6, i64 800, !6, i64 804}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!"int", !4, i64 0}
> !7 = !{!3, !6, i64 804}
>
> The two loads are loads of different int members of the same struct. The
> type
> based aliasing gives them different meta data tags (!2 and !7). This allows
> the
> analysis to determine that they are different solely from the type based
> aliasing information. Looking at !2, it points to !3 with offset 800. This
> offset is used to identify which member of the struct is being accessed.
>
> Next we will consider arrays. When there is an array access, the type based
> aliasing views it as an access of the type of the element. In general, this
> is
> not a problem. For C/C++, there is no real difference between an array
> reference and a dereference of a pointer. However, this causes a lose of
> information when accessing arrays that are part of a struct or union.
>
> Here is an example:
>
> %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* getelementptr
> %inbounds (%struct.S, %struct.S* @s, i32 0, i32 0), i64 0, i64 %idxprom
> %1 = load i32, i32* %arrayidx, align 4, !tbaa !1
> ...
> !1 = !{!2, !2, i64 0}
> !2 = !{!"int", !3, i64 0}
>
> This is an access to an array of integers in a struct of type S. Note that
> the
> type on the load is "int". The type bases alias information has lost that
> this
> is a reference to a member of a struct.
>
> We finish by considering unions. Like arrays, an access to a member of a
> union
> is treated as if is it type of the type of the member being accessed. Here
> is
> an example:
>
> %4 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 0,
> i32 %0), align 4, !tbaa !2
> ...
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
>
> Here we lose the information that the reference is part of a union, so we
> cannot
> tell that this memory may overlap with something of a different type. Clang
> currently relies on other aliasing analysis like the basic alias analysis to
> observer that the two references are aliased.
>
> Proposed changes for arrays
> ===========================
>
> To deal with array references, they should be treated as if all array
> accesses
> are accesses to the first member of the array. For the purpose of type
> based
> aliasing, this should be good enough. The offset in the tag would be the
> offset of the start of the array plus, if applicable, the offset needed to
> access the member of the array element as if the element was a top-level
> struct
> member at offset 0. Note that the values for the indexing of the array is
> not
> included. Thus, accesses to an element of the last dimension of a
> multidimensional array appears the same as an access to a flattened version
> of
> the multidimensional array. Then, in the struct path, the array member's
> offset
> will be the starting offset of the array, as it is now. What will change in
> the
> struct path is the type node for the array. The type node will become the
> type
> of the array element instead of "omnipotent char", as it is now.
>
> This change is a must to be able to get union aliasing correct because we
> need
> to know when an array is part of a union that may overlap with other
> members.
>
>
>
> Proposed changes for unions
> ============================
>
> To properly deal with unions, there are a few issues that need to be dealt
> with.
>
> 1) Unions have to somehow be represented in the TBAA. As was pointed out
> above,
> this information is currently lost.
>
> 2) With the struct path TBAA, it is assumed that the length of a member
> extends
> to the start of the next. This will not be true for unions.
>
> 3) With the current struct path TBAA, you can determine which member is
> reference by looking at the offset. That is not true with unions because
> every
> member starts at offset 0. We will need another way of doing this for
> unions.
>
> Any solution we come up with will have to get around these three problems.
>
> To deal with unions, we will use the change in bug 21725 (see link above).
> This
> will treat a union as if it is a struct. However, the important change to
> make
> the unions work is that the length of the memory reference will have to be
> taken
> into consideration when looking at the type based aliasing. This should be
It was not clear how you'll take the length into consideration. Are
you talking about inferences like "I know the access was 4 bytes long,
so it can't be accessing the `short` field"? If so, we'd need to
verify (and maintain) that no passes ask AA about a subsegment of a
memory access (i.e. "does that store alias the first two bytes of this
i32 load"); or at least prevent them from using TBAA when they refine
their queries this way.
> easy
> enough because TypeBasedAAResult::alias takes two arguments of type
> MemoryLocation, and they contain the size information that is needed. This
> should easy take care of the first two problems.
>
> In TypeBasedAAResult::alias, we will also have to deal with the fact that
> unions
> have multiple members all at offset 0. This means that, unlike structs, the
> compiler will not be able to tell which member of the union the memory
> reference
> actually used. To deal with this, TypeBasedAAResult::alias (and the
> functions
> it calls) will have to acts as if all of the unions members could have been
> accessed. So the search along the tree will follow all of the member
> instead of
> just one as we currently do with structs. Changes to the algorithm can be
> made
> to avoid traversing the same TBAA nodes multiple times. The section at the
> end
> explores the consequences of this decision and a possible alternative.
I don't think this fully solves the problem -- you'll also need to fix
getMostGenericTBAA. That is, even if you implement the above scheme,
say you started out with:
union U {
int i;
float f;
};
float f(union U *u, int *ii, float *ff, bool c) {
if (c) {
*ii = 10;
*ff = 10.0;
} else {
u->i = 10; // S0
u->f = 10.0; // S1
}
return u->f;
}
(I presume you're trying to avoid reordering S0 and S1?)
SimplifyCFG or some other such pass may transform f to:
float f(union U *u, int *ii, float *ff, bool c) {
int *iptr = c ? ii : &(u->i);
int *fptr = c ? ff : &(u->f);
*iptr = 10; // S2
*fptr = 10.0; // S3
return u->f;
}
then getMostGenericTBAA will infer scalar "int" TBAA for S2 and scalar
"float" TBAA for S3, which will be NoAlias and allow the reordering
you were trying to avoid.
-- Sanjoy
>
> Examples
> ========
>
> Source code for the example
> ---------------------------
>
> struct S
> {
> int b;
> struct T
> {
> int a[10];
> } t;
> } s;
>
> struct C
> {
> int a;
> int b;
> };
>
> struct R
> {
> union {
> struct C a[10];
> struct C b[10];
> } u;
> int c;
> } r;
>
> union U
> {
> int i;
> float f;
> } u;
>
> struct Q
> {
> int a;
> union U u;
> } q;
>
> int foo()
> {
> return s.t.a[4] + s.b + r.u.b[3].b + u.i + u.f + q.u.i + q.u.f + q.a +
> r.c;
> }
>
> ----------------------------
> Current llvm-ir
> ----------------------------
>
> *** IR Dump Before Module Verifier ***
> ; Function Attrs: nounwind
> define signext i32 @foo() #0 {
> entry:
> %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
> %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 0), align 4, !tbaa !6
> %add = add nsw i32 %0, %1
> %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
> %add1 = add nsw i32 %add, %2
> %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 0,
> i32 0), align 4, !tbaa !2
> %add2 = add nsw i32 %add1, %3
> %conv = sitofp i32 %add2 to float
> %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa
> !11
> %add3 = fadd float %conv, %4
> %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 1, i32 0), align 4, !tbaa !2
> %conv4 = sitofp i32 %5 to float
> %add5 = fadd float %add3, %conv4
> %6 = load float, float* bitcast (%union.U* getelementptr inbounds
> (%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !11
> %add6 = fadd float %add5, %6
> %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 0), align 4, !tbaa !13
> %conv7 = sitofp i32 %7 to float
> %add8 = fadd float %add6, %conv7
> %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 1), align 4, !tbaa !15
> %conv9 = sitofp i32 %8 to float
> %add10 = fadd float %add8, %conv9
> %conv11 = fptosi float %add10 to i32
> ret i32 %conv11
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !3, i64 0}
> !7 = !{!"S", !3, i64 0, !8, i64 4}
> !8 = !{!"T", !4, i64 0}
> !9 = !{!10, !3, i64 4}
> !10 = !{!"C", !3, i64 0, !3, i64 4}
> !11 = !{!12, !12, i64 0}
> !12 = !{!"float", !4, i64 0}
> !13 = !{!14, !3, i64 0}
> !14 = !{!"Q", !3, i64 0, !4, i64 4}
> !15 = !{!16, !3, i64 80}
> !16 = !{!"R", !4, i64 0, !3, i64 80}
>
> ----------------------------
> Suggested new llvm-ir
> ----------------------------
>
> *** IR Dump Before Module Verifier ***
> ; Function Attrs: nounwind
> define signext i32 @foo() #0 {
> entry:
> %0 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 1, i32 0, i64 4), align 4, !tbaa !2
> %1 = load i32, i32* getelementptr inbounds (%struct.S, %struct.S* @s, i32
> 0, i32 0), align 4, !tbaa !6
> %add = add nsw i32 %0, %1
> %2 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 0, i32 0, i64 3, i32 1), align 4, !tbaa !9
> %add1 = add nsw i32 %add, %2
> %3 = load i32, i32* getelementptr inbounds (%union.U, %union.U* @u, i32 0,
> i32 0), align 4, !tbaa !18 // Need to change to
> reference the union "U", not just the scalar.
> %add2 = add nsw i32 %add1, %3
> %conv = sitofp i32 %add2 to float
> %4 = load float, float* bitcast (%union.U* @u to float*), align 4, !tbaa
> !11
> %add3 = fadd float %conv, %4
> %5 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 1, i32 0), align 4, !tbaa !19 // Need to reference the
> top level struct "Q", and not just the scalar.
> %conv4 = sitofp i32 %5 to float
> %add5 = fadd float %add3, %conv4
> %6 = load float, float* bitcast (%union.U* getelementptr inbounds
> (%struct.Q, %struct.Q* @q, i32 0, i32 1) to float*), align 4, !tbaa !20
> // Need to reference the struct "Q".
> %add6 = fadd float %add5, %6
> %7 = load i32, i32* getelementptr inbounds (%struct.Q, %struct.Q* @q, i32
> 0, i32 0), align 4, !tbaa !13
> %conv7 = sitofp i32 %7 to float
> %add8 = fadd float %add6, %conv7
> %8 = load i32, i32* getelementptr inbounds (%struct.R, %struct.R* @r, i32
> 0, i32 1), align 4, !tbaa !15
> %conv9 = sitofp i32 %8 to float
> %add10 = fadd float %add8, %conv9
> %conv11 = fptosi float %add10 to i32
> ret i32 %conv11
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!7, !3, i64 4} // Need to change to
> point to the struct "S" with the starting offset of the array.
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !3, i64 0}
> !7 = !{!"S", !3, i64 0, !8, i64 4}
> !8 = !{!"T", !3, i64 0} // Use "int" for the
> type of the array instead of "omnipotent char.".
> !9 = !{!16, !3, i64 44} // Point to the
> outermost struct "R" instead of "C". Add the offset of the array in "R" and
> the offset of the member in "C".
> !10 = !{!"C", !3, i64 0, !3, i64 4}
> !11 = !{!17, !12, i64 0} // Need to point to
> the union "U" instead of using the scalar.
> !12 = !{!"float", !4, i64 0}
> !13 = !{!14, !3, i64 0}
> !14 = !{!"Q", !3, i64 0, !17, i64 4} // Use the union "U"
> as the type for the member.
> !15 = !{!16, !3, i64 80}
> !16 = !{!"R", !21, i64 0, !3, i64 80} // Have the first
> member point to the union "R.u".
> !17 = !{!"U", !3, i64 0, !12, i64 0} // Introduce the
> struct path for the union.
> !18 = !{!17, !3, i64 0} // Tag for a union
> reference goes through the union.
> !19 = !{!14, !3, i64 4} // Tag for a union
> reference inside a struct points to the top level struct.
> !20 = !{!14, !11, i64 4} // Same as !19
> except for the float.
> !21 = !{!"R.u", !10, i64 0, !10, i64 0} // Add a struct path
> for the union defined in "R".
>
>
> Multiple members at the same offset
> ===================================
>
> Consider the following example:
>
> union U {
> int a;
> float b;
> };
>
> int foo( U * u, int * i, float * f )
> {
> *i = 0;
> *f = 100.0;
> return u->a;
> }
>
> With the changes I described above, the reference "u->a" will alias both
> "*i"
> and "*f" because, when we see the struct-path for the union, we will follow
> path
> for "a" and "b". This may be more conservative than we want. It might also
> be
> exactly what we want.
>
> The difficulty in being more precise is that, in general, we cannot know
> which
> member of the union was access with the current information in the llvm-ir.
> If
> we want to fix this we can create a new scalar to represent the members
> which will be used as the scalar meta data in the tag. Then, when a
> struct-path
> node for a union is reached, we will have to search each possible path to
> see if
> it reaches the scalar node on the tag. If it does, that is the path we
> follow.
>
> With this change, the llvm-ir for the example would be:
>
> define signext i32 @foo(%union.U* %u, i32* %i, float* %f) #0 {
> entry:
> store i32 0, i32* %i, align 4, !tbaa !2
> store float 1.000000e+02, float* %f, align 4, !tbaa !6
> %a = bitcast %union.U* %u to i32*
> %0 = load i32, i32* %a, align 4, !tbaa !11 // Use the new tag
> ret i32 %0
> }
>
> !0 = !{i32 1, !"PIC Level", i32 2}
> !1 = !{!"clang version 4.0.0 (trunk 290896)"}
> !2 = !{!3, !3, i64 0}
> !3 = !{!"int", !4, i64 0}
> !4 = !{!"omnipotent char", !5, i64 0}
> !5 = !{!"Simple C/C++ TBAA"}
> !6 = !{!7, !7, i64 0}
> !7 = !{!"float", !4, i64 0}
> !8 = !{!"U", !9, i64 0, !10, i64 0} // The struct path for the union
> with special members.
> !9 = !{!"U.a", !3, 0} // The member of the union.
> !10 = !{!"U.b", !7, 0} // The member of the union.
> !11 = !{!8, !9, 0} // The new tag where the scalar is
> the union member instead of the generic "int".
>
>
>
> Read versus write aliasing
> ==========================
>
> It has come to my attention that there is a question about whether the read
> versus write aliasing matters for union aliasing. Maybe there is something
> in
> the C/C++ specification I am missing, but I believe we need to handle this
> as
> well. Suppose we take an example similar to the one in defect 21725:
>
> #include <stdio.h>
>
> union U {
> short s;
> int i;
> } u;
>
> int v = 987;
> union U* up = &u;
>
> int foo()
> {
> int temp = u.s;
> up->i = 123; // 123
> printf("%d\n", up->i);
> printf("%hd\n", temp);
> return 0;
> }
>
> In this case, if the read of "u.s" is not aliased to the write of "up->i"
> and
> they are reordered, then "temp" could get the wrong value.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
More information about the llvm-dev
mailing list