Coverage Report

Created: 2018-12-14 11:24

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemorySSA.h
Line
Count
Source (jump to first uncovered line)
1
//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
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
/// \file
11
/// This file exposes an interface to building/using memory SSA to
12
/// walk memory instructions using a use/def graph.
13
///
14
/// Memory SSA class builds an SSA form that links together memory access
15
/// instructions such as loads, stores, atomics, and calls. Additionally, it
16
/// does a trivial form of "heap versioning" Every time the memory state changes
17
/// in the program, we generate a new heap version. It generates
18
/// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
19
///
20
/// As a trivial example,
21
/// define i32 @main() #0 {
22
/// entry:
23
///   %call = call noalias i8* @_Znwm(i64 4) #2
24
///   %0 = bitcast i8* %call to i32*
25
///   %call1 = call noalias i8* @_Znwm(i64 4) #2
26
///   %1 = bitcast i8* %call1 to i32*
27
///   store i32 5, i32* %0, align 4
28
///   store i32 7, i32* %1, align 4
29
///   %2 = load i32* %0, align 4
30
///   %3 = load i32* %1, align 4
31
///   %add = add nsw i32 %2, %3
32
///   ret i32 %add
33
/// }
34
///
35
/// Will become
36
/// define i32 @main() #0 {
37
/// entry:
38
///   ; 1 = MemoryDef(0)
39
///   %call = call noalias i8* @_Znwm(i64 4) #3
40
///   %2 = bitcast i8* %call to i32*
41
///   ; 2 = MemoryDef(1)
42
///   %call1 = call noalias i8* @_Znwm(i64 4) #3
43
///   %4 = bitcast i8* %call1 to i32*
44
///   ; 3 = MemoryDef(2)
45
///   store i32 5, i32* %2, align 4
46
///   ; 4 = MemoryDef(3)
47
///   store i32 7, i32* %4, align 4
48
///   ; MemoryUse(3)
49
///   %7 = load i32* %2, align 4
50
///   ; MemoryUse(4)
51
///   %8 = load i32* %4, align 4
52
///   %add = add nsw i32 %7, %8
53
///   ret i32 %add
54
/// }
55
///
56
/// Given this form, all the stores that could ever effect the load at %8 can be
57
/// gotten by using the MemoryUse associated with it, and walking from use to
58
/// def until you hit the top of the function.
59
///
60
/// Each def also has a list of users associated with it, so you can walk from
61
/// both def to users, and users to defs. Note that we disambiguate MemoryUses,
62
/// but not the RHS of MemoryDefs. You can see this above at %7, which would
63
/// otherwise be a MemoryUse(4). Being disambiguated means that for a given
64
/// store, all the MemoryUses on its use lists are may-aliases of that store
65
/// (but the MemoryDefs on its use list may not be).
66
///
67
/// MemoryDefs are not disambiguated because it would require multiple reaching
68
/// definitions, which would require multiple phis, and multiple memoryaccesses
69
/// per instruction.
70
//
71
//===----------------------------------------------------------------------===//
72
73
#ifndef LLVM_ANALYSIS_MEMORYSSA_H
74
#define LLVM_ANALYSIS_MEMORYSSA_H
75
76
#include "llvm/ADT/DenseMap.h"
77
#include "llvm/ADT/GraphTraits.h"
78
#include "llvm/ADT/SmallPtrSet.h"
79
#include "llvm/ADT/SmallVector.h"
80
#include "llvm/ADT/ilist.h"
81
#include "llvm/ADT/ilist_node.h"
82
#include "llvm/ADT/iterator.h"
83
#include "llvm/ADT/iterator_range.h"
84
#include "llvm/ADT/simple_ilist.h"
85
#include "llvm/Analysis/AliasAnalysis.h"
86
#include "llvm/Analysis/MemoryLocation.h"
87
#include "llvm/Analysis/PHITransAddr.h"
88
#include "llvm/IR/BasicBlock.h"
89
#include "llvm/IR/DerivedUser.h"
90
#include "llvm/IR/Dominators.h"
91
#include "llvm/IR/Module.h"
92
#include "llvm/IR/Type.h"
93
#include "llvm/IR/Use.h"
94
#include "llvm/IR/User.h"
95
#include "llvm/IR/Value.h"
96
#include "llvm/IR/ValueHandle.h"
97
#include "llvm/Pass.h"
98
#include "llvm/Support/Casting.h"
99
#include <algorithm>
100
#include <cassert>
101
#include <cstddef>
102
#include <iterator>
103
#include <memory>
104
#include <utility>
105
106
namespace llvm {
107
108
class Function;
109
class Instruction;
110
class MemoryAccess;
111
class MemorySSAWalker;
112
class LLVMContext;
113
class raw_ostream;
114
115
namespace MSSAHelpers {
116
117
struct AllAccessTag {};
118
struct DefsOnlyTag {};
119
120
} // end namespace MSSAHelpers
121
122
enum : unsigned {
123
  // Used to signify what the default invalid ID is for MemoryAccess's
124
  // getID()
125
  INVALID_MEMORYACCESS_ID = -1U
126
};
127
128
template <class T> class memoryaccess_def_iterator_base;
129
using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;
130
using const_memoryaccess_def_iterator =
131
    memoryaccess_def_iterator_base<const MemoryAccess>;
132
133
// The base for all memory accesses. All memory accesses in a block are
134
// linked together using an intrusive list.
135
class MemoryAccess
136
    : public DerivedUser,
137
      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
138
      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
139
public:
140
  using AllAccessType =
141
      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
142
  using DefsOnlyType =
143
      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
144
145
  MemoryAccess(const MemoryAccess &) = delete;
146
  MemoryAccess &operator=(const MemoryAccess &) = delete;
147
148
  void *operator new(size_t) = delete;
149
150
  // Methods for support type inquiry through isa, cast, and
151
  // dyn_cast
152
824
  static bool classof(const Value *V) {
153
824
    unsigned ID = V->getValueID();
154
824
    return ID == MemoryUseVal || 
ID == MemoryPhiVal727
||
ID == MemoryDefVal282
;
155
824
  }
156
157
31.3M
  BasicBlock *getBlock() const { return Block; }
158
159
  void print(raw_ostream &OS) const;
160
  void dump() const;
161
162
  /// The user iterators for a memory access
163
  using iterator = user_iterator;
164
  using const_iterator = const_user_iterator;
165
166
  /// This iterator walks over all of the defs in a given
167
  /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
168
  /// MemoryUse/MemoryDef, this walks the defining access.
169
  memoryaccess_def_iterator defs_begin();
170
  const_memoryaccess_def_iterator defs_begin() const;
171
  memoryaccess_def_iterator defs_end();
172
  const_memoryaccess_def_iterator defs_end() const;
173
174
  /// Get the iterators for the all access list and the defs only list
175
  /// We default to the all access list.
176
62
  AllAccessType::self_iterator getIterator() {
177
62
    return this->AllAccessType::getIterator();
178
62
  }
179
0
  AllAccessType::const_self_iterator getIterator() const {
180
0
    return this->AllAccessType::getIterator();
181
0
  }
182
29
  AllAccessType::reverse_self_iterator getReverseIterator() {
183
29
    return this->AllAccessType::getReverseIterator();
184
29
  }
185
0
  AllAccessType::const_reverse_self_iterator getReverseIterator() const {
186
0
    return this->AllAccessType::getReverseIterator();
187
0
  }
188
18
  DefsOnlyType::self_iterator getDefsIterator() {
189
18
    return this->DefsOnlyType::getIterator();
190
18
  }
191
0
  DefsOnlyType::const_self_iterator getDefsIterator() const {
192
0
    return this->DefsOnlyType::getIterator();
193
0
  }
194
40
  DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
195
40
    return this->DefsOnlyType::getReverseIterator();
196
40
  }
