Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CFLAndersAliasAnalysis.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-based, summary-based alias analysis algorithm. It
10
// differs from CFLSteensAliasAnalysis in its inclusion-based nature while
11
// CFLSteensAliasAnalysis is unification-based. This pass has worse performance
12
// than CFLSteensAliasAnalysis (the worst case complexity of
13
// CFLAndersAliasAnalysis is cubic, while the worst case complexity of
14
// CFLSteensAliasAnalysis is almost linear), but it is able to yield more
15
// precise analysis result. The precision of this analysis is roughly the same
16
// as that of an one level context-sensitive Andersen's algorithm.
17
//
18
// The algorithm used here is based on recursive state machine matching scheme
19
// proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
20
// Rugina. The general idea is to extend the traditional transitive closure
21
// algorithm to perform CFL matching along the way: instead of recording
22
// "whether X is reachable from Y", we keep track of "whether X is reachable
23
// from Y at state Z", where the "state" field indicates where we are in the CFL
24
// matching process. To understand the matching better, it is advisable to have
25
// the state machine shown in Figure 3 of the paper available when reading the
26
// codes: all we do here is to selectively expand the transitive closure by
27
// discarding edges that are not recognized by the state machine.
28
//
29
// There are two differences between our current implementation and the one
30
// described in the paper:
31
// - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
32
// while in the paper the authors did the computation in a demand-driven
33
// fashion. We did not implement the demand-driven algorithm due to the
34
// additional coding complexity and higher memory profile, but if we found it
35
// necessary we may switch to it eventually.
36
// - In the paper the authors use a state machine that does not distinguish
37
// value reads from value writes. For example, if Y is reachable from X at state
38
// S3, it may be the case that X is written into Y, or it may be the case that
39
// there's a third value Z that writes into both X and Y. To make that
40
// distinction (which is crucial in building function summary as well as
41
// retrieving mod-ref info), we choose to duplicate some of the states in the
42
// paper's proposed state machine. The duplication does not change the set the
43
// machine accepts. Given a pair of reachable values, it only provides more
44
// detailed information on which value is being written into and which is being
45
// read from.
46
//
47
//===----------------------------------------------------------------------===//
48
49
// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
50
// CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
51
// FunctionPasses are only allowed to inspect the Function that they're being
52
// run on. Realistically, this likely isn't a problem until we allow
53
// FunctionPasses to run concurrently.
54
55
#include "llvm/Analysis/CFLAndersAliasAnalysis.h"
56
#include "AliasAnalysisSummary.h"
57
#include "CFLGraph.h"
58
#include "llvm/ADT/DenseMap.h"
59
#include "llvm/ADT/DenseMapInfo.h"
60
#include "llvm/ADT/DenseSet.h"
61
#include "llvm/ADT/None.h"
62
#include "llvm/ADT/Optional.h"
63
#include "llvm/ADT/STLExtras.h"
64
#include "llvm/ADT/SmallVector.h"
65
#include "llvm/ADT/iterator_range.h"
66
#include "llvm/Analysis/AliasAnalysis.h"
67
#include "llvm/Analysis/MemoryLocation.h"
68
#include "llvm/IR/Argument.h"
69
#include "llvm/IR/Function.h"
70
#include "llvm/IR/PassManager.h"
71
#include "llvm/IR/Type.h"
72
#include "llvm/Pass.h"
73
#include "llvm/Support/Casting.h"
74
#include "llvm/Support/Compiler.h"
75
#include "llvm/Support/Debug.h"
76
#include "llvm/Support/raw_ostream.h"
77
#include <algorithm>
78
#include <bitset>
79
#include <cassert>
80
#include <cstddef>
81
#include <cstdint>
82
#include <functional>
83
#include <utility>
84
#include <vector>
85
86
using namespace llvm;
87
using namespace llvm::cflaa;
88
89
#define DEBUG_TYPE "cfl-anders-aa"
90
91
61
CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {}
92
CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
93
82
    : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
