Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MemorySSAUpdater.h
Line
Count
Source
1
//===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- 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
// An automatic updater for MemorySSA that handles arbitrary insertion,
11
// deletion, and moves.  It performs phi insertion where necessary, and
12
// automatically updates the MemorySSA IR to be correct.
13
// While updating loads or removing instructions is often easy enough to not
14
// need this, updating stores should generally not be attemped outside this
15
// API.
16
//
17
// Basic API usage:
18
// Create the memory access you want for the instruction (this is mainly so
19
// we know where it is, without having to duplicate the entire set of create
20
// functions MemorySSA supports).
21
// Call insertDef or insertUse depending on whether it's a MemoryUse or a
22
// MemoryDef.
23
// That's it.
24
//
25
// For moving, first, move the instruction itself using the normal SSA
26
// instruction moving API, then just call moveBefore, moveAfter,or moveTo with
27
// the right arguments.
28
//
29
//===----------------------------------------------------------------------===//
30
31
#ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
32
#define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
33
34
#include "llvm/ADT/SetVector.h"
35
#include "llvm/ADT/SmallPtrSet.h"
36
#include "llvm/ADT/SmallSet.h"
37
#include "llvm/ADT/SmallVector.h"
38
#include "llvm/Analysis/LoopInfo.h"
39
#include "llvm/Analysis/LoopIterator.h"
40
#include "llvm/Analysis/MemorySSA.h"
41
#include "llvm/IR/BasicBlock.h"
42
#include "llvm/IR/CFGDiff.h"
43
#include "llvm/IR/Dominators.h"
44
#include "llvm/IR/Module.h"
45
#include "llvm/IR/OperandTraits.h"
46
#include "llvm/IR/Type.h"
47
#include "llvm/IR/Use.h"
48
#include "llvm/IR/User.h"
49
#include "llvm/IR/Value.h"
50
#include "llvm/IR/ValueHandle.h"
51
#include "llvm/IR/ValueMap.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/Casting.h"
54
#include "llvm/Support/ErrorHandling.h"
55
56
namespace llvm {
57
58
class Function;
59
class Instruction;
60
class MemoryAccess;
61
class LLVMContext;
62
class raw_ostream;
63
64
using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
65
using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
66
using CFGUpdate = cfg::Update<BasicBlock *>;
67
using GraphDiffInvBBPair =
68
    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
69
70
class MemorySSAUpdater {
71
private:
72
  MemorySSA *MSSA;
73
74
  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
75
  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
76
  SmallVector<WeakVH, 16> InsertedPHIs;
77
78
  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
79
  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
80
81
public:
82
1.15M
  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
83
84
  /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
85
  /// below the new def block (and any inserted phis).  RenameUses should be set
86
  /// to true if the definition may cause new aliases for loads below it.  This
87
  /// is not the case for hoisting or sinking or other forms of code *movement*.
88
  /// It *is* the case for straight code insertion.
89
  /// For example:
90
  /// store a
91
  /// if (foo) { }
92
  /// load a
93
  ///
94
  /// Moving the store into the if block, and calling insertDef, does not
95
  /// require RenameUses.
96
  /// However, changing it to:
97
  /// store a
98
  /// if (foo) { store b }
99
  /// load a
100
  /// Where a mayalias b, *does* require RenameUses be set to true.
101
  void insertDef(MemoryDef *Def, bool RenameUses = false);
102
  void insertUse(MemoryUse *Use);
103
  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
104
  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
105
  void removeEdge(BasicBlock *From, BasicBlock *To);
106
  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
107
  /// following a CFG change that replaced multiple edges (switch) with a direct
108
  /// branch.
109
  void removeDuplicatePhiEdgesBetween(const BasicBlock *From,
110
                                      const BasicBlock *To);
111
  /// Update MemorySSA when inserting a unique backedge block for a loop.
112
  void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader,
113
                                                  BasicBlock *LoopPreheader,
114
                                                  BasicBlock *BackedgeBlock);
115
  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
116
  /// the exit blocks and a 1:1 mapping of all blocks and instructions
117
  /// cloned. This involves duplicating all defs and uses in the cloned blocks
118
  /// Updating phi nodes in exit block successors is done separately.
119
  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
120
                           ArrayRef<BasicBlock *> ExitBlocks,
121
                           const ValueToValueMapTy &VM,
122
                           bool IgnoreIncomingWithNoClones = false);
