Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
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
38
#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
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"
45
#include "llvm/Analysis/TargetLibraryInfo.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"
52
#include "llvm/Support/raw_ostream.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
64
CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
65
76
    : AAResultBase(), TLI(TLI) {}
66
CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
67
84
    : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
68
160
CFLSteensAAResult::~CFLSteensAAResult() = default;
69
70
/// Information we have about a function and would like to keep around.
71
class CFLSteensAAResult::FunctionInfo {
72
  StratifiedSets<InstantiatedValue> Sets;
73
  AliasSummary Summary;
74
75
public:
76
  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
77
               StratifiedSets<InstantiatedValue> S);
78
79
2.78k
  const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
80
2.78k
    return Sets;
81
2.78k
  }
82
83
64
  const AliasSummary &getAliasSummary() const { return Summary; }
84
};
85
86
const StratifiedIndex StratifiedLink::SetSentinel =
87
    std::numeric_limits<StratifiedIndex>::max();
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
922
static bool canSkipAddingToSets(Value *Val) {
95
922
  // Constants can share instances, which may falsely unify multiple
96
922
  // sets, e.g. in
97
922
  // store i32* null, i32** %ptr1
98
922
  // store i32* null, i32** %ptr2
99
922
  // clearly ptr1 and ptr2 should not be unified into the same set, so
100
922
  // we should filter out the (potentially shared) instance to
101
922
  // i32* null.
102
922
  if (
isa<Constant>(Val)922
) {
103
42
    // TODO: Because all of these things are constant, we can determine whether
104
42
    // the data is *actually* mutable at graph building time. This will probably
105
42
    // come for free/cheap with offset awareness.
106
42
    bool CanStoreMutableData = isa<GlobalValue>(Val) ||
107
10
                               isa<ConstantExpr>(Val) ||
108
0
                               isa<ConstantAggregate>(Val);
109
42
    return !CanStoreMutableData;
110
42
  }
111
880
112
880
  return false;
113
880
}
114
115
CFLSteensAAResult::FunctionInfo::FunctionInfo(
116
    Function &Fn, const SmallVectorImpl<Value *> &RetVals,
117
    StratifiedSets<InstantiatedValue> S)
118
115
    : Sets(std::move(S)) {
119
115
  // Historically, an arbitrary upper-bound of 50 args was selected. We may want
120
115
  // to remove this if it doesn't really matter in practice.
121
115
  if (Fn.arg_size() > MaxSupportedArgsInSummary)
122
0
    return;
123
115
124
115
  DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
125
115
126
115
  // Our intention here is to record all InterfaceValues that share the same
127
115
  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
128
115
  // have its StratifiedIndex scanned here and check if the index is presented
129
115
  // in InterfaceMap: if it is not, we add the correspondence to the map;
130
115
  // otherwise, an aliasing relation is found and we add it to
131
115
  // RetParamRelations.
132
115
133
115
  auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
134
164
                                    StratifiedIndex SetIndex) {
135
164
    unsigned Level = 0;
136
321
    while (
true321
) {
137
321
      InterfaceValue CurrValue{InterfaceIndex, Level};
138
321
139
321
      auto Itr = InterfaceMap.find(SetIndex);
140
321
      if (
Itr != InterfaceMap.end()321
) {
141
33
        if (CurrValue != Itr->second)
142
33
          Summary.RetParamRelations.push_back(
143
33
              ExternalRelation{CurrValue, Itr->second, UnknownOffset});
144
33
        break;
145
33
      }
146
288
147
288
      auto &Link = Sets.getLink(SetIndex);
148
288
      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
149
288
      auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
150
288
      if (ExternalAttrs.any())
151
35
        Summary.RetParamAttributes.push_back(
152
35
            ExternalAttribute{CurrValue, ExternalAttrs});
153
288
154
288
      if (!Link.hasBelow())
155
131
        break;
156
157
157
157
      ++Level;
158
157
      SetIndex = Link.Below;
159
157
    }
160
164
  };
161
115
162
115
  // Populate RetParamRelations for return values
