Coverage Report

Created: 2019-03-24 22:13

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