LLVM  14.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/SetVector.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallSet.h"
37 #include "llvm/ADT/SmallVector.h"
39 #include "llvm/IR/ValueHandle.h"
40 #include "llvm/IR/ValueMap.h"
41 #include "llvm/Support/CFGDiff.h"
42 #include <utility>
43 
44 namespace llvm {
45 
46 class BasicBlock;
47 class DominatorTree;
48 class Instruction;
49 class LoopBlocksRPO;
50 
54 
56 private:
57  MemorySSA *MSSA;
58 
59  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
60  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
61  SmallVector<WeakVH, 16> InsertedPHIs;
62 
63  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
64  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
65 
66 public:
67  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
68 
69  /// Insert a definition into the MemorySSA IR. RenameUses will rename any use
70  /// below the new def block (and any inserted phis). RenameUses should be set
71  /// to true if the definition may cause new aliases for loads below it. This
72  /// is not the case for hoisting or sinking or other forms of code *movement*.
73  /// It *is* the case for straight code insertion.
74  /// For example:
75  /// store a
76  /// if (foo) { }
77  /// load a
78  ///
79  /// Moving the store into the if block, and calling insertDef, does not
80  /// require RenameUses.
81  /// However, changing it to:
82  /// store a
83  /// if (foo) { store b }
84  /// load a
85  /// Where a mayalias b, *does* require RenameUses be set to true.
86  void insertDef(MemoryDef *Def, bool RenameUses = false);
87  void insertUse(MemoryUse *Use, bool RenameUses = false);
88  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
89  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
91  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
92  /// following a CFG change that replaced multiple edges (switch) with a direct
93  /// branch.
95  const BasicBlock *To);
96  /// Update MemorySSA when inserting a unique backedge block for a loop.
98  BasicBlock *LoopPreheader,
99  BasicBlock *BackedgeBlock);
100  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
101  /// the exit blocks and a 1:1 mapping of all blocks and instructions
102  /// cloned. This involves duplicating all defs and uses in the cloned blocks
103  /// Updating phi nodes in exit block successors is done separately.
104  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
105  ArrayRef<BasicBlock *> ExitBlocks,
106  const ValueToValueMapTy &VM,
107  bool IgnoreIncomingWithNoClones = false);
108  // Block BB was fully or partially cloned into its predecessor P1. Map
109  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
111  const ValueToValueMapTy &VM);
112  /// Update phi nodes in exit block successors following cloning. Exit blocks
113  /// that were not cloned don't have additional predecessors added.
115  const ValueToValueMapTy &VMap,
116  DominatorTree &DT);
118  ArrayRef<BasicBlock *> ExitBlocks,
119  ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
120 
121  /// Apply CFG updates, analogous with the DT edge updates. By default, the
122  /// DT is assumed to be already up to date. If UpdateDTFirst is true, first
123  /// update the DT with the same updates.
125  bool UpdateDTFirst = false);
126  /// Apply CFG insert updates, analogous with the DT edge updates.
128 
129  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
130  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
133  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
134  /// `From` to `To`. Move all accesses from `From` to `To` starting at
135  /// instruction `Start`. `To` is newly created BB, so empty of
136  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
137  /// `To` with MPhi nodes need to update incoming block.
138  /// |------| |------|
139  /// | From | | From |
140  /// | | |------|
141  /// | | ||
142  /// | | => \/
143  /// | | |------| <- Start
144  /// | | | To |
145  /// |------| |------|
147  Instruction *Start);
148  /// `From` block was merged into `To`. There is a CFG edge from `To` to
149  /// `From`.`To` still branches to `From`, but all instructions were moved and
150  /// `From` is now an empty block; `From` is about to be deleted. Move all
151  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
152  /// have multiple successors, `From` has a single predecessor. `From` may have
153  /// successors with MPhi nodes, replace their incoming block with `To`.
154  /// |------| |------|
155  /// | To | | To |
156  /// |------| | |
157  /// || => | |
158  /// \/ | |
159  /// |------| | | <- Start
160  /// | From | | |
161  /// |------| |------|
163  Instruction *Start);
164  /// A new empty BasicBlock (New) now branches directly to Old. Some of
165  /// Old's predecessors (Preds) are now branching to New instead of Old.
166  /// If New is the only predecessor, move Old's Phi, if present, to New.
167  /// Otherwise, add a new Phi in New with appropriate incoming values, and
168  /// update the incoming values in Old's Phi node too, if present.
170  BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
171  bool IdenticalEdgesWereMerged = true);
172  // The below are utility functions. Other than creation of accesses to pass
173  // to insertDef, and removeAccess to remove accesses, you should generally
174  // not attempt to update memoryssa yourself. It is very non-trivial to get
175  // the edge cases right, and the above calls already operate in near-optimal
176  // time bounds.
177 
178  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
179  /// with a specified clobbering definition.
180  ///
181  /// Returns the new MemoryAccess.
182  /// This should be called when a memory instruction is created that is being
183  /// used to replace an existing memory instruction. It will *not* create PHI
184  /// nodes, or verify the clobbering definition. The insertion place is used
185  /// solely to determine where in the memoryssa access lists the instruction
186  /// will be placed. The caller is expected to keep ordering the same as
187  /// instructions.
188  /// It will return the new MemoryAccess.
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 or after an existing
196  /// MemoryAccess.
197  ///
198  /// Returns the new MemoryAccess.
199  /// This should be called when a memory instruction is created that is being
200  /// used to replace an existing memory instruction. It will *not* create PHI
201  /// nodes, or verify the clobbering definition.
202  ///
203  /// Note: If a MemoryAccess already exists for I, this function will make it
204  /// inaccessible and it *must* have removeMemoryAccess called on it.
206  MemoryAccess *Definition,
207  MemoryUseOrDef *InsertPt);
209  MemoryAccess *Definition,
210  MemoryAccess *InsertPt);
211 
212  /// Remove a MemoryAccess from MemorySSA, including updating all
213  /// definitions and uses.
214  /// This should be called when a memory instruction that has a MemoryAccess
215  /// associated with it is erased from the program. For example, if a store or
216  /// load is simply erased (not replaced), removeMemoryAccess should be called
217  /// on the MemoryAccess for that store/load.
218  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
219 
220  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
221  /// This should be called when an instruction (load/store) is deleted from
222  /// the program.
223  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
224  if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
225  removeMemoryAccess(MA, OptimizePhis);
226  }
227 
228  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
229  /// Assumption we make here: all uses of deleted defs and phi must either
230  /// occur in blocks about to be deleted (thus will be deleted as well), or
231  /// they occur in phis that will simply lose an incoming value.
232  /// Deleted blocks still have successor info, but their predecessor edges and
233  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
234  /// deleted after this call.
235  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
236 
237  /// Instruction I will be changed to an unreachable. Remove all accesses in
238  /// I's block that follow I (inclusive), and update the Phis in the blocks'
239  /// successors.
240  void changeToUnreachable(const Instruction *I);
241 
242  /// Get handle on MemorySSA.
243  MemorySSA* getMemorySSA() const { return MSSA; }
244 
245 private:
246  // Move What before Where in the MemorySSA IR.
247  template <class WhereType>
248  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
249  // Move all memory accesses from `From` to `To` starting at `Start`.
250  // Restrictions apply, see public wrappers of this method.
251  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
252  MemoryAccess *getPreviousDef(MemoryAccess *);
253  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
254  MemoryAccess *
255  getPreviousDefFromEnd(BasicBlock *,
257  MemoryAccess *
258  getPreviousDefRecursive(BasicBlock *,
260  MemoryAccess *recursePhi(MemoryAccess *Phi);
261  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
262  template <class RangeType>
263  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
264  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
265  void fixupDefs(const SmallVectorImpl<WeakVH> &);
266  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
267  // instructions and blocks cloned, and a map of MemoryPhi : Definition
268  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
269  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
270  // caller of this private method, and maps existing MemoryPhis to new
271  // definitions that new MemoryAccesses must point to. These definitions may
272  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
273  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
274  // may be MemoryPhis or MemoryDefs and not MemoryUses.
275  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
276  // the clone involved simplifications that may have: (1) turned a MemoryUse
277  // into an instruction that MemorySSA has no representation for, or (2) turned
278  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
279  // representation for. No other cases are supported.
280  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
281  const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
282  bool CloneWasSimplified = false);
283  template <typename Iter>
284  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
285  Iter ValuesBegin, Iter ValuesEnd,
286  DominatorTree &DT);
288  const GraphDiff<BasicBlock *> *GD);
289 };
290 } // end namespace llvm
291 
292 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
llvm::MemorySSAUpdater::MemorySSAUpdater
MemorySSAUpdater(MemorySSA *MSSA)
Definition: MemorySSAUpdater.h:67
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
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:1436
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
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:1371
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1246
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:483
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:319
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:808
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:1428
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:636
CFGDiff.h
llvm::MemorySSAUpdater::insertUse
void insertUse(MemoryUse *Use, bool RenameUses=false)
Definition: MemorySSAUpdater.cpp:245
llvm::MemorySSAUpdater::moveAfter
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1195
llvm::MemorySSAUpdater::updateForClonedBlockIntoPred
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
Definition: MemorySSAUpdater.cpp:755
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1199
llvm::Instruction
Definition: Instruction.h:45
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:537
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:78
llvm::MemorySSAUpdater::applyInsertUpdates
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
Definition: MemorySSAUpdater.cpp:859
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:530
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:55
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:243
llvm::MemorySSAUpdater::changeToUnreachable
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1407
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:675
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
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:721
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
Definition: MemorySSAUpdater.h:223
llvm::MemoryDef
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:376
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:792
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:1446
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:313
llvm::MemoryAccess
Definition: MemorySSA.h:136
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:786
llvm::MemorySSAUpdater::moveBefore
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1190
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:1267
llvm::MemorySSAUpdater::moveAllAfterMergeBlocks
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1257
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:246
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:43
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:1304
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
SmallSet.h