//===- 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 CondGuardInst;
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(CondGuardInst *CI);
/// Remove an \@llvm.assume intrinsic from this function's cache if it has
/// been added to the cache earlier.
void unregisterAssumption(CondGuardInst *CI);
/// Update the cache of values being affected by this assumption (i.e.
/// the values about which this assumption provides information).
void updateAffectedValues(CondGuardInst *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