[SCEVAA] Don't crash on pointers with no dominance relationship.

[efriedma]

Summary

If you try to compute the difference between two SCEV values which don't have a dominance relationship (so there's no point in the source code where the difference could actually be computed), SCEV will crash. This patch teaches SCEVAA not to do that.

I'm not sure this is the right fix; it seems like I'm working around the underlying issue rather than actually solving it. Does it makes sense to call AliasAnalysis::alias() in the case where HasDominanceRelation returns false? Alias analysis is normally defined in terms of memory operations, so I'm not sure what alias() means in the case where you can't construct a memory operation which refers to both pointers.

Fixes https://bugs.llvm.org/show_bug.cgi?id=33761.

[sunfish]

I haven't thought about this in depth, but it seems like SCEV theoretically should be able to cope under such circumstances.

From the comments in PR33761, SCEV is being asked to compute the difference between ((8 * %tmp2) + %tmp) and {%tmp,+,64}<%bb4>, where %tmp2 doesn't dominate the loop. It seems the result should be something like {0,+,64}<%bb4> + (-8 * %tmp2), and there is even a point in the program where the expression can be computed -- immediately after %tmp2.

[efriedma]

there is even a point in the program where the expression can be computed -- immediately after %tmp2.

That doesn't seem right... what's the value of {0,+,64}<%bb4> in the case the loop doesn't execute? (Assuming you replace "i1 true" with an actual condition.)

[• dberlin]

First, it's definitely the case that you can't compute the difference for all SCEVs. It's equivalent to being able to symbolically executing the program with only static information :)

It is possible to compute the difference between the expressions in some cases, using symbolic execution to come up with path sensitive symbolic answers.
Given alias() is giving all-paths answers, you'd need to meet those answers over all paths anyway.

It's possible that gives you a better answer than "no idea" (IE you discover that on any path, they cannot alias).

It's almost certainly not worth it.

Dominance checking is basically shortcutting this to try to difference them only when you can prove that all paths must lead to computing the result :)

lib/Analysis/ScalarEvolutionAliasAnalysis.cpp

101

FWIW: This rediscovers the same info again and again .
But i'm not sure it's that slow.

IE you could cache scev->largest domtree dfs number interval, and only have to do this computation once per scev.
In fact, it also speeds up the other computation if you want

IE if the dom tree dfs in/out numbers for scev A are {50, 75}, when you call GetBottom on scev B, the second you see an operand with a set of dfs numbers that is either not between those or not encompassing those, there is no dominance relationship between the scevs and you can stop.

(Of course, then you can't cache the dfs number pair for that scev, but ...)

It's fine if you want to leave all this as a comment, i don't know if it's slow enough to be worth doing atm.

[sunfish]

Ah, I overlooked that the loop doesn't dominate the exit block.

That said, it suggests another idea here, which would be to permit the formation of expressions like {0,+,64}<%bb4> + (-8 * %tmp2) in SCEV itself, and then just assert if such an expression is passed into SCEVExpander or similar.

[hfinkel]

I'm not sure this is the right fix; it seems like I'm working around the underlying issue rather than actually solving it.

I agree. This seems like working around the underlying issue.

Does it makes sense to call AliasAnalysis::alias() in the case where HasDominanceRelation returns false?

No, I don't think it does (for the reason you've specified). We only support aliasing queries between values with some dominance relation.

I couple of thoughts:

1. If we wanted to handle this somehow in SCEVAAResult::alias, can't we just put a dominance check on the values directly instead of trying to examine the SCEVs? Meaning:

Instruction *IA = dyn_cast<Instruction>(LocA.Ptr),
                      *IB = dyn_cast<Instruction>(LocB.Ptr);
if (IA && IB &&
     (DT->dominates(IA->getParent(), IB->getParent()) ||
      DT->dominates(IB->getParent(), IA->getParent())) &&
     "Queries between values without a dominance relationship is not supported");

(or returning a conservative answer instead of asserting)

2. I think that what AliasSetPrinter is doing is just not well defined. We should really fix it (although, frankly, I'm not sure how without increasing its asymptotic complexity by having it create a set for each block only with others with a dominance relationship, but maybe that's okay as AliasSetPrinter is a diagnostic tool).

[efriedma]

If we wanted to handle this somehow in SCEVAAResult::alias, can't we just put a dominance check on the values directly instead of trying to examine the SCEVs?

Oh. Yes, that would be simpler. :) Maybe slightly less powerful, depending on the structure of the code.

I think that what AliasSetPrinter is doing is just not well defined

In this case, it's probably worth noting that I have a testcase which doesn't involve aa-eval; BasicAA also makes queries like this (see BasicAAResult::aliasPHI). I can reduce it if that would be interesting.

