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

source code of llvm/include/llvm/Analysis/MemorySSAUpdater.h