[LLVMdev] Optimization hints for "constant" loads

[Philip Reames]

On 10/21/2014 01:44 PM, Andrew Trick wrote:
>> On Oct 21, 2014, at 11:46 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:
>>
>> Thank you for the explanation, I think I misunderstood your solution
>> initially.  Is it accurate to say: by making the definition of the
>> source pointer of an !invariant load control (or data) dependent on
>> some initialization event, you can effectively separate the
>> initialization event (where the location is not invariant) and the
>> rest of the execution (where the location is invariant).
>>
>> This approach looks similar to Ruby's "freeze" method:
>> http://ruby-doc.org/core-2.1.3/Object.html#method-i-freeze
>>
>> What is the aliasing relationship between a non-invariant load from
>> the result of a safe_cast and a load from (or store to) the argument
>> we pass to it?  Is it sensible to make them MustAlias?  I'm trying to
>> think if a frontend needs to be careful about using the return value
>> of check_cast only for !invariant loads (or some other restriction),
>> or is it legal (or desirable) to mix and match both kinds of loads
>> from both kinds of pointers.
> %p1 = ...
> store %v0, %p1
> %p2 = llvm.safe_cast %p1
> store %v1, %p1
> store %v2, %p2
> %v3 = load %p2, !invariant
>
> The load can be moved above both stores (%v1 and %v2). AFAIK, the invariant metadata tag essentially tells alias analysis not to even try, just assume no aliasing. So the semantics effectively guarantee that %v0==%v1==%v3==%v3. The IR is still “legal” in that it is verifiable, but it is nonsense.
>
> Note that it is also totally valid for an alias analysis to return that they MustAlias. That would allow forwarding from store %v0 to the load. This would have to be implemented as a special case, since the invariant tag normally bypasses pointer analysis. I admit this is weird, but I’m don’t know of any problems it will cause. This can already happen with TBAA, and will be a problem with any metadata that can be abused by the frontend or language design. A difficultly with this approach is that the frontend has the burden for emitting guards anywhere the “invariant” data could be modified.
>
> How do you imagine mixing and matching invariant and non-invariant? I showed some examples of doing that safely, but I’m not sure how it’s relevant to you.
>
> -Andy
Ok, I'm catching up on this thread.  Let me summarize a couple of things 
I noticed while reading.

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.

The notions of "invariant over some range" and "safe to speculate over 
some range" are related, but distinct.  However, to get the most power 
out of the former, you often need the later.

Andy seems to be arguing in favour of data flow mostly because it's 
easier for the optimizer.  Unless I'm misreading, there's nothing 
preventing us from using control flow for the same patterns.  For example:
p1 = ...
*p1 = 5
p2 = llvm.safe_cast p1
p3 = select is_constant p2, p1
load p3

Is isomorphic with:
p1 = ...
*p1 = 5
if is_constant:
   invariant.start(p1)
load p1

Andy, is this correct?  Or am I missing something?

(p.s. You guys seem to be throwing around the terms "!invariant" and 
"invariant load" without clearly defining them.  I'm unsure if you mean 
the same things.)


I suspect this is going to be a topic we should discuss in person at the 
developers conference or over a beer at a social.  It's a bit 
complicated to keep track of in email.


My belief is that a path sensitive invariant indicator for a memory 
location is probably sufficient for most use cases.  In particular, the 
initialization and use logic is usually not in the same compilation for 
the cases I care about.  I care that such cases are *possible*, but I'm 
less concerned about them being *easy*.  I'm also having real trouble 
find examples of cases where Andy's "conditionally invariant data" is 
useful.  Given that we *have an existing* mechanism which only needs a 
slightly tweak for "endless" invariant regions, I'm tempted to stick 
with what we have.

The only change (clarification?) I'd make to the current scheme is to 
specify that a location is both invariant *and dereferenceable* at the 
point it is listed in an invariant.start.   This enables speculative 
loading up to that construct.  I think this is actually what the current 
intrinsic is trying for from the documentation.

(Hm.. it does make it hard to rearrange calls to invariant.start 
though...  Thoughts?)

I suspect that for the Array.length case, I'd probably do something like 
this:
arr = function_that_returns_array();
invariant.start(arr.length)
... arbitrary control flow ...
length = arr.length
... arbitrary control flow ...
length2 = arr.length

My reasoning here is that if something returns an array (in this 
compilation) I want the invariant fact to be visible.  If that factory 
function gets inlined, I'd end up with:
arr = new Array;
arr.length = X;
invariant.start(arr.length)
... arbitrary control flow ...
length = arr.length
... arbitrary control flow ...
length2 = arr.length

Both cases seem nearly ideal here.  I know I can lift the loads as far 
as the function which returns the base pointer.  I know I can value 
forward loads (either with or without lifting).  I know I can value 
forward the store to the load (as I normally would).

In terms of aliasing, it seems like having invariant.start read from 
it's arguments memory is sufficient.  That prevents reorderings of 
stores to that location before the address to after the 
invariant.start.  Due to conservative aliasing, that might be somewhat 
harmful, but I don't really see a way to avoid this...  (Or is this the 
point Andy's trying to solve with the data flow?)  I don't have a sense 
for how painful this is.  Try it and see?

I could see a useful extension for a function attribute (type?, TBAA?) 
for describing the return value's invariant fields (*at the point of the 
return*), but that is more minor goodness for IR size then clearly 
necessary.

Philip