[hfinkel]

In D41689#970310, @efriedma wrote:

If we wanted to handle this somehow in SCEVAAResult::alias, can't we just put a dominance check on the values directly instead of trying to examine the SCEVs?

Oh. Yes, that would be simpler. :) Maybe slightly less powerful, depending on the structure of the code.

I think that what AliasSetPrinter is doing is just not well defined

In this case, it's probably worth noting that I have a testcase which doesn't involve aa-eval; BasicAA also makes queries like this (see BasicAAResult::aliasPHI). I can reduce it if that would be interesting.

I'd find that interesting.

In general, I think that we need to decide what the interface contract here is. I had thought that we required a dominance relationship because there had to be at least on well-defined point where both values could be simultaneously evaluated in order to produce a well-defined result. This might be too strict. I can imagine saying something along these lines but allowing for some kind of hypothetical PHI translation (i.e. saying that the values can be compared if there could exist some series of well-defined PHIs that would bring the values together under at least one valid path through the CFG (albeit under different names). I get a little worried here in defining how this works in the face of backedges (because I need alias (%a, %b) to, say, compare in the current loop iteration, not %b from some loop iteration against %a hypothetically PHI-translated into some other iteration). Our BasicAA::aliasPHI, as I believe we discovered when investigating some bug involving a use of ValueTracking, is somewhat-fundamentally broken in some related sense, so I find your comment unsurprising in that regard.

In any case, I'd be fine with doing a simple dominance check in SCEVAA and working on a separate patch to clean up the docs about what AA means and then trying to clean up everything else.

include/llvm/Analysis/ScalarEvolutionAliasAnalysis.h

 #include "llvm/Pass.h"
 
 namespace llvm {
 
 /// A simple alias analysis implementation that uses ScalarEvolution to answer
 /// queries.
 class SCEVAAResult : public AAResultBase<SCEVAAResult> {
   ScalarEvolution &SE;
+  DominatorTree &DT;
 
 public:
-  explicit SCEVAAResult(ScalarEvolution &SE) : AAResultBase(), SE(SE) {}
-  SCEVAAResult(SCEVAAResult &&Arg) : AAResultBase(std::move(Arg)), SE(Arg.SE) {}
+  explicit SCEVAAResult(ScalarEvolution &SE, DominatorTree &DT)
+      : AAResultBase(), SE(SE), DT(DT) {}
+  SCEVAAResult(SCEVAAResult &&Arg)
+      : AAResultBase(std::move(Arg)), SE(Arg.SE), DT(Arg.DT) {}
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
 
 private:
   Value *GetBaseValue(const SCEV *S);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
public:
 
   bool runOnFunction(Function &F) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 };
 
 /// Creates an instance of \c SCEVAAWrapperPass.
 FunctionPass *createSCEVAAWrapperPass();
 
-}
+} // namespace llvm
 
 #endif

lib/Analysis/ScalarEvolutionAliasAnalysis.cpp

 // dependencies between different iterations.
 //
 // ScalarEvolution has a more complete understanding of pointer arithmetic
 // than BasicAliasAnalysis' collection of ad-hoc analyses.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
+#include "llvm/IR/Dominators.h"
+
 using namespace llvm;
 
