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