1 //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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
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
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.
29 //===----------------------------------------------------------------------===//
31 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
32 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
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"
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
*>>;
70 class MemorySSAUpdater
{
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
;
78 SmallPtrSet
<BasicBlock
*, 8> VisitedBlocks
;
79 SmallSet
<AssertingVH
<MemoryPhi
>, 8> NonOptPhis
;
82 MemorySSAUpdater(MemorySSA
*MSSA
) : MSSA(MSSA
) {}
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.
94 /// Moving the store into the if block, and calling insertDef, does not
95 /// require RenameUses.
96 /// However, changing it to:
98 /// if (foo) { store b }
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
, bool RenameUses
= false);
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
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
,
132 void updateExitBlocksForClonedLoop(
133 ArrayRef
<BasicBlock
*> ExitBlocks
,
134 ArrayRef
<std::unique_ptr
<ValueToValueMapTy
>> VMaps
, DominatorTree
&DT
);
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
);
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 |
155 /// | | |------| <- Start
157 /// |------| |------|
158 void moveAllAfterSpliceBlocks(BasicBlock
*From
, BasicBlock
*To
,
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 /// |------| |------|
171 /// |------| | | <- Start
173 /// |------| |------|
174 void moveAllAfterMergeBlocks(BasicBlock
*From
, BasicBlock
*To
,
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
190 /// Create a MemoryAccess in MemorySSA at a specified point in a block,
191 /// with a specified clobbering definition.
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
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
);
207 /// Create a MemoryAccess in MemorySSA before or after an existing
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.
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
);
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);
232 /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
233 /// This should be called when an instruction (load/store) is deleted from
235 void removeMemoryAccess(const Instruction
*I
, bool OptimizePhis
= false) {
236 if (MemoryAccess
*MA
= MSSA
->getMemoryAccess(I
))
237 removeMemoryAccess(MA
, OptimizePhis
);
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
);
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'
252 void changeToUnreachable(const Instruction
*I
);
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
);
259 /// Get handle on MemorySSA.
260 MemorySSA
* getMemorySSA() const { return MSSA
; }
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
*);
272 getPreviousDefFromEnd(BasicBlock
*,
273 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> &);
275 getPreviousDefRecursive(BasicBlock
*,
276 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> &);
277 MemoryAccess
*recursePhi(MemoryAccess
*Phi
);
278 MemoryAccess
*tryRemoveTrivialPhi(MemoryPhi
*Phi
);
279 template <class RangeType
>
280 MemoryAccess
*tryRemoveTrivialPhi(MemoryPhi
*Phi
, RangeType
&Operands
);
281 void tryRemoveTrivialPhis(ArrayRef
<WeakVH
> UpdatedPHIs
);
282 void fixupDefs(const SmallVectorImpl
<WeakVH
> &);
283 // Clone all uses and defs from BB to NewBB given a 1:1 map of all
284 // instructions and blocks cloned, and a map of MemoryPhi : Definition
285 // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
286 // instructions and old blocks to cloned blocks. MPhiMap, is created in the
287 // caller of this private method, and maps existing MemoryPhis to new
288 // definitions that new MemoryAccesses must point to. These definitions may
289 // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
290 // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
291 // may be MemoryPhis or MemoryDefs and not MemoryUses.
292 // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
293 // the clone involved simplifications that may have: (1) turned a MemoryUse
294 // into an instruction that MemorySSA has no representation for, or (2) turned
295 // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
296 // representation for. No other cases are supported.
297 void cloneUsesAndDefs(BasicBlock
*BB
, BasicBlock
*NewBB
,
298 const ValueToValueMapTy
&VMap
, PhiToDefMap
&MPhiMap
,
299 bool CloneWasSimplified
= false);
300 template <typename Iter
>
301 void privateUpdateExitBlocksForClonedLoop(ArrayRef
<BasicBlock
*> ExitBlocks
,
302 Iter ValuesBegin
, Iter ValuesEnd
,
304 void applyInsertUpdates(ArrayRef
<CFGUpdate
>, DominatorTree
&DT
,
305 const GraphDiff
<BasicBlock
*> *GD
);
307 } // end namespace llvm
309 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H