[DependenceAnalysis] Dependecies for loads marked with "ivnariant.load" should not be shared with general accesses. Fix for https://bugs.llvm.org/show_bug.cgi?id=42151

[ebrevnov]

Summary

Dependence anlysis has a mechanism to cache results. Thus for particular memory access the cache keep track of side effects in basic blocks. The problem is that for invariant loads dependepce analysis legally ignores many dependencies due to a special semantic rules for such loads. But later results calculated for invariant load retrived from the cache for general case acceses. As a result we have wrong dependence information causing GVN to do illegal transformation. Fixes, T42151.

Proposed solution is to disable caching of invariant loads. I think such loads a pretty rare and it doesn't make sense to extend caching mechanism for them.

[ebrevnov]

Remove accidental changes.

[lebedev.ri]

There should be a test.

[ebrevnov]

In D64405#1575668, @lebedev.ri wrote:

There should be a test.

Will add shortly. Sorry for that.

[ebrevnov]

Adding unit test.

[jdoerfert]

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

lib/Analysis/MemoryDependenceAnalysis.cpp

987

"the semantics of invariant loads"

[ebrevnov]

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

[ebrevnov]

lib/Analysis/MemoryDependenceAnalysis.cpp

987

Thanks for catching this. Will fix.

[jdoerfert]

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

[ebrevnov]

In D64405#1577644, @jdoerfert wrote:

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

I believe you assumption regarding 'invariant.load' metadata not changing the semantics is not accurate. According to spec, If such instruction is executed there are number of assumptions the optimizer may do regarding the program. For example it's safe to assume that there are no stores before and no stores changing value after such instruction. Otherwise behavior is undefined. In general case there is no way to know at compile time if invariant load will be exectuted or not. That means you can't blindly propagate results of dependence analysis for invariant load to "normal" loads. And visa-verse results of dependence analysis for "normal" load doesn't take semantic imposed by "invariant.load" into account and would be sub-optimal if used for invariant load.

[jdoerfert]

In D64405#1577916, @ebrevnov wrote:

In D64405#1577644, @jdoerfert wrote:

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

I believe you assumption regarding 'invariant.load' metadata not changing the semantics is not accurate. According to spec, If such instruction is executed there are number of assumptions the optimizer may do regarding the program. For example it's safe to assume that there are no stores before and no stores changing value after such instruction. Otherwise behavior is undefined. In general case there is no way to know at compile time if invariant load will be exectuted or not. That means you can't blindly propagate results of dependence analysis for invariant load to "normal" loads. And visa-verse results of dependence analysis for "normal" load doesn't take semantic imposed by "invariant.load" into account and would be sub-optimal if used for invariant load.

First, I already agreed, you cannot propagate results from inv. loads to non-inv. loads.

I still think you can drop inv. metadata, you did only say it has more restrictions but that is not a problem. If you think dropping the inv. metdata is a problem, please give me an example.

Now the "sub-optimal" part of propagating non-inv. load results to inv. loads. I also agree that this is in general not what you want. However, I was trying to make the point that hat there is one exception: the best possible result. If we have the best possible result already cached for a non-inv. load, we could reuse it for inv. loads as well because they only have less, not more dependences. If you disagree, an example would be good.

[ebrevnov]

In D64405#1578347, @jdoerfert wrote:

In D64405#1577916, @ebrevnov wrote:

In D64405#1577644, @jdoerfert wrote:

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

I believe you assumption regarding 'invariant.load' metadata not changing the semantics is not accurate. According to spec, If such instruction is executed there are number of assumptions the optimizer may do regarding the program. For example it's safe to assume that there are no stores before and no stores changing value after such instruction. Otherwise behavior is undefined. In general case there is no way to know at compile time if invariant load will be exectuted or not. That means you can't blindly propagate results of dependence analysis for invariant load to "normal" loads. And visa-verse results of dependence analysis for "normal" load doesn't take semantic imposed by "invariant.load" into account and would be sub-optimal if used for invariant load.

