X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=8071b0a81a89bf0223fa6bf41b221ed7e334faf2;hb=d250329291dd9fe0d5f0e72e6cf1e287558a7cba;hp=ceba842970d3005e474a3bec805546065b7643c9;hpb=8e5f2c6f65841542e2a7092553fe42a00048e4c7;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index ceba842970d..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" @@ -32,58 +34,25 @@ using namespace llvm; STATISTIC(NumAtomic, "Number of atomic phis lowered"); -namespace { - class VISIBILITY_HIDDEN PNE : public MachineFunctionPass { - MachineRegisterInfo *MRI; // Machine register information - - public: - static char ID; // Pass identification, replacement for typeid - PNE() : MachineFunctionPass((intptr_t)&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); - - 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; @@ -110,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); @@ -140,13 +107,58 @@ static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, return true; } +// 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); + } + + 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; + } + + // 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()); @@ -166,15 +178,19 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, if (isSourceDefinedByImplicitDef(MPhi, MRI)) // If all sources of a PHI node are implicit_def, just emit an // implicit_def instead of a copy. - BuildMI(MBB, AfterPHIsIt, + BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg); else { IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 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 = getAnalysisToUpdate(); + LiveVariables *LV = getAnalysisIfAvailable(); if (LV) { MachineInstr *PHICopy = prior(AfterPHIsIt); @@ -187,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 @@ -216,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); @@ -224,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. @@ -236,7 +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(); + MachineBasicBlock::iterator InsertPos = FindCopyInsertPoint(opBlock, SrcReg); // Insert the copy. TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); @@ -255,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. @@ -275,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; } @@ -348,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); } } @@ -363,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();