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 :slight_smile:

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".

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

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. :slight_smile:

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 :slight_smile:

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.

From: "Krzysztof Parzyszek" <kparzysz@codeaurora.org>
To: llvmdev@cs.uiuc.edu
Sent: Wednesday, April 1, 2015 5:39:15 AM
Subject: Re: [LLVMdev] where should volatileness really live in the AA API?

>
> 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
> :slight_smile:

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

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. :slight_smile:

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.

Yes.

I actually do not expect a ton to break here if we made getModRefInfo
return Ref/NoModRef for volatile loads.
(I'm going to ignore ordering here because i haven't looked deeply
enough into the models)

For GVN and memdep users, getPointerDependencyFrom already scans all
loads and reports load-load dependencies on volatile ones if the
queryinst is volatile.

MemorySSA can be localized to do what we want. I can make it consider
them part of the chain, make it do nothing, etc, completely
independent of whatever we choose for getModRefInfo.

A scan of getModRefInfo callers seems that they mostly care about
stores (outside of AA users).

So i'll give it a whirl.

I'll be happy to review the patches provided you're willing to fix the bugs as they're reported. :slight_smile:

More seriously, moving the check into the callers and incrementally working outward would probably be a better strategy. That way the conservatism is explicit at the use site and can be fixed case by case.

Philip