Hi Johannes,
I read your proposal and thought about the model.
As you concerned in A3, certain programs may be valid only when memory
blocks with overlapping lifetimes have disjoint addresses.
Look at this example (I'm using malloc, but alloca also works):
p1 = malloc(4)
p2 = malloc(4) // for brevity, assume that there as enough space & p1 and
p2 != null
set<char*> s;
s.insert(p1); s.insert(p2); // If the second insert did nothing, it would
be surprise to programmers
work(s);
free(data1)
free(data2)
Clearly, IR semantics should guarantee that escaped blocks are disjoint. It
would be great for verification tools on LLVM IR to be able to answer that
the second insert will succeed.
The problem is that definition of escapedness is not clear at the semantic
level. Describing the IR semantics w.r.t. LLVM's escaped analysis function
isn't something we want.
Semantic definition of escapedness of a pointer seems hard, I mean in a
stepwise manner.
It isn't a single instruction such as 'escape i8* ptr', and we need
to look
over all instructions in the function. For example, '(int)(p+1) -
(int)p'
isn't semantically escaping the pointer p because the result is 1
regardless of the value of p.
Stepwisely defining the semantics of instructions is a desirable direction
IMO.
In practice, syntactically checking escapedness + nice engineering might
not break optimizations in most cases (as undef/poison did); but it would
be great to move to another level, since LLVM IR is used in so many places
:)
The pointer comparison is another beast. It indeed has a few issues, and
solving it might require nontrivial solution.
Thanks,
Juneyoung
On Tue, Jan 5, 2021 at 9:37 AM Johannes Doerfert <johannesdoerfert at
gmail.com>
wrote:
> 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
>
--
Juneyoung Lee
Software Foundation Lab, Seoul National University
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210106/883aa025/attachment.html>