Coverage Report

Created: 2019-07-24 05:18

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