Coverage Report

Created: 2019-03-24 22:13

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/AliasSetTracker.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
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 defines two classes: AliasSetTracker and AliasSet. These interfaces
10
// are used to classify a collection of pointer references into a maximal number
11
// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
12
// object refers to memory disjoint from the other sets.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
17
#define LLVM_ANALYSIS_ALIASSETTRACKER_H
18
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/ADT/DenseMapInfo.h"
21
#include "llvm/ADT/ilist.h"
22
#include "llvm/ADT/ilist_node.h"
23
#include "llvm/Analysis/AliasAnalysis.h"
24
#include "llvm/IR/Instruction.h"
25
#include "llvm/IR/Metadata.h"
26
#include "llvm/IR/ValueHandle.h"
27
#include "llvm/Support/Casting.h"
28
#include <cassert>
29
#include <cstddef>
30
#include <cstdint>
31
#include <iterator>
32
#include <vector>
33
34
namespace llvm {
35
36
class AliasSetTracker;
37
class BasicBlock;
38
class LoadInst;
39
class Loop;
40
class MemorySSA;
41
class AnyMemSetInst;
42
class AnyMemTransferInst;
43
class raw_ostream;
44
class StoreInst;
45
class VAArgInst;
46
class Value;
47
48
class AliasSet : public ilist_node<AliasSet> {
49
  friend class AliasSetTracker;
50
51
  class PointerRec {
52
    Value *Val;  // The pointer this record corresponds to.
53
    PointerRec **PrevInList = nullptr;
54
    PointerRec *NextInList = nullptr;
55
    AliasSet *AS = nullptr;
56
    LocationSize Size = LocationSize::mapEmpty();
57
    AAMDNodes AAInfo;
58
59
    // Whether the size for this record has been set at all. This makes no
60
    // guarantees about the size being known.
61
2.65M
    bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
62
63
  public:
64
    PointerRec(Value *V)
65
2.64M
      : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
66
67
18.3M
    Value *getValue() const { return Val; }
68
69
6.90M
    PointerRec *getNext() const { return NextInList; }
70
4.64M
    bool hasAliasSet() const { return AS != nullptr; }
71
72
2.77M
    PointerRec** setPrevInList(PointerRec **PIL) {
73
2.77M
      PrevInList = PIL;
74
2.77M
      return &NextInList;
75
2.77M
    }
76
77
4.65M
    bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
78
4.65M
      bool SizeChanged = false;
79
4.65M
      if (NewSize != Size) {
80
2.65M
        LocationSize OldSize = Size;
81
2.65M
        Size = isSizeSet() ? 
Size.unionWith(NewSize)13.8k
:
NewSize2.64M
;
82
2.65M
        SizeChanged = OldSize != Size;
83
2.65M
      }
84
4.65M
85
4.65M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
86
2.64M
        // We don't have a AAInfo yet. Set it to NewAAInfo.
87
2.64M
        AAInfo = NewAAInfo;
88
2.01M
      else {
89
2.01M
        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
90
2.01M
        if (!Intersection) {
91
241k
          // NewAAInfo conflicts with AAInfo.
92
241k
          AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
93
241k
          return SizeChanged;
94
241k
        }
95
1.76M
        AAInfo = Intersection;
96
1.76M
      }
97
4.65M
      
return SizeChanged4.41M
;
98
4.65M
    }
99
100
17.1M
    LocationSize getSize() const {
101
17.1M
      assert(isSizeSet() && "Getting an unset size!");
102
17.1M
      return Size;
103
17.1M
    }
104
105
    /// Return the AAInfo, or null if there is no information or conflicting
106
    /// information.
107
17.1M
    AAMDNodes getAAInfo() const {
108
17.1M
      // If we have missing or conflicting AAInfo, return null.
109
17.1M
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
110
17.1M
          AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
111
205k
        return AAMDNodes();
112
16.9M
      return AAInfo;
113
16.9M
    }
114
115
1.92M
    AliasSet *getAliasSet(AliasSetTracker &AST) {
116
1.92M
      assert(AS && "No AliasSet yet!");
117
1.92M
      if (AS->Forward) {
118
73.0k
        AliasSet *OldAS = AS;
119
73.0k
        AS = OldAS->getForwardedTarget(AST);
120
73.0k
        AS->addRef();
121
73.0k
        OldAS->dropRef(AST);
122
73.0k
      }
123
1.92M
      return AS;
124
1.92M
    }
125
126
2.64M
    void setAliasSet(AliasSet *as) {
127
2.64M
      assert(!AS && "Already have an alias set!");
128
2.64M
      AS = as;
129
2.64M
    }
130
131
2.64M
    void eraseFromList() {
132
2.64M
      if (NextInList) 
NextInList->PrevInList = PrevInList1.49M
;
133
2.64M
      *PrevInList = NextInList;
134
2.64M
      if (AS->PtrListEnd == &NextInList) {
135
1.12M
        AS->PtrListEnd = PrevInList;
136
1.12M
        assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
137
1.12M
      }
138
2.64M
      delete this;
139
2.64M
    }
140
  };
141
142
  // Doubly linked list of nodes.
143
  PointerRec *PtrList = nullptr;
144
  PointerRec **PtrListEnd;
145
  // Forwarding pointer.
146
  AliasSet *Forward = nullptr;
147
148
  /// All instructions without a specific address in this alias set.
149
  /// In rare cases this vector can have a null'ed out WeakVH
150
  /// instances (can happen if some other loop pass deletes an
151
  /// instruction in this list).
152
  std::vector<WeakVH> UnknownInsts;
153
154
  /// Number of nodes pointing to this AliasSet plus the number of AliasSets
155
  /// forwarding to it.
156
  unsigned RefCount : 27;
157
158
  // Signifies that this set should be considered to alias any pointer.
159
  // Use when the tracker holding this set is saturated.
160
  unsigned AliasAny : 1;
161
162
  /// The kinds of access this alias set models.
163
  ///
164
  /// We keep track of whether this alias set merely refers to the locations of
165
  /// memory (and not any particular access), whether it modifies or references
166
  /// the memory, or whether it does both. The lattice goes from "NoAccess" to
167
  /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
168
  enum AccessLattice {
169
    NoAccess = 0,
170
    RefAccess = 1,
171
    ModAccess = 2,
172
    ModRefAccess = RefAccess | ModAccess
173
  };
174
  unsigned Access : 2;
175
176
  /// The kind of alias relationship between pointers of the set.
177
  ///
178
  /// These represent conservatively correct alias results between any members
179
  /// of the set. We represent these independently of the values of alias
180
  /// results in order to pack it into a single bit. Lattice goes from
181
  /// MustAlias to MayAlias.
182
  enum AliasLattice {
183
    SetMustAlias = 0, SetMayAlias = 1
184
  };
185
  unsigned Alias : 1;
186
187
  unsigned SetSize = 0;
188
189
3.11M
  void addRef() { ++RefCount; }
190
191
136k
  void dropRef(AliasSetTracker &AST) {
192
136k
    assert(RefCount >= 1 && "Invalid reference count detected!");
193
136k
    if (--RefCount == 0)
194
60.6k
      removeFromTracker(AST);
195
136k
  }
196
197
1.24M
  Instruction *getUnknownInst(unsigned i) const {
198
1.24M
    assert(i < UnknownInsts.size());
199
1.24M
    return cast_or_null<Instruction>(UnknownInsts[i]);
200
1.24M
  }
201
202
public:
203
  AliasSet(const AliasSet &) = delete;
204
  AliasSet &operator=(const AliasSet &) = delete;
205
206
  /// Accessors...
207
886k
  bool isRef() const { return Access & RefAccess; }
208
1.55M
  bool isMod() const { return Access & ModAccess; }
209
3.67M
  bool isMustAlias() const { return Alias == SetMustAlias; }
210
1
  bool isMayAlias()  const { return Alias == SetMayAlias; }
211
212
  /// Return true if this alias set should be ignored as part of the
213
  /// AliasSetTracker object.
214
1.06M
  bool isForwardingAliasSet() const { return Forward; }
215
216
  /// Merge the specified alias set into this alias set.
217
  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
218
219
  // Alias Set iteration - Allow access to all of the pointers which are part of
220
  // this alias set.
221
  class iterator;
222
3.42M
  iterator begin() const { return iterator(PtrList); }
223
2.82M
  iterator end()   const { return iterator(); }
224
270
  bool empty() const { return PtrList == nullptr; }
225
226
  // Unfortunately, ilist::size() is linear, so we have to add code to keep
227
  // track of the list's exact size.
228
493k
  unsigned size() { return SetSize; }
229
230
  /// If this alias set is known to contain a single instruction and *only* a
231
  /// single unique instruction, return it.  Otherwise, return nullptr.
232
  Instruction* getUniqueInstruction();
233
234
  void print(raw_ostream &OS) const;
235
  void dump() const;
236
237
  /// Define an iterator for alias sets... this is just a forward iterator.
238
  class iterator : public std::iterator<std::forward_iterator_tag,
239
                                        PointerRec, ptrdiff_t> {
240
    PointerRec *CurNode;
241
242
  public:
243
6.25M
    explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
244
245
9.45M
    bool operator==(const iterator& x) const {
246
9.45M
      return CurNode == x.CurNode;
247
9.45M
    }
248
9.45M
    bool operator!=(const iterator& x) const { return !operator==(x); }
249
250
1.03M
    value_type &operator*() const {
251
1.03M
      assert(CurNode && "Dereferencing AliasSet.end()!");
252
1.03M
      return *CurNode;
253
1.03M
    }
254
602k
    value_type *operator->() const { return &operator*(); }
255
256
7.68M
    Value *getPointer() const { return CurNode->getValue(); }
257
7.68M
    LocationSize getSize() const { return CurNode->getSize(); }
258
7.68M
    AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
259
260
6.90M
    iterator& operator++() {                // Preincrement
261
6.90M
      assert(CurNode && "Advancing past AliasSet.end()!");
262
6.90M
      CurNode = CurNode->getNext();
263
6.90M
      return *this;
264
6.90M
    }
265
0
    iterator operator++(int) { // Postincrement
266
0
      iterator tmp = *this; ++*this; return tmp;
267
0
    }
268
  };
269
270
private:
271
  // Can only be created by AliasSetTracker.
272
  AliasSet()
273
      : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
274
1.00M
        Alias(SetMustAlias) {}
275
276
10.3M
  PointerRec *getSomePointer() const {
277
10.3M
    return PtrList;
278
10.3M
  }
279
280
  /// Return the real alias set this represents. If this has been merged with
281
  /// another set and is forwarding, return the ultimate destination set. This
282
  /// also implements the union-find collapsing as well.
283
2.07M
  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
284
2.07M
    if (!Forward) 
return this1.99M
;
285
74.0k
286
74.0k
    AliasSet *Dest = Forward->getForwardedTarget(AST);
287
74.0k
    if (Dest != Forward) {
288
1.03k
      Dest->addRef();
289
1.03k
      Forward->dropRef(AST);
290
1.03k
      Forward = Dest;
291
1.03k
    }
292
74.0k
    return Dest;
293
74.0k
  }
