1 //==- CFLSteensAliasAnalysis.h - Unification-based Alias Analysis -*- C++-*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// This is the interface for LLVM's unification-based alias analysis 10 /// implemented with CFL graph reachability. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H 15 #define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/Optional.h" 19 #include "llvm/Analysis/AliasAnalysis.h" 20 #include "llvm/Analysis/CFLAliasAnalysisUtils.h" 21 #include "llvm/Analysis/MemoryLocation.h" 22 #include "llvm/IR/PassManager.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/Casting.h" 25 #include <forward_list> 26 #include <memory> 27 28 namespace llvm { 29 30 class Function; 31 class TargetLibraryInfo; 32 33 namespace cflaa { 34 35 struct AliasSummary; 36 37 } // end namespace cflaa 38 39 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> { 40 friend AAResultBase<CFLSteensAAResult>; 41 42 class FunctionInfo; 43 44 public: 45 explicit CFLSteensAAResult( 46 std::function<const TargetLibraryInfo &(Function &)> GetTLI); 47 CFLSteensAAResult(CFLSteensAAResult &&Arg); 48 ~CFLSteensAAResult(); 49 50 /// Handle invalidation events from the new pass manager. 51 /// 52 /// By definition, this result is stateless and so remains valid. invalidate(Function &,const PreservedAnalyses &,FunctionAnalysisManager::Invalidator &)53 bool invalidate(Function &, const PreservedAnalyses &, 54 FunctionAnalysisManager::Invalidator &) { 55 return false; 56 } 57 58 /// Inserts the given Function into the cache. 59 void scan(Function *Fn); 60 61 void evict(Function *Fn); 62 63 /// Ensures that the given function is available in the cache. 64 /// Returns the appropriate entry from the cache. 65 const Optional<FunctionInfo> &ensureCached(Function *Fn); 66 67 /// Get the alias summary for the given function 68 /// Return nullptr if the summary is not found or not available 69 const cflaa::AliasSummary *getAliasSummary(Function &Fn); 70 71 AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB); 72 alias(const MemoryLocation & LocA,const MemoryLocation & LocB,AAQueryInfo & AAQI)73 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, 74 AAQueryInfo &AAQI) { 75 if (LocA.Ptr == LocB.Ptr) 76 return MustAlias; 77 78 // Comparisons between global variables and other constants should be 79 // handled by BasicAA. 80 // CFLSteensAA may report NoAlias when comparing a GlobalValue and 81 // ConstantExpr, but every query needs to have at least one Value tied to a 82 // Function, and neither GlobalValues nor ConstantExprs are. 83 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) 84 return AAResultBase::alias(LocA, LocB, AAQI); 85 86 AliasResult QueryResult = query(LocA, LocB); 87 if (QueryResult == MayAlias) 88 return AAResultBase::alias(LocA, LocB, AAQI); 89 90 return QueryResult; 91 } 92 93 private: 94 std::function<const TargetLibraryInfo &(Function &)> GetTLI; 95 96 /// Cached mapping of Functions to their StratifiedSets. 97 /// If a function's sets are currently being built, it is marked 98 /// in the cache as an Optional without a value. This way, if we 99 /// have any kind of recursion, it is discernable from a function 100 /// that simply has empty sets. 101 DenseMap<Function *, Optional<FunctionInfo>> Cache; 102 std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles; 103 104 FunctionInfo buildSetsFrom(Function *F); 105 }; 106 107 /// Analysis pass providing a never-invalidated alias analysis result. 108 /// 109 /// FIXME: We really should refactor CFL to use the analysis more heavily, and 110 /// in particular to leverage invalidation to trigger re-computation of sets. 111 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> { 112 friend AnalysisInfoMixin<CFLSteensAA>; 113 114 static AnalysisKey Key; 115 116 public: 117 using Result = CFLSteensAAResult; 118 119 CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM); 120 }; 121 122 /// Legacy wrapper pass to provide the CFLSteensAAResult object. 123 class CFLSteensAAWrapperPass : public ImmutablePass { 124 std::unique_ptr<CFLSteensAAResult> Result; 125 126 public: 127 static char ID; 128 129 CFLSteensAAWrapperPass(); 130 getResult()131 CFLSteensAAResult &getResult() { return *Result; } getResult()132 const CFLSteensAAResult &getResult() const { return *Result; } 133 134 void initializePass() override; 135 void getAnalysisUsage(AnalysisUsage &AU) const override; 136 }; 137 138 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to 139 // alias analysis. 140 ImmutablePass *createCFLSteensAAWrapperPass(); 141 142 } // end namespace llvm 143 144 #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H 145