Coverage Report

Created: 2019-02-20 00:17

/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
847
  static bool classof(const Value *V) {
152
847
    unsigned ID = V->getValueID();
153
847
    return ID == MemoryUseVal || 
ID == MemoryPhiVal750
||
ID == MemoryDefVal299
;
154
847
  }
155
156
31.4M
  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
62
  AllAccessType::self_iterator getIterator() {
176
62
    return this->AllAccessType::getIterator();
177
62
  }
178
0
  AllAccessType::const_self_iterator getIterator() const {
179
0
    return this->AllAccessType::getIterator();
180
0
  }
181
32
  AllAccessType::reverse_self_iterator getReverseIterator() {
182
32
    return this->AllAccessType::getReverseIterator();
183
32
  }
184
0
  AllAccessType::const_reverse_self_iterator getReverseIterator() const {
185
0
    return this->AllAccessType::getReverseIterator();
186
0
  }
187
32
  DefsOnlyType::self_iterator getDefsIterator() {
188
32
    return this->DefsOnlyType::getIterator();
189
32
  }
190
0
  DefsOnlyType::const_self_iterator getDefsIterator() const {
191
0
    return this->DefsOnlyType::getIterator();
192
0
  }
193
63
  DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
194
63
    return this->DefsOnlyType::getReverseIterator();
195
63
  }
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
170
  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.5M
        Block(BB) {}
219
220
  // Use deleteValue() to delete a generic MemoryAccess.
221
10.5M
  ~MemoryAccess() = default;
222
223
private:
224
  BasicBlock *Block;
225
};
226
227
template <>
228
struct ilist_alloc_traits<MemoryAccess> {
229
9.81M
  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.5M
  Instruction *getMemoryInst() const { return MemoryInstruction; }
252
253
  /// Get the access that produces the memory state used by this Use.
254
16.9M
  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
255
256
18.1M
  static bool classof(const Value *MA) {
257
18.1M
    return MA->getValueID() == MemoryUseVal || 
MA->getValueID() == MemoryDefVal13.3M
;
258
18.1M
  }
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.29M
        MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
286
9.29M
    setDefiningAccess(DMA);
287
9.29M
  }
288
289
  // Use deleteValue() to delete a generic MemoryUseOrDef.
290
9.29M
  ~MemoryUseOrDef() = default;
291
292
3.11M
  void setOptimizedAccessType(Optional<AliasResult> AR) {
293
3.11M
    OptimizedAccessAlias = AR;
294
3.11M
  }
295
296
  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
297
21.0M
                         Optional<AliasResult> AR = MayAlias) {
298
21.0M
    if (!Optimized) {
299
17.9M
      setOperand(0, DMA);
300
17.9M
      return;
301
17.9M
    }
302
3.05M
    setOptimized(DMA);
303
3.05M
    setOptimizedAccessType(AR);
304
3.05M
  }
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.10M
                       /*NumOperands=*/1) {}
323
324
  // allocate space for exactly one operand
325
3.10M
  void *operator new(size_t s) { return User::operator new(s, 1); }
326
327
46.1M
  static bool classof(const Value *MA) {
328
46.1M
    return MA->getValueID() == MemoryUseVal;
329
46.1M
  }
330
331
  void print(raw_ostream &OS) const;
332
333
4.17M
  void setOptimized(MemoryAccess *DMA) {
334
4.17M
    OptimizedID = DMA->getID();
335
4.17M
    setOperand(0, DMA);
336
4.17M
  }
337
338
1.41M
  bool isOptimized() const {
339
1.41M
    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
340
1.41M
  }
341
342
289k
  MemoryAccess *getOptimized() const {
343
289k
    return getDefiningAccess();
344
289k
  }
345
346
53
  void resetOptimized() {
347
53
    OptimizedID = INVALID_MEMORYACCESS_ID;
348
53
  }
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.18M
        ID(Ver) {}
383
384
  // allocate space for exactly two operands
385
6.18M
  void *operator new(size_t s) { return User::operator new(s, 2); }
386
387
36.5M
  static bool classof(const Value *MA) {
388
36.5M
    return MA->getValueID() == MemoryDefVal;
389
36.5M
  }
390
391
6.21k
  void setOptimized(MemoryAccess *MA) {
392
6.21k
    setOperand(1, MA);
393
6.21k
    OptimizedID = MA->getID();
394
6.21k
  }