294
295
  void removeFromTracker(AliasSetTracker &AST);
296
297
  void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
298
                  const AAMDNodes &AAInfo, bool KnownMustAlias = false,
299
                  bool SkipSizeUpdate = false);
300
  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
301
302
  void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
303
    bool WasEmpty = UnknownInsts.empty();
304
    for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
305
      if (UnknownInsts[i] == I) {
306
        UnknownInsts[i] = UnknownInsts.back();
307
        UnknownInsts.pop_back();
308
        --i; --e;  // Revisit the moved entry.
309
      }
310
    if (!WasEmpty && UnknownInsts.empty())
311
      dropRef(AST);
312
  }
313
314
public:
315
  /// If the specified pointer "may" (or must) alias one of the members in the
316
  /// set return the appropriate AliasResult. Otherwise return NoAlias.
317
  AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
318
                             const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
319
  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
320
};
321
322
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
323
0
  AS.print(OS);
324
0
  return OS;
325
0
}
326
327
class AliasSetTracker {
328
  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
329
  /// Value is deleted.
330
0
  class ASTCallbackVH final : public CallbackVH {
331
    AliasSetTracker *AST;
332
333
    void deleted() override;
334
    void allUsesReplacedWith(Value *) override;
335
336
  public:
337
    ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
338
339
    ASTCallbackVH &operator=(Value *V);
340
  };
341
  /// Traits to tell DenseMap that tell us how to compare and hash the value
342
  /// handle.
343
  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
344
345
  AliasAnalysis &AA;
346
  MemorySSA *MSSA;
347
  Loop *L;
348
  ilist<AliasSet> AliasSets;
349
350
  using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
351
                                  ASTCallbackVHDenseMapInfo>;
352
353
  // Map from pointers to their node
354
  PointerMapType PointerMap;
355
356
public:
357
  /// Create an empty collection of AliasSets, and use the specified alias
358
  /// analysis object to disambiguate load and store addresses.
359
574k
  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
360
  explicit AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l)
