193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===// 293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// The LLVM Compiler Infrastructure 493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file is distributed under the University of Illinois Open Source 693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// License. See LICENSE.TXT for details. 793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file declares the SSAUpdater class. 1193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 1393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H 1693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 17aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer#include "llvm/ADT/StringRef.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Compiler.h" 19aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnernamespace llvm { 2193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner class BasicBlock; 22aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class Instruction; 23aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class LoadInst; 244aad88d1fd88413029dd05255306b07cb19396eeBob Wilson template<typename T> class SmallVectorImpl; 254aad88d1fd88413029dd05255306b07cb19396eeBob Wilson template<typename T> class SSAUpdaterTraits; 26aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class PHINode; 27aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class Type; 28aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class Use; 29aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer class Value; 30ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 31064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// \brief Helper class for SSA formation on a set of values defined in 32064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// multiple blocks. 33064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// 34064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// This is used when code duplication or another unstructured 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// transformation wants to rewrite a set of uses of one value with uses of a 3693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner/// set of values. 3793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerclass SSAUpdater { 384aad88d1fd88413029dd05255306b07cb19396eeBob Wilson friend class SSAUpdaterTraits<SSAUpdater>; 3984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 4084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilsonprivate: 41064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// This keeps track of which value to use on a per-block basis. When we 42064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// insert PHI nodes, we keep track of them here. 4384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void *AV; 45ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 46fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands /// ProtoType holds the type of the values being rewritten. 47db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *ProtoType; 48fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands 49064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// PHI nodes are given a name based on ProtoName. 50fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands std::string ProtoName; 51ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 52064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to 53064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// the vector. 54f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner SmallVectorImpl<PHINode*> *InsertedPHIs; 554aad88d1fd88413029dd05255306b07cb19396eeBob Wilson 5693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerpublic: 57064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// If InsertedPHIs is specified, it will be filled 58f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner /// in with all PHI Nodes created by rewriting. 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = nullptr); 6093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner ~SSAUpdater(); 61ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 62064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Reset this object to get ready for a new set of SSA updates with 63064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// type 'Ty'. 64064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// 65064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// PHI nodes get a name based on 'Name'. 66db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner void Initialize(Type *Ty, StringRef Name); 67ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 68064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Indicate that a rewritten value is available in the specified block 69064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// with the specified value. 7093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void AddAvailableValue(BasicBlock *BB, Value *V); 710bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 72064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Return true if the SSAUpdater already has a value for the specified 73064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// block. 740bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner bool HasValueForBlock(BasicBlock *BB) const; 75ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 76064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Construct SSA form, materializing a value that is live at the end 77064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// of the specified block. 785fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *GetValueAtEndOfBlock(BasicBlock *BB); 79ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 80064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Construct SSA form, materializing a value that is live in the 81064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// middle of the specified block. 821a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 83064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except 84064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// in one important case: if there is a definition of the rewritten value 85064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// after the 'use' in BB. Consider code like this: 861a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 87064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \code 881a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// X1 = ... 891a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// SomeBB: 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// use(X) 911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// X2 = ... 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// br Cond, SomeBB, OutBB 93064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \endcode 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// 951a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// In this case, there are two values (X1 and X2) added to the AvailableVals 961a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// set by the client of the rewriter, and those values are both live out of 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// their respective blocks. However, the use of X happens in the *middle* of 981a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// a block. Because of this, we need to insert a new PHI node in SomeBB to 991a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner /// merge the appropriate values, and this value isn't live out of the block. 1001a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Value *GetValueInMiddleOfBlock(BasicBlock *BB); 101ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 102064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Rewrite a use of the symbolic value. 103064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// 104064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// This handles PHI nodes, which use their value in the corresponding 105064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// predecessor. Note that this will not work if the use is supposed to be 106064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// rewritten to a value defined in the same block as the use, but above it. 107064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// Any 'AddAvailableValue's added for the use's block will be considered to 108064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// be below it. 10993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner void RewriteUse(Use &U); 110ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands 111064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Rewrite a use like \c RewriteUse but handling in-block definitions. 112064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// 113064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// This version of the method can rewrite uses in the same block as 114064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// a definition, because it assumes that all uses of a value are below any 115ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner /// inserted values. 116ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner void RewriteUseAfterInsertions(Use &U); 117ffd9beefb8d1fc854fc2863ad443a557be2b4196Chris Lattner 11893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerprivate: 1195fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); 12084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 1219f9ce61972871efcf794bdc6125835c2c32cd863Craig Topper void operator=(const SSAUpdater&) LLVM_DELETED_FUNCTION; 1229f9ce61972871efcf794bdc6125835c2c32cd863Craig Topper SSAUpdater(const SSAUpdater&) LLVM_DELETED_FUNCTION; 12393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner}; 124064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth 125064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// \brief Helper class for promoting a collection of loads and stores into SSA 126064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// Form using the SSAUpdater. 127064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth/// 128a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner/// This handles complexities that SSAUpdater doesn't, such as multiple loads 129a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner/// and stores in one block. 130a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner/// 131a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner/// Clients of this class are expected to subclass this and implement the 132a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner/// virtual methods. 133a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattnerclass LoadAndStorePromoter { 134deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattnerprotected: 135deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SSAUpdater &SSA; 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 137a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattnerpublic: 138deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner LoadAndStorePromoter(const SmallVectorImpl<Instruction*> &Insts, 139231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel SSAUpdater &S, StringRef Name = StringRef()); 140a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner virtual ~LoadAndStorePromoter() {} 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 142064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief This does the promotion. 143064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// 144064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// Insts is a list of loads and stores to promote, and Name is the basename 145064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// for the PHIs to insert. After this is complete, the loads and stores are 146064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// removed from the code. 147deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner void run(const SmallVectorImpl<Instruction*> &Insts) const; 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 149064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Return true if the specified instruction is in the Inst list. 150064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// 151064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// The Insts list is the one passed into the constructor. Clients should 152064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// implement this with a more efficient version if possible. 153a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner virtual bool isInstInList(Instruction *I, 154aa5354c3ba93032dcc76e8c105575f31196084f1Benjamin Kramer const SmallVectorImpl<Instruction*> &Insts) const; 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 156064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief This hook is invoked after all the stores are found and inserted as 157064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// available values. 158deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void doExtraRewritesBeforeFinalDeletion() const { 159deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 161064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Clients can choose to implement this to get notified right before 162064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// a load is RAUW'd another value. 163deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const { 164deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 165deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 166064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Called before each instruction is deleted. 167deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner virtual void instructionDeleted(Instruction *I) const { 168deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 169deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 170064a68682d7fff603dfb53e21cad951943e62905Chandler Carruth /// \brief Called to update debug info associated with the instruction. 171231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel virtual void updateDebugInfo(Instruction *I) const { 172231a5ab746ca12000aa57208869a98f78781aa6bDevang Patel } 173a2d845a3ff0b11ca7de6dd0485aa23edef7d149aChris Lattner}; 17493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 17593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} // End llvm namespace 17693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 17793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#endif 178