[LLVMdev] Optimization hints for "constant" loads

[Andrew Trick]

> On Dec 1, 2014, at 2:21 PM, Philip Reames <listmail at philipreames.com> wrote:
> 
> 
> On 12/01/2014 11:14 AM, Andrew Trick wrote:
>> 
>>> On Oct 21, 2014, at 4:03 PM, Philip Reames <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote:
>>> 
>>> Sanjoy made a good point.  We don't actually need a new variant of "invariant.start".  Simply using an invariant.start with no uses gives us a notion of an invariant region with no end.  (Since the result doesn't escape, there can be no end hidden inside a function call.)   This seems like a simple notion to exploit and is strict step forward from where we are, without a new intrinsic.
>> 
>> I'm coming back to this because it is a sticking point for me in all of the proposals that were floated informally on the commits list. I would really like this to work, but can't prove that it's safe.
> As I said in the other thread, !invariant.load and llvm.invariant.* are not the same.  This thread is discussing the later, not the former.  The other thread is discussing the former, but not the later.  
>> 
>> Given:
>> 
>> %a = newArray()
>> %pLen = gep(%a, <length offset>)
>> invariant.start(<size>, %pLen)
>> %len = load %pLen
>> 
>> %o = foo() // may deallocate %a
>> store %something
>> load %o
>> 
>> I want to claim that the LLVM optimizer cannot do the following (but don't have a complete line of reasoning yet):
>> 
>> %a = newArray()
>> %pLen = gep(%a, <length offset>)
>> invariant.start(<size>, %pLen)
>> %len = load %pLen
>> 
>> %o = foo() // may deallocate %a
>> if ptrtoint(%o) == ptrtoint(%pLen)
>>   load %pLen
>>   store %something // Oops... this might alias
>> else
>>   store %something
>>   load %o
> Just to make sure we're on the same page, it *would* be legal for the optimizer to construct:
> %a = newArray()
> %pLen = gep(%a, <length offset>)
> invariant.start(<size>, %pLen)
> %len = load %pLen
> 
> %o = foo() // may deallocate %a
> if ptrtoint(%o) == ptrtoint(%pLen)
>   store %something // Oops... this might alias
>   load %pLen <--- This is now after the store
> else
>   store %something
>   load %o
> 
> Are we in agreement here?  

It’s fine in the sense that memory access has not been reordered… yet.

But is there an implicit invariant.end(%pLen) at the call to foo(), at which point the array can be freed and another object allocated in its place? I don’t think so. The way I interpreted the conclusion of this email thread is that invariant.start can be used without invariant.end. Since the token returned by the intrinsic never escapes, you can just assume the memory is invariant at all uses. The problem here is that the optimizer could (in theory) introduce new uses of the pointer after the object lifetime. This is the same problem that you yourself have raised. I hoped we could sidestep the problem because it crops up with any representation that attaches invariance to a pointer value. If we have an answer for this, then we can easily debate other representations like broadening !invariant.load metadata semantics and introducing new intrinsics.

-Andy

> 
> What is the argument that you see leading from the second to your problematic example?  I'm missing the reasoning by which you got there.  I agree that the example is problematic, I'm just not sure how it would arise.  
> 
> 
>> 
>> Either we need to make a convincing argument, or bail on most of the tentative proposals for expressing invariance, and resort to generating IR like this:
>> 
>> %a = newArray()
>> %pLen = gep(%a, <length offset>)
>> %t = invariant.start(<size>, %pLen)
>> %len = load %pLen
>> 
>> %o = foo() // may deallocate %a
>> invariant.end(%t, <size>, %pLen)
>> store %something
>> load %o
>> 
>> ...which is pretty painful to implement and may be very difficult to optimize.
>> 
>> -Andy
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141201/3c1e0dbc/attachment.html>