Differential D31885
Remove TBAA information from LValues representing union members Authored by kparzysz on Apr 10 2017, 8:06 AM.
Details The TBAA information for union members may be wrong, and in the current form TBAA cannot represent them correctly. This is a follow-up to this thread from llvm-dev: This fixes http://llvm.org/PR32056
Diff Detail
Event Timeline
Comment Actions FYI: I gave it a try, and it looks like the union aliasing-related issue mentioned in Bug 32056 is not resolved by this patch. Comment Actions Disclaimer: I am not an LLVM developer. Just looking at the patch, I wonder if it could be much less intrusive if LValue CodeGenFunction::EmitLValue(const Expr *E) is split into two methods -- a private one, and a public-facing one that applies your ClearTBAA method. Comment Actions I'm not sure this is the right way to do this; I suspect we're lumping together a bunch of different bugs:
(1) and (3) are independent bugs. (1) if desired, should just be fixed (the vector type should be a child of the scalar element type in the current representation). (2) needs to be fixed too, is not strictly related to unions, and needs to be fixed in the backend. Doing this does not seem hard (we just need to record a Write Boolean in MemoryLocation and then check them in TypeBasedAAResult (TBAA can't be used if both locations are writes). (3) is what this should address. What we should do here is only generate the scalar TBAA for the union accesses. As I recall, the only reason that the scalar TBAA for union accesses is a problem is because of (2), but that's easy to fix in the backend (and we need to do that anyway). @dberlin , do you agree? Comment Actions This is not meant as a fine-grained solution to the TBAA problem, but a temporary fix for generating wrong information. Just yesterday I helped diagnose yet another problem related to this, so this issue is causing trouble out there. Comment Actions I understand. But temporary solutions have a tendency to become fairly long lived and I'd like to make sure we're not removing correct information (i.e. the scalar type information) along with the incorrect information. This has been broken for a long time, if it takes another few days to get a better fix then that's worthwhile. Comment Actions I pretty strongly agree that these are different bugs, and at the least, deserving of different patches as they have different tradeoffs/solutions. I'm not sure about the solution to #2, because i thought there were very specific points in time at which the effective type could change. In fact, i mostly believe tbaa doesn't belong in memory location, and that it should be looked up separately by the TBAA AA impl since that's the thing that should care about it. As we've repeatedly said, memory locations and pointers don't really have tbaa info, instructions do. We're really just trying to pass that along. Comment Actions
I think this is a key point. I'm not sure that there are specific points that the frontend can deduce: union U {
int i;
float f;
};
void bar1(int *i) {
*i = 0; // we just reset the type here
}
void bar2(float *f) {
*f = 0.0f; // we just reset the type here too
}
void foo(U *u) {
bar1(&u->i);
bar2(&u->f);
}Even if the union has structs instead of scalar types, I'm not sure that changes the situation. There certainly are situation where you can't silently change the types of objects in C++ just by starting to write a to differently-typed object at the same location, but I think that using this property relies on having some lifetime information for the objects in question, and so AA would need to be able to use this lifetime information to do more. This seems like an orthogonal issue (i.e. we can always add TBAA write <-> write ability in the presence of such lifetime information as an additional feature). Maybe I'm missing something...
I agree (and I think we'll need to do this in order to handle such lifetime information (and there are also issues around noalias handling that are relevant)). Comment Actions I'm not really concerned about the approach here---I can abandon this patch if you have something better. You have two testcases. One is based on an issue that our customer encountered. As long as TBAA doesn't produce false negatives, it's all good. Comment Actions Union type accesses must explicitly be made through a union if you want the effective type to change. If you don't make it an explicitly visible union access at each point, you will get wrong code, and this is pretty much unsolvable in general if you want tbaa to work at all. Because otherwise foo, bar1, and bar2 could all be in different translation units, in which case, you just destroyed all usefulness of tbaa because it has to assume all pointers can conflict with all pointers :) Comment Actions See https://bugs.llvm.org/show_bug.cgi?id=28189 for a testcase for (2) for this which doesn't involve unions. Comment Actions To expand a bit: In the above example, assuming you make the union accesses explicit, the union accesses themselves have to *always* conflict with all types in the union , and now you can do that if you know it's a union access., but you couldn't otherwise. Past that, you aren't going to be able to usefully differentiate between the current effective type of a union. There are a few other points where the effective type may change, but i believe the frontend does know about them (IE placement new, etc). Comment Actions Yes, this is what I had in mind. However, we may just want to not handle this at all. The demonstration you provide: #include <stdio.h>
#include <string.h>
#include <stdlib.h>
int f(int* x, int *y) {
*x = 10;
int z = *y;
*(float*)x = 1.0;
return z;
}
int (*ff)(int*,int*) = f;
int main() {
void* x = malloc(4);
printf("%d\n", ff(x, x));
}shows that the problem is more than I implied. To support this, we not only need to ignore the TBAA between the two writes (*x and *(float*)x), but also between the float write and the preceding int read. I wonder how much of TBAA we could keep at all and still support this. Thoughts? Comment Actions The standard is just kind of broken here, Comment Actions
How can you change the effective type of malloc'ed memory in C, if storing a value of a new type doesn't have any effect? memset? A new C language feature? Something else? Comment Actions In particular, i could have: foo.c: #include <stdio.h>
#include <string.h>
#include <stdlib.h>
int f(int* x, int *y) {
*x = 10;
int z = *y;
*(float*)x = 1.0;
return z;
}bar.c: extern int f(int *, int *)
int (*ff)(int*,int*) = f;
int main() {
void* x = malloc(4);
printf("%d\n", ff(x, x));
}In foo.c, there is no information you could ever use to tell you the *(float*) is legal or illegal. That is just a normal function :) Thus, GCC, et all have taken the position that if you change the effective type, it must be completely visible in all cases. Comment Actions memcpy is the traditional way, but in some sense it doesn't matter. Comment Actions To be clear, I'm find with disabling union tbaa until we can fix things for real. I'm somewhat concerned that this patch is quadratic in the AST. FWIW, I tried just setting TBAAPath = true in EmitLValueForField and then returning nullptr from CodeGenTBAA::getTBAAStructTagInfo when BaseQTy->isUnionType() is true. This mostly works, although it does not handle the array case as this patch does. Maybe putting some code in EmitArraySubscriptExpr will also take care of that? Comment Actions Thanks for CC'ing me. There are two problems here. The first is that vectors are aggregates which contain values of their element type. (And honestly, we may need to be more permissive than this because people are pretty lax about the element type in a vector until it comes time to actually use it.) We really can't be wishy-washy about casting a pointer-to-vector to a pointer-to-element and manipulating it as an array, or vice-versa — that's an incredibly common part of vector programming. But even if we wanted to be wishy-washy, there are language features which allow you to drill into a vector and access an element individually, and while you can't take the address of the result, it still generates an access of the element type which obviously aliases the entire vector. So we need to be modeling that, and hey, if we do that, we'll stop miscompiling this test case and can all go home. :) The second is that our alias-analysis philosophy says that the fact that two accesses "sufficiently obviously" can alias should always override TBAA. I have a hard time seeing what about the test cases I'm seeing makes it insufficiently obvious that the accesses alias. The accesses are ultimately derived from the same pointer; either the analysis is capable of counting to 32, in which case it should see that they definitely alias, or it is not, in which can it needs to assume that they might. Perhaps the existing AA interface is just inadequate? It seems to me that it can't express that middle-ground of "I have a concrete reason to think that these pointers are related but cannot answer for certain whether they overlap". Because if it could just answer that rather than having to downgrade all the way to MayAlias, it seems clear to me that (1) most memory transforms would treat it exactly the same as MayAlias but (2) it should be considered strong enough to suppress TBAA. John. Comment Actions I'm not sure i agree.
Just to note: Even assuming this wasn't crazytown, we certainly can't do it in the backend :) The answer in such a case is to disable TBAA on those accesses in the frontend and not emit it. Any notion that it can or should leave "mustalias" or other answers alone or something like this fails instantly to work, because aa not a perfect game. Further, AA should work okay in any order. The fact that we currently have to "override tbaa" is a bug and should be fixed by not emitting TBAA for those accesses, not by trying to override it after the fact in the backend (which, again, doesn't actually work :P) Comment Actions I'd be happy to address this, but I'm not sure how. Memoizing results could be one way, but don't know if that's acceptable. This location in codegen seems to be the last place where the original C/C++ types are available, in particular the information as to whether a type is a union or not. Maybe it would be possible to propagate some bit somewhere, but then this patch would become much less localized. Comment Actions There was a deliberate decision to make TBAA conservative about type punning in LLVM because, in practice, the strict form of TBAA you think we should follow has proven to be a failed optimization paradigm: it just leads users to globally disable TBAA, which is obviously a huge loss. This was never motivated purely by the nonsensicality of the standardization of unions. (And the nonsensicality of the standard very much continues. The code that we've all agreed is obviously being miscompiled here is still a strict violation of the "improved" union rules in C++, and if we decide to treat it as ill-formed we're going to break a massive amount of code (and vector code in particular heavily uses unions), because trust me, nobody is reliably placement-newing union fields when they're non-trivial. C++'s new rules are unworkable in part because they rely on C++-specific features that cannot be easily adopted in headers which need to be language-neutral.)
Well, thanks for calling me crazy, I guess. John. Comment Actions I think you have completely missed my point. i have not said we should be super strict,. We already aren't around unions. I"m fine with that. I'm saying "there is no DWIM like you are advocating we can reasonably define overall" and " whatever we do come up with, we can't do it in the backend". I don't believe a philosophy of "we come up with a reasonable interpretation and write it down" is a "failed paradigm" (it's also definitely not going to be DWIM). Compilers already are pretty nice about TBAA relative to what the standard says, as they must be. People who want to abide turn it on, those who don't, don't. Most actually *do* turn it on, contrary to your argument that it is a failed paradigm. You seem to be advocating for "if it's obvious they should alias, they should alias", but that is not amenable to any real implementation either, and we don't get whatever we thought was the right answer to this question right now anyway! So let me be concrete: How, precisely, do you propose we fix these bugs, such that they work 100% of the time, and do not require the backend to understand language rules? I see no path but to write a reasonable interpretation of the TBAA rules down, and then make the frontend emit TBAA that conforms to that. That is not what we do now. If you see another path, i'd love to know it.
??? I believe i have explained in detail why backend approaches fail. You can't tell the backend "hey, these accesses explicitly do not alias", and then expect it to somehow say they do, but only in the right cases.
Comment Actions
Okay, so the problem right now is that we're not conservative regarding union type punning, and while BasicAA sometimes fixes this for us, it doesn't always, and can't always, and so now we're miscompiling code. Removing the TBAA from union accesses would make us conservative. In the long term, I think we agree that we need a better way of actually representing unions in our TBAA representation. The question is what to do in the short term. Maybe there's some less drastic short-term solution that addresses these test cases?
I think we all agree that the vector types need to have their scalar (element) types as parents in the current TBAA representation. That's a separate change that we should just make. That, unfortunately, only fixes a subset of the union-related miscompiles. @rjmccall, if you agree that not adding TBAA to union accesses is reasonable at this stage, what do you think of this implementation of that goal? Comment Actions I'm not worried particularly about localization because we want to extend TBAA to support unions, etc. anyway. I suppose I don't understand how the propagation that is necessary here differs from what is necessary to propagate the base-type information for structs. Comment Actions We have it on by default. That has been acceptable to users precisely because we are conservative about punning. In contrast, GCC adopted very strict rules about punning that led basically everyone to turn off strict aliasing. That is what I am describing as a failed paradigm.
That's our current implementation. That's why TBAA delegates to BasicAA and allows it to override its judgement. That is not an accident.
I'm not saying the backend should magically understand language rules. Clearly language rules should be abstractly represented in IR in a way that can be interpreted. Case in point, we need to be representing the aliasability of vector types and their elements correctly in TBAA metadata. I'm saying that it's sometimes okay for frontends to rely on an operational understanding of how the backend uses that information, along with major exceptions and overrides to its analysis. For example, readonly/readnone have a basically behavioral semantics that doesn't actually constrain the operations carried out by the callee. This kind of analysis is appropriate for situations like this where we want to be generally aggressive as long as any resulting miscompiles are reasonably defensible, which in practice means not miscompiling sufficiently obvious instances of type-punning. Your proposal to we simply drop TBAA from all accesses related to unions is extremely conservative. It means that an access through a union has to be treated as potentially aliasing every other visible access, at least in terms of their types. That level of conservatism is not necessary in this case if we hew to the original understanding of LLVM's TBAA that punning is only allowed when it is sufficiently obvious. If you are interested in making a strict definition of "sufficiently obvious", and then arguing that it cannot possibly work, we can have that conversation; but right now I'm not seeing anything that says that our approach is basically broken, other you repeatedly asserting it because you think TBAA should be capable of completely standing alone. My proposal is that (1) we should correctly encode the aliasability of vector types in TBAA metadata and, separately, (2) we should also ensure that TBAA is correctly overridden by BasicAA in this case, which may require introducing an intermediate level of response between MayAlias and MustAlias. John. Comment Actions
Did you look at the large number of bugs that prompted this patch and discussions on the mailing list?
How do you see #2 working? It's quite literally not possible for basicaa to detect all cases it should override. If you want paper references on the strict breakdown of what can be decided statically, i'm happy to provide them. So i'd like to understand how you see it "correctly overriding in BasicAA". Comment Actions I agree that BasicAA "can't always", but I'm not sure it "can't often enough". Again, it seems to me that the low-level problem is just that the AA interface isn't designed for what we're trying to do with TBAA. "MayAlias" is the default answer for everything that can't be proven one way or the other, and "MustAlias" demands that the memory be actually known to overlap. If there were an intermediate "LikelyAlias" for pointers that are known to be related but BasicAA just doesn't know for certain whether the accesses overlap, then TBAA would turn itself off in those cases as long as at least a basic value-propagation pass has been run. That would put us on much firmer ground to say "it's reasonable for the compiler to assume that these things don't alias, and if you're going to use type-punning like this, you just need to rewrite your code to make it more obvious that the pointers are related". When you're given a language rule as weak as this, especially one that's so frequently violated, that's the only kind of argument which is going to have any traction with users. John. Comment Actions Just so i understand: Ignoring everything else (we can't actually make likelyalias work, i think the code in the bugs makes that very clear), you also believe we should effectively pessimize every other language that generates correct TBAA info for LLVM and will now no longer get optimized well because we've decided not to have clang emit TBAA metadata only in the cases where it actually wants TBAA applied? Comment Actions None of the code in the bugs I've seen makes that very clear, but perhaps I just missed the compelling example.
Are you under the impression that I'm proposing something new and that TBAA does not currently defer to BasicAA? Clang really does want TBAA applied to unions. I want LLVM to know that an access to a float through a union doesn't alias an arbitrary int* argument, even if the union includes an int. Anyway, TBAA tends to be less important in other languages, which tend to make much stronger non-type-based aliasing assumptions: functional languages assert that values are immutable, Fortran knows that arrays don't alias, Rust knows when references are unique, etc. John. Comment Actions Well, actually, chandler changed how it works, so it doesn't actually work quite the way it used to but it has the same effect ;) I'm saying "this approach does not work well now" (ie see bugs) , and i don't think continuing to try to make the contract even *more* incestuous is better than trying to make it *less*. I see literally no advantage to doing so, and plenty of disadvantage (pessimization of other languages, continuation of a pipeline ordering that requires overrides, etc) IE this is a thing we should be fixing, over time, to be a cleaner and better design, that does not make clang special here, and fixes these bugs. I have trouble seeing, why, if folks are willing to do that work, one would be opposed to it. I also ran it across 50 third party packages and spec2006 that use strict aliasing (These are just those things i could quickly test that had perf benchmarks) If it really caused any real perf loss, we could always define metadata to say these accesses are noalias if we can't prove they are mustalias. as an aside, I do not believe you could reasonably apply this to unions because it's not possible to tell people what to do differently when it's *llvm ir* that has the issue. IE i can't reasonably tell users "please stop doing things that don't generate explicit enough IR". If the frontend did it, i would likely have something reasonably to tell them. Comment Actions What I'm trying to get across is that you're not going to be able to completely eliminate the "incest" without making TBAA substantially more aggressive, in ways that aren't really acceptable and definitely not consistent with how we've always described LLVM's TBAA to users. I certainly would not feel comfortable ever switching Clang by default to a GCC-like model which will literally miscompile something as simple as: void foo(float *f) -> int { *f = /*something*/; return *(int*) f; } If you acknowledge that, then we can legitimately talk about the right way to get the behavior that we want. I would be fine with making that conservatism opt-in somehow, for example, especially if (as you suggest) we could use that to signal to BasicAA that it should not impose artificial limits on differentiating LikelyAlias from MayAlias. (I still think that that would be useful to allow this kind of LikelyAlias result, at least for TBAA's use. For example, the double* in the printf loop in the union-tbaa2.cpp test doesn't definitively overlap either store, but it's clearly still related enough that conservative-TBAA should be suppressed.)
This is interesting information, thank you. One obvious concern is that it almost certainly under-represents unions, which tend to be uncommon in benchmarks; benchmark swifts have also often be explicitly massaged to remove anything that could be described undefined behavior, which again is not consistent with the real world. But it does suggest that we could try it.
Yes, this seems like a direction we should be taking.
Specific simple patterns in the source language will reliably turn into specific patterns in the IR that we can guarantee are explicit enough. If you get a pointer value from some opaque source, assign it to a local variable, and then use it multiple times, the optimizer will reliably see that the pointer is the same at each use. Similarly if the pointer is just a local variable itself. That's basically all I would guarantee as "sufficiently obvious": the pointers are obviously derived from the same source. In these test cases, the accesses happen from different functions; but in order to be miscompiled they have to get inlined into one (unless we added some sort of cross-function AA, I suppose), which still admits the same kind of trivial pointer analysis. John. Comment Actions ...
Looking at this in more detail, we actually generate builtin-vector types which use char* as their access type (always, even for floating-point vectors). It is only the struct-path info which causes the issue for the test case here. It might be reasonable to make this less conservative, but that's another story... Comment Actions Unfortunately, probably not. The root problem there is that the design of vector types and vector interfaces is generally quite bad; you cannot rely on things like vectors being stored with an appropriate element type for whatever value the user is actually trying to work with. For example, Clang's xmmintrin.h specifies that m128 is a vector of 4 ints. How confident are you that that type is never used to store a vector of 4 floats? Keep in mind that the compiler allows m128 to freely implicitly convert to __v4sf. John. Comment Actions Sounds to me like we should just not apply struct-path TBAA data that runs through a union field because either LLVM's representation can't handle it or Clang isn't generating the representation right. That should be simple to do in a targeted place in Clang rather than awkwardly doing it retroactively like in the current patch. Comment Actions The TBAA information seems to be assembled from several smaller pieces during code generation. There is already a check for unions in EmitLValueForField, which turns off path TBAA information for union fields, but that is not sufficient to avoid problems. Both testcases will still fail with this code in place (the C++ testcase needs to be updated: it's missing "-O2 -std=c++11"). Comment Actions I'm not intimately familiar with clang, so if you know about a better place for doing this, please let me know. Comment Actions The right fix is probably just to make sure that EmitLValueForField doesn't add TBAA information when the base LValue doesn't have it. That will also fix problems with recursive member access where the base is may_alias. Comment Actions That won't work for arrays that are member of unions. We'd need to change EmitArraySubscriptExpr, which at some point calls MakeAddrLValue for the type being loaded/stored. MakeAddrLValue adds TBAAInfo for that type (unsigned short in case of the C testcase) and it does so regardless of any struct paths. This TBAA info must be removed for the testcase to be fixed. At that point we would have to examine the base expression to see if it refers to a union member, which is not different from the approach in this review. The LValue construction is done in a piecewise manner where some elements of the previously (recursively) created LValues may or may not be preserved. This makes me concerned that any more detailed attempt at fixing this may accidentally omit some case. Comment Actions That is a reasonable concern. Hmm. It seems to me that we do already propagate an important semantic property from the base l-value in every important case: the alignment source. That audit has already been done, and all you really need to do do is generalize it: look at all the places that generically propagate an AlignmentSource, e.g. EmitPointerWithAlignment and almost everywhere that calls LValue::getAlignmentSource(), and make them propagate an LValueBaseInfo (or whatever) instead. You can then make sure that may_alias-ness is stored in an LValueBaseInfo along with the alignment source, and then suppress TBAA when a base info is known to be may_alias, and then your temporary fix is just to make all union accesses unconditionally set may_alias to true. | ||||||
I'm not sure if this is a complete list of different ways to get a union member.