[LICM] Don't assert on volatile accesses

[mssimpso]

Summary

A constant pointer in a non-volatile alias set (e.g., null) may be used by volatile accesses. For such cases, we might should bail out instead of asserting. This should fix PR25628.

Contributed-by: Ed Baunton

[edbaunton]

Thanks Matt.

After I created this patch, I actually did some more investigation with Nuno Lopes where we discovered that there is a more subtle bug seemingly going on with the alias analysis that occurs in tbaa.

Running the alias analysis without tbaa produces 2 alias sets, while with tbaa it (seemingly erroneously) produces a third alias set.

The upshot is, that the AST that is checked a few lines up in this file returns isVolatile as false because it is checking a third set.

I spent a few hours yesterday trying to track how this magical third set gets produced in the tbaa code and the AliasAnalysis code in general but couldn't get to the bottom of it.

As it is, this patch *I think* will fix the assertion at hand in a relatively safe way: the isSimple already checks isVolatile and bails the optimisation if that is the case (rather than assertion).

The full fix would be to adjust tbaa to stop producing this third spurious alias set (if that is the case).

tldr; not sure this is a really good fix.

[edbaunton]

Also that test case can be reduced more by using the one that was posted on the bug originally.

[mssimpso]

Ed,

It's not surprising to me that TBAA would produce more precise results (and thus an additional alias set in this case). The essential piece is that, in the test case, it's claiming that the address of b cannot be null, which is correct I think. That allows LICM to remove load2 and change load3 to load from null. The alias set containing null cannot be marked volatile since it doesn't contain any loads or stores. But now null is used by load3, which is volatile. So your original patch sounded like a reasonable solution to me! Hopefully someone more knowledgeable will chime in.

In your patch, the check for isVolatile is done in IsUnordered.

[edbaunton]

Seems like both isSimple and isUnordered check for volatility: http://llvm.org/docs/doxygen/html/Instructions_8h_source.html#l00281 ?

[mssimpso]

In D16986#346586, @edbaunton wrote:

Seems like both isSimple and isUnordered check for volatility

Yes, you are right!

[edbaunton]

Another option would be to adjust the AliasSetTracker's add method to check if any of the users of the instruction are volatile and then mark the set as as volatile (currently it only checks if the instruction itself is volatile before marking the set as volatile). This would be a bit more inefficient as you would have to loop for every user of every load and store added to the set but it would mean no change to the LICM logic... I am not sure which is more correct.

[kparzysz]

Regarding the potential AST modification: loads from null or stores to it are not legal. The original testcase isn't legal either (it contains a dereference of an uninitialized pointer). While the compiler should not abort on any code, we should not be making special accommodations for handling such situations that could negatively affect legal cases.

[reames]

The changes to LICM in this patch are almost certainly not the right approach. The removed assertions give a good hint on where to look; this is likely an AliasSetTracker bug.

p.s. Finding another test case which doesn't involve UB - even just using a non-zero address space - would be good.

[reames]

In D16986#346579, @mssimpso wrote:

Ed,

It's not surprising to me that TBAA would produce more precise results (and thus an additional alias set in this case). The essential piece is that, in the test case, it's claiming that the address of b cannot be null, which is correct I think. That allows LICM to remove load2 and change load3 to load from null. The alias set containing null cannot be marked volatile since it doesn't contain any loads or stores. But now null is used by load3, which is volatile. So your original patch sounded like a reasonable solution to me! Hopefully someone more knowledgeable will chime in.

This response hits the nail on the head. If you have a alias set which is being read from with a volatile load which isn't marked volatile, that's the bug you need to fix.

[mssimpso]

I'm abandoning this change due to feedback from Philip and Krzysztof suggesting it's probably not the right approach. Ed, please feel free to continue investigating this issue if it interests you. Thanks.

[nlopes]

Just a quick comment on this bug. We can see it from two angles:

