Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CFLSteensAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
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
//
9
// This file implements a CFL-base, summary-based alias analysis algorithm. It
10
// does not depend on types. The algorithm is a mixture of the one described in
11
// "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast
12
// algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by
13
// Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a
14
// graph of the uses of a variable, where each node is a memory location, and
15
// each edge is an action that happened on that memory location.  The "actions"
16
// can be one of Dereference, Reference, or Assign. The precision of this
17
// analysis is roughly the same as that of an one level context-sensitive
18
// Steensgaard's algorithm.
19
//
20
// Two variables are considered as aliasing iff you can reach one value's node
21
// from the other value's node and the language formed by concatenating all of
22
// the edge labels (actions) conforms to a context-free grammar.
23
//
24
// Because this algorithm requires a graph search on each query, we execute the
25
// algorithm outlined in "Fast algorithms..." (mentioned above)
26
// in order to transform the graph into sets of variables that may alias in
27
// ~nlogn time (n = number of variables), which makes queries take constant
28
// time.
29
//===----------------------------------------------------------------------===//
30
31
// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
32
// CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
33
// FunctionPasses are only allowed to inspect the Function that they're being
34
// run on. Realistically, this likely isn't a problem until we allow
35
// FunctionPasses to run concurrently.
36
37
#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
38
#include "AliasAnalysisSummary.h"
39
#include "CFLGraph.h"
40
#include "StratifiedSets.h"
41
#include "llvm/ADT/DenseMap.h"
42
#include "llvm/ADT/Optional.h"
43
#include "llvm/ADT/SmallVector.h"
44
#include "llvm/Analysis/TargetLibraryInfo.h"
45
#include "llvm/IR/Constants.h"
46
#include "llvm/IR/Function.h"
47
#include "llvm/IR/Type.h"
48
#include "llvm/IR/Value.h"
49
#include "llvm/Pass.h"
50
#include "llvm/Support/Debug.h"
51
#include "llvm/Support/raw_ostream.h"
52
#include <algorithm>
53
#include <cassert>
54
#include <limits>
55
#include <memory>
56
#include <utility>
57
58
using namespace llvm;
59
using namespace llvm::cflaa;
60
61
#define DEBUG_TYPE "cfl-steens-aa"
62
63
CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
64
77
    : AAResultBase(), TLI(TLI) {}
65
CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
66
84
    : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
67
161
CFLSteensAAResult::~CFLSteensAAResult() = default;
68
69
/// Information we have about a function and would like to keep around.
70
class CFLSteensAAResult::FunctionInfo {
71
  StratifiedSets<InstantiatedValue> Sets;
72
  AliasSummary Summary;
73
74
public:
75
  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
76
               StratifiedSets<InstantiatedValue> S);
77
78
2.79k
  const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
79
2.79k
    return Sets;
80
2.79k
  }
81
82
64
  const AliasSummary &getAliasSummary() const { return Summary; }
83
};
84
85
const StratifiedIndex StratifiedLink::SetSentinel =
86
    std::numeric_limits<StratifiedIndex>::max();
87
88
//===----------------------------------------------------------------------===//
89
// Function declarations that require types defined in the namespace above
90
//===----------------------------------------------------------------------===//
91
92
/// Determines whether it would be pointless to add the given Value to our sets.
93
932
static bool canSkipAddingToSets(Value *Val) {
94
932
  // Constants can share instances, which may falsely unify multiple
95
932
  // sets, e.g. in
96
932
  // store i32* null, i32** %ptr1
97
932
  // store i32* null, i32** %ptr2
98
932
  // clearly ptr1 and ptr2 should not be unified into the same set, so
99
932
  // we should filter out the (potentially shared) instance to
100
932
  // i32* null.
101
932
  if (isa<Constant>(Val)) {
102
48
    // TODO: Because all of these things are constant, we can determine whether
103
48
    // the data is *actually* mutable at graph building time. This will probably
104
48
    // come for free/cheap with offset awareness.
105
48
    bool CanStoreMutableData = isa<GlobalValue>(Val) ||
106
48
                               
isa<ConstantExpr>(Val)12
||
107
48
                               
isa<ConstantAggregate>(Val)0
;
108
48
    return !CanStoreMutableData;
109
48
  }
110
884
111
884
  return false;
112
884
}
113
114
CFLSteensAAResult::FunctionInfo::FunctionInfo(
115
    Function &Fn, const SmallVectorImpl<Value *> &RetVals,
116
    StratifiedSets<InstantiatedValue> S)
