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/SmallPtrSet.h" 35 #include "llvm/ADT/SmallSet.h" 36 #include "llvm/ADT/SmallVector.h" 37 #include "llvm/Analysis/MemorySSA.h" 38 #include "llvm/IR/ValueHandle.h" 39 #include "llvm/IR/ValueMap.h" 40 #include "llvm/Support/CFGDiff.h" 41 #include "llvm/Support/Compiler.h" 42 43 namespace llvm { 44 45 class BasicBlock; 46 class DominatorTree; 47 class Instruction; 48 class LoopBlocksRPO; 49 template <typename T, unsigned int N> class SmallSetVector; 50 51 using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; 52 using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>; 53 using CFGUpdate = cfg::Update<BasicBlock *>; 54 55 class MemorySSAUpdater { 56 private: 57 MemorySSA *MSSA; 58 59 /// We use WeakVH rather than a costly deletion to deal with dangling pointers. 60 /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. 61 SmallVector<WeakVH, 16> InsertedPHIs; 62 63 SmallPtrSet<BasicBlock *, 8> VisitedBlocks; 64 SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis; 65 66 public: MemorySSAUpdater(MemorySSA * MSSA)67 MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} 68 69 /// Insert a definition into the MemorySSA IR. RenameUses will rename any use 70 /// below the new def block (and any inserted phis). RenameUses should be set 71 /// to true if the definition may cause new aliases for loads below it. This 72 /// is not the case for hoisting or sinking or other forms of code *movement*. 73 /// It *is* the case for straight code insertion. 74 /// For example: 75 /// store a 76 /// if (foo) { } 77 /// load a 78 /// 79 /// Moving the store into the if block, and calling insertDef, does not 80 /// require RenameUses. 81 /// However, changing it to: 82 /// store a 83 /// if (foo) { store b } 84 /// load a 85 /// Where a mayalias b, *does* require RenameUses be set to true. 86 LLVM_ABI void insertDef(MemoryDef *Def, bool RenameUses = false); 87 LLVM_ABI void insertUse(MemoryUse *Use, bool RenameUses = false); 88 /// Update the MemoryPhi in `To` following an edge deletion between `From` and 89 /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made. 90 LLVM_ABI void removeEdge(BasicBlock *From, BasicBlock *To); 91 /// Update the MemoryPhi in `To` to have a single incoming edge from `From`, 92 /// following a CFG change that replaced multiple edges (switch) with a direct 93 /// branch. 94 LLVM_ABI void removeDuplicatePhiEdgesBetween(const BasicBlock *From, 95 const BasicBlock *To); 96 /// Update MemorySSA when inserting a unique backedge block for a loop. 97 LLVM_ABI void 98 updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, 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 LLVM_ABI 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. 111 LLVM_ABI void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *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. 115 LLVM_ABI void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 116 const ValueToValueMapTy &VMap, 117 DominatorTree &DT); 118 LLVM_ABI void updateExitBlocksForClonedLoop( 119 ArrayRef<BasicBlock *> ExitBlocks, 120 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT); 121 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. 125 LLVM_ABI void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT, 126 bool UpdateDTFirst = false); 127 /// Apply CFG insert updates, analogous with the DT edge updates. 128 LLVM_ABI void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, 129 DominatorTree &DT); 130 131 LLVM_ABI void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); 132 LLVM_ABI void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); 133 LLVM_ABI void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, 134 MemorySSA::InsertionPlace Where); 135 /// `From` block was spliced into `From` and `To`. There is a CFG edge from 136 /// `From` to `To`. Move all accesses from `From` to `To` starting at 137 /// instruction `Start`. `To` is newly created BB, so empty of 138 /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of 139 /// `To` with MPhi nodes need to update incoming block. 140 /// |------| |------| 141 /// | From | | From | 142 /// | | |------| 143 /// | | || 144 /// | | => \/ 145 /// | | |------| <- Start 146 /// | | | To | 147 /// |------| |------| 148 LLVM_ABI void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, 149 Instruction *Start); 150 /// `From` block was merged into `To`. There is a CFG edge from `To` to 151 /// `From`.`To` still branches to `From`, but all instructions were moved and 152 /// `From` is now an empty block; `From` is about to be deleted. Move all 153 /// accesses from `From` to `To` starting at instruction `Start`. `To` may 154 /// have multiple successors, `From` has a single predecessor. `From` may have 155 /// successors with MPhi nodes, replace their incoming block with `To`. 156 /// |------| |------| 157 /// | To | | To | 158 /// |------| | | 159 /// || => | | 160 /// \/ | | 161 /// |------| | | <- Start 162 /// | From | | | 163 /// |------| |------| 164 LLVM_ABI void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, 165 Instruction *Start); 166 /// A new empty BasicBlock (New) now branches directly to Old. Some of 167 /// Old's predecessors (Preds) are now branching to New instead of Old. 168 /// If New is the only predecessor, move Old's Phi, if present, to New. 169 /// Otherwise, add a new Phi in New with appropriate incoming values, and 170 /// update the incoming values in Old's Phi node too, if present. 171 LLVM_ABI void wireOldPredecessorsToNewImmediatePredecessor( 172 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds, 173 bool IdenticalEdgesWereMerged = true); 174 // The below are utility functions. Other than creation of accesses to pass 175 // to insertDef, and removeAccess to remove accesses, you should generally 176 // not attempt to update memoryssa yourself. It is very non-trivial to get 177 // the edge cases right, and the above calls already operate in near-optimal 178 // time bounds. 179 180 /// Create a MemoryAccess in MemorySSA at a specified point in a block. 181 /// 182 /// When used by itself, this method will only insert the new MemoryAccess 183 /// into the access list, but not make any other changes, such as inserting 184 /// MemoryPHI nodes, or updating users to point to the new MemoryAccess. You 185 /// must specify a correct Definition in this case. 186 /// 187 /// Usually, this API is instead combined with insertUse() or insertDef(), 188 /// which will perform all the necessary MSSA updates. If these APIs are used, 189 /// then nullptr can be used as Definition, as the correct defining access 190 /// will be automatically determined. 191 /// 192 /// Note: If a MemoryAccess already exists for I, this function will make it 193 /// inaccessible and it *must* have removeMemoryAccess called on it. 194 LLVM_ABI MemoryAccess * 195 createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, 196 const BasicBlock *BB, MemorySSA::InsertionPlace Point, 197 bool CreationMustSucceed = true); 198 199 /// Create a MemoryAccess in MemorySSA before an existing MemoryAccess. 200 /// 201 /// See createMemoryAccessInBB() for usage details. 202 LLVM_ABI MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, 203 MemoryAccess *Definition, 204 MemoryUseOrDef *InsertPt); 205 /// Create a MemoryAccess in MemorySSA after an existing MemoryAccess. 206 /// 207 /// See createMemoryAccessInBB() for usage details. 208 LLVM_ABI MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, 209 MemoryAccess *Definition, 210 MemoryAccess *InsertPt); 211 212 /// Remove a MemoryAccess from MemorySSA, including updating all 213 /// definitions and uses. 214 /// This should be called when a memory instruction that has a MemoryAccess 215 /// associated with it is erased from the program. For example, if a store or 216 /// load is simply erased (not replaced), removeMemoryAccess should be called 217 /// on the MemoryAccess for that store/load. 218 LLVM_ABI void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false); 219 220 /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. 221 /// This should be called when an instruction (load/store) is deleted from 222 /// the program. 223 void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) { 224 if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) 225 removeMemoryAccess(MA, OptimizePhis); 226 } 227 228 /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. 229 /// Assumption we make here: all uses of deleted defs and phi must either 230 /// occur in blocks about to be deleted (thus will be deleted as well), or 231 /// they occur in phis that will simply lose an incoming value. 232 /// Deleted blocks still have successor info, but their predecessor edges and 233 /// Phi nodes may already be updated. Instructions in DeadBlocks should be 234 /// deleted after this call. 235 LLVM_ABI void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks); 236 237 /// Instruction I will be changed to an unreachable. Remove all accesses in 238 /// I's block that follow I (inclusive), and update the Phis in the blocks' 239 /// successors. 240 LLVM_ABI void changeToUnreachable(const Instruction *I); 241 242 /// Get handle on MemorySSA. getMemorySSA()243 MemorySSA* getMemorySSA() const { return MSSA; } 244 245 private: 246 // Move What before Where in the MemorySSA IR. 247 template <class WhereType> 248 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); 249 // Move all memory accesses from `From` to `To` starting at `Start`. 250 // Restrictions apply, see public wrappers of this method. 251 void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); 252 MemoryAccess *getPreviousDef(MemoryAccess *); 253 MemoryAccess *getPreviousDefInBlock(MemoryAccess *); 254 MemoryAccess * 255 getPreviousDefFromEnd(BasicBlock *, 256 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 257 MemoryAccess * 258 getPreviousDefRecursive(BasicBlock *, 259 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 260 MemoryAccess *recursePhi(MemoryAccess *Phi); 261 MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi); 262 template <class RangeType> 263 MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); 264 void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs); 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). 269 /// 270 /// \param VMap Maps old instructions to cloned instructions and old blocks 271 /// to cloned blocks 272 /// \param MPhiMap, is created in the caller of this private method, and maps 273 /// existing MemoryPhis to new definitions that new MemoryAccesses 274 /// must point to. These definitions may not necessarily be MemoryPhis 275 /// themselves, they may be MemoryDefs. As such, the map is between 276 /// MemoryPhis and MemoryAccesses, where the MemoryAccesses may be 277 /// MemoryPhis or MemoryDefs and not MemoryUses. 278 /// \param IsInClonedRegion Determines whether a basic block was cloned. 279 /// References to accesses outside the cloned region will not be 280 /// remapped. 281 /// \param CloneWasSimplified If false, the clone was exact. Otherwise, 282 /// assume that the clone involved simplifications that may have: 283 /// (1) turned a MemoryUse into an instruction that MemorySSA has no 284 /// representation for, or (2) turned a MemoryDef into a MemoryUse or 285 /// an instruction that MemorySSA has no representation for. No other 286 /// cases are supported. 287 void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, 288 const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap, 289 function_ref<bool(BasicBlock *)> IsInClonedRegion, 290 bool CloneWasSimplified = false); 291 292 template <typename Iter> 293 void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 294 Iter ValuesBegin, Iter ValuesEnd, 295 DominatorTree &DT); 296 void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT, 297 const GraphDiff<BasicBlock *> *GD); 298 }; 299 } // end namespace llvm 300 301 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H 302