Index: include/llvm/Analysis/ScalarEvolutionAliasAnalysis.h
===================================================================
--- include/llvm/Analysis/ScalarEvolutionAliasAnalysis.h
+++ include/llvm/Analysis/ScalarEvolutionAliasAnalysis.h
@@ -26,10 +26,13 @@
 /// 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);
 
@@ -67,6 +70,6 @@
 /// Creates an instance of \c SCEVAAWrapperPass.
 FunctionPass *createSCEVAAWrapperPass();
 
-}
+} // namespace llvm
 
 #endif
Index: lib/Analysis/ScalarEvolutionAliasAnalysis.cpp
===================================================================
--- lib/Analysis/ScalarEvolutionAliasAnalysis.cpp
+++ lib/Analysis/ScalarEvolutionAliasAnalysis.cpp
@@ -20,8 +20,87 @@
 //===----------------------------------------------------------------------===//
 
 #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
@@ -41,7 +120,8 @@
   // 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);
@@ -113,7 +193,8 @@
 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;
@@ -133,11 +214,13 @@
 
 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>();
 }
Index: test/Analysis/ScalarEvolution/scev-aa.ll
===================================================================
--- test/Analysis/ScalarEvolution/scev-aa.ll
+++ test/Analysis/ScalarEvolution/scev-aa.ll
@@ -212,6 +212,28 @@
   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