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 | |
42 | namespace llvm { |
43 | |
44 | class BasicBlock; |
45 | class DominatorTree; |
46 | class Instruction; |
47 | class LoopBlocksRPO; |
48 | template <typename T, unsigned int N> class SmallSetVector; |
49 | |
50 | using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; |
51 | using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>; |
52 | using CFGUpdate = cfg::Update<BasicBlock *>; |
53 | |
54 | class MemorySSAUpdater { |
55 | private: |
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 | |
65 | public: |
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 *, |
97 | BasicBlock *, |
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 | /// |
179 | /// When used by itself, this method will only insert the new MemoryAccess |
180 | /// into the access list, but not make any other changes, such as inserting |
181 | /// MemoryPHI nodes, or updating users to point to the new MemoryAccess. You |
182 | /// must specify a correct Definition in this case. |
183 | /// |
184 | /// Usually, this API is instead combined with insertUse() or insertDef(), |
185 | /// which will perform all the necessary MSSA updates. If these APIs are used, |
186 | /// then nullptr can be used as Definition, as the correct defining access |
187 | /// will be automatically determined. |
188 | /// |
189 | /// Note: If a MemoryAccess already exists for I, this function will make it |
190 | /// inaccessible and it *must* have removeMemoryAccess called on it. |
191 | MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, |
192 | const BasicBlock *BB, |
193 | MemorySSA::InsertionPlace Point); |
194 | |
195 | /// Create a MemoryAccess in MemorySSA before an existing MemoryAccess. |
196 | /// |
197 | /// See createMemoryAccessInBB() for usage details. |
198 | MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, |
199 | MemoryAccess *Definition, |
200 | MemoryUseOrDef *InsertPt); |
201 | /// Create a MemoryAccess in MemorySSA after an existing MemoryAccess. |
202 | /// |
203 | /// See createMemoryAccessInBB() for usage details. |
204 | MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, |
205 | MemoryAccess *Definition, |
206 | MemoryAccess *InsertPt); |
207 | |
208 | /// Remove a MemoryAccess from MemorySSA, including updating all |
209 | /// definitions and uses. |
210 | /// This should be called when a memory instruction that has a MemoryAccess |
211 | /// associated with it is erased from the program. For example, if a store or |
212 | /// load is simply erased (not replaced), removeMemoryAccess should be called |
213 | /// on the MemoryAccess for that store/load. |
214 | void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false); |
215 | |
216 | /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. |
217 | /// This should be called when an instruction (load/store) is deleted from |
218 | /// the program. |
219 | void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) { |
220 | if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) |
221 | removeMemoryAccess(MA, OptimizePhis); |
222 | } |
223 | |
224 | /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. |
225 | /// Assumption we make here: all uses of deleted defs and phi must either |
226 | /// occur in blocks about to be deleted (thus will be deleted as well), or |
227 | /// they occur in phis that will simply lose an incoming value. |
228 | /// Deleted blocks still have successor info, but their predecessor edges and |
229 | /// Phi nodes may already be updated. Instructions in DeadBlocks should be |
230 | /// deleted after this call. |
231 | void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks); |
232 | |
233 | /// Instruction I will be changed to an unreachable. Remove all accesses in |
234 | /// I's block that follow I (inclusive), and update the Phis in the blocks' |
235 | /// successors. |
236 | void changeToUnreachable(const Instruction *I); |
237 | |
238 | /// Get handle on MemorySSA. |
239 | MemorySSA* getMemorySSA() const { return MSSA; } |
240 | |
241 | private: |
242 | // Move What before Where in the MemorySSA IR. |
243 | template <class WhereType> |
244 | void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); |
245 | // Move all memory accesses from `From` to `To` starting at `Start`. |
246 | // Restrictions apply, see public wrappers of this method. |
247 | void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); |
248 | MemoryAccess *getPreviousDef(MemoryAccess *); |
249 | MemoryAccess *getPreviousDefInBlock(MemoryAccess *); |
250 | MemoryAccess * |
251 | getPreviousDefFromEnd(BasicBlock *, |
252 | DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); |
253 | MemoryAccess * |
254 | getPreviousDefRecursive(BasicBlock *, |
255 | DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); |
256 | MemoryAccess *recursePhi(MemoryAccess *Phi); |
257 | MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi); |
258 | template <class RangeType> |
259 | MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); |
260 | void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs); |
261 | void fixupDefs(const SmallVectorImpl<WeakVH> &); |
262 | // Clone all uses and defs from BB to NewBB given a 1:1 map of all |
263 | // instructions and blocks cloned, and a map of MemoryPhi : Definition |
264 | // (MemoryAccess Phi or Def). VMap maps old instructions to cloned |
265 | // instructions and old blocks to cloned blocks. MPhiMap, is created in the |
266 | // caller of this private method, and maps existing MemoryPhis to new |
267 | // definitions that new MemoryAccesses must point to. These definitions may |
268 | // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such, |
269 | // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses |
270 | // may be MemoryPhis or MemoryDefs and not MemoryUses. |
271 | // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that |
272 | // the clone involved simplifications that may have: (1) turned a MemoryUse |
273 | // into an instruction that MemorySSA has no representation for, or (2) turned |
274 | // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no |
275 | // representation for. No other cases are supported. |
276 | void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, |
277 | const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap, |
278 | bool CloneWasSimplified = false); |
279 | template <typename Iter> |
280 | void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, |
281 | Iter ValuesBegin, Iter ValuesEnd, |
282 | DominatorTree &DT); |
283 | void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT, |
284 | const GraphDiff<BasicBlock *> *GD); |
285 | }; |
286 | } // end namespace llvm |
287 | |
288 | #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H |
289 | |