First, I already agreed, you cannot propagate results from inv. loads to non-inv. loads.

I still think you can drop inv. metadata, you did only say it has more restrictions but that is not a problem. If you think dropping the inv. metdata is a problem, please give me an example.

Now the "sub-optimal" part of propagating non-inv. load results to inv. loads. I also agree that this is in general not what you want. However, I was trying to make the point that hat there is one exception: the best possible result. If we have the best possible result already cached for a non-inv. load, we could reuse it for inv. loads as well because they only have less, not more dependences. If you disagree, an example would be good.

Looks we are totally aligned here. Honestly I don't understand why we can't track this thread down to the end. I agree potentially we may reuse result of non-inv load for inv load if we know it's the best. But supporting this case would be about the same complexity as extending current caching for non-inv as well as inv loads. If I simply drop the first guard around the code which does cache lookup we will end up with inv load not removed on the following example.

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
target triple = "x86_64-unknown-linux-gnu"

declare void @llvm.memset.p0i8.i8(i8*, i8, i32, i1)
declare void @foo(i8*)

define i8 @test(i1 %cmp, i8 *%p) {
entry:

%res1 = load i8, i8* %p
call void @foo(i8 *%p)
br i1 %cmp, label %b2, label %b1

b1:

%res2 = load i8, i8* %p
%res3 = add i8 %res1, %res2
br label %alive

b2:

%v = load i8, i8* %p, !invariant.load !1
%res.dead = add i8 %v, %res1
br label %alive

alive:

%res.phi = phi i8 [%res3, %b1], [%res.dead, %b2]
ret i8 %res.phi

}

!1 = !{}

That means we should either follow current approach and completely exclude non inv loads from caching or implement full support for caching inv.load.

[jdoerfert]

In D64405#1582297, @ebrevnov wrote:

In D64405#1578347, @jdoerfert wrote:

In D64405#1577916, @ebrevnov wrote:

In D64405#1577644, @jdoerfert wrote:

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

I believe you assumption regarding 'invariant.load' metadata not changing the semantics is not accurate. According to spec, If such instruction is executed there are number of assumptions the optimizer may do regarding the program. For example it's safe to assume that there are no stores before and no stores changing value after such instruction. Otherwise behavior is undefined. In general case there is no way to know at compile time if invariant load will be exectuted or not. That means you can't blindly propagate results of dependence analysis for invariant load to "normal" loads. And visa-verse results of dependence analysis for "normal" load doesn't take semantic imposed by "invariant.load" into account and would be sub-optimal if used for invariant load.

First, I already agreed, you cannot propagate results from inv. loads to non-inv. loads.

I still think you can drop inv. metadata, you did only say it has more restrictions but that is not a problem. If you think dropping the inv. metdata is a problem, please give me an example.

Now the "sub-optimal" part of propagating non-inv. load results to inv. loads. I also agree that this is in general not what you want. However, I was trying to make the point that hat there is one exception: the best possible result. If we have the best possible result already cached for a non-inv. load, we could reuse it for inv. loads as well because they only have less, not more dependences. If you disagree, an example would be good.

Looks we are totally aligned here. Honestly I don't understand why we can't track this thread down to the end. I agree potentially we may reuse result of non-inv load for inv load if we know it's the best. But supporting this case would be about the same complexity as extending current caching for non-inv as well as inv loads. If I simply drop the first guard around the code which does cache lookup we will end up with inv load not removed on the following example.

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
target triple = "x86_64-unknown-linux-gnu"

declare void @llvm.memset.p0i8.i8(i8*, i8, i32, i1)
declare void @foo(i8*)

