An Assumption-Tracking Pass

[hfinkel]

Summary

This patch adds an immutable pass, AssumptionTracker, which keeps a cache of @llvm.assume instructions within a module. It uses callback value handles to keep stale functions and intrinsics out of the map, and it relies on any code that creates new @llvm.assume calls to notify it of the new instructions. The benefit is that code needing to find @llvm.assume intrinsics can do so directly, without scanning the function, thus allowing the cost of @llvm.assume handling to be negligible when none are present.

I apologize ahead of time: Some of the patches in this series now depend on each other in odd ways. You probably can't compile them unless you apply them all.

[atrick]

(1) A high-level comment, which may have already been discussed: Rather that eagerly scanning for all callbacks whenever the first assumption is registered for a function, why not do this only when the assumptions are first queried? This may not be very important but seems like a pure win, especially when we have passes that are called repeatedly but may not need to actually query the analysis.

(2) I like that you updated passes the clone instructions to invalidate the cache. But this is not robust. Unfortunately, we don't have a hook for cloning instructions (we probably should). To make up for it, I think you at least need to write a verifier for this analysis, which should be easy.

Otherwise LGTM.

include/llvm/Analysis/AssumptionTracker.h

42–43

This comment looks copy-pasted.

79–80

I don't like this FIXME because it implies a design for concurrency that has not even been formally proposed and would require FIXMEs all over the code.

lib/Analysis/AssumptionTracker.cpp

29

Put 'this' in quotes to clarify meaning.

[reames]

Er, it looks like this patch is missing some of the changes? I don't see AT being piped through all the passes you're trying to use it in?

Overall approach seems reasonable.

include/llvm/Analysis/AssumptionTracker.h

12

Comment could be improved. Specifically, why are they tracked? What is the actually mapping?

Suggestions: pass that keeps track of @llvm.assume intrinsics found in each function of the module. As a result, scanning for assumes is quite cheap and can be used freely by the optimizers.

31

Order wise, I'd reverse this. Interface at the top, details at the bottom. What are most users going to want to find?

91

Naming wise, this is used to force a recalculation, not to remove intrinsics. Maybe a name like "forgetCachedAssumptions" might make that clearer?

102

Might be worth adding a couple of filter ranges here. e.g. dominating_assumptions(F, I), or entry_assumptions(F).

Putting them here would simplify implementation changes later if we wanted to tune for these.

lib/Analysis/AssumptionTracker.cpp

57

I might use a inst_iterator here. Also, I'm not a huge fan of the match notation for such trivial matches, but that's purely stylistic.

71

Adding a check that instruction belongs to a BB might be useful.

75

The choice to scan here is non-obvious. Doing so avoids a rescan latter, but is that valuable?

lib/Transforms/InstCombine/InstCombineCalls.cpp

1005

This part seems bug prone. Don't we already have hook into the builder which catches all adds to the worklist? What about using that mechanism to do assumption recognition?

lib/Transforms/Scalar/LoopUnswitch.cpp

828

I may be missing the obvious here, but where did this AT come from? I don't see it being piped through the class.

[chandlerc]

Generally I agree with Andy's high-level comment about populating the cache lazily. A few minor comments below. Otherwise, I think this makes sense given the current pass infrastructure. I look forward to this kind of thing getting *much* easier to design in the new PM world.

include/llvm/Analysis/AssumptionTracker.h

33

I wouldn't bother with the 'AT' prefix for a nested class.

57–59

Why do you support building these for instructions without parents?

79–80

Agreed.

81–83

Rather than storing the CallHandleSets by value, kep a mapping to unique_ptr<>s to them? That would in turn make it more reasonable to use a small-size optimized container in addition to reducing the size of the top level map.

96–98

I don't think these section comments are really adding much value. It's all pretty clear.

119

Does this actually release memory though?

[hfinkel]

include/llvm/Analysis/AssumptionTracker.h

57–59

Hrmm... maybe this is not needed, IIRC it comes from.... Currently, in AssumptionTracker::ATCallCallbackVH::deleted() I have this:
I->second.erase(cast<CallInst>(getValPtr()))
this causes a new temporary ATCallCallbackVH to be created from getValPtr() in order to remove *this from the map. getValPtr() has already been removed from its parent function, and so it has no parent, which is why this was needed.