94
143
CFLAndersAAResult::~CFLAndersAAResult() = default;
95
96
namespace {
97
98
enum class MatchState : uint8_t {
99
  // The following state represents S1 in the paper.
100
  FlowFromReadOnly = 0,
101
  // The following two states together represent S2 in the paper.
102
  // The 'NoReadWrite' suffix indicates that there exists an alias path that
103
  // does not contain assignment and reverse assignment edges.
104
  // The 'ReadOnly' suffix indicates that there exists an alias path that
105
  // contains reverse assignment edges only.
106
  FlowFromMemAliasNoReadWrite,
107
  FlowFromMemAliasReadOnly,
108
  // The following two states together represent S3 in the paper.
109
  // The 'WriteOnly' suffix indicates that there exists an alias path that
110
  // contains assignment edges only.
111
  // The 'ReadWrite' suffix indicates that there exists an alias path that
112
  // contains both assignment and reverse assignment edges. Note that if X and Y
113
  // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
114
  // and written to Y. Instead, it means that a third value Z is written to both
115
  // X and Y.
116
  FlowToWriteOnly,
117
  FlowToReadWrite,
118
  // The following two states together represent S4 in the paper.
119
  FlowToMemAliasWriteOnly,
120
  FlowToMemAliasReadWrite,
121
};
122
123
using StateSet = std::bitset<7>;
124
125
const unsigned ReadOnlyStateMask =
126
    (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
127
    (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
128
const unsigned WriteOnlyStateMask =
129
    (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
130
    (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
131
132
// A pair that consists of a value and an offset
133
struct OffsetValue {
134
  const Value *Val;
135
  int64_t Offset;
136
};
137
138
0
bool operator==(OffsetValue LHS, OffsetValue RHS) {
139
0
  return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
140
0
}
141
144
bool operator<(OffsetValue LHS, OffsetValue RHS) {
142
144
  return std::less<const Value *>()(LHS.Val, RHS.Val) ||
143
144
         
(76
LHS.Val == RHS.Val76
&&
LHS.Offset < RHS.Offset0
);
144
144
}
145
146
// A pair that consists of an InstantiatedValue and an offset
147
struct OffsetInstantiatedValue {
148
  InstantiatedValue IVal;
149
  int64_t Offset;
150
};
151
152
0
bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
153
0
  return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
154
0
}
155
156
// We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
157
// the paper) during the analysis.
158
class ReachabilitySet {
159
  using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
160
  using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
161
162
  ValueReachMap ReachMap;
163
164
public:
165
  using const_valuestate_iterator = ValueStateMap::const_iterator;
166
  using const_value_iterator = ValueReachMap::const_iterator;
167
168
  // Insert edge 'From->To' at state 'State'
169
1.01k
  bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
170
1.01k
    assert(From != To);
171
1.01k
    auto &States = ReachMap[To][From];
172
1.01k
    auto Idx = static_cast<size_t>(State);
173
1.01k
    if (!States.test(Idx)) {
174
948
      States.set(Idx);
175
948
      return true;
176
948
    }
177
64
    return false;
178
64
  }
179
180
  // Return the set of all ('From', 'State') pair for a given node 'To'
181
  iterator_range<const_valuestate_iterator>
182
547
  reachableValueAliases(InstantiatedValue V) const {
183
547
    auto Itr = ReachMap.find(V);
184
547
    if (Itr == ReachMap.end())
185
265
      return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
186
265
                                                   const_valuestate_iterator());
187
282
    return make_range<const_valuestate_iterator>(Itr->second.begin(),
188
282
                                                 Itr->second.end());
189
282
  }
190
191
190
  iterator_range<const_value_iterator> value_mappings() const {
192
190
    return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
193
190
  }
194
};
195
196
// We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
197
// in the paper) during the analysis.
198
class AliasMemSet {
199
  using MemSet = DenseSet<InstantiatedValue>;
200
  using MemMapType = DenseMap<InstantiatedValue, MemSet>;
201
202
  MemMapType MemMap;
203
204
public:
205
  using const_mem_iterator = MemSet::const_iterator;
206
207
40
  bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
208
40
    // Top-level values can never be memory aliases because one cannot take the
209
40
    // addresses of them
210
40
    assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
211
40
    return MemMap[LHS].insert(RHS).second;
212
40
  }
213
214
808
  const MemSet *getMemoryAliases(InstantiatedValue V) const {
215
808
    auto Itr = MemMap.find(V);
216
808
    if (Itr == MemMap.end())
217
742
      return nullptr;
218
66
    return &Itr->second;
219
66
  }
220
};
221
222
// We use AliasAttrMap to keep track of the AliasAttr of each node.
223
class AliasAttrMap {
224
  using MapType = DenseMap<InstantiatedValue, AliasAttrs>;
225
226
  MapType AttrMap;
227
228
public:
229
  using const_iterator = MapType::const_iterator;
230
231
1.06k
  bool add(InstantiatedValue V, AliasAttrs Attr) {
232
1.06k
    auto &OldAttr = AttrMap[V];
233
1.06k
    auto NewAttr = OldAttr | Attr;
234
1.06k
    if (OldAttr == NewAttr)
235
594
      return false;
236
466
    OldAttr = NewAttr;
237
466
    return true;
238
466
  }
239
240
780
  AliasAttrs getAttrs(InstantiatedValue V) const {
241
780
    AliasAttrs Attr;
242
780
    auto Itr = AttrMap.find(V);
243
780
    if (Itr != AttrMap.end())
244
780
      Attr = Itr->second;
245
780
    return Attr;
246
780
  }
247
248
190
  iterator_range<const_iterator> mappings() const {
249
190
    return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
250
190
  }
251
};
252
253
struct WorkListItem {
254
  InstantiatedValue From;
255
  InstantiatedValue To;
256
  MatchState State;
257
};
258
259
struct ValueSummary {
260
  struct Record {
261
    InterfaceValue IValue;
262
    unsigned DerefLevel;
263
  };
264
  SmallVector<Record, 4> FromRecords, ToRecords;
265
};
266
267
} // end anonymous namespace
268
269
namespace llvm {
270
271
// Specialize DenseMapInfo for OffsetValue.
272
template <> struct DenseMapInfo<OffsetValue> {
273
0
  static OffsetValue getEmptyKey() {
274
0
    return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
275
0
                       DenseMapInfo<int64_t>::getEmptyKey()};
276
0
  }
277
278
0
  static OffsetValue getTombstoneKey() {
279
0
    return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
280
0
                       DenseMapInfo<int64_t>::getEmptyKey()};
281
0
  }