define i8 @test(i1 %cmp, i8 *%p) {
entry:

%res1 = load i8, i8* %p
call void @foo(i8 *%p)
br i1 %cmp, label %b2, label %b1

b1:

%res2 = load i8, i8* %p
%res3 = add i8 %res1, %res2
br label %alive

b2:

%v = load i8, i8* %p, !invariant.load !1
%res.dead = add i8 %v, %res1
br label %alive

alive:

%res.phi = phi i8 [%res3, %b1], [%res.dead, %b2]
ret i8 %res.phi

}

!1 = !{}

That means we should either follow current approach and completely exclude non inv loads from caching or implement full support for caching inv.load.

I don't want to block this further, so LGTM.

---

For the record, I did not want to simply remove the first guard but I thought we could do something like this:

Before:

// If we have a cached entry, and it is non-dirty, use it as the value for
// this dependency.
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
  ++NumCacheNonLocalPtr;
  return ExistingResult->getResult();
}

After:

// If we have a cached entry, and it is non-dirty, use it as the value for
// this dependency. If this is an invariant load, use the existing result
// only if it is the best possible, otherwise we forget we checked for a
// cached value.
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
  if (!isInvariantLoad || isBestPossible(ExistingResult)) {
    ++NumCacheNonLocalPtr;
    return ExistingResult->getResult();
  }
  ExistingResult = nullptr;
}

Out of curiosity, would that still be broken with your example?

[ebrevnov]

Updating comment as requested.

[ebrevnov]

One more test case added.

[ebrevnov]

In D64405#1582896, @jdoerfert wrote:

In D64405#1582297, @ebrevnov wrote:

In D64405#1578347, @jdoerfert wrote:

In D64405#1577916, @ebrevnov wrote:

In D64405#1577644, @jdoerfert wrote:

In D64405#1577614, @ebrevnov wrote:

In D64405#1576608, @jdoerfert wrote:

Why do we need both changes, reading the cache and writing it, assuming I understand the code correctly?
I would have assumed not caching "inv-load" results would fix the problem. And I can see we do not want to reuse
non-inv-load results for inv-loads. However, I would argue one could always check for a cached result and use
it if the result is "good". Do I miss something here?

Yes, you are reading the change correctly. The thing is that both results (one for inv-load case another for non inv-load) are "good". They are just different. Each result should be used for corresponding case only and not for the other. In other words using result from non-inv case for inv-case is not correct as well. Does it make sense?

No, but I'm tired. I would have assumed that I can drop the inv-load metadata without semantic change. If that is the case, I should be able to use the non-inv result if it is cached and already good enough. That would mean we can keep the lookup but do only return the cached result if it is "the best". Maybe my problem is that I do not know the lattice of potential values.

Either way, is it possible and useful to test for the number of (un)cached queries?

I believe you assumption regarding 'invariant.load' metadata not changing the semantics is not accurate. According to spec, If such instruction is executed there are number of assumptions the optimizer may do regarding the program. For example it's safe to assume that there are no stores before and no stores changing value after such instruction. Otherwise behavior is undefined. In general case there is no way to know at compile time if invariant load will be exectuted or not. That means you can't blindly propagate results of dependence analysis for invariant load to "normal" loads. And visa-verse results of dependence analysis for "normal" load doesn't take semantic imposed by "invariant.load" into account and would be sub-optimal if used for invariant load.

First, I already agreed, you cannot propagate results from inv. loads to non-inv. loads.

I still think you can drop inv. metadata, you did only say it has more restrictions but that is not a problem. If you think dropping the inv. metdata is a problem, please give me an example.

Now the "sub-optimal" part of propagating non-inv. load results to inv. loads. I also agree that this is in general not what you want. However, I was trying to make the point that hat there is one exception: the best possible result. If we have the best possible result already cached for a non-inv. load, we could reuse it for inv. loads as well because they only have less, not more dependences. If you disagree, an example would be good.

Looks we are totally aligned here. Honestly I don't understand why we can't track this thread down to the end. I agree potentially we may reuse result of non-inv load for inv load if we know it's the best. But supporting this case would be about the same complexity as extending current caching for non-inv as well as inv loads. If I simply drop the first guard around the code which does cache lookup we will end up with inv load not removed on the following example.

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
target triple = "x86_64-unknown-linux-gnu"