361
156
      : AA(aa), MSSA(mssa), L(l) {}
362
574k
  ~AliasSetTracker() { clear(); }
363
364
  /// These methods are used to add different types of instructions to the alias
365
  /// sets. Adding a new instruction can result in one of three actions
366
  /// happening:
367
  ///
368
  ///   1. If the instruction doesn't alias any other sets, create a new set.
369
  ///   2. If the instruction aliases exactly one set, add it to the set
370
  ///   3. If the instruction aliases multiple sets, merge the sets, and add
371
  ///      the instruction to the result.
372
  ///
373
  /// These methods return true if inserting the instruction resulted in the
374
  /// addition of a new alias set (i.e., the pointer did not alias anything).
375
  ///
376
  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
377
  void add(LoadInst *LI);
378
  void add(StoreInst *SI);
379
  void add(VAArgInst *VAAI);
380
  void add(AnyMemSetInst *MSI);
381
  void add(AnyMemTransferInst *MTI);
382
  void add(Instruction *I);       // Dispatch to one of the other add methods...
383
  void add(BasicBlock &BB);       // Add all instructions in basic block
384
  void add(const AliasSetTracker &AST); // Add alias relations from another AST
385
  void addUnknown(Instruction *I);
386
  void addAllInstructionsInLoopUsingMSSA();
