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

41–42

This comment looks copy-pasted.

78–79

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

28

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

11

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.

30

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

90

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

101

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

56

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.

70

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

74

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

lib/Transforms/InstCombine/InstCombineCalls.cpp

1003

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

32

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

56–58

Why do you support building these for instructions without parents?

78–79

Agreed.

80–82

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.

95–97

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

118

Does this actually release memory though?

[hfinkel]

include/llvm/Analysis/AssumptionTracker.h

56–58

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

11

Done.

30

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.

32

Done.

41–42

Indeed. Fixed.

56–58

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

78–79

Done.

80–82

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?

90

Done.

95–97

Removed.

101

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

118

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

lib/Analysis/AssumptionTracker.cpp

28

Done.

56

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

70

Done.

74

Documented. (Also see general comment).

lib/Transforms/InstCombine/InstCombineCalls.cpp

1003

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.
+//
+//===----------------------------------------------------------------------===//
+
+#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"
+
+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 ATFunctionCallbackVH : public CallbackVH {
+    AssumptionTracker *AT;
+    void deleted() override;
+
+    public:
+      ATFunctionCallbackVH(Value *V, AssumptionTracker *AT = nullptr)
+        : CallbackVH(V), AT(AT) {}
+  };
+
+  /// 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 ATCallCallbackVH : 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;
+
+      ATCallCallbackVH(Instruction *I, AssumptionTracker *AT = nullptr)
+        : CallbackVH(I), AT(AT), F(nullptr) {
+        if (I != DMI::getEmptyKey() && I != DMI::getTombstoneKey() &&
+            I->getParent())
+          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 ATFunctionCallbackVH;
+  friend ATCallCallbackVH;
+
+  // FIXME: SmallSet might be better here, but it currently has no iterators.
+  typedef DenseSet<ATCallCallbackVH, ATCallCallbackVH::DMI> CallHandleSet;
+  // FIXME: DenseMap is not thread safe; if we ever run function passes
+  // concurrently, this will need to be changed!
+  typedef DenseMap<ATFunctionCallbackVH, CallHandleSet,
+                   DenseMapInfo<Value *>> 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 clearAssumptions(Function *F);
+
+  /// Add an @llvm.assume intrinsic to the cache for its parent function.
+  void registerAssumption(CallInst *CI);
+
+  // ---------------------------------------------------------------------------
+  // Assumption Iterator interface...
+  //
+  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());
+  }
+
+  // ---------------------------------------------------------------------------
+  // Pass interface...
+  //
+
+  AssumptionTracker();
+  ~AssumptionTracker();
+
+  void releaseMemory() override {
+    CachedAssumeCalls.clear();
+  }
+
+  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::ATFunctionCallbackVH::deleted() {
+  AT->clearAssumptions(cast<Function>(getValPtr()));
+  // this now dangles!
+}
+
+void AssumptionTracker::clearAssumptions(Function *F) {
+  CachedAssumeCalls.erase(F);
+}
+
+void AssumptionTracker::ATCallCallbackVH::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(cast<CallInst>(getValPtr()));
+  // this now dangles!
+}
+
+AssumptionTracker::FunctionCallsMap::iterator
+AssumptionTracker::scanFunction(Function *F) {
+  auto IP =
+    CachedAssumeCalls.insert(std::make_pair(ATFunctionCallbackVH(F, this),
+                                            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(ATCallCallbackVH(&II, this));
+
+  return I;
+}
+
+void AssumptionTracker::registerAssumption(CallInst *CI) {
+  assert(match(cast<Value>(CI),
+               m_Intrinsic<Intrinsic::assume>(m_Value())) &&
+         "Registered call does not call @llvm.assume");
+
+  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(ATCallCallbackVH(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
   CGSCCPassManager.cpp
   CaptureTracking.cpp

lib/Transforms/InstCombine/InstCombine.h

 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 class CallSite;
+class AssumptionTracker;
 class DataLayout;
 class TargetLibraryInfo;
 class DbgDeclareInst;
 class MemIntrinsic;
 class MemSetInst;
 
 /// SelectPatternFlavor - We can match a variety of different patterns for
 /// select operations.
void InsertHelper(Instruction *I, const Twine &Name, BasicBlock *BB,
     Worklist.Add(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

 //===- InstCombineCalls.cpp -----------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitCall and visitInvoke functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombine.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionTracker.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 using namespace PatternMatch;
if (!CannotRemove && (isa<ReturnInst>(TI) || isa<ResumeInst>(TI)))
       return EraseInstFromFunction(CI);
     break;
   }
   case Intrinsic::assume: {
     // Canonicalize assume(a && b) -> assume(a); assume(b);
     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());
+      AT->registerAssumption(
+        Builder->CreateCall(AssumeIntrinsic, A, II->getName()));
+      AT->registerAssumption(
+        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());
+      AT->registerAssumption(
+        Builder->CreateCall(AssumeIntrinsic, Builder->CreateNot(A), II->getName()));
+      AT->registerAssumption(
+        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

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->clearAssumptions(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);
+
+    // FIXME: We could register any cloned assumptions instead of clearing the
+    // whole function's cache.
+    if (IFI.AT)
+      IFI.AT->clearAssumptions(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->clearAssumptions(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());