+// Find a basic block which is dominated by all the operands of the given
+// SCEV.
+static BasicBlock *GetBottom(DominatorTree &DT, const SCEV *S) {
+  struct FindBottom {
+    BasicBlock *Bottom = nullptr;
+    DominatorTree &DT;
+
+    FindBottom(DominatorTree &DT) : DT(DT) {}
+
+    // Process a BB: if it is dominated by Bottom, it becomes the new Bottom.
+    void CheckBB(BasicBlock *BB) {
+      if (!Bottom) {
+        Bottom = BB;
+        return;
+      }
+      if (DT.dominates(Bottom, BB))
+        Bottom = BB;
+      else
+        assert(DT.dominates(BB, Bottom) &&
+               "SCEV expressions always have a dominance relationship");
+    }
+
+    bool checkSCEVUnknown(const SCEVUnknown *SU) {
+      if (auto *I = dyn_cast<Instruction>(SU->getValue()))
+        CheckBB(I->getParent());
+      return false;
+    }
+
+    bool checkSCEVAddRecExpr(const SCEVAddRecExpr *AddRec) {
+      // (Note that we don't need to recuse into AddRecs: the operands
+      // always dominate the loop.)
+      CheckBB(AddRec->getLoop()->getHeader());
+      return false;
+    }
+
+    bool follow(const SCEV *S) {
+      switch (static_cast<SCEVTypes>(S->getSCEVType())) {
+      case scConstant:
+        return false;
+      case scAddRecExpr:
+        return checkSCEVAddRecExpr(cast<SCEVAddRecExpr>(S));
+      case scTruncate:
+      case scZeroExtend:
+      case scSignExtend:
+      case scAddExpr:
+      case scMulExpr:
+      case scUMaxExpr:
+      case scSMaxExpr:
+      case scUDivExpr:
+        return true;
+      case scUnknown:
+        return checkSCEVUnknown(cast<SCEVUnknown>(S));
+      case scCouldNotCompute:
+        llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+      }
+      return false;
+    }
+    bool isDone() { return false; }
+  };
+  FindBottom FB(DT);
+  SCEVTraversal<FindBottom> ST(FB);
+  ST.visitAll(S);
+  return FB.Bottom;
+}
+
+// Verify that the two input expressions have a dominance relation,
+// i.e. there's some basic block where we could expand the difference
+// between the two expressions. (This is an invariant of SCEV, but
+// apparently not an invariant of alias analysis.)
+static bool HasDominanceRelation(DominatorTree &DT, const SCEV *AS,
+                                 const SCEV *BS) {
+  BasicBlock *BottomA = GetBottom(DT, AS);
+  BasicBlock *BottomB = GetBottom(DT, BS);
+  return !BottomA || !BottomB || DT.dominates(BottomA, BottomB) ||
+         DT.dominates(BottomB, BottomA);
+}
+
 AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
                                 const MemoryLocation &LocB) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are. This allows the code below to ignore this special
   // case.
   if (LocA.Size == 0 || LocB.Size == 0)
     return NoAlias;
 
   // This is SCEVAAResult. Get the SCEVs!
   const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
   const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
 
   // If they evaluate to the same expression, it's a MustAlias.
   if (AS == BS)
     return MustAlias;
 
   // If something is known about the difference between the two addresses,
   // see if it's enough to prove a NoAlias.
   if (SE.getEffectiveSCEVType(AS->getType()) ==
-      SE.getEffectiveSCEVType(BS->getType())) {
+          SE.getEffectiveSCEVType(BS->getType()) &&
+      HasDominanceRelation(DT, AS, BS)) {
     unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
     APInt ASizeInt(BitWidth, LocA.Size);
     APInt BSizeInt(BitWidth, LocB.Size);
 
     // Compute the difference between the two pointers.
     const SCEV *BA = SE.getMinusSCEV(BS, AS);
 
     // Test whether the difference is known to be great enough that memory of
Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
   }
   // No Identified object found.
   return nullptr;
 }
 
 AnalysisKey SCEVAA::Key;
 
 SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) {
-  return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F));
+  return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F),
+                      AM.getResult<DominatorTreeAnalysis>(F));
 }
 
 char SCEVAAWrapperPass::ID = 0;
 INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
                       "ScalarEvolution-based Alias Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
                     "ScalarEvolution-based Alias Analysis", false, true)
 
 FunctionPass *llvm::createSCEVAAWrapperPass() {
   return new SCEVAAWrapperPass();
 }
 
 SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
   initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 bool SCEVAAWrapperPass::runOnFunction(Function &F) {
   Result.reset(
-      new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
+      new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE(),
+                       getAnalysis<DominatorTreeWrapperPass>().getDomTree()));
   return false;
 }
 
 void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<ScalarEvolutionWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
 }

test/Analysis/ScalarEvolution/scev-aa.ll

for.body:                                         ; preds = %entry, %for.body
   %tmp6 = load i64, i64* %p                            ; <i64> [#uses=1]
   %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
+; Just make sure this doesn't crash; PR33761
+; CHECK: Function: patatino: 3 pointers, 0 call sites
+
+define void @patatino(i64 %arg) {
+bb:
+  %tmp = inttoptr i64 %arg to i64*
+  br i1 true, label %bb1, label %bb4
+
+bb1:
+  %tmp2 = phi i64 [ 0, %bb ], [ %tmp7, %bb4 ]
+  %tmp3 = getelementptr i64, i64* %tmp, i64 %tmp2
+  store i64 %tmp2, i64* %tmp3
+  ret void
+
+bb4:
+  %tmp5 = phi i64 [ 0, %bb ], [ %tmp7, %bb4 ]
+  %tmp6 = getelementptr i64, i64* %tmp, i64 %tmp5
+  store i64 %tmp5, i64* %tmp6
+  %tmp7 = add nsw i64 %tmp5, 8
+  br i1 false, label %bb1, label %bb4
+}
+
 ; CHECK: 14 no alias responses
-; CHECK: 26 may alias responses
+; CHECK: 29 may alias responses
 ; CHECK: 18 must alias responses