395
396
6.59k
  MemoryAccess *getOptimized() const {
397
6.59k
    return cast_or_null<MemoryAccess>(getOperand(1));
398
6.59k
  }
399
400
6.51k
  bool isOptimized() const {
401
6.51k
    return getOptimized() && 
OptimizedID == getOptimized()->getID()48
;
402
6.51k
  }
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.58M
  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.8M
  static Use *op_begin(MemoryUseOrDef *MUD) {
427
34.8M
    if (auto *MU = dyn_cast<MemoryUse>(MUD))
428
13.7M
      return OperandTraits<MemoryUse>::op_begin(MU);
429
21.1M
    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
430
21.1M
  }
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.19M
  block_iterator block_begin() {
498
3.19M
    auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace);
499
3.19M
    return reinterpret_cast<block_iterator>(Ref + 1);
500
3.19M
  }
501
502
6.41M
  const_block_iterator block_begin() const {
503
6.41M
    const auto *Ref =
504
6.41M
        reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace);
505
6.41M
    return reinterpret_cast<const_block_iterator>(Ref + 1);
506
6.41M
  }
507
508
10
  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.45M
  unsigned getNumIncomingValues() const { return getNumOperands(); }
528
529
  /// Return incoming value number x
530
6.45M
  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
531
3.19M
  void setIncomingValue(unsigned I, MemoryAccess *V) {
532
3.19M
    assert(V && "PHI node got a null value!");
533
3.19M
    setOperand(I, V);
534
3.19M
  }
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.41M
  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.03k
  BasicBlock *getIncomingBlock(const Use &U) const {
545
1.03k
    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
546
1.03k
    return getIncomingBlock(unsigned(&U - op_begin()));
547
1.03k
  }
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.19M
  void setIncomingBlock(unsigned I, BasicBlock *BB) {
556
3.19M
    assert(BB && "PHI node got a null basic block!");
557
3.19M
    block_begin()[I] = BB;
558
3.19M
  }
559
560
  /// Add an incoming value to the end of the PHI list
561
3.19M
  void addIncoming(MemoryAccess *V, BasicBlock *BB) {
562
3.19M
    if (getNumOperands() == ReservedSpace)
563
1.72M
      growOperands(); // Get more space!
564
3.19M
    // Initialize some new operands.
565
3.19M
    setNumHungOffUseOperands(getNumOperands() + 1);
566
3.19M
    setIncomingValue(getNumOperands() - 1, V);
567
3.19M
    setIncomingBlock(getNumOperands() - 1, BB);
568
3.19M
  }
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
180
  int getBasicBlockIndex(const BasicBlock *BB) const {
573
220
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I40
)
574
220
      if (block_begin()[I] == BB)
575
180
        return I;
576
180
    
return -10
;
577
180
  }
578
579
18
  MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
580
18
    int Idx = getBasicBlockIndex(BB);
581
18
    assert(Idx >= 0 && "Invalid basic block argument!");
582
18
    return getIncomingValue(Idx);
583
18
  }
584
585
  // After deleting incoming position I, the order of incoming may be changed.
586
208
  void unorderedDeleteIncoming(unsigned I) {
587
208
    unsigned E = getNumOperands();
588
208
    assert(I < E && "Cannot remove out of bounds Phi entry.");
589
208
    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
590
208
    // itself should be deleted.
591
208
    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
592
208
                     "at least 2 values.");
593
208
    setIncomingValue(I, getIncomingValue(E - 1));
594
208
    setIncomingBlock(I, block_begin()[E - 1]);
595
208
    setOperand(E - 1, nullptr);
596
208
    block_begin()[E - 1] = nullptr;
597
208
    setNumHungOffUseOperands(getNumOperands() - 1);
598
208
  }
599
600
  // After deleting entries that satisfy Pred, remaining entries may have
601
  // changed order.
602
210
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
677
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I467
)
604
467
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
208
        unorderedDeleteIncoming(I);
606
208
        E = getNumOperands();
607
208
        --I;
608
208
      }
609
210
    assert(getNumOperands() >= 1 &&
610
210
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
210
  }
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
106
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
332
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I226
)
604
226
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
106
        unorderedDeleteIncoming(I);
606
106
        E = getNumOperands();
607
106
        --I;
608
106
      }
609
106
    assert(getNumOperands() >= 1 &&
610
106
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
106
  }
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
98
  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