197
0
  DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
198
0
    return this->DefsOnlyType::getReverseIterator();
199
0
  }
200
201
protected:
202
  friend class MemoryDef;
203
  friend class MemoryPhi;
204
  friend class MemorySSA;
205
  friend class MemoryUse;
206
  friend class MemoryUseOrDef;
207
208
  /// Used by MemorySSA to change the block of a MemoryAccess when it is
209
  /// moved.
210
119
  void setBlock(BasicBlock *BB) { Block = BB; }
211
212
  /// Used for debugging and tracking things about MemoryAccesses.
213
  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
214
  inline unsigned getID() const;
215
216
  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
217
               BasicBlock *BB, unsigned NumOperands)
218
      : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
219
10.4M
        Block(BB) {}
220
221
  // Use deleteValue() to delete a generic MemoryAccess.
222
10.4M
  ~MemoryAccess() = default;
223
224
private:
225
  BasicBlock *Block;
226
};
227
228
template <>
229
struct ilist_alloc_traits<MemoryAccess> {
230
9.74M
  static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
231
};
232
233
472
inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
234
472
  MA.print(OS);
235
472
  return OS;
236
472
}
237
238
/// Class that has the common methods + fields of memory uses/defs. It's
239
/// a little awkward to have, but there are many cases where we want either a
240
/// use or def, and there are many cases where uses are needed (defs aren't
241
/// acceptable), and vice-versa.
242
///
243
/// This class should never be instantiated directly; make a MemoryUse or
244
/// MemoryDef instead.
245
class MemoryUseOrDef : public MemoryAccess {
246
public:
247
  void *operator new(size_t) = delete;
248
249
  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
250
251
  /// Get the instruction that this MemoryUse represents.
252
20.4M
  Instruction *getMemoryInst() const { return MemoryInstruction; }
253
254
  /// Get the access that produces the memory state used by this Use.
255
16.7M
  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
256
257
17.9M
  static bool classof(const Value *MA) {
258
17.9M
    return MA->getValueID() == MemoryUseVal || 
MA->getValueID() == MemoryDefVal13.3M
;
259
17.9M
  }
260
261
  // Sadly, these have to be public because they are needed in some of the
262
  // iterators.
263
  inline bool isOptimized() const;
264
  inline MemoryAccess *getOptimized() const;
265
  inline void setOptimized(MemoryAccess *);
266
267
  // Retrieve AliasResult type of the optimized access. Ideally this would be
268
  // returned by the caching walker and may go away in the future.
269
193
  Optional<AliasResult> getOptimizedAccessType() const {
270
193
    return OptimizedAccessAlias;
271
193
  }
272
273
  /// Reset the ID of what this MemoryUse was optimized to, causing it to
274
  /// be rewalked by the walker if necessary.
275
  /// This really should only be called by tests.
276
  inline void resetOptimized();
277
278
protected:
279
  friend class MemorySSA;
280
  friend class MemorySSAUpdater;
281
282
  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
283
                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
284
                 unsigned NumOperands)
285
      : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
286
9.23M
        MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
287
9.23M
    setDefiningAccess(DMA);
288
9.23M
  }
289
290
  // Use deleteValue() to delete a generic MemoryUseOrDef.
291
9.23M
  ~MemoryUseOrDef() = default;
292
293
3.09M
  void setOptimizedAccessType(Optional<AliasResult> AR) {
294
3.09M
    OptimizedAccessAlias = AR;
295
3.09M
  }
296
297
  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
298
20.9M
                         Optional<AliasResult> AR = MayAlias) {
299
20.9M
    if (!Optimized) {
300
17.8M
      setOperand(0, DMA);
301
17.8M
      return;
302
17.8M
    }
303
3.03M
    setOptimized(DMA);
304
3.03M
    setOptimizedAccessType(AR);
305
3.03M
  }
306
307
private:
308
  Instruction *MemoryInstruction;
309
  Optional<AliasResult> OptimizedAccessAlias;
310
};
311
312
/// Represents read-only accesses to memory
313
///
314
/// In particular, the set of Instructions that will be represented by
315
/// MemoryUse's is exactly the set of Instructions for which
316
/// AliasAnalysis::getModRefInfo returns "Ref".
317
class MemoryUse final : public MemoryUseOrDef {
318
public:
319
  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
320
321
  MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
322
      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
323
3.09M
                       /*NumOperands=*/1) {}
324
325
  // allocate space for exactly one operand
326
3.09M
  void *operator new(size_t s) { return User::operator new(s, 1); }
327
328
45.8M
  static bool classof(const Value *MA) {
329
45.8M
    return MA->getValueID() == MemoryUseVal;
330
45.8M
  }
331
332
  void print(raw_ostream &OS) const;
333
334
4.14M
  void setOptimized(MemoryAccess *DMA) {
335
4.14M
    OptimizedID = DMA->getID();
336
4.14M
    setOperand(0, DMA);
337
4.14M
  }
338
339
1.40M
  bool isOptimized() const {
340
1.40M
    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
341
1.40M
  }
342
343
288k
  MemoryAccess *getOptimized() const {
344
288k
    return getDefiningAccess();
345
288k
  }