282
283
0
  static unsigned getHashValue(const OffsetValue &OVal) {
284
0
    return DenseMapInfo<std::pair<const Value *, int64_t>>::getHashValue(
285
0
        std::make_pair(OVal.Val, OVal.Offset));
286
0
  }
287
288
0
  static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
289
0
    return LHS == RHS;
290
0
  }
291
};
292
293
// Specialize DenseMapInfo for OffsetInstantiatedValue.
294
template <> struct DenseMapInfo<OffsetInstantiatedValue> {
295
0
  static OffsetInstantiatedValue getEmptyKey() {
296
0
    return OffsetInstantiatedValue{
297
0
        DenseMapInfo<InstantiatedValue>::getEmptyKey(),
298
0
        DenseMapInfo<int64_t>::getEmptyKey()};
299
0
  }
300
301
0
  static OffsetInstantiatedValue getTombstoneKey() {
302
0
    return OffsetInstantiatedValue{
303
0
        DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
304
0
        DenseMapInfo<int64_t>::getEmptyKey()};
305
0
  }
306
307
0
  static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
308
0
    return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::getHashValue(
309
0
        std::make_pair(OVal.IVal, OVal.Offset));
310
0
  }
311
312
  static bool isEqual(const OffsetInstantiatedValue &LHS,
313
0
                      const OffsetInstantiatedValue &RHS) {
314
0
    return LHS == RHS;
315
0
  }
316
};
317
318
} // end namespace llvm
319
320
class CFLAndersAAResult::FunctionInfo {
321
  /// Map a value to other values that may alias it
322
  /// Since the alias relation is symmetric, to save some space we assume values
323
  /// are properly ordered: if a and b alias each other, and a < b, then b is in
324
  /// AliasMap[a] but not vice versa.
325
  DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
326
327
  /// Map a value to its corresponding AliasAttrs
328
  DenseMap<const Value *, AliasAttrs> AttrMap;
329
330
  /// Summary of externally visible effects.
331
  AliasSummary Summary;
332
333
  Optional<AliasAttrs> getAttrs(const Value *) const;
334
335
public:
336
  FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
337
               const ReachabilitySet &, const AliasAttrMap &);
338
339
  bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const;
340
64
  const AliasSummary &getAliasSummary() const { return Summary; }
