diff options
Diffstat (limited to 'lib/Transforms/Utils/SSAUpdater.cpp')
| -rw-r--r-- | lib/Transforms/Utils/SSAUpdater.cpp | 531 |
1 files changed, 102 insertions, 429 deletions
diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index 25d50dbf2a8ba..f4bdb527655ab 100644 --- a/lib/Transforms/Utils/SSAUpdater.cpp +++ b/lib/Transforms/Utils/SSAUpdater.cpp @@ -12,7 +12,6 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "ssaupdater" -#include "llvm/Transforms/Utils/SSAUpdater.h" #include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/AlignOf.h" @@ -20,40 +19,17 @@ #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/SSAUpdater.h" +#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" using namespace llvm; -/// BBInfo - Per-basic block information used internally by SSAUpdater. -/// The predecessors of each block are cached here since pred_iterator is -/// slow and we need to iterate over the blocks at least a few times. -class SSAUpdater::BBInfo { -public: - BasicBlock *BB; // Back-pointer to the corresponding block. - Value *AvailableVal; // Value to use in this block. - BBInfo *DefBB; // Block that defines the available value. - int BlkNum; // Postorder number. - BBInfo *IDom; // Immediate dominator. - unsigned NumPreds; // Number of predecessor blocks. - BBInfo **Preds; // Array[NumPreds] of predecessor blocks. - PHINode *PHITag; // Marker for existing PHIs that match. - - BBInfo(BasicBlock *ThisBB, Value *V) - : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0), - NumPreds(0), Preds(0), PHITag(0) { } -}; - -typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy; - typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; static AvailableValsTy &getAvailableVals(void *AV) { return *static_cast<AvailableValsTy*>(AV); } -static BBMapTy *getBBMap(void *BM) { - return static_cast<BBMapTy*>(BM); -} - SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) - : AV(0), PrototypeValue(0), BM(0), InsertedPHIs(NewPHI) {} + : AV(0), PrototypeValue(0), InsertedPHIs(NewPHI) {} SSAUpdater::~SSAUpdater() { delete &getAvailableVals(AV); @@ -105,9 +81,7 @@ static bool IsEquivalentPHI(PHINode *PHI, /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is /// live at the end of the specified block. Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { - assert(BM == 0 && "Unexpected Internal State"); Value *Res = GetValueAtEndOfBlockInternal(BB); - assert(BM == 0 && "Unexpected Internal State"); return Res; } @@ -231,427 +205,126 @@ void SSAUpdater::RewriteUse(Use &U) { U.set(V); } -/// 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. -Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { - AvailableValsTy &AvailableVals = getAvailableVals(AV); - if (Value *V = AvailableVals[BB]) - return V; - - // Pool allocation used internally by GetValueAtEndOfBlock. - BumpPtrAllocator Allocator; - BBMapTy BBMapObj; - BM = &BBMapObj; - - SmallVector<BBInfo*, 100> BlockList; - BuildBlockList(BB, &BlockList, &Allocator); - - // Special case: bail out if BB is unreachable. - if (BlockList.size() == 0) { - BM = 0; - return UndefValue::get(PrototypeValue->getType()); - } - - FindDominators(&BlockList); - FindPHIPlacement(&BlockList); - FindAvailableVals(&BlockList); - - BM = 0; - return BBMapObj[BB]->DefBB->AvailableVal; +/// PHIiter - Iterator for PHI operands. This is used for the PHI_iterator +/// in the SSAUpdaterImpl template. +namespace { + class PHIiter { + private: + PHINode *PHI; + unsigned idx; + + public: + explicit PHIiter(PHINode *P) // begin iterator + : PHI(P), idx(0) {} + PHIiter(PHINode *P, bool) // end iterator + : PHI(P), idx(PHI->getNumIncomingValues()) {} + + PHIiter &operator++() { ++idx; return *this; } + bool operator==(const PHIiter& x) const { return idx == x.idx; } + bool operator!=(const PHIiter& x) const { return !operator==(x); } + Value *getIncomingValue() { return PHI->getIncomingValue(idx); } + BasicBlock *getIncomingBlock() { return PHI->getIncomingBlock(idx); } + }; } -/// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds -/// vector, set Info->NumPreds, and allocate space in Info->Preds. -static void FindPredecessorBlocks(SSAUpdater::BBInfo *Info, - SmallVectorImpl<BasicBlock*> *Preds, - BumpPtrAllocator *Allocator) { - // We can get our predecessor info by walking the pred_iterator list, - // but it is relatively slow. If we already have PHI nodes in this - // block, walk one of them to get the predecessor list instead. - BasicBlock *BB = Info->BB; - if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { - for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI) - Preds->push_back(SomePhi->getIncomingBlock(PI)); - } else { - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - Preds->push_back(*PI); +/// SSAUpdaterTraits<SSAUpdater> - Traits for the SSAUpdaterImpl template, +/// specialized for SSAUpdater. +namespace llvm { +template<> +class SSAUpdaterTraits<SSAUpdater> { +public: + typedef BasicBlock BlkT; + typedef Value *ValT; + typedef PHINode PhiT; + + typedef succ_iterator BlkSucc_iterator; + static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return succ_begin(BB); } + static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return succ_end(BB); } + + typedef PHIiter PHI_iterator; + static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } + static inline PHI_iterator PHI_end(PhiT *PHI) { + return PHI_iterator(PHI, true); } - Info->NumPreds = Preds->size(); - Info->Preds = static_cast<SSAUpdater::BBInfo**> - (Allocator->Allocate(Info->NumPreds * sizeof(SSAUpdater::BBInfo*), - AlignOf<SSAUpdater::BBInfo*>::Alignment)); -} - -/// BuildBlockList - Starting from the specified basic block, traverse back -/// through its predecessors until reaching blocks with known values. Create -/// BBInfo structures for the blocks and append them to the block list. -void SSAUpdater::BuildBlockList(BasicBlock *BB, BlockListTy *BlockList, - BumpPtrAllocator *Allocator) { - AvailableValsTy &AvailableVals = getAvailableVals(AV); - BBMapTy *BBMap = getBBMap(BM); - SmallVector<BBInfo*, 10> RootList; - SmallVector<BBInfo*, 64> WorkList; - - BBInfo *Info = new (*Allocator) BBInfo(BB, 0); - (*BBMap)[BB] = Info; - WorkList.push_back(Info); - - // Search backward from BB, creating BBInfos along the way and stopping when - // reaching blocks that define the value. Record those defining blocks on - // the RootList. - SmallVector<BasicBlock*, 10> Preds; - while (!WorkList.empty()) { - Info = WorkList.pop_back_val(); - Preds.clear(); - FindPredecessorBlocks(Info, &Preds, Allocator); - - // Treat an unreachable predecessor as a definition with 'undef'. - if (Info->NumPreds == 0) { - Info->AvailableVal = UndefValue::get(PrototypeValue->getType()); - Info->DefBB = Info; - RootList.push_back(Info); - continue; - } - - for (unsigned p = 0; p != Info->NumPreds; ++p) { - BasicBlock *Pred = Preds[p]; - // Check if BBMap already has a BBInfo for the predecessor block. - BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred); - if (BBMapBucket.second) { - Info->Preds[p] = BBMapBucket.second; - continue; - } - - // Create a new BBInfo for the predecessor. - Value *PredVal = AvailableVals.lookup(Pred); - BBInfo *PredInfo = new (*Allocator) BBInfo(Pred, PredVal); - BBMapBucket.second = PredInfo; - Info->Preds[p] = PredInfo; - - if (PredInfo->AvailableVal) { - RootList.push_back(PredInfo); - continue; - } - WorkList.push_back(PredInfo); + /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds + /// vector, set Info->NumPreds, and allocate space in Info->Preds. + static void FindPredecessorBlocks(BasicBlock *BB, + SmallVectorImpl<BasicBlock*> *Preds) { + // We can get our predecessor info by walking the pred_iterator list, + // but it is relatively slow. If we already have PHI nodes in this + // block, walk one of them to get the predecessor list instead. + if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { + for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI) + Preds->push_back(SomePhi->getIncomingBlock(PI)); + } else { + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + Preds->push_back(*PI); } } - // Now that we know what blocks are backwards-reachable from the starting - // block, do a forward depth-first traversal to assign postorder numbers - // to those blocks. - BBInfo *PseudoEntry = new (*Allocator) BBInfo(0, 0); - unsigned BlkNum = 1; - - // Initialize the worklist with the roots from the backward traversal. - while (!RootList.empty()) { - Info = RootList.pop_back_val(); - Info->IDom = PseudoEntry; - Info->BlkNum = -1; - WorkList.push_back(Info); + /// GetUndefVal - Get an undefined value of the same type as the value + /// being handled. + static Value *GetUndefVal(BasicBlock *BB, SSAUpdater *Updater) { + return UndefValue::get(Updater->PrototypeValue->getType()); } - while (!WorkList.empty()) { - Info = WorkList.back(); - - if (Info->BlkNum == -2) { - // All the successors have been handled; assign the postorder number. - Info->BlkNum = BlkNum++; - // If not a root, put it on the BlockList. - if (!Info->AvailableVal) - BlockList->push_back(Info); - WorkList.pop_back(); - continue; - } - - // Leave this entry on the worklist, but set its BlkNum to mark that its - // successors have been put on the worklist. When it returns to the top - // the list, after handling its successors, it will be assigned a number. - Info->BlkNum = -2; - - // Add unvisited successors to the work list. - for (succ_iterator SI = succ_begin(Info->BB), E = succ_end(Info->BB); - SI != E; ++SI) { - BBInfo *SuccInfo = (*BBMap)[*SI]; - if (!SuccInfo || SuccInfo->BlkNum) - continue; - SuccInfo->BlkNum = -1; - WorkList.push_back(SuccInfo); - } + /// CreateEmptyPHI - Create a new PHI instruction in the specified block. + /// Reserve space for the operands but do not fill them in yet. + static Value *CreateEmptyPHI(BasicBlock *BB, unsigned NumPreds, + SSAUpdater *Updater) { + PHINode *PHI = PHINode::Create(Updater->PrototypeValue->getType(), + Updater->PrototypeValue->getName(), + &BB->front()); + PHI->reserveOperandSpace(NumPreds); + return PHI; } - PseudoEntry->BlkNum = BlkNum; -} -/// IntersectDominators - This is the dataflow lattice "meet" operation for -/// finding dominators. Given two basic blocks, it walks up the dominator -/// tree until it finds a common dominator of both. It uses the postorder -/// number of the blocks to determine how to do that. -static SSAUpdater::BBInfo *IntersectDominators(SSAUpdater::BBInfo *Blk1, - SSAUpdater::BBInfo *Blk2) { - while (Blk1 != Blk2) { - while (Blk1->BlkNum < Blk2->BlkNum) { - Blk1 = Blk1->IDom; - if (!Blk1) - return Blk2; - } - while (Blk2->BlkNum < Blk1->BlkNum) { - Blk2 = Blk2->IDom; - if (!Blk2) - return Blk1; - } + /// AddPHIOperand - Add the specified value as an operand of the PHI for + /// the specified predecessor block. + static void AddPHIOperand(PHINode *PHI, Value *Val, BasicBlock *Pred) { + PHI->addIncoming(Val, Pred); } - return Blk1; -} -/// FindDominators - Calculate the dominator tree for the subset of the CFG -/// corresponding to the basic blocks on the BlockList. This uses the -/// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey and -/// Kennedy, published in Software--Practice and Experience, 2001, 4:1-10. -/// Because the CFG subset does not include any edges leading into blocks that -/// define the value, the results are not the usual dominator tree. The CFG -/// subset has a single pseudo-entry node with edges to a set of root nodes -/// for blocks that define the value. The dominators for this subset CFG are -/// not the standard dominators but they are adequate for placing PHIs within -/// the subset CFG. -void SSAUpdater::FindDominators(BlockListTy *BlockList) { - bool Changed; - do { - Changed = false; - // Iterate over the list in reverse order, i.e., forward on CFG edges. - for (BlockListTy::reverse_iterator I = BlockList->rbegin(), - E = BlockList->rend(); I != E; ++I) { - BBInfo *Info = *I; - - // Start with the first predecessor. - assert(Info->NumPreds > 0 && "unreachable block"); - BBInfo *NewIDom = Info->Preds[0]; - - // Iterate through the block's other predecessors. - for (unsigned p = 1; p != Info->NumPreds; ++p) { - BBInfo *Pred = Info->Preds[p]; - NewIDom = IntersectDominators(NewIDom, Pred); - } - - // Check if the IDom value has changed. - if (NewIDom != Info->IDom) { - Info->IDom = NewIDom; - Changed = true; - } - } - } while (Changed); -} - -/// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for -/// any blocks containing definitions of the value. If one is found, then the -/// successor of Pred is in the dominance frontier for the definition, and -/// this function returns true. -static bool IsDefInDomFrontier(const SSAUpdater::BBInfo *Pred, - const SSAUpdater::BBInfo *IDom) { - for (; Pred != IDom; Pred = Pred->IDom) { - if (Pred->DefBB == Pred) - return true; + /// InstrIsPHI - Check if an instruction is a PHI. + /// + static PHINode *InstrIsPHI(Instruction *I) { + return dyn_cast<PHINode>(I); } - return false; -} - -/// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of -/// the known definitions. Iteratively add PHIs in the dom frontiers until -/// nothing changes. Along the way, keep track of the nearest dominating -/// definitions for non-PHI blocks. -void SSAUpdater::FindPHIPlacement(BlockListTy *BlockList) { - bool Changed; - do { - Changed = false; - // Iterate over the list in reverse order, i.e., forward on CFG edges. - for (BlockListTy::reverse_iterator I = BlockList->rbegin(), - E = BlockList->rend(); I != E; ++I) { - BBInfo *Info = *I; - - // If this block already needs a PHI, there is nothing to do here. - if (Info->DefBB == Info) - continue; - - // Default to use the same def as the immediate dominator. - BBInfo *NewDefBB = Info->IDom->DefBB; - for (unsigned p = 0; p != Info->NumPreds; ++p) { - if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) { - // Need a PHI here. - NewDefBB = Info; - break; - } - } - - // Check if anything changed. - if (NewDefBB != Info->DefBB) { - Info->DefBB = NewDefBB; - Changed = true; - } - } - } while (Changed); -} - -/// FindAvailableVal - If this block requires a PHI, first check if an existing -/// PHI matches the PHI placement and reaching definitions computed earlier, -/// and if not, create a new PHI. Visit all the block's predecessors to -/// calculate the available value for each one and fill in the incoming values -/// for a new PHI. -void SSAUpdater::FindAvailableVals(BlockListTy *BlockList) { - AvailableValsTy &AvailableVals = getAvailableVals(AV); - // Go through the worklist in forward order (i.e., backward through the CFG) - // and check if existing PHIs can be used. If not, create empty PHIs where - // they are needed. - for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end(); - I != E; ++I) { - BBInfo *Info = *I; - // Check if there needs to be a PHI in BB. - if (Info->DefBB != Info) - continue; - - // Look for an existing PHI. - FindExistingPHI(Info->BB, BlockList); - if (Info->AvailableVal) - continue; - - PHINode *PHI = PHINode::Create(PrototypeValue->getType(), - PrototypeValue->getName(), - &Info->BB->front()); - PHI->reserveOperandSpace(Info->NumPreds); - Info->AvailableVal = PHI; - AvailableVals[Info->BB] = PHI; + /// ValueIsPHI - Check if a value is a PHI. + /// + static PHINode *ValueIsPHI(Value *Val, SSAUpdater *Updater) { + return dyn_cast<PHINode>(Val); } - // Now go back through the worklist in reverse order to fill in the arguments - // for any new PHIs added in the forward traversal. - for (BlockListTy::reverse_iterator I = BlockList->rbegin(), - E = BlockList->rend(); I != E; ++I) { - BBInfo *Info = *I; - - if (Info->DefBB != Info) { - // Record the available value at join nodes to speed up subsequent - // uses of this SSAUpdater for the same value. - if (Info->NumPreds > 1) - AvailableVals[Info->BB] = Info->DefBB->AvailableVal; - continue; - } - - // Check if this block contains a newly added PHI. - PHINode *PHI = dyn_cast<PHINode>(Info->AvailableVal); - if (!PHI || PHI->getNumIncomingValues() == Info->NumPreds) - continue; - - // Iterate through the block's predecessors. - for (unsigned p = 0; p != Info->NumPreds; ++p) { - BBInfo *PredInfo = Info->Preds[p]; - BasicBlock *Pred = PredInfo->BB; - // Skip to the nearest preceding definition. - if (PredInfo->DefBB != PredInfo) - PredInfo = PredInfo->DefBB; - PHI->addIncoming(PredInfo->AvailableVal, Pred); - } - - DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n"); - - // If the client wants to know about all new instructions, tell it. - if (InsertedPHIs) InsertedPHIs->push_back(PHI); + /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source + /// operands, i.e., it was just added. + static PHINode *ValueIsNewPHI(Value *Val, SSAUpdater *Updater) { + PHINode *PHI = ValueIsPHI(Val, Updater); + if (PHI && PHI->getNumIncomingValues() == 0) + return PHI; + return 0; } -} -/// FindExistingPHI - Look through the PHI nodes in a block to see if any of -/// them match what is needed. -void SSAUpdater::FindExistingPHI(BasicBlock *BB, BlockListTy *BlockList) { - PHINode *SomePHI; - for (BasicBlock::iterator It = BB->begin(); - (SomePHI = dyn_cast<PHINode>(It)); ++It) { - if (CheckIfPHIMatches(SomePHI)) { - RecordMatchingPHI(SomePHI); - break; - } - // Match failed: clear all the PHITag values. - for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end(); - I != E; ++I) - (*I)->PHITag = 0; + /// GetPHIValue - For the specified PHI instruction, return the value + /// that it defines. + static Value *GetPHIValue(PHINode *PHI) { + return PHI; } -} +}; -/// CheckIfPHIMatches - Check if a PHI node matches the placement and values -/// in the BBMap. -bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) { - BBMapTy *BBMap = getBBMap(BM); - SmallVector<PHINode*, 20> WorkList; - WorkList.push_back(PHI); - - // Mark that the block containing this PHI has been visited. - (*BBMap)[PHI->getParent()]->PHITag = PHI; - - while (!WorkList.empty()) { - PHI = WorkList.pop_back_val(); - - // Iterate through the PHI's incoming values. - for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { - Value *IncomingVal = PHI->getIncomingValue(i); - BBInfo *PredInfo = (*BBMap)[PHI->getIncomingBlock(i)]; - // Skip to the nearest preceding definition. - if (PredInfo->DefBB != PredInfo) - PredInfo = PredInfo->DefBB; - - // Check if it matches the expected value. - if (PredInfo->AvailableVal) { - if (IncomingVal == PredInfo->AvailableVal) - continue; - return false; - } - - // Check if the value is a PHI in the correct block. - PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal); - if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB) - return false; - - // If this block has already been visited, check if this PHI matches. - if (PredInfo->PHITag) { - if (IncomingPHIVal == PredInfo->PHITag) - continue; - return false; - } - PredInfo->PHITag = IncomingPHIVal; - - WorkList.push_back(IncomingPHIVal); - } - } - return true; -} +} // End llvm namespace -/// RecordMatchingPHI - For a PHI node that matches, record it and its input -/// PHIs in both the BBMap and the AvailableVals mapping. -void SSAUpdater::RecordMatchingPHI(PHINode *PHI) { - BBMapTy *BBMap = getBBMap(BM); +/// 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. +Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { AvailableValsTy &AvailableVals = getAvailableVals(AV); - SmallVector<PHINode*, 20> WorkList; - WorkList.push_back(PHI); - - // Record this PHI. - BasicBlock *BB = PHI->getParent(); - AvailableVals[BB] = PHI; - (*BBMap)[BB]->AvailableVal = PHI; - - while (!WorkList.empty()) { - PHI = WorkList.pop_back_val(); - - // Iterate through the PHI's incoming values. - for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { - PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); - if (!IncomingPHIVal) continue; - BB = IncomingPHIVal->getParent(); - BBInfo *Info = (*BBMap)[BB]; - if (!Info || Info->AvailableVal) - continue; - - // Record the PHI and add it to the worklist. - AvailableVals[BB] = IncomingPHIVal; - Info->AvailableVal = IncomingPHIVal; - WorkList.push_back(IncomingPHIVal); - } - } + if (Value *V = AvailableVals[BB]) + return V; + + SSAUpdaterImpl<SSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); + return Impl.GetValue(BB); } |