117
116
    : Sets(std::move(S)) {
118
116
  // Historically, an arbitrary upper-bound of 50 args was selected. We may want
119
116
  // to remove this if it doesn't really matter in practice.
120
116
  if (Fn.arg_size() > MaxSupportedArgsInSummary)
121
0
    return;
122
116
123
116
  DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
124
116
125
116
  // Our intention here is to record all InterfaceValues that share the same
126
116
  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
127
116
  // have its StratifiedIndex scanned here and check if the index is presented
128
116
  // in InterfaceMap: if it is not, we add the correspondence to the map;
129
116
  // otherwise, an aliasing relation is found and we add it to
130
116
  // RetParamRelations.
131
116
132
116
  auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
133
164
                                    StratifiedIndex SetIndex) {
134
164
    unsigned Level = 0;
135
321
    while (true) {
136
321
      InterfaceValue CurrValue{InterfaceIndex, Level};
137
321
138
321
      auto Itr = InterfaceMap.find(SetIndex);
139
321
      if (Itr != InterfaceMap.end()) {
140
33
        if (CurrValue != Itr->second)
141
33
          Summary.RetParamRelations.push_back(
142
33
              ExternalRelation{CurrValue, Itr->second, UnknownOffset});
143
33
        break;
144
33
      }
145
288
146
288
      auto &Link = Sets.getLink(SetIndex);
147
288
      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
148
288
      auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
149
288
      if (ExternalAttrs.any())
150
35
        Summary.RetParamAttributes.push_back(
151
35
            ExternalAttribute{CurrValue, ExternalAttrs});
152
288
153
288
      if (!Link.hasBelow())
154
131
        break;
155
157
156
157
      ++Level;
157
157
      SetIndex = Link.Below;
158
157
    }
159
164
  };
160
116
161
116
  // Populate RetParamRelations for return values
162
116
  for (auto *RetVal : RetVals) {
163
24
    assert(RetVal != nullptr);
164
24
    assert(RetVal->getType()->isPointerTy());
165
24
    auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
166
24
    if (RetInfo.hasValue())
167
24
      AddToRetParamRelations(0, RetInfo->Index);
168
24
  }
169
116
170
116
  // Populate RetParamRelations for parameters
171
116
  unsigned I = 0;
172
152
  for (auto &Param : Fn.args()) {
173
152
    if (Param.getType()->isPointerTy()) {
174
140
      auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
175
140
      if (ParamInfo.hasValue())
176
140
        AddToRetParamRelations(I + 1, ParamInfo->Index);
177
140
    }
178
152
    ++I;
179
152
  }
180
116
}
181
182
// Builds the graph + StratifiedSets for a function.
183
116
CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
184
116
  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
185
116
  StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
186
116
187
116
  // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
188
116
  auto &Graph = GraphBuilder.getCFLGraph();
189
466
  for (const auto &Mapping : Graph.value_mappings()) {
190
466
    auto Val = Mapping.first;
191
466
    if (canSkipAddingToSets(Val))
192
0
      continue;
193
466
    auto &ValueInfo = Mapping.second;
194
466
195
466
    assert(ValueInfo.getNumLevels() > 0);
196
466
    SetBuilder.add(InstantiatedValue{Val, 0});
197
466
    SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
198
466
                              ValueInfo.getNodeInfoAtLevel(0).Attr);
199
724
    for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; 
++I258
) {
200
258
      SetBuilder.add(InstantiatedValue{Val, I + 1});
201
258
      SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
202
258
                                ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
203
258
      SetBuilder.addBelow(InstantiatedValue{Val, I},
204
258
                          InstantiatedValue{Val, I + 1});
205
258
    }
206
466
  }
207
116
208
116
  // Add all assign edges to StratifiedSets
