llvm dev - Dec 2012 - [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?

>> Oh, I was reading "precedes/following" as having static
(dominance)
>> meaning. That is, in the above example you could not delete the store
>> since it is not true that
>> llvm.lifetime.end dominates it.
>>
>> Nick, is this what you had in mind? If not, then we must delete a
>> matching llvm.lifetime.end, but it is not clear how we define
>> "matching". In the following code some executions will hit
the first
>> llvm.lifetime.end and others will hit the second one.
>
>
> Yes, I meant at runtime.
>
OK, thanks. What is the meaning in the case of aliases? Should this work:

llvm.lifetime.start(%x)

...

llvm.lifetime.end(%y which alias %x sometimes)

If so, I guess that in order to delete a llvm.lifetime.start we have
to delete all llvm.lifetime.end that are "directly" reachable from it
and take an argument that may alias the one passed to
llvm.lifetime.start. Is that it? What about calling
llvm.lifetime.start in one function and llvm.lifetime.end in another?

It seems that deleting llvm.lifetime.start is impossible in general,
but it is safe to add one if at least one already exists, is that the
case?

On the other hand, removing llvm.lifetime.end should always be safe, right?

Cheers,
Rafael

On 12/27/2012 12:35 PM, Rafael Espíndola wrote:
>>> Oh, I was reading "precedes/following" as having static
(dominance)
>>> meaning. That is, in the above example you could not delete the
store
>>> since it is not true that
>>> llvm.lifetime.end dominates it.
>>>
>>> Nick, is this what you had in mind? If not, then we must delete a
>>> matching llvm.lifetime.end, but it is not clear how we define
>>> "matching". In the following code some executions will
hit the first
>>> llvm.lifetime.end and others will hit the second one.
>>
>>
>> Yes, I meant at runtime.
>>
>
> OK, thanks. What is the meaning in the case of aliases? Should this work:
>
> llvm.lifetime.start(%x)
>
> ...
>
> llvm.lifetime.end(%y which alias %x sometimes)
That's only a matching pair iff %x == %y at run time.

(If I wanted to require statically analyzable pairings, I would've made 
start return type {} and have the end intrinsic take that as an 
argument, like I did for the invariant intrinsics.)

You can almost entirely model lifetime.start and lifetime.end as being a 
store of undef to the address. However, they're the tiniest bit 
stronger. With a store of undef, you can delete stores that precede 
(with no intervening load) and loads that follow (with no intervening 
store). On top of that, a start lets you delete loads that precede, and 
an end lets you delete stores that follow.
> If so, I guess that in order to delete a llvm.lifetime.start we have
> to delete all llvm.lifetime.end that are "directly" reachable
from it
> and take an argument that may alias the one passed to
> llvm.lifetime.start. Is that it? What about calling
> llvm.lifetime.start in one function and llvm.lifetime.end in another?
>
> It seems that deleting llvm.lifetime.start is impossible in general,
> but it is safe to add one if at least one already exists, is that the
> case?
>
> On the other hand, removing llvm.lifetime.end should always be safe, right?
I really only invented them for a specific case, so I haven't thought 
through all the cases where it may or may not be legal to add or delete 
them. Here goes!

Suppose you have four lifetime operations on the same address in memory, 
with loads and stores all around them:

   start1--end1 .. start2--end2

If you remove start1 then you have a bare pointer, the memory came from 
somewhere and you lose the optimization that loads before start1 become 
undef, but you don't miscompile.

If you remove end1 then the code between start1 and start2 is in 
trouble. We would miscompile start1+store+load+start2 by folding the 
load to undef.

If you remove start2, we miscompile again. Accesses between start2 and 
end2 could be transformed into loads of undef and dead stores, and deleted.

Removing end2 only means that you get to assume the memory is still live 
since you haven't been told otherwise.

So ultimately the problem is with removing either part of the end->start 
transition. We need to make sure we don't remove one of those.

This means that the optimizer can't consider lifetime intrinsics to be 
no-ops unless it can prove it's looking at the first start or last end 
of that memory address. That's much worse than I thought it was when I 
first added these intrinsics. Sorry.

Nick

On Fri, Dec 28, 2012 at 12:35 AM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> >> Oh, I was reading "precedes/following" as having static
(dominance)
> >> meaning. That is, in the above example you could not delete the
store
> >> since it is not true that
> >> llvm.lifetime.end dominates it.
> >>
> >> Nick, is this what you had in mind? If not, then we must delete a
> >> matching llvm.lifetime.end, but it is not clear how we define
> >> "matching". In the following code some executions will
hit the first
> >> llvm.lifetime.end and others will hit the second one.
> >
> >
> > Yes, I meant at runtime.
> >
>
> OK, thanks. What is the meaning in the case of aliases? Should this work:
>
> llvm.lifetime.start(%x)
>
> ...
>
> llvm.lifetime.end(%y which alias %x sometimes)
>
I'm not sure if "sometimes" actually happens in the wild.
In recent patches to lifetime handling in ASan
I assumed that argument in llvm.lifetime intrinsic
can come from bitcasts or phi nodes, but all its possible values should
originate from the same alloca instruction.

>
> If so, I guess that in order to delete a llvm.lifetime.start we have
> to delete all llvm.lifetime.end that are "directly" reachable
from it
> and take an argument that may alias the one passed to
> llvm.lifetime.start. Is that it? What about calling
> llvm.lifetime.start in one function and llvm.lifetime.end in another?
>
I don't see how this can happen, assuming that arguments of llvm.lifetime
can only come from allocas.

>
> It seems that deleting llvm.lifetime.start is impossible in general,
> but it is safe to add one if at least one already exists, is that the
> case?
>
> On the other hand, removing llvm.lifetime.end should always be safe, right?
>
> Cheers,
> Rafael
>


-- 
Alexey Samsonov, MSK
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121228/c9578b89/attachment.html>

> Suppose you have four lifetime operations on the same address in memory,
> with loads and stores all around them:
>
>   start1--end1 .. start2--end2
>
> If you remove start1 then you have a bare pointer, the memory came from
> somewhere and you lose the optimization that loads before start1 become
> undef, but you don't miscompile.
This is assuming no looping after end1 or end2, right?
> If you remove end1 then the code between start1 and start2 is in trouble.
We
> would miscompile start1+store+load+start2 by folding the load to undef.
OK, my understanding was different. I was reading that a store before
all starts was invalid. BTW, can't we handle loads and stores
uniformly? That is, we can model them as

* We ask an oracle if a memory object will be used as an argument to
llvm.lifetime.start or llvm.lifetime.end. If it is, then the address
has an extra valid bit associated with it.

* At the creation of the object (stack or heap allocation) the bit is false.
* llvm.lifetime.start sets the bit to true. Doing it more than once is a nop.
* llvm.lifetime.end sets the bit to false.

With these rules, we can implement:

* Asan doesn't have an oracle, but can start tracking the bit when it
first gets to a llvm.lifetime.*. It can flag as invalid any operation
that touches memory with a false bit.
* Removing a llvm.lifetime.start is impossible in general, as we don't
know if some function will access that address.
* Removing a llvm.lifetime.end is always safe. It just extends the
life of the object, maybe until it is freed or the function that
called alloca returns.
* Adding a llvm.lifetime.start is always safe. It just extends the
life of the object.
> If you remove start2, we miscompile again. Accesses between start2 and end2
> could be transformed into loads of undef and dead stores, and deleted.
Agreed.
> Removing end2 only means that you get to assume the memory is still live
> since you haven't been told otherwise.
Agreed.
> So ultimately the problem is with removing either part of the end->start
> transition. We need to make sure we don't remove one of those.
>
> This means that the optimizer can't consider lifetime intrinsics to be
> no-ops unless it can prove it's looking at the first start or last end
of
> that memory address. That's much worse than I thought it was when I
first
> added these intrinsics. Sorry.
What do you think of the semantics I proposed above? I think they
still model what we want, but allow the optimizer to do any
optimizations it would do without them, as it can just add
llvm.lifetime.start and drop llvm.lifetime.end as needed.
> Nick
Cheers,
Rafael

> I don't see how this can happen, assuming that arguments of
llvm.lifetime
> can only come from allocas.
I think the intention was that it could also be used for
constructor/destructor calls on heap memory.

Cheers,
Rafael

On 12/28/2012 1:51 AM, Alexey Samsonov wrote:
> On Fri, Dec 28, 2012 at 12:35 AM, Rafael Espíndola
> <rafael.espindola at gmail.com <mailto:rafael.espindola at
gmail.com>> wrote:
>
>     What about calling
>     llvm.lifetime.start in one function and llvm.lifetime.end in another?
>
>
> I don't see how this can happen, assuming that arguments of
llvm.lifetime
> can only come from allocas.
It could happen after a cold section of a function was outlined, for 
example.  Informational intrinsics should not prohibit optimizations, 
and barring provably wrong cases, we need to assume that an optimization 
(possibly a future one) can transform code in a way that is not 
predictable up front.

-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation