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