341
};
342
343
83
static bool hasReadOnlyState(StateSet Set) {
344
83
  return (Set & StateSet(ReadOnlyStateMask)).any();
345
83
}
346
347
65
static bool hasWriteOnlyState(StateSet Set) {
348
65
  return (Set & StateSet(WriteOnlyStateMask)).any();
349
65
}
350
351
static Optional<InterfaceValue>
352
getInterfaceValue(InstantiatedValue IValue,
353
959
                  const SmallVectorImpl<Value *> &RetVals) {
354
959
  auto Val = IValue.Val;
355
959
356
959
  Optional<unsigned> Index;
357
959
  if (auto Arg = dyn_cast<Argument>(Val))
358
222
    Index = Arg->getArgNo() + 1;
359
737
  else if (is_contained(RetVals, Val))
360
61
    Index = 0;
361
959
362
959
  if (Index)
363
283
    return InterfaceValue{*Index, IValue.DerefLevel};
364
676
  return None;
365
676
}
366
367
static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
368
95
                            const AliasAttrMap &AMap) {
369
562
  for (const auto &Mapping : AMap.mappings()) {
370
562
    auto IVal = Mapping.first;
371
562
372
562
    // Insert IVal into the map
373
562
    auto &Attr = AttrMap[IVal.Val];
374
562
    // AttrMap only cares about top-level values
375
562
    if (IVal.DerefLevel == 0)
376
369
      Attr |= Mapping.second;
377
562
  }
378
95
}
379
380
static void
381
populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
382
95
                 const ReachabilitySet &ReachSet) {
383
314
  for (const auto &OuterMapping : ReachSet.value_mappings()) {
384
314
    // AliasMap only cares about top-level values
385
314
    if (OuterMapping.first.DerefLevel > 0)
386
113
      continue;
387
201
388
201
    auto Val = OuterMapping.first.Val;
389
201
    auto &AliasList = AliasMap[Val];
390
495
    for (const auto &InnerMapping : OuterMapping.second) {
391
495
      // Again, AliasMap only cares about top-level values
392
495
      if (InnerMapping.first.DerefLevel == 0)
393
262
        AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
394
495
    }
395
201
396
201
    // Sort AliasList for faster lookup
397
201
    llvm::sort(AliasList);
398
201
  }
399
95
}
400
401
static void populateExternalRelations(
402
    SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
403
95
    const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
404
95
  // If a function only returns one of its argument X, then X will be both an
405
95
  // argument and a return value at the same time. This is an edge case that
406
95
  // needs special handling here.
407
95
  for (const auto &Arg : Fn.args()) {
408
88
    if (is_contained(RetVals, &Arg)) {
409
3
      auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
410
3
      auto RetVal = InterfaceValue{0, 0};
411
3
      ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
412
3
    }
413
88
  }
414
95
415
95
  // Below is the core summary construction logic.
416
95
  // A naive solution of adding only the value aliases that are parameters or
417
95
  // return values in ReachSet to the summary won't work: It is possible that a
418
95
  // parameter P is written into an intermediate value I, and the function
419
95
  // subsequently returns *I. In that case, *I is does not value alias anything
420
95
  // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
421
95
  // (I, 1).
422
95
  // To account for the aforementioned case, we need to check each non-parameter
423
95
  // and non-return value for the possibility of acting as an intermediate.
424
95
  // 'ValueMap' here records, for each value, which InterfaceValues read from or
425
95
  // write into it. If both the read list and the write list of a given value
426
95
  // are non-empty, we know that a particular value is an intermidate and we
427
95
  // need to add summary edges from the writes to the reads.
428
95
  DenseMap<Value *, ValueSummary> ValueMap;
429
314
  for (const auto &OuterMapping : ReachSet.value_mappings()) {
430
314
    if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
431
83
      for (const auto &InnerMapping : OuterMapping.second) {
432
83
        // If Src is a param/return value, we get a same-level assignment.
433
83
        if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
434
18
          // This may happen if both Dst and Src are return values
435
18
          if (*Dst == *Src)
436
0
            continue;
437
18
438
18
          if (hasReadOnlyState(InnerMapping.second))
439
9
            ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
440
18
          // No need to check for WriteOnly state, since ReachSet is symmetric
441
65
        } else {
442
65
          // If Src is not a param/return, add it to ValueMap
443
65
          auto SrcIVal = InnerMapping.first;
444
65
          if (hasReadOnlyState(InnerMapping.second))
445
38
            ValueMap[SrcIVal.Val].FromRecords.push_back(
446
38
                ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
447
65
          if (hasWriteOnlyState(InnerMapping.second))
448
27
            ValueMap[SrcIVal.Val].ToRecords.push_back(
449
27
                ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
450
65
        }
451
83
      }
452
67
    }
453
314
  }
454
95
455
95
  for (const auto &Mapping : ValueMap) {
456
56
    for (const auto &FromRecord : Mapping.second.FromRecords) {
457
38
      for (const auto &ToRecord : Mapping.second.ToRecords) {
458
9
        auto ToLevel = ToRecord.DerefLevel;
459
9
        auto FromLevel = FromRecord.DerefLevel;
460
9
        // Same-level assignments should have already been processed by now
461
9
        if (ToLevel == FromLevel)
462
0
          continue;
463
9
464
9
        auto SrcIndex = FromRecord.IValue.Index;
465
9
        auto SrcLevel = FromRecord.IValue.DerefLevel;
466
9
        auto DstIndex = ToRecord.IValue.Index;
467
9
        auto DstLevel = ToRecord.IValue.DerefLevel;
468
9
        if (ToLevel > FromLevel)
469
3
          SrcLevel += ToLevel - FromLevel;
470
6
        else
471
6
          DstLevel += FromLevel - ToLevel;
472
9
473
9
        ExtRelations.push_back(ExternalRelation{
474
9
            InterfaceValue{SrcIndex, SrcLevel},
475
9
            InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
476
9
      }
477
38
    }
478
56
  }
479
95
480
95
  // Remove duplicates in ExtRelations
481
95
  llvm::sort(ExtRelations);
482
95
  ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
483
95
                     ExtRelations.end());
484
95
}
485
486
static void populateExternalAttributes(
487
    SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
488
95
    const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
489
562
  for (const auto &Mapping : AMap.mappings()) {
490
562
    if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
491
198
      auto Attr = getExternallyVisibleAttrs(Mapping.second);
492
198
      if (Attr.any())
493
26
        ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
494
198
    }
495
562
  }
496
95
}
497
498
CFLAndersAAResult::FunctionInfo::FunctionInfo(
499
    const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
500
95
    const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
501
95
  populateAttrMap(AttrMap, AMap);
502
95
  populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
503
95
  populateAliasMap(AliasMap, ReachSet);
504
95
  populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
505
95
}
506
507
Optional<AliasAttrs>
508
1.33k
CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
509
1.33k
  assert(V != nullptr);
