1 //=- CFLAndersAliasAnalysis.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 inclusion-based alias analysis 11 /// implemented with CFL graph reachability. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H 16 #define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H 17 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/Optional.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/IR/Function.h" 22 #include "llvm/IR/ValueHandle.h" 23 #include "llvm/Pass.h" 24 #include <forward_list> 25 26 namespace llvm { 27 28 class TargetLibraryInfo; 29 30 namespace cflaa { 31 struct AliasSummary; 32 } 33 34 class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> { 35 friend AAResultBase<CFLAndersAAResult>; 36 class FunctionInfo; 37 38 public: 39 explicit CFLAndersAAResult(const TargetLibraryInfo &); 40 CFLAndersAAResult(CFLAndersAAResult &&); 41 ~CFLAndersAAResult(); 42 43 /// Handle invalidation events from the new pass manager. 44 /// By definition, this result is stateless and so remains valid. 45 bool invalidate(Function &, const PreservedAnalyses &, 46 FunctionAnalysisManager::Invalidator &) { 47 return false; 48 } 49 /// Evict the given function from cache 50 void evict(const Function &Fn); 51 52 /// \brief Get the alias summary for the given function 53 /// Return nullptr if the summary is not found or not available 54 const cflaa::AliasSummary *getAliasSummary(const Function &); 55 56 AliasResult query(const MemoryLocation &, const MemoryLocation &); 57 AliasResult alias(const MemoryLocation &, const MemoryLocation &); 58 59 private: 60 struct FunctionHandle final : public CallbackVH { 61 FunctionHandle(Function *Fn, CFLAndersAAResult *Result) 62 : CallbackVH(Fn), Result(Result) { 63 assert(Fn != nullptr); 64 assert(Result != nullptr); 65 } 66 67 void deleted() override { removeSelfFromCache(); } 68 void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } 69 70 private: 71 CFLAndersAAResult *Result; 72 73 void removeSelfFromCache() { 74 assert(Result != nullptr); 75 auto *Val = getValPtr(); 76 Result->evict(*cast<Function>(Val)); 77 setValPtr(nullptr); 78 } 79 }; 80 81 /// \brief Ensures that the given function is available in the cache. 82 /// Returns the appropriate entry from the cache. 83 const Optional<FunctionInfo> &ensureCached(const Function &); 84 85 /// \brief Inserts the given Function into the cache. 86 void scan(const Function &); 87 88 /// \brief Build summary for a given function 89 FunctionInfo buildInfoFrom(const Function &); 90 91 const TargetLibraryInfo &TLI; 92 93 /// \brief Cached mapping of Functions to their StratifiedSets. 94 /// If a function's sets are currently being built, it is marked 95 /// in the cache as an Optional without a value. This way, if we 96 /// have any kind of recursion, it is discernable from a function 97 /// that simply has empty sets. 98 DenseMap<const Function *, Optional<FunctionInfo>> Cache; 99 100 std::forward_list<FunctionHandle> Handles; 101 }; 102 103 /// Analysis pass providing a never-invalidated alias analysis result. 104 /// 105 /// FIXME: We really should refactor CFL to use the analysis more heavily, and 106 /// in particular to leverage invalidation to trigger re-computation. 107 class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> { 108 friend AnalysisInfoMixin<CFLAndersAA>; 109 static AnalysisKey Key; 110 111 public: 112 typedef CFLAndersAAResult Result; 113 114 CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM); 115 }; 116 117 /// Legacy wrapper pass to provide the CFLAndersAAResult object. 118 class CFLAndersAAWrapperPass : public ImmutablePass { 119 std::unique_ptr<CFLAndersAAResult> Result; 120 121 public: 122 static char ID; 123 124 CFLAndersAAWrapperPass(); 125 126 CFLAndersAAResult &getResult() { return *Result; } 127 const CFLAndersAAResult &getResult() const { return *Result; } 128 129 void initializePass() override; 130 void getAnalysisUsage(AnalysisUsage &AU) const override; 131 }; 132 133 //===--------------------------------------------------------------------===// 134 // 135 // createCFLAndersAAWrapperPass - This pass implements a set-based approach to 136 // alias analysis. 137 // 138 ImmutablePass *createCFLAndersAAWrapperPass(); 139 } 140 141 #endif 142