603
323
    for (unsigned I = 0, E = getNumOperands(); I != E; 
++I225
)
604
225
      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
605
100
        unorderedDeleteIncoming(I);
606
100
        E = getNumOperands();
607
100
        --I;
608
100
      }
609
98
    assert(getNumOperands() >= 1 &&
610
98
           "Cannot remove all incoming blocks in a MemoryPhi.");
611
98
  }
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
106
  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
615
106
    unorderedDeleteIncomingIf(
616
226
        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
617
106
  }
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.1M
  static bool classof(const Value *V) {
627
32.1M
    return V->getValueID() == MemoryPhiVal;
628
32.1M
  }
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.72M
  void growOperands() {
652
1.72M
    unsigned E = getNumOperands();
653
1.72M
    // 2 op PHI nodes are VERY common, so reserve at least enough for that.
654
1.72M
    ReservedSpace = std::max(E + E / 2, 2u);
655
1.72M
    growHungoffUses(ReservedSpace, /* IsPhi */ true);
656
1.72M
  }
657
658
  static void deleteMe(DerivedUser *Self);
659
};
660
661
5.58M
inline unsigned MemoryAccess::getID() const {
662
5.58M
  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
663
5.58M
         "only memory defs and phis have ids");
664
5.58M
  if (const auto *MD = dyn_cast<MemoryDef>(this))
665
2.58M
    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.24k
    return MD->isOptimized();
672
1.41M
  return cast<MemoryUse>(this)->isOptimized();
673
1.41M
}
674
675
290k
inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
676
290k
  if (const auto *MD = dyn_cast<MemoryDef>(this))
677
32
    return MD->getOptimized();
678
289k
  return cast<MemoryUse>(this)->getOptimized();
679
289k
}
680
681
4.17M
inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
682
4.17M
  if (auto *MD = dyn_cast<MemoryDef>(this))
683
6.21k
    MD->setOptimized(MA);
684
4.17M
  else
685
4.17M
    cast<MemoryUse>(this)->setOptimized(MA);
686
4.17M
}
687
688
14.8k
inline void MemoryUseOrDef::resetOptimized() {
689
14.8k
  if (auto *MD = dyn_cast<MemoryDef>(this))
690
14.7k
    MD->resetOptimized();
691
52
  else
692
52
    cast<MemoryUse>(this)->resetOptimized();
693
14.8k
}
694
695
template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
696
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
697
698
/// Encapsulates MemorySSA, including all data associated with memory
699
/// accesses.
700
class MemorySSA {
701
public:
702
  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
703
  ~MemorySSA();
704
705
  MemorySSAWalker *getWalker();
706
  MemorySSAWalker *getSkipSelfWalker();
707
708
  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
709
  /// access associated with it. If passed a basic block gets the memory phi
710
  /// node that exists for that block, if there is one. Otherwise, this will get
711
  /// a MemoryUseOrDef.
712
2.45M
  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
713
2.45M
    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
714
2.45M
  }
715
716
5.24k
  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
717
5.24k
    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
718
5.24k
  }
719
720
  void dump() const;
721
  void print(raw_ostream &) const;
722
723
  /// Return true if \p MA represents the live on entry value
724
  ///
725
  /// Loads and stores from pointer arguments and other global values may be
726
  /// defined by memory operations that do not occur in the current function, so
727
  /// they may be live on entry to the function. MemorySSA represents such
728
  /// memory state by the live on entry definition, which is guaranteed to occur
729
  /// before any other memory access in the function.
730
11.1M
  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
731
11.1M
    return MA == LiveOnEntryDef.get();
732
11.1M
  }
733
734
2.15M
  inline MemoryAccess *getLiveOnEntryDef() const {
735
2.15M
    return LiveOnEntryDef.get();
736
2.15M
  }
737
738
  // Sadly, iplists, by default, owns and deletes pointers added to the
739
  // list. It's not currently possible to have two iplists for the same type,
740
  // where one owns the pointers, and one does not. This is because the traits
741
  // are per-type, not per-tag.  If this ever changes, we should make the
742
  // DefList an iplist.
743
  using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
744
  using DefsList =
745
      simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
746
747
  /// Return the list of MemoryAccess's for a given basic block.
748
  ///
749
  /// This list is not modifiable by the user.
750
46.8k
  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
751
46.8k
    return getWritableBlockAccesses(BB);
752
46.8k
  }
753
754
  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
