lib/CodeGen/PHIElimination.cpp

   1 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass eliminates machine instruction PHI nodes by inserting copy
  11 // instructions.  This destroys SSA information, but is the desired input for
  12 // some register allocators.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "phielim"
  17 #include "llvm/CodeGen/LiveVariables.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineInstr.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include <algorithm>
  29 #include <map>
  30 using namespace llvm;
  31
  32 STATISTIC(NumAtomic, "Number of atomic phis lowered");
  33
  34 namespace {
  35   class VISIBILITY_HIDDEN PNE : public MachineFunctionPass {
  36     MachineRegisterInfo  *MRI; // Machine register information
  37
  38   public:
  39     static char ID; // Pass identification, replacement for typeid
  40     PNE() : MachineFunctionPass((intptr_t)&ID) {}
  41
  42     virtual bool runOnMachineFunction(MachineFunction &Fn);
  43
  44     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  45       AU.addPreserved<LiveVariables>();
  46       AU.addPreservedID(MachineLoopInfoID);
  47       AU.addPreservedID(MachineDominatorsID);
  48       MachineFunctionPass::getAnalysisUsage(AU);
  49     }
  50
  51   private:
  52     /// findInsertionPoint - Find a safe location to insert a move to copy
  53     /// source of a PHI instruction.
  54     MachineBasicBlock::iterator
  55       findInsertionPoint(MachineBasicBlock &MBB, MachineInstr *DefMI,
  56                          unsigned DstReg, unsigned SrcReg) const;
  57
  58     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  59     /// in predecessor basic blocks.
  60     ///
  61     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
  62     void LowerAtomicPHINode(MachineBasicBlock &MBB,
  63                             MachineBasicBlock::iterator AfterPHIsIt);
  64
  65     /// analyzePHINodes - Gather information about the PHI nodes in
  66     /// here. In particular, we want to map the number of uses of a virtual
  67     /// register which is used in a PHI node. We map that to the BB the
  68     /// vreg is coming from. This is used later to determine when the vreg
  69     /// is killed in the BB.
  70     ///
  71     void analyzePHINodes(const MachineFunction& Fn);
  72
  73     typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair;
  74     typedef std::map<BBVRegPair, unsigned> VRegPHIUse;
  75
  76     VRegPHIUse VRegPHIUseCount;
  77
  78     // Defs of PHI sources which are implicit_def.
  79     SmallPtrSet<MachineInstr*, 4> ImpDefs;
  80   };
  81
  82   char PNE::ID = 0;
  83   RegisterPass<PNE> X("phi-node-elimination",
  84                       "Eliminate PHI nodes for register allocation");
  85 }
  86
  87 const PassInfo *llvm::PHIEliminationID = X.getPassInfo();
  88
  89 bool PNE::runOnMachineFunction(MachineFunction &Fn) {
  90   MRI = &Fn.getRegInfo();
  91
  92   analyzePHINodes(Fn);
  93
  94   bool Changed = false;
  95
  96   // Eliminate PHI instructions by inserting copies into predecessor blocks.
  97   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  98     Changed |= EliminatePHINodes(Fn, *I);
  99
 100   // Remove dead IMPLICIT_DEF instructions.
 101   for (SmallPtrSet<MachineInstr*,4>::iterator I = ImpDefs.begin(),
 102          E = ImpDefs.end(); I != E; ++I) {
 103     MachineInstr *DefMI = *I;
 104     unsigned DefReg = DefMI->getOperand(0).getReg();
 105     if (MRI->use_begin(DefReg) == MRI->use_end())
 106       DefMI->eraseFromParent();
 107   }
 108
 109   ImpDefs.clear();
 110   VRegPHIUseCount.clear();
 111   return Changed;
 112 }
 113
 114
 115 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 116 /// predecessor basic blocks.
 117 ///
 118 bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) {
 119   if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
 120     return false;   // Quick exit for basic blocks without PHIs.
 121
 122   // Get an iterator to the first instruction after the last PHI node (this may
 123   // also be the end of the basic block).
 124   MachineBasicBlock::iterator AfterPHIsIt = MBB.begin();
 125   while (AfterPHIsIt != MBB.end() &&
 126          AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI)
 127     ++AfterPHIsIt;    // Skip over all of the PHI nodes...
 128
 129   while (MBB.front().getOpcode() == TargetInstrInfo::PHI)
 130     LowerAtomicPHINode(MBB, AfterPHIsIt);
 131
 132   return true;
 133 }
 134
 135 /// findInsertionPoint - Find a safe location to insert a move to copy
 136 /// source of a PHI instruction.
 137 MachineBasicBlock::iterator
 138 PNE::findInsertionPoint(MachineBasicBlock &MBB, MachineInstr *DefMI,
 139                         unsigned DstReg, unsigned SrcReg) const {
 140   if (DefMI->getOpcode() == TargetInstrInfo::PHI ||
 141       DefMI->getParent() != &MBB)
 142     return MBB.getFirstTerminator();
 143
 144   for (MachineRegisterInfo::use_iterator I = MRI->use_begin(SrcReg),
 145          E = MRI->use_end(); I != E; ++I)
 146     if (I->getParent() == &MBB)
 147       return MBB.getFirstTerminator();
 148   for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg),
 149          E = MRI->use_end(); I != E; ++I)
 150     if (I->getParent() == &MBB)
 151       return MBB.getFirstTerminator();
 152
 153   MachineBasicBlock::iterator I = DefMI;
 154   return ++I;
 155 }
 156
 157 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
 158 /// under the assuption that it needs to be lowered in a way that supports
 159 /// atomic execution of PHIs.  This lowering method is always correct all of the
 160 /// time.
 161 void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB,
 162                              MachineBasicBlock::iterator AfterPHIsIt) {
 163   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
 164   MachineInstr *MPhi = MBB.remove(MBB.begin());
 165
 166   unsigned DestReg = MPhi->getOperand(0).getReg();
 167
 168   // Create a new register for the incoming PHI arguments.
 169   MachineFunction &MF = *MBB.getParent();
 170   const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
 171   unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
 172
 173   // Insert a register to register copy in the top of the current block (but
 174   // after any remaining phi nodes) which copies the new incoming register
 175   // into the phi node destination.
 176   //
 177   const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
 178   TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC);
 179
 180   // Update live variable information if there is any...
 181   LiveVariables *LV = getAnalysisToUpdate<LiveVariables>();
 182   if (LV) {
 183     MachineInstr *PHICopy = prior(AfterPHIsIt);
 184
 185     // Increment use count of the newly created virtual register.
 186     LV->getVarInfo(IncomingReg).NumUses++;
 187
 188     // Add information to LiveVariables to know that the incoming value is
 189     // killed.  Note that because the value is defined in several places (once
 190     // each for each incoming block), the "def" block and instruction fields
 191     // for the VarInfo is not filled in.
 192     //
 193     LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
 194
 195     // Since we are going to be deleting the PHI node, if it is the last use
 196     // of any registers, or if the value itself is dead, we need to move this
 197     // information over to the new copy we just inserted.
 198     //
 199     LV->removeVirtualRegistersKilled(MPhi);
 200
 201     // If the result is dead, update LV.
 202     if (MPhi->registerDefIsDead(DestReg)) {
 203       LV->addVirtualRegisterDead(DestReg, PHICopy);
 204       LV->removeVirtualRegistersDead(MPhi);
 205     }
 206
 207     LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true;
 208   }
 209
 210   // Adjust the VRegPHIUseCount map to account for the removal of this PHI
 211   // node.
 212   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
 213     --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(),
 214                                  MPhi->getOperand(i).getReg())];
 215
 216   // Now loop over all of the incoming arguments, changing them to copy into
 217   // the IncomingReg register in the corresponding predecessor basic block.
 218   //
 219   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
 220   for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) {
 221     unsigned SrcReg = MPhi->getOperand(i-1).getReg();
 222     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 223            "Machine PHI Operands must all be virtual registers!");
 224
 225     // If source is defined by an implicit def, there is no need to insert
 226     // a copy.
 227     MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
 228     if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 229       ImpDefs.insert(DefMI);
 230       continue;
 231     }
 232
 233     // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 234     // source path the PHI.
 235     MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMBB();
 236
 237     // Check to make sure we haven't already emitted the copy for this block.
 238     // This can happen because PHI nodes may have multiple entries for the
 239     // same basic block.
 240     if (!MBBsInsertedInto.insert(&opBlock))
 241       continue;  // If the copy has already been emitted, we're done.
 242
 243     // Find a safe location to insert the copy, this may be the first
 244     // terminator in the block (or end()).
 245     MachineBasicBlock::iterator InsertPos =
 246       findInsertionPoint(opBlock, DefMI, IncomingReg, SrcReg);
 247
 248     // Insert the copy.
 249     TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
 250
 251     // Now update live variable information if we have it.  Otherwise we're done
 252     if (!LV) continue;
 253
 254     // We want to be able to insert a kill of the register if this PHI
 255     // (aka, the copy we just inserted) is the last use of the source
 256     // value.  Live variable analysis conservatively handles this by
 257     // saying that the value is live until the end of the block the PHI
 258     // entry lives in.  If the value really is dead at the PHI copy, there
 259     // will be no successor blocks which have the value live-in.
 260     //
 261     // Check to see if the copy is the last use, and if so, update the
 262     // live variables information so that it knows the copy source
 263     // instruction kills the incoming value.
 264     //
 265     LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg);
 266     InRegVI.UsedBlocks[opBlock.getNumber()] = true;
 267
 268     // Loop over all of the successors of the basic block, checking to see
 269     // if the value is either live in the block, or if it is killed in the
 270     // block.  Also check to see if this register is in use by another PHI
 271     // node which has not yet been eliminated.  If so, it will be killed
 272     // at an appropriate point later.
 273     //
 274
 275     // Is it used by any PHI instructions in this block?
 276     bool ValueIsLive = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0;
 277
 278     std::vector<MachineBasicBlock*> OpSuccBlocks;
 279
 280     // Otherwise, scan successors, including the BB the PHI node lives in.
 281     for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
 282            E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) {
 283       MachineBasicBlock *SuccMBB = *SI;
 284
 285       // Is it alive in this successor?
 286       unsigned SuccIdx = SuccMBB->getNumber();
 287       if (SuccIdx < InRegVI.AliveBlocks.size() &&
 288           InRegVI.AliveBlocks[SuccIdx]) {
 289         ValueIsLive = true;
 290         break;
 291       }
 292
 293       OpSuccBlocks.push_back(SuccMBB);
 294     }
 295
 296     // Check to see if this value is live because there is a use in a successor
 297     // that kills it.
 298     if (!ValueIsLive) {
 299       switch (OpSuccBlocks.size()) {
 300       case 1: {
 301         MachineBasicBlock *MBB = OpSuccBlocks[0];
 302         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 303           if (InRegVI.Kills[i]->getParent() == MBB) {
 304             ValueIsLive = true;
 305             break;
 306           }
 307         break;
 308       }
 309       case 2: {
 310         MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1];
 311         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 312           if (InRegVI.Kills[i]->getParent() == MBB1 ||
 313               InRegVI.Kills[i]->getParent() == MBB2) {
 314             ValueIsLive = true;
 315             break;
 316           }
 317         break;
 318       }
 319       default:
 320         std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
 321         for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 322           if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
 323                                  InRegVI.Kills[i]->getParent())) {
 324             ValueIsLive = true;
 325             break;
 326           }
 327       }
 328     }
 329
 330     // Okay, if we now know that the value is not live out of the block,
 331     // we can add a kill marker in this block saying that it kills the incoming
 332     // value!
 333     if (!ValueIsLive) {
 334       // In our final twist, we have to decide which instruction kills the
 335       // register.  In most cases this is the copy, however, the first
 336       // terminator instruction at the end of the block may also use the value.
 337       // In this case, we should mark *it* as being the killing block, not the
 338       // copy.
 339       MachineBasicBlock::iterator KillInst = prior(InsertPos);
 340       MachineBasicBlock::iterator Term = opBlock.getFirstTerminator();
 341       if (Term != opBlock.end()) {
 342         if (Term->readsRegister(SrcReg))
 343           KillInst = Term;
 344
 345         // Check that no other terminators use values.
 346 #ifndef NDEBUG
 347         for (MachineBasicBlock::iterator TI = next(Term); TI != opBlock.end();
 348              ++TI) {
 349           assert(!TI->readsRegister(SrcReg) &&
 350                  "Terminator instructions cannot use virtual registers unless"
 351                  "they are the first terminator in a block!");
 352         }
 353 #endif
 354       }
 355
 356       // Finally, mark it killed.
 357       LV->addVirtualRegisterKilled(SrcReg, KillInst);
 358
 359       // This vreg no longer lives all of the way through opBlock.
 360       unsigned opBlockNum = opBlock.getNumber();
 361       if (opBlockNum < InRegVI.AliveBlocks.size())
 362         InRegVI.AliveBlocks[opBlockNum] = false;
 363     }
 364   }
 365
 366   // Really delete the PHI instruction now!
 367   delete MPhi;
 368   ++NumAtomic;
 369 }
 370
 371 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 372 /// particular, we want to map the number of uses of a virtual register which is
 373 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 374 /// used later to determine when the vreg is killed in the BB.
 375 ///
 376 void PNE::analyzePHINodes(const MachineFunction& Fn) {
 377   for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
 378        I != E; ++I)
 379     for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
 380          BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
 381       for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 382         ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
 383                                      BBI->getOperand(i).getReg())];
 384 }