Coverage Report

Created: 2018-11-12 17:33

/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
457
  static bool classof(const Value *V) {
153
457
    unsigned ID = V->getValueID();
154
457
    return ID == MemoryUseVal || 
ID == MemoryPhiVal411
||
ID == MemoryDefVal130
;
155
457
  }
156
157
18.4M
  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
17
  AllAccessType::self_iterator getIterator() {
177
17
    return this->AllAccessType::getIterator();
178
17
  }
179
0
  AllAccessType::const_self_iterator getIterator() const {
180
0
    return this->AllAccessType::getIterator();
181
0
  }
182
19
  AllAccessType::reverse_self_iterator getReverseIterator() {
183
19
    return this->AllAccessType::getReverseIterator();
184
19
  }
185
0
  AllAccessType::const_reverse_self_iterator getReverseIterator() const {
186
0
    return this->AllAccessType::getReverseIterator();
187
0
  }
188
11
  DefsOnlyType::self_iterator getDefsIterator() {
189
11
    return this->DefsOnlyType::getIterator();
190
11
  }
191
0
  DefsOnlyType::const_self_iterator getDefsIterator() const {
192
0
    return this->DefsOnlyType::getIterator();
193
0
  }
194
33
  DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
195
33
    return this->DefsOnlyType::getReverseIterator();
196
33
  }
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
77
  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
6.04M
        Block(BB) {}
220
221
  // Use deleteValue() to delete a generic MemoryAccess.
222
6.04M
  ~MemoryAccess() = default;
223
224
private:
225
  BasicBlock *Block;
226
};
227
228
template <>
229
struct ilist_alloc_traits<MemoryAccess> {
230
5.59M
  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
11.2M
  Instruction *getMemoryInst() const { return MemoryInstruction; }
253
254
  /// Get the access that produces the memory state used by this Use.
255
9.60M
  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
256
257
10.0M
  static bool classof(const Value *MA) {
258
10.0M
    return MA->getValueID() == MemoryUseVal || 
MA->getValueID() == MemoryDefVal7.13M
;
259
10.0M
  }
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
5.35M
        MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
287
5.35M
    setDefiningAccess(DMA);
288
5.35M
  }
289
290
  // Use deleteValue() to delete a generic MemoryUseOrDef.
291
5.35M
  ~MemoryUseOrDef() = default;
292
293
1.81M
  void setOptimizedAccessType(Optional<AliasResult> AR) {
294
1.81M
    OptimizedAccessAlias = AR;
295
1.81M
  }
296
297
  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
298
12.1M
                         Optional<AliasResult> AR = MayAlias) {
299
12.1M
    if (!Optimized) {
300
10.3M
      setOperand(0, DMA);
301
10.3M
      return;
302
10.3M
    }
303
1.77M
    setOptimized(DMA);
304
1.77M
    setOptimizedAccessType(AR);
305
1.77M
  }
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
1.80M
                       /*NumOperands=*/1) {}
324
325
  // allocate space for exactly one operand
326
1.80M
  void *operator new(size_t s) { return User::operator new(s, 1); }
327
328
26.5M
  static bool classof(const Value *MA) {
329
26.5M
    return MA->getValueID() == MemoryUseVal;
330
26.5M
  }
331
332
  void print(raw_ostream &OS) const;
333
334
2.42M
  void setOptimized(MemoryAccess *DMA) {
335
2.42M
    OptimizedID = DMA->getID();
336
2.42M
    setOperand(0, DMA);
337
2.42M
  }
338
339
942k
  bool isOptimized() const {
340
942k
    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
341
942k
  }
342
343
292k
  MemoryAccess *getOptimized() const {
344
292k
    return getDefiningAccess();
345
292k
  }
346
347
180
  void resetOptimized() {
348
180
    OptimizedID = INVALID_MEMORYACCESS_ID;
349
180
  }
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
3.55M
        ID(Ver) {}
384
385
  // allocate space for exactly two operands
386
3.55M
  void *operator new(size_t s) { return User::operator new(s, 2); }
387
388
20.8M
  static bool classof(const Value *MA) {
389
20.8M
    return MA->getValueID() == MemoryDefVal;
390
20.8M
  }
391
392
6.12k
  void setOptimized(MemoryAccess *MA) {
393
6.12k
    setOperand(1, MA);
394
6.12k
    OptimizedID = MA->getID();
395
6.12k
  }
396
397
6.41k
  MemoryAccess *getOptimized() const {
398
6.41k
    return cast_or_null<MemoryAccess>(getOperand(1));
399
6.41k
  }
400
401
6.39k
  bool isOptimized() const {
402
6.39k
    return getOptimized() && 
OptimizedID == getOptimized()->getID()22
;
403
6.39k
  }
