Index: include/llvm/Analysis/AssumptionTracker.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/AssumptionTracker.h
@@ -0,0 +1,131 @@
+//===- llvm/Analysis/AssumptionTracker.h - Track @llvm.assume ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a pass that keeps track of @llvm.assume intrinsics in
+// the functions of a module (allowing assumptions within any function to be
+// found cheaply by other parts of the optimizer).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ASSUMPTIONTRACKER_H
+#define LLVM_ANALYSIS_ASSUMPTIONTRACKER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include <memory>
+
+namespace llvm {
+
+/// An immutable pass that tracks @llvm.assume intrinsics in a module.
+class AssumptionTracker : public ImmutablePass {
+  /// A callback value handle applied to function objects, which we use to
+  /// delete our cache of intrinsics for a function when it is deleted.
+  class FunctionCallbackVH : public CallbackVH {
+    AssumptionTracker *AT;
+    void deleted() override;
+
+    public:
+      typedef DenseMapInfo<Value *> DMI;
+
+      FunctionCallbackVH(Value *V, AssumptionTracker *AT = nullptr)
+        : CallbackVH(V), AT(AT) {}
+  };
+
+  /// A callback value handle applied to call instructions, which keeps
+  /// track of the call's parent function so that we can remove a
+  /// assumption intrinsic call from our cache when the instruction is
+  /// deleted.
+  class CallCallbackVH : public CallbackVH {
+    AssumptionTracker *AT;
+    void deleted() override;
+
+    // We store the function here because we need it to lookup the set
+    // containing this handle when the underlying CallInst is being deleted.
+    Function *F;
+
+    public:
+      typedef DenseMapInfo<Instruction *> DMI;
+
+      CallCallbackVH(Instruction *I, AssumptionTracker *AT = nullptr)
+        : CallbackVH(I), AT(AT), F(nullptr) {
+        if (I != DMI::getEmptyKey() && I != DMI::getTombstoneKey())
+          F = I->getParent()->getParent();
+      }
+
+      operator CallInst*() const {
+        Value *V = getValPtr();
+        if (V == DMI::getEmptyKey() || V == DMI::getTombstoneKey())
+          return static_cast<CallInst*>(V);
+
+        return cast<CallInst>(V);
+      }
+
+      CallInst *operator->() const { return cast<CallInst>(getValPtr()); }
+      CallInst &operator*() const { return *cast<CallInst>(getValPtr()); }
+  };
+
+  friend FunctionCallbackVH;
+  friend CallCallbackVH;
+
+  // FIXME: SmallSet might be better here, but it currently has no iterators.
+  typedef DenseSet<CallCallbackVH, CallCallbackVH::DMI> CallHandleSet;
+  typedef DenseMap<FunctionCallbackVH, std::unique_ptr<CallHandleSet>,
+                   FunctionCallbackVH::DMI> FunctionCallsMap;
+  FunctionCallsMap CachedAssumeCalls;
+
+  /// Scan the provided function for @llvm.assume intrinsic calls. Returns an
+  /// iterator to the set for this function in the CachedAssumeCalls map.
+  FunctionCallsMap::iterator scanFunction(Function *F);
+
+public:
+  /// Remove the cache of @llvm.assume intrinsics for the given function.
+  void forgetCachedAssumptions(Function *F);
+
+  /// Add an @llvm.assume intrinsic to the cache for its parent function.
+  /// Note that if the parent function is not already in the cache, then it is
+  /// scanned for all assumptions within this call so that, for all functions,
+  /// the set of assumptions is always complete.
+  void registerAssumption(CallInst *CI);
+
+  typedef CallHandleSet::iterator assumption_iterator;
+  typedef iterator_range<assumption_iterator> assumption_range;
+
+  inline assumption_range assumptions(Function *F) {
+    FunctionCallsMap::iterator I = CachedAssumeCalls.find(F);
+    if (I == CachedAssumeCalls.end()) {
+      I = scanFunction(F);
+    }
+
+    return assumption_range(I->second->begin(), I->second->end());
+  }
+
+  AssumptionTracker();
+  ~AssumptionTracker();
+
+  void releaseMemory() override {
+    CachedAssumeCalls.shrink_and_clear();
+  }
+
+  void verifyAnalysis() const override;
+  bool doFinalization(Module &) override {
+    verifyAnalysis();
+    return false;
+  }
+
+  static char ID; // Pass identification, replacement for typeid
+};
+
+} // end namespace llvm
+
+#endif
Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -262,6 +262,7 @@
 void initializeTargetTransformInfoAnalysisGroup(PassRegistry&);
 void initializeNoTTIPass(PassRegistry&);
 void initializeTargetLibraryInfoPass(PassRegistry&);
+void initializeAssumptionTrackerPass(PassRegistry &);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAliasAnalysisPass(PassRegistry&);
 void initializeScopedNoAliasAAPass(PassRegistry&);
