LLVM  10.0.0svn
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"
38 #include "llvm/Analysis/LoopInfo.h"
41 #include "llvm/IR/BasicBlock.h"
42 #include "llvm/IR/CFGDiff.h"
43 #include "llvm/IR/Dominators.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/OperandTraits.h"
46 #include "llvm/IR/Type.h"
47 #include "llvm/IR/Use.h"
48 #include "llvm/IR/User.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/IR/ValueHandle.h"
51 #include "llvm/IR/ValueMap.h"
52 #include "llvm/Pass.h"
53 #include "llvm/Support/Casting.h"
55 
56 namespace llvm {
57 
58 class Function;
59 class Instruction;
60 class MemoryAccess;
61 class LLVMContext;
62 class raw_ostream;
63 
67 using GraphDiffInvBBPair =
68  std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
69 
71 private:
72  MemorySSA *MSSA;
73 
74  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
75  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
76  SmallVector<WeakVH, 16> InsertedPHIs;
77 
78  SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
79  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
80 
81 public:
82  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
83 
84  /// Insert a definition into the MemorySSA IR. RenameUses will rename any use
85  /// below the new def block (and any inserted phis). RenameUses should be set
86  /// to true if the definition may cause new aliases for loads below it. This
87  /// is not the case for hoisting or sinking or other forms of code *movement*.
88  /// It *is* the case for straight code insertion.
89  /// For example:
90  /// store a
91  /// if (foo) { }
92  /// load a
93  ///
94  /// Moving the store into the if block, and calling insertDef, does not
95  /// require RenameUses.
96  /// However, changing it to:
97  /// store a
98  /// if (foo) { store b }
99  /// load a
100  /// Where a mayalias b, *does* require RenameUses be set to true.
101  void insertDef(MemoryDef *Def, bool RenameUses = false);
102  void insertUse(MemoryUse *Use, bool RenameUses = false);
103  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
104  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
105  void removeEdge(BasicBlock *From, BasicBlock *To);
106  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
107  /// following a CFG change that replaced multiple edges (switch) with a direct
108  /// branch.
110  const BasicBlock *To);
111  /// Update MemorySSA when inserting a unique backedge block for a loop.
113  BasicBlock *LoopPreheader,
114  BasicBlock *BackedgeBlock);
115  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
116  /// the exit blocks and a 1:1 mapping of all blocks and instructions
117  /// cloned. This involves duplicating all defs and uses in the cloned blocks
118  /// Updating phi nodes in exit block successors is done separately.
119  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
120  ArrayRef<BasicBlock *> ExitBlocks,
121  const ValueToValueMapTy &VM,
122  bool IgnoreIncomingWithNoClones = false);
123  // Block BB was fully or partially cloned into its predecessor P1. Map
124  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
126  const ValueToValueMapTy &VM);
127  /// Update phi nodes in exit block successors following cloning. Exit blocks
128  /// that were not cloned don't have additional predecessors added.
130  const ValueToValueMapTy &VMap,
131  DominatorTree &DT);
133  ArrayRef<BasicBlock *> ExitBlocks,
134  ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
135 
136  /// Apply CFG updates, analogous with the DT edge updates.
138  /// Apply CFG insert updates, analogous with the DT edge updates.
140 
141  void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
142  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
143  void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
145  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
146  /// `From` to `To`. Move all accesses from `From` to `To` starting at
147  /// instruction `Start`. `To` is newly created BB, so empty of
148  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
149  /// `To` with MPhi nodes need to update incoming block.
150  /// |------| |------|
151  /// | From | | From |
152  /// | | |------|
153  /// | | ||
154  /// | | => \/
155  /// | | |------| <- Start
156  /// | | | To |
157  /// |------| |------|
159  Instruction *Start);
160  /// `From` block was merged into `To`. There is a CFG edge from `To` to
161  /// `From`.`To` still branches to `From`, but all instructions were moved and
162  /// `From` is now an empty block; `From` is about to be deleted. Move all
163  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
164  /// have multiple successors, `From` has a single predecessor. `From` may have
165  /// successors with MPhi nodes, replace their incoming block with `To`.
166  /// |------| |------|
167  /// | To | | To |
168  /// |------| | |
169  /// || => | |
170  /// \/ | |
171  /// |------| | | <- Start
172  /// | From | | |
173  /// |------| |------|
175  Instruction *Start);
176  /// A new empty BasicBlock (New) now branches directly to Old. Some of
177  /// Old's predecessors (Preds) are now branching to New instead of Old.
178  /// If New is the only predecessor, move Old's Phi, if present, to New.
179  /// Otherwise, add a new Phi in New with appropriate incoming values, and
180  /// update the incoming values in Old's Phi node too, if present.
182  BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
183  bool IdenticalEdgesWereMerged = true);
184  // The below are utility functions. Other than creation of accesses to pass
185  // to insertDef, and removeAccess to remove accesses, you should generally
186  // not attempt to update memoryssa yourself. It is very non-trivial to get
187  // the edge cases right, and the above calls already operate in near-optimal
188  // time bounds.
189 
190  /// Create a MemoryAccess in MemorySSA at a specified point in a block,
191  /// with a specified clobbering definition.
192  ///
193  /// Returns the new MemoryAccess.
194  /// This should be called when a memory instruction is created that is being
195  /// used to replace an existing memory instruction. It will *not* create PHI
196  /// nodes, or verify the clobbering definition. The insertion place is used
197  /// solely to determine where in the memoryssa access lists the instruction
198  /// will be placed. The caller is expected to keep ordering the same as
199  /// instructions.
200  /// It will return the new MemoryAccess.
201  /// Note: If a MemoryAccess already exists for I, this function will make it
202  /// inaccessible and it *must* have removeMemoryAccess called on it.
204  const BasicBlock *BB,
206 
207  /// Create a MemoryAccess in MemorySSA before or after an existing
208  /// MemoryAccess.
209  ///
210  /// Returns the new MemoryAccess.
211  /// This should be called when a memory instruction is created that is being
212  /// used to replace an existing memory instruction. It will *not* create PHI
213  /// nodes, or verify the clobbering definition.
214  ///
215  /// Note: If a MemoryAccess already exists for I, this function will make it
216  /// inaccessible and it *must* have removeMemoryAccess called on it.
218  MemoryAccess *Definition,
219  MemoryUseOrDef *InsertPt);
221  MemoryAccess *Definition,
222  MemoryAccess *InsertPt);
223 
224  /// Remove a MemoryAccess from MemorySSA, including updating all
225  /// definitions and uses.
226  /// This should be called when a memory instruction that has a MemoryAccess
227  /// associated with it is erased from the program. For example, if a store or
228  /// load is simply erased (not replaced), removeMemoryAccess should be called
229  /// on the MemoryAccess for that store/load.
230  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);
231 
232  /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
233  /// This should be called when an instruction (load/store) is deleted from
234  /// the program.
235  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
236  if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
237  removeMemoryAccess(MA, OptimizePhis);
238  }
239 
240  /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
241  /// Assumption we make here: all uses of deleted defs and phi must either
242  /// occur in blocks about to be deleted (thus will be deleted as well), or
243  /// they occur in phis that will simply lose an incoming value.
244  /// Deleted blocks still have successor info, but their predecessor edges and
245  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
246  /// deleted after this call.
247  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
248 
249  /// Instruction I will be changed to an unreachable. Remove all accesses in
250  /// I's block that follow I (inclusive), and update the Phis in the blocks'
251  /// successors.
252  void changeToUnreachable(const Instruction *I);
253 
254  /// Conditional branch BI is changed or replaced with an unconditional branch
255  /// to `To`. Update Phis in BI's successors to remove BI's BB.
257  const BasicBlock *To);
258 
259  /// Get handle on MemorySSA.
260  MemorySSA* getMemorySSA() const { return MSSA; }
261 
262 private:
263  // Move What before Where in the MemorySSA IR.
264  template <class WhereType>
265  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
266  // Move all memory accesses from `From` to `To` starting at `Start`.
267  // Restrictions apply, see public wrappers of this method.
268  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
269  MemoryAccess *getPreviousDef(MemoryAccess *);
270  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
271  MemoryAccess *
272  getPreviousDefFromEnd(BasicBlock *,
274  MemoryAccess *
275  getPreviousDefRecursive(BasicBlock *,
277  MemoryAccess *recursePhi(MemoryAccess *Phi);
278  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
279  template <class RangeType>
280  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
281  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
282  void fixupDefs(const SmallVectorImpl<WeakVH> &);
283  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
284  // instructions and blocks cloned, and a map of MemoryPhi : Definition
285  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
286  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
287  // caller of this private method, and maps existing MemoryPhis to new
288  // definitions that new MemoryAccesses must point to. These definitions may
289  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
290  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
291  // may be MemoryPhis or MemoryDefs and not MemoryUses.
292  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
293  // the clone involved simplifications that may have: (1) turned a MemoryUse
294  // into an instruction that MemorySSA has no representation for, or (2) turned
295  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
296  // representation for. No other cases are supported.
297  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
298  const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
299  bool CloneWasSimplified = false);
300  template <typename Iter>
301  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
302  Iter ValuesBegin, Iter ValuesEnd,
303  DominatorTree &DT);
305  const GraphDiff<BasicBlock *> *GD);
306 };
307 } // end namespace llvm
308 
309 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
void insertUse(MemoryUse *Use, bool RenameUses=false)
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:375
std::pair< const GraphDiff< BasicBlock * > *, Inverse< BasicBlock * > > GraphDiffInvBBPair
This defines the Use class.
Represents read-only accesses to memory.
Definition: MemorySSA.h:319
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG updates, analogous with the DT edge updates.
mir Rename Register Operands
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:720
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Conditional or Unconditional Branch instruction.
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:327
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...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void removeMemoryAccess(const Instruction *I, bool OptimizePhis=false)
Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
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...
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...
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:247
#define I(x, y, z)
Definition: MD5.cpp:58
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
MemorySSAUpdater(MemorySSA *MSSA)
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:481
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
void changeCondBranchToUnconditionalTo(const BranchInst *BI, const BasicBlock *To)
Conditional branch BI is changed or replaced with an unconditional branch to To.