755
  /// block.
756
  ///
757
  /// This list is not modifiable by the user.
758
2.52M
  const DefsList *getBlockDefs(const BasicBlock *BB) const {
759
2.52M
    return getWritableBlockDefs(BB);
760
2.52M
  }
761
762
  /// Given two memory accesses in the same basic block, determine
763
  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
764
  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
765
766
  /// Given two memory accesses in potentially different blocks,
767
  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
768
  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
769
770
  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
771
  /// dominates Use \p B.
772
  bool dominates(const MemoryAccess *A, const Use &B) const;
773
774
  /// Verify that MemorySSA is self consistent (IE definitions dominate
775
  /// all uses, uses appear in the right places).  This is used by unit tests.
776
  void verifyMemorySSA() const;
777
778
  /// Used in various insertion functions to specify whether we are talking
779
  /// about the beginning or end of a block.
780
  enum InsertionPlace { Beginning, End };
781
782
protected:
783
  // Used by Memory SSA annotater, dumpers, and wrapper pass
784
  friend class MemorySSAAnnotatedWriter;
785
  friend class MemorySSAPrinterLegacyPass;
786
  friend class MemorySSAUpdater;
787
788
  void verifyDefUses(Function &F) const;
789
  void verifyDomination(Function &F) const;
790
  void verifyOrdering(Function &F) const;
791
  void verifyDominationNumbers(const Function &F) const;
792
793
  // This is used by the use optimizer and updater.
794
4.95M
  AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
795
4.95M
    auto It = PerBlockAccesses.find(BB);
796
4.95M
    return It == PerBlockAccesses.end() ? 
nullptr1.20M
:
It->second.get()3.75M
;
797
4.95M
  }
798
799
  // This is used by the use optimizer and updater.
800
2.53M
  DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
801
2.53M
    auto It = PerBlockDefs.find(BB);
802
2.53M
    return It == PerBlockDefs.end() ? 
nullptr1.31M
:
It->second.get()1.21M
;
803
2.53M
  }
804
805
  // These is used by the updater to perform various internal MemorySSA
806
  // machinsations.  They do not always leave the IR in a correct state, and
807
  // relies on the updater to fixup what it breaks, so it is not public.
808
809
  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
810
  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
811
812
  // Rename the dominator tree branch rooted at BB.
813
  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
814
13
                  SmallPtrSetImpl<BasicBlock *> &Visited) {
815
13
    renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
816
13
  }
817
818
  void removeFromLookups(MemoryAccess *);
819
  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
820
  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
821
                               InsertionPlace);
822
  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
823
                             AccessList::iterator);
824
  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
825
                                      const MemoryUseOrDef *Template = nullptr);
826
827
private:
828
  class ClobberWalkerBase;
829
  class CachingWalker;
830
  class SkipSelfWalker;
831
  class OptimizeUses;
832
833
  CachingWalker *getWalkerImpl();
834
  void buildMemorySSA();
835
  void optimizeUses();
836
837
  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
838
  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
839
840
  using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
841
  using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
842
843
  void
844
  determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
845
  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
846
  bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
847
  MemoryPhi *createMemoryPhi(BasicBlock *BB);
848
  MemoryUseOrDef *createNewAccess(Instruction *,
849
                                  const MemoryUseOrDef *Template = nullptr);
850
  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
851
  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
852
  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
853
  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
854
  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
855
                  SmallPtrSetImpl<BasicBlock *> &Visited,
856
                  bool SkipVisited = false, bool RenameAllUses = false);
857
  AccessList *getOrCreateAccessList(const BasicBlock *);
858
  DefsList *getOrCreateDefsList(const BasicBlock *);
859
  void renumberBlock(const BasicBlock *) const;
860
  AliasAnalysis *AA;
861
  DominatorTree *DT;
862
  Function &F;
863
864
  // Memory SSA mappings
865
  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
866
867
  // These two mappings contain the main block to access/def mappings for
868
  // MemorySSA. The list contained in PerBlockAccesses really owns all the
869
  // MemoryAccesses.
870
  // Both maps maintain the invariant that if a block is found in them, the
871
  // corresponding list is not empty, and if a block is not found in them, the
872
  // corresponding list is empty.
873
  AccessMap PerBlockAccesses;
874
  DefsMap PerBlockDefs;
875
  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
876
877
  // Domination mappings
878
  // Note that the numbering is local to a block, even though the map is