346
347
199
  void resetOptimized() {
348
199
    OptimizedID = INVALID_MEMORYACCESS_ID;
349
199
  }
350
351
protected:
352
  friend class MemorySSA;
353
354
private:
355
  static void deleteMe(DerivedUser *Self);
356
357
  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
358
};
359
360
template <>
361
struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
362
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)
363
364
/// Represents a read-write access to memory, whether it is a must-alias,
365
/// or a may-alias.
366
///
367
/// In particular, the set of Instructions that will be represented by
368
/// MemoryDef's is exactly the set of Instructions for which
369
/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
370
/// Note that, in order to provide def-def chains, all defs also have a use
371
/// associated with them. This use points to the nearest reaching
372
/// MemoryDef/MemoryPhi.
373
class MemoryDef final : public MemoryUseOrDef {
374
public:
375
  friend class MemorySSA;
376
377
  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
378
379
  MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
380
            unsigned Ver)
381
      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
382
                       /*NumOperands=*/2),
383
6.14M
        ID(Ver) {}
384
385
  // allocate space for exactly two operands
386
6.14M
  void *operator new(size_t s) { return User::operator new(s, 2); }
387
388
36.2M
  static bool classof(const Value *MA) {
389
36.2M
    return MA->getValueID() == MemoryDefVal;
390
36.2M
  }
391
392
6.11k
  void setOptimized(MemoryAccess *MA) {
393
6.11k
    setOperand(1, MA);
394
6.11k
    OptimizedID = MA->getID();
395
6.11k
  }
396
397
6.41k
  MemoryAccess *getOptimized() const {
398
6.41k
    return cast_or_null<MemoryAccess>(getOperand(1));
399
6.41k
  }
400
401
6.38k
  bool isOptimized() const {
402
6.38k
    return getOptimized() && 
OptimizedID == getOptimized()->getID()22
;
403
6.38k
  }
404
405
14.8k
  void resetOptimized() {
406
14.8k
    OptimizedID = INVALID_MEMORYACCESS_ID;
407
14.8k
  }
408
409
  void print(raw_ostream &OS) const;
410
411
2.57M
  unsigned getID() const { return ID; }
412
413
private:
414
  static void deleteMe(DerivedUser *Self);
415
416
  const unsigned ID;
417
  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
418
};
419
420
template <>
421
struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
422
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)
423
424
template <>
425
struct OperandTraits<MemoryUseOrDef> {
426
34.6M
  static Use *op_begin(MemoryUseOrDef *MUD) {
427
34.6M
    if (auto *MU = dyn_cast<MemoryUse>(MUD))
428
13.6M
      return OperandTraits<MemoryUse>::op_begin(MU);
429
20.9M
    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
430
20.9M
  }
431
432
  static Use *op_end(MemoryUseOrDef *MUD) {
433
    if (auto *MU = dyn_cast<MemoryUse>(MUD))
434
      return OperandTraits<MemoryUse>::op_end(MU);
435
    return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
436
  }
437
438
  static unsigned operands(const MemoryUseOrDef *MUD) {
439
    if (const auto *MU = dyn_cast<MemoryUse>(MUD))
440
      return OperandTraits<MemoryUse>::operands(MU);
441
    return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
442
  }
443
};
444
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
445
446
/// Represents phi nodes for memory accesses.
447
///
448
/// These have the same semantic as regular phi nodes, with the exception that
449
/// only one phi will ever exist in a given basic block.
450
/// Guaranteeing one phi per block means guaranteeing there is only ever one
451
/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
452
/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
453
/// a MemoryPhi's operands.
454
/// That is, given
455
/// if (a) {
456
///   store %a
457
///   store %b
458
/// }
459
/// it *must* be transformed into
460
/// if (a) {
461
///    1 = MemoryDef(liveOnEntry)
462
///    store %a
463
///    2 = MemoryDef(1)
464
///    store %b
465
/// }
466
/// and *not*
467
/// if (a) {
468
///    1 = MemoryDef(liveOnEntry)
469
///    store %a
470
///    2 = MemoryDef(liveOnEntry)
471
///    store %b
472
/// }
473
/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
474
/// end of the branch, and if there are not two phi nodes, one will be
475
/// disconnected completely from the SSA graph below that point.
476
/// Because MemoryUse's do not generate new definitions, they do not have this
477
/// issue.
478
class MemoryPhi final : public MemoryAccess {
479
  // allocate space for exactly zero operands
480
1.21M
  void *operator new(size_t s) { return User::operator new(s); }
481
482
public:
483
  /// Provide fast operand accessors
484
  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
485
486
  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
487
      : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
488
1.21M
        ReservedSpace(NumPreds) {
489
1.21M
    allocHungoffUses(ReservedSpace);
490
1.21M
  }
491
492
  // Block iterator interface. This provides access to the list of incoming
493
  // basic blocks, which parallels the list of incoming values.
494
  using block_iterator = BasicBlock **;
495
  using const_block_iterator = BasicBlock *const *;
496
497
3.17M
  block_iterator block_begin() {
498
3.17M
    auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace);
499
3.17M
    return reinterpret_cast<block_iterator>(Ref + 1);
500
3.17M
  }
501
502
6.40M
  const_block_iterator block_begin() const {
503
6.40M
    const auto *Ref =
504
6.40M
        reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace);
505
6.40M
    return reinterpret_cast<const_block_iterator>(Ref + 1);
506
6.40M
  }
507
508
6
  block_iterator block_end() { return block_begin() + getNumOperands(); }
509
510
0
  const_block_iterator block_end() const {
511
0
    return block_begin() + getNumOperands();
512
0
  }
513
514
  iterator_range<block_iterator> blocks() {
515
    return make_range(block_begin(), block_end());
516
  }
517
518
  iterator_range<const_block_iterator> blocks() const {
519
    return make_range(block_begin(), block_end());
520
  }
521
522
682
  op_range incoming_values() { return operands(); }
523
524
0
  const_op_range incoming_values() const { return operands(); }
525
526
  /// Return the number of incoming edges
527
6.43M
  unsigned getNumIncomingValues() const { return getNumOperands(); }
528
529
  /// Return incoming value number x
530
6.43M
  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
531
3.17M
  void setIncomingValue(unsigned I, MemoryAccess *V) {
532
3.17M
    assert(V && "PHI node got a null value!");
533
3.17M
    setOperand(I, V);
534
3.17M
  }
535
536
  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
