<div dir="ltr"><div dir="ltr">> No, you mix things up here.<br>
><br>> Nobody proposed to modify the semantics of `alloca`.<br>> `alloca` provides you with a fresh, unobserved block of<br>> dereferenceable memory that is implicitly freed as the stack<br>> unwinds. That is it. No context necessary.<br><br></div><div>It is, alloca must have its integral address decided at its *allocation* time as well, like 0xFF00... .</div><div><br></div><div>For example, if 0xFFFF0000 ~ 0xFF000000 is already allocated, the new alloca cannot be placed there unless it is not observed in the future, according to your proposal.<br><br></div><div>But how do we know from the current state whether the stack variable is going to be observed or not?<br></div><div>It is like writing an interpreter for IR; we cannot write an interpreter that relies on the future memory state to make the current step.<br></div><div><br></div><div>Making icmp/ptrtoint yield poison will still make loop versioning or pointer rewriting transformations unsound because these operations now can create poison (even if pointers are noundef).</div><div><br></div><div>> What I proposed is twofold:<br>
></div><div>> 1) We stop folding comparisons between different allocas if changing the <br>> address<br>> of both might be observable. Thus, if both might have their address <br>> "taken"/escaped,<br>> other than the comparisons we want to fold, we cannot proceed.<br></div><div>></div><div>> 2) We define lifetime markers to mean `memset(undef)`.<br></div><div><br></div><div>2) is fine, I think the suggestion semantically makes sense perfectly. 1) is something I'm concerned about now.</div><div><br></div><div>There are more than pointer foldings, such as rewriting such expression, code motion ptr cmp, introduce ptr cmp, etc. There is also analysis relying on ptr cmp.</div><div>Defining the correctness of each of them is something we want to avoid, and maybe that's why we want to define precise semantics for things.</div><div><br></div><div><br></div><div>If the sudden textual change at lifetime intrinsics is a concern, maybe we can have a migration time and make the Verifier raise a warning if lifetime is used with an unknown pointer.<br></div><div>I think this will be less aggressive and may give nice feedback to potential projects that are using lifetime with non-alloca.</div><div>At the end, we can implement IR writer that lowers lifetime with non-alloca into memset(undef). WDYT?</div><div><br></div><div>Thanks,</div><div>Juneyoung</div><div><br></div><div class="gmail_quote"><div>p.s. The reply was late, sorry. I think I can spend more time on this today.</div><div><br></div><div></div><div dir="ltr" class="gmail_attr">On Thu, Jan 7, 2021 at 9:02 AM Johannes Doerfert <<a href="mailto:johannesdoerfert@gmail.com">johannesdoerfert@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
On 1/6/21 4:33 PM, Juneyoung Lee wrote:<br>
>>> Stepwisely defining the semantics of instructions is a desirable<br>
> direction<br>
>>> IMO.<br>
>> I'm confused. What in the proposal would prevent us from defining<br>
>> the semantics of instructions, or force us to do it in an "undesirable<br>
> way"?<br>
><br>
> I meant it would be great if the output state after executing an<br>
> instruction can be described using its input state.<br>
> (that was the meaning of 'stepwise semantics', I should have been more<br>
> clear about this)<br>
><br>
> For example, the semantics of 'z = add x y' can be defined as follows:<br>
> Given an input state s, next state s' = s[z -> s(x) + s(y)]<br>
> where s(x) is the value of x in the previous state, and s[z -> v] is a<br>
> state with z updated to v.<br>
><br>
> Another example that involves memory: the semantics of 'i = ptrtoint p' can<br>
> be defined as follows:<br>
> Given an input state s, next state s' = s[i -> s(p).obj.address +<br>
> s(p).offset]<br>
> where obj.address is the begin address of a memory object obj pointed by p<br>
> & offset is p's byte offset. (Imagine a pointer to the offset of some char<br>
> array).<br>
> Note that ptrtoint & add can be nicely defined w.r.t the input state.<br>
><br>
><br>
> Now, the instruction that we're facing is 'p = alloca'.<br>
> To describe the output state after executing 'p = alloca', the address of<br>
> new alloca should be determined.<br>
> If observedness is involved, we need to know the future state again. :/ We<br>
> don't know whether the alloca is going to be observed or not without seeing<br>
> the future.<br>
> This is the problem of the current lifetime intrinsics as well.<br>
<br>
No, you mix things up here.<br>
<br>
Nobody proposed to modify the semantics of `alloca`.<br>
`alloca` provides you with a fresh, unobserved block of<br>
dereferenceable memory that is implicitly freed as the stack<br>
unwinds. That is it. No context necessary.<br>
<br>
If you want to modify the IR, you need to argue the observable<br>
semantics which is nothing new. That this might require more than<br>
a peephole view of the program is also not new.<br>
<br>
<br>
> One possible approach to resolve this is adding an 'unobserved' flag to<br>
> alloca instruction (similar to what was suggested by Nicolai).<br>
> And, we can say that if alloca with 'unobserved' is used by ptrtoint/icmp,<br>
> it is UB.<br>
<br>
The flag can be added, like we add other attributes. It should not<br>
be required for any optimization we talked about though. It basically<br>
is a way to manifest derived or given information into the IR.<br>
<br>
Attribute deduction, as well as frontends with domain knowledge,<br>
can add such information. The flag we discussed in phab was not even<br>
sufficient for all the transformation examples I presented in my mail,<br>
that is why I extended my argument. We could still have a "noescape"<br>
flag for allocas, but I'm not sure how useful that really is. We can<br>
certainly deduce it and manifest it, unsure if we have domain knowledge<br>
we can use for non-trivial cases though.<br>
<br>
<br>
> But this makes ptrtoint/icmp make UB-raising instructions, which<br>
> contradicts with what LLVM does.<br>
<br>
As with other violation of attributes I would, on first though, suggest<br>
to produce poison, not UB.<br>
<br>
<br>
> Also, existing optimizations like loop versioning can introduce<br>
> ptrtoint/pointer comparisons too.<br>
<br>
Sure. I am not certain why that is a problem. I get the feeling things<br>
are still mixed up here.<br>
<br>
What I proposed is twofold:<br>
<br>
1) We stop folding comparisons between different allocas if changing the <br>
address<br>
of both might be observable. Thus, if both might have their address <br>
"taken"/escaped,<br>
other than the comparisons we want to fold, we cannot proceed.<br>
<br>
2) We define lifetime markers to mean `memset(undef)`.<br>
<br>
The first should be sufficient for the problem you were trying to solve <br>
in the<br>
first place. The second makes lifetime markers less weird. Note that 1) <br>
is not changing<br>
the semantics of the IR. We basically just argue there is a bug in our <br>
instcombine right<br>
now as we do not check all necessary preconditions.<br>
<br>
<br>
><br>
> I see that there are other questions that I didn't answer yet, but let me<br>
> answer this first to limit the length of the text :)<br>
<br>
Sure, we can split the discussion :)<br>
<br>
~ Johannes<br>
<br>
<br>
><br>
> Thanks,<br>
> Juneyoung<br>
><br>
> On Thu, Jan 7, 2021 at 3:36 AM Johannes Doerfert <<a href="mailto:johannesdoerfert@gmail.com" target="_blank">johannesdoerfert@gmail.com</a>><br>
> wrote:<br>
><br>
>> On 1/5/21 8:00 PM, Juneyoung Lee wrote:<br>
>>> Hi Johannes,<br>
>>><br>
>>> I read your proposal and thought about the model.<br>
>> Cool, thanks!<br>
>><br>
>><br>
>>> As you concerned in A3, certain programs may be valid only when memory<br>
>>> blocks with overlapping lifetimes have disjoint addresses.<br>
>>> Look at this example (I'm using malloc, but alloca also works):<br>
>>><br>
>>> p1 = malloc(4)<br>
>>> p2 = malloc(4) // for brevity, assume that there as enough space & p1 and<br>
>>> p2 != null<br>
>>> set<char*> s;<br>
>>> s.insert(p1); s.insert(p2); // If the second insert did nothing, it would<br>
>>> be surprise to programmers<br>
>>> work(s);<br>
>>> free(data1)<br>
>>> free(data2)<br>
>>><br>
>>> Clearly, IR semantics should guarantee that escaped blocks are disjoint.<br>
>> It<br>
>>> would be great for verification tools on LLVM IR to be able to answer<br>
>> that<br>
>>> the second insert will succeed.<br>
>> I agree, the second insert should succeed, assuming `p1 && p2`.<br>
>> I don't think my proposal would in any way impact the program above,<br>
>> if anything the A3 reasoning makes sure such a program with allocas<br>
>> is not miscompiled.<br>
>><br>
>> I'm also not sure I understand what you try to argue for. Maybe<br>
>> elaborate a bit what it is you think is bad or needs to be changed.<br>
>><br>
>><br>
>>> The problem is that definition of escapedness is not clear at the<br>
>> semantic<br>
>>> level. Describing the IR semantics w.r.t. LLVM's escaped analysis<br>
>> function<br>
>>> isn't something we want.<br>
>>><br>
>>> Semantic definition of escapedness of a pointer seems hard, I mean in a<br>
>>> stepwise manner.<br>
>>> It isn't a single instruction such as 'escape i8* ptr', and we need to<br>
>> look<br>
>>> over all instructions in the function. For example, '(int)(p+1) - (int)p'<br>
>>> isn't semantically escaping the pointer p because the result is 1<br>
>>> regardless of the value of p.<br>
>>> Stepwisely defining the semantics of instructions is a desirable<br>
>> direction<br>
>>> IMO.<br>
>> I'm confused. What in the proposal would prevent us from defining<br>
>> the semantics of instructions, or force us to do it in an "undesirable<br>
>> way"?<br>
>><br>
>><br>
>>> In practice, syntactically checking escapedness + nice engineering might<br>
>>> not break optimizations in most cases (as undef/poison did); but it would<br>
>>> be great to move to another level, since LLVM IR is used in so many<br>
>> places<br>
>>> :)<br>
>> The property under which you can coalesce objects is simple:<br>
>> It is not observable.<br>
>><br>
>> Now, if the address of one of the two objects you coalesce is not<br>
>> observed, coalescing is not observable. That is a sufficient condition<br>
>> not a necessary one. Pointer "escaping" is one step further. If the<br>
>> address doesn't escape it is not observed. This does not mean the<br>
>> "semantic conditions for coalescing", e.g., for the purpose of translation<br>
>> validation, is supposed to be build on top of our "definition of escaping<br>
>> pointers". That said, we use "does not escape" as a precondition for<br>
>> various transformation and I'm unsure what is any different now. The<br>
>> entire escape argument is only used in the validity of the pointer folding.<br>
>> Similarly, we can fold a comparison of a noalias pointer with another one<br>
>> if the former does not escape (and both are dereferenced and one is<br>
>> written for sure).<br>
>><br>
>><br>
>>> The pointer comparison is another beast. It indeed has a few issues, and<br>
>>> solving it might require nontrivial solution.<br>
>> I think the main problem of the inconsistencies and such we've seen is<br>
>> rooted in the erroneous folding of pointer comparisons. Cleaning up the<br>
>> lifetime marker semantics is actually unrelated and simply not folding<br>
>> as described in A3 should solve the issue that has been reported.<br>
>> Nevertheless,<br>
>> we should take a crack at lifetime markers while we are here.<br>
>><br>
>><br>
>> ~ Johannes<br>
>><br>
>><br>
>><br>
>>> Thanks,<br>
>>> Juneyoung<br>
>>><br>
>>> On Tue, Jan 5, 2021 at 9:37 AM Johannes Doerfert <<br>
>> <a href="mailto:johannesdoerfert@gmail.com" target="_blank">johannesdoerfert@gmail.com</a>><br>
>>> wrote:<br>
>>><br>
>>>> 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<br>
>> 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<br>
>> 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,<br>
>> 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<br>
>> 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<br>
>> 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<br>
>> unclear<br>
>>>> to me what the impact of this would be<br>
>>>> on real code. I suggested before that we run some experiments<br>
>> 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<br>
>>>> 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<br>
>>>> 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>
>><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><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></div>