X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=8071b0a81a89bf0223fa6bf41b221ed7e334faf2;hb=d5bbb07ec806e6fa1e804afd7073987fdacc83e4;hp=6f3c82c70811ef3b9b3c5f430deb5dbc0a8e0c92;hpb=db14d63ceac6d667dc1669d199c01a8d3246203c;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 6f3c82c7081..8071b0a81a8 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -14,13 +14,15 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "phielim" +#include "PHIElimination.h" +#include "llvm/BasicBlock.h" +#include "llvm/Instructions.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineFunctionPass.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/ADT/SmallPtrSet.h" #include "llvm/ADT/STLExtras.h" @@ -31,63 +33,26 @@ using namespace llvm; STATISTIC(NumAtomic, "Number of atomic phis lowered"); -STATISTIC(NumEH, "Number of EH try blocks skipped"); -namespace { - class VISIBILITY_HIDDEN PNE : public MachineFunctionPass { - MachineRegisterInfo *MRI; // Machine register information - - public: - static char ID; // Pass identification, replacement for typeid - PNE() : MachineFunctionPass(&ID) {} - - virtual bool runOnMachineFunction(MachineFunction &Fn); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addPreserved(); - AU.addPreservedID(MachineLoopInfoID); - AU.addPreservedID(MachineDominatorsID); - MachineFunctionPass::getAnalysisUsage(AU); - } - - private: - /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions - /// in predecessor basic blocks. - /// - bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); - void LowerAtomicPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt); - - /// analyzePHINodes - Gather information about the PHI nodes in - /// here. In particular, we want to map the number of uses of a virtual - /// register which is used in a PHI node. We map that to the BB the - /// vreg is coming from. This is used later to determine when the vreg - /// is killed in the BB. - /// - void analyzePHINodes(const MachineFunction& Fn); - - void WalkPassEHTryRange(MachineBasicBlock &MBB, - MachineBasicBlock::iterator &I, unsigned SrcReg); - - typedef std::pair BBVRegPair; - typedef std::map VRegPHIUse; - - VRegPHIUse VRegPHIUseCount; - - // Defs of PHI sources which are implicit_def. - SmallPtrSet ImpDefs; - }; -} - -char PNE::ID = 0; -static RegisterPass +char PHIElimination::ID = 0; +static RegisterPass X("phi-node-elimination", "Eliminate PHI nodes for register allocation"); const PassInfo *const llvm::PHIEliminationID = &X; -bool PNE::runOnMachineFunction(MachineFunction &Fn) { +void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addPreserved(); + AU.addPreservedID(MachineLoopInfoID); + AU.addPreservedID(MachineDominatorsID); + MachineFunctionPass::getAnalysisUsage(AU); +} + +bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) { MRI = &Fn.getRegInfo(); + PHIDefs.clear(); + PHIKills.clear(); analyzePHINodes(Fn); bool Changed = false; @@ -114,16 +79,14 @@ bool PNE::runOnMachineFunction(MachineFunction &Fn) { /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in /// predecessor basic blocks. /// -bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { +bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, + MachineBasicBlock &MBB) { if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) return false; // Quick exit for basic blocks without PHIs. // Get an iterator to the first instruction after the last PHI node (this may // also be the end of the basic block). - MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); - while (AfterPHIsIt != MBB.end() && - AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) - ++AfterPHIsIt; // Skip over all of the PHI nodes... + MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin()); while (MBB.front().getOpcode() == TargetInstrInfo::PHI) LowerAtomicPHINode(MBB, AfterPHIsIt); @@ -144,46 +107,58 @@ static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, return true; } -void PNE::WalkPassEHTryRange(MachineBasicBlock &MBB, - MachineBasicBlock::iterator &I, unsigned SrcReg) { - if (I == MBB.begin()) - return; - MachineBasicBlock::iterator PI = prior(I); - if (PI->getOpcode() != TargetInstrInfo::EH_LABEL) - return; - - // Trying to walk pass the EH try range. If we run into a use instruction, - // we want to insert the copy there. - SmallPtrSet UsesInMBB; - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SrcReg), - UE = MRI->use_end(); UI != UE; ++UI) { - MachineInstr *UseMI = &*UI; - if (UseMI->getParent() == &MBB) - UsesInMBB.insert(UseMI); +// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg. +// This needs to be after any def or uses of SrcReg, but before any subsequent +// point where control flow might jump out of the basic block. +MachineBasicBlock::iterator +llvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB, + unsigned SrcReg) { + // Handle the trivial case trivially. + if (MBB.empty()) + return MBB.begin(); + + // If this basic block does not contain an invoke, then control flow always + // reaches the end of it, so place the copy there. The logic below works in + // this case too, but is more expensive. + if (!isa(MBB.getBasicBlock()->getTerminator())) + return MBB.getFirstTerminator(); + + // Discover any definition/uses in this basic block. + SmallPtrSet DefUsesInMBB; + for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), + RE = MRI->reg_end(); RI != RE; ++RI) { + MachineInstr *DefUseMI = &*RI; + if (DefUseMI->getParent() == &MBB) + DefUsesInMBB.insert(DefUseMI); } - while (PI != MBB.begin()) { - --PI; - if (PI->getOpcode() == TargetInstrInfo::EH_LABEL) { - ++NumEH; - I = PI; - return; - } else if (UsesInMBB.count(&*PI)) { - ++NumEH; - I = next(PI); - return; - } + MachineBasicBlock::iterator InsertPoint; + if (DefUsesInMBB.empty()) { + // No def/uses. Insert the copy at the start of the basic block. + InsertPoint = MBB.begin(); + } else if (DefUsesInMBB.size() == 1) { + // Insert the copy immediately after the definition/use. + InsertPoint = *DefUsesInMBB.begin(); + ++InsertPoint; + } else { + // Insert the copy immediately after the last definition/use. + InsertPoint = MBB.end(); + while (!DefUsesInMBB.count(&*--InsertPoint)) {} + ++InsertPoint; } - return; + + // Make sure the copy goes after any phi nodes however. + return SkipPHIsAndLabels(MBB, InsertPoint); } /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, /// under the assuption that it needs to be lowered in a way that supports /// atomic execution of PHIs. This lowering method is always correct all of the /// time. -/// -void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt) { +/// +void llvm::PHIElimination::LowerAtomicPHINode( + MachineBasicBlock &MBB, + MachineBasicBlock::iterator AfterPHIsIt) { // Unlink the PHI node from the basic block, but don't delete the PHI yet. MachineInstr *MPhi = MBB.remove(MBB.begin()); @@ -210,6 +185,10 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); } + // Record PHI def. + assert(!hasPHIDef(DestReg) && "Vreg has multiple phi-defs?"); + PHIDefs[DestReg] = &MBB; + // Update live variable information if there is any. LiveVariables *LV = getAnalysisIfAvailable(); if (LV) { @@ -224,8 +203,6 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // each for each incoming block), the "def" block and instruction fields // for the VarInfo is not filled in. LV->addVirtualRegisterKilled(IncomingReg, PHICopy); - - LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true; } // Since we are going to be deleting the PHI node, if it is the last use of @@ -253,6 +230,13 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && "Machine PHI Operands must all be virtual registers!"); + // Get the MachineBasicBlock equivalent of the BasicBlock that is the source + // path the PHI. + MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); + + // Record the kill. + PHIKills[SrcReg].insert(&opBlock); + // If source is defined by an implicit def, there is no need to insert a // copy. MachineInstr *DefMI = MRI->getVRegDef(SrcReg); @@ -261,10 +245,6 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, continue; } - // Get the MachineBasicBlock equivalent of the BasicBlock that is the source - // path the PHI. - MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); - // Check to make sure we haven't already emitted the copy for this block. // This can happen because PHI nodes may have multiple entries for the same // basic block. @@ -273,10 +253,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // Find a safe location to insert the copy, this may be the first terminator // in the block (or end()). - MachineBasicBlock::iterator InsertPos = opBlock.getFirstTerminator(); - - // Walk pass EH try range if needed. - WalkPassEHTryRange(opBlock, InsertPos, SrcReg); + MachineBasicBlock::iterator InsertPos = FindCopyInsertPoint(opBlock, SrcReg); // Insert the copy. TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); @@ -295,7 +272,6 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // variables information so that it knows the copy source instruction kills // the incoming value. LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); - InRegVI.UsedBlocks[opBlock.getNumber()] = true; // Loop over all of the successors of the basic block, checking to see if // the value is either live in the block, or if it is killed in the block. @@ -315,8 +291,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // Is it alive in this successor? unsigned SuccIdx = SuccMBB->getNumber(); - if (SuccIdx < InRegVI.AliveBlocks.size() && - InRegVI.AliveBlocks[SuccIdx]) { + if (InRegVI.AliveBlocks.test(SuccIdx)) { ValueIsLive = true; break; } @@ -388,8 +363,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // This vreg no longer lives all of the way through opBlock. unsigned opBlockNum = opBlock.getNumber(); - if (opBlockNum < InRegVI.AliveBlocks.size()) - InRegVI.AliveBlocks[opBlockNum] = false; + InRegVI.AliveBlocks.reset(opBlockNum); } } @@ -403,7 +377,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, /// used in a PHI node. We map that to the BB the vreg is coming from. This is /// used later to determine when the vreg is killed in the BB. /// -void PNE::analyzePHINodes(const MachineFunction& Fn) { +void llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) { for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();