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/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>
27 
28 namespace llvm {
29 
30 class TargetLibraryInfo;
31 
32 namespace cflaa {
33 struct AliasSummary;
34 }
35 
36 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
37   friend AAResultBase<CFLSteensAAResult>;
38   class FunctionInfo;
39 
40 public:
41   explicit CFLSteensAAResult(const TargetLibraryInfo &);
42   CFLSteensAAResult(CFLSteensAAResult &&Arg);
43   ~CFLSteensAAResult();
44 
45   /// Handle invalidation events from the new pass manager.
46   ///
47   /// By definition, this result is stateless and so remains valid.
invalidate(Function &,const PreservedAnalyses &)48   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
49 
50   /// \brief Inserts the given Function into the cache.
51   void scan(Function *Fn);
52 
53   void evict(Function *Fn);
54 
55   /// \brief Ensures that the given function is available in the cache.
56   /// Returns the appropriate entry from the cache.
57   const Optional<FunctionInfo> &ensureCached(Function *Fn);
58 
59   /// \brief Get the alias summary for the given function
60   /// Return nullptr if the summary is not found or not available
61   const cflaa::AliasSummary *getAliasSummary(Function &Fn);
62 
63   AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
64 
alias(const MemoryLocation & LocA,const MemoryLocation & LocB)65   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
66     if (LocA.Ptr == LocB.Ptr)
67       return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
68 
69     // Comparisons between global variables and other constants should be
70     // handled by BasicAA.
71     // CFLSteensAA may report NoAlias when comparing a GlobalValue and
72     // ConstantExpr, but every query needs to have at least one Value tied to a
73     // Function, and neither GlobalValues nor ConstantExprs are.
74     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
75       return AAResultBase::alias(LocA, LocB);
76 
77     AliasResult QueryResult = query(LocA, LocB);
78     if (QueryResult == MayAlias)
79       return AAResultBase::alias(LocA, LocB);
80 
81     return QueryResult;
82   }
83 
84   /// Get the location associated with a pointer argument of a callsite.
85   ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
86 
87   /// Returns the behavior when calling the given call site.
88   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
89 
90   /// Returns the behavior when calling the given function. For use when the
91   /// call site is not known.
92   FunctionModRefBehavior getModRefBehavior(const Function *F);
93 
94 private:
95   struct FunctionHandle final : public CallbackVH {
FunctionHandlefinal96     FunctionHandle(Function *Fn, CFLSteensAAResult *Result)
97         : CallbackVH(Fn), Result(Result) {
98       assert(Fn != nullptr);
99       assert(Result != nullptr);
100     }
101 
deletedfinal102     void deleted() override { removeSelfFromCache(); }
allUsesReplacedWithfinal103     void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
104 
105   private:
106     CFLSteensAAResult *Result;
107 
removeSelfFromCachefinal108     void removeSelfFromCache() {
109       assert(Result != nullptr);
110       auto *Val = getValPtr();
111       Result->evict(cast<Function>(Val));
112       setValPtr(nullptr);
113     }
114   };
115 
116   const TargetLibraryInfo &TLI;
117 
118   /// \brief Cached mapping of Functions to their StratifiedSets.
119   /// If a function's sets are currently being built, it is marked
120   /// in the cache as an Optional without a value. This way, if we
121   /// have any kind of recursion, it is discernable from a function
122   /// that simply has empty sets.
123   DenseMap<Function *, Optional<FunctionInfo>> Cache;
124   std::forward_list<FunctionHandle> Handles;
125 
126   FunctionInfo buildSetsFrom(Function *F);
127 };
128 
129 /// Analysis pass providing a never-invalidated alias analysis result.
130 ///
131 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
132 /// in particular to leverage invalidation to trigger re-computation of sets.
133 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
134   friend AnalysisInfoMixin<CFLSteensAA>;
135   static char PassID;
136 
137 public:
138   typedef CFLSteensAAResult Result;
139 
140   CFLSteensAAResult run(Function &F, AnalysisManager<Function> &AM);
141 };
142 
143 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
144 class CFLSteensAAWrapperPass : public ImmutablePass {
145   std::unique_ptr<CFLSteensAAResult> Result;
146 
147 public:
148   static char ID;
149 
150   CFLSteensAAWrapperPass();
151 
getResult()152   CFLSteensAAResult &getResult() { return *Result; }
getResult()153   const CFLSteensAAResult &getResult() const { return *Result; }
154 
155   void initializePass() override;
156   void getAnalysisUsage(AnalysisUsage &AU) const override;
157 };
158 
159 //===--------------------------------------------------------------------===//
160 //
161 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
162 // alias analysis.
163 //
164 ImmutablePass *createCFLSteensAAWrapperPass();
165 }
166 
167 #endif
168