declare void @llvm.memset.p0i8.i8(i8*, i8, i32, i1)
declare void @foo(i8*)

define i8 @test(i1 %cmp, i8 *%p) {
entry:

%res1 = load i8, i8* %p
call void @foo(i8 *%p)
br i1 %cmp, label %b2, label %b1

b1:

%res2 = load i8, i8* %p
%res3 = add i8 %res1, %res2
br label %alive

b2:

%v = load i8, i8* %p, !invariant.load !1
%res.dead = add i8 %v, %res1
br label %alive

alive:

%res.phi = phi i8 [%res3, %b1], [%res.dead, %b2]
ret i8 %res.phi

}

!1 = !{}

That means we should either follow current approach and completely exclude non inv loads from caching or implement full support for caching inv.load.

I don't want to block this further, so LGTM.

---

For the record, I did not want to simply remove the first guard but I thought we could do something like this:

Before:

// If we have a cached entry, and it is non-dirty, use it as the value for
// this dependency.
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
  ++NumCacheNonLocalPtr;
  return ExistingResult->getResult();
}

After:

// If we have a cached entry, and it is non-dirty, use it as the value for
// this dependency. If this is an invariant load, use the existing result
// only if it is the best possible, otherwise we forget we checked for a
// cached value.
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
  if (!isInvariantLoad || isBestPossible(ExistingResult)) {
    ++NumCacheNonLocalPtr;
    return ExistingResult->getResult();
  }
  ExistingResult = nullptr;
}

Out of curiosity, would that still be broken with your example?

It should work. Main challenge I see here is how to perform "isBestPossible" check effectively so it doesn't introduce compile time slow down. Because when this check fails we will have to perform full analysis in addition.

[ebrevnov]

I don't have commit rights. I need someone's assistance with putting the fix in. Thanks!

[ebrevnov]

Just found small issue with the patch. Will update once testing is good.

[jdoerfert]

In D64405#1585175, @ebrevnov wrote:

In D64405#1582896, @jdoerfert wrote:

Out of curiosity, would that still be broken with your example?

It should work. Main challenge I see here is how to perform "isBestPossible" check effectively so it doesn't introduce compile time slow down. Because when this check fails we will have to perform full analysis in addition.

Isn't MemDepResult type Other with OtherType::NonFuncLocal the best case possible? Checking for that one should be cheap, or am I missing something? Would you be willing to give it a try and see what the actual performance is?

[jdoerfert]

In D64405#1587110, @ebrevnov wrote:

Just found small issue with the patch. Will update once testing is good.

Reopen the review so it appears on my dashboard again.

[reames]

I'd like to suggest a change of approach here. There's already precedent in the code for dealing with inconsistent results from metadata. See the getNonLocalPointerDepFromBB handling for AATags and Size changes. I don't see a reason why invariant_load can't be handled in the same manner in the same place. Doing that consolidates all the cache invalidation in one place, and has the benefit of caching all accesses with as much precision as possible. (i.e. an invariant_load would be cached as invariant until the first normal load from that location was found, and then cached as normal loads)

test/Analysis/DependenceAnalysis/InvariantLoad.ll

1

Stylistically, I'd suggest combining these two files into one and using update_test_checks.py to generate check lines.

And surely there is a more reduced test case possible?

[ebrevnov]

In D64405#1589715, @reames wrote:

I'd like to suggest a change of approach here. There's already precedent in the code for dealing with inconsistent results from metadata. See the getNonLocalPointerDepFromBB handling for AATags and Size changes. I don't see a reason why invariant_load can't be handled in the same manner in the same place. Doing that consolidates all the cache invalidation in one place, and has the benefit of caching all accesses with as much precision as possible. (i.e. an invariant_load would be cached as invariant until the first normal load from that location was found, and then cached as normal loads)

