X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSSAUpdater.cpp;h=17f0af84dde359cf7545a51609c8e3c5e5d352be;hb=ba2a226fab1711e32686d62ae1250ea1400247ee;hp=b8996d46f94050604d9ab188c429d934c36c1296;hpb=211678a0d761942578970fc78a72c56d69ed36db;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSSAUpdater.cpp b/lib/CodeGen/MachineSSAUpdater.cpp index b8996d46f94..17f0af84dde 100644 --- a/lib/CodeGen/MachineSSAUpdater.cpp +++ b/lib/CodeGen/MachineSSAUpdater.cpp @@ -13,58 +13,36 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/MachineSSAUpdater.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.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(); } MachineSSAUpdater::~MachineSSAUpdater() { - delete &getAvailableVals(AV); + delete static_cast(AV); } /// Initialize - Reset this object to get ready for a new set of SSA @@ -99,11 +77,11 @@ unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { static unsigned LookForIdenticalPHI(MachineBasicBlock *BB, - SmallVector, 8> &PredValues) { + SmallVectorImpl > &PredValues) { if (BB->empty()) return 0; - MachineBasicBlock::iterator I = BB->front(); + MachineBasicBlock::iterator I = BB->begin(); if (!I->isPHI()) return 0; @@ -131,10 +109,11 @@ unsigned LookForIdenticalPHI(MachineBasicBlock *BB, /// a value of the given register class at the start of the specified basic /// block. It returns the virtual register defined by the instruction. static -MachineInstr *InsertNewDef(unsigned Opcode, +MachineInstrBuilder 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); } @@ -203,14 +182,13 @@ unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { return DupPHI; // Otherwise, we do need a PHI: insert one now. - MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front(); - MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, - Loc, VRC, MRI, TII); + MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); + MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, + Loc, VRC, MRI, TII); // Fill in all the predecessors of the PHI. - MachineInstrBuilder MIB(InsertedPHI); for (unsigned i = 0, e = PredValues.size(); i != e; ++i) - MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first); + InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first); // See if the PHI node can be merged to a single value. This can happen in // loop cases when we get a PHI of itself and one other value. @@ -235,7 +213,6 @@ MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, } llvm_unreachable("MachineOperand::getParent() failure?"); - return 0; } /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, @@ -263,438 +240,125 @@ 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; - - // 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(); } + + /// Iterator for PHI operands. + class PHI_iterator { + private: + MachineInstr *PHI; + unsigned idx; + + public: + explicit PHI_iterator(MachineInstr *P) // begin iterator + : PHI(P), idx(1) {} + PHI_iterator(MachineInstr *P, bool) // end iterator + : PHI(P), idx(PHI->getNumOperands()) {} + + PHI_iterator &operator++() { idx += 2; return *this; } + bool operator==(const PHI_iterator& x) const { return idx == x.idx; } + bool operator!=(const PHI_iterator& x) const { return !operator==(x); } + unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } + MachineBasicBlock *getIncomingBlock() { + return PHI->getOperand(idx+1).getMBB(); + } + }; + 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); - } - } - - // 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); + Updater->VRC, Updater->MRI, + Updater->TII); + return NewDef->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); - } + /// 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->begin(); + MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, + Updater->VRC, Updater->MRI, + Updater->TII); + return PHI->getOperand(0).getReg(); } - 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; - } + /// 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) { + MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(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 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 && 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; +} // End llvm namespace - 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 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); }