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 26namespace llvm { 27 28class TargetLibraryInfo; 29 30namespace cflaa { 31struct AliasSummary; 32} 33 34class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> { 35 friend AAResultBase<CFLAndersAAResult>; 36 class FunctionInfo; 37 38public: 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 59private: 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. 107class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> { 108 friend AnalysisInfoMixin<CFLAndersAA>; 109 static AnalysisKey Key; 110 111public: 112 typedef CFLAndersAAResult Result; 113 114 CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM); 115}; 116 117/// Legacy wrapper pass to provide the CFLAndersAAResult object. 118class CFLAndersAAWrapperPass : public ImmutablePass { 119 std::unique_ptr<CFLAndersAAResult> Result; 120 121public: 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// 138ImmutablePass *createCFLAndersAAWrapperPass(); 139} 140 141#endif 142