LLVM  6.0.0svn
CFLSteensAliasAnalysis.cpp
Go to the documentation of this file.
1 //===- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
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 //
10 // This file implements a CFL-base, summary-based alias analysis algorithm. It
11 // does not depend on types. The algorithm is a mixture of the one described in
12 // "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast
13 // algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by
14 // Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a
15 // graph of the uses of a variable, where each node is a memory location, and
16 // each edge is an action that happened on that memory location. The "actions"
17 // can be one of Dereference, Reference, or Assign. The precision of this
18 // analysis is roughly the same as that of an one level context-sensitive
19 // Steensgaard's algorithm.
20 //
21 // Two variables are considered as aliasing iff you can reach one value's node
22 // from the other value's node and the language formed by concatenating all of
23 // the edge labels (actions) conforms to a context-free grammar.
24 //
25 // Because this algorithm requires a graph search on each query, we execute the
26 // algorithm outlined in "Fast algorithms..." (mentioned above)
27 // in order to transform the graph into sets of variables that may alias in
28 // ~nlogn time (n = number of variables), which makes queries take constant
29 // time.
30 //===----------------------------------------------------------------------===//
31 
32 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
33 // CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
34 // FunctionPasses are only allowed to inspect the Function that they're being
35 // run on. Realistically, this likely isn't a problem until we allow
36 // FunctionPasses to run concurrently.
37 
39 #include "AliasAnalysisSummary.h"
40 #include "CFLGraph.h"
41 #include "StratifiedSets.h"
42 #include "llvm/ADT/DenseMap.h"
43 #include "llvm/ADT/Optional.h"
44 #include "llvm/ADT/SmallVector.h"
46 #include "llvm/IR/Constants.h"
47 #include "llvm/IR/Function.h"
48 #include "llvm/IR/Type.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Debug.h"
53 #include <algorithm>
54 #include <cassert>
55 #include <limits>
56 #include <memory>
57 #include <utility>
58 
59 using namespace llvm;
60 using namespace llvm::cflaa;
61 
62 #define DEBUG_TYPE "cfl-steens-aa"
63 
65  : AAResultBase(), TLI(TLI) {}
67  : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
69 
70 /// Information we have about a function and would like to keep around.
73  AliasSummary Summary;
74 
75 public:
78 
80  return Sets;
81  }
82 
83  const AliasSummary &getAliasSummary() const { return Summary; }
84 };
85 
86 const StratifiedIndex StratifiedLink::SetSentinel =
88 
89 //===----------------------------------------------------------------------===//
90 // Function declarations that require types defined in the namespace above
91 //===----------------------------------------------------------------------===//
92 
93 /// Determines whether it would be pointless to add the given Value to our sets.
94 static bool canSkipAddingToSets(Value *Val) {
95  // Constants can share instances, which may falsely unify multiple
96  // sets, e.g. in
97  // store i32* null, i32** %ptr1
98  // store i32* null, i32** %ptr2
99  // clearly ptr1 and ptr2 should not be unified into the same set, so
100  // we should filter out the (potentially shared) instance to
101  // i32* null.
102  if (isa<Constant>(Val)) {
103  // TODO: Because all of these things are constant, we can determine whether
104  // the data is *actually* mutable at graph building time. This will probably
105  // come for free/cheap with offset awareness.
106  bool CanStoreMutableData = isa<GlobalValue>(Val) ||
107  isa<ConstantExpr>(Val) ||
108  isa<ConstantAggregate>(Val);
109  return !CanStoreMutableData;
110  }
111 
112  return false;
113 }
114 
116  Function &Fn, const SmallVectorImpl<Value *> &RetVals,
118  : Sets(std::move(S)) {
119  // Historically, an arbitrary upper-bound of 50 args was selected. We may want
120  // to remove this if it doesn't really matter in practice.
122  return;
123 
125 
126  // Our intention here is to record all InterfaceValues that share the same
127  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
128  // have its StratifiedIndex scanned here and check if the index is presented
129  // in InterfaceMap: if it is not, we add the correspondence to the map;
130  // otherwise, an aliasing relation is found and we add it to
131  // RetParamRelations.
132 
133  auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
134  StratifiedIndex SetIndex) {
135  unsigned Level = 0;
136  while (true) {
137  InterfaceValue CurrValue{InterfaceIndex, Level};
138 
139  auto Itr = InterfaceMap.find(SetIndex);
140  if (Itr != InterfaceMap.end()) {
141  if (CurrValue != Itr->second)
142  Summary.RetParamRelations.push_back(
143  ExternalRelation{CurrValue, Itr->second, UnknownOffset});
144  break;
145  }
146 
147  auto &Link = Sets.getLink(SetIndex);
148  InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
149  auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
150  if (ExternalAttrs.any())
151  Summary.RetParamAttributes.push_back(
152  ExternalAttribute{CurrValue, ExternalAttrs});
153 
154  if (!Link.hasBelow())
155  break;
156 
157  ++Level;
158  SetIndex = Link.Below;
159  }
160  };
161 
162  // Populate RetParamRelations for return values
163  for (auto *RetVal : RetVals) {
164  assert(RetVal != nullptr);
165  assert(RetVal->getType()->isPointerTy());
166  auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
167  if (RetInfo.hasValue())
168  AddToRetParamRelations(0, RetInfo->Index);
169  }
170 
171  // Populate RetParamRelations for parameters
172  unsigned I = 0;
173  for (auto &Param : Fn.args()) {
174  if (Param.getType()->isPointerTy()) {
175  auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
176  if (ParamInfo.hasValue())
177  AddToRetParamRelations(I + 1, ParamInfo->Index);
178  }
179  ++I;
180  }
181 }
182 
183 // Builds the graph + StratifiedSets for a function.
184 CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
185  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
187 
188  // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
189  auto &Graph = GraphBuilder.getCFLGraph();
190  for (const auto &Mapping : Graph.value_mappings()) {
191  auto Val = Mapping.first;
192  if (canSkipAddingToSets(Val))
193  continue;
194  auto &ValueInfo = Mapping.second;
195 
196  assert(ValueInfo.getNumLevels() > 0);
197  SetBuilder.add(InstantiatedValue{Val, 0});
198  SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
199  ValueInfo.getNodeInfoAtLevel(0).Attr);
200  for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
201  SetBuilder.add(InstantiatedValue{Val, I + 1});
202  SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
203  ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
204  SetBuilder.addBelow(InstantiatedValue{Val, I},
205  InstantiatedValue{Val, I + 1});
206  }
207  }
208 
209  // Add all assign edges to StratifiedSets
210  for (const auto &Mapping : Graph.value_mappings()) {
211  auto Val = Mapping.first;
212  if (canSkipAddingToSets(Val))
213  continue;
214  auto &ValueInfo = Mapping.second;
215 
216  for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
217  auto Src = InstantiatedValue{Val, I};
218  for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
219  SetBuilder.addWith(Src, Edge.Other);
220  }
221  }
222 
223  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
224 }
225 
227  auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
228  (void)InsertPair;
229  assert(InsertPair.second &&
230  "Trying to scan a function that has already been cached");
231 
232  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
233  // may get evaluated after operator[], potentially triggering a DenseMap
234  // resize and invalidating the reference returned by operator[]
235  auto FunInfo = buildSetsFrom(Fn);
236  Cache[Fn] = std::move(FunInfo);
237 
238  Handles.emplace_front(Fn, this);
239 }
240 
241 void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
242 
243 /// Ensures that the given function is available in the cache, and returns the
244 /// entry.
246 CFLSteensAAResult::ensureCached(Function *Fn) {
247  auto Iter = Cache.find(Fn);
248  if (Iter == Cache.end()) {
249  scan(Fn);
250  Iter = Cache.find(Fn);
251  assert(Iter != Cache.end());
252  assert(Iter->second.hasValue());
253  }
254  return Iter->second;
255 }
256 
257 const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
258  auto &FunInfo = ensureCached(&Fn);
259  if (FunInfo.hasValue())
260  return &FunInfo->getAliasSummary();
261  else
262  return nullptr;
263 }
264 
265 AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
266  const MemoryLocation &LocB) {
267  auto *ValA = const_cast<Value *>(LocA.Ptr);
268  auto *ValB = const_cast<Value *>(LocB.Ptr);
269 
270  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
271  return NoAlias;
272 
273  Function *Fn = nullptr;
274  Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
275  Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
276  if (!MaybeFnA && !MaybeFnB) {
277  // The only times this is known to happen are when globals + InlineAsm are
278  // involved
279  DEBUG(dbgs()
280  << "CFLSteensAA: could not extract parent function information.\n");
281  return MayAlias;
282  }
283 
284  if (MaybeFnA) {
285  Fn = MaybeFnA;
286  assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
287  "Interprocedural queries not supported");
288  } else {
289  Fn = MaybeFnB;
290  }
291 
292  assert(Fn != nullptr);
293  auto &MaybeInfo = ensureCached(Fn);
294  assert(MaybeInfo.hasValue());
295 
296  auto &Sets = MaybeInfo->getStratifiedSets();
297  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
298  if (!MaybeA.hasValue())
299  return MayAlias;
300 
301  auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
302  if (!MaybeB.hasValue())
303  return MayAlias;
304 
305  auto SetA = *MaybeA;
306  auto SetB = *MaybeB;
307  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
308  auto AttrsB = Sets.getLink(SetB.Index).Attrs;
309 
310  // If both values are local (meaning the corresponding set has attribute
311  // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
312  // they may-alias each other if and only if they are in the same set.
313  // If at least one value is non-local (meaning it either is global/argument or
314  // it comes from unknown sources like integer cast), the situation becomes a
315  // bit more interesting. We follow three general rules described below:
316  // - Non-local values may alias each other
317  // - AttrNone values do not alias any non-local values
318  // - AttrEscaped do not alias globals/arguments, but they may alias
319  // AttrUnknown values
320  if (SetA.Index == SetB.Index)
321  return MayAlias;
322  if (AttrsA.none() || AttrsB.none())
323  return NoAlias;
324  if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
325  return MayAlias;
326  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
327  return MayAlias;
328  return NoAlias;
329 }
330 
332 
335 }
336 
339  "Unification-Based CFL Alias Analysis", false, true)
340 
342  return new CFLSteensAAWrapperPass();
343 }
344 
345 CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
347 }
348 
350  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
351  Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
352 }
353 
355  AU.setPreservesAll();
357 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
StratifiedSets< T > build()
Builds a StratifiedSet from the information we&#39;ve been given since either construction or the prior b...
This is the result of instantiating InterfaceValue at a particular callsite.
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value...
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
AnalysisUsage & addRequired()
Definition: BitVector.h:920
bool addWith(const T &Main, const T &ToAdd)
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
Key
PAL metadata keys.
Legacy wrapper pass to provide the CFLSteensAAResult object.
This is the interface for LLVM&#39;s unification-based alias analysis implemented with CFL graph reachabi...
const StratifiedLink & getLink(StratifiedIndex Index) const
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
Represent the analysis usage information of a pass.
size_t arg_size() const
Definition: Function.h:630
INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa", "Unification-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
const AliasSummary & getAliasSummary() const
const SmallVector< Value *, 4 > & getReturnValues() const
Definition: CFLGraph.h:663
bool isGlobalOrArgAttr(AliasAttrs Attr)
Struct that holds a reference to a particular GUID in a global value summary.
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
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
Definition: CFLGraph.h:165
Provides information about what library functions are available for the current target.
static bool canSkipAddingToSets(Value *Val)
Determines whether it would be pointless to add the given Value to our sets.
bool addBelow(const T &Main, const T &ToAdd)
Restructures the stratified sets as necessary to make "ToAdd" in a set below "Main".
Alias summary information.
This file defines various utility types and functions useful to summary-based alias analysis...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Information we have about a function and would like to keep around.
void setPreservesAll()
Set by analyses that do not transform their input at all.
This file defines CFLGraph, an auxiliary data structure used by CFL-based alias analysis.
amdgpu Simplify well known AMD library false Value Value * Arg
FunctionInfo(Function &Fn, const SmallVectorImpl< Value *> &RetVals, StratifiedSets< InstantiatedValue > S)
CFLSteensAAResult(const TargetLibraryInfo &TLI)
static const int64_t UnknownOffset
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ImmutablePass * createCFLSteensAAWrapperPass()
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void initializeCFLSteensAAWrapperPassPass(PassRegistry &)
static const Function * parentFunctionOfValue(const Value *Val)
Generic Builder class that produces StratifiedSets instances.
LLVM Value Representation.
Definition: Value.h:73
const CFLGraph & getCFLGraph() const
Definition: CFLGraph.h:662
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
#define DEBUG(X)
Definition: Debug.h:118
A container for analyses that lazily runs them and caches their results.
const StratifiedSets< InstantiatedValue > & getStratifiedSets() const
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
void noteAttributes(const T &Main, AliasAttrs NewAttrs)
iterator_range< arg_iterator > args()
Definition: Function.h:621
Optional< StratifiedInfo > find(const T &Elem) const