510
1.33k
511
1.33k
  auto Itr = AttrMap.find(V);
512
1.33k
  if (Itr != AttrMap.end())
513
1.32k
    return Itr->second;
514
1
  return None;
515
1
}
516
517
bool CFLAndersAAResult::FunctionInfo::mayAlias(
518
    const Value *LHS, LocationSize MaybeLHSSize, const Value *RHS,
519
665
    LocationSize MaybeRHSSize) const {
520
665
  assert(LHS && RHS);
521
665
522
665
  // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
523
665
  // after the analysis gets executed, and we want to be conservative in those
524
665
  // cases.
525
665
  auto MaybeAttrsA = getAttrs(LHS);
526
665
  auto MaybeAttrsB = getAttrs(RHS);
527
665
  if (!MaybeAttrsA || 
!MaybeAttrsB664
)
528
1
    return true;
529
664
530
664
  // Check AliasAttrs before AliasMap lookup since it's cheaper
531
664
  auto AttrsA = *MaybeAttrsA;
532
664
  auto AttrsB = *MaybeAttrsB;
533
664
  if (hasUnknownOrCallerAttr(AttrsA))
534
148
    return AttrsB.any();
535
516
  if (hasUnknownOrCallerAttr(AttrsB))
536
10
    return AttrsA.any();
537
506
  if (isGlobalOrArgAttr(AttrsA))
538
48
    return isGlobalOrArgAttr(AttrsB);
539
458
  if (isGlobalOrArgAttr(AttrsB))
540
74
    return isGlobalOrArgAttr(AttrsA);
541
384
542
384
  // At this point both LHS and RHS should point to locally allocated objects
543
384
544
384
  auto Itr = AliasMap.find(LHS);
545
384
  if (Itr != AliasMap.end()) {
546
296
547
296
    // Find out all (X, Offset) where X == RHS
548
849
    auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
549
849
      return std::less<const Value *>()(LHS.Val, RHS.Val);
550
849
    };
551
#ifdef EXPENSIVE_CHECKS
552
    assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
553
#endif
554
    auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
555
296
                                      OffsetValue{RHS, 0}, Comparator);
556
296
557
296
    if (RangePair.first != RangePair.second) {
558
108
      // Be conservative about unknown sizes
559
108
      if (MaybeLHSSize == LocationSize::unknown() ||
560
108
          MaybeRHSSize == LocationSize::unknown())
561
0
        return true;
562
108
563
108
      const uint64_t LHSSize = MaybeLHSSize.getValue();
564
108
      const uint64_t RHSSize = MaybeRHSSize.getValue();
565
108
566
108
      for (const auto &OVal : make_range(RangePair)) {
567
108
        // Be conservative about UnknownOffset
568
108
        if (OVal.Offset == UnknownOffset)
569
108
          return true;
570
0
571
0
        // We know that LHS aliases (RHS + OVal.Offset) if the control flow
572
0
        // reaches here. The may-alias query essentially becomes integer
573
0
        // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
574
0
        // LHSSize) and [0, RHSSize).
575
0
576
0
        // Try to be conservative on super large offsets
577
0
        if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
578
0
          return true;
579
0
580
0
        auto LHSStart = OVal.Offset;
581
0
        // FIXME: Do we need to guard against integer overflow?
582
0
        auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
583
0
        auto RHSStart = 0;
584
0
        auto RHSEnd = static_cast<int64_t>(RHSSize);
585
0
        if (LHSEnd > RHSStart && LHSStart < RHSEnd)
586
0
          return true;
587
0
      }
588
108
    }