Thanks for the suggestion. Will take a look.

[ebrevnov]

In D64405#1590778, @ebrevnov wrote:

In D64405#1589715, @reames wrote:

I'd like to suggest a change of approach here. There's already precedent in the code for dealing with inconsistent results from metadata. See the getNonLocalPointerDepFromBB handling for AATags and Size changes. I don't see a reason why invariant_load can't be handled in the same manner in the same place. Doing that consolidates all the cache invalidation in one place, and has the benefit of caching all accesses with as much precision as possible. (i.e. an invariant_load would be cached as invariant until the first normal load from that location was found, and then cached as normal loads)

Thanks for the suggestion. Will take a look.

These two cases for Size/AATags turned out to be different than invariant load one. In the former case when cache data is invalid it is updated with a new one and all subsequent queries for both new and old Size/AATags will be satisfied from the cache. In case of invariant load we need to always keep two distinct results (except the case pointed out by Johannes) otherwise we won't optimize out invariant loads what completely defeats the idea of marking loads as invariant. Please let me know if I'm missing something here.

[ebrevnov]

test/Analysis/DependenceAnalysis/InvariantLoad.ll

1

Will work on the first request.
Regarding tests reduction. It already took lot of efforts (not mine though :-)) to reduce tests to what we have today. I don't believe they can be significantly reduced with preserving same semantics.

[ebrevnov]

In D64405#1589567, @jdoerfert wrote:

In D64405#1585175, @ebrevnov wrote:

In D64405#1582896, @jdoerfert wrote:

Out of curiosity, would that still be broken with your example?

It should work. Main challenge I see here is how to perform "isBestPossible" check effectively so it doesn't introduce compile time slow down. Because when this check fails we will have to perform full analysis in addition.

Isn't MemDepResult type Other with OtherType::NonFuncLocal the best case possible? Checking for that one should be cheap, or am I missing something? Would you be willing to give it a try and see what the actual performance is?

I now see what you mean :-) I was thinking of a "bestResult" as best for load in current context. Sure will give it a try. Thanks!

[ebrevnov]

1. Fix down stream assertion to not assume dependence result to be always added to the cache.
2. Implemented check for "best" possible result suggested by Johannes.
3. Merged test cases into one file and applied update_test_checks.py

[jdoerfert]

I like the part about the cache: checking for all loads, caching for non-inv loads only. Though, I didn't even know what @reames mentioned before.
For this reason, and the fact that I don't understand the changes in line 1456ff, I think @reames should make sure this is good.

[ebrevnov]

Hi Philip (@reames ), please take a look when possible. Thanks!

[ebrevnov]

ping @reames

[reames]

Stylistic comments only for the moment. I'm trying to wrap my head around the revised invariants. On first thought, I'd still prefer my earlier suggestion, but I haven't full understood the objection. I'll try to spend some more thinking time on this tomorrow.

lib/Analysis/MemoryDependenceAnalysis.cpp

981

Please move this definition back to where it was as nothing in the new scope uses it.

981–982

I'd suggest structuring the bit the follows as a conditional clear of ExistingResult here.

if (isInvariantLoad && !ExistingResult->getResult().isNonFuncLocal()))

ExistingResult = nullptr;

1036

Per the above, ExistingResult must be null for an invariant load, so this can be rewritten as:

if (ExistingResult)

ExistingResult->setResult(Dep);

else if (!isInvariantLoad)

1470

This bit looks to be NFC minus the removal of the assert? Is that correct?

[reames]

LGTM

I'm not really a fan of the design on this, but I've convinced myself this is functionally correct. The alternate solution I proposed originally I still think can (and maybe should) be made to work, but getting a correctness bug fixed in the meantime is reasonable.

lib/Analysis/MemoryDependenceAnalysis.cpp

1046

This code assumes the element is cached, and should be skipped if we don't actually cache.

