Coverage Report

Created: 2019-03-24 22:13

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