Hi @nikic,

I've seen a miscompile for my OOT target with this patch. Unfortunately I haven't gone to the bottom with it yet (and I don't think I will until after new years), so I'm not sure what the problem is exactly, but I think that AA comes to the conclusion that a read and a write to the exact same location doesn't alias, and then things go wrong. Are you aware of any problems?

Another question that is a bit related. In 35676a4f9a536 which this patch builds upon, a comment in isKnownNonZeroFromAssume was removed:

-  // Note that the patterns below need to be kept in sync with the code
-  // in AssumptionCache::updateAffectedValues.

Don't they need to be kept in sync anymore?

In rGb21840751278128ef6942074ae89ea63c9c6ac58#967637, @uabelho wrote:

Hi @nikic,

I've seen a miscompile for my OOT target with this patch. Unfortunately I haven't gone to the bottom with it yet (and I don't think I will until after new years), so I'm not sure what the problem is exactly, but I think that AA comes to the conclusion that a read and a write to the exact same location doesn't alias, and then things go wrong. Are you aware of any problems?

@uableho: Our problem seem to be related to a bad DominatorTree (exposed by this patch). If I do

@@ -2178,8 +2186,14 @@ static bool isKnownNonNullFromDominatingCondition(const Value *V,
           BasicBlock *NonNullSuccessor =
               BI->getSuccessor(NonNullIfTrue ? 0 : 1);
           BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
-          if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
+          DominatorTree DT2(*NonNullSuccessor->getParent());
+          if (Edge.isSingleEdge() && DT2.dominates(Edge, CtxI->getParent())) {

to force a recalculation of DT then the miscompile is gone. Ouch, that could be a much bigger problem than I expected here. I haven't had time to figure out why the DT is incorrect (I assume that since this is deep down in the backend when doing misched the DomTree (on IR level) should just be preserved by the PM, or recalculated when swapping functions, but I don't really know the details).

In rGb21840751278128ef6942074ae89ea63c9c6ac58#967713, @bjope wrote:

In rGb21840751278128ef6942074ae89ea63c9c6ac58#967637, @uabelho wrote:

Hi @nikic,

I've seen a miscompile for my OOT target with this patch. Unfortunately I haven't gone to the bottom with it yet (and I don't think I will until after new years), so I'm not sure what the problem is exactly, but I think that AA comes to the conclusion that a read and a write to the exact same location doesn't alias, and then things go wrong. Are you aware of any problems?

@uableho: Our problem seem to be related to a bad DominatorTree (exposed by this patch). If I do

@@ -2178,8 +2186,14 @@ static bool isKnownNonNullFromDominatingCondition(const Value *V,
           BasicBlock *NonNullSuccessor =
               BI->getSuccessor(NonNullIfTrue ? 0 : 1);
           BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
-          if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
+          DominatorTree DT2(*NonNullSuccessor->getParent());
+          if (Edge.isSingleEdge() && DT2.dominates(Edge, CtxI->getParent())) {

to force a recalculation of DT then the miscompile is gone. Ouch, that could be a much bigger problem than I expected here. I haven't had time to figure out why the DT is incorrect (I assume that since this is deep down in the backend when doing misched the DomTree (on IR level) should just be preserved by the PM, or recalculated when swapping functions, but I don't really know the details).

@bjope Interesting. I've looked at another miscompile that starts happening with a3614a31c46:

[BasicAA] Pass context instruction to isKnownNonZero()

This allows us to handle additional cases like assumes.

which does

@@ -1280,7 +1280,7 @@ AliasResult BasicAAResult::aliasGEP(
       if (DecompGEP1.VarIndices.size() == 1) {
         // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale).
         const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
-        if (isKnownNonZero(Var.V, DL))
+        if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT))
           MinAbsVarIndex = Var.Scale.abs();
       } else if (DecompGEP1.VarIndices.size() == 2) {
         // VarIndex = Scale*V0 + (-Scale)*V1.

and if revert that both problems disappear, so it could very well be that the DT is no good.

There is a bunch of lit tests that fail if adding a DT->verify() check in isKnownNonZero.

But with a patch like this

diff --git a/llvm/lib/Analysis/AliasAnalysis.cpp b/llvm/lib/Analysis/AliasAnalysis.cpp
index f5b62ef06a23..fae7a84332fd 100644
--- a/llvm/lib/Analysis/AliasAnalysis.cpp
+++ b/llvm/lib/Analysis/AliasAnalysis.cpp
@@ -883,8 +883,8 @@ bool AAResultsWrapperPass::runOnFunction(Function &F) {
 
 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<BasicAAWrapperPass>();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addRequiredTransitive<BasicAAWrapperPass>();
+  AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
 
   // We also need to mark all the alias analysis passes we will potentially
   // probe in runOnFunction as used here to ensure the legacy pass manager
diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
index f9275daf1224..a0da8b7347ea 100644
--- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp
@@ -1875,9 +1875,9 @@ bool BasicAAWrapperPass::runOnFunction(Function &F) {
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<AssumptionCacheTracker>();
-  AU.addRequired<DominatorTreeWrapperPass>();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addRequiredTransitive<AssumptionCacheTracker>();
+  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
+  AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<PhiValuesWrapperPass>();
 }

the DT seem to be updated correctly. However, with such patch we get some other failures when setting up pass pipeline for some Hexagon tests and sometimes when using GVNHoist. But I guess hitting asserts in some sense is better than miscompiles...