AssumptionCache.h 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183
  1. //===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume ---*- C++ -*-===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // This file contains a pass that keeps track of @llvm.assume intrinsics in
  11. // the functions of a module (allowing assumptions within any function to be
  12. // found cheaply by other parts of the optimizer).
  13. //
  14. //===----------------------------------------------------------------------===//
  15. #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
  16. #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
  17. #include "llvm/ADT/ArrayRef.h"
  18. #include "llvm/ADT/DenseMap.h"
  19. #include "llvm/ADT/SmallSet.h"
  20. #include "llvm/IR/Function.h"
  21. #include "llvm/IR/Instructions.h"
  22. #include "llvm/IR/ValueHandle.h"
  23. #include "llvm/Pass.h"
  24. #include <memory>
  25. namespace llvm {
  26. // FIXME: Replace this brittle forward declaration with the include of the new
  27. // PassManager.h when doing so doesn't break the PassManagerBuilder.
  28. template <typename IRUnitT> class AnalysisManager;
  29. class PreservedAnalyses;
  30. /// \brief A cache of @llvm.assume calls within a function.
  31. ///
  32. /// This cache provides fast lookup of assumptions within a function by caching
  33. /// them and amortizing the cost of scanning for them across all queries. The
  34. /// cache is also conservatively self-updating so that it will never return
  35. /// incorrect results about a function even as the function is being mutated.
  36. /// However, flushing the cache and rebuilding it (or explicitly updating it)
  37. /// may allow it to discover new assumptions.
  38. class AssumptionCache {
  39. /// \brief The function for which this cache is handling assumptions.
  40. ///
  41. /// We track this to lazily populate our assumptions.
  42. Function &F;
  43. /// \brief Vector of weak value handles to calls of the @llvm.assume
  44. /// intrinsic.
  45. SmallVector<WeakVH, 4> AssumeHandles;
  46. /// \brief Flag tracking whether we have scanned the function yet.
  47. ///
  48. /// We want to be as lazy about this as possible, and so we scan the function
  49. /// at the last moment.
  50. bool Scanned;
  51. /// \brief Scan the function for assumptions and add them to the cache.
  52. void scanFunction();
  53. public:
  54. /// \brief Construct an AssumptionCache from a function by scanning all of
  55. /// its instructions.
  56. AssumptionCache(Function &F) : F(F), Scanned(false) {}
  57. /// \brief Add an @llvm.assume intrinsic to this function's cache.
  58. ///
  59. /// The call passed in must be an instruction within this fuction and must
  60. /// not already be in the cache.
  61. void registerAssumption(CallInst *CI);
  62. /// \brief Clear the cache of @llvm.assume intrinsics for a function.
  63. ///
  64. /// It will be re-scanned the next time it is requested.
  65. void clear() {
  66. AssumeHandles.clear();
  67. Scanned = false;
  68. }
  69. /// \brief Access the list of assumption handles currently tracked for this
  70. /// fuction.
  71. ///
  72. /// Note that these produce weak handles that may be null. The caller must
  73. /// handle that case.
  74. /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
  75. /// when we can write that to filter out the null values. Then caller code
  76. /// will become simpler.
  77. MutableArrayRef<WeakVH> assumptions() {
  78. if (!Scanned)
  79. scanFunction();
  80. return AssumeHandles;
  81. }
  82. };
  83. /// \brief A function analysis which provides an \c AssumptionCache.
  84. ///
  85. /// This analysis is intended for use with the new pass manager and will vend
  86. /// assumption caches for a given function.
  87. class AssumptionAnalysis {
  88. static char PassID;
  89. public:
  90. typedef AssumptionCache Result;
  91. /// \brief Opaque, unique identifier for this analysis pass.
  92. static void *ID() { return (void *)&PassID; }
  93. /// \brief Provide a name for the analysis for debugging and logging.
  94. static StringRef name() { return "AssumptionAnalysis"; }
  95. AssumptionAnalysis() {}
  96. AssumptionAnalysis(const AssumptionAnalysis &Arg) {}
  97. AssumptionAnalysis(AssumptionAnalysis &&Arg) {}
  98. AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; }
  99. AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; }
  100. AssumptionCache run(Function &F) { return AssumptionCache(F); }
  101. };
  102. /// \brief Printer pass for the \c AssumptionAnalysis results.
  103. class AssumptionPrinterPass {
  104. raw_ostream &OS;
  105. public:
  106. explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
  107. PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
  108. static StringRef name() { return "AssumptionPrinterPass"; }
  109. };
  110. /// \brief An immutable pass that tracks lazily created \c AssumptionCache
  111. /// objects.
  112. ///
  113. /// This is essentially a workaround for the legacy pass manager's weaknesses
  114. /// which associates each assumption cache with Function and clears it if the
  115. /// function is deleted. The nature of the AssumptionCache is that it is not
  116. /// invalidated by any changes to the function body and so this is sufficient
  117. /// to be conservatively correct.
  118. class AssumptionCacheTracker : public ImmutablePass {
  119. /// A callback value handle applied to function objects, which we use to
  120. /// delete our cache of intrinsics for a function when it is deleted.
  121. class FunctionCallbackVH : public CallbackVH {
  122. AssumptionCacheTracker *ACT;
  123. void deleted() override;
  124. public:
  125. typedef DenseMapInfo<Value *> DMI;
  126. FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
  127. : CallbackVH(V), ACT(ACT) {}
  128. };
  129. friend FunctionCallbackVH;
  130. typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
  131. FunctionCallbackVH::DMI> FunctionCallsMap;
  132. FunctionCallsMap AssumptionCaches;
  133. public:
  134. /// \brief Get the cached assumptions for a function.
  135. ///
  136. /// If no assumptions are cached, this will scan the function. Otherwise, the
  137. /// existing cache will be returned.
  138. AssumptionCache &getAssumptionCache(Function &F);
  139. AssumptionCacheTracker();
  140. ~AssumptionCacheTracker() override;
  141. void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
  142. void verifyAnalysis() const override;
  143. bool doFinalization(Module &) override {
  144. verifyAnalysis();
  145. return false;
  146. }
  147. static char ID; // Pass identification, replacement for typeid
  148. };
  149. } // end namespace llvm
  150. #endif