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/LoopInfo.h" 39 #include "llvm/Analysis/LoopIterator.h" 40 #include "llvm/Analysis/MemorySSA.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" 54 #include "llvm/Support/ErrorHandling.h" 55 56 namespace llvm { 57 58 class Function; 59 class Instruction; 60 class MemoryAccess; 61 class LLVMContext; 62 class raw_ostream; 63 64 using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; 65 using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>; 66 using CFGUpdate = cfg::Update<BasicBlock *>; 67 using GraphDiffInvBBPair = 68 std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>; 69 70 class MemorySSAUpdater { 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: MemorySSAUpdater(MemorySSA * MSSA)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); 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. 109 void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To); 110 /// Update MemorySSA after a loop was cloned, given the blocks in RPO order, 111 /// the exit blocks and a 1:1 mapping of all blocks and instructions 112 /// cloned. This involves duplicating all defs and uses in the cloned blocks 113 /// Updating phi nodes in exit block successors is done separately. 114 void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, 115 ArrayRef<BasicBlock *> ExitBlocks, 116 const ValueToValueMapTy &VM, 117 bool IgnoreIncomingWithNoClones = false); 118 // Block BB was fully or partially cloned into its predecessor P1. Map 119 // contains the 1:1 mapping of instructions cloned and VM[BB]=P1. 120 void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, 121 const ValueToValueMapTy &VM); 122 /// Update phi nodes in exit block successors following cloning. Exit blocks 123 /// that were not cloned don't have additional predecessors added. 124 void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 125 const ValueToValueMapTy &VMap, 126 DominatorTree &DT); 127 void updateExitBlocksForClonedLoop( 128 ArrayRef<BasicBlock *> ExitBlocks, 129 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT); 130 131 /// Apply CFG updates, analogous with the DT edge updates. 132 void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT); 133 /// Apply CFG insert updates, analogous with the DT edge updates. 134 void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT); 135 136 void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); 137 void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); 138 void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, 139 MemorySSA::InsertionPlace Where); 140 /// `From` block was spliced into `From` and `To`. There is a CFG edge from 141 /// `From` to `To`. Move all accesses from `From` to `To` starting at 142 /// instruction `Start`. `To` is newly created BB, so empty of 143 /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of 144 /// `To` with MPhi nodes need to update incoming block. 145 /// |------| |------| 146 /// | From | | From | 147 /// | | |------| 148 /// | | || 149 /// | | => \/ 150 /// | | |------| <- Start 151 /// | | | To | 152 /// |------| |------| 153 void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, 154 Instruction *Start); 155 /// `From` block was merged into `To`. There is a CFG edge from `To` to 156 /// `From`.`To` still branches to `From`, but all instructions were moved and 157 /// `From` is now an empty block; `From` is about to be deleted. Move all 158 /// accesses from `From` to `To` starting at instruction `Start`. `To` may 159 /// have multiple successors, `From` has a single predecessor. `From` may have 160 /// successors with MPhi nodes, replace their incoming block with `To`. 161 /// |------| |------| 162 /// | To | | To | 163 /// |------| | | 164 /// || => | | 165 /// \/ | | 166 /// |------| | | <- Start 167 /// | From | | | 168 /// |------| |------| 169 void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, 170 Instruction *Start); 171 /// A new empty BasicBlock (New) now branches directly to Old. Some of 172 /// Old's predecessors (Preds) are now branching to New instead of Old. 173 /// If New is the only predecessor, move Old's Phi, if present, to New. 174 /// Otherwise, add a new Phi in New with appropriate incoming values, and 175 /// update the incoming values in Old's Phi node too, if present. 176 void wireOldPredecessorsToNewImmediatePredecessor( 177 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds, 178 bool IdenticalEdgesWereMerged = true); 179 // The below are utility functions. Other than creation of accesses to pass 180 // to insertDef, and removeAccess to remove accesses, you should generally 181 // not attempt to update memoryssa yourself. It is very non-trivial to get 182 // the edge cases right, and the above calls already operate in near-optimal 183 // time bounds. 184 185 /// Create a MemoryAccess in MemorySSA at a specified point in a block, 186 /// with a specified clobbering definition. 187 /// 188 /// Returns the new MemoryAccess. 189 /// This should be called when a memory instruction is created that is being 190 /// used to replace an existing memory instruction. It will *not* create PHI 191 /// nodes, or verify the clobbering definition. The insertion place is used 192 /// solely to determine where in the memoryssa access lists the instruction 193 /// will be placed. The caller is expected to keep ordering the same as 194 /// instructions. 195 /// It will return the new MemoryAccess. 196 /// Note: If a MemoryAccess already exists for I, this function will make it 197 /// inaccessible and it *must* have removeMemoryAccess called on it. 198 MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, 199 const BasicBlock *BB, 200 MemorySSA::InsertionPlace Point); 201 202 /// Create a MemoryAccess in MemorySSA before or after an existing 203 /// MemoryAccess. 204 /// 205 /// Returns the new MemoryAccess. 206 /// This should be called when a memory instruction is created that is being 207 /// used to replace an existing memory instruction. It will *not* create PHI 208 /// nodes, or verify the clobbering definition. 209 /// 210 /// Note: If a MemoryAccess already exists for I, this function will make it 211 /// inaccessible and it *must* have removeMemoryAccess called on it. 212 MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, 213 MemoryAccess *Definition, 214 MemoryUseOrDef *InsertPt); 215 MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, 216 MemoryAccess *Definition, 217 MemoryAccess *InsertPt); 218 219 /// Remove a MemoryAccess from MemorySSA, including updating all 220 /// definitions and uses. 221 /// This should be called when a memory instruction that has a MemoryAccess 222 /// associated with it is erased from the program. For example, if a store or 223 /// load is simply erased (not replaced), removeMemoryAccess should be called 224 /// on the MemoryAccess for that store/load. 225 void removeMemoryAccess(MemoryAccess *); 226 227 /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. 228 /// This should be called when an instruction (load/store) is deleted from 229 /// the program. removeMemoryAccess(const Instruction * I)230 void removeMemoryAccess(const Instruction *I) { 231 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) 232 removeMemoryAccess(MA); 233 } 234 235 /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. 236 /// Assumption we make here: all uses of deleted defs and phi must either 237 /// occur in blocks about to be deleted (thus will be deleted as well), or 238 /// they occur in phis that will simply lose an incoming value. 239 /// Deleted blocks still have successor info, but their predecessor edges and 240 /// Phi nodes may already be updated. Instructions in DeadBlocks should be 241 /// deleted after this call. 242 void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks); 243 244 /// Get handle on MemorySSA. getMemorySSA()245 MemorySSA* getMemorySSA() const { return MSSA; } 246 247 private: 248 // Move What before Where in the MemorySSA IR. 249 template <class WhereType> 250 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); 251 // Move all memory accesses from `From` to `To` starting at `Start`. 252 // Restrictions apply, see public wrappers of this method. 253 void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); 254 MemoryAccess *getPreviousDef(MemoryAccess *); 255 MemoryAccess *getPreviousDefInBlock(MemoryAccess *); 256 MemoryAccess * 257 getPreviousDefFromEnd(BasicBlock *, 258 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 259 MemoryAccess * 260 getPreviousDefRecursive(BasicBlock *, 261 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 262 MemoryAccess *recursePhi(MemoryAccess *Phi); 263 template <class RangeType> 264 MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); 265 void fixupDefs(const SmallVectorImpl<WeakVH> &); 266 // Clone all uses and defs from BB to NewBB given a 1:1 map of all 267 // instructions and blocks cloned, and a map of MemoryPhi : Definition 268 // (MemoryAccess Phi or Def). VMap maps old instructions to cloned 269 // instructions and old blocks to cloned blocks. MPhiMap, is created in the 270 // caller of this private method, and maps existing MemoryPhis to new 271 // definitions that new MemoryAccesses must point to. These definitions may 272 // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such, 273 // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses 274 // may be MemoryPhis or MemoryDefs and not MemoryUses. 275 void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, 276 const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap); 277 template <typename Iter> 278 void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 279 Iter ValuesBegin, Iter ValuesEnd, 280 DominatorTree &DT); 281 void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT, 282 const GraphDiff<BasicBlock *> *GD); 283 }; 284 } // end namespace llvm 285 286 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H 287