blob: 0efbd59023d6d7d917c8b397695a5a5147f15c7f [file] [log] [blame]
//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume -----*- C++ -*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See 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).
#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 CallInst;
class Function;
class raw_ostream;
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 {
/// The function for which this cache is handling assumptions.
/// We track this to lazily populate our assumptions.
Function &F;
/// Vector of weak value handles to calls of the \@llvm.assume
/// intrinsic.
SmallVector<WeakTrackingVH, 4> AssumeHandles;
class AffectedValueCallbackVH final : public CallbackVH {
AssumptionCache *AC;
void deleted() override;
void allUsesReplacedWith(Value *) override;
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<WeakTrackingVH, 1>,
AffectedValuesMap AffectedValues;
/// Get the vector of assumptions which affect a value from the cache.
SmallVector<WeakTrackingVH, 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();
/// Construct an AssumptionCache from a function by scanning all of
/// its instructions.
AssumptionCache(Function &F) : F(F) {}
/// 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(CallInst *CI);
/// Remove an \@llvm.assume intrinsic from this function's cache if it has
/// been added to the cache earlier.
void unregisterAssumption(CallInst *CI);
/// Update the cache of values being affected by this assumption (i.e.
/// the values about which this assumption provides information).
void updateAffectedValues(CallInst *CI);
/// Clear the cache of \@llvm.assume intrinsics for a function.
/// It will be re-scanned the next time it is requested.
void 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<WeakTrackingVH> assumptions() {
if (!Scanned)
return AssumeHandles;
/// Access the list of assumptions which affect this value.
MutableArrayRef<WeakTrackingVH> assumptionsFor(const Value *V) {
if (!Scanned)
auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
if (AVI == AffectedValues.end())
return MutableArrayRef<WeakTrackingVH>();
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;
using Result = AssumptionCache;
AssumptionCache run(Function &F, FunctionAnalysisManager &) {
return AssumptionCache(F);
/// Printer pass for the \c AssumptionAnalysis results.
class AssumptionPrinterPass : public PassInfoMixin<AssumptionPrinterPass> {
raw_ostream &OS;
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;
using DMI = DenseMapInfo<Value *>;
FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
: CallbackVH(V), ACT(ACT) {}
friend FunctionCallbackVH;
using FunctionCallsMap =
DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
FunctionCallsMap AssumptionCaches;
/// 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() override;
void releaseMemory() override {
void verifyAnalysis() const override;
bool doFinalization(Module &) override {
return false;
static char ID; // Pass identification, replacement for typeid
} // end namespace llvm