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