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