[llvm-dev] lifetime.start/end

[Johannes Doerfert via llvm-dev]

Hi Juneyoung,

Happy new year :)

After we had a lengthy discussion on phab last year, I've tried to 
summarize my thoughts,
especially given that I had some time to think about things over the break.
Still, no promises on the quality ;)

I start with general questions I asked myself and then go on rambling 
about a potential design.


Q1: Is lifetime a given property or a derived one, thus is it fixed or 
modifiable?

This is a question I asked myself a lot recently. I think it is derived 
and modifiable,
at least I hope it is. Only that would allow transformations I would want
us to do. Here are some examples:
   https://godbolt.org/z/G8obj3
   https://godbolt.org/z/obaTc


Q2: Is a pointer comparison, or similar use, extending the lifetime?

Asked differently, can we hoist a pointer comparison into a region where 
the pointer is dead?
This is an important question which we haven't discussed much as we 
assumed LICM has to work.

The current behavior is that non-dereferencing uses are not extending 
the lifetime and are
allowed outside of "lifetime regions" (as indicated by markers). They 
will always produce valid
results. Though, we might want to think about a lifetime marker that 
spits out a new pointer
value instead of reusing the old one.


Q3: Can we use lifetime to argue about addresses?

The question here is, can we fold address comparisons based on 
lifetimes, or not.

So far, we fold comparisons based on "address information". For example, 
we "know" globals,
allocas, and mallocs cannot be equal to one another. Also, two distinct 
allocations, for globals
and allocas, are considered unequal. Now, the crux is that we have to be 
consistent if we do two
comparisons, and, as of now, we are not (bug number missing). Since the 
backend (or any other place
for that matter) might coalesce allocas, their addresses might not be 
different after all. If we
already folded a comparison to "unequal" we are doomed if we later have 
a comparison that results
in "equal". (Note, this is different from aliasing rules as they can be 
stricter.)


Design:

I would hope we can come up with a model that treats memory "the same", 
regardless if it is global,
stack, or heap. I want to avoid special casing one of them wrt. lifetime 
as I believe most optimizations
would apply to any of them, potentially for different reasons and with 
different gains, but nevertheless.


Proposal (largely based on the conversation in phab):

A1: Lifetime is a concept that talks about memory content *only*. 
Basically, the memory content is set to
     undefined by lifetime markers. It is derived/modifiable as it is 
just an "as-is" property of the memory
     content. The lifetimes of an object, as described by markers, might 
change during the compilation. They
     might become smaller if we deduce the object is not accessed and 
the memory content is not used, they
     might become larger if objects with non-overlapping lifetimes are 
coalesced. (One could see the latter as
     introducing a new object though.)

A2: If we define lifetime as above, it has nothing to do with the 
address of an object. Consequently, pointer
     comparisons and similar operations are valid outside the lifetime. 
Loads and stores are as well, they can
     even not be removed "easily". A store followed by a lifetime marker 
or a load following a lifetime marker
     is dead or results in undef respectively.

A3: We could not use lifetime to argue about addresses. This means we 
could/should also not argue that overlapping
     lifetimes result in different addresses. Thus, a comparison between 
the address of two allocas could not
     immediately be folded. That said, there would be special cases 
though. Basically, if one of the allocas does
     not escape, other than the comparisons to be folded, we can fold 
them. Afterwards, coalescing or splitting
     would still be consistent because it is unobservable. The problem 
we have in-tree is that we fold even though
     the address is still observed (after the fold). It is still unclear 
to me what the impact of this would be
     on real code. I suggested before that we run some experiments first 
before we make any decision whatsoever.

This is pretty much saying that lifetime markers are `memset(undef)`, as 
you suggested before (I think).
There are some implementation level differences but at the end of the 
day they are basically the same.

Happy to hear some thoughts on this, especially if it fixes the problems 
that lead to D93376 in the first place.

~ Johannes


On 12/18/20 2:42 AM, Juneyoung Lee via llvm-dev wrote:
> Hello all,
>
> We're discussing the well-formedness of lifetime.start/end intrinsic here (
> https://reviews.llvm.org/D93376), deciding what is a (syntactically &
> semantically) valid use of these intrinsics.
>
> I'd like to gather more context about the intrinsics.
>
> 1. Is there a frontend or framework that introduces lifetime call with
> non-stack allocated objects?
> If exists, which behavior do they expect from it?
>
> 2. Can a block's lifetime be started bytewise or elementwise?
> I imagine an optimization that allow using stack very compactly, but wonder
> there is a real-world use case.
>
> Thanks,
> Juneyoung
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev