Line data Source code
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/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 25 : 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 *);
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 27 : void removeMemoryAccess(const Instruction *I) {
230 27 : if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
231 6 : removeMemoryAccess(MA);
232 27 : }
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 0 : 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
|