537
  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
538
539
  /// Return incoming basic block number @p i.
540
6.40M
  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
541
542
  /// Return incoming basic block corresponding
543
  /// to an operand of the PHI.
544
1.02k
  BasicBlock *getIncomingBlock(const Use &U) const {
545
1.02k
    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
546
1.02k
    return getIncomingBlock(unsigned(&U - op_begin()));
547
1.02k
  }
548
549
  /// Return incoming basic block corresponding
550
  /// to value use iterator.
551
0
  BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
552
0
    return getIncomingBlock(I.getUse());
553
0
  }
554
555
3.17M
  void setIncomingBlock(unsigned I, BasicBlock *BB) {
556
3.17M
    assert(BB && "PHI node got a null basic block!");
557
3.17M
    block_begin()[I] = BB;
558
3.17M
  }
559
560
  /// Add an incoming value to the end of the PHI list
561
3.17M
  void addIncoming(MemoryAccess *V, BasicBlock *BB) {
562
3.17M
    if (getNumOperands() == ReservedSpace)
563
1.70M
      growOperands(); // Get more space!
564
3.17M
    // Initialize some new operands.
565
3.17M
    setNumHungOffUseOperands(getNumOperands() + 1);
566
3.17M
    setIncomingValue(getNumOperands() - 1, V);
567
3.17M
    setIncomingBlock(getNumOperands() - 1, BB);
568
3.17M
  }
569
570
  /// Return the first index of the specified basic
571
  /// block in the value list for this PHI.  Returns -1 if no instance.
572
176
  int getBasicBlockIndex(const BasicBlock *BB) const {
573
214
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I38
)
574
214
      if (block_begin()[I] == BB)
575
176
        return I;
576
176
    
return -10
;
577
176
  }
578
579
17
  MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
580
17
    int Idx = getBasicBlockIndex(BB);
581
17
    assert(Idx >= 0 && "Invalid basic block argument!");
582
17
    return getIncomingValue(Idx);
583
17
  }
584
585
  // After deleting incoming position I, the order of incoming may be changed.
586
164
  void unorderedDeleteIncoming(unsigned I) {
587
164
    unsigned E = getNumOperands();
588
164
    assert(I < E && "Cannot remove out of bounds Phi entry.");
589
164
    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
590
164
    // itself should be deleted.
591
164
    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
592
164
                     "at least 2 values.");
593
164
    setIncomingValue(I, getIncomingValue(E - 1));
594
164
    setIncomingBlock(I, block_begin()[E - 1]);
595
164
    setOperand(E - 1, nullptr);
596
164
    block_begin()[E - 1] = nullptr;
597
164
    setNumHungOffUseOperands(getNumOperands() - 1);
598
164
  }
599
600
  // After deleting entries that satisfy Pred, remaining entries may have
601
  // changed order.
602
168
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
547
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I379
)
604
379
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
164
        unorderedDeleteIncoming(I);
606
164
        E = getNumOperands();
607
164
        --I;
608
164
      }
609
168
    assert(getNumOperands() >= 1 &&
610
168
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
168
  }
void llvm::MemoryPhi::unorderedDeleteIncomingIf<llvm::MemoryPhi::unorderedDeleteIncomingBlock(llvm::BasicBlock const*)::'lambda'(llvm::MemoryAccess const*, llvm::BasicBlock const*)>(llvm::MemoryPhi::unorderedDeleteIncomingBlock(llvm::BasicBlock const*)::'lambda'(llvm::MemoryAccess const*, llvm::BasicBlock const*)&&)
Line
Count
Source
602
105
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
329
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I224
)
604
224
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
105
        unorderedDeleteIncoming(I);
606
105
        E = getNumOperands();
607
105
        --I;
608
105
      }
609
105
    assert(getNumOperands() >= 1 &&
610
105
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
105
  }
MemorySSAUpdater.cpp:void llvm::MemoryPhi::unorderedDeleteIncomingIf<llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(llvm::BasicBlock*, llvm::BasicBlock*)::$_0>(llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(llvm::BasicBlock*, llvm::BasicBlock*)::$_0&&)
Line
Count
Source
602
6
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
22
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I16
)
604
16
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
2
        unorderedDeleteIncoming(I);
606
2
        E = getNumOperands();
607
2
        --I;
608
2
      }
609
6
    assert(getNumOperands() >= 1 &&
610
6
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
6
  }
MemorySSAUpdater.cpp:void llvm::MemoryPhi::unorderedDeleteIncomingIf<llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(llvm::BasicBlock*, llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, bool)::$_8>(llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(llvm::BasicBlock*, llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, bool)::$_8&&)
Line
Count
Source
602
57
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
196
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I139
)
604
139
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
57
        unorderedDeleteIncoming(I);
606
57
        E = getNumOperands();
607
57
        --I;
608
57
      }
609
57
    assert(getNumOperands() >= 1 &&
610
57
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
57
  }
Unexecuted instantiation: void llvm::MemoryPhi::unorderedDeleteIncomingIf<llvm::MemoryPhi::unorderedDeleteIncomingValue(llvm::MemoryAccess const*)::'lambda'(llvm::MemoryAccess const*, llvm::BasicBlock const*)>(llvm::MemoryPhi::unorderedDeleteIncomingValue(llvm::MemoryAccess const*)::'lambda'(llvm::MemoryAccess const*, llvm::BasicBlock const*)&&)
612
613
  // After deleting incoming block BB, the incoming blocks order may be changed.
614
105
  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
615
105
    unorderedDeleteIncomingIf(
616
224
        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
617
105
  }
618
619
  // After deleting incoming memory access MA, the incoming accesses order may
620
  // be changed.
621
0
  void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
622
0
    unorderedDeleteIncomingIf(
623
0
        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
624
0
  }
625
626
31.9M
  static bool classof(const Value *V) {
627
31.9M
    return V->getValueID() == MemoryPhiVal;
628
31.9M
  }
629
630
  void print(raw_ostream &OS) const;
631
632
2.98M
  unsigned getID() const { return ID; }
633
634
protected:
635
  friend class MemorySSA;
636
637
  /// this is more complicated than the generic
638
  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
639
  /// values and pointers to the incoming blocks, all in one allocation.
640
1.21M
  void allocHungoffUses(unsigned N) {
641
1.21M
    User::allocHungoffUses(N, /* IsPhi */ true);
642
1.21M
  }
643
644
private:
645
  // For debugging only
646
  const unsigned ID;
