1 //=- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis ---*- C++-*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This is the interface for LLVM's unification-based alias analysis
11 /// implemented with CFL graph reachability.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
16 #define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/ValueHandle.h"
25 #include "llvm/Pass.h"
26 #include <forward_list>
30 class TargetLibraryInfo;
36 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
37 friend AAResultBase<CFLSteensAAResult>;
41 explicit CFLSteensAAResult(const TargetLibraryInfo &);
42 CFLSteensAAResult(CFLSteensAAResult &&Arg);
45 /// Handle invalidation events from the new pass manager.
47 /// By definition, this result is stateless and so remains valid.
48 bool invalidate(Function &, const PreservedAnalyses &,
49 FunctionAnalysisManager::Invalidator &) {
53 /// \brief Inserts the given Function into the cache.
54 void scan(Function *Fn);
56 void evict(Function *Fn);
58 /// \brief Ensures that the given function is available in the cache.
59 /// Returns the appropriate entry from the cache.
60 const Optional<FunctionInfo> &ensureCached(Function *Fn);
62 /// \brief Get the alias summary for the given function
63 /// Return nullptr if the summary is not found or not available
64 const cflaa::AliasSummary *getAliasSummary(Function &Fn);
66 AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
68 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
69 if (LocA.Ptr == LocB.Ptr)
70 return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
72 // Comparisons between global variables and other constants should be
73 // handled by BasicAA.
74 // CFLSteensAA may report NoAlias when comparing a GlobalValue and
75 // ConstantExpr, but every query needs to have at least one Value tied to a
76 // Function, and neither GlobalValues nor ConstantExprs are.
77 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
78 return AAResultBase::alias(LocA, LocB);
80 AliasResult QueryResult = query(LocA, LocB);
81 if (QueryResult == MayAlias)
82 return AAResultBase::alias(LocA, LocB);
88 struct FunctionHandle final : public CallbackVH {
89 FunctionHandle(Function *Fn, CFLSteensAAResult *Result)
90 : CallbackVH(Fn), Result(Result) {
91 assert(Fn != nullptr);
92 assert(Result != nullptr);
95 void deleted() override { removeSelfFromCache(); }
96 void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
99 CFLSteensAAResult *Result;
101 void removeSelfFromCache() {
102 assert(Result != nullptr);
103 auto *Val = getValPtr();
104 Result->evict(cast<Function>(Val));
109 const TargetLibraryInfo &TLI;
111 /// \brief Cached mapping of Functions to their StratifiedSets.
112 /// If a function's sets are currently being built, it is marked
113 /// in the cache as an Optional without a value. This way, if we
114 /// have any kind of recursion, it is discernable from a function
115 /// that simply has empty sets.
116 DenseMap<Function *, Optional<FunctionInfo>> Cache;
117 std::forward_list<FunctionHandle> Handles;
119 FunctionInfo buildSetsFrom(Function *F);
122 /// Analysis pass providing a never-invalidated alias analysis result.
124 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
125 /// in particular to leverage invalidation to trigger re-computation of sets.
126 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
127 friend AnalysisInfoMixin<CFLSteensAA>;
128 static AnalysisKey Key;
131 typedef CFLSteensAAResult Result;
133 CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
136 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
137 class CFLSteensAAWrapperPass : public ImmutablePass {
138 std::unique_ptr<CFLSteensAAResult> Result;
143 CFLSteensAAWrapperPass();
145 CFLSteensAAResult &getResult() { return *Result; }
146 const CFLSteensAAResult &getResult() const { return *Result; }
148 void initializePass() override;
149 void getAnalysisUsage(AnalysisUsage &AU) const override;
152 //===--------------------------------------------------------------------===//
154 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
157 ImmutablePass *createCFLSteensAAWrapperPass();