209
466
  for (const auto &Mapping : Graph.value_mappings()) {
210
466
    auto Val = Mapping.first;
211
466
    if (canSkipAddingToSets(Val))
212
0
      continue;
213
466
    auto &ValueInfo = Mapping.second;
214
466
215
1.19k
    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; 
++I724
) {
216
724
      auto Src = InstantiatedValue{Val, I};
217
724
      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
218
219
        SetBuilder.addWith(Src, Edge.Other);
219
724
    }
220
466
  }
221
116
222
116
  return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
223
116
}
224
225
116
void CFLSteensAAResult::scan(Function *Fn) {
226
116
  auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
227
116
  (void)InsertPair;
228
116
  assert(InsertPair.second &&
229
116
         "Trying to scan a function that has already been cached");
230
116
231
116
  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
232
116
  // may get evaluated after operator[], potentially triggering a DenseMap
233
116
  // resize and invalidating the reference returned by operator[]
234
116
  auto FunInfo = buildSetsFrom(Fn);
235
116
  Cache[Fn] = std::move(FunInfo);
236
116
237
116
  Handles.emplace_front(Fn, this);
238
116
}
239
240
0
void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
241
242
/// Ensures that the given function is available in the cache, and returns the
243
/// entry.
244
const Optional<CFLSteensAAResult::FunctionInfo> &
245
2.85k
CFLSteensAAResult::ensureCached(Function *Fn) {
246
2.85k
  auto Iter = Cache.find(Fn);
247
2.85k
  if (Iter == Cache.end()) {
248
116
    scan(Fn);
249
116
    Iter = Cache.find(Fn);
250
116
    assert(Iter != Cache.end());
251
116
    assert(Iter->second.hasValue());
252
116
  }
253
2.85k
  return Iter->second;
254
2.85k
}
255
256
64
const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
257
64
  auto &FunInfo = ensureCached(&Fn);
258
64
  if (FunInfo.hasValue())
259
64
    return &FunInfo->getAliasSummary();
260
0
  else
261
0
    return nullptr;
262
64
}
263
264
AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
265
2.79k
                                     const MemoryLocation &LocB) {
266
2.79k
  auto *ValA = const_cast<Value *>(LocA.Ptr);
267
2.79k
  auto *ValB = const_cast<Value *>(LocB.Ptr);
268
2.79k
269
2.79k
  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
270
0
    return NoAlias;
271
2.79k
272
2.79k
  Function *Fn = nullptr;
273
2.79k
  Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
274
2.79k
  Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
275
2.79k
  if (!MaybeFnA && 
!MaybeFnB45
) {
276
2
    // The only times this is known to happen are when globals + InlineAsm are
277
2
    // involved
278
2
    LLVM_DEBUG(
279
2
        dbgs()
280
2
        << "CFLSteensAA: could not extract parent function information.\n");
281
2
    return MayAlias;
282
2
  }
283
2.79k
284
2.79k
  if (MaybeFnA) {
285
2.75k
    Fn = MaybeFnA;
286
2.75k
    assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
287
2.75k
           "Interprocedural queries not supported");
288
2.75k
  } else {
289
43
    Fn = MaybeFnB;
290
43
  }
291
2.79k
292
2.79k
  assert(Fn != nullptr);
293
2.79k
  auto &MaybeInfo = ensureCached(Fn);
294
2.79k
  assert(MaybeInfo.hasValue());
295
2.79k
296
2.79k
  auto &Sets = MaybeInfo->getStratifiedSets();
297
2.79k
  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
298
2.79k
  if (!MaybeA.hasValue())
299
5
    return MayAlias;
300
2.79k
301
2.79k
  auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
302
2.79k
  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
546
    return MayAlias;
322
2.24k
  if (AttrsA.none() || 
AttrsB.none()1.95k
)
323
336
    return NoAlias;
324
1.90k
  if (hasUnknownOrCallerAttr(AttrsA) || 
hasUnknownOrCallerAttr(AttrsB)1.18k
)
325
1.17k
    return MayAlias;
326
731
  if (isGlobalOrArgAttr(AttrsA) && 
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
35
CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
346
35
  initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
347
35
}
348
349
35
void CFLSteensAAWrapperPass::initializePass() {
350
35
  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
351
35
  Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
352
35
}
353
354
35
void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
355
35
  AU.setPreservesAll();
356
35
  AU.addRequired<TargetLibraryInfoWrapperPass>();
357
35
}