1 | //==- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | /// \file |
10 | /// This is the interface for LLVM's unification-based alias analysis |
11 | /// implemented with CFL graph reachability. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H |
16 | #define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H |
17 | |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/Optional.h" |
20 | #include "llvm/Analysis/AliasAnalysis.h" |
21 | #include "llvm/Analysis/CFLAliasAnalysisUtils.h" |
22 | #include "llvm/Analysis/MemoryLocation.h" |
23 | #include "llvm/IR/PassManager.h" |
24 | #include "llvm/Pass.h" |
25 | #include "llvm/Support/Casting.h" |
26 | #include <forward_list> |
27 | #include <memory> |
28 | |
29 | namespace llvm { |
30 | |
31 | class Function; |
32 | class TargetLibraryInfo; |
33 | |
34 | namespace cflaa { |
35 | |
36 | struct AliasSummary; |
37 | |
38 | } // end namespace cflaa |
39 | |
40 | class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> { |
41 | friend AAResultBase<CFLSteensAAResult>; |
42 | |
43 | class FunctionInfo; |
44 | |
45 | public: |
46 | explicit CFLSteensAAResult(const TargetLibraryInfo &TLI); |
47 | CFLSteensAAResult(CFLSteensAAResult &&Arg); |
48 | ~CFLSteensAAResult(); |
49 | |
50 | /// Handle invalidation events from the new pass manager. |
51 | /// |
52 | /// By definition, this result is stateless and so remains valid. |
53 | bool invalidate(Function &, const PreservedAnalyses &, |
54 | FunctionAnalysisManager::Invalidator &) { |
55 | return false; |
56 | } |
57 | |
58 | /// Inserts the given Function into the cache. |
59 | void scan(Function *Fn); |
60 | |
61 | void evict(Function *Fn); |
62 | |
63 | /// Ensures that the given function is available in the cache. |
64 | /// Returns the appropriate entry from the cache. |
65 | const Optional<FunctionInfo> &ensureCached(Function *Fn); |
66 | |
67 | /// Get the alias summary for the given function |
68 | /// Return nullptr if the summary is not found or not available |
69 | const cflaa::AliasSummary *getAliasSummary(Function &Fn); |
70 | |
71 | AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); |
72 | |
73 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
74 | if (LocA.Ptr == LocB.Ptr) |
75 | return MustAlias; |
76 | |
77 | // Comparisons between global variables and other constants should be |
78 | // handled by BasicAA. |
79 | // CFLSteensAA may report NoAlias when comparing a GlobalValue and |
80 | // ConstantExpr, but every query needs to have at least one Value tied to a |
81 | // Function, and neither GlobalValues nor ConstantExprs are. |
82 | if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) |
83 | return AAResultBase::alias(LocA, LocB); |
84 | |
85 | AliasResult QueryResult = query(LocA, LocB); |
86 | if (QueryResult == MayAlias) |
87 | return AAResultBase::alias(LocA, LocB); |
88 | |
89 | return QueryResult; |
90 | } |
91 | |
92 | private: |
93 | const TargetLibraryInfo &TLI; |
94 | |
95 | /// Cached mapping of Functions to their StratifiedSets. |
96 | /// If a function's sets are currently being built, it is marked |
97 | /// in the cache as an Optional without a value. This way, if we |
98 | /// have any kind of recursion, it is discernable from a function |
99 | /// that simply has empty sets. |
100 | DenseMap<Function *, Optional<FunctionInfo>> Cache; |
101 | std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles; |
102 | |
103 | FunctionInfo buildSetsFrom(Function *F); |
104 | }; |
105 | |
106 | /// Analysis pass providing a never-invalidated alias analysis result. |
107 | /// |
108 | /// FIXME: We really should refactor CFL to use the analysis more heavily, and |
109 | /// in particular to leverage invalidation to trigger re-computation of sets. |
110 | class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> { |
111 | friend AnalysisInfoMixin<CFLSteensAA>; |
112 | |
113 | static AnalysisKey Key; |
114 | |
115 | public: |
116 | using Result = CFLSteensAAResult; |
117 | |
118 | CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM); |
119 | }; |
120 | |
121 | /// Legacy wrapper pass to provide the CFLSteensAAResult object. |
122 | class CFLSteensAAWrapperPass : public ImmutablePass { |
123 | std::unique_ptr<CFLSteensAAResult> Result; |
124 | |
125 | public: |
126 | static char ID; |
127 | |
128 | CFLSteensAAWrapperPass(); |
129 | |
130 | CFLSteensAAResult &getResult() { return *Result; } |
131 | const CFLSteensAAResult &getResult() const { return *Result; } |
132 | |
133 | void initializePass() override; |
134 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
135 | }; |
136 | |
137 | // createCFLSteensAAWrapperPass - This pass implements a set-based approach to |
138 | // alias analysis. |
139 | ImmutablePass *createCFLSteensAAWrapperPass(); |
140 | |
141 | } // end namespace llvm |
142 | |
143 | #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H |
144 | |