647
  unsigned ReservedSpace;
648
649
  /// This grows the operand list in response to a push_back style of
650
  /// operation.  This grows the number of ops by 1.5 times.
651
1.70M
  void growOperands() {
652
1.70M
    unsigned E = getNumOperands();
653
1.70M
    // 2 op PHI nodes are VERY common, so reserve at least enough for that.
654
1.70M
    ReservedSpace = std::max(E + E / 2, 2u);
655
1.70M
    growHungoffUses(ReservedSpace, /* IsPhi */ true);
656
1.70M
  }
657
658
  static void deleteMe(DerivedUser *Self);
659
};
660
661
5.55M
inline unsigned MemoryAccess::getID() const {
662
5.55M
  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
663
5.55M
         "only memory defs and phis have ids");
664
5.55M
  if (const auto *MD = dyn_cast<MemoryDef>(this))
665
2.57M
    return MD->getID();
666
2.98M
  return cast<MemoryPhi>(this)->getID();
667
2.98M
}
668
669
1.40M
inline bool MemoryUseOrDef::isOptimized() const {
670
1.40M
  if (const auto *MD = dyn_cast<MemoryDef>(this))
671
6.11k
    return MD->isOptimized();
672
1.40M
  return cast<MemoryUse>(this)->isOptimized();
673
1.40M
}
674
675
288k
inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
676
288k
  if (const auto *MD = dyn_cast<MemoryDef>(this))
677
2
    return MD->getOptimized();
678
288k
  return cast<MemoryUse>(this)->getOptimized();
679
288k
}
680
681
4.15M
inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
682
4.15M
  if (auto *MD = dyn_cast<MemoryDef>(this))
683
6.11k
    MD->setOptimized(MA);
684
4.14M
  else
685
4.14M
    cast<MemoryUse>(this)->setOptimized(MA);
686
4.15M
}
687
688
15.0k
inline void MemoryUseOrDef::resetOptimized() {
689
15.0k
  if (auto *MD = dyn_cast<MemoryDef>(this))
690
14.8k
    MD->resetOptimized();
691
198
  else
692
198
    cast<MemoryUse>(this)->resetOptimized();
693
15.0k
}
694
695
template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
696
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
697
698
/// Encapsulates MemorySSA, including all data associated with memory
699
/// accesses.
700
class MemorySSA {
701
public:
702
  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
703
  ~MemorySSA();
704
705
  MemorySSAWalker *getWalker();
706
707
  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
708
  /// access associated with it. If passed a basic block gets the memory phi
709
  /// node that exists for that block, if there is one. Otherwise, this will get
710
  /// a MemoryUseOrDef.
711
2.43M
  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
712
2.43M
    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
713
2.43M
  }
714
715
5.08k
  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
716
5.08k
    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
717
5.08k
  }
718
719
  void dump() const;
720
  void print(raw_ostream &) const;
721
722
  /// Return true if \p MA represents the live on entry value
723
  ///
724
  /// Loads and stores from pointer arguments and other global values may be
725
  /// defined by memory operations that do not occur in the current function, so
726
  /// they may be live on entry to the function. MemorySSA represents such
727
  /// memory state by the live on entry definition, which is guaranteed to occur
728
  /// before any other memory access in the function.
729
11.0M
  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
730
11.0M
    return MA == LiveOnEntryDef.get();
731
11.0M
  }
732
733
2.14M
  inline MemoryAccess *getLiveOnEntryDef() const {
734
2.14M
    return LiveOnEntryDef.get();
735
2.14M
  }
736
737
  // Sadly, iplists, by default, owns and deletes pointers added to the
738
  // list. It's not currently possible to have two iplists for the same type,
739
  // where one owns the pointers, and one does not. This is because the traits
740
  // are per-type, not per-tag.  If this ever changes, we should make the
741
  // DefList an iplist.
742
  using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
743
  using DefsList =
744
      simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
745
746
  /// Return the list of MemoryAccess's for a given basic block.
747
  ///
748
  /// This list is not modifiable by the user.
749
45.1k
  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
750
45.1k
    return getWritableBlockAccesses(BB);
751
45.1k
  }
752
753
  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
754
  /// block.
755
  ///
756
  /// This list is not modifiable by the user.
757
2.51M
  const DefsList *getBlockDefs(const BasicBlock *BB) const {
758
2.51M
    return getWritableBlockDefs(BB);
759
2.51M
  }
760
761
  /// Given two memory accesses in the same basic block, determine
762
  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
763
  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
764
765
  /// Given two memory accesses in potentially different blocks,
766
  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
767
  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
768
769
  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
770
  /// dominates Use \p B.
771
  bool dominates(const MemoryAccess *A, const Use &B) const;
772
773
  /// Verify that MemorySSA is self consistent (IE definitions dominate
774
  /// all uses, uses appear in the right places).  This is used by unit tests.
775
  void verifyMemorySSA() const;
776
777
  /// Check clobber sanity for an access.
778
  void checkClobberSanityAccess(const MemoryAccess *MA) const;
779
780
  /// Used in various insertion functions to specify whether we are talking
781
  /// about the beginning or end of a block.
782
  enum InsertionPlace { Beginning, End };
783
784
protected:
785
  // Used by Memory SSA annotater, dumpers, and wrapper pass
786
  friend class MemorySSAAnnotatedWriter;
787
  friend class MemorySSAPrinterLegacyPass;
788
  friend class MemorySSAUpdater;
789
790
  void verifyDefUses(Function &F) const;
791
  void verifyDomination(Function &F) const;
792
  void verifyOrdering(Function &F) const;
793
  void verifyDominationNumbers(const Function &F) const;
794
  void verifyClobberSanity(const Function &F) const;
795
796
  // This is used by the use optimizer and updater.
797
4.92M
  AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
798
4.92M
    auto It = PerBlockAccesses.find(BB);
799
4.92M
    return It == PerBlockAccesses.end() ? 
nullptr1.19M
:
It->second.get()3.72M
;
800
4.92M
  }
801
802
  // This is used by the use optimizer and updater.
803
2.52M
  DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
804
2.52M
    auto It = PerBlockDefs.find(BB);
805
2.52M
    return It == PerBlockDefs.end() ? 
nullptr1.31M
:
It->second.get()1.21M
;
806
2.52M
  }
807
808
  // These is used by the updater to perform various internal MemorySSA
809
  // machinsations.  They do not always leave the IR in a correct state, and
810
  // relies on the updater to fixup what it breaks, so it is not public.