879
  // global.
880
  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
881
  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
882
883
  // Memory SSA building info
884
  std::unique_ptr<ClobberWalkerBase> WalkerBase;
885
  std::unique_ptr<CachingWalker> Walker;
886
  std::unique_ptr<SkipSelfWalker> SkipWalker;
887
  unsigned NextID;
888
};
889
890
// Internal MemorySSA utils, for use by MemorySSA classes and walkers
891
class MemorySSAUtil {
892
protected:
893
  friend class GVNHoist;
894
  friend class MemorySSAWalker;
895
896
  // This function should not be used by new passes.
897
  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
898
                                  AliasAnalysis &AA);
899
};
900
901
// This pass does eager building and then printing of MemorySSA. It is used by
902
// the tests to be able to build, dump, and verify Memory SSA.
903
class MemorySSAPrinterLegacyPass : public FunctionPass {
904
public:
905
  MemorySSAPrinterLegacyPass();
906
907
  bool runOnFunction(Function &) override;
908
  void getAnalysisUsage(AnalysisUsage &AU) const override;
909
910
  static char ID;
911
};
912
913
/// An analysis that produces \c MemorySSA for a function.
914
///
915
class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
916
  friend AnalysisInfoMixin<MemorySSAAnalysis>;
917
918
  static AnalysisKey Key;
919
920
public:
921
  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
922
  // pointers after construction.  Use a wrapper class instead of plain
923
  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
924
  struct Result {
925
300
    Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
926
927
335
    MemorySSA &getMSSA() { return *MSSA.get(); }
928
929
    std::unique_ptr<MemorySSA> MSSA;
930
  };
931
932
  Result run(Function &F, FunctionAnalysisManager &AM);
933
};
934
935
/// Printer pass for \c MemorySSA.
936
class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
937
  raw_ostream &OS;
938
939
public:
940
20
  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
941
942
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
943
};
944
945
/// Verifier pass for \c MemorySSA.
946
struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
947
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
948
};
949
950
/// Legacy analysis pass which computes \c MemorySSA.
951
class MemorySSAWrapperPass : public FunctionPass {
952
public:
953
  MemorySSAWrapperPass();
954
955
  static char ID;
956
957
  bool runOnFunction(Function &) override;
958
  void releaseMemory() override;
959
714k
  MemorySSA &getMSSA() { return *MSSA; }
960
0
  const MemorySSA &getMSSA() const { return *MSSA; }
961
962
  void getAnalysisUsage(AnalysisUsage &AU) const override;
963
964
  void verifyAnalysis() const override;
965
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
966
967
private:
968
  std::unique_ptr<MemorySSA> MSSA;
969
};
970
971
/// This is the generic walker interface for walkers of MemorySSA.
972
/// Walkers are used to be able to further disambiguate the def-use chains
973
/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
974
/// you.
975
/// In particular, while the def-use chains provide basic information, and are
976
/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
977
/// MemoryUse as AliasAnalysis considers it, a user mant want better or other
978
/// information. In particular, they may want to use SCEV info to further
979
/// disambiguate memory accesses, or they may want the nearest dominating
980
/// may-aliasing MemoryDef for a call or a store. This API enables a
981
/// standardized interface to getting and using that info.
982
class MemorySSAWalker {
983
public:
984
  MemorySSAWalker(MemorySSA *);
985
715k
  virtual ~MemorySSAWalker() = default;
986
987
  using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
988
989
  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
990
  /// will give you the nearest dominating MemoryAccess that Mod's the location
991
  /// the instruction accesses (by skipping any def which AA can prove does not
992
  /// alias the location(s) accessed by the instruction given).
993
  ///
994
  /// Note that this will return a single access, and it must dominate the
995
  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
996
  /// this will return the MemoryPhi, not the operand. This means that
997
  /// given:
998
  /// if (a) {
999
  ///   1 = MemoryDef(liveOnEntry)
1000
  ///   store %a
1001
  /// } else {
1002
  ///   2 = MemoryDef(liveOnEntry)
1003
  ///   store %b
1004
  /// }
1005
  /// 3 = MemoryPhi(2, 1)
1006
  /// MemoryUse(3)
1007
  /// load %a
1008
  ///
1009
  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1010
  /// in the if (a) branch.
1011
1.41M
  MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1012
1.41M
    MemoryAccess *MA = MSSA->getMemoryAccess(I);
1013
1.41M
    assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
1014
1.41M
    return getClobberingMemoryAccess(MA);
1015
1.41M
  }
