1 //===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- 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 // This file declares the SSAUpdater class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 14 #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 15 16 #include "llvm/ADT/ArrayRef.h" 17 #include "llvm/ADT/StringRef.h" 18 #include <string> 19 20 namespace llvm { 21 22 class BasicBlock; 23 class Instruction; 24 class LoadInst; 25 class PHINode; 26 template <typename T> class SmallVectorImpl; 27 template <typename T> class SSAUpdaterTraits; 28 class Type; 29 class Use; 30 class Value; 31 class DbgValueInst; 32 33 /// Helper class for SSA formation on a set of values defined in 34 /// multiple blocks. 35 /// 36 /// This is used when code duplication or another unstructured 37 /// transformation wants to rewrite a set of uses of one value with uses of a 38 /// set of values. 39 class SSAUpdater { 40 friend class SSAUpdaterTraits<SSAUpdater>; 41 42 private: 43 /// This keeps track of which value to use on a per-block basis. When we 44 /// insert PHI nodes, we keep track of them here. 45 void *AV = nullptr; 46 47 /// ProtoType holds the type of the values being rewritten. 48 Type *ProtoType = nullptr; 49 50 /// PHI nodes are given a name based on ProtoName. 51 std::string ProtoName; 52 53 /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to 54 /// the vector. 55 SmallVectorImpl<PHINode *> *InsertedPHIs; 56 57 public: 58 /// If InsertedPHIs is specified, it will be filled 59 /// in with all PHI Nodes created by rewriting. 60 explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr); 61 SSAUpdater(const SSAUpdater &) = delete; 62 SSAUpdater &operator=(const SSAUpdater &) = delete; 63 ~SSAUpdater(); 64 65 /// Reset this object to get ready for a new set of SSA updates with 66 /// type 'Ty'. 67 /// 68 /// PHI nodes get a name based on 'Name'. 69 void Initialize(Type *Ty, StringRef Name); 70 71 /// Indicate that a rewritten value is available in the specified block 72 /// with the specified value. 73 void AddAvailableValue(BasicBlock *BB, Value *V); 74 75 /// Return true if the SSAUpdater already has a value for the specified 76 /// block. 77 bool HasValueForBlock(BasicBlock *BB) const; 78 79 /// Return the value for the specified block if the SSAUpdater has one, 80 /// otherwise return nullptr. 81 Value *FindValueForBlock(BasicBlock *BB) const; 82 83 /// Construct SSA form, materializing a value that is live at the end 84 /// of the specified block. 85 Value *GetValueAtEndOfBlock(BasicBlock *BB); 86 87 /// Construct SSA form, materializing a value that is live in the 88 /// middle of the specified block. 89 /// 90 /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except 91 /// in one important case: if there is a definition of the rewritten value 92 /// after the 'use' in BB. Consider code like this: 93 /// 94 /// \code 95 /// X1 = ... 96 /// SomeBB: 97 /// use(X) 98 /// X2 = ... 99 /// br Cond, SomeBB, OutBB 100 /// \endcode 101 /// 102 /// In this case, there are two values (X1 and X2) added to the AvailableVals 103 /// set by the client of the rewriter, and those values are both live out of 104 /// their respective blocks. However, the use of X happens in the *middle* of 105 /// a block. Because of this, we need to insert a new PHI node in SomeBB to 106 /// merge the appropriate values, and this value isn't live out of the block. 107 Value *GetValueInMiddleOfBlock(BasicBlock *BB); 108 109 /// Rewrite a use of the symbolic value. 110 /// 111 /// This handles PHI nodes, which use their value in the corresponding 112 /// predecessor. Note that this will not work if the use is supposed to be 113 /// rewritten to a value defined in the same block as the use, but above it. 114 /// Any 'AddAvailableValue's added for the use's block will be considered to 115 /// be below it. 116 void RewriteUse(Use &U); 117 118 /// Rewrite debug value intrinsics to conform to a new SSA form. 119 /// 120 /// This will scout out all the debug value instrinsics associated with 121 /// the instruction. Anything outside of its block will have its 122 /// value set to the new SSA value if available, and undef if not. 123 void UpdateDebugValues(Instruction *I); 124 void UpdateDebugValues(Instruction *I, 125 SmallVectorImpl<DbgValueInst *> &DbgValues); 126 127 /// Rewrite a use like \c RewriteUse but handling in-block definitions. 128 /// 129 /// This version of the method can rewrite uses in the same block as 130 /// a definition, because it assumes that all uses of a value are below any 131 /// inserted values. 132 void RewriteUseAfterInsertions(Use &U); 133 134 private: 135 Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); 136 void UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue); 137 }; 138 139 /// Helper class for promoting a collection of loads and stores into SSA 140 /// Form using the SSAUpdater. 141 /// 142 /// This handles complexities that SSAUpdater doesn't, such as multiple loads 143 /// and stores in one block. 144 /// 145 /// Clients of this class are expected to subclass this and implement the 146 /// virtual methods. 147 class LoadAndStorePromoter { 148 protected: 149 SSAUpdater &SSA; 150 151 public: 152 LoadAndStorePromoter(ArrayRef<const Instruction *> Insts, 153 SSAUpdater &S, StringRef Name = StringRef()); 154 virtual ~LoadAndStorePromoter() = default; 155 156 /// This does the promotion. 157 /// 158 /// Insts is a list of loads and stores to promote, and Name is the basename 159 /// for the PHIs to insert. After this is complete, the loads and stores are 160 /// removed from the code. 161 void run(const SmallVectorImpl<Instruction *> &Insts); 162 163 /// Return true if the specified instruction is in the Inst list. 164 /// 165 /// The Insts list is the one passed into the constructor. Clients should 166 /// implement this with a more efficient version if possible. 167 virtual bool isInstInList(Instruction *I, 168 const SmallVectorImpl<Instruction *> &Insts) const; 169 170 /// This hook is invoked after all the stores are found and inserted as 171 /// available values. 172 virtual void doExtraRewritesBeforeFinalDeletion() {} 173 174 /// Clients can choose to implement this to get notified right before 175 /// a load is RAUW'd another value. 176 virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {} 177 178 /// Called before each instruction is deleted. 179 virtual void instructionDeleted(Instruction *I) const {} 180 181 /// Called to update debug info associated with the instruction. 182 virtual void updateDebugInfo(Instruction *I) const {} 183 184 /// Return false if a sub-class wants to keep one of the loads/stores 185 /// after the SSA construction. 186 virtual bool shouldDelete(Instruction *I) const { return true; } 187 }; 188 189 } // end namespace llvm 190 191 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 192