X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=56dca086ef252163c04f285b7370ef8448f5eac3;hb=f0443c1eb44d737d9bd78962932fc80f74c6113c;hp=67c555fd17f8fd314877cd5fb7cf8642e80a8c63;hpb=a5fec0dba34206274041543b5924d2565fb10f9b;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 67c555fd17f..56dca086ef2 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "phielim" +#include "PHIElimination.h" #include "llvm/BasicBlock.h" #include "llvm/Instructions.h" #include "llvm/CodeGen/LiveVariables.h" @@ -22,7 +23,6 @@ #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" @@ -34,78 +34,24 @@ 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(&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); - - // 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 FindCopyInsertPoint(MachineBasicBlock &MBB, - unsigned SrcReg); - - // SkipPHIsAndLabels - Copies need to be inserted after phi nodes and - // also after any exception handling labels: in landing pads execution - // starts at the label, so any copies placed before it won't be executed! - MachineBasicBlock::iterator SkipPHIsAndLabels(MachineBasicBlock &MBB, - MachineBasicBlock::iterator I) { - // Rather than assuming that EH labels come before other kinds of labels, - // just skip all labels. - while (I != MBB.end() && - (I->getOpcode() == TargetInstrInfo::PHI || I->isLabel())) - ++I; - return I; - } - - 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.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; @@ -132,7 +78,8 @@ 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. @@ -162,8 +109,9 @@ static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, // 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 PNE::FindCopyInsertPoint(MachineBasicBlock &MBB, - unsigned SrcReg) { +MachineBasicBlock::iterator +llvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB, + unsigned SrcReg) { // Handle the trivial case trivially. if (MBB.empty()) return MBB.begin(); @@ -206,9 +154,10 @@ MachineBasicBlock::iterator PNE::FindCopyInsertPoint(MachineBasicBlock &MBB, /// 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()); @@ -235,6 +184,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) { @@ -249,8 +202,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 @@ -278,6 +229,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); @@ -286,10 +244,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. @@ -317,7 +271,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. @@ -337,8 +290,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; } @@ -410,8 +362,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); } } @@ -425,7 +376,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();