1016
1017
  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1018
  /// but takes a MemoryAccess instead of an Instruction.
1019
  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
1020
1021
  /// Given a potentially clobbering memory access and a new location,
1022
  /// calling this will give you the nearest dominating clobbering MemoryAccess
1023
  /// (by skipping non-aliasing def links).
1024
  ///
1025
  /// This version of the function is mainly used to disambiguate phi translated
1026
  /// pointers, where the value of a pointer may have changed from the initial
1027
  /// memory access. Note that this expects to be handed either a MemoryUse,
1028
  /// or an already potentially clobbering access. Unlike the above API, if
1029
  /// given a MemoryDef that clobbers the pointer as the starting access, it
1030
  /// will return that MemoryDef, whereas the above would return the clobber
1031
  /// starting from the use side of  the memory def.
1032
  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1033
                                                  const MemoryLocation &) = 0;
1034
1035
  /// Given a memory access, invalidate anything this walker knows about
1036
  /// that access.
1037
  /// This API is used by walkers that store information to perform basic cache
1038
  /// invalidation.  This will be called by MemorySSA at appropriate times for
1039
  /// the walker it uses or returns.
1040
0
  virtual void invalidateInfo(MemoryAccess *) {}
1041
1042
2.24k
  virtual void verify(const MemorySSA *MSSA) { assert(MSSA == this->MSSA); }
1043
1044
protected:
1045
  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1046
                          // constructor.
1047
  MemorySSA *MSSA;
1048
};
1049
1050
/// A MemorySSAWalker that does no alias queries, or anything else. It
1051
/// simply returns the links as they were constructed by the builder.
1052
class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1053
public:
1054
  // Keep the overrides below from hiding the Instruction overload of
1055
  // getClobberingMemoryAccess.
1056
  using MemorySSAWalker::getClobberingMemoryAccess;
1057
1058
  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1059
  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1060
                                          const MemoryLocation &) override;
1061
};
1062
1063
using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1064
using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1065
1066
/// Iterator base class used to implement const and non-const iterators
1067
/// over the defining accesses of a MemoryAccess.
1068
template <class T>
1069
class memoryaccess_def_iterator_base
1070
    : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1071
                                  std::forward_iterator_tag, T, ptrdiff_t, T *,
1072
                                  T *> {
1073
  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1074
1075
public:
1076
2.67M
  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1077
9.12M
  memoryaccess_def_iterator_base() = default;
1078
1079
15.5M
  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1080
15.5M
    return Access == Other.Access && 
(5.34M
!Access5.34M
||
ArgNo == Other.ArgNo0
);
1081
15.5M
  }
1082
1083
  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1084
  // block from the operand in constant time (In a PHINode, the uselist has
1085
  // both, so it's just subtraction). We provide it as part of the
1086
  // iterator to avoid callers having to linear walk to get the block.
1087
  // If the operation becomes constant time on MemoryPHI's, this bit of
1088
  // abstraction breaking should be removed.
1089
6.41M
  BasicBlock *getPhiArgBlock() const {
1090
6.41M
    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1091
6.41M
    assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1092
6.41M
    return MP->getIncomingBlock(ArgNo);
1093
6.41M
  }
1094
1095
6.45M
  typename BaseT::iterator::pointer operator*() const {
1096
6.45M
    assert(Access && "Tried to access past the end of our iterator");
1097
6.45M
    // Go to the first argument for phis, and the defining access for everything
1098
6.45M
    // else.
1099
6.45M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1100
6.45M
      return MP->getIncomingValue(ArgNo);
1101
0
    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1102
0
  }
1103
1104
  using BaseT::operator++;
1105
6.45M
  memoryaccess_def_iterator &operator++() {
1106
6.45M
    assert(Access && "Hit end of iterator");
1107
6.45M
    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1108
6.45M
      if (++ArgNo >= MP->getNumIncomingValues()) {
1109
2.67M
        ArgNo = 0;
1110
2.67M
        Access = nullptr;
1111
2.67M
      }
1112
6.45M
    } else {
1113
0
      Access = nullptr;
1114
0
    }
1115
6.45M
    return *this;
1116
6.45M
  }
1117
1118
private:
1119
  T *Access = nullptr;
1120
  unsigned ArgNo = 0;