1. TBAA is just doing its job since it is exploiting the fact that 2 pointers with different types don't alias (the metadata has 2 different type branches). So TBAA claims the pointers don't alias, while they do in practice (it's undefined behavior, though). -- in this case LICM needs patching to account for this aggressiveness.
2. Or we can say that TBAA shouldn't mess with volatile stuff since that's dangerous. In that case LICM is fine and TBAA needs patching.

I'm personally more favorable of 2), since I don't think it's worth to mess with volatile stuff, since it can be dangerous for applications and probably there isn't much performance to gain there.

[reames]

In D16986#358193, @nlopes wrote:

Just a quick comment on this bug. We can see it from two angles:

1. TBAA is just doing its job since it is exploiting the fact that 2 pointers with different types don't alias (the metadata has 2 different type branches). So TBAA claims the pointers don't alias, while they do in practice (it's undefined behavior, though). -- in this case LICM needs patching to account for this aggressiveness.
2. Or we can say that TBAA shouldn't mess with volatile stuff since that's dangerous. In that case LICM is fine and TBAA needs patching.

I'm personally more favorable of 2), since I don't think it's worth to mess with volatile stuff, since it can be dangerous for applications and probably there isn't much performance to gain there.

I disagree with your framing. Unless I misunderstood the issue, this is a clear bug in AST regardless of what TBAA returns for aliasing information. If we ended up with a volatile memory access being part of a alias set, that alias set *must* be marked volatile. It's okay to have non-volatile accesses as part of the volatile set, but not the other way around. If we required the isVolatile flag to be precise for all elements in the set, we'd essentially be requiring alias analysis to *always* get a precise no-alias result when it's possible to do so. That's not an invariant we can uphold.

[nlopes]

In D16986#358822, @reames wrote:

In D16986#358193, @nlopes wrote:

Just a quick comment on this bug. We can see it from two angles:

1. TBAA is just doing its job since it is exploiting the fact that 2 pointers with different types don't alias (the metadata has 2 different type branches). So TBAA claims the pointers don't alias, while they do in practice (it's undefined behavior, though). -- in this case LICM needs patching to account for this aggressiveness.
2. Or we can say that TBAA shouldn't mess with volatile stuff since that's dangerous. In that case LICM is fine and TBAA needs patching.

I'm personally more favorable of 2), since I don't think it's worth to mess with volatile stuff, since it can be dangerous for applications and probably there isn't much performance to gain there.

I disagree with your framing. Unless I misunderstood the issue, this is a clear bug in AST regardless of what TBAA returns for aliasing information. If we ended up with a volatile memory access being part of a alias set, that alias set *must* be marked volatile. It's okay to have non-volatile accesses as part of the volatile set, but not the other way around. If we required the isVolatile flag to be precise for all elements in the set, we'd essentially be requiring alias analysis to *always* get a precise no-alias result when it's possible to do so. That's not an invariant we can uphold.

One of the alias set is not being marked as volatile because TBAA decides it cannot possibly alias with the volatile alias set (because of the UB). But then store forwarding happens and LICM realizes (or doesn't) that two of the alias sets that were said to be disjoint by TBAA in fact alias.
It's not related with volatile information being or not being precise. I agree that we only aim for an over approximation.
The information returned by TBAA *is* correct. I just believe it's too aggressive.

So I believe my analysis is correct. It's the fact that TBAA decides that two pointers don't alias and therefore only one of the sets gets marked as volatile.

[reames]

In D16986#359180, @nlopes wrote:

But then store forwarding happens and LICM realizes (or doesn't) that two of the alias sets that were said to be disjoint by TBAA in fact alias.

Can you clarify this point? AFAIK, LICM does not do store forwarding. How did store forwarding come into the picture at all?

Also, if we ever discover two pointers mustalias, then by definition they must be the same alias set. If not, we have constructed *invalid, and incorrect* alias sets. Oh, I think I see the problem. You're saying that they're both noalias and mustalias discovered through two different mechanism. Ouch, ouch, ouch.

[nlopes]

In D16986#359209, @reames wrote:

In D16986#359180, @nlopes wrote:

But then store forwarding happens and LICM realizes (or doesn't) that two of the alias sets that were said to be disjoint by TBAA in fact alias.

Can you clarify this point? AFAIK, LICM does not do store forwarding. How did store forwarding come into the picture at all?

It does. see here: http://www.llvm.org/docs/doxygen/html/LICM_8cpp_source.html#l00790
LICM does store forwarding of loop-invariant stores. Plus it moves the store to the loop exit.
So yes, it's this mechanism that is breaking the assumption that an alias set not marked as volatile cannot become volatile later (which it can if UB is exploited, like in this case).

Also, if we ever discover two pointers mustalias, then by definition they must be the same alias set. If not, we have constructed *invalid, and incorrect* alias sets. Oh, I think I see the problem. You're saying that they're both noalias and mustalias discovered through two different mechanism. Ouch, ouch, ouch.

If you add UB to the picture, then 2 pointers that must alias may end up in different alias sets. That's ok; it's just LICM doesn't know how to handle this specific volatile case.

I second my case that we should change TBAA instead, such that it handles volatile stuff more conservatively.

[• dberlin]

"I second my case that we should change TBAA instead, such that it handles
volatile stuff more conservatively."

Volatileness and aliasing are different properties.
It's completely reasonable for TBAA (and other alias analysis) to say two
pointers may or may not access different memory.
It may use any way it feels like to achieve that goal.

The volatileness of a given access is something the optimizer needs to take
into account, not TBAA.

(and yes, you can get completely inconsistent results between different
alias analysis providers, where some will say mustalias and some will say
noalias for the same thing).

TL;DR You should fix LICM or AST, depending on your viewpoint.
You also have to take into account that TBAA does not obey transitiveness
or other various nice properties,not to mention different AA levels giving
inconsistent results.

Only one result is "most correct" at the language semantic level, but both
results are correct at the IR level (ie both noalias and mustalias). It
can use or not use whatever metadata it likes.

(apropos of nothing, the lack of transitivity/etc in TBAA is one of the
reasons effective partitioning schemes for aliasing information don't
usually work out :P. Since AST is basically a partitioning scheme, you are
feeling the pain of the edge cases of TBAA)

[nlopes]

In D16986#363895, @dberlin wrote:

"I second my case that we should change TBAA instead, such that it handles
volatile stuff more conservatively."

Volatileness and aliasing are different properties.
It's completely reasonable for TBAA (and other alias analysis) to say two
pointers may or may not access different memory.
It may use any way it feels like to achieve that goal.

The volatileness of a given access is something the optimizer needs to take
into account, not TBAA.

(and yes, you can get completely inconsistent results between different
alias analysis providers, where some will say mustalias and some will say
noalias for the same thing).

TL;DR You should fix LICM or AST, depending on your viewpoint.
You also have to take into account that TBAA does not obey transitiveness
or other various nice properties,not to mention different AA levels giving
inconsistent results.

Only one result is "most correct" at the language semantic level, but both
results are correct at the IR level (ie both noalias and mustalias). It
can use or not use whatever metadata it likes.

(apropos of nothing, the lack of transitivity/etc in TBAA is one of the
reasons effective partitioning schemes for aliasing information don't
usually work out :P. Since AST is basically a partitioning scheme, you are
feeling the pain of the edge cases of TBAA)

I agree with your points.
I was only trying to make the case that maybe TBAA should be less aggressive in the presence of volatile stuff, i.e., it could switch off the analysis of metadata for volatile stuff.
My concern is that in the past there's been pain in handling volatile stuff, resulting in miscompilations. Given that the perf of volatile stuff is probably a non-issue (I don't have any data; just guessing), I would prefer to go the conservative path.
Otherwise, LICM just needs a very simple patch.

[kparzysz]

In D16986#364339, @nlopes wrote:

Given that the perf of volatile stuff is probably a non-issue (I don't have any data; just guessing), I would prefer to go the conservative path.

It is actually important to our (Hexagon) customers.

lib/Transforms/Scalar/LICM.cpp

for (User *U : ASIV->users()) {
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
-        assert(!Load->isVolatile() && "AST broken");
-        if (!Load->isSimple())
+        if (!Load->isSimple() || !Load->isUnordered())
           return Changed;
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
-        assert(!Store->isVolatile() && "AST broken");
-        if (!Store->isSimple())
+        if (!Store->isSimple() || !Store->isUnordered())
           return Changed;
         // Don't sink stores from loops without dedicated block exits. Exits
         // containing indirect branches are not transformed by loop simplify,
         // make sure we catch that. An additional load may be generated in the
         // preheader for SSA updater, so also avoid sinking when no preheader
         // is available.
         if (!HasDedicatedExits || !Preheader)
           return Changed;

test/Transforms/LICM/PR25628.ll

+; RUN: opt -S -tbaa -licm < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK-NOT: %load2 = load i32*, i32** @b
+
+@b = external global i32*, align 8
+
+define void @f(i1 %B, i1 %D) {
+entry:
+  br i1 %B, label %for.body, label %for.end4
+
+for.body:
+  store i32* null, i32** @b, align 8, !tbaa !0
+  store i32 1, i32* null, align 8
+  %load2 = load i32*, i32** @b, align 8, !tbaa !0
+  %load3 = load volatile i32, i32* %load2, align 8, !tbaa !4
+  br i1 %D, label %for.body, label %for.end4
+
+for.end4:
+  ret void
+}
+
+!0 = !{!1, !1, i64 0}
+!1 = !{!"any pointer", !2, i64 0}
+!2 = !{!"omnipotent char", !3, i64 0}
+!3 = !{!"Simple C/C++ TBAA"}
+!4 = !{!5, !5, i64 0}
+!5 = !{!"int", !2, i64 0}