llvm dev - Apr 2015 - [LLVMdev] where should volatileness really live in the AA API?

So, i'm working through the last of miniscule gvn optimizations, and
one of the things that gets tested is whether it will eliminate
non-volatile loads in favor of ohter non-volatile loads when there are
volatile loads in the way.


I.E.
define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
entry:
  %x = load i32, i32* %p
  %0 = load volatile i32, i32* %q
  %y = load i32, i32* %p
  %add = sub i32 %y, %x
  ret i32 %add
}


Currently, getModRefInfo will return Mod for getModRefInfo(%0,
AA->getLocation(%y))

This is because it punts on saying anything about ordered loads

I can certainly watch for this case in the caller, and ignore it if
it's volatile load vs non-volatile load. This is what MemDep does.

class Location is theoretically about pointers and sizes, but right
now, our struct Location in AA already has metadata tags and other
*instruction* specific info that it grabs from the instruction you
pass to getLocation. IE it includes noalias data that it tries to
match against other instructions.
So we already have broken this abstraction to return better answers :)


Is there a good reason it shouldn't also grab the
volatileness/orderedness from the original instruction, store it and
use it to try to give better getModRefInfo answers too?

Nothing that involves walking, sure, but it can trivially give the
same answer to this case, which is "the volatile load does not affect
the regular load".

On 3/31/2015 5:41 PM, Daniel Berlin wrote:
>
> class Location is theoretically about pointers and sizes, but right
> now, our struct Location in AA already has metadata tags and other
> *instruction* specific info that it grabs from the instruction you
> pass to getLocation. IE it includes noalias data that it tries to
> match against other instructions.
> So we already have broken this abstraction to return better answers :)
Is it using anything other than alias-related metadata?  My view is that 
volatileness does not belong in the alias analysis.  Noalias metadata 
helps directly with what AA does, so it makes sense to have it there. 
Volatileness, not so much.

-Krzysztof

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

On 03/31/2015 03:41 PM, Daniel Berlin wrote:
> So, i'm working through the last of miniscule gvn optimizations, and
> one of the things that gets tested is whether it will eliminate
> non-volatile loads in favor of ohter non-volatile loads when there are
> volatile loads in the way.
I'm pretty sure I'm the one who added that set of test cases. 
:)
> I.E.
> define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
> entry:
>    %x = load i32, i32* %p
>    %0 = load volatile i32, i32* %q
>    %y = load i32, i32* %p
>    %add = sub i32 %y, %x
>    ret i32 %add
> }
>
>
> Currently, getModRefInfo will return Mod for getModRefInfo(%0,
> AA->getLocation(%y))
>
> This is because it punts on saying anything about ordered loads
I think this is a conservatively correct, but non ideal answer.  A 
correct answer would also be to return Ref or NoModRef (depending on 
actual aliasing of the underlying locations).  Ordering is not an 
alasing property and should not be reported as such.  However, I believe 
a large number of callers may expect this and fleshing out all those 
bugs may not be fun.

Also worth commenting on is that *volatile* and *ordering* have 
distinctly different properties.  We couple them in a lot of odd ways, 
but the reasoning and legal optimizations are quite different.
> I can certainly watch for this case in the caller, and ignore it if
> it's volatile load vs non-volatile load. This is what MemDep does.
Can you point to the code you're talking about?  A volatile load 
encountered during the normal instruction walk is treated like any other 
(provided we know the query instruction is non-volatile.)  We are 
conservative about volatile stores, but that's on my list to fix.

Note that we are really conservative about volatile query instructions.  
We also haven't done anything for the callsite dependency path.  (I've 
never really understood why that needed to be a separate codepath, but 
that's a different issue.)
>
> class Location is theoretically about pointers and sizes, but right
> now, our struct Location in AA already has metadata tags and other
> *instruction* specific info that it grabs from the instruction you
> pass to getLocation. IE it includes noalias data that it tries to
> match against other instructions.
> So we already have broken this abstraction to return better answers :)
I disagree with your interpretation here.  The aliasing metadata does 
describe the location as seen by the instruction it's derived from.  
However, the alias metadata means that locations which would otherwise 
alias, no longer do.  In effect, we have many distinct locations which 
might happen to map to the same address.
> Is there a good reason it shouldn't also grab the
> volatileness/orderedness from the original instruction, store it and
> use it to try to give better getModRefInfo answers too?
>
> Nothing that involves walking, sure, but it can trivially give the
> same answer to this case, which is "the volatile load does not affect
> the regular load".
I strongly believe that ordering and aliasing are distinct properties.