1121
};
1122
1123
inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1124
  return memoryaccess_def_iterator(this);
1125
}
1126
1127
inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1128
  return const_memoryaccess_def_iterator(this);
1129
}
1130
1131
6.45M
inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1132
6.45M
  return memoryaccess_def_iterator();
1133
6.45M
}
1134
1135
0
inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1136
0
  return const_memoryaccess_def_iterator();
1137
0
}
1138
1139
/// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1140
/// and uses in the inverse case.
1141
template <> struct GraphTraits<MemoryAccess *> {
1142
  using NodeRef = MemoryAccess *;
1143
  using ChildIteratorType = memoryaccess_def_iterator;
1144
1145
  static NodeRef getEntryNode(NodeRef N) { return N; }
1146
  static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1147
  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1148
};
1149
1150
template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1151
  using NodeRef = MemoryAccess *;
1152
  using ChildIteratorType = MemoryAccess::iterator;
1153
1154
  static NodeRef getEntryNode(NodeRef N) { return N; }
1155
  static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1156
  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1157
};
1158
1159
/// Provide an iterator that walks defs, giving both the memory access,
1160
/// and the current pointer location, updating the pointer location as it
1161
/// changes due to phi node translation.
1162
///
1163
/// This iterator, while somewhat specialized, is what most clients actually
1164
/// want when walking upwards through MemorySSA def chains. It takes a pair of
1165
/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1166
/// memory location through phi nodes for the user.
1167
class upward_defs_iterator
1168
    : public iterator_facade_base<upward_defs_iterator,
1169
                                  std::forward_iterator_tag,
1170
                                  const MemoryAccessPair> {
1171
  using BaseT = upward_defs_iterator::iterator_facade_base;
1172
1173
public:
1174
  upward_defs_iterator(const MemoryAccessPair &Info)
1175
      : DefIterator(Info.first), Location(Info.second),
1176
2.67M
        OriginalAccess(Info.first) {
1177
2.67M
    CurrentPair.first = nullptr;
1178
2.67M
1179
2.67M
    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1180
2.67M
    fillInCurrentPair();
1181
2.67M
  }
1182
1183
2.67M
  upward_defs_iterator() { CurrentPair.first = nullptr; }
1184
1185
9.12M
  bool operator==(const upward_defs_iterator &Other) const {
1186
9.12M
    return DefIterator == Other.DefIterator;
1187
9.12M
  }
1188
1189
6.45M
  BaseT::iterator::reference operator*() const {
1190
6.45M
    assert(DefIterator != OriginalAccess->defs_end() &&
1191
6.45M
           "Tried to access past the end of our iterator");
1192
6.45M
    return CurrentPair;
1193
6.45M
  }
1194
1195
  using BaseT::operator++;
1196
6.45M
  upward_defs_iterator &operator++() {
1197
6.45M
    assert(DefIterator != OriginalAccess->defs_end() &&
1198
6.45M
           "Tried to access past the end of the iterator");
1199
6.45M
    ++DefIterator;
1200
6.45M
    if (DefIterator != OriginalAccess->defs_end())
1201
3.78M
      fillInCurrentPair();
1202
6.45M
    return *this;
1203
6.45M
  }
1204
1205
0
  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1206
1207
private:
1208
6.45M
  void fillInCurrentPair() {
1209
6.45M
    CurrentPair.first = *DefIterator;
1210
6.45M
    if (WalkingPhi && Location.Ptr) {
1211
6.41M
      PHITransAddr Translator(
1212
6.41M
          const_cast<Value *>(Location.Ptr),
1213
6.41M
          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1214
6.41M
      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1215
6.41M
                                        DefIterator.getPhiArgBlock(), nullptr,
1216
6.41M
                                        false))
1217
0
        if (Translator.getAddr() != Location.Ptr) {
1218
0
          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
1219
0
          return;
1220
0
        }
1221
6.45M
    }
1222
6.45M
    CurrentPair.second = Location;
1223
6.45M
  }
1224
1225
  MemoryAccessPair CurrentPair;
1226
  memoryaccess_def_iterator DefIterator;
1227
  MemoryLocation Location;
1228
  MemoryAccess *OriginalAccess = nullptr;
1229
  bool WalkingPhi = false;
1230
};
1231
1232
2.67M
inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
1233
2.67M
  return upward_defs_iterator(Pair);