[hfinkel]

Regarding the scanning-on-register, the rationale is that:

• It keeps the implementation simple. This way we have an invariant: If a function is in the cache then its set of assumptions is complete. If we don't scan on registration then we could have partial sets in the cache, and we need to keep track of that. Obviously, that could be done, but I'd rather not add the extra complexity unless there is a clear benefit.
• Functions with assumptions will likely be scanned at some point, and because the pass is never invalidated (the analysis is immutable), this is not wasted work (except perhaps that the cache in invalidated when we inline a callee, but that's a separate issue that will be fixed regardless).

A verification function has been added; because the pass manager currently does not verify immutable passes, I added a call to the verification inside the pass's finalization function (this does not provide a huge amount of coverage, but it is something).

include/llvm/Analysis/AssumptionTracker.h

12

Done.

31

Unfortunately, this required a number of forward declarations, and I'm not sure it is worthwhile. Many other analysis classes have their interface at the bottom too for this reason.

33

Done.

42–43

Indeed. Fixed.

57–59

Yes, can be cleaned up (and is in the next version).

79–80

Done.

81–83

Done.

Regarding the small-size-optimized container, we have a SmallDenseMap, however it is not clear to me that the key-set is actually going to be small. It will almost certainly contain all non-empty functions in the module. Is that small?

91

Done.

96–98

Removed.

102

I agree, but let's do this as-needed.

119

Only sometimes ;) -- shrink_and_clear() always does.

lib/Analysis/AssumptionTracker.cpp

29

Done.

57

I'm not sure that buys us anything, the range-based for loop is pretty simple.

71

Done.

75

Documented. (Also see general comment).

lib/Transforms/InstCombine/InstCombineCalls.cpp

1005

Thanks for pointing this out, I did not realize that IRBuilder had that hook. Done.

lib/Transforms/Scalar/LoopUnswitch.cpp

828

Yep; thus the comment about the patch interdependencies when I posted.

[hfinkel]

Updated per reviewer comments (and rebased).

[hfinkel]

r217334, thanks!

include/llvm/Analysis/AssumptionTracker.h

+//===- 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

include/llvm/InitializePasses.h

 void initializeStripSymbolsPass(PassRegistry&);
 void initializeTailCallElimPass(PassRegistry&);
 void initializeTailDuplicatePassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeDataLayoutPassPass(PassRegistry &);
 void initializeTargetTransformInfoAnalysisGroup(PassRegistry&);
 void initializeNoTTIPass(PassRegistry&);
 void initializeTargetLibraryInfoPass(PassRegistry&);
+void initializeAssumptionTrackerPass(PassRegistry &);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAliasAnalysisPass(PassRegistry&);
 void initializeScopedNoAliasAAPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesPass(PassRegistry&);
 void initializeUnreachableBlockElimPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);
 void initializeVirtRegMapPass(PassRegistry&);

lib/Analysis/AssumptionTracker.cpp

+//===- 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;
+

