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