Index: lib/Analysis/AssumptionTracker.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/AssumptionTracker.cpp
@@ -0,0 +1,111 @@
+//===- AssumptionTracker.cpp - Track @llvm.assume -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a pass that keeps track of @llvm.assume intrinsics in
+// the functions of a module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/AssumptionTracker.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/Debug.h"
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+void AssumptionTracker::FunctionCallbackVH::deleted() {
+  AT->forgetCachedAssumptions(cast<Function>(getValPtr()));
+  // 'this' now dangles!
+}
+
+void AssumptionTracker::forgetCachedAssumptions(Function *F) {
+  CachedAssumeCalls.erase(F);
+}
+
+void AssumptionTracker::CallCallbackVH::deleted() {
+  assert(F && "delete callback called on dummy handle");
+  FunctionCallsMap::iterator I = AT->CachedAssumeCalls.find(F);
+  assert(I != AT->CachedAssumeCalls.end() &&
+         "Function cleared from the map without removing the values?");
+
+  I->second->erase(*this);
+  // 'this' now dangles!
+}
+
+AssumptionTracker::FunctionCallsMap::iterator
+AssumptionTracker::scanFunction(Function *F) {
+  auto IP =
+    CachedAssumeCalls.insert(std::make_pair(FunctionCallbackVH(F, this),
+                                            std::unique_ptr<CallHandleSet>(
+                                              new CallHandleSet())));
+  assert(IP.second && "Scanning function already in the map?");
+
+  FunctionCallsMap::iterator I = IP.first;
+
+  // Go through all instructions in all blocks, add all calls to @llvm.assume
+  // to our cache.
+  for (BasicBlock &B : *F)
+    for (Instruction &II : B)
+      if (match(cast<Value>(&II), m_Intrinsic<Intrinsic::assume>(m_Value())))
+        I->second->insert(CallCallbackVH(&II, this));
+
+  return I;
+}
+
+void AssumptionTracker::verifyAnalysis() const {
+#ifndef NDEBUG
+  for (const auto &I : CachedAssumeCalls) {
+    for (const BasicBlock &B : cast<Function>(*I.first))
+      for (const Instruction &II : B) {
+        Instruction *C = const_cast<Instruction*>(&II);
+        if (match(C, m_Intrinsic<Intrinsic::assume>(m_Value()))) {
+          assert(I.second->count(CallCallbackVH(C,
+                   const_cast<AssumptionTracker*>(this))) &&
+                 "Assumption in scanned function not in cache");
+        }
+    }
+  }
+#endif
+}
+
+void AssumptionTracker::registerAssumption(CallInst *CI) {
+  assert(match(cast<Value>(CI),
+               m_Intrinsic<Intrinsic::assume>(m_Value())) &&
+         "Registered call does not call @llvm.assume");
+  assert(CI->getParent() &&
+         "Cannot register @llvm.assume call not in a basic block");
+
+  Function *F = CI->getParent()->getParent();
+  assert(F && "Cannot register @llvm.assume call not in a function");
+
+  FunctionCallsMap::iterator I = CachedAssumeCalls.find(F);
+  if (I == CachedAssumeCalls.end()) {
+    I = scanFunction(F);
+    assert(I->second->count(CI) && "Function scan did not find the call");
+
+    return;
+  }
+
+  I->second->insert(CallCallbackVH(CI, this));
+}
+
+AssumptionTracker::AssumptionTracker() : ImmutablePass(ID) {
+  initializeAssumptionTrackerPass(*PassRegistry::getPassRegistry());
+}
+
+AssumptionTracker::~AssumptionTracker() {}
+
+INITIALIZE_PASS(AssumptionTracker, "assumption-tracker", "Assumption Tracker",
+                false, true)
+char AssumptionTracker::ID = 0;
+
Index: lib/Analysis/CMakeLists.txt
===================================================================
--- lib/Analysis/CMakeLists.txt
+++ lib/Analysis/CMakeLists.txt
@@ -5,6 +5,7 @@
   AliasDebugger.cpp
   AliasSetTracker.cpp
   Analysis.cpp
+  AssumptionTracker.cpp
   BasicAliasAnalysis.cpp
   BlockFrequencyInfo.cpp
   BlockFrequencyInfoImpl.cpp
Index: lib/Transforms/InstCombine/InstCombine.h
===================================================================
--- lib/Transforms/InstCombine/InstCombine.h
+++ lib/Transforms/InstCombine/InstCombine.h
@@ -11,12 +11,14 @@
 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 
 #include "InstCombineWorklist.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
 
@@ -71,14 +73,20 @@
 class LLVM_LIBRARY_VISIBILITY InstCombineIRInserter
     : public IRBuilderDefaultInserter<true> {
   InstCombineWorklist &Worklist;
+  AssumptionTracker *AT;
 
 public:
-  InstCombineIRInserter(InstCombineWorklist &WL) : Worklist(WL) {}
+  InstCombineIRInserter(InstCombineWorklist &WL, AssumptionTracker *AT)
+    : Worklist(WL), AT(AT) {}
 
   void InsertHelper(Instruction *I, const Twine &Name, BasicBlock *BB,
                     BasicBlock::iterator InsertPt) const {
     IRBuilderDefaultInserter<true>::InsertHelper(I, Name, BB, InsertPt);
     Worklist.Add(I);
+
+    using namespace llvm::PatternMatch;
+    if ((match(I, m_Intrinsic<Intrinsic::assume>(m_Value()))))
+      AT->registerAssumption(cast<CallInst>(I));
   }
 };
 