Note: This doesn't appear to be a functional bug as the remove code checks for existence in the cache along the removal path. Even for things referenced from the reverse map cache.

[ebrevnov]

Corrections requested by Philip.

[ebrevnov]

lib/Analysis/MemoryDependenceAnalysis.cpp

981–982

Even though I don't feel that requested structure is any better I have no objections against that change. Please note that ExistingResult should be checked for not being null as well.

1036

Taking into account your next comment I think we better just bail out for invariant loads.

1470

Absolutely.

[ebrevnov]

BTW, Philip,

If you like current version please go ahead and commit it since I don't have committer rights yet.

Thanks
Evgeniy

[ebrevnov]

ping @reames

[ebrevnov]

ping

[ebrevnov]

Nope

lib/Analysis/MemoryDependenceAnalysis.cpp

 /// cached information in Cache or by doing a lookup (which may use dirty cache
 /// info if available).
 ///
 /// If we do a lookup, add the result to the cache.
 MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
     Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
     BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
 
+  NonLocalDepEntry *ExistingResult = nullptr;
+  bool isInvariantLoad = false;
+
+  if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
+      isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
+
+  // Due to the semantics of invariant loads many dependencies are ignored. Thus
+  // results of dependence analysis can't be shared with general case.
+  // Don't use cached results for invariant load.
+  if (!isInvariantLoad) {
     // Do a binary search to see if we already have an entry for this block in
     // the cache set.  If so, find it.
     NonLocalDepInfo::iterator Entry = std::upper_bound(
         Cache->begin(), Cache->begin() + NumSortedEntries, NonLocalDepEntry(BB));
     if (Entry != Cache->begin() && (Entry - 1)->getBB() == BB)
       --Entry;
 
-  NonLocalDepEntry *ExistingResult = nullptr;
     if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
       ExistingResult = &*Entry;
 
     // If we have a cached entry, and it is non-dirty, use it as the value for
     // this dependency.
     if (ExistingResult && !ExistingResult->getResult().isDirty()) {
       ++NumCacheNonLocalPtr;
       return ExistingResult->getResult();
     }
+  }
 
   // Otherwise, we have to scan for the value.  If we have a dirty cache
   // entry, start scanning from its position, otherwise we scan from the end
   // of the block.
   BasicBlock::iterator ScanPos = BB->end();
   if (ExistingResult && ExistingResult->getResult().getInst()) {
     assert(ExistingResult->getResult().getInst()->getParent() == BB &&
            "Instruction invalidated?");
     ++NumCacheDirtyNonLocalPtr;
     ScanPos = ExistingResult->getResult().getInst()->getIterator();
 
     // Eliminating the dirty entry from 'Cache', so update the reverse info.
     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
     RemoveFromReverseMap(ReverseNonLocalPtrDeps, &*ScanPos, CacheKey);
   } else {
     ++NumUncacheNonLocalPtr;
   }
 
   // Scan the block for the dependency.
   MemDepResult Dep =
       getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
 
+  // Don't put results of dependence analysis into cache.
+  if (!isInvariantLoad) {
     // If we had a dirty entry for the block, update it.  Otherwise, just add
     // a new entry.
     if (ExistingResult)
       ExistingResult->setResult(Dep);
     else
       Cache->push_back(NonLocalDepEntry(BB, Dep));
+  }
 
   // If the block has a dependency (i.e. it isn't completely transparent to
   // the value), remember the reverse association because we just added it
   // to Cache!
   if (!Dep.isDef() && !Dep.isClobber())
     return Dep;
 
   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
   // update MemDep when we remove instructions.
   Instruction *Inst = Dep.getInst();
   assert(Inst && "Didn't depend on anything?");
   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
   return Dep;
 }
 
