LLVM  16.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 
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"
41 
42 namespace llvm {
43 
44 class BasicBlock;
45 class DominatorTree;
46 class Instruction;
47 class LoopBlocksRPO;
48 template <typename T, unsigned int N> class SmallSetVector;
49 
53 
55 private:
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;
63  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
64 
65 public:
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);
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.
176 
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,
193 
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);
210 
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);
218 
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  }
226 
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);
235 
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);
240 
241  /// Get handle on MemorySSA.
242  MemorySSA* getMemorySSA() const { return MSSA; }
243 
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
290 
291 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
llvm::MemorySSAUpdater::MemorySSAUpdater
MemorySSAUpdater(MemorySSA *MSSA)
Definition: MemorySSAUpdater.h:66
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::MemorySSAUpdater::createMemoryAccessBefore
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.
Definition: MemorySSAUpdater.cpp:1437
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::MemorySSAUpdater::removeBlocks
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Definition: MemorySSAUpdater.cpp:1372
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1247
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
llvm::MemorySSAUpdater::applyUpdates
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:809
llvm::MemorySSAUpdater::createMemoryAccessInBB
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
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::LoopBlocksRPO
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
llvm::MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
Definition: MemorySSAUpdater.cpp:637
CFGDiff.h
llvm::MemorySSAUpdater::insertUse
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:238
llvm::MemorySSAUpdater::moveAfter
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1196
llvm::MemorySSAUpdater::updateForClonedBlockIntoPred
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
Definition: MemorySSAUpdater.cpp:756
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
llvm::Instruction
Definition: Instruction.h:42
SmallPtrSet.h
llvm::MemorySSAUpdater::removeDuplicatePhiEdgesBetween
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
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::MemorySSAUpdater::applyInsertUpdates
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:860
llvm::MemorySSAUpdater::removeEdge
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
Definition: MemorySSAUpdater.cpp:531
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:242
llvm::MemorySSAUpdater::changeToUnreachable
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1408
llvm::MemorySSAUpdater::updateForClonedLoop
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
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
Definition: MemorySSAUpdater.h:222
llvm::MemoryDef
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
llvm::TrackingVH
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
llvm::MemorySSA::InsertionPlace
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::MemorySSAUpdater::createMemoryAccessAfter
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Definition: MemorySSAUpdater.cpp:1447
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::MemorySSAUpdater::insertDef
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
Definition: MemorySSAUpdater.cpp:307
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::ValueMap< const Value *, WeakTrackingVH >
ValueHandle.h
ValueMap.h
llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
Definition: MemorySSAUpdater.cpp:787
llvm::MemorySSAUpdater::moveBefore
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1191
llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor
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
llvm::MemorySSAUpdater::moveAllAfterMergeBlocks
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1258
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
MemorySSA.h
SmallVector.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::cfg::Update
Definition: CFGUpdate.h:28
BB
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
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
SmallSet.h