@@ -86,6 +94,7 @@
 class LLVM_LIBRARY_VISIBILITY InstCombiner
     : public FunctionPass,
       public InstVisitor<InstCombiner, Instruction *> {
+  AssumptionTracker *AT;
   const DataLayout *DL;
   TargetLibraryInfo *TLI;
   bool MadeIRChange;
@@ -114,6 +123,8 @@
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
+  AssumptionTracker *getAssumptionTracker() const { return AT; }
+
   const DataLayout *getDataLayout() const { return DL; }
 
   TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; }
Index: lib/Transforms/InstCombine/InstCombineCalls.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -996,6 +996,8 @@
   }
   case Intrinsic::assume: {
     // Canonicalize assume(a && b) -> assume(a); assume(b);
+    // Note: New assumption intrinsics created here are registered by
+    // the InstCombineIRInserter object.
     Value *IIOperand = II->getArgOperand(0), *A, *B,
           *AssumeIntrinsic = II->getCalledValue();
     if (match(IIOperand, m_And(m_Value(A), m_Value(B)))) {
@@ -1005,8 +1007,10 @@
     }
     // assume(!(a || b)) -> assume(!a); assume(!b);
     if (match(IIOperand, m_Not(m_Or(m_Value(A), m_Value(B))))) {
-      Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(A), II->getName());
-      Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(B), II->getName());
+      Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(A),
+                          II->getName());
+      Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(B),
+                          II->getName());
       return EraseInstFromFunction(*II);
     }
     break;
Index: lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- lib/Transforms/InstCombine/InstructionCombining.cpp
+++ lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -39,6 +39,7 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringSwitch.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
@@ -85,12 +86,14 @@
 char InstCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(InstCombiner, "instcombine",
                 "Combine redundant instructions", false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionTracker)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
 INITIALIZE_PASS_END(InstCombiner, "instcombine",
                 "Combine redundant instructions", false, false)
 
 void InstCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
+  AU.addRequired<AssumptionTracker>();
   AU.addRequired<TargetLibraryInfo>();
 }
 
@@ -2907,6 +2910,7 @@
   if (skipOptnoneFunction(F))
     return false;
 
+  AT = &getAnalysis<AssumptionTracker>();
   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
   DL = DLP ? &DLP->getDataLayout() : nullptr;
   TLI = &getAnalysis<TargetLibraryInfo>();
@@ -2918,7 +2922,7 @@
   /// instructions into the worklist when they are created.
   IRBuilder<true, TargetFolder, InstCombineIRInserter>
     TheBuilder(F.getContext(), TargetFolder(DL),
-               InstCombineIRInserter(Worklist));
+               InstCombineIRInserter(Worklist, AT));
   Builder = &TheBuilder;
 
   InstCombinerLibCallSimplifier TheSimplifier(DL, TLI, this);
Index: lib/Transforms/Scalar/LoopUnswitch.cpp
===================================================================
--- lib/Transforms/Scalar/LoopUnswitch.cpp
+++ lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -823,6 +823,10 @@
   F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(),
                                 NewBlocks[0], F->end());
 
+  // FIXME: We could register any cloned assumptions instead of clearing the
+  // whole function's cache.
+  AT->forgetCachedAssumptions(F);
+
   // Now we create the new Loop object for the versioned loop.
   Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM);
 
Index: lib/Transforms/Utils/InlineFunction.cpp
===================================================================
--- lib/Transforms/Utils/InlineFunction.cpp
+++ lib/Transforms/Utils/InlineFunction.cpp
@@ -18,6 +18,7 @@
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
@@ -982,6 +983,11 @@
 
     // Add noalias metadata if necessary.
     AddAliasScopeMetadata(CS, VMap, IFI.DL, IFI.AA);
+
+    // FIXME: We could register any cloned assumptions instead of clearing the
+    // whole function's cache.
+    if (IFI.AT)
+      IFI.AT->forgetCachedAssumptions(Caller);
   }
 
   // If there are any alloca instructions in the block that used to be the entry
Index: lib/Transforms/Utils/LoopUnroll.cpp
===================================================================
--- lib/Transforms/Utils/LoopUnroll.cpp
+++ lib/Transforms/Utils/LoopUnroll.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Transforms/Utils/UnrollLoop.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
@@ -442,6 +443,10 @@
     }
   }
 
+  // FIXME: We could register any cloned assumptions instead of clearing the
+  // whole function's cache.
+  AT->forgetCachedAssumptions(F);
+
   DominatorTree *DT = nullptr;
   if (PP) {
     // FIXME: Reconstruct dom info, because it is not preserved properly.