123
  // Block BB was fully or partially cloned into its predecessor P1. Map
124
  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
125
  void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
126
                                    const ValueToValueMapTy &VM);
127
  /// Update phi nodes in exit block successors following cloning. Exit blocks
128
  /// that were not cloned don't have additional predecessors added.
129
  void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
130
                                     const ValueToValueMapTy &VMap,
131
                                     DominatorTree &DT);
132
  void updateExitBlocksForClonedLoop(
133
      ArrayRef<BasicBlock *> ExitBlocks,
134
      ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
135
136
  /// Apply CFG updates, analogous with the DT edge updates.
137
  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
138
  /// Apply CFG insert updates, analogous with the DT edge updates.
139
  void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
140
141
  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
142
  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
143
  void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
144
                   MemorySSA::InsertionPlace Where);
145
  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
146
  /// `From` to `To`. Move all accesses from `From` to `To` starting at
147
  /// instruction `Start`. `To` is newly created BB, so empty of
148
  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
149
  /// `To` with MPhi nodes need to update incoming block.
150
  /// |------|        |------|
151
  /// | From |        | From |
152
  /// |      |        |------|
153
  /// |      |           ||
154
  /// |      |   =>      \/
155
  /// |      |        |------|  <- Start
156
  /// |      |        |  To  |
157
  /// |------|        |------|
158
  void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
159
                                Instruction *Start);
160
  /// `From` block was merged into `To`. There is a CFG edge from `To` to
161
  /// `From`.`To` still branches to `From`, but all instructions were moved and
162
  /// `From` is now an empty block; `From` is about to be deleted. Move all
163
  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
164
  /// have multiple successors, `From` has a single predecessor. `From` may have
165
  /// successors with MPhi nodes, replace their incoming block with `To`.
166
  /// |------|        |------|
167
  /// |  To  |        |  To  |
168
  /// |------|        |      |
169
  ///    ||      =>   |      |
170
  ///    \/           |      |
171
  /// |------|        |      |  <- Start
172
  /// | From |        |      |
173
  /// |------|        |------|
174
  void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
175
                               Instruction *Start);
176
  /// A new empty BasicBlock (New) now branches directly to Old. Some of
177
  /// Old's predecessors (Preds) are now branching to New instead of Old.
178
  /// If New is the only predecessor, move Old's Phi, if present, to New.
179
  /// Otherwise, add a new Phi in New with appropriate incoming values, and
180
  /// update the incoming values in Old's Phi node too, if present.
181
  void wireOldPredecessorsToNewImmediatePredecessor(
182
      BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
183
      bool IdenticalEdgesWereMerged = true);
184
  // The below are utility functions. Other than creation of accesses to pass
185
  // to insertDef, and removeAccess to remove accesses, you should generally
186
  // not attempt to update memoryssa yourself. It is very non-trivial to get
187
  // the edge cases right, and the above calls already operate in near-optimal
188
  // time bounds.
189
190
  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
191
  /// with a specified clobbering definition.
192
  ///
193
  /// Returns the new MemoryAccess.
194
  /// This should be called when a memory instruction is created that is being
195
  /// used to replace an existing memory instruction. It will *not* create PHI
196
  /// nodes, or verify the clobbering definition. The insertion place is used
197
  /// solely to determine where in the memoryssa access lists the instruction
198
  /// will be placed. The caller is expected to keep ordering the same as
199
  /// instructions.
200
  /// It will return the new MemoryAccess.
201
  /// Note: If a MemoryAccess already exists for I, this function will make it
202
  /// inaccessible and it *must* have removeMemoryAccess called on it.
203
  MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
204
                                       const BasicBlock *BB,
205
                                       MemorySSA::InsertionPlace Point);
