aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm14/include/llvm/Analysis/AssumptionCache.h
blob: 4cf76fe5a06cc77d908c52c00f52e97a7eda020b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that keeps track of @llvm.assume intrinsics in
// the functions of a module (allowing assumptions within any function to be
// found cheaply by other parts of the optimizer).
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
#define LLVM_ANALYSIS_ASSUMPTIONCACHE_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include <memory>

namespace llvm {

class AssumeInst;
class Function;
class raw_ostream;
class TargetTransformInfo;
class Value;

/// A cache of \@llvm.assume calls within a function.
///
/// This cache provides fast lookup of assumptions within a function by caching
/// them and amortizing the cost of scanning for them across all queries. Passes
/// that create new assumptions are required to call registerAssumption() to
/// register any new \@llvm.assume calls that they create. Deletions of
/// \@llvm.assume calls do not require special handling.
class AssumptionCache {
public:
  /// Value of ResultElem::Index indicating that the argument to the call of the
  /// llvm.assume.
  enum : unsigned { ExprResultIdx = std::numeric_limits<unsigned>::max() };

  struct ResultElem {
    WeakVH Assume;

    /// contains either ExprResultIdx or the index of the operand bundle
    /// containing the knowledge.
    unsigned Index;
    operator Value *() const { return Assume; }
  };

private:
  /// The function for which this cache is handling assumptions.
  ///
  /// We track this to lazily populate our assumptions.
  Function &F;

  TargetTransformInfo *TTI;

  /// Vector of weak value handles to calls of the \@llvm.assume
  /// intrinsic.
  SmallVector<ResultElem, 4> AssumeHandles;

  class AffectedValueCallbackVH final : public CallbackVH {
    AssumptionCache *AC;

    void deleted() override;
    void allUsesReplacedWith(Value *) override;

  public:
    using DMI = DenseMapInfo<Value *>;

    AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
        : CallbackVH(V), AC(AC) {}
  };

  friend AffectedValueCallbackVH;

  /// A map of values about which an assumption might be providing
  /// information to the relevant set of assumptions.
  using AffectedValuesMap =
      DenseMap<AffectedValueCallbackVH, SmallVector<ResultElem, 1>,
               AffectedValueCallbackVH::DMI>;
  AffectedValuesMap AffectedValues;

  /// Get the vector of assumptions which affect a value from the cache.
  SmallVector<ResultElem, 1> &getOrInsertAffectedValues(Value *V);

  /// Move affected values in the cache for OV to be affected values for NV.
  void transferAffectedValuesInCache(Value *OV, Value *NV);

  /// Flag tracking whether we have scanned the function yet.
  ///
  /// We want to be as lazy about this as possible, and so we scan the function
  /// at the last moment.
  bool Scanned = false;

  /// Scan the function for assumptions and add them to the cache.
  void scanFunction();

public:
  /// Construct an AssumptionCache from a function by scanning all of
  /// its instructions.
  AssumptionCache(Function &F, TargetTransformInfo *TTI = nullptr)
      : F(F), TTI(TTI) {}

  /// This cache is designed to be self-updating and so it should never be
  /// invalidated.
  bool invalidate(Function &, const PreservedAnalyses &,
                  FunctionAnalysisManager::Invalidator &) {
    return false;
  }

  /// Add an \@llvm.assume intrinsic to this function's cache.
  ///
  /// The call passed in must be an instruction within this function and must
  /// not already be in the cache.
  void registerAssumption(AssumeInst *CI);

  /// Remove an \@llvm.assume intrinsic from this function's cache if it has
  /// been added to the cache earlier.
  void unregisterAssumption(AssumeInst *CI);

  /// Update the cache of values being affected by this assumption (i.e.
  /// the values about which this assumption provides information).
  void updateAffectedValues(AssumeInst *CI);

  /// Clear the cache of \@llvm.assume intrinsics for a function.
  ///
  /// It will be re-scanned the next time it is requested.
  void clear() {
    AssumeHandles.clear();
    AffectedValues.clear();
    Scanned = false;
  }

  /// Access the list of assumption handles currently tracked for this
  /// function.
  ///
  /// Note that these produce weak handles that may be null. The caller must
  /// handle that case.
  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
  /// when we can write that to filter out the null values. Then caller code
  /// will become simpler.
  MutableArrayRef<ResultElem> assumptions() {
    if (!Scanned)
      scanFunction();
    return AssumeHandles;
  }

  /// Access the list of assumptions which affect this value.
  MutableArrayRef<ResultElem> assumptionsFor(const Value *V) {
    if (!Scanned)
      scanFunction();

    auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
    if (AVI == AffectedValues.end())
      return MutableArrayRef<ResultElem>();

    return AVI->second;
  }
};

/// A function analysis which provides an \c AssumptionCache.
///
/// This analysis is intended for use with the new pass manager and will vend
/// assumption caches for a given function.
class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {
  friend AnalysisInfoMixin<AssumptionAnalysis>;

  static AnalysisKey Key;

public:
  using Result = AssumptionCache;

  AssumptionCache run(Function &F, FunctionAnalysisManager &);
};

/// Printer pass for the \c AssumptionAnalysis results.
class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
  raw_ostream &OS;

public:
  explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
};

/// An immutable pass that tracks lazily created \c AssumptionCache
/// objects.
///
/// This is essentially a workaround for the legacy pass manager's weaknesses
/// which associates each assumption cache with Function and clears it if the
/// function is deleted. The nature of the AssumptionCache is that it is not
/// invalidated by any changes to the function body and so this is sufficient
/// to be conservatively correct.
class AssumptionCacheTracker : 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 FunctionCallbackVH final : public CallbackVH {
    AssumptionCacheTracker *ACT;

    void deleted() override;

  public:
    using DMI = DenseMapInfo<Value *>;

    FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
        : CallbackVH(V), ACT(ACT) {}
  };

  friend FunctionCallbackVH;

  using FunctionCallsMap =
      DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
               FunctionCallbackVH::DMI>;

  FunctionCallsMap AssumptionCaches;

public:
  /// Get the cached assumptions for a function.
  ///
  /// If no assumptions are cached, this will scan the function. Otherwise, the
  /// existing cache will be returned.
  AssumptionCache &getAssumptionCache(Function &F);

  /// Return the cached assumptions for a function if it has already been
  /// scanned. Otherwise return nullptr.
  AssumptionCache *lookupAssumptionCache(Function &F);

  AssumptionCacheTracker();
  ~AssumptionCacheTracker() override;

  void releaseMemory() override {
    verifyAnalysis();
    AssumptionCaches.shrink_and_clear();
  }

  void verifyAnalysis() const override;

  bool doFinalization(Module &) override {
    verifyAnalysis();
    return false;
  }

  static char ID; // Pass identification, replacement for typeid
};

template<> struct simplify_type<AssumptionCache::ResultElem> {
  using SimpleType = Value *;

  static SimpleType getSimplifiedValue(AssumptionCache::ResultElem &Val) {
    return Val;
  }
};
template<> struct simplify_type<const AssumptionCache::ResultElem> {
  using SimpleType = /*const*/ Value *;

  static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val) {
    return Val;
  }
};

} // end namespace llvm

#endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif