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