I think in practice we have two different bits of functionality mixed 
together.  Actual alias analysis should be done strictly in terms of 
Locations.  The question on whether two locations might alias is 
independent of what semantics might be associated with a given pair of 
accesses that are mayalias.

I would have no problem with having the wrapper APIs - which ask 
questions about the interactions between instructions - using 
information about volatile and ordering.  I'm really really queasy with 
the idea of a "volatile location" vs a non-volatile location. There 
might be a workable semantic model here, but it seems much harder to 
reason about.

> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

----- Original Message -----
> From: "Krzysztof Parzyszek" <kparzysz at codeaurora.org>
> To: llvmdev at cs.uiuc.edu
> Sent: Wednesday, April 1, 2015 5:39:15 AM
> Subject: Re: [LLVMdev] where should volatileness really live in the AA API?
> 
> On 3/31/2015 5:41 PM, Daniel Berlin wrote:
> >
> > class Location is theoretically about pointers and sizes, but right
> > now, our struct Location in AA already has metadata tags and other
> > *instruction* specific info that it grabs from the instruction you
> > pass to getLocation. IE it includes noalias data that it tries to
> > match against other instructions.
> > So we already have broken this abstraction to return better answers
> > :)
> 
> Is it using anything other than alias-related metadata?  My view is
> that
> volatileness does not belong in the alias analysis.  Noalias metadata
> helps directly with what AA does, so it makes sense to have it there.
> Volatileness, not so much.
I agree. volatileness and aliasing are orthogonal properties and I'd like
not to conflate them. I also don't understand what they have to do with
memory dependence. The fact that we promise not to change the number of volatile
loads/stores to some location is only something relevant to a transformation
that might change that (GVN in this case). Danny, can't we reasonably
localize that logic to the transforming passes?

 -Hal
> 
> -Krzysztof
> 
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
> hosted by The Linux Foundation
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Thu, Apr 16, 2015 at 6:31 PM, Philip Reames
<listmail at philipreames.com> wrote:
> On 03/31/2015 03:41 PM, Daniel Berlin wrote:
>>
>> So, i'm working through the last of miniscule gvn optimizations,
and
>> one of the things that gets tested is whether it will eliminate
>> non-volatile loads in favor of ohter non-volatile loads when there are
>> volatile loads in the way.
>
> I'm pretty sure I'm the one who added that set of test cases.  :)
>>
>> I.E.
>> define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
>> entry:
>>    %x = load i32, i32* %p
>>    %0 = load volatile i32, i32* %q
>>    %y = load i32, i32* %p
>>    %add = sub i32 %y, %x
>>    ret i32 %add
>> }
>>
>>
>> Currently, getModRefInfo will return Mod for getModRefInfo(%0,
>> AA->getLocation(%y))
>>
>> This is because it punts on saying anything about ordered loads
>
> I think this is a conservatively correct, but non ideal answer.  A correct
> answer would also be to return Ref or NoModRef (depending on actual
aliasing
> of the underlying locations).  Ordering is not an alasing property and
> should not be reported as such.  However, I believe a large number of
> callers may expect this and fleshing out all those bugs may not be fun.
Yeah, I realized about 10 minutes after writing that email that
including it in location would be a bad idea, and that they should be
reported as different properties.

I do think getModRefInfo is wrong here, given what it knows. It does
*not* modify memory, and it knows it.
The fact that it is volatile may make it a dependency for another
load, but that has no relevance to whether it modifies memory or not.

I'd rather flesh out these bugs, and report the, IMHO, right answer.
>
> Also worth commenting on is that *volatile* and *ordering* have distinctly
> different properties.  We couple them in a lot of odd ways, but the
> reasoning and legal optimizations are quite different.
>
>> I can certainly watch for this case in the caller, and ignore it if
>> it's volatile load vs non-volatile load. This is what MemDep does.
>
> Can you point to the code you're talking about?  A volatile load
encountered
> during the normal instruction walk is treated like any other (provided we
> know the query instruction is non-volatile.)
Yes, this is what i meant by "it ignores it". It decided is had no
impact as a dependency.
>  We are conservative about
> volatile stores, but that's on my list to fix.
>
> Note that we are really conservative about volatile query instructions
>> Nothing that involves walking, sure, but it can trivially give the
>> same answer to this case, which is "the volatile load does not
affect
>> the regular load".
>
> I strongly believe that ordering and aliasing are distinct properties.
>
Which is fine, so we should stop reporting one as if it affects the other.