404
405
14.7k
  void resetOptimized() {
406
14.7k
    OptimizedID = INVALID_MEMORYACCESS_ID;
407
14.7k
  }
408
409
  void print(raw_ostream &OS) const;
410
411
1.60M
  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
19.9M
  static Use *op_begin(MemoryUseOrDef *MUD) {
427
19.9M
    if (auto *MU = dyn_cast<MemoryUse>(MUD))
428
8.43M
      return OperandTraits<MemoryUse>::op_begin(MU);
429
11.5M
    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
430
11.5M
  }
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
694k
  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
694k
        ReservedSpace(NumPreds) {
489
694k
    allocHungoffUses(ReservedSpace);
490
694k
  }
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
1.77M
  block_iterator block_begin() {
498
1.77M
    auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace);
499
1.77M
    return reinterpret_cast<block_iterator>(Ref + 1);
500
1.77M
  }
501
502
3.62M
  const_block_iterator block_begin() const {
503
3.62M
    const auto *Ref =
504
3.62M
        reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace);
505
3.62M
    return reinterpret_cast<const_block_iterator>(Ref + 1);
506
3.62M
  }
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
683
  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
3.64M
  unsigned getNumIncomingValues() const { return getNumOperands(); }
528
529
  /// Return incoming value number x
530
3.64M
  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
531
1.77M
  void setIncomingValue(unsigned I, MemoryAccess *V) {
532
1.77M
    assert(V && "PHI node got a null value!");
533
1.77M
    setOperand(I, V);
534
1.77M
  }
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
3.62M
  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
541
542
  /// Return incoming basic block corresponding
543
  /// to an operand of the PHI.
544
860
  BasicBlock *getIncomingBlock(const Use &U) const {
545
860
    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
546
860
    return getIncomingBlock(unsigned(&U - op_begin()));
547
860
  }
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
1.77M
  void setIncomingBlock(unsigned I, BasicBlock *BB) {
556
1.77M
    assert(BB && "PHI node got a null basic block!");
557
1.77M
    block_begin()[I] = BB;
558
1.77M
  }
559
560
  /// Add an incoming value to the end of the PHI list
561
1.77M
  void addIncoming(MemoryAccess *V, BasicBlock *BB) {
562
1.77M
    if (getNumOperands() == ReservedSpace)
563
969k
      growOperands(); // Get more space!
564
1.77M
    // Initialize some new operands.
565
1.77M
    setNumHungOffUseOperands(getNumOperands() + 1);
566
1.77M
    setIncomingValue(getNumOperands() - 1, V);
567
1.77M
    setIncomingBlock(getNumOperands() - 1, BB);
568
1.77M
  }
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
73
  int getBasicBlockIndex(const BasicBlock *BB) const {
573
87
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I14
)
574
87
      if (block_begin()[I] == BB)
575
73
        return I;
576
73
    
return -10
;
577
73
  }
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
83
  void unorderedDeleteIncoming(unsigned I) {
587
83
    unsigned E = getNumOperands();
588
83
    assert(I < E && "Cannot remove out of bounds Phi entry.");
589
83
    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
590
83
    // itself should be deleted.
591
83
    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
592
83
                     "at least 2 values.");
593
83
    setIncomingValue(I, getIncomingValue(E - 1));
594
83
    setIncomingBlock(I, block_begin()[E - 1]);
595
83
    setOperand(E - 1, nullptr);
596
83
    block_begin()[E - 1] = nullptr;
597
83
    setNumHungOffUseOperands(getNumOperands() - 1);
598
83
  }
599
600
  // After deleting entries that satisfy Pred, remaining entries may have
601
  // changed order.
602
83
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
274
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I191
)
604
191
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
83
        unorderedDeleteIncoming(I);
606
83
        E = getNumOperands();
607
83
        --I;
608
83
      }
609
83
    assert(getNumOperands() >= 1 &&
610
83
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
83
  }
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
26
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
78
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I52
)
604
52
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
26
        unorderedDeleteIncoming(I);
606
26
        E = getNumOperands();
607
26
        --I;
608
26
      }
609
26
    assert(getNumOperands() >= 1 &&
610
26
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
26
  }
Unexecuted instantiation: MemorySSAUpdater.cpp:void llvm::MemoryPhi::unorderedDeleteIncomingIf<llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(llvm::BasicBlock*, llvm::BasicBlock*)::$_0>(llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween(llvm::BasicBlock*, llvm::BasicBlock*)::$_0&&)
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
26
  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
615
26
    unorderedDeleteIncomingIf(
616
52
        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
617
26
  }
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
18.2M
  static bool classof(const Value *V) {
627
18.2M
    return V->getValueID() == MemoryPhiVal;
628
18.2M
  }
629
630
  void print(raw_ostream &OS) const;
631
632
1.76M
  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
