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 // \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 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/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" 49 50 namespace llvm { 51 52 class Function; 53 class Instruction; 54 class MemoryAccess; 55 class LLVMContext; 56 class raw_ostream; 57 58 class MemorySSAUpdater { 59 private: 60 MemorySSA *MSSA; 61 SmallVector<MemoryPhi *, 8> InsertedPHIs; 62 SmallPtrSet<BasicBlock *, 8> VisitedBlocks; 63 64 public: 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. 71 /// For example: 72 /// store a 73 /// if (foo) { } 74 /// load a 75 /// 76 /// Moving the store into the if block, and calling insertDef, does not 77 /// require RenameUses. 78 /// However, changing it to: 79 /// store a 80 /// if (foo) { store b } 81 /// load a 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); 89 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 94 // time bounds. 95 96 /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block, 97 /// with a specified clobbering definition. 98 /// 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 105 /// instructions. 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); 112 113 /// \brief Create a MemoryAccess in MemorySSA before or after an existing 114 /// MemoryAccess. 115 /// 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. 120 /// 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); 129 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 *); 137 138 private: 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 *> &); 150 }; 151 } // end namespace llvm 152 153 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H 154
