LLVM  16.0.0git
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 //===----------------------------------------------------------------------===//
34 #include "llvm/ADT/SmallPtrSet.h"
35 #include "llvm/ADT/SmallSet.h"
36 #include "llvm/ADT/SmallVector.h"
38 #include "llvm/IR/ValueHandle.h"
39 #include "llvm/IR/ValueMap.h"
40 #include "llvm/Support/CFGDiff.h"
42 namespace llvm {
44 class BasicBlock;
45 class DominatorTree;
46 class Instruction;
47 class LoopBlocksRPO;
48 template <typename T, unsigned int N> class SmallSetVector;
55 private:
56  MemorySSA *MSSA;
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;
62  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
63  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
65 public:
66  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
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);
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.
128  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
129  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *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  /// |------| |------|
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.
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.
177  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
178  /// with a specified clobbering definition.
179  ///
180  /// Returns the new MemoryAccess.
181  /// This should be called when a memory instruction is created that is being
182  /// used to replace an existing memory instruction. It will *not* create PHI
183  /// nodes, or verify the clobbering definition. The insertion place is used
184  /// solely to determine where in the memoryssa access lists the instruction
185  /// will be placed. The caller is expected to keep ordering the same as
186  /// instructions.
187  /// It will return the new MemoryAccess.
188  /// Note: If a MemoryAccess already exists for I, this function will make it
189  /// inaccessible and it *must* have removeMemoryAccess called on it.
191  const BasicBlock *BB,
194  /// Create a MemoryAccess in MemorySSA before or after an existing
195  /// MemoryAccess.
196  ///
197  /// Returns the new MemoryAccess.
198  /// This should be called when a memory instruction is created that is being
199  /// used to replace an existing memory instruction. It will *not* create PHI
200  /// nodes, or verify the clobbering definition.
201  ///
202  /// Note: If a MemoryAccess already exists for I, this function will make it
203  /// inaccessible and it *must* have removeMemoryAccess called on it.
205  MemoryAccess *Definition,
206  MemoryUseOrDef *InsertPt);
208  MemoryAccess *Definition,
209  MemoryAccess *InsertPt);
211  /// Remove a MemoryAccess from MemorySSA, including updating all
212  /// definitions and uses.
213  /// This should be called when a memory instruction that has a MemoryAccess
214  /// associated with it is erased from the program. For example, if a store or
215  /// load is simply erased (not replaced), removeMemoryAccess should be called
216  /// on the MemoryAccess for that store/load.
217  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
219  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
220  /// This should be called when an instruction (load/store) is deleted from
221  /// the program.
222  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
223  if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
224  removeMemoryAccess(MA, OptimizePhis);
225  }
227  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
228  /// Assumption we make here: all uses of deleted defs and phi must either
229  /// occur in blocks about to be deleted (thus will be deleted as well), or
230  /// they occur in phis that will simply lose an incoming value.
231  /// Deleted blocks still have successor info, but their predecessor edges and
232  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
233  /// deleted after this call.
234  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
236  /// Instruction I will be changed to an unreachable. Remove all accesses in
237  /// I's block that follow I (inclusive), and update the Phis in the blocks'
238  /// successors.
239  void changeToUnreachable(const Instruction *I);
241  /// Get handle on MemorySSA.
242  MemorySSA* getMemorySSA() const { return MSSA; }
244 private:
245  // Move What before Where in the MemorySSA IR.
246  template <class WhereType>
247  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
248  // Move all memory accesses from `From` to `To` starting at `Start`.
249  // Restrictions apply, see public wrappers of this method.
250  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
251  MemoryAccess *getPreviousDef(MemoryAccess *);
252  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
253  MemoryAccess *
254  getPreviousDefFromEnd(BasicBlock *,
256  MemoryAccess *
257  getPreviousDefRecursive(BasicBlock *,
259  MemoryAccess *recursePhi(MemoryAccess *Phi);
260  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
261  template <class RangeType>
262  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
263  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
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  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
275  // the clone involved simplifications that may have: (1) turned a MemoryUse
276  // into an instruction that MemorySSA has no representation for, or (2) turned
277  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
278  // representation for. No other cases are supported.
279  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
280  const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
281  bool CloneWasSimplified = false);
282  template <typename Iter>
283  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
284  Iter ValuesBegin, Iter ValuesEnd,
285  DominatorTree &DT);
287  const GraphDiff<BasicBlock *> *GD);
288 };
289 } // end namespace llvm
MemorySSAUpdater(MemorySSA *MSSA)
Definition: MemorySSAUpdater.h:66
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Def
Definition: TGLexer.h:50
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.
Definition: MemorySSAUpdater.cpp:1437
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Definition: DenseMap.h:880
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Definition: MemorySSAUpdater.cpp:1372
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1247
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:809
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
Definition: MemorySSAUpdater.cpp:1429
Definition: CFGDiff.h:57
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
Definition: MemorySSAUpdater.cpp:637
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:238
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1196
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
Definition: MemorySSAUpdater.cpp:756
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
Definition: Instruction.h:42
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...
Definition: MemorySSAUpdater.cpp:538
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:860
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
Definition: MemorySSAUpdater.cpp:531
Definition: MemorySSAUpdater.h:54
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1408
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...
Definition: MemorySSAUpdater.cpp:676
Definition: DenseMap.h:714
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
#define I(x, y, z)
Definition: MD5.cpp:58
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
Definition: MemorySSAUpdater.h:222
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Definition: MemorySSAUpdater.cpp:1447
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
Definition: MemorySSAUpdater.cpp:307
Definition: MemorySSA.h:142
llvm::ValueMap< const Value *, WeakTrackingVH >
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
Definition: MemorySSAUpdater.cpp:787
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1191
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Definition: MemorySSAUpdater.cpp:1268
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1258
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
Definition: CFGUpdate.h:28
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43