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