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