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
Hi Steven,
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 PerronMotivation
The main motivation for this is functional correctness of code using unions.
See Invalid Bug ID 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
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 
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.
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 setC11 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.
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:
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)
Thanks Daniel and Sanjoy for you comments. I’ll try to list the issues I need to respond to, and double check my understand.
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.
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.
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.
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
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.
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
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
Pardon my exclamation, are you saying TBAA will return NoAlias between union members under current implementation?
If so, this is definitely a concern.
Kevin
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”.
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.
You mean making a ‘scalar type node’, because those represent ‘or’? -Hal
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
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
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). 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
So, 32056 – Invalid code generation (aliasing between scalar and vector type) 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 intEverything 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
> /
unionWe don't allow multiple parents, however.
Because of that, you suggest we follow all nodes for unions, special
casing union-type nodes somehowLet 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)
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