206
207
  /// Create a MemoryAccess in MemorySSA before or after an existing
208
  /// MemoryAccess.
209
  ///
210
  /// Returns the new MemoryAccess.
211
  /// This should be called when a memory instruction is created that is being
212
  /// used to replace an existing memory instruction. It will *not* create PHI
213
  /// nodes, or verify the clobbering definition.
214
  ///
215
  /// Note: If a MemoryAccess already exists for I, this function will make it
216
  /// inaccessible and it *must* have removeMemoryAccess called on it.
217
  MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
218
                                           MemoryAccess *Definition,
219
                                           MemoryUseOrDef *InsertPt);
220
  MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
221
                                          MemoryAccess *Definition,
222
                                          MemoryAccess *InsertPt);
223
224
  /// Remove a MemoryAccess from MemorySSA, including updating all
225
  /// definitions and uses.
226
  /// This should be called when a memory instruction that has a MemoryAccess
227
  /// associated with it is erased from the program.  For example, if a store or
228
  /// load is simply erased (not replaced), removeMemoryAccess should be called
229
  /// on the MemoryAccess for that store/load.
230
  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
231
232
  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
233
  /// This should be called when an instruction (load/store) is deleted from
234
  /// the program.
235
422k
  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
236
422k
    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
237
110k
      removeMemoryAccess(MA, OptimizePhis);
238
422k
  }
239
240
  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
241
  /// Assumption we make here: all uses of deleted defs and phi must either
242
  /// occur in blocks about to be deleted (thus will be deleted as well), or
243
  /// they occur in phis that will simply lose an incoming value.
244
  /// Deleted blocks still have successor info, but their predecessor edges and
245
  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
246
  /// deleted after this call.
247
  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
248
249
  /// Instruction I will be changed to an unreachable. Remove all accesses in
250
  /// I's block that follow I (inclusive), and update the Phis in the blocks'
251
  /// successors.
252
  void changeToUnreachable(const Instruction *I);
253
254
  /// Conditional branch BI is changed or replaced with an unconditional branch
255
  /// to `To`. Update Phis in BI's successors to remove BI's BB.
256
  void changeCondBranchToUnconditionalTo(const BranchInst *BI,
257
                                         const BasicBlock *To);
258
259
  /// Get handle on MemorySSA.
260
4.47k
  MemorySSA* getMemorySSA() const { return MSSA; }
261
262
private:
263
  // Move What before Where in the MemorySSA IR.
264
  template <class WhereType>
265
  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
266
  // Move all memory accesses from `From` to `To` starting at `Start`.
267
  // Restrictions apply, see public wrappers of this method.
268
  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
269
  MemoryAccess *getPreviousDef(MemoryAccess *);
270
  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
271
  MemoryAccess *
272
  getPreviousDefFromEnd(BasicBlock *,
273
                        DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
274
  MemoryAccess *
275
  getPreviousDefRecursive(BasicBlock *,
276
                          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
277
  MemoryAccess *recursePhi(MemoryAccess *Phi);
278
  template <class RangeType>
279
  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
280
  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
281
  void fixupDefs(const SmallVectorImpl<WeakVH> &);
282
  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
283
  // instructions and blocks cloned, and a map of MemoryPhi : Definition
284
  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
285
  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
286
  // caller of this private method, and maps existing MemoryPhis to new
287
  // definitions that new MemoryAccesses must point to. These definitions may
288
  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
289
  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
290
  // may be MemoryPhis or MemoryDefs and not MemoryUses.
291
  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
292
  // the clone involved simplifications that may have: (1) turned a MemoryUse
293
  // into an instruction that MemorySSA has no representation for, or (2) turned
294
  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
295
  // representation for. No other cases are supported.
296
  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
297
                        const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
298
                        bool CloneWasSimplified = false);
299
  template <typename Iter>
300
  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
301
                                            Iter ValuesBegin, Iter ValuesEnd,
302
                                            DominatorTree &DT);
303
  void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
304
                          const GraphDiff<BasicBlock *> *GD);
305
};
306
} // end namespace llvm
307
308
#endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H