From 4aad88d1fd88413029dd05255306b07cb19396ee Mon Sep 17 00:00:00 2001 From: Bob Wilson Date: Tue, 4 May 2010 23:18:19 +0000 Subject: [PATCH] Combine the implementations of the core part of the SSAUpdater and MachineSSAUpdater to avoid duplicating all the code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103060 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/MachineSSAUpdater.h | 18 +- include/llvm/Transforms/Utils/SSAUpdater.h | 22 +- .../llvm/Transforms/Utils/SSAUpdaterImpl.h | 463 +++++++++++++++ lib/CodeGen/MachineSSAUpdater.cpp | 546 ++++-------------- lib/Transforms/Utils/SSAUpdater.cpp | 531 ++++------------- 5 files changed, 680 insertions(+), 900 deletions(-) create mode 100644 include/llvm/Transforms/Utils/SSAUpdaterImpl.h diff --git a/include/llvm/CodeGen/MachineSSAUpdater.h b/include/llvm/CodeGen/MachineSSAUpdater.h index 979ef0113ba..cbb45a71275 100644 --- a/include/llvm/CodeGen/MachineSSAUpdater.h +++ b/include/llvm/CodeGen/MachineSSAUpdater.h @@ -23,6 +23,7 @@ namespace llvm { class TargetInstrInfo; class TargetRegisterClass; template class SmallVectorImpl; + template class SSAUpdaterTraits; class BumpPtrAllocator; /// MachineSSAUpdater - This class updates SSA form for a set of virtual @@ -30,9 +31,7 @@ namespace llvm { /// or another unstructured transformation wants to rewrite a set of uses of one /// vreg with uses of a set of vregs. class MachineSSAUpdater { -public: - class BBInfo; - typedef SmallVectorImpl BlockListTy; + friend class SSAUpdaterTraits; private: /// AvailableVals - This keeps track of which value to use on a per-block @@ -40,11 +39,6 @@ private: //typedef DenseMap AvailableValsTy; void *AV; - /// BBMap - The GetValueAtEndOfBlock method maintains this mapping from - /// basic blocks to BBInfo structures. - /// typedef DenseMap BBMapTy; - void *BM; - /// VR - Current virtual register whose uses are being updated. unsigned VR; @@ -111,14 +105,6 @@ public: private: void ReplaceRegWith(unsigned OldReg, unsigned NewReg); unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB); - void BuildBlockList(MachineBasicBlock *BB, BlockListTy *BlockList, - BumpPtrAllocator *Allocator); - void FindDominators(BlockListTy *BlockList); - void FindPHIPlacement(BlockListTy *BlockList); - void FindAvailableVals(BlockListTy *BlockList); - void FindExistingPHI(MachineBasicBlock *BB, BlockListTy *BlockList); - bool CheckIfPHIMatches(MachineInstr *PHI); - void RecordMatchingPHI(MachineInstr *PHI); void operator=(const MachineSSAUpdater&); // DO NOT IMPLEMENT MachineSSAUpdater(const MachineSSAUpdater&); // DO NOT IMPLEMENT diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h index 5b77ed660fc..ca98466b345 100644 --- a/include/llvm/Transforms/Utils/SSAUpdater.h +++ b/include/llvm/Transforms/Utils/SSAUpdater.h @@ -19,8 +19,8 @@ namespace llvm { class BasicBlock; class Use; class PHINode; - template - class SmallVectorImpl; + template class SmallVectorImpl; + template class SSAUpdaterTraits; class BumpPtrAllocator; /// SSAUpdater - This class updates SSA form for a set of values defined in @@ -28,9 +28,7 @@ namespace llvm { /// transformation wants to rewrite a set of uses of one value with uses of a /// set of values. class SSAUpdater { -public: - class BBInfo; - typedef SmallVectorImpl BlockListTy; + friend class SSAUpdaterTraits; private: /// AvailableVals - This keeps track of which value to use on a per-block @@ -42,14 +40,10 @@ private: /// and a type for PHI nodes. Value *PrototypeValue; - /// BBMap - The GetValueAtEndOfBlock method maintains this mapping from - /// basic blocks to BBInfo structures. - /// typedef DenseMap BBMapTy; - void *BM; - /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that /// it creates to the vector. SmallVectorImpl *InsertedPHIs; + public: /// SSAUpdater constructor. If InsertedPHIs is specified, it will be filled /// in with all PHI Nodes created by rewriting. @@ -102,14 +96,6 @@ public: private: Value *GetValueAtEndOfBlockInternal(BasicBlock *BB); - void BuildBlockList(BasicBlock *BB, BlockListTy *BlockList, - BumpPtrAllocator *Allocator); - void FindDominators(BlockListTy *BlockList); - void FindPHIPlacement(BlockListTy *BlockList); - void FindAvailableVals(BlockListTy *BlockList); - void FindExistingPHI(BasicBlock *BB, BlockListTy *BlockList); - bool CheckIfPHIMatches(PHINode *PHI); - void RecordMatchingPHI(PHINode *PHI); void operator=(const SSAUpdater&); // DO NOT IMPLEMENT SSAUpdater(const SSAUpdater&); // DO NOT IMPLEMENT diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h new file mode 100644 index 00000000000..82537968444 --- /dev/null +++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h @@ -0,0 +1,463 @@ +//===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides a template that implements the core algorithm for the +// SSAUpdater and MachineSSAUpdater. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H +#define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H + +namespace llvm { + +template class SSAUpdaterTraits; + +template +class SSAUpdaterImpl { +private: + UpdaterT *Updater; + + typedef SSAUpdaterTraits Traits; + typedef typename Traits::BlkT BlkT; + typedef typename Traits::ValT ValT; + typedef typename Traits::PhiT PhiT; + + /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl. + /// 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 BBInfo { + public: + BlkT *BB; // Back-pointer to the corresponding block. + ValT 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. + PhiT *PHITag; // Marker for existing PHIs that match. + + BBInfo(BlkT *ThisBB, ValT V) + : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0), + NumPreds(0), Preds(0), PHITag(0) { } + }; + + typedef DenseMap AvailableValsTy; + AvailableValsTy *AvailableVals; + + SmallVectorImpl *InsertedPHIs; + + typedef SmallVectorImpl BlockListTy; + typedef DenseMap BBMapTy; + BBMapTy BBMap; + BumpPtrAllocator Allocator; + +public: + explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, + SmallVectorImpl *Ins) : + Updater(U), AvailableVals(A), InsertedPHIs(Ins) { } + + /// GetValue - 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. + ValT GetValue(BlkT *BB) { + SmallVector BlockList; + BuildBlockList(BB, &BlockList); + + // Special case: bail out if BB is unreachable. + if (BlockList.size() == 0) { + ValT V = Traits::GetUndefVal(BB, Updater); + (*AvailableVals)[BB] = V; + return V; + } + + FindDominators(&BlockList); + FindPHIPlacement(&BlockList); + FindAvailableVals(&BlockList); + + return BBMap[BB]->DefBB->AvailableVal; + } + + /// 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 BuildBlockList(BlkT *BB, BlockListTy *BlockList) { + SmallVector RootList; + SmallVector 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 Preds; + while (!WorkList.empty()) { + Info = WorkList.pop_back_val(); + Preds.clear(); + Traits::FindPredecessorBlocks(Info->BB, &Preds); + Info->NumPreds = Preds.size(); + Info->Preds = static_cast + (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*), + AlignOf::Alignment)); + + // Treat an unreachable predecessor as a definition with 'undef'. + if (Info->NumPreds == 0) { + Info->AvailableVal = Traits::GetUndefVal(Info->BB, Updater); + Info->DefBB = Info; + RootList.push_back(Info); + continue; + } + + for (unsigned p = 0; p != Info->NumPreds; ++p) { + BlkT *Pred = Preds[p]; + // Check if BBMap already has a BBInfo for the predecessor block. + typename BBMapTy::value_type &BBMapBucket = + BBMap.FindAndConstruct(Pred); + if (BBMapBucket.second) { + Info->Preds[p] = BBMapBucket.second; + continue; + } + + // Create a new BBInfo for the predecessor. + ValT 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); + } + } + + // 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); + } + + 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 (typename Traits::BlkSucc_iterator SI = + Traits::BlkSucc_begin(Info->BB), + E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) { + BBInfo *SuccInfo = BBMap[*SI]; + if (!SuccInfo || SuccInfo->BlkNum) + continue; + SuccInfo->BlkNum = -1; + WorkList.push_back(SuccInfo); + } + } + 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. + BBInfo *IntersectDominators(BBInfo *Blk1, 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; + } + } + 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 FindDominators(BlockListTy *BlockList) { + bool Changed; + do { + Changed = false; + // Iterate over the list in reverse order, i.e., forward on CFG edges. + for (typename 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. + bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) { + for (; Pred != IDom; Pred = Pred->IDom) { + if (Pred->DefBB == Pred) + return true; + } + 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 FindPHIPlacement(BlockListTy *BlockList) { + bool Changed; + do { + Changed = false; + // Iterate over the list in reverse order, i.e., forward on CFG edges. + for (typename 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 FindAvailableVals(BlockListTy *BlockList) { + // 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 (typename 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; + + ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater); + Info->AvailableVal = PHI; + (*AvailableVals)[Info->BB] = PHI; + } + + // Now go back through the worklist in reverse order to fill in the + // arguments for any new PHIs added in the forward traversal. + for (typename 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. + PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater); + if (!PHI) + continue; + + // Iterate through the block's predecessors. + for (unsigned p = 0; p != Info->NumPreds; ++p) { + BBInfo *PredInfo = Info->Preds[p]; + BlkT *Pred = PredInfo->BB; + // Skip to the nearest preceding definition. + if (PredInfo->DefBB != PredInfo) + PredInfo = PredInfo->DefBB; + Traits::AddPHIOperand(PHI, 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); + } + } + + /// FindExistingPHI - Look through the PHI nodes in a block to see if any of + /// them match what is needed. + void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { + for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end(); + BBI != BBE; ++BBI) { + PhiT *SomePHI = Traits::InstrIsPHI(BBI); + if (!SomePHI) + break; + if (CheckIfPHIMatches(SomePHI)) { + RecordMatchingPHI(SomePHI); + break; + } + // Match failed: clear all the PHITag values. + for (typename BlockListTy::iterator I = BlockList->begin(), + E = BlockList->end(); I != E; ++I) + (*I)->PHITag = 0; + } + } + + /// CheckIfPHIMatches - Check if a PHI node matches the placement and values + /// in the BBMap. + bool CheckIfPHIMatches(PhiT *PHI) { + SmallVector 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 (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI), + E = Traits::PHI_end(PHI); I != E; ++I) { + ValT IncomingVal = I.getIncomingValue(); + BBInfo *PredInfo = BBMap[I.getIncomingBlock()]; + // 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. + PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater); + 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; + } + + /// RecordMatchingPHI - For a PHI node that matches, record it and its input + /// PHIs in both the BBMap and the AvailableVals mapping. + void RecordMatchingPHI(PhiT *PHI) { + SmallVector WorkList; + WorkList.push_back(PHI); + + // Record this PHI. + BlkT *BB = PHI->getParent(); + ValT PHIVal = Traits::GetPHIValue(PHI); + (*AvailableVals)[BB] = PHIVal; + BBMap[BB]->AvailableVal = PHIVal; + + while (!WorkList.empty()) { + PHI = WorkList.pop_back_val(); + + // Iterate through the PHI's incoming values. + for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI), + E = Traits::PHI_end(PHI); I != E; ++I) { + ValT IncomingVal = I.getIncomingValue(); + PhiT *IncomingPHI = Traits::ValueIsPHI(IncomingVal, Updater); + if (!IncomingPHI) continue; + BB = IncomingPHI->getParent(); + BBInfo *Info = BBMap[BB]; + if (!Info || Info->AvailableVal) + continue; + + // Record the PHI and add it to the worklist. + (*AvailableVals)[BB] = IncomingVal; + Info->AvailableVal = IncomingVal; + WorkList.push_back(IncomingPHI); + } + } + } +}; + +} // End llvm namespace + +#endif diff --git a/lib/CodeGen/MachineSSAUpdater.cpp b/lib/CodeGen/MachineSSAUpdater.cpp index b8996d46f94..99fb99ac3c7 100644 --- a/lib/CodeGen/MachineSSAUpdater.cpp +++ b/lib/CodeGen/MachineSSAUpdater.cpp @@ -26,39 +26,17 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/SSAUpdaterImpl.h" using namespace llvm; -/// BBInfo - Per-basic block information used internally by MachineSSAUpdater. -class MachineSSAUpdater::BBInfo { -public: - MachineBasicBlock *BB; // Back-pointer to the corresponding block. - unsigned 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. - MachineInstr *PHITag; // Marker for existing PHIs that match. - - BBInfo(MachineBasicBlock *ThisBB, unsigned V) - : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0), - NumPreds(0), Preds(0), PHITag(0) { } -}; - -typedef DenseMap BBMapTy; - typedef DenseMap AvailableValsTy; static AvailableValsTy &getAvailableVals(void *AV) { return *static_cast(AV); } -static BBMapTy *getBBMap(void *BM) { - return static_cast(BM); -} - MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, SmallVectorImpl *NewPHI) - : AV(0), BM(0), InsertedPHIs(NewPHI) { + : AV(0), InsertedPHIs(NewPHI) { TII = MF.getTarget().getInstrInfo(); MRI = &MF.getRegInfo(); } @@ -134,7 +112,8 @@ static MachineInstr *InsertNewDef(unsigned Opcode, MachineBasicBlock *BB, MachineBasicBlock::iterator I, const TargetRegisterClass *RC, - MachineRegisterInfo *MRI, const TargetInstrInfo *TII) { + MachineRegisterInfo *MRI, + const TargetInstrInfo *TII) { unsigned NewVR = MRI->createVirtualRegister(RC); return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); } @@ -263,438 +242,131 @@ void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) { I->second = NewReg; } -/// 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. -unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ - AvailableValsTy &AvailableVals = getAvailableVals(AV); - if (unsigned V = AvailableVals[BB]) - return V; +/// MachinePHIiter - Iterator for PHI operands. This is used for the +/// PHI_iterator in the SSAUpdaterImpl template. +namespace { + class MachinePHIiter { + private: + MachineInstr *PHI; + unsigned idx; + + public: + explicit MachinePHIiter(MachineInstr *P) // begin iterator + : PHI(P), idx(1) {} + MachinePHIiter(MachineInstr *P, bool) // end iterator + : PHI(P), idx(PHI->getNumOperands()) {} + + MachinePHIiter &operator++() { idx += 2; return *this; } + bool operator==(const MachinePHIiter& x) const { return idx == x.idx; } + bool operator!=(const MachinePHIiter& x) const { return !operator==(x); } + unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } + MachineBasicBlock *getIncomingBlock() { + return PHI->getOperand(idx+1).getMBB(); + } + }; +} - // Pool allocation used internally by GetValueAtEndOfBlock. - BumpPtrAllocator Allocator; - BBMapTy BBMapObj; - BM = &BBMapObj; +/// SSAUpdaterTraits - Traits for the SSAUpdaterImpl +/// template, specialized for MachineSSAUpdater. +namespace llvm { +template<> +class SSAUpdaterTraits { +public: + typedef MachineBasicBlock BlkT; + typedef unsigned ValT; + typedef MachineInstr PhiT; + + typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; + static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } + static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } + + typedef MachinePHIiter 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); + } - SmallVector BlockList; - BuildBlockList(BB, &BlockList, &Allocator); + /// FindPredecessorBlocks - Put the predecessors of BB into the Preds + /// vector. + static void FindPredecessorBlocks(MachineBasicBlock *BB, + SmallVectorImpl *Preds){ + for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), + E = BB->pred_end(); PI != E; ++PI) + Preds->push_back(*PI); + } - // Special case: bail out if BB is unreachable. - if (BlockList.size() == 0) { - BM = 0; + /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. + /// Add it into the specified block and return the register. + static unsigned GetUndefVal(MachineBasicBlock *BB, + MachineSSAUpdater *Updater) { // Insert an implicit_def to represent an undef value. MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, BB, BB->getFirstTerminator(), - VRC, MRI, TII); - unsigned V = NewDef->getOperand(0).getReg(); - AvailableVals[BB] = V; - return V; - } - - FindDominators(&BlockList); - FindPHIPlacement(&BlockList); - FindAvailableVals(&BlockList); - - BM = 0; - return BBMapObj[BB]->DefBB->AvailableVal; -} - -/// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds -/// vector, set Info->NumPreds, and allocate space in Info->Preds. -static void FindPredecessorBlocks(MachineSSAUpdater::BBInfo *Info, - SmallVectorImpl *Preds, - BumpPtrAllocator *Allocator) { - MachineBasicBlock *BB = Info->BB; - for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), - E = BB->pred_end(); PI != E; ++PI) - Preds->push_back(*PI); - - Info->NumPreds = Preds->size(); - Info->Preds = static_cast - (Allocator->Allocate(Info->NumPreds * sizeof(MachineSSAUpdater::BBInfo*), - AlignOf::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 MachineSSAUpdater::BuildBlockList(MachineBasicBlock *BB, - BlockListTy *BlockList, - BumpPtrAllocator *Allocator) { - AvailableValsTy &AvailableVals = getAvailableVals(AV); - BBMapTy *BBMap = getBBMap(BM); - SmallVector RootList; - SmallVector 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 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) { - // Insert an implicit_def to represent an undef value. - MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, - Info->BB, - Info->BB->getFirstTerminator(), - VRC, MRI, TII); - Info->AvailableVal = NewDef->getOperand(0).getReg(); - Info->DefBB = Info; - RootList.push_back(Info); - continue; - } - - for (unsigned p = 0; p != Info->NumPreds; ++p) { - MachineBasicBlock *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. - unsigned 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); - } + Updater->VRC, Updater->MRI, + Updater->TII); + return NewDef->getOperand(0).getReg(); } - // 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); + /// CreateEmptyPHI - Create a PHI instruction that defines a new register. + /// Add it into the specified block and return the register. + static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, + MachineSSAUpdater *Updater) { + MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); + MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, + Updater->VRC, Updater->MRI, + Updater->TII); + return PHI->getOperand(0).getReg(); } - 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 (MachineBasicBlock::succ_iterator SI = Info->BB->succ_begin(), - E = Info->BB->succ_end(); SI != E; ++SI) { - BBInfo *SuccInfo = (*BBMap)[*SI]; - if (!SuccInfo || SuccInfo->BlkNum) - continue; - SuccInfo->BlkNum = -1; - WorkList.push_back(SuccInfo); - } + /// AddPHIOperand - Add the specified value as an operand of the PHI for + /// the specified predecessor block. + static void AddPHIOperand(MachineInstr *PHI, unsigned Val, + MachineBasicBlock *Pred) { + PHI->addOperand(MachineOperand::CreateReg(Val, false)); + PHI->addOperand(MachineOperand::CreateMBB(Pred)); } - 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 MachineSSAUpdater::BBInfo * -IntersectDominators(MachineSSAUpdater::BBInfo *Blk1, - MachineSSAUpdater::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; - } - } - 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 MachineSSAUpdater::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 MachineSSAUpdater::BBInfo *Pred, - const MachineSSAUpdater::BBInfo *IDom) { - for (; Pred != IDom; Pred = Pred->IDom) { - if (Pred->DefBB == Pred) - return true; + /// InstrIsPHI - Check if an instruction is a PHI. + /// + static MachineInstr *InstrIsPHI(MachineInstr *I) { + if (I->isPHI()) + return I; + return 0; } - 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 MachineSSAUpdater::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 MachineSSAUpdater::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; - - MachineBasicBlock::iterator Loc = - Info->BB->empty() ? Info->BB->end() : Info->BB->front(); - MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, Info->BB, Loc, - VRC, MRI, TII); - unsigned PHI = InsertedPHI->getOperand(0).getReg(); - Info->AvailableVal = PHI; - AvailableVals[Info->BB] = PHI; + /// ValueIsPHI - Check if the instruction that defines the specified register + /// is a PHI instruction. + static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { + return InstrIsPHI(Updater->MRI->getVRegDef(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. - unsigned PHI = Info->AvailableVal; - MachineInstr *InsertedPHI = MRI->getVRegDef(PHI); - if (!InsertedPHI->isPHI() || InsertedPHI->getNumOperands() > 1) - continue; - - // Iterate through the block's predecessors. - MachineInstrBuilder MIB(InsertedPHI); - for (unsigned p = 0; p != Info->NumPreds; ++p) { - BBInfo *PredInfo = Info->Preds[p]; - MachineBasicBlock *Pred = PredInfo->BB; - // Skip to the nearest preceding definition. - if (PredInfo->DefBB != PredInfo) - PredInfo = PredInfo->DefBB; - MIB.addReg(PredInfo->AvailableVal).addMBB(Pred); - } - - DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); - - // If the client wants to know about all new instructions, tell it. - if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); + /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source + /// operands, i.e., it was just added. + static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { + MachineInstr *PHI = ValueIsPHI(Val, Updater); + if (PHI && PHI->getNumOperands() <= 1) + return PHI; + return 0; } -} -/// FindExistingPHI - Look through the PHI nodes in a block to see if any of -/// them match what is needed. -void MachineSSAUpdater::FindExistingPHI(MachineBasicBlock *BB, - BlockListTy *BlockList) { - for (MachineBasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); - BBI != BBE && BBI->isPHI(); ++BBI) { - if (CheckIfPHIMatches(BBI)) { - RecordMatchingPHI(BBI); - 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 register + /// that it defines. + static unsigned GetPHIValue(MachineInstr *PHI) { + return PHI->getOperand(0).getReg(); } -} - -/// CheckIfPHIMatches - Check if a PHI node matches the placement and values -/// in the BBMap. -bool MachineSSAUpdater::CheckIfPHIMatches(MachineInstr *PHI) { - BBMapTy *BBMap = getBBMap(BM); - SmallVector 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 = 1, e = PHI->getNumOperands(); i != e; i += 2) { - unsigned IncomingVal = PHI->getOperand(i).getReg(); - BBInfo *PredInfo = (*BBMap)[PHI->getOperand(i+1).getMBB()]; - // 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. - MachineInstr *IncomingPHIVal = MRI->getVRegDef(IncomingVal); - if (!IncomingPHIVal->isPHI() || - 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 MachineSSAUpdater::RecordMatchingPHI(MachineInstr *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. +unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ AvailableValsTy &AvailableVals = getAvailableVals(AV); - SmallVector WorkList; - WorkList.push_back(PHI); - - // Record this PHI. - MachineBasicBlock *BB = PHI->getParent(); - AvailableVals[BB] = PHI->getOperand(0).getReg(); - (*BBMap)[BB]->AvailableVal = PHI->getOperand(0).getReg(); - - while (!WorkList.empty()) { - PHI = WorkList.pop_back_val(); - - // Iterate through the PHI's incoming values. - for (unsigned i = 1, e = PHI->getNumOperands(); i != e; i += 2) { - unsigned IncomingVal = PHI->getOperand(i).getReg(); - MachineInstr *IncomingPHIVal = MRI->getVRegDef(IncomingVal); - if (!IncomingPHIVal->isPHI()) continue; - BB = IncomingPHIVal->getParent(); - BBInfo *Info = (*BBMap)[BB]; - if (!Info || Info->AvailableVal) - continue; - - // Record the PHI and add it to the worklist. - AvailableVals[BB] = IncomingVal; - Info->AvailableVal = IncomingVal; - WorkList.push_back(IncomingPHIVal); - } - } + if (unsigned V = AvailableVals[BB]) + return V; + + SSAUpdaterImpl Impl(this, &AvailableVals, InsertedPHIs); + return Impl.GetValue(BB); } diff --git a/lib/Transforms/Utils/SSAUpdater.cpp b/lib/Transforms/Utils/SSAUpdater.cpp index 25d50dbf2a8..f4bdb527655 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 BBMapTy; - typedef DenseMap AvailableValsTy; static AvailableValsTy &getAvailableVals(void *AV) { return *static_cast(AV); } -static BBMapTy *getBBMap(void *BM) { - return static_cast(BM); -} - SSAUpdater::SSAUpdater(SmallVectorImpl *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 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 *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(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 - Traits for the SSAUpdaterImpl template, +/// specialized for SSAUpdater. +namespace llvm { +template<> +class SSAUpdaterTraits { +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 - (Allocator->Allocate(Info->NumPreds * sizeof(SSAUpdater::BBInfo*), - AlignOf::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 RootList; - SmallVector 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 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 *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(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(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(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(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(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 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(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 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(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 Impl(this, &AvailableVals, InsertedPHIs); + return Impl.GetValue(BB); } -- 2.34.1