1 //===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- 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 primary stateless and local alias analysis. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H 15 #define LLVM_ANALYSIS_CFLALIASANALYSIS_H 16 17 #include "llvm/Analysis/AliasAnalysis.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/None.h" 20 #include "llvm/ADT/Optional.h" 21 #include "llvm/IR/Function.h" 22 #include "llvm/IR/Module.h" 23 #include "llvm/IR/ValueHandle.h" 24 #include "llvm/Pass.h" 25 #include <forward_list> 26 27 namespace llvm { 28 29 class CFLAAResult : public AAResultBase<CFLAAResult> { 30 friend AAResultBase<CFLAAResult>; 31 32 struct FunctionInfo; 33 34 public: 35 explicit CFLAAResult(const TargetLibraryInfo &TLI); 36 CFLAAResult(CFLAAResult &&Arg); 37 38 /// Handle invalidation events from the new pass manager. 39 /// 40 /// By definition, this result is stateless and so remains valid. invalidate(Function &,const PreservedAnalyses &)41 bool invalidate(Function &, const PreservedAnalyses &) { return false; } 42 43 /// \brief Inserts the given Function into the cache. 44 void scan(Function *Fn); 45 46 void evict(Function *Fn); 47 48 /// \brief Ensures that the given function is available in the cache. 49 /// Returns the appropriate entry from the cache. 50 const Optional<FunctionInfo> &ensureCached(Function *Fn); 51 52 AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); 53 alias(const MemoryLocation & LocA,const MemoryLocation & LocB)54 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { 55 if (LocA.Ptr == LocB.Ptr) { 56 if (LocA.Size == LocB.Size) { 57 return MustAlias; 58 } else { 59 return PartialAlias; 60 } 61 } 62 63 // Comparisons between global variables and other constants should be 64 // handled by BasicAA. 65 // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing 66 // a GlobalValue and ConstantExpr, but every query needs to have at least 67 // one Value tied to a Function, and neither GlobalValues nor ConstantExprs 68 // are. 69 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) { 70 return AAResultBase::alias(LocA, LocB); 71 } 72 73 AliasResult QueryResult = query(LocA, LocB); 74 if (QueryResult == MayAlias) 75 return AAResultBase::alias(LocA, LocB); 76 77 return QueryResult; 78 } 79 80 private: 81 struct FunctionHandle final : public CallbackVH { FunctionHandlefinal82 FunctionHandle(Function *Fn, CFLAAResult *Result) 83 : CallbackVH(Fn), Result(Result) { 84 assert(Fn != nullptr); 85 assert(Result != nullptr); 86 } 87 deletedfinal88 void deleted() override { removeSelfFromCache(); } allUsesReplacedWithfinal89 void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } 90 91 private: 92 CFLAAResult *Result; 93 removeSelfFromCachefinal94 void removeSelfFromCache() { 95 assert(Result != nullptr); 96 auto *Val = getValPtr(); 97 Result->evict(cast<Function>(Val)); 98 setValPtr(nullptr); 99 } 100 }; 101 102 /// \brief Cached mapping of Functions to their StratifiedSets. 103 /// If a function's sets are currently being built, it is marked 104 /// in the cache as an Optional without a value. This way, if we 105 /// have any kind of recursion, it is discernable from a function 106 /// that simply has empty sets. 107 DenseMap<Function *, Optional<FunctionInfo>> Cache; 108 std::forward_list<FunctionHandle> Handles; 109 110 FunctionInfo buildSetsFrom(Function *F); 111 }; 112 113 /// Analysis pass providing a never-invalidated alias analysis result. 114 /// 115 /// FIXME: We really should refactor CFL to use the analysis more heavily, and 116 /// in particular to leverage invalidation to trigger re-computation of sets. 117 class CFLAA { 118 public: 119 typedef CFLAAResult Result; 120 121 /// \brief Opaque, unique identifier for this analysis pass. ID()122 static void *ID() { return (void *)&PassID; } 123 124 CFLAAResult run(Function &F, AnalysisManager<Function> *AM); 125 126 /// \brief Provide access to a name for this pass for debugging purposes. name()127 static StringRef name() { return "CFLAA"; } 128 129 private: 130 static char PassID; 131 }; 132 133 /// Legacy wrapper pass to provide the CFLAAResult object. 134 class CFLAAWrapperPass : public ImmutablePass { 135 std::unique_ptr<CFLAAResult> Result; 136 137 public: 138 static char ID; 139 140 CFLAAWrapperPass(); 141 getResult()142 CFLAAResult &getResult() { return *Result; } getResult()143 const CFLAAResult &getResult() const { return *Result; } 144 145 bool doInitialization(Module &M) override; 146 bool doFinalization(Module &M) override; 147 void getAnalysisUsage(AnalysisUsage &AU) const override; 148 }; 149 150 //===--------------------------------------------------------------------===// 151 // 152 // createCFLAAWrapperPass - This pass implements a set-based approach to 153 // alias analysis. 154 // 155 ImmutablePass *createCFLAAWrapperPass(); 156 } 157 158 #endif 159