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