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/Analysis/CFLAliasAnalysisUtils.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Pass.h"
27 #include <forward_list>
31 class TargetLibraryInfo;
37 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
38 friend AAResultBase<CFLSteensAAResult>;
42 explicit CFLSteensAAResult(const TargetLibraryInfo &);
43 CFLSteensAAResult(CFLSteensAAResult &&Arg);
46 /// Handle invalidation events from the new pass manager.
48 /// By definition, this result is stateless and so remains valid.
49 bool invalidate(Function &, const PreservedAnalyses &,
50 FunctionAnalysisManager::Invalidator &) {
54 /// \brief Inserts the given Function into the cache.
55 void scan(Function *Fn);
57 void evict(Function *Fn);
59 /// \brief Ensures that the given function is available in the cache.
60 /// Returns the appropriate entry from the cache.
61 const Optional<FunctionInfo> &ensureCached(Function *Fn);
63 /// \brief Get the alias summary for the given function
64 /// Return nullptr if the summary is not found or not available
65 const cflaa::AliasSummary *getAliasSummary(Function &Fn);
67 AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
69 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
70 if (LocA.Ptr == LocB.Ptr)
71 return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
73 // Comparisons between global variables and other constants should be
74 // handled by BasicAA.
75 // CFLSteensAA may report NoAlias when comparing a GlobalValue and
76 // ConstantExpr, but every query needs to have at least one Value tied to a
77 // Function, and neither GlobalValues nor ConstantExprs are.
78 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
79 return AAResultBase::alias(LocA, LocB);
81 AliasResult QueryResult = query(LocA, LocB);
82 if (QueryResult == MayAlias)
83 return AAResultBase::alias(LocA, LocB);
89 const TargetLibraryInfo &TLI;
91 /// \brief Cached mapping of Functions to their StratifiedSets.
92 /// If a function's sets are currently being built, it is marked
93 /// in the cache as an Optional without a value. This way, if we
94 /// have any kind of recursion, it is discernable from a function
95 /// that simply has empty sets.
96 DenseMap<Function *, Optional<FunctionInfo>> Cache;
97 std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
99 FunctionInfo buildSetsFrom(Function *F);
102 /// Analysis pass providing a never-invalidated alias analysis result.
104 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
105 /// in particular to leverage invalidation to trigger re-computation of sets.
106 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
107 friend AnalysisInfoMixin<CFLSteensAA>;
108 static AnalysisKey Key;
111 typedef CFLSteensAAResult Result;
113 CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
116 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
117 class CFLSteensAAWrapperPass : public ImmutablePass {
118 std::unique_ptr<CFLSteensAAResult> Result;
123 CFLSteensAAWrapperPass();
125 CFLSteensAAResult &getResult() { return *Result; }
126 const CFLSteensAAResult &getResult() const { return *Result; }
128 void initializePass() override;
129 void getAnalysisUsage(AnalysisUsage &AU) const override;
132 //===--------------------------------------------------------------------===//
134 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
137 ImmutablePass *createCFLSteensAAWrapperPass();