LLVM API Documentation

PHIElimination.cpp

Go to the documentation of this file.
00001 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass eliminates machine instruction PHI nodes by inserting copy
00011 // instructions.  This destroys SSA information, but is the desired input for
00012 // some register allocators.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/CodeGen/LiveVariables.h"
00017 #include "llvm/CodeGen/Passes.h"
00018 #include "llvm/CodeGen/MachineFunctionPass.h"
00019 #include "llvm/CodeGen/MachineInstr.h"
00020 #include "llvm/CodeGen/SSARegMap.h"
00021 #include "llvm/Target/TargetInstrInfo.h"
00022 #include "llvm/Target/TargetMachine.h"
00023 #include "llvm/ADT/DenseMap.h"
00024 #include "llvm/ADT/STLExtras.h"
00025 #include "llvm/ADT/Statistic.h"
00026 #include <set>
00027 #include <algorithm>
00028 using namespace llvm;
00029 
00030 namespace {
00031   Statistic<> NumAtomic("phielim", "Number of atomic phis lowered");
00032   Statistic<> NumSimple("phielim", "Number of simple phis lowered");
00033   
00034   struct PNE : public MachineFunctionPass {
00035     bool runOnMachineFunction(MachineFunction &Fn) {
00036       bool Changed = false;
00037 
00038       // Eliminate PHI instructions by inserting copies into predecessor blocks.
00039       for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
00040         Changed |= EliminatePHINodes(Fn, *I);
00041 
00042       return Changed;
00043     }
00044 
00045     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00046       AU.addPreserved<LiveVariables>();
00047       MachineFunctionPass::getAnalysisUsage(AU);
00048     }
00049 
00050   private:
00051     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
00052     /// in predecessor basic blocks.
00053     ///
00054     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
00055     void LowerAtomicPHINode(MachineBasicBlock &MBB,
00056                             MachineBasicBlock::iterator AfterPHIsIt,
00057                             DenseMap<unsigned, VirtReg2IndexFunctor> &VUC);
00058   };
00059 
00060   RegisterPass<PNE> X("phi-node-elimination",
00061                       "Eliminate PHI nodes for register allocation");
00062 }
00063 
00064 
00065 const PassInfo *llvm::PHIEliminationID = X.getPassInfo();
00066 
00067 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
00068 /// predecessor basic blocks.
00069 ///
00070 bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) {
00071   if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
00072     return false;   // Quick exit for basic blocks without PHIs.
00073 
00074   // VRegPHIUseCount - Keep track of the number of times each virtual register
00075   // is used by PHI nodes in successors of this block.
00076   DenseMap<unsigned, VirtReg2IndexFunctor> VRegPHIUseCount;
00077   VRegPHIUseCount.grow(MF.getSSARegMap()->getLastVirtReg());
00078 
00079   for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(),
00080          E = MBB.pred_end(); PI != E; ++PI)
00081     for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(),
00082            E = (*PI)->succ_end(); SI != E; ++SI)
00083       for (MachineBasicBlock::iterator BBI = (*SI)->begin(), E = (*SI)->end();
00084            BBI != E && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
00085         for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
00086           VRegPHIUseCount[BBI->getOperand(i).getReg()]++;
00087       
00088   // Get an iterator to the first instruction after the last PHI node (this may
00089   // also be the end of the basic block).
00090   MachineBasicBlock::iterator AfterPHIsIt = MBB.begin();
00091   while (AfterPHIsIt != MBB.end() &&
00092          AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI)
00093     ++AfterPHIsIt;    // Skip over all of the PHI nodes...
00094 
00095   while (MBB.front().getOpcode() == TargetInstrInfo::PHI) {
00096     LowerAtomicPHINode(MBB, AfterPHIsIt, VRegPHIUseCount);
00097   }
00098   return true;
00099 }
00100 
00101 /// InstructionUsesRegister - Return true if the specified machine instr has a
00102 /// use of the specified register.
00103 static bool InstructionUsesRegister(MachineInstr *MI, unsigned SrcReg) {
00104   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
00105     if (MI->getOperand(0).isRegister() &&
00106         MI->getOperand(0).getReg() == SrcReg &&
00107         MI->getOperand(0).isUse())
00108       return true;
00109   return false;
00110 }
00111 
00112 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
00113 /// under the assuption that it needs to be lowered in a way that supports
00114 /// atomic execution of PHIs.  This lowering method is always correct all of the
00115 /// time.
00116 void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB,
00117                              MachineBasicBlock::iterator AfterPHIsIt,
00118                    DenseMap<unsigned, VirtReg2IndexFunctor> &VRegPHIUseCount) {
00119   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
00120   MachineInstr *MPhi = MBB.remove(MBB.begin());
00121 
00122   unsigned DestReg = MPhi->getOperand(0).getReg();
00123 
00124   // Create a new register for the incoming PHI arguments/
00125   MachineFunction &MF = *MBB.getParent();
00126   const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg);
00127   unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC);
00128 
00129   // Insert a register to register copy in the top of the current block (but
00130   // after any remaining phi nodes) which copies the new incoming register
00131   // into the phi node destination.
00132   //
00133   const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo();
00134   RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC);
00135 
00136   // Update live variable information if there is any...
00137   LiveVariables *LV = getAnalysisToUpdate<LiveVariables>();
00138   if (LV) {
00139     MachineInstr *PHICopy = prior(AfterPHIsIt);
00140 
00141     // Add information to LiveVariables to know that the incoming value is
00142     // killed.  Note that because the value is defined in several places (once
00143     // each for each incoming block), the "def" block and instruction fields
00144     // for the VarInfo is not filled in.
00145     //
00146     LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
00147 
00148     // Since we are going to be deleting the PHI node, if it is the last use
00149     // of any registers, or if the value itself is dead, we need to move this
00150     // information over to the new copy we just inserted.
00151     //
00152     LV->removeVirtualRegistersKilled(MPhi);
00153 
00154     // If the result is dead, update LV.
00155     if (LV->RegisterDefIsDead(MPhi, DestReg)) {
00156       LV->addVirtualRegisterDead(DestReg, PHICopy);
00157       LV->removeVirtualRegistersDead(MPhi);
00158     }
00159     
00160     // Realize that the destination register is defined by the PHI copy now, not
00161     // the PHI itself.
00162     LV->getVarInfo(DestReg).DefInst = PHICopy;
00163   }
00164 
00165   // Adjust the VRegPHIUseCount map to account for the removal of this PHI
00166   // node.
00167   unsigned NumPreds = (MPhi->getNumOperands()-1)/2;
00168   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
00169     VRegPHIUseCount[MPhi->getOperand(i).getReg()] -= NumPreds;
00170 
00171   // Now loop over all of the incoming arguments, changing them to copy into
00172   // the IncomingReg register in the corresponding predecessor basic block.
00173   //
00174   std::set<MachineBasicBlock*> MBBsInsertedInto;
00175   for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) {
00176     unsigned SrcReg = MPhi->getOperand(i-1).getReg();
00177     assert(MRegisterInfo::isVirtualRegister(SrcReg) &&
00178            "Machine PHI Operands must all be virtual registers!");
00179 
00180     // Get the MachineBasicBlock equivalent of the BasicBlock that is the
00181     // source path the PHI.
00182     MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMachineBasicBlock();
00183 
00184     // Check to make sure we haven't already emitted the copy for this block.
00185     // This can happen because PHI nodes may have multiple entries for the
00186     // same basic block.
00187     if (!MBBsInsertedInto.insert(&opBlock).second)
00188       continue;  // If the copy has already been emitted, we're done.
00189  
00190     // Get an iterator pointing to the first terminator in the block (or end()).
00191     // This is the point where we can insert a copy if we'd like to.
00192     MachineBasicBlock::iterator I = opBlock.getFirstTerminator();
00193     
00194     // Insert the copy.
00195     RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC);
00196 
00197     // Now update live variable information if we have it.  Otherwise we're done
00198     if (!LV) continue;
00199     
00200     // We want to be able to insert a kill of the register if this PHI
00201     // (aka, the copy we just inserted) is the last use of the source
00202     // value.  Live variable analysis conservatively handles this by
00203     // saying that the value is live until the end of the block the PHI
00204     // entry lives in.  If the value really is dead at the PHI copy, there
00205     // will be no successor blocks which have the value live-in.
00206     //
00207     // Check to see if the copy is the last use, and if so, update the
00208     // live variables information so that it knows the copy source
00209     // instruction kills the incoming value.
00210     //
00211     LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg);
00212 
00213     // Loop over all of the successors of the basic block, checking to see
00214     // if the value is either live in the block, or if it is killed in the
00215     // block.  Also check to see if this register is in use by another PHI
00216     // node which has not yet been eliminated.  If so, it will be killed
00217     // at an appropriate point later.
00218     //
00219 
00220     // Is it used by any PHI instructions in this block?
00221     bool ValueIsLive = VRegPHIUseCount[SrcReg] != 0;
00222 
00223     std::vector<MachineBasicBlock*> OpSuccBlocks;
00224     
00225     // Otherwise, scan successors, including the BB the PHI node lives in.
00226     for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
00227            E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) {
00228       MachineBasicBlock *SuccMBB = *SI;
00229 
00230       // Is it alive in this successor?
00231       unsigned SuccIdx = SuccMBB->getNumber();
00232       if (SuccIdx < InRegVI.AliveBlocks.size() &&
00233           InRegVI.AliveBlocks[SuccIdx]) {
00234         ValueIsLive = true;
00235         break;
00236       }
00237 
00238       OpSuccBlocks.push_back(SuccMBB);
00239     }
00240 
00241     // Check to see if this value is live because there is a use in a successor
00242     // that kills it.
00243     if (!ValueIsLive) {
00244       switch (OpSuccBlocks.size()) {
00245       case 1: {
00246         MachineBasicBlock *MBB = OpSuccBlocks[0];
00247         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
00248           if (InRegVI.Kills[i]->getParent() == MBB) {
00249             ValueIsLive = true;
00250             break;
00251           }
00252         break;
00253       }
00254       case 2: {
00255         MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1];
00256         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
00257           if (InRegVI.Kills[i]->getParent() == MBB1 || 
00258               InRegVI.Kills[i]->getParent() == MBB2) {
00259             ValueIsLive = true;
00260             break;
00261           }
00262         break;        
00263       }
00264       default:
00265         std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
00266         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
00267           if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
00268                                  InRegVI.Kills[i]->getParent())) {
00269             ValueIsLive = true;
00270             break;
00271           }
00272       }
00273     }        
00274 
00275     // Okay, if we now know that the value is not live out of the block,
00276     // we can add a kill marker in this block saying that it kills the incoming
00277     // value!
00278     if (!ValueIsLive) {
00279       // In our final twist, we have to decide which instruction kills the
00280       // register.  In most cases this is the copy, however, the first 
00281       // terminator instruction at the end of the block may also use the value.
00282       // In this case, we should mark *it* as being the killing block, not the
00283       // copy.
00284       bool FirstTerminatorUsesValue = false;
00285       if (I != opBlock.end()) {
00286         FirstTerminatorUsesValue = InstructionUsesRegister(I, SrcReg);
00287       
00288         // Check that no other terminators use values.
00289 #ifndef NDEBUG
00290         for (MachineBasicBlock::iterator TI = next(I); TI != opBlock.end();
00291              ++TI) {
00292           assert(!InstructionUsesRegister(TI, SrcReg) &&
00293                  "Terminator instructions cannot use virtual registers unless"
00294                  "they are the first terminator in a block!");
00295         }
00296 #endif
00297       }
00298       
00299       MachineBasicBlock::iterator KillInst;
00300       if (!FirstTerminatorUsesValue) 
00301         KillInst = prior(I);
00302       else
00303         KillInst = I;
00304       
00305       // Finally, mark it killed.
00306       LV->addVirtualRegisterKilled(SrcReg, KillInst);
00307 
00308       // This vreg no longer lives all of the way through opBlock.
00309       unsigned opBlockNum = opBlock.getNumber();
00310       if (opBlockNum < InRegVI.AliveBlocks.size())
00311         InRegVI.AliveBlocks[opBlockNum] = false;
00312     }
00313   }
00314     
00315   // Really delete the PHI instruction now!
00316   delete MPhi;
00317   ++NumAtomic;
00318 }