589
296
  }
590
384
591
384
  
return false276
;
592
384
}
593
594
static void propagate(InstantiatedValue From, InstantiatedValue To,
595
                      MatchState State, ReachabilitySet &ReachSet,
596
1.28k
                      std::vector<WorkListItem> &WorkList) {
597
1.28k
  if (From == To)
598
276
    return;
599
1.01k
  if (ReachSet.insert(From, To, State))
600
948
    WorkList.push_back(WorkListItem{From, To, State});
601
1.01k
}
602
603
static void initializeWorkList(std::vector<WorkListItem> &WorkList,
604
                               ReachabilitySet &ReachSet,
605
95
                               const CFLGraph &Graph) {
606
369
  for (const auto &Mapping : Graph.value_mappings()) {
607
369
    auto Val = Mapping.first;
608
369
    auto &ValueInfo = Mapping.second;
609
369
    assert(ValueInfo.getNumLevels() > 0);
610
369
611
369
    // Insert all immediate assignment neighbors to the worklist
612
931
    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; 
++I562
) {
613
562
      auto Src = InstantiatedValue{Val, I};
614
562
      // If there's an assignment edge from X to Y, it means Y is reachable from
615
562
      // X at S3 and X is reachable from Y at S1
616
562
      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
617
192
        propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
618
192
                  WorkList);
619
192
        propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
620
192
                  WorkList);
621
192
      }
622
562
    }
623
369
  }
624
95
}
625
626
static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
627
2.42k
                                                InstantiatedValue V) {
628
2.42k
  auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
629
2.42k
  if (Graph.getNode(NodeBelow))
630
392
    return NodeBelow;
631
2.03k
  return None;
632
2.03k
}
633
634
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
635
                                ReachabilitySet &ReachSet, AliasMemSet &MemSet,
636
948
                                std::vector<WorkListItem> &WorkList) {
637
948
  auto FromNode = Item.From;
638
948
  auto ToNode = Item.To;
639
948
640
948
  auto NodeInfo = Graph.getNode(ToNode);
641
948
  assert(NodeInfo != nullptr);
642
948
643
948
  // TODO: propagate field offsets
644
948
645
948
  // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
646
948
  // relations that are symmetric, we could actually cut the storage by half by
647
948
  // sorting FromNode and ToNode before insertion happens.
648
948
649
948
  // The newly added value alias pair may potentially generate more memory
650
948
  // alias pairs. Check for them here.
651
948
  auto FromNodeBelow = getNodeBelow(Graph, FromNode);
652
948
  auto ToNodeBelow = getNodeBelow(Graph, ToNode);
653
948
  if (FromNodeBelow && 
ToNodeBelow124
&&
654
948
      
MemSet.insert(*FromNodeBelow, *ToNodeBelow)40
) {
655
36
    propagate(*FromNodeBelow, *ToNodeBelow,
656
36
              MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
657
109
    for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
658
109
      auto Src = Mapping.first;
659
327
      auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
660
327
        if (Mapping.second.test(static_cast<size_t>(FromState)))
661
49
          propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
662
327
      };
663
109
664
109
      MemAliasPropagate(MatchState::FlowFromReadOnly,
665
109
                        MatchState::FlowFromMemAliasReadOnly);
666
109
      MemAliasPropagate(MatchState::FlowToWriteOnly,
667
109
                        MatchState::FlowToMemAliasWriteOnly);
668
109
      MemAliasPropagate(MatchState::FlowToReadWrite,
669
109
                        MatchState::FlowToMemAliasReadWrite);
670
109
    }
671
36
  }
672
948
673
948
  // This is the core of the state machine walking algorithm. We expand ReachSet
674
948
  // based on which state we are at (which in turn dictates what edges we
675
948
  // should examine)
676
948
  // From a high-level point of view, the state machine here guarantees two
677
948
  // properties:
678
948
  // - If *X and *Y are memory aliases, then X and Y are value aliases
679
948
  // - If Y is an alias of X, then reverse assignment edges (if there is any)
680
948
  // should precede any assignment edges on the path from X to Y.
681
948
  auto NextAssignState = [&](MatchState State) {
682
948
    for (const auto &AssignEdge : NodeInfo->Edges)
683
624
      propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
684
948
  };