811
812
  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
813
  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
814
815
  // Rename the dominator tree branch rooted at BB.
816
  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
817
1
                  SmallPtrSetImpl<BasicBlock *> &Visited) {
818
1
    renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
819
1
  }
820
821
  void removeFromLookups(MemoryAccess *);
822
  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
823
  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
824
                               InsertionPlace);
825
  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
826
                             AccessList::iterator);
827
  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
828
                                      const MemoryUseOrDef *Template = nullptr);
829
830
private:
831
  class CachingWalker;
832
  class OptimizeUses;
833
834
  CachingWalker *getWalkerImpl();
835
  void buildMemorySSA();
836
  void optimizeUses();
837
838
  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
839
  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
840
841
  using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
842
  using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
843
844
  void
845
  determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
846
  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
847
  bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
848
  MemoryPhi *createMemoryPhi(BasicBlock *BB);
849
  MemoryUseOrDef *createNewAccess(Instruction *,
850
                                  const MemoryUseOrDef *Template = nullptr);
851
  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
852
  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
853
  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
854
  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
855
  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
856
                  SmallPtrSetImpl<BasicBlock *> &Visited,
857
                  bool SkipVisited = false, bool RenameAllUses = false);
858
  AccessList *getOrCreateAccessList(const BasicBlock *);
859
  DefsList *getOrCreateDefsList(const BasicBlock *);
860
  void renumberBlock(const BasicBlock *) const;
861
  AliasAnalysis *AA;
862
  DominatorTree *DT;
863
  Function &F;
864
865
  // Memory SSA mappings
866
  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
867
868
  // These two mappings contain the main block to access/def mappings for
869
  // MemorySSA. The list contained in PerBlockAccesses really owns all the
870
  // MemoryAccesses.
871
  // Both maps maintain the invariant that if a block is found in them, the
872
  // corresponding list is not empty, and if a block is not found in them, the
873
  // corresponding list is empty.
874
  AccessMap PerBlockAccesses;
875
  DefsMap PerBlockDefs;
876
  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
877
878
  // Domination mappings
879
  // Note that the numbering is local to a block, even though the map is
880
  // global.
881
  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
882
  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
883
884
  // Memory SSA building info
885
  std::unique_ptr<CachingWalker> Walker;
886
  unsigned NextID;
887
};
888
889
// Internal MemorySSA utils, for use by MemorySSA classes and walkers
890
class MemorySSAUtil {
891
protected:
892
  friend class GVNHoist;
893
  friend class MemorySSAWalker;
894
895
  // This function should not be used by new passes.
896
  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
897
                                  AliasAnalysis &AA);
898
};
899
900
// This pass does eager building and then printing of MemorySSA. It is used by
901
// the tests to be able to build, dump, and verify Memory SSA.
902
class MemorySSAPrinterLegacyPass : public FunctionPass {
903
public:
904
  MemorySSAPrinterLegacyPass();
905
906
  bool runOnFunction(Function &) override;
907
  void getAnalysisUsage(AnalysisUsage &AU) const override;
908
909
  static char ID;
910
};
911
912
/// An analysis that produces \c MemorySSA for a function.
913
///
914
class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
915
  friend AnalysisInfoMixin<MemorySSAAnalysis>;
916
917
  static AnalysisKey Key;
918
919
public:
920
  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
921
  // pointers after construction.  Use a wrapper class instead of plain
922
  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
923
  struct Result {
924
240
    Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
925
926
275
    MemorySSA &getMSSA() { return *MSSA.get(); }
927
928
    std::unique_ptr<MemorySSA> MSSA;
929
  };
930
931
  Result run(Function &F, FunctionAnalysisManager &AM);
932
};
933
934
/// Printer pass for \c MemorySSA.
935
class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
936
  raw_ostream &OS;
937
938
public:
939
20
  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
940
941
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
942
};
943
944
/// Verifier pass for \c MemorySSA.
945
struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
946
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
947
};
948
949
/// Legacy analysis pass which computes \c MemorySSA.
950
class MemorySSAWrapperPass : public FunctionPass {
951
public:
952
  MemorySSAWrapperPass();
953
954
  static char ID;
955
956
  bool runOnFunction(Function &) override;
957
  void releaseMemory() override;
958
706k
  MemorySSA &getMSSA() { return *MSSA; }
959
0
  const MemorySSA &getMSSA() const { return *MSSA; }
960
961
  void getAnalysisUsage(AnalysisUsage &AU) const override;
962
963
  void verifyAnalysis() const override;
964
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
965
966
private:
967
  std::unique_ptr<MemorySSA> MSSA;
968
};
969
970
/// This is the generic walker interface for walkers of MemorySSA.
971
/// Walkers are used to be able to further disambiguate the def-use chains
972
/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
973
/// you.
974
/// In particular, while the def-use chains provide basic information, and are
975
/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
976
/// MemoryUse as AliasAnalysis considers it, a user mant want better or other
977
/// information. In particular, they may want to use SCEV info to further
978
/// disambiguate memory accesses, or they may want the nearest dominating
979
/// may-aliasing MemoryDef for a call or a store. This API enables a
980
/// standardized interface to getting and using that info.
981
class MemorySSAWalker {
982
public:
983
  MemorySSAWalker(MemorySSA *);
984
706k
  virtual ~MemorySSAWalker() = default;
985
986
  using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
987
988
  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
989
  /// will give you the nearest dominating MemoryAccess that Mod's the location
990
  /// the instruction accesses (by skipping any def which AA can prove does not
991
  /// alias the location(s) accessed by the instruction given).
992
  ///
993
  /// Note that this will return a single access, and it must dominate the
994
  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
995
  /// this will return the MemoryPhi, not the operand. This means that
996
  /// given:
997
  /// if (a) {
998
  ///   1 = MemoryDef(liveOnEntry)
999
  ///   store %a
1000
  /// } else {
1001
  ///   2 = MemoryDef(liveOnEntry)
1002
  ///   store %b
1003
  /// }
1004
  /// 3 = MemoryPhi(2, 1)
1005
  /// MemoryUse(3)
1006
  /// load %a
1007
  ///
1008
  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1009
  /// in the if (a) branch.
1010
1.40M
  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1011
1.40M
    MemoryAccess *MA = MSSA->getMemoryAccess(I);
1012
1.40M
    assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
1013
1.40M
    return getClobberingMemoryAccess(MA);
1014
1.40M
  }
