Rafael EspĂndola
2012-Dec-28 12:20 UTC
[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.> NickCheers, Rafael
Nick Lewycky
2012-Dec-28 18:00 UTC
[LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
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 >
Krzysztof Parzyszek
2012-Dec-28 18:10 UTC
[LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
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
Maybe Matching Threads
- [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
- [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
- [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
- [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?
- [LLVMdev] Can simplifycfg kill llvm.lifetime intrinsics?