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