LLVM  13.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 BranchInst;
48 class DominatorTree;
49 class Instruction;
50 class LoopBlocksRPO;
51 
55 
57 private:
58  MemorySSA *MSSA;
59 
60  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
61  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
62  SmallVector<WeakVH, 16> InsertedPHIs;
63 
64  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
65  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
66 
67 public:
68  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
69 
70  /// Insert a definition into the MemorySSA IR. RenameUses will rename any use
71  /// below the new def block (and any inserted phis). RenameUses should be set
72  /// to true if the definition may cause new aliases for loads below it. This
73  /// is not the case for hoisting or sinking or other forms of code *movement*.
74  /// It *is* the case for straight code insertion.
75  /// For example:
76  /// store a
77  /// if (foo) { }
78  /// load a
79  ///
80  /// Moving the store into the if block, and calling insertDef, does not
81  /// require RenameUses.
82  /// However, changing it to:
83  /// store a
84  /// if (foo) { store b }
85  /// load a
86  /// Where a mayalias b, *does* require RenameUses be set to true.
87  void insertDef(MemoryDef *Def, bool RenameUses = false);
88  void insertUse(MemoryUse *Use, bool RenameUses = false);
89  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
90  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
92  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
93  /// following a CFG change that replaced multiple edges (switch) with a direct
94  /// branch.
96  const BasicBlock *To);
97  /// Update MemorySSA when inserting a unique backedge block for a loop.
99  BasicBlock *LoopPreheader,
100  BasicBlock *BackedgeBlock);
101  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
102  /// the exit blocks and a 1:1 mapping of all blocks and instructions
103  /// cloned. This involves duplicating all defs and uses in the cloned blocks
104  /// Updating phi nodes in exit block successors is done separately.
105  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
106  ArrayRef<BasicBlock *> ExitBlocks,
107  const ValueToValueMapTy &VM,
108  bool IgnoreIncomingWithNoClones = false);
109  // Block BB was fully or partially cloned into its predecessor P1. Map
110  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
112  const ValueToValueMapTy &VM);
113  /// Update phi nodes in exit block successors following cloning. Exit blocks
114  /// that were not cloned don't have additional predecessors added.
116  const ValueToValueMapTy &VMap,
117  DominatorTree &DT);
119  ArrayRef<BasicBlock *> ExitBlocks,
120  ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
121 
122  /// Apply CFG updates, analogous with the DT edge updates. By default, the
123  /// DT is assumed to be already up to date. If UpdateDTFirst is true, first
124  /// update the DT with the same updates.
126  bool UpdateDTFirst = false);
127  /// Apply CFG insert updates, analogous with the DT edge updates.
129 
130  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
131  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
134  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
135  /// `From` to `To`. Move all accesses from `From` to `To` starting at
136  /// instruction `Start`. `To` is newly created BB, so empty of
137  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
138  /// `To` with MPhi nodes need to update incoming block.
139  /// |------| |------|
140  /// | From | | From |
141  /// | | |------|
142  /// | | ||
143  /// | | => \/
144  /// | | |------| <- Start
145  /// | | | To |
146  /// |------| |------|
148  Instruction *Start);
149  /// `From` block was merged into `To`. There is a CFG edge from `To` to
150  /// `From`.`To` still branches to `From`, but all instructions were moved and
151  /// `From` is now an empty block; `From` is about to be deleted. Move all
152  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
153  /// have multiple successors, `From` has a single predecessor. `From` may have
154  /// successors with MPhi nodes, replace their incoming block with `To`.
155  /// |------| |------|
156  /// | To | | To |
157  /// |------| | |
158  /// || => | |
159  /// \/ | |
160  /// |------| | | <- Start
161  /// | From | | |
162  /// |------| |------|
164  Instruction *Start);
165  /// A new empty BasicBlock (New) now branches directly to Old. Some of
166  /// Old's predecessors (Preds) are now branching to New instead of Old.
167  /// If New is the only predecessor, move Old's Phi, if present, to New.
168  /// Otherwise, add a new Phi in New with appropriate incoming values, and
169  /// update the incoming values in Old's Phi node too, if present.
171  BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
172  bool IdenticalEdgesWereMerged = true);
173  // The below are utility functions. Other than creation of accesses to pass
174  // to insertDef, and removeAccess to remove accesses, you should generally
175  // not attempt to update memoryssa yourself. It is very non-trivial to get
176  // the edge cases right, and the above calls already operate in near-optimal
177  // time bounds.
178 
179  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
180  /// with a specified clobbering definition.
181  ///
182  /// Returns the new MemoryAccess.
183  /// This should be called when a memory instruction is created that is being
184  /// used to replace an existing memory instruction. It will *not* create PHI
185  /// nodes, or verify the clobbering definition. The insertion place is used
186  /// solely to determine where in the memoryssa access lists the instruction
187  /// will be placed. The caller is expected to keep ordering the same as
188  /// instructions.
189  /// It will return the new MemoryAccess.
190  /// Note: If a MemoryAccess already exists for I, this function will make it
191  /// inaccessible and it *must* have removeMemoryAccess called on it.
193  const BasicBlock *BB,
195 
196  /// Create a MemoryAccess in MemorySSA before or after an existing
197  /// MemoryAccess.
198  ///
199  /// Returns the new MemoryAccess.
200  /// This should be called when a memory instruction is created that is being
201  /// used to replace an existing memory instruction. It will *not* create PHI
202  /// nodes, or verify the clobbering definition.
203  ///
204  /// Note: If a MemoryAccess already exists for I, this function will make it
205  /// inaccessible and it *must* have removeMemoryAccess called on it.
207  MemoryAccess *Definition,
208  MemoryUseOrDef *InsertPt);
210  MemoryAccess *Definition,
211  MemoryAccess *InsertPt);
212 
213  /// Remove a MemoryAccess from MemorySSA, including updating all
214  /// definitions and uses.
215  /// This should be called when a memory instruction that has a MemoryAccess
216  /// associated with it is erased from the program. For example, if a store or
217  /// load is simply erased (not replaced), removeMemoryAccess should be called
218  /// on the MemoryAccess for that store/load.
219  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
220 
221  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
222  /// This should be called when an instruction (load/store) is deleted from
223  /// the program.
224  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
225  if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
226  removeMemoryAccess(MA, OptimizePhis);
227  }
228 
229  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
230  /// Assumption we make here: all uses of deleted defs and phi must either
231  /// occur in blocks about to be deleted (thus will be deleted as well), or
232  /// they occur in phis that will simply lose an incoming value.
233  /// Deleted blocks still have successor info, but their predecessor edges and
234  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
235  /// deleted after this call.
236  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
237 
238  /// Instruction I will be changed to an unreachable. Remove all accesses in
239  /// I's block that follow I (inclusive), and update the Phis in the blocks'
240  /// successors.
241  void changeToUnreachable(const Instruction *I);
242 
243  /// Conditional branch BI is changed or replaced with an unconditional branch
244  /// to `To`. Update Phis in BI's successors to remove BI's BB.
246  const BasicBlock *To);
247 
248  /// Get handle on MemorySSA.
249  MemorySSA* getMemorySSA() const { return MSSA; }
250 
251 private:
252  // Move What before Where in the MemorySSA IR.
253  template <class WhereType>
254  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
255  // Move all memory accesses from `From` to `To` starting at `Start`.
256  // Restrictions apply, see public wrappers of this method.
257  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
258  MemoryAccess *getPreviousDef(MemoryAccess *);
259  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
260  MemoryAccess *
261  getPreviousDefFromEnd(BasicBlock *,
263  MemoryAccess *
264  getPreviousDefRecursive(BasicBlock *,
266  MemoryAccess *recursePhi(MemoryAccess *Phi);
267  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
268  template <class RangeType>
269  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
270  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
271  void fixupDefs(const SmallVectorImpl<WeakVH> &);
272  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
273  // instructions and blocks cloned, and a map of MemoryPhi : Definition
274  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
275  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
276  // caller of this private method, and maps existing MemoryPhis to new
277  // definitions that new MemoryAccesses must point to. These definitions may
278  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
279  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
280  // may be MemoryPhis or MemoryDefs and not MemoryUses.
281  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
282  // the clone involved simplifications that may have: (1) turned a MemoryUse
283  // into an instruction that MemorySSA has no representation for, or (2) turned
284  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
285  // representation for. No other cases are supported.
286  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
287  const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
288  bool CloneWasSimplified = false);
289  template <typename Iter>
290  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
291  Iter ValuesBegin, Iter ValuesEnd,
292  DominatorTree &DT);
294  const GraphDiff<BasicBlock *> *GD);
295 };
296 } // end namespace llvm
297 
298 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
llvm::MemorySSAUpdater::MemorySSAUpdater
MemorySSAUpdater(MemorySSA *MSSA)
Definition: MemorySSAUpdater.h:68
llvm
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:1453
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:151
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:134
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:485
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:323
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:810
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:1445
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:638
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:1196
llvm::MemorySSAUpdater::updateForClonedBlockIntoPred
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
Definition: MemorySSAUpdater.cpp:757
llvm::MemorySSAUpdater::moveToPlace
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
Definition: MemorySSAUpdater.cpp:1200
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:539
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:856
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:532
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:56
llvm::MemorySSAUpdater::getMemorySSA
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:249
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:677
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:59
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:224
llvm::MemoryDef
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:379
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:791
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::MemorySSAUpdater::createMemoryAccessAfter
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Definition: MemorySSAUpdater.cpp:1463
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:314
llvm::MemoryAccess
Definition: MemorySSA.h:140
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:788
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:250
llvm::MemorySSAUpdater::changeCondBranchToUnconditionalTo
void changeCondBranchToUnconditionalTo(const BranchInst *BI, const BasicBlock *To)
Conditional branch BI is changed or replaced with an unconditional branch to To.
Definition: MemorySSAUpdater.cpp:1429
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:27
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::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3007
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
SmallSet.h