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/Optional.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Analysis/CFLAliasAnalysisUtils.h"
22#include "llvm/Analysis/MemoryLocation.h"
23#include "llvm/IR/PassManager.h"
24#include "llvm/Pass.h"
25#include "llvm/Support/Casting.h"
26#include <forward_list>
27#include <memory>
28
29namespace llvm {
30
31class Function;
32class TargetLibraryInfo;
33
34namespace cflaa {
35
36struct AliasSummary;
37
38} // end namespace cflaa
39
40class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
41 friend AAResultBase<CFLSteensAAResult>;
42
43 class FunctionInfo;
44
45public:
46 explicit CFLSteensAAResult(const TargetLibraryInfo &TLI);
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.
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
73 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
74 if (LocA.Ptr == LocB.Ptr)
75 return MustAlias;
76
77 // Comparisons between global variables and other constants should be
78 // handled by BasicAA.
79 // CFLSteensAA may report NoAlias when comparing a GlobalValue and
80 // ConstantExpr, but every query needs to have at least one Value tied to a
81 // Function, and neither GlobalValues nor ConstantExprs are.
82 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
83 return AAResultBase::alias(LocA, LocB);
84
85 AliasResult QueryResult = query(LocA, LocB);
86 if (QueryResult == MayAlias)
87 return AAResultBase::alias(LocA, LocB);
88
89 return QueryResult;
90 }
91
92private:
93 const TargetLibraryInfo &TLI;
94
95 /// Cached mapping of Functions to their StratifiedSets.
96 /// If a function's sets are currently being built, it is marked
97 /// in the cache as an Optional without a value. This way, if we
98 /// have any kind of recursion, it is discernable from a function
99 /// that simply has empty sets.
100 DenseMap<Function *, Optional<FunctionInfo>> Cache;
101 std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
102
103 FunctionInfo buildSetsFrom(Function *F);
104};
105
106/// Analysis pass providing a never-invalidated alias analysis result.
107///
108/// FIXME: We really should refactor CFL to use the analysis more heavily, and
109/// in particular to leverage invalidation to trigger re-computation of sets.
110class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
111 friend AnalysisInfoMixin<CFLSteensAA>;
112
113 static AnalysisKey Key;
114
115public:
116 using Result = CFLSteensAAResult;
117
118 CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
119};
120
121/// Legacy wrapper pass to provide the CFLSteensAAResult object.
122class CFLSteensAAWrapperPass : public ImmutablePass {
123 std::unique_ptr<CFLSteensAAResult> Result;
124
125public:
126 static char ID;
127
128 CFLSteensAAWrapperPass();
129
130 CFLSteensAAResult &getResult() { return *Result; }
131 const CFLSteensAAResult &getResult() const { return *Result; }
132
133 void initializePass() override;
134 void getAnalysisUsage(AnalysisUsage &AU) const override;
135};
136
137// createCFLSteensAAWrapperPass - This pass implements a set-based approach to
138// alias analysis.
139ImmutablePass *createCFLSteensAAWrapperPass();
140
141} // end namespace llvm
142
143#endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
144