LLVM  9.0.0svn
CFLSteensAliasAnalysis.h
Go to the documentation of this file.
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"
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> {
41 
42  class FunctionInfo;
43 
44 public:
45  explicit CFLSteensAAResult(const TargetLibraryInfo &TLI);
48 
49  /// Handle invalidation events from the new pass manager.
50  ///
51  /// By definition, this result is stateless and so remains valid.
54  return false;
55  }
56 
57  /// Inserts the given Function into the cache.
58  void scan(Function *Fn);
59 
60  void evict(Function *Fn);
61 
62  /// Ensures that the given function is available in the cache.
63  /// Returns the appropriate entry from the cache.
64  const Optional<FunctionInfo> &ensureCached(Function *Fn);
65 
66  /// Get the alias summary for the given function
67  /// Return nullptr if the summary is not found or not available
68  const cflaa::AliasSummary *getAliasSummary(Function &Fn);
69 
70  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
71 
72  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
73  if (LocA.Ptr == LocB.Ptr)
74  return MustAlias;
75 
76  // Comparisons between global variables and other constants should be
77  // handled by BasicAA.
78  // CFLSteensAA may report NoAlias when comparing a GlobalValue and
79  // ConstantExpr, but every query needs to have at least one Value tied to a
80  // Function, and neither GlobalValues nor ConstantExprs are.
81  if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
82  return AAResultBase::alias(LocA, LocB);
83 
84  AliasResult QueryResult = query(LocA, LocB);
85  if (QueryResult == MayAlias)
86  return AAResultBase::alias(LocA, LocB);
87 
88  return QueryResult;
89  }
90 
91 private:
92  const TargetLibraryInfo &TLI;
93 
94  /// Cached mapping of Functions to their StratifiedSets.
95  /// If a function's sets are currently being built, it is marked
96  /// in the cache as an Optional without a value. This way, if we
97  /// have any kind of recursion, it is discernable from a function
98  /// that simply has empty sets.
100  std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
101 
102  FunctionInfo buildSetsFrom(Function *F);
103 };
104 
105 /// Analysis pass providing a never-invalidated alias analysis result.
106 ///
107 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
108 /// in particular to leverage invalidation to trigger re-computation of sets.
109 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
111 
112  static AnalysisKey Key;
113 
114 public:
116 
118 };
119 
120 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
122  std::unique_ptr<CFLSteensAAResult> Result;
123 
124 public:
125  static char ID;
126 
128 
129  CFLSteensAAResult &getResult() { return *Result; }
130  const CFLSteensAAResult &getResult() const { return *Result; }
131 
132  void initializePass() override;
133  void getAnalysisUsage(AnalysisUsage &AU) const override;
134 };
135 
136 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
137 // alias analysis.
139 
140 } // end namespace llvm
141 
142 #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool invalidate(Function &, const PreservedAnalyses &, FunctionAnalysisManager::Invalidator &)
Handle invalidation events from the new pass manager.
F(f)
static void query(const MachineInstr &MI, AliasAnalysis &AA, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
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)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:77
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
Represent the analysis usage information of a pass.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:85
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:89
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:255
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.
This file provides utility analysis objects describing memory locations.
ImmutablePass * createCFLSteensAAWrapperPass()
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
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:66