diff options
| -rw-r--r-- | include/llvm/Transforms/Utils/SSAUpdater.h | 104 | ||||
| -rw-r--r-- | lib/Transforms/Utils/SSAUpdater.cpp | 44 |
2 files changed, 60 insertions, 88 deletions
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index cd04893..0c0e5de 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -28,82 +28,90 @@ namespace llvm { class Use; class Value; -/// SSAUpdater - This class updates SSA form for a set of values defined in -/// multiple blocks. This is used when code duplication or another unstructured +/// \brief Helper class for SSA formation on a set of values defined in +/// multiple blocks. +/// +/// This is used when code duplication or another unstructured /// transformation wants to rewrite a set of uses of one value with uses of a /// set of values. class SSAUpdater { friend class SSAUpdaterTraits<SSAUpdater>; private: - /// AvailableVals - This keeps track of which value to use on a per-block - /// basis. When we insert PHI nodes, we keep track of them here. + /// This keeps track of which value to use on a per-block basis. When we + /// insert PHI nodes, we keep track of them here. //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; void *AV; /// ProtoType holds the type of the values being rewritten. Type *ProtoType; - // PHI nodes are given a name based on ProtoName. + /// PHI nodes are given a name based on ProtoName. std::string ProtoName; - /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that - /// it creates to the vector. + /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to + /// the vector. SmallVectorImpl<PHINode*> *InsertedPHIs; public: - /// SSAUpdater constructor. If InsertedPHIs is specified, it will be filled + /// If InsertedPHIs is specified, it will be filled /// in with all PHI Nodes created by rewriting. explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0); ~SSAUpdater(); - /// Initialize - Reset this object to get ready for a new set of SSA - /// updates with type 'Ty'. PHI nodes get a name based on 'Name'. + /// \brief Reset this object to get ready for a new set of SSA updates with + /// type 'Ty'. + /// + /// PHI nodes get a name based on 'Name'. void Initialize(Type *Ty, StringRef Name); - /// AddAvailableValue - Indicate that a rewritten value is available at the - /// end of the specified block with the specified value. + /// \brief Indicate that a rewritten value is available in the specified block + /// with the specified value. void AddAvailableValue(BasicBlock *BB, Value *V); - /// HasValueForBlock - Return true if the SSAUpdater already has a value for - /// the specified block. + /// \brief Return true if the SSAUpdater already has a value for the specified + /// block. bool HasValueForBlock(BasicBlock *BB) const; - /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is - /// live at the end of the specified block. + /// \brief Construct SSA form, materializing a value that is live at the end + /// of the specified block. Value *GetValueAtEndOfBlock(BasicBlock *BB); - /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that - /// is live in the middle of the specified block. + /// \brief Construct SSA form, materializing a value that is live in the + /// middle of the specified block. /// - /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one - /// important case: if there is a definition of the rewritten value after the - /// 'use' in BB. Consider code like this: + /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except + /// in one important case: if there is a definition of the rewritten value + /// after the 'use' in BB. Consider code like this: /// + /// \code /// X1 = ... /// SomeBB: /// use(X) /// X2 = ... /// br Cond, SomeBB, OutBB + /// \endcode /// /// In this case, there are two values (X1 and X2) added to the AvailableVals /// set by the client of the rewriter, and those values are both live out of /// their respective blocks. However, the use of X happens in the *middle* of /// a block. Because of this, we need to insert a new PHI node in SomeBB to /// merge the appropriate values, and this value isn't live out of the block. - /// Value *GetValueInMiddleOfBlock(BasicBlock *BB); - /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, - /// which use their value in the corresponding predecessor. Note that this - /// will not work if the use is supposed to be rewritten to a value defined in - /// the same block as the use, but above it. Any 'AddAvailableValue's added - /// for the use's block will be considered to be below it. + /// \brief Rewrite a use of the symbolic value. + /// + /// This handles PHI nodes, which use their value in the corresponding + /// predecessor. Note that this will not work if the use is supposed to be + /// rewritten to a value defined in the same block as the use, but above it. + /// Any 'AddAvailableValue's added for the use's block will be considered to + /// be below it. void RewriteUse(Use &U); - /// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse. However, - /// this version of the method can rewrite uses in the same block as a - /// definition, because it assumes that all uses of a value are below any + /// \brief Rewrite a use like \c RewriteUse but handling in-block definitions. + /// + /// This version of the method can rewrite uses in the same block as + /// a definition, because it assumes that all uses of a value are below any /// inserted values. void RewriteUseAfterInsertions(Use &U); @@ -113,15 +121,15 @@ private: void operator=(const SSAUpdater&) LLVM_DELETED_FUNCTION; SSAUpdater(const SSAUpdater&) LLVM_DELETED_FUNCTION; }; - -/// LoadAndStorePromoter - This little helper class provides a convenient way to -/// promote a collection of loads and stores into SSA Form using the SSAUpdater. + +/// \brief Helper class for promoting a collection of loads and stores into SSA +/// Form using the SSAUpdater. +/// /// This handles complexities that SSAUpdater doesn't, such as multiple loads /// and stores in one block. /// /// Clients of this class are expected to subclass this and implement the /// virtual methods. -/// class LoadAndStorePromoter { protected: SSAUpdater &SSA; @@ -130,34 +138,36 @@ public: SSAUpdater &S, StringRef Name = StringRef()); virtual ~LoadAndStorePromoter() {} - /// run - This does the promotion. Insts is a list of loads and stores to - /// promote, and Name is the basename for the PHIs to insert. After this is - /// complete, the loads and stores are removed from the code. + /// \brief This does the promotion. + /// + /// Insts is a list of loads and stores to promote, and Name is the basename + /// for the PHIs to insert. After this is complete, the loads and stores are + /// removed from the code. void run(const SmallVectorImpl<Instruction*> &Insts) const; - /// Return true if the specified instruction is in the Inst list (which was - /// passed into the run method). Clients should implement this with a more - /// efficient version if possible. + /// \brief Return true if the specified instruction is in the Inst list. + /// + /// The Insts list is the one passed into the constructor. Clients should + /// implement this with a more efficient version if possible. virtual bool isInstInList(Instruction *I, const SmallVectorImpl<Instruction*> &Insts) const; - /// doExtraRewritesBeforeFinalDeletion - This hook is invoked after all the - /// stores are found and inserted as available values, but + /// \brief This hook is invoked after all the stores are found and inserted as + /// available values. virtual void doExtraRewritesBeforeFinalDeletion() const { } - /// replaceLoadWithValue - Clients can choose to implement this to get - /// notified right before a load is RAUW'd another value. + /// \brief Clients can choose to implement this to get notified right before + /// a load is RAUW'd another value. virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const { } - /// This is called before each instruction is deleted. + /// \brief Called before each instruction is deleted. virtual void instructionDeleted(Instruction *I) const { } - /// updateDebugInfo - This is called to update debug info associated with the - /// instruction. + /// \brief Called to update debug info associated with the instruction. virtual void updateDebugInfo(Instruction *I) const { } }; diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index 9d90fbe..fc85ef3 100644 --- a/lib/Transforms/Utils/SSAUpdater.cpp +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -42,8 +42,6 @@ SSAUpdater::~SSAUpdater() { delete static_cast<AvailableValsTy*>(AV); } -/// Initialize - Reset this object to get ready for a new set of SSA -/// updates with type 'Ty'. PHI nodes get a name based on 'Name'. void SSAUpdater::Initialize(Type *Ty, StringRef Name) { if (AV == 0) AV = new AvailableValsTy(); @@ -53,14 +51,10 @@ void SSAUpdater::Initialize(Type *Ty, StringRef Name) { ProtoName = Name; } -/// HasValueForBlock - Return true if the SSAUpdater already has a value for -/// the specified block. bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { return getAvailableVals(AV).count(BB); } -/// AddAvailableValue - Indicate that a rewritten value is available in the -/// specified block with the specified value. void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { assert(ProtoType != 0 && "Need to initialize SSAUpdater"); assert(ProtoType == V->getType() && @@ -68,8 +62,6 @@ void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { getAvailableVals(AV)[BB] = V; } -/// IsEquivalentPHI - Check if PHI has the same incoming value as specified -/// in ValueMapping for each predecessor block. static bool IsEquivalentPHI(PHINode *PHI, DenseMap<BasicBlock*, Value*> &ValueMapping) { unsigned PHINumValues = PHI->getNumIncomingValues(); @@ -86,32 +78,11 @@ static bool IsEquivalentPHI(PHINode *PHI, return true; } -/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is -/// live at the end of the specified block. Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { Value *Res = GetValueAtEndOfBlockInternal(BB); return Res; } -/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that -/// is live in the middle of the specified block. -/// -/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one -/// important case: if there is a definition of the rewritten value after the -/// 'use' in BB. Consider code like this: -/// -/// X1 = ... -/// SomeBB: -/// use(X) -/// X2 = ... -/// br Cond, SomeBB, OutBB -/// -/// In this case, there are two values (X1 and X2) added to the AvailableVals -/// set by the client of the rewriter, and those values are both live out of -/// their respective blocks. However, the use of X happens in the *middle* of -/// a block. Because of this, we need to insert a new PHI node in SomeBB to -/// merge the appropriate values, and this value isn't live out of the block. -/// Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { // If there is no definition of the renamed variable in this block, just use // GetValueAtEndOfBlock to do our work. @@ -203,8 +174,6 @@ Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { return InsertedPHI; } -/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, -/// which use their value in the corresponding predecessor. void SSAUpdater::RewriteUse(Use &U) { Instruction *User = cast<Instruction>(U.getUser()); @@ -222,10 +191,6 @@ void SSAUpdater::RewriteUse(Use &U) { U.set(V); } -/// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse. However, -/// this version of the method can rewrite uses in the same block as a -/// definition, because it assumes that all uses of a value are below any -/// inserted values. void SSAUpdater::RewriteUseAfterInsertions(Use &U) { Instruction *User = cast<Instruction>(U.getUser()); @@ -238,8 +203,6 @@ void SSAUpdater::RewriteUseAfterInsertions(Use &U) { U.set(V); } -/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template, -/// specialized for SSAUpdater. namespace llvm { template<> class SSAUpdaterTraits<SSAUpdater> { @@ -342,10 +305,9 @@ public: } // End llvm namespace -/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry -/// for the specified BB and if so, return it. If not, construct SSA form by -/// first calculating the required placement of PHIs and then inserting new -/// PHIs where needed. +/// Check to see if AvailableVals has an entry for the specified BB and if so, +/// return it. If not, construct SSA form by first calculating the required +/// placement of PHIs and then inserting new PHIs where needed. Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { AvailableValsTy &AvailableVals = getAvailableVals(AV); if (Value *V = AvailableVals[BB]) |