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 28namespace llvm { 29 30class TargetLibraryInfo; 31 32namespace cflaa { 33struct AliasSummary; 34} 35 36class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> { 37 friend AAResultBase<CFLSteensAAResult>; 38 class FunctionInfo; 39 40public: 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 &) { 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 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 94private: 95 struct FunctionHandle final : public CallbackVH { 96 FunctionHandle(Function *Fn, CFLSteensAAResult *Result) 97 : CallbackVH(Fn), Result(Result) { 98 assert(Fn != nullptr); 99 assert(Result != nullptr); 100 } 101 102 void deleted() override { removeSelfFromCache(); } 103 void allUsesReplacedWith(Value *) override { removeSelfFromCache(); } 104 105 private: 106 CFLSteensAAResult *Result; 107 108 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. 133class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> { 134 friend AnalysisInfoMixin<CFLSteensAA>; 135 static char PassID; 136 137public: 138 typedef CFLSteensAAResult Result; 139 140 CFLSteensAAResult run(Function &F, AnalysisManager<Function> &AM); 141}; 142 143/// Legacy wrapper pass to provide the CFLSteensAAResult object. 144class CFLSteensAAWrapperPass : public ImmutablePass { 145 std::unique_ptr<CFLSteensAAResult> Result; 146 147public: 148 static char ID; 149 150 CFLSteensAAWrapperPass(); 151 152 CFLSteensAAResult &getResult() { return *Result; } 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// 164ImmutablePass *createCFLSteensAAWrapperPass(); 165} 166 167#endif 168