LLVM 19.0.0git
MemorySSAUpdater.h
Go to the documentation of this file.
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
35#include "llvm/ADT/SmallSet.h"
38#include "llvm/IR/ValueHandle.h"
39#include "llvm/IR/ValueMap.h"
41
42namespace llvm {
43
44class BasicBlock;
45class DominatorTree;
46class Instruction;
47class LoopBlocksRPO;
48template <typename T, unsigned int N> class SmallSetVector;
49
53
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;
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.
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.
94 const BasicBlock *To);
95 /// Update MemorySSA when inserting a unique backedge block for a loop.
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.
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.
114 const ValueToValueMapTy &VMap,
115 DominatorTree &DT);
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.
124 bool UpdateDTFirst = false);
125 /// Apply CFG insert updates, analogous with the DT edge updates.
127
128 void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
129 void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
130 void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
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 /// |------| |------|
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 /// |------| |------|
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.
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.
192 const BasicBlock *BB,
194
195 /// Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
196 ///
197 /// See createMemoryAccessInBB() for usage details.
199 MemoryAccess *Definition,
200 MemoryUseOrDef *InsertPt);
201 /// Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
202 ///
203 /// See createMemoryAccessInBB() for usage details.
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
241private:
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 *);
251 getPreviousDefFromEnd(BasicBlock *,
254 getPreviousDefRecursive(BasicBlock *,
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);
284 const GraphDiff<BasicBlock *> *GD);
285};
286} // end namespace llvm
287
288#endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
BlockVerifier::State From
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 ma...
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block.
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
void insertUse(MemoryUse *Use, bool RenameUses=false)
MemorySSAUpdater(MemorySSA *MSSA)
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18