387
388
  void clear();
389
390
  /// Return the alias sets that are active.
391
  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
392
393
  /// Return the alias set which contains the specified memory location.  If
394
  /// the memory location aliases two or more existing alias sets, will have
395
  /// the effect of merging those alias sets before the single resulting alias
396
  /// set is returned.
397
  AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
398
399
  /// Return the underlying alias analysis object used by this tracker.
400
236k
  AliasAnalysis &getAliasAnalysis() const { return AA; }
401
402
  /// This method is used to remove a pointer value from the AliasSetTracker
403
  /// entirely. It should be used when an instruction is deleted from the
404
  /// program to update the AST. If you don't use this, you would have dangling
405
  /// pointers to deleted instructions.
406
  void deleteValue(Value *PtrVal);
407
408
  /// This method should be used whenever a preexisting value in the program is
409
  /// copied or cloned, introducing a new value.  Note that it is ok for clients
410
  /// that use this method to introduce the same value multiple times: if the
411
  /// tracker already knows about a value, it will ignore the request.
412
  void copyValue(Value *From, Value *To);
413
414
  using iterator = ilist<AliasSet>::iterator;
415
  using const_iterator = ilist<AliasSet>::const_iterator;
416
417
71.0k
  const_iterator begin() const { return AliasSets.begin(); }
418
71.0k
  const_iterator end()   const { return AliasSets.end(); }
419
420
4.31M
  iterator begin() { return AliasSets.begin(); }
421
4.31M
  iterator end()   { return AliasSets.end(); }
422
423
  void print(raw_ostream &OS) const;
424
  void dump() const;
425
426
private:
427
  friend class AliasSet;
428
429
  // The total number of pointers contained in all "may" alias sets.
430
  unsigned TotalMayAliasSetSize = 0;
431
432
  // A non-null value signifies this AST is saturated. A saturated AST lumps
433
  // all pointers into a single "May" set.
434
  AliasSet *AliasAnyAS = nullptr;
435
436
  void removeAliasSet(AliasSet *AS);
437
438
  /// Just like operator[] on the map, except that it creates an entry for the
439
  /// pointer if it doesn't already exist.
440
4.64M
  AliasSet::PointerRec &getEntryFor(Value *V) {
441
4.64M
    AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
442
4.64M
    if (!Entry)
443
2.64M
      Entry = new AliasSet::PointerRec(V);
444
4.64M
    return *Entry;
445
4.64M
  }
446
447
  AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
448
  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
449
                                     const AAMDNodes &AAInfo,
450
                                     bool &MustAliasAll);
451
452
  /// Merge all alias sets into a single set that is considered to alias any
453
  /// pointer.
454
  AliasSet &mergeAllAliasSets();
455
456
  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
457
};
458
459
0
inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
460
0
  AST.print(OS);
461
0
  return OS;
462
0
}
463
464
} // end namespace llvm
465
466
#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H