X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FPHIElimination.cpp;h=845b1c11d645d7e85211da70c61beab9ec5e0fbf;hb=63e3cd4e0f3731d6801ac24199652e4d7b4b3729;hp=1cffca6b8ff6d1a2a0111c876a7f58c6e3b65df8;hpb=8af24b86a8dea1696839104c34d6445ee7294d2a;p=oota-llvm.git diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 1cffca6b8ff..845b1c11d64 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -13,14 +13,14 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "phielim" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/SSARegMap.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Compiler.h" @@ -28,23 +28,31 @@ #include using namespace llvm; +STATISTIC(NumAtomic, "Number of atomic phis lowered"); +//STATISTIC(NumSimple, "Number of simple phis lowered"); + namespace { - static Statistic<> NumAtomic("phielim", "Number of atomic phis lowered"); - static Statistic<> NumSimple("phielim", "Number of simple phis lowered"); - struct VISIBILITY_HIDDEN PNE : public MachineFunctionPass { + static char ID; // Pass identification, replacement for typeid + PNE() : MachineFunctionPass((intptr_t)&ID) {} + bool runOnMachineFunction(MachineFunction &Fn) { + analyzePHINodes(Fn); + bool Changed = false; // Eliminate PHI instructions by inserting copies into predecessor blocks. for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) Changed |= EliminatePHINodes(Fn, *I); + VRegPHIUseCount.clear(); return Changed; } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); + AU.addPreservedID(MachineLoopInfoID); + AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -54,15 +62,27 @@ namespace { /// bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); void LowerAtomicPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt, - DenseMap &VUC); + 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; }; + char PNE::ID = 0; RegisterPass X("phi-node-elimination", "Eliminate PHI nodes for register allocation"); } - const PassInfo *llvm::PHIEliminationID = X.getPassInfo(); /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in @@ -72,20 +92,6 @@ bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) return false; // Quick exit for basic blocks without PHIs. - // VRegPHIUseCount - Keep track of the number of times each virtual register - // is used by PHI nodes in successors of this block. - DenseMap VRegPHIUseCount; - VRegPHIUseCount.grow(MF.getSSARegMap()->getLastVirtReg()); - - for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(), - E = MBB.pred_end(); PI != E; ++PI) - for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(), - E = (*PI)->succ_end(); SI != E; ++SI) - for (MachineBasicBlock::iterator BBI = (*SI)->begin(), E = (*SI)->end(); - BBI != E && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) - for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) - VRegPHIUseCount[BBI->getOperand(i).getReg()]++; - // 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(); @@ -93,9 +99,9 @@ bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) ++AfterPHIsIt; // Skip over all of the PHI nodes... - while (MBB.front().getOpcode() == TargetInstrInfo::PHI) { - LowerAtomicPHINode(MBB, AfterPHIsIt, VRegPHIUseCount); - } + while (MBB.front().getOpcode() == TargetInstrInfo::PHI) + LowerAtomicPHINode(MBB, AfterPHIsIt); + return true; } @@ -115,30 +121,32 @@ static bool InstructionUsesRegister(MachineInstr *MI, unsigned SrcReg) { /// atomic execution of PHIs. This lowering method is always correct all of the /// time. void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, - MachineBasicBlock::iterator AfterPHIsIt, - DenseMap &VRegPHIUseCount) { + MachineBasicBlock::iterator AfterPHIsIt) { // Unlink the PHI node from the basic block, but don't delete the PHI yet. MachineInstr *MPhi = MBB.remove(MBB.begin()); unsigned DestReg = MPhi->getOperand(0).getReg(); - // Create a new register for the incoming PHI arguments/ + // Create a new register for the incoming PHI arguments. MachineFunction &MF = *MBB.getParent(); - const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); - unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); + const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); + unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC); // Insert a register to register copy in the top of the current block (but // after any remaining phi nodes) which copies the new incoming register // into the phi node destination. // - const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); - RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); + const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); + TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); // Update live variable information if there is any... LiveVariables *LV = getAnalysisToUpdate(); if (LV) { MachineInstr *PHICopy = prior(AfterPHIsIt); + // Increment use count of the newly created virtual register. + LV->getVarInfo(IncomingReg).NumUses++; + // Add information to LiveVariables to know that the incoming value is // killed. Note that because the value is defined in several places (once // each for each incoming block), the "def" block and instruction fields @@ -157,17 +165,15 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, LV->addVirtualRegisterDead(DestReg, PHICopy); LV->removeVirtualRegistersDead(MPhi); } - - // Realize that the destination register is defined by the PHI copy now, not - // the PHI itself. - LV->getVarInfo(DestReg).DefInst = PHICopy; + + LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true; } // Adjust the VRegPHIUseCount map to account for the removal of this PHI // node. - unsigned NumPreds = (MPhi->getNumOperands()-1)/2; for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) - VRegPHIUseCount[MPhi->getOperand(i).getReg()] -= NumPreds; + --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(), + MPhi->getOperand(i).getReg())]; // Now loop over all of the incoming arguments, changing them to copy into // the IncomingReg register in the corresponding predecessor basic block. @@ -175,12 +181,12 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, std::set MBBsInsertedInto; for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { unsigned SrcReg = MPhi->getOperand(i-1).getReg(); - assert(MRegisterInfo::isVirtualRegister(SrcReg) && + 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).getMachineBasicBlock(); + MachineBasicBlock &opBlock = *MPhi->getOperand(i).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 @@ -193,7 +199,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, MachineBasicBlock::iterator I = opBlock.getFirstTerminator(); // Insert the copy. - RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC); + TII->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC, RC); // Now update live variable information if we have it. Otherwise we're done if (!LV) continue; @@ -210,6 +216,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // 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 @@ -219,7 +226,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // // Is it used by any PHI instructions in this block? - bool ValueIsLive = VRegPHIUseCount[SrcReg] != 0; + bool ValueIsLive = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0; std::vector OpSuccBlocks; @@ -317,3 +324,18 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, delete MPhi; ++NumAtomic; } + +/// 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 PNE::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(); + BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) + for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) + ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(), + BBI->getOperand(i).getReg())]; +}