163
24
  for (auto *RetVal : RetVals) {
164
24
    assert(RetVal != nullptr);
165
24
    assert(RetVal->getType()->isPointerTy());
166
24
    auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
167
24
    if (RetInfo.hasValue())
168
24
      AddToRetParamRelations(0, RetInfo->Index);
169
24
  }
170
115
171
115
  // Populate RetParamRelations for parameters
172
115
  unsigned I = 0;
173
152
  for (auto &Param : Fn.args()) {
174
152
    if (
Param.getType()->isPointerTy()152
) {
175
140
      auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
176
140
      if (ParamInfo.hasValue())
177
140
        AddToRetParamRelations(I + 1, ParamInfo->Index);
178
140
    }
179
152
    ++I;
180
152
  }
181
115
}
182
183
// Builds the graph + StratifiedSets for a function.
184
115
CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
185
115
  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
186
115
  StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
187
115
188
115
  // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
189
115
  auto &Graph = GraphBuilder.getCFLGraph();
190
461
  for (const auto &Mapping : Graph.value_mappings()) {
191
461
    auto Val = Mapping.first;
192
461
    if (canSkipAddingToSets(Val))
193
0
      continue;
194
461
    auto &ValueInfo = Mapping.second;
195
461
196
461
    assert(ValueInfo.getNumLevels() > 0);
197
461
    SetBuilder.add(InstantiatedValue{Val, 0});
198
461
    SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
199
461
                              ValueInfo.getNodeInfoAtLevel(0).Attr);
200
716
    for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; 
I < E716
;
++I255
) {
201
255
      SetBuilder.add(InstantiatedValue{Val, I + 1});
202
255
      SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
203
255
                                ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
204
255
      SetBuilder.addBelow(InstantiatedValue{Val, I},
205
255
                          InstantiatedValue{Val, I + 1});
206
255
    }
207
461
  }
208
115
209
115
  // Add all assign edges to StratifiedSets
210
461
  for (const auto &Mapping : Graph.value_mappings()) {
211
461
    auto Val = Mapping.first;
212
461
    if (canSkipAddingToSets(Val))
213
0
      continue;
214
461
    auto &ValueInfo = Mapping.second;
215
461
216
1.17k
    for (unsigned I = 0, E = ValueInfo.getNumLevels(); 
I < E1.17k
;
++I716
) {
217
716
      auto Src = InstantiatedValue{Val, I};
218
716
      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
219
215
        SetBuilder.addWith(Src, Edge.Other);
220
716
    }
221
461
  }
222
115
223
115
  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
224
115
}
225
226
115
void CFLSteensAAResult::scan(Function *Fn) {
227
115
  auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
228
115
  (void)InsertPair;
229
115
  assert(InsertPair.second &&
230
115
         "Trying to scan a function that has already been cached");
231
115
232
115
  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
233
115
  // may get evaluated after operator[], potentially triggering a DenseMap
234
115
  // resize and invalidating the reference returned by operator[]
235
115
  auto FunInfo = buildSetsFrom(Fn);
236
115
  Cache[Fn] = std::move(FunInfo);
237
115
238
115
  Handles.emplace_front(Fn, this);
239
115
}
240
241
0
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.
245
const Optional<CFLSteensAAResult::FunctionInfo> &
246
2.85k
CFLSteensAAResult::ensureCached(Function *Fn) {
247
2.85k
  auto Iter = Cache.find(Fn);
248
2.85k
  if (
Iter == Cache.end()2.85k
) {
249
115
    scan(Fn);
250
115
    Iter = Cache.find(Fn);
251
115
    assert(Iter != Cache.end());
252
115
    assert(Iter->second.hasValue());
253
115
  }
254
2.85k
  return Iter->second;
255
2.85k
}
256
257
64
const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
258
64
  auto &FunInfo = ensureCached(&Fn);
259
64
  if (FunInfo.hasValue())
260
64
    return &FunInfo->getAliasSummary();
261
64
  else
262
0
    return nullptr;
