Coverage Report

Created: 2018-07-12 09:57

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/AssumptionCache.h
Line
Count
Source (jump to first uncovered line)
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/DenseMapInfo.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/IR/PassManager.h"
24
#include "llvm/IR/ValueHandle.h"
25
#include "llvm/Pass.h"
26
#include <memory>
27
28
namespace llvm {
29
30
class CallInst;
31
class Function;
32
class raw_ostream;
33
class Value;
34
35
/// A cache of \@llvm.assume calls within a function.
36
///
37
/// This cache provides fast lookup of assumptions within a function by caching
38
/// them and amortizing the cost of scanning for them across all queries. Passes
39
/// that create new assumptions are required to call registerAssumption() to
40
/// register any new \@llvm.assume calls that they create. Deletions of
41
/// \@llvm.assume calls do not require special handling.
42
class AssumptionCache {
43
  /// The function for which this cache is handling assumptions.
44
  ///
45
  /// We track this to lazily populate our assumptions.
46
  Function &F;
47
48
  /// Vector of weak value handles to calls of the \@llvm.assume
49
  /// intrinsic.
50
  SmallVector<WeakTrackingVH, 4> AssumeHandles;
51
52
0
  class AffectedValueCallbackVH final : public CallbackVH {
53
    AssumptionCache *AC;
54
55
    void deleted() override;
56
    void allUsesReplacedWith(Value *) override;
57
58
  public:
59
    using DMI = DenseMapInfo<Value *>;
60
61
    AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
62
71.6k
        : CallbackVH(V), AC(AC) {}
63
  };
64
65
  friend AffectedValueCallbackVH;
66
67
  /// A map of values about which an assumption might be providing
68
  /// information to the relevant set of assumptions.
69
  using AffectedValuesMap =
70
      DenseMap<AffectedValueCallbackVH, SmallVector<WeakTrackingVH, 1>,
71
               AffectedValueCallbackVH::DMI>;
72
  AffectedValuesMap AffectedValues;
73
74
  /// Get the vector of assumptions which affect a value from the cache.
75
  SmallVector<WeakTrackingVH, 1> &getOrInsertAffectedValues(Value *V);
76
77
  /// Copy affected values in the cache for OV to be affected values for NV.
78
  void copyAffectedValuesInCache(Value *OV, Value *NV);
79
80
  /// Flag tracking whether we have scanned the function yet.
81
  ///
82
  /// We want to be as lazy about this as possible, and so we scan the function
83
  /// at the last moment.
84
  bool Scanned = false;
85
86
  /// Scan the function for assumptions and add them to the cache.
87
  void scanFunction();
88
89
public:
90
  /// Construct an AssumptionCache from a function by scanning all of
91
  /// its instructions.
92
1.68M
  AssumptionCache(Function &F) : F(F) {}
93
94
  /// This cache is designed to be self-updating and so it should never be
95
  /// invalidated.
96
  bool invalidate(Function &, const PreservedAnalyses &,
97
2.29k
                  FunctionAnalysisManager::Invalidator &) {
98
2.29k
    return false;
99
2.29k
  }
100
101
  /// Add an \@llvm.assume intrinsic to this function's cache.
102
  ///
103
  /// The call passed in must be an instruction within this function and must
104
  /// not already be in the cache.
105
  void registerAssumption(CallInst *CI);
106
107
  /// Update the cache of values being affected by this assumption (i.e.
108
  /// the values about which this assumption provides information).
109
  void updateAffectedValues(CallInst *CI);
110
111
  /// Clear the cache of \@llvm.assume intrinsics for a function.
112
  ///
113
  /// It will be re-scanned the next time it is requested.
114
0
  void clear() {
115
0
    AssumeHandles.clear();
116
0
    AffectedValues.clear();
117
0
    Scanned = false;
118
0
  }
119
120
  /// Access the list of assumption handles currently tracked for this
121
  /// function.
122
  ///
123
  /// Note that these produce weak handles that may be null. The caller must
124
  /// handle that case.
125
  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
126
  /// when we can write that to filter out the null values. Then caller code
127
  /// will become simpler.
128
4.68M
  MutableArrayRef<WeakTrackingVH> assumptions() {
129
4.68M
    if (!Scanned)
130
77.4k
      scanFunction();
131
4.68M
    return AssumeHandles;
132
4.68M
  }
133
134
  /// Access the list of assumptions which affect this value.
135
522M
  MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) {
136
522M
    if (!Scanned)
137
762k
      scanFunction();
138
522M
139
522M
    auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
140
522M
    if (AVI == AffectedValues.end())
141
522M
      return MutableArrayRef<WeakTrackingVH>();
142
2.96k
143
2.96k
    return AVI->second;
144
2.96k
  }
145
};
146
147
/// A function analysis which provides an \c AssumptionCache.
148
///
149
/// This analysis is intended for use with the new pass manager and will vend
150
/// assumption caches for a given function.
151
class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
152
  friend AnalysisInfoMixin<AssumptionAnalysis>;
153
154
  static AnalysisKey Key;
155
156
public:
157
  using Result = AssumptionCache;
158
159
2.08k
  AssumptionCache run(Function &F, FunctionAnalysisManager &) {
160
2.08k
    return AssumptionCache(F);
161
2.08k
  }
162
};
163
164
/// Printer pass for the \c AssumptionAnalysis results.
165
class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
166
  raw_ostream &OS;
167
168
public:
169
1
  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
170
171
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
172
};
173
174
/// An immutable pass that tracks lazily created \c AssumptionCache
175
/// objects.
176
///
177
/// This is essentially a workaround for the legacy pass manager's weaknesses
178
/// which associates each assumption cache with Function and clears it if the
179
/// function is deleted. The nature of the AssumptionCache is that it is not
180
/// invalidated by any changes to the function body and so this is sufficient
181
/// to be conservatively correct.
182
class AssumptionCacheTracker : public ImmutablePass {
183
  /// A callback value handle applied to function objects, which we use to
184
  /// delete our cache of intrinsics for a function when it is deleted.
185
  class FunctionCallbackVH final : public CallbackVH {
186
    AssumptionCacheTracker *ACT;
187
188
    void deleted() override;
189
190
  public:
191
    using DMI = DenseMapInfo<Value *>;
192
193
    FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
194
76.0M
        : CallbackVH(V), ACT(ACT) {}
195
  };
196
197
  friend FunctionCallbackVH;
198
199
  using FunctionCallsMap =
200
      DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
201
               FunctionCallbackVH::DMI>;
202
203
  FunctionCallsMap AssumptionCaches;
204
205
public:
206
  /// Get the cached assumptions for a function.
207
  ///
208
  /// If no assumptions are cached, this will scan the function. Otherwise, the
209
  /// existing cache will be returned.
210
  AssumptionCache &getAssumptionCache(Function &F);
211
212
  AssumptionCacheTracker();
213
  ~AssumptionCacheTracker() override;
214
215
82.1k
  void releaseMemory() override {
216
82.1k
    verifyAnalysis();
217
82.1k
    AssumptionCaches.shrink_and_clear();
218
82.1k
  }
219
220
  void verifyAnalysis() const override;
221
222
71.7k
  bool doFinalization(Module &) override {
223
71.7k
    verifyAnalysis();
224
71.7k
    return false;
225
71.7k
  }
226
227
  static char ID; // Pass identification, replacement for typeid
228
};
229
230
} // end namespace llvm
231
232
#endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H