1 //- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ---*- 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 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.
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.
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
30 //===----------------------------------------------------------------------===//
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.
38 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
40 #include "StratifiedSets.h"
41 #include "llvm/ADT/DenseMap.h"
42 #include "llvm/ADT/None.h"
43 #include "llvm/ADT/Optional.h"
44 #include "llvm/Analysis/TargetLibraryInfo.h"
45 #include "llvm/IR/Constants.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/Pass.h"
48 #include "llvm/Support/Compiler.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/ErrorHandling.h"
51 #include "llvm/Support/raw_ostream.h"
58 using namespace llvm::cflaa;
60 #define DEBUG_TYPE "cfl-steens-aa"
62 CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
63 : AAResultBase(), TLI(TLI) {}
64 CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
65 : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
66 CFLSteensAAResult::~CFLSteensAAResult() {}
68 /// Information we have about a function and would like to keep around.
69 class CFLSteensAAResult::FunctionInfo {
70 StratifiedSets<InstantiatedValue> Sets;
74 FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
75 StratifiedSets<InstantiatedValue> S);
77 const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
80 const AliasSummary &getAliasSummary() const { return Summary; }
83 const StratifiedIndex StratifiedLink::SetSentinel =
84 std::numeric_limits<StratifiedIndex>::max();
86 //===----------------------------------------------------------------------===//
87 // Function declarations that require types defined in the namespace above
88 //===----------------------------------------------------------------------===//
90 /// Determines whether it would be pointless to add the given Value to our sets.
91 static bool canSkipAddingToSets(Value *Val) {
92 // Constants can share instances, which may falsely unify multiple
94 // store i32* null, i32** %ptr1
95 // store i32* null, i32** %ptr2
96 // clearly ptr1 and ptr2 should not be unified into the same set, so
97 // we should filter out the (potentially shared) instance to
99 if (isa<Constant>(Val)) {
100 // TODO: Because all of these things are constant, we can determine whether
101 // the data is *actually* mutable at graph building time. This will probably
102 // come for free/cheap with offset awareness.
103 bool CanStoreMutableData = isa<GlobalValue>(Val) ||
104 isa<ConstantExpr>(Val) ||
105 isa<ConstantAggregate>(Val);
106 return !CanStoreMutableData;
112 CFLSteensAAResult::FunctionInfo::FunctionInfo(
113 Function &Fn, const SmallVectorImpl<Value *> &RetVals,
114 StratifiedSets<InstantiatedValue> S)
115 : Sets(std::move(S)) {
116 // Historically, an arbitrary upper-bound of 50 args was selected. We may want
117 // to remove this if it doesn't really matter in practice.
118 if (Fn.arg_size() > MaxSupportedArgsInSummary)
121 DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
123 // Our intention here is to record all InterfaceValues that share the same
124 // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
125 // have its StratifiedIndex scanned here and check if the index is presented
126 // in InterfaceMap: if it is not, we add the correspondence to the map;
127 // otherwise, an aliasing relation is found and we add it to
128 // RetParamRelations.
130 auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
131 StratifiedIndex SetIndex) {
134 InterfaceValue CurrValue{InterfaceIndex, Level};
136 auto Itr = InterfaceMap.find(SetIndex);
137 if (Itr != InterfaceMap.end()) {
138 if (CurrValue != Itr->second)
139 Summary.RetParamRelations.push_back(
140 ExternalRelation{CurrValue, Itr->second, UnknownOffset});
144 auto &Link = Sets.getLink(SetIndex);
145 InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
146 auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
147 if (ExternalAttrs.any())
148 Summary.RetParamAttributes.push_back(
149 ExternalAttribute{CurrValue, ExternalAttrs});
151 if (!Link.hasBelow())
155 SetIndex = Link.Below;
159 // Populate RetParamRelations for return values
160 for (auto *RetVal : RetVals) {
161 assert(RetVal != nullptr);
162 assert(RetVal->getType()->isPointerTy());
163 auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
164 if (RetInfo.hasValue())
165 AddToRetParamRelations(0, RetInfo->Index);
168 // Populate RetParamRelations for parameters
170 for (auto &Param : Fn.args()) {
171 if (Param.getType()->isPointerTy()) {
172 auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
173 if (ParamInfo.hasValue())
174 AddToRetParamRelations(I + 1, ParamInfo->Index);
180 // Builds the graph + StratifiedSets for a function.
181 CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
182 CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
183 StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
185 // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
186 auto &Graph = GraphBuilder.getCFLGraph();
187 for (const auto &Mapping : Graph.value_mappings()) {
188 auto Val = Mapping.first;
189 if (canSkipAddingToSets(Val))
191 auto &ValueInfo = Mapping.second;
193 assert(ValueInfo.getNumLevels() > 0);
194 SetBuilder.add(InstantiatedValue{Val, 0});
195 SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
196 ValueInfo.getNodeInfoAtLevel(0).Attr);
197 for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
198 SetBuilder.add(InstantiatedValue{Val, I + 1});
199 SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
200 ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
201 SetBuilder.addBelow(InstantiatedValue{Val, I},
202 InstantiatedValue{Val, I + 1});
206 // Add all assign edges to StratifiedSets
207 for (const auto &Mapping : Graph.value_mappings()) {
208 auto Val = Mapping.first;
209 if (canSkipAddingToSets(Val))
211 auto &ValueInfo = Mapping.second;
213 for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
214 auto Src = InstantiatedValue{Val, I};
215 for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
216 SetBuilder.addWith(Src, Edge.Other);
220 return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
223 void CFLSteensAAResult::scan(Function *Fn) {
224 auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
226 assert(InsertPair.second &&
227 "Trying to scan a function that has already been cached");
229 // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
230 // may get evaluated after operator[], potentially triggering a DenseMap
231 // resize and invalidating the reference returned by operator[]
232 auto FunInfo = buildSetsFrom(Fn);
233 Cache[Fn] = std::move(FunInfo);
235 Handles.emplace_front(Fn, this);
238 void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
240 /// Ensures that the given function is available in the cache, and returns the
242 const Optional<CFLSteensAAResult::FunctionInfo> &
243 CFLSteensAAResult::ensureCached(Function *Fn) {
244 auto Iter = Cache.find(Fn);
245 if (Iter == Cache.end()) {
247 Iter = Cache.find(Fn);
248 assert(Iter != Cache.end());
249 assert(Iter->second.hasValue());
254 const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
255 auto &FunInfo = ensureCached(&Fn);
256 if (FunInfo.hasValue())
257 return &FunInfo->getAliasSummary();
262 AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
263 const MemoryLocation &LocB) {
264 auto *ValA = const_cast<Value *>(LocA.Ptr);
265 auto *ValB = const_cast<Value *>(LocB.Ptr);
267 if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
270 Function *Fn = nullptr;
271 Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
272 Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
273 if (!MaybeFnA && !MaybeFnB) {
274 // The only times this is known to happen are when globals + InlineAsm are
277 << "CFLSteensAA: could not extract parent function information.\n");
283 assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
284 "Interprocedural queries not supported");
289 assert(Fn != nullptr);
290 auto &MaybeInfo = ensureCached(Fn);
291 assert(MaybeInfo.hasValue());
293 auto &Sets = MaybeInfo->getStratifiedSets();
294 auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
295 if (!MaybeA.hasValue())
298 auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
299 if (!MaybeB.hasValue())
304 auto AttrsA = Sets.getLink(SetA.Index).Attrs;
305 auto AttrsB = Sets.getLink(SetB.Index).Attrs;
307 // If both values are local (meaning the corresponding set has attribute
308 // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
309 // they may-alias each other if and only if they are in the same set.
310 // If at least one value is non-local (meaning it either is global/argument or
311 // it comes from unknown sources like integer cast), the situation becomes a
312 // bit more interesting. We follow three general rules described below:
313 // - Non-local values may alias each other
314 // - AttrNone values do not alias any non-local values
315 // - AttrEscaped do not alias globals/arguments, but they may alias
316 // AttrUnknown values
317 if (SetA.Index == SetB.Index)
319 if (AttrsA.none() || AttrsB.none())
321 if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
323 if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
328 AnalysisKey CFLSteensAA::Key;
330 CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) {
331 return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));
334 char CFLSteensAAWrapperPass::ID = 0;
335 INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
336 "Unification-Based CFL Alias Analysis", false, true)
338 ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
339 return new CFLSteensAAWrapperPass();
342 CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
343 initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
346 void CFLSteensAAWrapperPass::initializePass() {
347 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
348 Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
351 void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
352 AU.setPreservesAll();
353 AU.addRequired<TargetLibraryInfoWrapperPass>();