1 //===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This is the interface for LLVM's primary stateless and local alias analysis.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H
15 #define LLVM_ANALYSIS_CFLALIASANALYSIS_H
17 #include "llvm/Analysis/AliasAnalysis.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Pass.h"
25 #include <forward_list>
29 class CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
32 struct FunctionHandle final : public CallbackVH {
33 FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA)
34 : CallbackVH(Fn), CFLAA(CFLAA) {
35 assert(Fn != nullptr);
36 assert(CFLAA != nullptr);
39 void deleted() override { removeSelfFromCache(); }
40 void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
43 CFLAliasAnalysis *CFLAA;
45 void removeSelfFromCache() {
46 assert(CFLAA != nullptr);
47 auto *Val = getValPtr();
48 CFLAA->evict(cast<Function>(Val));
53 /// \brief Cached mapping of Functions to their StratifiedSets.
54 /// If a function's sets are currently being built, it is marked
55 /// in the cache as an Optional without a value. This way, if we
56 /// have any kind of recursion, it is discernable from a function
57 /// that simply has empty sets.
58 DenseMap<Function *, Optional<FunctionInfo>> Cache;
59 std::forward_list<FunctionHandle> Handles;
65 ~CFLAliasAnalysis() override;
67 void getAnalysisUsage(AnalysisUsage &AU) const override;
69 void *getAdjustedAnalysisPointer(const void *ID) override;
71 /// \brief Inserts the given Function into the cache.
72 void scan(Function *Fn);
74 void evict(Function *Fn);
76 /// \brief Ensures that the given function is available in the cache.
77 /// Returns the appropriate entry from the cache.
78 const Optional<FunctionInfo> &ensureCached(Function *Fn);
80 AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
82 AliasResult alias(const MemoryLocation &LocA,
83 const MemoryLocation &LocB) override {
84 if (LocA.Ptr == LocB.Ptr) {
85 if (LocA.Size == LocB.Size) {
92 // Comparisons between global variables and other constants should be
93 // handled by BasicAA.
94 // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing
95 // a GlobalValue and ConstantExpr, but every query needs to have at least
96 // one Value tied to a Function, and neither GlobalValues nor ConstantExprs
98 if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
99 return AliasAnalysis::alias(LocA, LocB);
102 AliasResult QueryResult = query(LocA, LocB);
103 if (QueryResult == MayAlias)
104 return AliasAnalysis::alias(LocA, LocB);
109 bool doInitialization(Module &M) override;
112 FunctionInfo buildSetsFrom(Function *F);
115 //===--------------------------------------------------------------------===//
117 // createCFLAliasAnalysisPass - This pass implements a set-based approach to
120 ImmutablePass *createCFLAliasAnalysisPass();