Coverage Report

Created: 2018-07-19 03:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemorySSAUpdater.h
Line
Count
Source (jump to first uncovered line)
1
//===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// \file
11
// An automatic updater for MemorySSA that handles arbitrary insertion,
12
// deletion, and moves.  It performs phi insertion where necessary, and
13
// automatically updates the MemorySSA IR to be correct.
14
// While updating loads or removing instructions is often easy enough to not
15
// need this, updating stores should generally not be attemped outside this
16
// API.
17
//
18
// Basic API usage:
19
// Create the memory access you want for the instruction (this is mainly so
20
// we know where it is, without having to duplicate the entire set of create
21
// functions MemorySSA supports).
22
// Call insertDef or insertUse depending on whether it's a MemoryUse or a
23
// MemoryDef.
24
// That's it.
25
//
26
// For moving, first, move the instruction itself using the normal SSA
27
// instruction moving API, then just call moveBefore, moveAfter,or moveTo with
28
// the right arguments.
29
//
30
//===----------------------------------------------------------------------===//
31
32
#ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
33
#define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
34
35
#include "llvm/ADT/SmallPtrSet.h"
36
#include "llvm/ADT/SmallSet.h"
37
#include "llvm/ADT/SmallVector.h"
38
#include "llvm/Analysis/MemorySSA.h"
39
#include "llvm/IR/BasicBlock.h"
40
#include "llvm/IR/Dominators.h"
41
#include "llvm/IR/Module.h"
42
#include "llvm/IR/OperandTraits.h"
43
#include "llvm/IR/Type.h"
44
#include "llvm/IR/Use.h"
45
#include "llvm/IR/User.h"
46
#include "llvm/IR/Value.h"
47
#include "llvm/IR/ValueHandle.h"
48
#include "llvm/Pass.h"
49
#include "llvm/Support/Casting.h"
50
#include "llvm/Support/ErrorHandling.h"
51
52
namespace llvm {
53
54
class Function;
55
class Instruction;
56
class MemoryAccess;
57
class LLVMContext;
58
class raw_ostream;
59
60
class MemorySSAUpdater {
61
private:
62
  MemorySSA *MSSA;
63
64
  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
65
  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
66
  SmallVector<WeakVH, 16> InsertedPHIs;
67
68
  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
69
  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
70
71
public:
72
1.06M
  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
73
  /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
74
  /// below the new def block (and any inserted phis).  RenameUses should be set
75
  /// to true if the definition may cause new aliases for loads below it.  This
76
  /// is not the case for hoisting or sinking or other forms of code *movement*.
77
  /// It *is* the case for straight code insertion.
78
  /// For example:
79
  /// store a
80
  /// if (foo) { }
81
  /// load a
82
  ///
83
  /// Moving the store into the if block, and calling insertDef, does not
84
  /// require RenameUses.
85
  /// However, changing it to:
86
  /// store a
87
  /// if (foo) { store b }
88
  /// load a
89
  /// Where a mayalias b, *does* require RenameUses be set to true.
90
  void insertDef(MemoryDef *Def, bool RenameUses = false);
91
  void insertUse(MemoryUse *Use);
92
  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
93
  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
94
  void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
95
                   MemorySSA::InsertionPlace Where);
96
  /// `From` block was spliced into `From` and `To`.
97
  /// Move all accesses from `From` to `To` starting at instruction `Start`.
98
  /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses.
99
  /// Edges are already updated, so successors of `To` with MPhi nodes need to
100
  /// update incoming block.
101
  /// |------|        |------|
102
  /// | From |        | From |
103
  /// |      |        |------|
104
  /// |      |           ||
105
  /// |      |   =>      \/
106
  /// |      |        |------|  <- Start
107
  /// |      |        |  To  |
108
  /// |------|        |------|
109
  void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
110
                                Instruction *Start);
111
  /// `From` block was merged into `To`. All instructions were moved and
112
  /// `From` is an empty block with successor edges; `From` is about to be
113
  /// deleted. Move all accesses from `From` to `To` starting at instruction
114
  /// `Start`. `To` may have multiple successors, `From` has a single
115
  /// predecessor. `From` may have successors with MPhi nodes, replace their