263
0
}
264
265
AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
266
2.79k
                                     const MemoryLocation &LocB) {
267
2.79k
  auto *ValA = const_cast<Value *>(LocA.Ptr);
268
2.79k
  auto *ValB = const_cast<Value *>(LocB.Ptr);
269
2.79k
270
2.79k
  if (
!ValA->getType()->isPointerTy() || 2.79k
!ValB->getType()->isPointerTy()2.79k
)
271
0
    return NoAlias;
272
2.79k
273
2.79k
  Function *Fn = nullptr;
274
2.79k
  Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
275
2.79k
  Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
276
2.79k
  if (
!MaybeFnA && 2.79k
!MaybeFnB41
) {
277
2
    // The only times this is known to happen are when globals + InlineAsm are
278
2
    // involved
279
2
    DEBUG(dbgs()
280
2
          << "CFLSteensAA: could not extract parent function information.\n");
281
2
    return MayAlias;
282
2
  }
283
2.78k
284
2.78k
  
if (2.78k
MaybeFnA2.78k
) {
285
2.74k
    Fn = MaybeFnA;
286
2.74k
    assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
287
2.74k
           "Interprocedural queries not supported");
288
2.78k
  } else {
289
39
    Fn = MaybeFnB;
290
39
  }
291
2.78k
292
2.78k
  assert(Fn != nullptr);
293
2.78k
  auto &MaybeInfo = ensureCached(Fn);
294
2.78k
  assert(MaybeInfo.hasValue());
295
2.78k
296
2.78k
  auto &Sets = MaybeInfo->getStratifiedSets();
297
2.78k
  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
298
2.78k
  if (!MaybeA.hasValue())
299
5
    return MayAlias;
300
2.78k
301
2.78k
  auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
302
2.78k
  if (!MaybeB.hasValue())
303
1
    return MayAlias;
304
2.78k
305
2.78k
  auto SetA = *MaybeA;
306
2.78k
  auto SetB = *MaybeB;
307
2.78k
  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
308
2.78k
  auto AttrsB = Sets.getLink(SetB.Index).Attrs;
309
2.78k
310
2.78k
  // If both values are local (meaning the corresponding set has attribute
311
2.78k
  // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
312
2.78k
  // they may-alias each other if and only if they are in the same set.
313
2.78k
  // If at least one value is non-local (meaning it either is global/argument or
314
2.78k
  // it comes from unknown sources like integer cast), the situation becomes a
315
2.78k
  // bit more interesting. We follow three general rules described below:
316
2.78k
  // - Non-local values may alias each other
317
2.78k
  // - AttrNone values do not alias any non-local values
318
2.78k
  // - AttrEscaped do not alias globals/arguments, but they may alias
319
2.78k
  // AttrUnknown values
320
2.78k
  if (SetA.Index == SetB.Index)
321
543
    return MayAlias;
322
2.23k
  
if (2.23k
AttrsA.none() || 2.23k
AttrsB.none()1.95k
)
323
332
    return NoAlias;
324
1.90k
  
if (1.90k
hasUnknownOrCallerAttr(AttrsA) || 1.90k
hasUnknownOrCallerAttr(AttrsB)1.18k
)
325
1.17k
    return MayAlias;
326
731
  
if (731
isGlobalOrArgAttr(AttrsA) && 731
isGlobalOrArgAttr(AttrsB)700
)
327
698
    return MayAlias;
328
33
  return NoAlias;
329
33
}
330
331
AnalysisKey CFLSteensAA::Key;
332
333
42
CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) {
334
42
  return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));
335
42
}
336
337
char CFLSteensAAWrapperPass::ID = 0;
338
INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
339
                "Unification-Based CFL Alias Analysis", false, true)
340
341
0
ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
342
0
  return new CFLSteensAAWrapperPass();
343
0
}
344
345
34
CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
346
34
  initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
347
34
}
348
349
34
void CFLSteensAAWrapperPass::initializePass() {
350
34
  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
351
34
  Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
352
34
}
353
354
34
void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
355
34
  AU.setPreservesAll();
356
34
  AU.addRequired<TargetLibraryInfoWrapperPass>();
357
34
}