1015
1016
  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1017
  /// but takes a MemoryAccess instead of an Instruction.
1018
  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
1019
1020
  /// Given a potentially clobbering memory access and a new location,
1021
  /// calling this will give you the nearest dominating clobbering MemoryAccess
1022
  /// (by skipping non-aliasing def links).
1023
  ///
1024
  /// This version of the function is mainly used to disambiguate phi translated
1025
  /// pointers, where the value of a pointer may have changed from the initial
1026
  /// memory access. Note that this expects to be handed either a MemoryUse,
1027
  /// or an already potentially clobbering access. Unlike the above API, if
1028
  /// given a MemoryDef that clobbers the pointer as the starting access, it
1029
  /// will return that MemoryDef, whereas the above would return the clobber
1030
  /// starting from the use side of  the memory def.
1031
  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1032
                                                  const MemoryLocation &) = 0;
1033
1034
  /// Given a memory access, invalidate anything this walker knows about
1035
  /// that access.
1036
  /// This API is used by walkers that store information to perform basic cache
1037
  /// invalidation.  This will be called by MemorySSA at appropriate times for
1038
  /// the walker it uses or returns.
1039
0
  virtual void invalidateInfo(MemoryAccess *) {}
1040
1041
1.83k
  virtual void verify(const MemorySSA *MSSA) { assert(MSSA == this->MSSA); }
1042
1043
protected:
1044
  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1045
                          // constructor.
1046
  MemorySSA *MSSA;
1047
};
1048
1049
/// A MemorySSAWalker that does no alias queries, or anything else. It
1050
/// simply returns the links as they were constructed by the builder.
1051
class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1052
public:
1053
  // Keep the overrides below from hiding the Instruction overload of
1054
  // getClobberingMemoryAccess.
1055
  using MemorySSAWalker::getClobberingMemoryAccess;
1056
1057
  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1058
  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1059
                                          const MemoryLocation &) override;
1060
};
1061
1062
using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1063
using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1064
1065
/// Iterator base class used to implement const and non-const iterators
1066
/// over the defining accesses of a MemoryAccess.
1067
template <class T>
1068
class memoryaccess_def_iterator_base
1069
    : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1070
                                  std::forward_iterator_tag, T, ptrdiff_t, T *,
1071
                                  T *> {
1072
  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1073
1074
public:
1075
2.65M
  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1076
9.09M
  memoryaccess_def_iterator_base() = default;
1077
1078
15.5M
  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1079
15.5M
    return Access == Other.Access && 
(5.31M
!Access5.31M
||
ArgNo == Other.ArgNo0
);
1080
15.5M
  }
1081
1082
  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1083
  // block from the operand in constant time (In a PHINode, the uselist has
1084
  // both, so it's just subtraction). We provide it as part of the
1085
  // iterator to avoid callers having to linear walk to get the block.
1086
  // If the operation becomes constant time on MemoryPHI's, this bit of
1087
  // abstraction breaking should be removed.
1088
6.39M
  BasicBlock *getPhiArgBlock() const {
1089
6.39M
    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1090
6.39M
    assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1091
6.39M
    return MP->getIncomingBlock(ArgNo);
1092
6.39M
  }
1093
1094
6.43M
  typename BaseT::iterator::pointer operator*() const {
1095
6.43M
    assert(Access && "Tried to access past the end of our iterator");
1096
6.43M
    // Go to the first argument for phis, and the defining access for everything
1097
6.43M
    // else.
1098
6.43M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1099
6.43M
      return MP->getIncomingValue(ArgNo);
1100
0
    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1101
0
  }
1102
1103
  using BaseT::operator++;
1104
6.43M
  memoryaccess_def_iterator &operator++() {
1105
6.43M
    assert(Access && "Hit end of iterator");
1106
6.43M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1107
6.43M
      if (++ArgNo >= MP->getNumIncomingValues()) {
1108
2.65M
        ArgNo = 0;
1109
2.65M
        Access = nullptr;
1110
2.65M
      }
1111
6.43M
    } else {
1112
0
      Access = nullptr;
1113
0
    }
1114
6.43M
    return *this;
1115
6.43M
  }
1116
1117
private:
1118
  T *Access = nullptr;
1119
  unsigned ArgNo = 0;
1120
};
1121
1122
inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1123
  return memoryaccess_def_iterator(this);
1124
}
1125
1126
inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1127
  return const_memoryaccess_def_iterator(this);
1128
}
1129
1130
6.43M
inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1131
6.43M
  return memoryaccess_def_iterator();
1132
6.43M
}
1133
1134
0
inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1135
0
  return const_memoryaccess_def_iterator();
1136
0
}
1137
1138
/// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1139
/// and uses in the inverse case.
1140
template <> struct GraphTraits<MemoryAccess *> {
1141
  using NodeRef = MemoryAccess *;
1142
  using ChildIteratorType = memoryaccess_def_iterator;
1143
1144
  static NodeRef getEntryNode(NodeRef N) { return N; }
1145
  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1146
  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1147
};
1148
1149
template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1150
  using NodeRef = MemoryAccess *;
1151
  using ChildIteratorType = MemoryAccess::iterator;
1152
1153
  static NodeRef getEntryNode(NodeRef N) { return N; }
1154
  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1155
  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1156
};
1157
1158
/// Provide an iterator that walks defs, giving both the memory access,
1159
/// and the current pointer location, updating the pointer location as it
1160
/// changes due to phi node translation.
1161
///
1162
/// This iterator, while somewhat specialized, is what most clients actually
1163
/// want when walking upwards through MemorySSA def chains. It takes a pair of
1164
/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1165
/// memory location through phi nodes for the user.
1166
class upward_defs_iterator
1167
    : public iterator_facade_base<upward_defs_iterator,
1168
                                  std::forward_iterator_tag,
