1 //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // \file 11 // 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 16 // API. 17 // 18 // Basic API usage: 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 23 // MemoryDef. 24 // That's it. 25 // 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. 29 // 30 //===----------------------------------------------------------------------===// 31 32 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H 33 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H 34 35 #include "llvm/ADT/SmallPtrSet.h" 36 #include "llvm/ADT/SmallSet.h" 37 #include "llvm/ADT/SmallVector.h" 38 #include "llvm/Analysis/MemorySSA.h" 39 #include "llvm/IR/BasicBlock.h" 40 #include "llvm/IR/Dominators.h" 41 #include "llvm/IR/Module.h" 42 #include "llvm/IR/OperandTraits.h" 43 #include "llvm/IR/Type.h" 44 #include "llvm/IR/Use.h" 45 #include "llvm/IR/User.h" 46 #include "llvm/IR/Value.h" 47 #include "llvm/IR/ValueHandle.h" 48 #include "llvm/Pass.h" 49 #include "llvm/Support/Casting.h" 50 #include "llvm/Support/ErrorHandling.h" 51 52 namespace llvm { 53 54 class Function; 55 class Instruction; 56 class MemoryAccess; 57 class LLVMContext; 58 class raw_ostream; 59 60 class MemorySSAUpdater { 61 private: 62 MemorySSA *MSSA; 63 64 /// We use WeakVH rather than a costly deletion to deal with dangling pointers. 65 /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. 66 SmallVector<WeakVH, 16> InsertedPHIs; 67 68 SmallPtrSet<BasicBlock *, 8> VisitedBlocks; 69 SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis; 70 71 public: MemorySSAUpdater(MemorySSA * MSSA)72 MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} 73 /// Insert a definition into the MemorySSA IR. RenameUses will rename any use 74 /// below the new def block (and any inserted phis). RenameUses should be set 75 /// to true if the definition may cause new aliases for loads below it. This 76 /// is not the case for hoisting or sinking or other forms of code *movement*. 77 /// It *is* the case for straight code insertion. 78 /// For example: 79 /// store a 80 /// if (foo) { } 81 /// load a 82 /// 83 /// Moving the store into the if block, and calling insertDef, does not 84 /// require RenameUses. 85 /// However, changing it to: 86 /// store a 87 /// if (foo) { store b } 88 /// load a 89 /// Where a mayalias b, *does* require RenameUses be set to true. 90 void insertDef(MemoryDef *Def, bool RenameUses = false); 91 void insertUse(MemoryUse *Use); 92 void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); 93 void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); 94 void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, 95 MemorySSA::InsertionPlace Where); 96 /// `From` block was spliced into `From` and `To`. 97 /// Move all accesses from `From` to `To` starting at instruction `Start`. 98 /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses. 99 /// Edges are already updated, so successors of `To` with MPhi nodes need to 100 /// update incoming block. 101 /// |------| |------| 102 /// | From | | From | 103 /// | | |------| 104 /// | | || 105 /// | | => \/ 106 /// | | |------| <- Start 107 /// | | | To | 108 /// |------| |------| 109 void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, 110 Instruction *Start); 111 /// `From` block was merged into `To`. All instructions were moved and 112 /// `From` is an empty block with successor edges; `From` is about to be 113 /// deleted. Move all accesses from `From` to `To` starting at instruction 114 /// `Start`. `To` may have multiple successors, `From` has a single 115 /// predecessor. `From` may have successors with MPhi nodes, replace their 116 /// incoming block with `To`. 117 /// |------| |------| 118 /// | To | | To | 119 /// |------| | | 120 /// || => | | 121 /// \/ | | 122 /// |------| | | <- Start 123 /// | From | | | 124 /// |------| |------| 125 void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, 126 Instruction *Start); 127 /// BasicBlock Old had New, an empty BasicBlock, added directly before it, 128 /// and the predecessors in Preds that used to point to Old, now point to 129 /// New. If New is the only predecessor, move Old's Phi, if present, to New. 130 /// Otherwise, add a new Phi in New with appropriate incoming values, and 131 /// update the incoming values in Old's Phi node too, if present. 132 void 133 wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, 134 ArrayRef<BasicBlock *> Preds); 135 136 // The below are utility functions. Other than creation of accesses to pass 137 // to insertDef, and removeAccess to remove accesses, you should generally 138 // not attempt to update memoryssa yourself. It is very non-trivial to get 139 // the edge cases right, and the above calls already operate in near-optimal 140 // time bounds. 141 142 /// Create a MemoryAccess in MemorySSA at a specified point in a block, 143 /// with a specified clobbering definition. 144 /// 145 /// Returns the new MemoryAccess. 146 /// This should be called when a memory instruction is created that is being 147 /// used to replace an existing memory instruction. It will *not* create PHI 148 /// nodes, or verify the clobbering definition. The insertion place is used 149 /// solely to determine where in the memoryssa access lists the instruction 150 /// will be placed. The caller is expected to keep ordering the same as 151 /// instructions. 152 /// It will return the new MemoryAccess. 153 /// Note: If a MemoryAccess already exists for I, this function will make it 154 /// inaccessible and it *must* have removeMemoryAccess called on it. 155 MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, 156 const BasicBlock *BB, 157 MemorySSA::InsertionPlace Point); 158 159 /// Create a MemoryAccess in MemorySSA before or after an existing 160 /// MemoryAccess. 161 /// 162 /// Returns the new MemoryAccess. 163 /// This should be called when a memory instruction is created that is being 164 /// used to replace an existing memory instruction. It will *not* create PHI 165 /// nodes, or verify the clobbering definition. 166 /// 167 /// Note: If a MemoryAccess already exists for I, this function will make it 168 /// inaccessible and it *must* have removeMemoryAccess called on it. 169 MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, 170 MemoryAccess *Definition, 171 MemoryUseOrDef *InsertPt); 172 MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, 173 MemoryAccess *Definition, 174 MemoryAccess *InsertPt); 175 176 /// Remove a MemoryAccess from MemorySSA, including updating all 177 /// definitions and uses. 178 /// This should be called when a memory instruction that has a MemoryAccess 179 /// associated with it is erased from the program. For example, if a store or 180 /// load is simply erased (not replaced), removeMemoryAccess should be called 181 /// on the MemoryAccess for that store/load. 182 void removeMemoryAccess(MemoryAccess *); 183 184 /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. 185 /// This should be called when an instruction (load/store) is deleted from 186 /// the program. removeMemoryAccess(const Instruction * I)187 void removeMemoryAccess(const Instruction *I) { 188 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) 189 removeMemoryAccess(MA); 190 } 191 192 /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. 193 /// Assumption we make here: all uses of deleted defs and phi must either 194 /// occur in blocks about to be deleted (thus will be deleted as well), or 195 /// they occur in phis that will simply lose an incoming value. 196 /// Deleted blocks still have successor info, but their predecessor edges and 197 /// Phi nodes may already be updated. Instructions in DeadBlocks should be 198 /// deleted after this call. 199 void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks); 200 201 /// Get handle on MemorySSA. getMemorySSA()202 MemorySSA* getMemorySSA() const { return MSSA; } 203 204 private: 205 // Move What before Where in the MemorySSA IR. 206 template <class WhereType> 207 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); 208 // Move all memory accesses from `From` to `To` starting at `Start`. 209 // Restrictions apply, see public wrappers of this method. 210 void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); 211 MemoryAccess *getPreviousDef(MemoryAccess *); 212 MemoryAccess *getPreviousDefInBlock(MemoryAccess *); 213 MemoryAccess * 214 getPreviousDefFromEnd(BasicBlock *, 215 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 216 MemoryAccess * 217 getPreviousDefRecursive(BasicBlock *, 218 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 219 MemoryAccess *recursePhi(MemoryAccess *Phi); 220 template <class RangeType> 221 MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); 222 void fixupDefs(const SmallVectorImpl<WeakVH> &); 223 }; 224 } // end namespace llvm 225 226 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H 227