[LLVMdev] Request for comments: TBAA on call

[Daniel Berlin]

On Wed, Sep 25, 2013 at 5:50 PM, Filip Pizlo <fpizlo at apple.com> wrote:

> Hi all,
>
> TBAA on loads and stores is super useful for conveying high-level type
> knowledge to LLVM transformations.  But often translating a high-level
> language into LLVM IR will result in runtime calls that are known at the
> high level to only affect (either by reading or by writing) some restricted
> subset of the heap.  These aren't read-only calls; that is often too strong
> of a guarantee.  A great example would be a GC barrier or GC allocation
> that may arise if LLVM is used as a backend for a compiler for a
> higher-level language.  There are probably other examples that arise in
> high-level languages, but let's use allocation as an example for now.  I
> can envision two ways of representing allocation in LLVM IR:
>
> Method #1:
>
>             %object = call @runtime_allocate(... /* pass size and/or other
> data */)
>
> Method #2:
>
>         SomeBlock:
>             ... ; code preceding the allocation
>             %objectFast = ... ; IR for the inlined allocation fast path,
> which produces %objectFast but may yield null if the fast path fails and we
> need to take slow path
>             %didFail = icmp eq %objectFast, null
>             br %didFail, label %AllocationSlowPath, label &Continue
>         AllocationSlowPath:
>             %objectSlow = call @runtime_allocate_slow_path(... /* pass
> size and/or other data */)
>             br label %Continue
>         Continue:
>             %object = phi [%objectFast, SomeBlock], [%objectSlow,
> AllocationSlowPath]
>
> In both of these cases, the call instruction will appear to clobber the
> world leading to more pessimistic optimization.  Moreover, it's not always
> correct to mark the allocation as being readonly; it may read or write
> observable state.  But if you don't like the allocation example then you
> can imagine that a GC store barrier would have an almost identical pattern
> to #2 and it would definitely not be readonly.  Anyway, such a pattern
> would lead to fewer loads being eliminated or hoisted, fewer stores being
> eliminated or sunk, etc - all due to those pesky calls.  But the high-level
> code generator that produces this IR will know for sure that
> @runtime_allocate or @runtime_allocate_slow_path can only affect a very
> narrow subset of the heap: namely, it will only read and write the GC's
> data structures.  So most of the loads and stores surrounding the
> allocation, that arose from source-level loads and stores, would definitely
> not have any interference with the call and this would !
>  be easy to convey using TBAA.
>
> Hence if we could decorate the calls to these runtime functions as only
> reading or writing certain TBAA types,


Out of curiosity, why is this tied to TBAA types, rather than variables or
something else?
IE what analysis are you performing that gives you type answers instead of
answers in terms of local/global variables?
The information you are talking about here is traditional mod/ref info that
is completely independent of TBAA.

The more specific the info you can get from the metadata, the better off
you are eliminating loads/stores

Otherwise, yes, it's certainly incredibly helpful to the other
optimizations.

However, unless there is a good reason, i'd suggest you just make it
generic call read/write metadata that talks about values (be they incoming
arguments, alloca'd memory, or whatever else).

It's actually a lot easier to reason about individual heap values than
entire types, unless, again, you only have an analysis that is providing
answers about types (or your plan was simply to use the existing TBAA info
and do a bottom-up closure over the entire callgraph, which would provide
some value, but lose a lot of info due to external function calls)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131007/9132c4ae/attachment.html>