1169
                                  const MemoryAccessPair> {
1170
  using BaseT = upward_defs_iterator::iterator_facade_base;
1171
1172
public:
1173
  upward_defs_iterator(const MemoryAccessPair &Info)
1174
      : DefIterator(Info.first), Location(Info.second),
1175
2.65M
        OriginalAccess(Info.first) {
1176
2.65M
    CurrentPair.first = nullptr;
1177
2.65M
1178
2.65M
    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1179
2.65M
    fillInCurrentPair();
1180
2.65M
  }
1181
1182
2.65M
  upward_defs_iterator() { CurrentPair.first = nullptr; }
1183
1184
9.09M
  bool operator==(const upward_defs_iterator &Other) const {
1185
9.09M
    return DefIterator == Other.DefIterator;
1186
9.09M
  }
1187
1188
6.43M
  BaseT::iterator::reference operator*() const {
1189
6.43M
    assert(DefIterator != OriginalAccess->defs_end() &&
1190
6.43M
           "Tried to access past the end of our iterator");
1191
6.43M
    return CurrentPair;
1192
6.43M
  }
1193
1194
  using BaseT::operator++;
1195
6.43M
  upward_defs_iterator &operator++() {
1196
6.43M
    assert(DefIterator != OriginalAccess->defs_end() &&
1197
6.43M
           "Tried to access past the end of the iterator");
1198
6.43M
    ++DefIterator;
1199
6.43M
    if (DefIterator != OriginalAccess->defs_end())
1200
3.77M
      fillInCurrentPair();
1201
6.43M
    return *this;
1202
6.43M
  }
1203
1204
0
  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1205
1206
private:
1207
6.43M
  void fillInCurrentPair() {
1208
6.43M
    CurrentPair.first = *DefIterator;
1209
6.43M
    if (WalkingPhi && Location.Ptr) {
1210
6.39M
      PHITransAddr Translator(
1211
6.39M
          const_cast<Value *>(Location.Ptr),
1212
6.39M
          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1213
6.39M
      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1214
6.39M
                                        DefIterator.getPhiArgBlock(), nullptr,
1215
6.39M
                                        false))
1216
0
        if (Translator.getAddr() != Location.Ptr) {
1217
0
          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
1218
0
          return;
1219
0
        }
1220
6.43M
    }
1221
6.43M
    CurrentPair.second = Location;
1222
6.43M
  }
1223
1224
  MemoryAccessPair CurrentPair;
1225
  memoryaccess_def_iterator DefIterator;
1226
  MemoryLocation Location;
1227
  MemoryAccess *OriginalAccess = nullptr;
1228
  bool WalkingPhi = false;
1229
};
1230
1231
2.65M
inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
1232
2.65M
  return upward_defs_iterator(Pair);
1233
2.65M
}
1234
1235
2.65M
inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1236
1237
inline iterator_range<upward_defs_iterator>
1238
upward_defs(const MemoryAccessPair &Pair) {
1239
  return make_range(upward_defs_begin(Pair), upward_defs_end());
1240
}
1241
1242
/// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1243
/// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1244
/// comparing against a null def_chain_iterator, this will compare equal only
1245
/// after walking said Phi/liveOnEntry.
1246
///
1247
/// The UseOptimizedChain flag specifies whether to walk the clobbering
1248
/// access chain, or all the accesses.
1249
///
1250
/// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1251
/// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1252
/// a phi node.  The optimized chain walks the clobbering access of a store.
1253
/// So if you are just trying to find, given a store, what the next
1254
/// thing that would clobber the same memory is, you want the optimized chain.
1255
template <class T, bool UseOptimizedChain = false>
1256
struct def_chain_iterator
1257
    : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1258
                                  std::forward_iterator_tag, MemoryAccess *> {
1259
  def_chain_iterator() : MA(nullptr) {}
1260
9.31M
  def_chain_iterator(T MA) : MA(MA) {}
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::def_chain_iterator(llvm::MemoryAccess const*)
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::def_chain_iterator(llvm::MemoryAccess*)
Line
Count
Source
1260
9.31M
  def_chain_iterator(T MA) : MA(MA) {}
1261
1262
8.60M
  T operator*() const { return MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator*() const
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator*() const
Line
Count
Source
1262
8.60M
  T operator*() const { return MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator*() const
1263
1264
6.60M
  def_chain_iterator &operator++() {
1265
6.60M
    // N.B. liveOnEntry has a null defining access.
1266
6.60M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1267
3.95M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1268
0
        MA = MUD->getOptimized();
1269
3.95M
      else
1270
3.95M
        MA = MUD->getDefiningAccess();
1271
3.95M
    } else {
1272
2.65M
      MA = nullptr;
1273
2.65M
    }
1274
6.60M
1275
6.60M
    return *this;
1276
6.60M
  }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator++()
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator++()
Line
Count
Source
1264
6.60M
  def_chain_iterator &operator++() {
1265
6.60M
    // N.B. liveOnEntry has a null defining access.
1266
6.60M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1267
3.95M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1268
0
        MA = MUD->getOptimized();
1269
3.95M
      else
1270
3.95M
        MA = MUD->getDefiningAccess();
1271
3.95M
    } else {
1272
2.65M
      MA = nullptr;
1273
2.65M
    }
1274
6.60M
1275
6.60M
    return *this;
1276
6.60M
  }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator++()
1277
1278
11.2M
  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator==(llvm::def_chain_iterator<llvm::MemoryAccess const*, false> const&) const
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator==(llvm::def_chain_iterator<llvm::MemoryAccess*, false> const&) const
Line
Count
Source
1278
11.2M
  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator==(llvm::def_chain_iterator<llvm::MemoryAccess const*, true> const&) const
1279
1280
private:
1281
  T MA;
1282
};
1283
1284
template <class T>
1285
inline iterator_range<def_chain_iterator<T>>
1286
4.65M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1287
4.65M
#ifdef EXPENSIVE_CHECKS
1288
4.65M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1289
4.65M
         "UpTo isn't in the def chain!");
1290
4.65M
#endif
1291
4.65M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1292
4.65M
}
Unexecuted instantiation: llvm::iterator_range<llvm::def_chain_iterator<llvm::MemoryAccess const*, false> > llvm::def_chain<llvm::MemoryAccess const*>(llvm::MemoryAccess const*, llvm::MemoryAccess*)
llvm::iterator_range<llvm::def_chain_iterator<llvm::MemoryAccess*, false> > llvm::def_chain<llvm::MemoryAccess*>(llvm::MemoryAccess*, llvm::MemoryAccess*)
Line
Count
Source
1286
4.65M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1287
4.65M
#ifdef EXPENSIVE_CHECKS
1288
4.65M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1289
4.65M
         "UpTo isn't in the def chain!");
1290
4.65M
#endif
1291
4.65M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1292
4.65M
}
1293
1294
template <class T>
1295
0
inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1296
0
  return make_range(def_chain_iterator<T, true>(MA),
1297
0
                    def_chain_iterator<T, true>(nullptr));
1298
0
}
1299
1300
} // end namespace llvm
1301
1302
#endif // LLVM_ANALYSIS_MEMORYSSA_H