694k
  void allocHungoffUses(unsigned N) {
641
694k
    User::allocHungoffUses(N, /* IsPhi */ true);
642
694k
  }
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
969k
  void growOperands() {
652
969k
    unsigned E = getNumOperands();
653
969k
    // 2 op PHI nodes are VERY common, so reserve at least enough for that.
654
969k
    ReservedSpace = std::max(E + E / 2, 2u);
655
969k
    growHungoffUses(ReservedSpace, /* IsPhi */ true);
656
969k
  }
657
658
  static void deleteMe(DerivedUser *Self);
659
};
660
661
3.37M
inline unsigned MemoryAccess::getID() const {
662
3.37M
  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
663
3.37M
         "only memory defs and phis have ids");
664
3.37M
  if (const auto *MD = dyn_cast<MemoryDef>(this))
665
1.60M
    return MD->getID();
666
1.76M
  return cast<MemoryPhi>(this)->getID();
667
1.76M
}
668
669
948k
inline bool MemoryUseOrDef::isOptimized() const {
670
948k
  if (const auto *MD = dyn_cast<MemoryDef>(this))
671
6.12k
    return MD->isOptimized();
672
942k
  return cast<MemoryUse>(this)->isOptimized();
673
942k
}
674
675
292k
inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
676
292k
  if (const auto *MD = dyn_cast<MemoryDef>(this))
677
2
    return MD->getOptimized();
678
292k
  return cast<MemoryUse>(this)->getOptimized();
679
292k
}
680
681
2.42M
inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
682
2.42M
  if (auto *MD = dyn_cast<MemoryDef>(this))
683
6.12k
    MD->setOptimized(MA);
684
2.42M
  else
685
2.42M
    cast<MemoryUse>(this)->setOptimized(MA);
686
2.42M
}
687
688
14.8k
inline void MemoryUseOrDef::resetOptimized() {
689
14.8k
  if (auto *MD = dyn_cast<MemoryDef>(this))
690
14.6k
    MD->resetOptimized();
691
179
  else
692
179
    cast<MemoryUse>(this)->resetOptimized();
693
14.8k
}
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
1.98M
  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
712
1.98M
    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
713
1.98M
  }
714
715
3.56k
  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
716
3.56k
    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
717
3.56k
  }
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
6.10M
  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
730
6.10M
    return MA == LiveOnEntryDef.get();
731
6.10M
  }
732
733
1.31M
  inline MemoryAccess *getLiveOnEntryDef() const {
734
1.31M
    return LiveOnEntryDef.get();
735
1.31M
  }
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.4k
  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
750
45.4k
    return getWritableBlockAccesses(BB);
751
45.4k
  }
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
1.33M
  const DefsList *getBlockDefs(const BasicBlock *BB) const {
758
1.33M
    return getWritableBlockDefs(BB);
759
1.33M
  }
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
2.82M
  AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
798
2.82M
    auto It = PerBlockAccesses.find(BB);
799
2.82M
    return It == PerBlockAccesses.end() ? 
nullptr607k
:
It->second.get()2.21M
;
800
2.82M
  }
801
802
  // This is used by the use optimizer and updater.
803
1.34M
  DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
804
1.34M
    auto It = PerBlockDefs.find(BB);
805
1.34M
    return It == PerBlockDefs.end() ? 
nullptr619k
:
It->second.get()722k
;
806
1.34M
  }
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
200
    Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
925
926
235
    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
457k
  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
458k
  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
947k
  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1011
947k
    MemoryAccess *MA = MSSA->getMemoryAccess(I);
1012
947k
    assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
1013
947k
    return getClobberingMemoryAccess(MA);
1014
947k
  }
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
882
  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
1.53M
  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1076
5.18M
  memoryaccess_def_iterator_base() = default;
1077
1078
8.82M
  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1079
8.82M
    return Access == Other.Access && 
(3.07M
!Access3.07M
||
ArgNo == Other.ArgNo0
);
1080
8.82M
  }
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
3.62M
  BasicBlock *getPhiArgBlock() const {
1089
3.62M
    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1090
3.62M
    assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1091
3.62M
    return MP->getIncomingBlock(ArgNo);
1092
3.62M
  }
1093
1094
3.64M
  typename BaseT::iterator::pointer operator*() const {
1095
3.64M
    assert(Access && "Tried to access past the end of our iterator");
1096
3.64M
    // Go to the first argument for phis, and the defining access for everything
1097
3.64M
    // else.
1098
3.64M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1099
3.64M
      return MP->getIncomingValue(ArgNo);
1100
0
    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1101
0
  }
1102
1103
  using BaseT::operator++;