1234
2.67M
}
1235
1236
2.67M
inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1237
1238
inline iterator_range<upward_defs_iterator>
1239
upward_defs(const MemoryAccessPair &Pair) {
1240
  return make_range(upward_defs_begin(Pair), upward_defs_end());
1241
}
1242
1243
/// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1244
/// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1245
/// comparing against a null def_chain_iterator, this will compare equal only
1246
/// after walking said Phi/liveOnEntry.
1247
///
1248
/// The UseOptimizedChain flag specifies whether to walk the clobbering
1249
/// access chain, or all the accesses.
1250
///
1251
/// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1252
/// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1253
/// a phi node.  The optimized chain walks the clobbering access of a store.
1254
/// So if you are just trying to find, given a store, what the next
1255
/// thing that would clobber the same memory is, you want the optimized chain.
1256
template <class T, bool UseOptimizedChain = false>
1257
struct def_chain_iterator
1258
    : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1259
                                  std::forward_iterator_tag, MemoryAccess *> {
1260
  def_chain_iterator() : MA(nullptr) {}
1261
9.37M
  def_chain_iterator(T MA) : MA(MA) {}
1262
1263
8.66M
  T operator*() const { return MA; }
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator*() const
Line
Count
Source
1263
8.66M
  T operator*() const { return MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator*() const
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator*() const
1264
1265
6.64M
  def_chain_iterator &operator++() {
1266
6.64M
    // N.B. liveOnEntry has a null defining access.
1267
6.64M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1268
3.97M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1269
0
        MA = MUD->getOptimized();
1270
3.97M
      else
1271
3.97M
        MA = MUD->getDefiningAccess();
1272
3.97M
    } else {
1273
2.67M
      MA = nullptr;
1274
2.67M
    }
1275
6.64M
1276
6.64M
    return *this;
1277
6.64M
  }
llvm::def_chain_iterator<llvm::MemoryAccess*, false>::operator++()
Line
Count
Source
1265
6.64M
  def_chain_iterator &operator++() {
1266
6.64M
    // N.B. liveOnEntry has a null defining access.
1267
6.64M
    if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1268
3.97M
      if (UseOptimizedChain && 
MUD->isOptimized()0
)
1269
0
        MA = MUD->getOptimized();
1270
3.97M
      else
1271
3.97M
        MA = MUD->getDefiningAccess();
1272
3.97M
    } else {
1273
2.67M
      MA = nullptr;
1274
2.67M
    }
1275
6.64M
1276
6.64M
    return *this;
1277
6.64M
  }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator++()
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator++()
1278
1279
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
1279
11.3M
  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, false>::operator==(llvm::def_chain_iterator<llvm::MemoryAccess const*, false> const&) const
Unexecuted instantiation: llvm::def_chain_iterator<llvm::MemoryAccess const*, true>::operator==(llvm::def_chain_iterator<llvm::MemoryAccess const*, true> const&) const
1280
1281
private:
1282
  T MA;
1283
};
1284
1285
template <class T>
1286
inline iterator_range<def_chain_iterator<T>>
1287
4.68M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1288
4.68M
#ifdef EXPENSIVE_CHECKS
1289
4.68M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1290
4.68M
         "UpTo isn't in the def chain!");
1291
4.68M
#endif
1292
4.68M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1293
4.68M
}
llvm::iterator_range<llvm::def_chain_iterator<llvm::MemoryAccess*, false> > llvm::def_chain<llvm::MemoryAccess*>(llvm::MemoryAccess*, llvm::MemoryAccess*)
Line
Count
Source
1287
4.68M
def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1288
4.68M
#ifdef EXPENSIVE_CHECKS
1289
4.68M
  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1290
4.68M
         "UpTo isn't in the def chain!");
1291
4.68M
#endif
1292
4.68M
  return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1293
4.68M
}
Unexecuted instantiation: llvm::iterator_range<llvm::def_chain_iterator<llvm::MemoryAccess const*, false> > llvm::def_chain<llvm::MemoryAccess const*>(llvm::MemoryAccess const*, llvm::MemoryAccess*)
1294
1295
template <class T>
1296
0
inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1297
0
  return make_range(def_chain_iterator<T, true>(MA),
1298
0
                    def_chain_iterator<T, true>(nullptr));
1299
0
}
1300
1301
} // end namespace llvm
1302
1303
#endif // LLVM_ANALYSIS_MEMORYSSA_H