116
  /// incoming block with `To`.
117
  /// |------|        |------|
118
  /// |  To  |        |  To  |
119
  /// |------|        |      |
120
  ///    ||      =>   |      |
121
  ///    \/           |      |
122
  /// |------|        |      |  <- Start
123
  /// | From |        |      |
124
  /// |------|        |------|
125
  void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
126
                               Instruction *Start);
127
128
  // The below are utility functions. Other than creation of accesses to pass
129
  // to insertDef, and removeAccess to remove accesses, you should generally
130
  // not attempt to update memoryssa yourself. It is very non-trivial to get
131
  // the edge cases right, and the above calls already operate in near-optimal
132
  // time bounds.
133
134
  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
135
  /// with a specified clobbering definition.
136
  ///
137
  /// Returns the new MemoryAccess.
138
  /// This should be called when a memory instruction is created that is being
139
  /// used to replace an existing memory instruction. It will *not* create PHI
140
  /// nodes, or verify the clobbering definition. The insertion place is used
141
  /// solely to determine where in the memoryssa access lists the instruction
142
  /// will be placed. The caller is expected to keep ordering the same as
143
  /// instructions.
144
  /// It will return the new MemoryAccess.
145
  /// Note: If a MemoryAccess already exists for I, this function will make it
146
  /// inaccessible and it *must* have removeMemoryAccess called on it.
147
  MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
148
                                       const BasicBlock *BB,
149
                                       MemorySSA::InsertionPlace Point);
150
151
  /// Create a MemoryAccess in MemorySSA before or after an existing
152
  /// MemoryAccess.
153
  ///
154
  /// Returns the new MemoryAccess.
155
  /// This should be called when a memory instruction is created that is being
156
  /// used to replace an existing memory instruction. It will *not* create PHI
157
  /// nodes, or verify the clobbering definition.
158
  ///
159
  /// Note: If a MemoryAccess already exists for I, this function will make it
160
  /// inaccessible and it *must* have removeMemoryAccess called on it.
161
  MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
162
                                           MemoryAccess *Definition,
163
                                           MemoryUseOrDef *InsertPt);
164
  MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
165
                                          MemoryAccess *Definition,
166
                                          MemoryAccess *InsertPt);
167
168
  /// Remove a MemoryAccess from MemorySSA, including updating all
169
  /// definitions and uses.
170
  /// This should be called when a memory instruction that has a MemoryAccess
171
  /// associated with it is erased from the program.  For example, if a store or
172
  /// load is simply erased (not replaced), removeMemoryAccess should be called
173
  /// on the MemoryAccess for that store/load.
174
  void removeMemoryAccess(MemoryAccess *);
175
176
  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
177
  /// This should be called when an instruction (load/store) is deleted from
178
  /// the program.
179
0
  void removeMemoryAccess(const Instruction *I) {
180
0
    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
181
0
      removeMemoryAccess(MA);
182
0
  }
183
184
  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
185
  /// Assumption we make here: all uses of deleted defs and phi must either
186
  /// occur in blocks about to be deleted (thus will be deleted as well), or
187
  /// they occur in phis that will simply lose an incoming value.
188
  /// Deleted blocks still have successor info, but their predecessor edges and
189
  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
190
  /// deleted after this call.
191
  void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
192
193
  /// Get handle on MemorySSA.
194
  MemorySSA* getMemorySSA() const { return MSSA; }
195
196
private:
197
  // Move What before Where in the MemorySSA IR.
198
  template <class WhereType>
199
  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
200
  // Move all memory accesses from `From` to `To` starting at `Start`.
201
  // Restrictions apply, see public wrappers of this method.
202
  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
203
  MemoryAccess *getPreviousDef(MemoryAccess *);
204
  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
205
  MemoryAccess *
206
  getPreviousDefFromEnd(BasicBlock *,
207
                        DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
208
  MemoryAccess *
209
  getPreviousDefRecursive(BasicBlock *,
210
                          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
211
  MemoryAccess *recursePhi(MemoryAccess *Phi);
212
  template <class RangeType>
213
  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
214
  void fixupDefs(const SmallVectorImpl<WeakVH> &);
215
};
216
} // end namespace llvm
217
218
#endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H