LLVM  6.0.0svn
CFLSteensAliasAnalysis.h
Go to the documentation of this file.
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"
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 
29 namespace llvm {
30 
31 class Function;
32 class TargetLibraryInfo;
33 
34 namespace cflaa {
35 
36 struct AliasSummary;
37 
38 } // end namespace cflaa
39 
40 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
42 
43  class FunctionInfo;
44 
45 public:
46  explicit CFLSteensAAResult(const TargetLibraryInfo &TLI);
49 
50  /// Handle invalidation events from the new pass manager.
51  ///
52  /// By definition, this result is stateless and so remains valid.
55  return false;
56  }
57 
58  /// \brief Inserts the given Function into the cache.
59  void scan(Function *Fn);
60 
61  void evict(Function *Fn);
62 
63  /// \brief 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  /// \brief 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 
92 private:
93  const TargetLibraryInfo &TLI;
94 
95  /// \brief 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.
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.
110 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
112 
113  static AnalysisKey Key;
114 
115 public:
117 
119 };
120 
121 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
123  std::unique_ptr<CFLSteensAAResult> Result;
124 
125 public:
126  static char ID;
127 
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.
140 
141 } // end namespace llvm
142 
143 #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
The two locations precisely alias each other.
Definition: AliasAnalysis.h:91
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
Handle invalidation events from the new pass manager.
F(f)
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
Key
PAL metadata keys.
AliasSummary is just a collection of ExternalRelation and ExternalAttribute.
Legacy wrapper pass to provide the CFLSteensAAResult object.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
const CFLSteensAAResult & getResult() const
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
Analysis pass providing a never-invalidated alias analysis result.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
Provides information about what library functions are available for the current target.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
Information we have about a function and would like to keep around.
amdgpu Simplify well known AMD library false Value Value * Arg
This file provides utility analysis objects describing memory locations.
ImmutablePass * createCFLSteensAAWrapperPass()
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
static Expected< BitVector > scan(StringRef &S, StringRef Original)
Definition: GlobPattern.cpp:67