685
948
  auto NextRevAssignState = [&](MatchState State) {
686
358
    for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
687
102
      propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
688
358
  };
689
948
  auto NextMemState = [&](MatchState State) {
690
808
    if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
691
66
      for (const auto &MemAlias : *AliasSet)
692
93
        propagate(FromNode, MemAlias, State, ReachSet, WorkList);
693
66
    }
694
808
  };
695
948
696
948
  switch (Item.State) {
697
948
  case MatchState::FlowFromReadOnly:
698
294
    NextRevAssignState(MatchState::FlowFromReadOnly);
699
294
    NextAssignState(MatchState::FlowToReadWrite);
700
294
    NextMemState(MatchState::FlowFromMemAliasReadOnly);
701
294
    break;
702
948
703
948
  case MatchState::FlowFromMemAliasNoReadWrite:
704
36
    NextRevAssignState(MatchState::FlowFromReadOnly);
705
36
    NextAssignState(MatchState::FlowToWriteOnly);
706
36
    break;
707
948
708
948
  case MatchState::FlowFromMemAliasReadOnly:
709
28
    NextRevAssignState(MatchState::FlowFromReadOnly);
710
28
    NextAssignState(MatchState::FlowToReadWrite);
711
28
    break;
712
948
713
948
  case MatchState::FlowToWriteOnly:
714
304
    NextAssignState(MatchState::FlowToWriteOnly);
715
304
    NextMemState(MatchState::FlowToMemAliasWriteOnly);
716
304
    break;
717
948
718
948
  case MatchState::FlowToReadWrite:
719
210
    NextAssignState(MatchState::FlowToReadWrite);
720
210
    NextMemState(MatchState::FlowToMemAliasReadWrite);
721
210
    break;
722
948
723
948
  case MatchState::FlowToMemAliasWriteOnly:
724
18
    NextAssignState(MatchState::FlowToWriteOnly);
725
18
    break;
726
948
727
948
  case MatchState::FlowToMemAliasReadWrite:
728
58
    NextAssignState(MatchState::FlowToReadWrite);
729
58
    break;
730
948
  }
731
948
}
732
733
static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
734
95
                                 const ReachabilitySet &ReachSet) {
735
95
  AliasAttrMap AttrMap;
736
95
  std::vector<InstantiatedValue> WorkList, NextList;
737
95
738
95
  // Initialize each node with its original AliasAttrs in CFLGraph
739
369
  for (const auto &Mapping : Graph.value_mappings()) {
740
369
    auto Val = Mapping.first;
741
369
    auto &ValueInfo = Mapping.second;
742
931
    for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; 
++I562
) {
743
562
      auto Node = InstantiatedValue{Val, I};
744
562
      AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
745
562
      WorkList.push_back(Node);
746
562
    }
747
369
  }
748
95
749
274
  while (!WorkList.empty()) {
750
780
    for (const auto &Dst : WorkList) {
751
780
      auto DstAttr = AttrMap.getAttrs(Dst);
752
780
      if (DstAttr.none())
753
269
        continue;
754
511
755
511
      // Propagate attr on the same level
756
511
      for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
757
352
        auto Src = Mapping.first;
758
352
        if (AttrMap.add(Src, DstAttr))
759
92
          NextList.push_back(Src);
760
352
      }
761
511
762
511
      // Propagate attr to the levels below
763
511
      auto DstBelow = getNodeBelow(Graph, Dst);
764
531
      while (DstBelow) {
765
146
        if (AttrMap.add(*DstBelow, DstAttr)) {
766
126
          NextList.push_back(*DstBelow);
767
126
          break;
768
126
        }
769
20
        DstBelow = getNodeBelow(Graph, *DstBelow);
770
20
      }
771
511
    }
772
179
    WorkList.swap(NextList);
773
179
    NextList.clear();
774
179
  }
775
95
776
95
  return AttrMap;
777
95
}
778
779
CFLAndersAAResult::FunctionInfo
780
95
CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
781
95
  CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
782
95
      *this, TLI,
783
95
      // Cast away the constness here due to GraphBuilder's API requirement
784
95
      const_cast<Function &>(Fn));
785
95
  auto &Graph = GraphBuilder.getCFLGraph();
786
95
787
95
  ReachabilitySet ReachSet;
788
95
  AliasMemSet MemSet;
789
95
790
95
  std::vector<WorkListItem> WorkList, NextList;
791
95
  initializeWorkList(WorkList, ReachSet, Graph);
792
95
  // TODO: make sure we don't stop before the fix point is reached