lib/Analysis/CMakeLists.txt

 add_llvm_library(LLVMAnalysis
   AliasAnalysis.cpp
   AliasAnalysisCounter.cpp
   AliasAnalysisEvaluator.cpp
   AliasDebugger.cpp
   AliasSetTracker.cpp
   Analysis.cpp
+  AssumptionTracker.cpp
   BasicAliasAnalysis.cpp
   BlockFrequencyInfo.cpp
   BlockFrequencyInfoImpl.cpp
   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
   CFLAliasAnalysis.cpp
   CGSCCPassManager.cpp

lib/Transforms/InstCombine/InstCombine.h

 //===- InstCombine.h - Main InstCombine pass definition ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 #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"
 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 class CallSite;
 class DataLayout;

 }
 
 /// InstCombineIRInserter - This is an IRBuilder insertion helper that works
 /// just like the normal insertion helper, but also adds any new instructions
 /// to the instcombine worklist.
 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));
   }
 };
 
 /// InstCombiner - The -instcombine pass.
 class LLVM_LIBRARY_VISIBILITY InstCombiner
     : public FunctionPass,
       public InstVisitor<InstCombiner, Instruction *> {
+  AssumptionTracker *AT;
   const DataLayout *DL;
   TargetLibraryInfo *TLI;
   bool MadeIRChange;
   LibCallSimplifier *Simplifier;
   bool MinimizeSize;
 
 public:
   /// Worklist - All of the instructions that need to be simplified.

 
 public:
   bool runOnFunction(Function &F) override;
 
   bool DoOneIteration(Function &F, unsigned ItNum);
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
+  AssumptionTracker *getAssumptionTracker() const { return AT; }
+
   const DataLayout *getDataLayout() const { return DL; }
 
   TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; }
 
   // Visitation implementation - Implement instruction combining for different
   // instruction types.  The semantics are as follows:
   // Return Value:
   //    null        - No change was made

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::stackrestore: {
     // are no allocas or calls between the restore and the return, nuke the
     // restore.
     if (!CannotRemove && (isa<ReturnInst>(TI) || isa<ResumeInst>(TI)))
       return EraseInstFromFunction(CI);
     break;
   }
   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)))) {
       Builder->CreateCall(AssumeIntrinsic, A, II->getName());
       Builder->CreateCall(AssumeIntrinsic, B, II->getName());
       return EraseInstFromFunction(*II);
     }
     // 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;
   }
   }
 
   return visitCallSite(II);
 }

lib/Transforms/InstCombine/InstructionCombining.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
 #include "InstCombine.h"
 #include "llvm-c/Initialization.h"
 #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"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"

 
 void LLVMInitializeInstCombine(LLVMPassRegistryRef R) {
   initializeInstCombine(*unwrap(R));
 }
 
 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>();
 }
 
 
 Value *InstCombiner::EmitGEPOffset(User *GEP) {
   return llvm::EmitGEPOffset(Builder, *getDataLayout(), GEP);
 }
 
public:
   }
 };
 }
 
 bool InstCombiner::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
+  AT = &getAnalysis<AssumptionTracker>();
   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
   DL = DLP ? &DLP->getDataLayout() : nullptr;
   TLI = &getAnalysis<TargetLibraryInfo>();
   // Minimizing size?
   MinimizeSize = F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
                                                 Attribute::MinSize);
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// 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);
   Simplifier = &TheSimplifier;
 
   bool EverMadeChange = false;
 
   // Lower dbg.declare intrinsics otherwise their value may be clobbered

lib/Transforms/Scalar/LoopUnswitch.cpp

for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
     LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L);
   }
 
   // Splice the newly inserted blocks into the function right before the
   // original preheader.
   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);
 
   // Recalculate unswitching quota, inherit simplified switches info for NewBB,
   // Probably clone more loop-unswitch related loop properties.
   BranchesInfo.cloneData(NewLoop, L, VMap);
 
   Loop *ParentLoop = L->getParentLoop();

lib/Transforms/Utils/InlineFunction.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #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"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
Function::iterator FirstNewBlock;
     // Update inlined instructions' line number information.
     fixupLineNumbers(Caller, FirstNewBlock, TheCall);
 
     // Clone existing noalias metadata if necessary.
     CloneAliasScopeMetadata(CS, VMap);
 
     // 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
   // block for the callee, move them to the entry block of the caller.  First
   // calculate which instruction they should be inserted before.  We insert the
   // instructions at the end of the current alloca list.
   {
     BasicBlock::iterator InsertPoint = Caller->begin()->begin();

lib/Transforms/Utils/LoopUnroll.cpp

 // The process of unrolling can produce extraneous basic blocks linked with
 // unconditional branches.  This will be corrected in the future.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/DiagnosticInfo.h"
for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
     if (Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
       if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM,
                                                       ForgottenLoops))
         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
     }
   }
 
+  // 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.
     // Incrementally updating domtree after loop unrolling would be easy.
     if (DominatorTreeWrapperPass *DTWP =
             PP->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
       DT = &DTWP->getDomTree();
       DT->recalculate(*L->getHeader()->getParent());