<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr">Hi Johannes,<div><br></div><div>I read your proposal and thought about the model.</div><div><br></div><div>As you concerned in A3, certain programs may be valid only when memory blocks with overlapping lifetimes have disjoint addresses.</div><div style="color:rgb(0,0,0)">Look at this example (I'm using malloc, but alloca also works):</div><div style="color:rgb(0,0,0)"><br></div><div><font face="monospace">p1 = malloc(4)<br></font></div><div><font face="monospace">p2 = malloc(4) // for brevity, assume that there as enough space & p1 and p2 != null</font></div><div><font face="monospace">set<char*> s;</font></div><div><font face="monospace">s.insert(p1); <font color="#0000ff">s.insert(p2);</font> // If the <font color="#0000ff">second insert</font> did nothing, it would be surprise to programmers</font></div><div><font face="monospace">work(s);</font></div><div><font face="monospace">free(data1)<br></font></div><div><font face="monospace">free(data2)</font></div><div><br></div><div>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.</div><div><br></div><div><span style="color:rgb(0,0,0)">The problem is that definition of escapedness is not clear at the semantic level. </span>Describing the IR semantics w.r.t. LLVM's escaped analysis function isn't something we want.</div><div><br></div><div>Semantic definition of escapedness of a pointer seems hard, I mean in a stepwise manner.</div><div>It isn't a single instruction such as '<font face="monospace">escape i8* ptr</font>', 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.</div><div>Stepwisely defining the semantics of instructions is a desirable direction IMO.</div><div><br></div><div>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 :)</div><div><br></div><div>The pointer comparison is another beast. It indeed has a few issues, and solving it might require nontrivial solution.</div><div><br></div><div>Thanks,</div><div>Juneyoung</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jan 5, 2021 at 9:37 AM Johannes Doerfert <<a href="mailto:johannesdoerfert@gmail.com" target="_blank">johannesdoerfert@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi Juneyoung,<br>
<br>
Happy new year :)<br>
<br>
After we had a lengthy discussion on phab last year, I've tried to <br>
summarize my thoughts,<br>
especially given that I had some time to think about things over the break.<br>
Still, no promises on the quality ;)<br>
<br>
I start with general questions I asked myself and then go on rambling <br>
about a potential design.<br>
<br>
<br>
Q1: Is lifetime a given property or a derived one, thus is it fixed or <br>
modifiable?<br>
<br>
This is a question I asked myself a lot recently. I think it is derived <br>
and modifiable,<br>
at least I hope it is. Only that would allow transformations I would want<br>
us to do. Here are some examples:<br>
<a href="https://godbolt.org/z/G8obj3" rel="noreferrer" target="_blank">https://godbolt.org/z/G8obj3</a><br>
<a href="https://godbolt.org/z/obaTc" rel="noreferrer" target="_blank">https://godbolt.org/z/obaTc</a><br>
<br>
<br>
Q2: Is a pointer comparison, or similar use, extending the lifetime?<br>
<br>
Asked differently, can we hoist a pointer comparison into a region where <br>
the pointer is dead?<br>
This is an important question which we haven't discussed much as we <br>
assumed LICM has to work.<br>
<br>
The current behavior is that non-dereferencing uses are not extending <br>
the lifetime and are<br>
allowed outside of "lifetime regions" (as indicated by markers). They <br>
will always produce valid<br>
results. Though, we might want to think about a lifetime marker that <br>
spits out a new pointer<br>
value instead of reusing the old one.<br>
<br>
<br>
Q3: Can we use lifetime to argue about addresses?<br>
<br>
The question here is, can we fold address comparisons based on <br>
lifetimes, or not.<br>
<br>
So far, we fold comparisons based on "address information". For example, <br>
we "know" globals,<br>
allocas, and mallocs cannot be equal to one another. Also, two distinct <br>
allocations, for globals<br>
and allocas, are considered unequal. Now, the crux is that we have to be <br>
consistent if we do two<br>
comparisons, and, as of now, we are not (bug number missing). Since the <br>
backend (or any other place<br>
for that matter) might coalesce allocas, their addresses might not be <br>
different after all. If we<br>
already folded a comparison to "unequal" we are doomed if we later have <br>
a comparison that results<br>
in "equal". (Note, this is different from aliasing rules as they can be <br>
stricter.)<br>
<br>
<br>
Design:<br>
<br>
I would hope we can come up with a model that treats memory "the same", <br>
regardless if it is global,<br>
stack, or heap. I want to avoid special casing one of them wrt. lifetime <br>
as I believe most optimizations<br>
would apply to any of them, potentially for different reasons and with <br>
different gains, but nevertheless.<br>
<br>
<br>
Proposal (largely based on the conversation in phab):<br>
<br>
A1: Lifetime is a concept that talks about memory content *only*. <br>
Basically, the memory content is set to<br>
undefined by lifetime markers. It is derived/modifiable as it is <br>
just an "as-is" property of the memory<br>
content. The lifetimes of an object, as described by markers, might <br>
change during the compilation. They<br>
might become smaller if we deduce the object is not accessed and <br>
the memory content is not used, they<br>
might become larger if objects with non-overlapping lifetimes are <br>
coalesced. (One could see the latter as<br>
introducing a new object though.)<br>
<br>
A2: If we define lifetime as above, it has nothing to do with the <br>
address of an object. Consequently, pointer<br>
comparisons and similar operations are valid outside the lifetime. <br>
Loads and stores are as well, they can<br>
even not be removed "easily". A store followed by a lifetime marker <br>
or a load following a lifetime marker<br>
is dead or results in undef respectively.<br>
<br>
A3: We could not use lifetime to argue about addresses. This means we <br>
could/should also not argue that overlapping<br>
lifetimes result in different addresses. Thus, a comparison between <br>
the address of two allocas could not<br>
immediately be folded. That said, there would be special cases <br>
though. Basically, if one of the allocas does<br>
not escape, other than the comparisons to be folded, we can fold <br>
them. Afterwards, coalescing or splitting<br>
would still be consistent because it is unobservable. The problem <br>
we have in-tree is that we fold even though<br>
the address is still observed (after the fold). It is still unclear <br>
to me what the impact of this would be<br>
on real code. I suggested before that we run some experiments first <br>
before we make any decision whatsoever.<br>
<br>
This is pretty much saying that lifetime markers are `memset(undef)`, as <br>
you suggested before (I think).<br>
There are some implementation level differences but at the end of the <br>
day they are basically the same.<br>
<br>
Happy to hear some thoughts on this, especially if it fixes the problems <br>
that lead to D93376 in the first place.<br>
<br>
~ Johannes<br>
<br>
<br>
On 12/18/20 2:42 AM, Juneyoung Lee via llvm-dev wrote:<br>
> Hello all,<br>
><br>
> We're discussing the well-formedness of lifetime.start/end intrinsic here (<br>
> <a href="https://reviews.llvm.org/D93376" rel="noreferrer" target="_blank">https://reviews.llvm.org/D93376</a>), deciding what is a (syntactically &<br>
> semantically) valid use of these intrinsics.<br>
><br>
> I'd like to gather more context about the intrinsics.<br>
><br>
> 1. Is there a frontend or framework that introduces lifetime call with<br>
> non-stack allocated objects?<br>
> If exists, which behavior do they expect from it?<br>
><br>
> 2. Can a block's lifetime be started bytewise or elementwise?<br>
> I imagine an optimization that allow using stack very compactly, but wonder<br>
> there is a real-world use case.<br>
><br>
> Thanks,<br>
> Juneyoung<br>
><br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br clear="all"></div></div></div></div></div></div></div></div></div></div><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><br></div><font size="1">Juneyoung Lee</font><div><font size="1">Software Foundation Lab, Seoul National University</font></div></div></div>