1 //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 // \brief An automatic updater for MemorySSA that handles arbitrary insertion,
12 // deletion, and moves. It performs phi insertion where necessary, and
13 // automatically updates the MemorySSA IR to be correct.
14 // While updating loads or removing instructions is often easy enough to not
15 // need this, updating stores should generally not be attemped outside this
19 // Create the memory access you want for the instruction (this is mainly so
20 // we know where it is, without having to duplicate the entire set of create
21 // functions MemorySSA supports).
22 // Call insertDef or insertUse depending on whether it's a MemoryUse or a
26 // For moving, first, move the instruction itself using the normal SSA
27 // instruction moving API, then just call moveBefore, moveAfter,or moveTo with
28 // the right arguments.
30 //===----------------------------------------------------------------------===//
32 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
33 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/Analysis/MemorySSA.h"
38 #include "llvm/IR/BasicBlock.h"
39 #include "llvm/IR/Dominators.h"
40 #include "llvm/IR/Module.h"
41 #include "llvm/IR/OperandTraits.h"
42 #include "llvm/IR/Type.h"
43 #include "llvm/IR/Use.h"
44 #include "llvm/IR/User.h"
45 #include "llvm/IR/Value.h"
46 #include "llvm/Pass.h"
47 #include "llvm/Support/Casting.h"
48 #include "llvm/Support/ErrorHandling.h"
58 class MemorySSAUpdater {
61 SmallVector<MemoryPhi *, 8> InsertedPHIs;
62 SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
65 MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
66 /// Insert a definition into the MemorySSA IR. RenameUses will rename any use
67 /// below the new def block (and any inserted phis). RenameUses should be set
68 /// to true if the definition may cause new aliases for loads below it. This
69 /// is not the case for hoisting or sinking or other forms of code *movement*.
70 /// It *is* the case for straight code insertion.
76 /// Moving the store into the if block, and calling insertDef, does not
77 /// require RenameUses.
78 /// However, changing it to:
80 /// if (foo) { store b }
82 /// Where a mayalias b, *does* require RenameUses be set to true.
83 void insertDef(MemoryDef *Def, bool RenameUses = false);
84 void insertUse(MemoryUse *Use);
85 void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
86 void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
87 void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
88 MemorySSA::InsertionPlace Where);
90 // The below are utility functions. Other than creation of accesses to pass
91 // to insertDef, and removeAccess to remove accesses, you should generally
92 // not attempt to update memoryssa yourself. It is very non-trivial to get
93 // the edge cases right, and the above calls already operate in near-optimal
96 /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block,
97 /// with a specified clobbering definition.
99 /// Returns the new MemoryAccess.
100 /// This should be called when a memory instruction is created that is being
101 /// used to replace an existing memory instruction. It will *not* create PHI
102 /// nodes, or verify the clobbering definition. The insertion place is used
103 /// solely to determine where in the memoryssa access lists the instruction
104 /// will be placed. The caller is expected to keep ordering the same as
106 /// It will return the new MemoryAccess.
107 /// Note: If a MemoryAccess already exists for I, this function will make it
108 /// inaccessible and it *must* have removeMemoryAccess called on it.
109 MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
110 const BasicBlock *BB,
111 MemorySSA::InsertionPlace Point);
113 /// \brief Create a MemoryAccess in MemorySSA before or after an existing
116 /// Returns the new MemoryAccess.
117 /// This should be called when a memory instruction is created that is being
118 /// used to replace an existing memory instruction. It will *not* create PHI
119 /// nodes, or verify the clobbering definition.
121 /// Note: If a MemoryAccess already exists for I, this function will make it
122 /// inaccessible and it *must* have removeMemoryAccess called on it.
123 MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
124 MemoryAccess *Definition,
125 MemoryUseOrDef *InsertPt);
126 MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
127 MemoryAccess *Definition,
128 MemoryAccess *InsertPt);
130 /// \brief Remove a MemoryAccess from MemorySSA, including updating all
131 /// definitions and uses.
132 /// This should be called when a memory instruction that has a MemoryAccess
133 /// associated with it is erased from the program. For example, if a store or
134 /// load is simply erased (not replaced), removeMemoryAccess should be called
135 /// on the MemoryAccess for that store/load.
136 void removeMemoryAccess(MemoryAccess *);
139 // Move What before Where in the MemorySSA IR.
140 template <class WhereType>
141 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
142 MemoryAccess *getPreviousDef(MemoryAccess *);
143 MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
144 MemoryAccess *getPreviousDefFromEnd(BasicBlock *);
145 MemoryAccess *getPreviousDefRecursive(BasicBlock *);
146 MemoryAccess *recursePhi(MemoryAccess *Phi);
147 template <class RangeType>
148 MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
149 void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
151 } // end namespace llvm
153 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H