1104
3.64M
  memoryaccess_def_iterator &operator++() {
1105
3.64M
    assert(Access && "Hit end of iterator");
1106
3.64M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1107
3.64M
      if (++ArgNo >= MP->getNumIncomingValues()) {
1108
1.53M
        ArgNo = 0;
1109
1.53M
        Access = nullptr;
1110
1.53M
      }
1111
3.64M
    } else {
1112
0
      Access = nullptr;
1113
0
    }
1114
3.64M
    return *this;
1115
3.64M
  }
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
3.64M
inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1131
3.64M
  return memoryaccess_def_iterator();
1132
3.64M
}
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
1.53M
        OriginalAccess(Info.first) {
1176
1.53M
    CurrentPair.first = nullptr;
1177
1.53M
1178
1.53M
    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1179
1.53M
    fillInCurrentPair();
1180
1.53M
  }
1181
1182
1.53M
  upward_defs_iterator() { CurrentPair.first = nullptr; }
1183
1184
5.18M
  bool operator==(const upward_defs_iterator &Other) const {
1185
5.18M
    return DefIterator == Other.DefIterator;
1186
5.18M
  }
1187
1188
3.64M
  BaseT::iterator::reference operator*() const {
1189
3.64M
    assert(DefIterator != OriginalAccess->defs_end() &&
1190
3.64M
           "Tried to access past the end of our iterator");
1191
3.64M
    return CurrentPair;
1192
3.64M
  }
1193
1194
  using BaseT::operator++;
1195
3.64M
  upward_defs_iterator &operator++() {
1196
3.64M
    assert(DefIterator != OriginalAccess->defs_end() &&
1197
3.64M
           "Tried to access past the end of the iterator");
1198
3.64M
    ++DefIterator;
1199
3.64M
    if (DefIterator != OriginalAccess->defs_end())
1200
2.10M
      fillInCurrentPair();
1201
3.64M
    return *this;
1202
3.64M
  }
1203
1204
0
  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1205
1206
private:
1207
3.64M
  void fillInCurrentPair() {
1208
3.64M
    CurrentPair.first = *DefIterator;
1209
3.64M
    if (WalkingPhi && Location.Ptr) {
1210
3.62M
      PHITransAddr Translator(
1211
3.62M
          const_cast<Value *>(Location.Ptr),
1212
3.62M
          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1213
3.62M
      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1214
3.62M
                                        DefIterator.getPhiArgBlock(), nullptr,
1215
3.62M
                                        false))
1216
0
        if (Translator.getAddr() != Location.Ptr) {
1217
0
          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
1218
0
          return;
1219
0
        }
1220
3.64M
    }
1221
3.64M
    CurrentPair.second = Location;
1222
3.64M
  }
1223
1224
  MemoryAccessPair CurrentPair;
1225
  memoryaccess_def_iterator DefIterator;
1226
  MemoryLocation Location;
1227
  MemoryAccess *OriginalAccess = nullptr;
1228
  bool WalkingPhi = false;
1229
};
1230
1231
1.53M
inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
1232
1.53M
  return upward_defs_iterator(Pair);
1233
1.53M
}
1234
1235
1.53M
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
5.47M
  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
5.47M
  def_chain_iterator(T MA) : MA(MA) {}
1261
1262
4.51M
  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
4.51M
  T operator*() const { return MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator*() const
1263
1264
3.31M
  def_chain_iterator &operator++() {
1265
3.31M
    // N.B. liveOnEntry has a null defining access.
1266
3.31M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1267
1.77M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1268
0
        MA = MUD->getOptimized();
1269
1.77M
      else
1270
1.77M
        MA = MUD->getDefiningAccess();
1271
1.77M
    } else {
1272
1.53M
      MA = nullptr;
1273
1.53M
    }
1274
3.31M
1275
3.31M
    return *this;
1276
3.31M
  }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator++()
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator++()
Line
Count
Source
1264
3.31M
  def_chain_iterator &operator++() {
1265
3.31M
    // N.B. liveOnEntry has a null defining access.
1266
3.31M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1267
1.77M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1268
0
        MA = MUD->getOptimized();
1269
1.77M
      else
1270
1.77M
        MA = MUD->getDefiningAccess();
1271
1.77M
    } else {
1272
1.53M
      MA = nullptr;
1273
1.53M
    }
1274
3.31M
1275
3.31M
    return *this;
1276
3.31M
  }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator++()
1277
1278
6.04M
  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
6.04M
  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
2.73M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1287
2.73M
#ifdef EXPENSIVE_CHECKS
1288
2.73M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1289
2.73M
         "UpTo isn't in the def chain!");
1290
2.73M
#endif
1291
2.73M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1292
2.73M
}
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
2.73M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1287
2.73M
#ifdef EXPENSIVE_CHECKS
1288
2.73M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1289
2.73M
         "UpTo isn't in the def chain!");
1290
2.73M
#endif
1291
2.73M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1292
2.73M
}
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