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