[llvm-dev] RFC: Resolving TBAA issues

[Hal Finkel via llvm-dev]

On 08/17/2017 07:20 PM, Daniel Berlin wrote:
>
>
> On Thu, Aug 17, 2017 at 4:49 PM, Hal Finkel <hfinkel at anl.gov 
> <mailto:hfinkel at anl.gov>> wrote:
>
>
>     On 08/17/2017 04:49 PM, Daniel Berlin via llvm-dev wrote:
>>
>>
>>
>>         For two given access sequences we can determine if the accessed
>>         objects are allowed to overlap by the rules of the input
>>         language.
>>
>>
>>     Sadly, this is where this becomes "unlikely to want to use to
>>     replace TBAA", at least for me. It may still be a thing we want
>>     anyway.
>
>     The rules proposed by Ivan for handling C/C++ seem pretty generic.
>
>
> Uh?
>
> "
>
>   [X...] is allowed to overlap with [S1..., X..., S2...]
>   and the most generic access sequence is [X...].
>
>   [X1..., X2...] is allowed to overlap with [S1..., X1...]
>   with the most generic access sequence to be [X1...].
>
>   [X1..., U, U::m1, X2...] is allowed to overlap with
>   [S1..., X1..., U, U::m2, S2...]
>   for a union U of an unknown effective type, provided m1 != m2
>   and the most generic access sequence is [X1..., U].
>
> If neither of the given sequences contains the leading access
> type of the other, then they are allowed to overlap if the
> leading access type of one sequence is a direct or indirect field
> of the final access type of the other sequence and then the most
> generic access sequence consists of a single element, which is
> that final access type.
>
> For the purpose of determining whether one type is a direct or
> indirect member of another type unions are considered to have no
> members as accesses to members of unions are only allowed to
> overlap if they have the base union object explicitly specified."
>
>
> This sounds super specific to me.  It talks about unions, and how they 
> behave in C/C++, etc.

I realize that it sounds super specific, but I'm not sure that it is. I 
was thinking about it in the following way: Imagine that we took the 
enhancement we previously discussed, but instead of implementing it 
directly, we just directly encoded for every access the path from the 
access type to the root. I think it would look very much like this 
proposal. You'd need some way of designating when you passed through a 
disjunctive node (where here we're calling "union", but the concept 
seems generic).

I need to think more about the direct/indirect access rules and what's 
being represented. I believe we end up recovering some of this 
information now because of the way that we track offsets. This might be 
better.

> It has initial sequence rules, etc.

How so?

> These would make no sense for "Rust", "Go", or "Haskell" at all.
>
>
>     We generally explain our current TBAA rules by saying that they're
>     generic but motivated by C/C++ rules.
>
>
> We do say that but that's not really what our implementation does in 
> any way.

Really? I thought it was motivated by C/C++ rules. When you say that 
it's "not really what our implementation does", is this because it drops 
a lot of potential information in the translation to our generic form?

>     I could say the same thing about this proposed system with its
>     proposed rules.
>
> It is, IMHO, nowhere near as generic.
>
>
>>
>>     This scheme is really an encoding of C/C++ TBAA info so it can be
>>     read by LLVM and requires that *LLVM* have some set of rules that
>>     it enforces about that scheme.
>>     But that scheme is still very language specific in how it is used.
>>     GCC still has something in between this and LLVM, where the
>>     language rules are a bit encoded (but not as much as you have).
>>
>>     We (and gcc) have deliberately avoided such schemes, in favor of
>>     transforming the info into abstract set trees that then tag loads
>>     and stores.
>>
>>     The encoding of "struct path" tbaa, is just a way of trading
>>     space vs time in that encoding.  We trade walking time for the
>>     space of transitive closure, etc.
>
>     If the provided statistic of 15% holds up, maybe which way we go
>     in this trade-off space doesn't matter much?
>
>
> Sure, that part i'm indifferent about.
>
>
>
>>
>>     None of the TBAA in LLVM really has any *real* relation to the
>>     original type system rules, and that is deliberate.  I've argued
>>     for years that calling it "TBAA" just badly confuses people, and
>>     i believe here is a good example :)
>>
>>     So i don't think what you've written can be used to replace TBAA.
>
>     So *if* we just take the proposed rules for C/C++ as the rules for
>     the scheme in general, I'm not sure this is true.
>
>
> Okay, let me try to rephrase a little more precisely:
> It is almost certainly true that we *could* make *any* particular 
> lowering work, at different costs to the front ends and middle ends.  
> IE i totally agree that the power of all of these systems (with small 
> extensions) are equal.  and also, for the record, i certainly think 
> the rules/scheme described here would almost certainly produce better 
> optimization results than what is currently implemented.
>
> *But*
> I don't see how you use this as a general scheme without ending up 
> forcing the other frontends to lower things to look as if it was a 
> C/C++ based type system.
> This is definitely *not* true today.
>
> They only have to lower things to look like a tree of sets.  Having 
> been down this path before, it's definitely easier to lower things to 
> look like trees of sets than like groups of C/C++ 
> structs/bitfields/etc that follow certain rules.

Our current TBAA has trees of structure types, essentially (lists of 
fields and offsets in each node). I don't understand how the mapping is 
easier or harder depending on whether we encode tree-node references vs. 
the path from the leaf to the root.

>
> This is one of the reasons I'm honestly having a lot of trouble seeing 
> how this is is definitively better than what IBM's proposal was, which 
> seemed both more generic and incremental, and handled most concerns.

The claim, as I understand it, is that this is more expressive. I'm 
trying to understand that.

>
> The only practical difference i see is that this just changes the 
> scheme from one where the language rules are mostly in the front ends 
> to one where the language rules are also partially in llvm.  To me 
> that isn't necessarily better, just different (heck, i'm even more 
> used to that system because it's a push closer to gcc :P)

Philosophically, this doesn't bother me too much provided that we can 
define the required semantics in terms of IR-level constructs (without 
direct appeal to some outside language standard). This seems to be true 
in this case. We have a lot of IR-level features that come about this 
way (where they have well defined, but seemingly arbitrary, semantics 
because of the source-level language semantics that motivated their 
creation).

>
> So overall I don't see one as particularly better than the other.
> You seem to.
> So i'd really like to understand your perspective on this in terms of 
> the pro/con that you are seeing.

I'm not sold yet (and may never be). I'm interested in exploring the 
alternative. Maybe we'll come up with some kind of hybrid design in the 
end, or maybe we'll go back to the previous proposal. When you say, "i 
certainly think the rules/scheme described here would almost certainly 
produce better optimization results than what is currently implemented." 
is this also true relative to our previous proposed enhancements?

In particular, I'd like to understand where this scheme is more 
expressive than our current one (and the current one plus proposed 
enhancement for unions/arrays).

>
> I mean, i'm  really not even opposed (though others may be) in 
> principle to saying "hey, let's just have a set of language specific 
> tbaa passes with semi-common metadata".

I'd rather not go there ;)

> I'd just like to understand why we would change tradeoffs, etc.

Me too.

Thanks again,
Hal

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170817/38ac2396/attachment.html>