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

> 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

On 12/28/2012 04:20 AM, Rafael Espíndola wrote:
>> 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?
Right. There's no reason start2 and end2 couldn't be the exact same 
Instruction*'s as start1 and end1 here, but I'm starting with an example
where those are the only starts and ends that run.
>> 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.
I'm not so sure about this.

First, stack and heap allocation really start with the bit true. It's 
safe to call alloca or malloc and then start using the pointer. I don't 
want to teach the frontend to put lifetime.start on every possible 
allocation point.

Making two llvm.lifetime.start call be a no-op is really bad for the 
optimizers to work with. It means that just because you see an 
llvm.lifetime.start, you can't optimize *anything* with it, unless you 
prove the absence of an earlier lifetime.start -- anywhere in the 
program, interprocedurally. Consider DSE doing its upwards walk to find 
dead stores, and what it means when it sees a lifetime.start.

While this has a simpler semantic model, I don't think we will ever be 
able to optimize much code with it.

As an alternative model, I propose replacing lifetime.start/end with a 
single intrinsic that does the equivalent of 'store undef, %ptr' and 
nothing more.

Nick
> 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 tha
> 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
>

On 12/28/2012 12:00 PM, Nick Lewycky wrote:
>
> As an alternative model, I propose replacing lifetime.start/end with a
> single intrinsic that does the equivalent of 'store undef, %ptr'
and
> nothing more.
Couldn't we just insert the store?  Unless it's a volatile (or otherwise
ordered) location, the optimizer would be free to remove it.

-Krzysztof


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