PredTranslationFailure:
     //
     // If this is the magic first block, return this as a clobber of the whole
     // incoming value.  Since we can't phi translate to one of the predecessors,
     // we have to bail out.
     if (SkipFirstBlock)
       return false;
 
     bool foundBlock = false;
     for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
       if (I.getBB() != BB)
         continue;
 
       assert((GotWorklistLimit || I.getResult().isNonLocal() ||
               !DT.isReachableFromEntry(BB)) &&
              "Should only be here with transparent block");
       foundBlock = true;
       I.setResult(MemDepResult::getUnknown());

test/Analysis/DependenceAnalysis/InvariantLoad.ll

+; RUN: opt < %s -passes=gvn -S | FileCheck %s
+
+; CHECK: ret i8 0
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @llvm.memset.p0i8.i8(i8*, i8, i32, i1)
+declare void @foo(i8*)
+
+define i8 @test(i1 %cmp) {
+entry:
+  %p = alloca i8
+  %addr = getelementptr inbounds i8, i8* %p, i64 0
+  store i8 5, i8* %addr
+  br label %header
+header:
+  %i = phi i8 [0, %entry], [%i.inc, %backedge]
+  br i1 %cmp, label %alive, label %dead
+dead:
+  call void @foo(i8* %p)
+  %v = load i8, i8* %addr, !invariant.load !1
+  %i.1 = add i8 %i, %v
+  br label %alive
+alive:
+  %i.2 = phi i8 [%i, %header], [%i.1, %dead]
+  store i8 -5, i8* %addr
+  br label %backedge
+backedge:
+  call void @llvm.memset.p0i8.i8(i8 * align 1 %p, i8 0, i32 1, i1 false)
+  %i.inc = add i8 %i.2, 1
+  %cmp.loop = icmp ugt i8 %i.inc, 100
+  br i1 %cmp.loop, label %exit, label %header
+exit:
+  %res = load i8, i8* %addr
+  ret i8 %res
+}
+
+!1 = !{}
+

test/Analysis/DependenceAnalysis/InvariantLoad2.ll

+; RUN: opt < %s -gvn -S | FileCheck %s
+
+
+; Check that first two loads are not optimized out while the one marked with
+; invariant.load reuses %res1
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @llvm.memset.p0i8.i8(i8*, i8, i32, i1)
+declare void @foo(i8*)
+
+define i8 @test(i1 %cmp, i8 *%p) {
+; CHECK: %res1 = load i8, i8* %p
+; CHECK: %res2 = load i8, i8* %p
+; CHECK: %res.dead = add i8 %res1, %res1
+
+entry:
+  %res1 = load i8, i8* %p
+  call void @foo(i8 *%p)
+  br i1 %cmp, label %b2, label %b1
+b1:
+  %res2 = load i8, i8* %p
+  %res3 = add i8 %res1, %res2
+  br label %alive
+b2:
+  %v = load i8, i8* %p, !invariant.load !1
+  %res.dead = add i8 %v, %res1
+  br label %alive
+alive:
+  %res.phi = phi i8 [%res3, %b1], [%res.dead, %b2]
+  ret i8 %res.phi
+}
+
+; This is essentially the same test case as the above one but with %b1 and %b2
+; swapped in "br i1 %cmp, label %b1, label %b2" instruction. That helps us to
+; ensure that results doesn't depend on visiting order.
+define i8 @test2(i1 %cmp, i8 *%p) {
+; CHECK: %res1 = load i8, i8* %p
+; CHECK: %res2 = load i8, i8* %p
+; CHECK: %res.dead = add i8 %res1, %res1
+entry:
+  %res1 = load i8, i8* %p
+  call void @foo(i8 *%p)
+  br i1 %cmp, label %b1, label %b2
+b1:
+  %res2 = load i8, i8* %p
+  %res3 = add i8 %res1, %res2
+  br label %alive
+b2:
+  %v = load i8, i8* %p, !invariant.load !1
+  %res.dead = add i8 %v, %res1
+  br label %alive
+alive:
+  %res.phi = phi i8 [%res3, %b1], [%res.dead, %b2]
+  ret i8 %res.phi
+}
+
+!1 = !{}
+