LLVM  14.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/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>
44 namespace llvm {
46 class BasicBlock;
47 class BranchInst;
48 class DominatorTree;
49 class Instruction;
50 class LoopBlocksRPO;
57 private:
58  MemorySSA *MSSA;
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;
64  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
65  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
67 public:
68  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
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);
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.
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.
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,
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);
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);
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  }
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);
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);
243  /// Get handle on MemorySSA.
244  MemorySSA* getMemorySSA() const { return MSSA; }
246 private:
247  // Move What before Where in the MemorySSA IR.
248  template <class WhereType>
249  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
250  // Move all memory accesses from `From` to `To` starting at `Start`.
251  // Restrictions apply, see public wrappers of this method.
252  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
253  MemoryAccess *getPreviousDef(MemoryAccess *);
254  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
255  MemoryAccess *
256  getPreviousDefFromEnd(BasicBlock *,
258  MemoryAccess *
259  getPreviousDefRecursive(BasicBlock *,
261  MemoryAccess *recursePhi(MemoryAccess *Phi);
262  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
263  template <class RangeType>
264  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
265  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
266  void fixupDefs(const SmallVectorImpl<WeakVH> &);
267  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
268  // instructions and blocks cloned, and a map of MemoryPhi : Definition
269  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
270  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
271  // caller of this private method, and maps existing MemoryPhis to new
272  // definitions that new MemoryAccesses must point to. These definitions may
273  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
274  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
275  // may be MemoryPhis or MemoryDefs and not MemoryUses.
276  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
277  // the clone involved simplifications that may have: (1) turned a MemoryUse
278  // into an instruction that MemorySSA has no representation for, or (2) turned
279  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
280  // representation for. No other cases are supported.
281  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
282  const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
283  bool CloneWasSimplified = false);
284  template <typename Iter>
285  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
286  Iter ValuesBegin, Iter ValuesEnd,
287  DominatorTree &DT);
289  const GraphDiff<BasicBlock *> *GD);
290 };
291 } // end namespace llvm
MemorySSAUpdater(MemorySSA *MSSA)
Definition: MemorySSAUpdater.h:68
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
@ 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:1441
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:1376
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
Definition: MemorySSAUpdater.cpp:1251
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:484
Represents read-only accesses to memory.
Definition: MemorySSA.h:320
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:1433
Definition: CFGDiff.h:57
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:245
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Definition: MemorySSAUpdater.cpp:1200
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:1204
Definition: Instruction.h:45
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:78
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:56
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
Definition: MemorySSAUpdater.h:244
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1412
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:705
#define I(x, y, z)
Definition: MD5.cpp:59
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:722
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
Definition: MemorySSAUpdater.h:224
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:377
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:793
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Definition: MemorySSAUpdater.cpp:1451
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:314
Definition: MemorySSA.h:137
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:1195
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:1272
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Definition: MemorySSAUpdater.cpp:1262
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:247
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
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:1309
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44