793
270
  while (!WorkList.empty()) {
794
175
    for (const auto &Item : WorkList)
795
948
      processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
796
175
797
175
    NextList.swap(WorkList);
798
175
    NextList.clear();
799
175
  }
800
95
801
95
  // Now that we have all the reachability info, propagate AliasAttrs according
802
95
  // to it
803
95
  auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
804
95
805
95
  return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
806
95
                      std::move(IValueAttrMap));
807
95
}
808
809
95
void CFLAndersAAResult::scan(const Function &Fn) {
810
95
  auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
811
95
  (void)InsertPair;
812
95
  assert(InsertPair.second &&
813
95
         "Trying to scan a function that has already been cached");
814
95
815
95
  // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
816
95
  // may get evaluated after operator[], potentially triggering a DenseMap
817
95
  // resize and invalidating the reference returned by operator[]
818
95
  auto FunInfo = buildInfoFrom(Fn);
819
95
  Cache[&Fn] = std::move(FunInfo);
820
95
  Handles.emplace_front(const_cast<Function *>(&Fn), this);
821
95
}
822
823
0
void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
824
825
const Optional<CFLAndersAAResult::FunctionInfo> &
826
729
CFLAndersAAResult::ensureCached(const Function &Fn) {
827
729
  auto Iter = Cache.find(&Fn);
828
729
  if (Iter == Cache.end()) {
829
95
    scan(Fn);
830
95
    Iter = Cache.find(&Fn);
831
95
    assert(Iter != Cache.end());
832
95
    assert(Iter->second.hasValue());
833
95
  }
834
729
  return Iter->second;
835
729
}
836
837
64
const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
838
64
  auto &FunInfo = ensureCached(Fn);
839
64
  if (FunInfo.hasValue())
840
64
    return &FunInfo->getAliasSummary();
841
0
  else
842
0
    return nullptr;
843
64
}
844
845
AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
846
665
                                     const MemoryLocation &LocB) {
847
665
  auto *ValA = LocA.Ptr;
848
665
  auto *ValB = LocB.Ptr;
849
665
850
665
  if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
851
0
    return NoAlias;
852
665
853
665
  auto *Fn = parentFunctionOfValue(ValA);
854
665
  if (!Fn) {
855
14
    Fn = parentFunctionOfValue(ValB);
856
14
    if (!Fn) {
857
0
      // The only times this is known to happen are when globals + InlineAsm are
858
0
      // involved
859
0
      LLVM_DEBUG(
860
0
          dbgs()
861
0
          << "CFLAndersAA: could not extract parent function information.\n");
862
0
      return MayAlias;
863
0
    }
864
651
  } else {
865
651
    assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
866
651
  }
867
665
868
665
  assert(Fn != nullptr);
869
665
  auto &FunInfo = ensureCached(*Fn);
870
665
871
665
  // AliasMap lookup
872
665
  if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
873
273
    return MayAlias;
874
392
  return NoAlias;
875
392
}
876
877
AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
878
                                     const MemoryLocation &LocB,
879
665
                                     AAQueryInfo &AAQI) {
880
665
  if (LocA.Ptr == LocB.Ptr)
881
0
    return MustAlias;
882
665
883
665
  // Comparisons between global variables and other constants should be
884
665
  // handled by BasicAA.
885
665
  // CFLAndersAA may report NoAlias when comparing a GlobalValue and
886
665
  // ConstantExpr, but every query needs to have at least one Value tied to a
887
665
  // Function, and neither GlobalValues nor ConstantExprs are.
888
665
  if (isa<Constant>(LocA.Ptr) && 
isa<Constant>(LocB.Ptr)14
)
889
0
    return AAResultBase::alias(LocA, LocB, AAQI);
890
665
891
665
  AliasResult QueryResult = query(LocA, LocB);
892
665
  if (QueryResult == MayAlias)
893
273
    return AAResultBase::alias(LocA, LocB, AAQI);
894
392
895
392
  return QueryResult;
896
392
}
897
898
AnalysisKey CFLAndersAA::Key;
899
900
41
CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
901
41
  return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
902
41
}
903
904
char CFLAndersAAWrapperPass::ID = 0;
905
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
906
                "Inclusion-Based CFL Alias Analysis", false, true)
907
908
0
ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
909
0
  return new CFLAndersAAWrapperPass();
910
0
}
911
912
20
CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
913
20
  initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
914
20
}
915
916
20
void CFLAndersAAWrapperPass::initializePass() {
917
20
  auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
918
20
  Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
919
20
}
920
921
20
void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
922
20
  AU.setPreservesAll();
923
20
  AU.addRequired<TargetLibraryInfoWrapperPass>();
924
20
}