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 "PHIElimination.h"
  18 #include "llvm/BasicBlock.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/CodeGen/LiveVariables.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/Target/TargetMachine.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/Debug.h"
  33 #include <algorithm>
  34 #include <map>
  35 using namespace llvm;
  36
  37 STATISTIC(NumAtomic, "Number of atomic phis lowered");
  38 STATISTIC(NumSplits, "Number of critical edges split on demand");
  39
  40 static cl::opt<bool>
  41 SplitEdges("split-phi-edges",
  42            cl::desc("Split critical edges during phi elimination"),
  43            cl::init(false), cl::Hidden);
  44
  45 char PHIElimination::ID = 0;
  46 static RegisterPass<PHIElimination>
  47 X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
  48
  49 const PassInfo *const llvm::PHIEliminationID = &X;
  50
  51 void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
  52   AU.addPreserved<LiveVariables>();
  53   if (SplitEdges) {
  54     AU.addRequired<LiveVariables>();
  55   } else {
  56     AU.setPreservesCFG();
  57     AU.addPreservedID(MachineLoopInfoID);
  58     AU.addPreservedID(MachineDominatorsID);
  59   }
  60   MachineFunctionPass::getAnalysisUsage(AU);
  61 }
  62
  63 bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
  64   MRI = &Fn.getRegInfo();
  65
  66   PHIDefs.clear();
  67   PHIKills.clear();
  68   analyzePHINodes(Fn);
  69
  70   bool Changed = false;
  71
  72   // Eliminate PHI instructions by inserting copies into predecessor blocks.
  73   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  74     Changed |= EliminatePHINodes(Fn, *I);
  75
  76   // Remove dead IMPLICIT_DEF instructions.
  77   for (SmallPtrSet<MachineInstr*,4>::iterator I = ImpDefs.begin(),
  78          E = ImpDefs.end(); I != E; ++I) {
  79     MachineInstr *DefMI = *I;
  80     unsigned DefReg = DefMI->getOperand(0).getReg();
  81     if (MRI->use_empty(DefReg))
  82       DefMI->eraseFromParent();
  83   }
  84
  85   ImpDefs.clear();
  86   VRegPHIUseCount.clear();
  87   return Changed;
  88 }
  89
  90
  91 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
  92 /// predecessor basic blocks.
  93 ///
  94 bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF,
  95                                              MachineBasicBlock &MBB) {
  96   if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
  97     return false;   // Quick exit for basic blocks without PHIs.
  98
  99   if (SplitEdges)
 100     SplitPHIEdges(MF, MBB);
 101
 102   // Get an iterator to the first instruction after the last PHI node (this may
 103   // also be the end of the basic block).
 104   MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin());
 105
 106   while (MBB.front().getOpcode() == TargetInstrInfo::PHI)
 107     LowerAtomicPHINode(MBB, AfterPHIsIt);
 108
 109   return true;
 110 }
 111
 112 /// isSourceDefinedByImplicitDef - Return true if all sources of the phi node
 113 /// are implicit_def's.
 114 static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
 115                                          const MachineRegisterInfo *MRI) {
 116   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
 117     unsigned SrcReg = MPhi->getOperand(i).getReg();
 118     const MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
 119     if (!DefMI || DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF)
 120       return false;
 121   }
 122   return true;
 123 }
 124
 125 // FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg.
 126 // This needs to be after any def or uses of SrcReg, but before any subsequent
 127 // point where control flow might jump out of the basic block.
 128 MachineBasicBlock::iterator
 129 llvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB,
 130                                           unsigned SrcReg) {
 131   // Handle the trivial case trivially.
 132   if (MBB.empty())
 133     return MBB.begin();
 134
 135   // If this basic block does not contain an invoke, then control flow always
 136   // reaches the end of it, so place the copy there.  The logic below works in
 137   // this case too, but is more expensive.
 138   if (!isa<InvokeInst>(MBB.getBasicBlock()->getTerminator()))
 139     return MBB.getFirstTerminator();
 140
 141   // Discover any definition/uses in this basic block.
 142   SmallPtrSet<MachineInstr*, 8> DefUsesInMBB;
 143   for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
 144        RE = MRI->reg_end(); RI != RE; ++RI) {
 145     MachineInstr *DefUseMI = &*RI;
 146     if (DefUseMI->getParent() == &MBB)
 147       DefUsesInMBB.insert(DefUseMI);
 148   }
 149
 150   MachineBasicBlock::iterator InsertPoint;
 151   if (DefUsesInMBB.empty()) {
 152     // No def/uses.  Insert the copy at the start of the basic block.
 153     InsertPoint = MBB.begin();
 154   } else if (DefUsesInMBB.size() == 1) {
 155     // Insert the copy immediately after the definition/use.
 156     InsertPoint = *DefUsesInMBB.begin();
 157     ++InsertPoint;
 158   } else {
 159     // Insert the copy immediately after the last definition/use.
 160     InsertPoint = MBB.end();
 161     while (!DefUsesInMBB.count(&*--InsertPoint)) {}
 162     ++InsertPoint;
 163   }
 164
 165   // Make sure the copy goes after any phi nodes however.
 166   return SkipPHIsAndLabels(MBB, InsertPoint);
 167 }
 168
 169 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
 170 /// under the assuption that it needs to be lowered in a way that supports
 171 /// atomic execution of PHIs.  This lowering method is always correct all of the
 172 /// time.
 173 ///
 174 void llvm::PHIElimination::LowerAtomicPHINode(
 175                                       MachineBasicBlock &MBB,
 176                                       MachineBasicBlock::iterator AfterPHIsIt) {
 177   // Unlink the PHI node from the basic block, but don't delete the PHI yet.
 178   MachineInstr *MPhi = MBB.remove(MBB.begin());
 179
 180   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
 181   unsigned DestReg = MPhi->getOperand(0).getReg();
 182   bool isDead = MPhi->getOperand(0).isDead();
 183
 184   // Create a new register for the incoming PHI arguments.
 185   MachineFunction &MF = *MBB.getParent();
 186   const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
 187   unsigned IncomingReg = 0;
 188
 189   // Insert a register to register copy at the top of the current block (but
 190   // after any remaining phi nodes) which copies the new incoming register
 191   // into the phi node destination.
 192   const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
 193   if (isSourceDefinedByImplicitDef(MPhi, MRI))
 194     // If all sources of a PHI node are implicit_def, just emit an
 195     // implicit_def instead of a copy.
 196     BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
 197             TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg);
 198   else {
 199     IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
 200     TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC);
 201   }
 202
 203   // Record PHI def.
 204   assert(!hasPHIDef(DestReg) && "Vreg has multiple phi-defs?");
 205   PHIDefs[DestReg] = &MBB;
 206
 207   // Update live variable information if there is any.
 208   LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
 209   if (LV) {
 210     MachineInstr *PHICopy = prior(AfterPHIsIt);
 211
 212     if (IncomingReg) {
 213       // Increment use count of the newly created virtual register.
 214       LV->getVarInfo(IncomingReg).NumUses++;
 215
 216       // Add information to LiveVariables to know that the incoming value is
 217       // killed.  Note that because the value is defined in several places (once
 218       // each for each incoming block), the "def" block and instruction fields
 219       // for the VarInfo is not filled in.
 220       LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
 221     }
 222
 223     // Since we are going to be deleting the PHI node, if it is the last use of
 224     // any registers, or if the value itself is dead, we need to move this
 225     // information over to the new copy we just inserted.
 226     LV->removeVirtualRegistersKilled(MPhi);
 227
 228     // If the result is dead, update LV.
 229     if (isDead) {
 230       LV->addVirtualRegisterDead(DestReg, PHICopy);
 231       LV->removeVirtualRegisterDead(DestReg, MPhi);
 232     }
 233   }
 234
 235   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
 236   for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
 237     --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(),
 238                                  MPhi->getOperand(i).getReg())];
 239
 240   // Now loop over all of the incoming arguments, changing them to copy into the
 241   // IncomingReg register in the corresponding predecessor basic block.
 242   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
 243   for (int i = NumSrcs - 1; i >= 0; --i) {
 244     unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
 245     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 246            "Machine PHI Operands must all be virtual registers!");
 247
 248     // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
 249     // path the PHI.
 250     MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
 251
 252     // Record the kill.
 253     PHIKills[SrcReg].insert(&opBlock);
 254
 255     // If source is defined by an implicit def, there is no need to insert a
 256     // copy.
 257     MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
 258     if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 259       ImpDefs.insert(DefMI);
 260       continue;
 261     }
 262
 263     // Check to make sure we haven't already emitted the copy for this block.
 264     // This can happen because PHI nodes may have multiple entries for the same
 265     // basic block.
 266     if (!MBBsInsertedInto.insert(&opBlock))
 267       continue;  // If the copy has already been emitted, we're done.
 268
 269     // Find a safe location to insert the copy, this may be the first terminator
 270     // in the block (or end()).
 271     MachineBasicBlock::iterator InsertPos = FindCopyInsertPoint(opBlock, SrcReg);
 272
 273     // Insert the copy.
 274     TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
 275
 276     // Now update live variable information if we have it.  Otherwise we're done
 277     if (!LV) continue;
 278
 279     // We want to be able to insert a kill of the register if this PHI (aka, the
 280     // copy we just inserted) is the last use of the source value.  Live
 281     // variable analysis conservatively handles this by saying that the value is
 282     // live until the end of the block the PHI entry lives in.  If the value
 283     // really is dead at the PHI copy, there will be no successor blocks which
 284     // have the value live-in.
 285
 286     // Also check to see if this register is in use by another PHI node which
 287     // has not yet been eliminated.  If so, it will be killed at an appropriate
 288     // point later.
 289
 290     // Is it used by any PHI instructions in this block?
 291     bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0;
 292
 293     // Okay, if we now know that the value is not live out of the block, we can
 294     // add a kill marker in this block saying that it kills the incoming value!
 295     // When SplitEdges is enabled, the value is never live out.
 296     if (!ValueIsUsed && (SplitEdges || !isLiveOut(SrcReg, opBlock, *LV))) {
 297       // In our final twist, we have to decide which instruction kills the
 298       // register.  In most cases this is the copy, however, the first
 299       // terminator instruction at the end of the block may also use the value.
 300       // In this case, we should mark *it* as being the killing block, not the
 301       // copy.
 302       MachineBasicBlock::iterator KillInst = prior(InsertPos);
 303       MachineBasicBlock::iterator Term = opBlock.getFirstTerminator();
 304       if (Term != opBlock.end()) {
 305         if (Term->readsRegister(SrcReg))
 306           KillInst = Term;
 307
 308         // Check that no other terminators use values.
 309 #ifndef NDEBUG
 310         for (MachineBasicBlock::iterator TI = next(Term); TI != opBlock.end();
 311              ++TI) {
 312           assert(!TI->readsRegister(SrcReg) &&
 313                  "Terminator instructions cannot use virtual registers unless"
 314                  "they are the first terminator in a block!");
 315         }
 316 #endif
 317       }
 318
 319       // Finally, mark it killed.
 320       LV->addVirtualRegisterKilled(SrcReg, KillInst);
 321
 322       // This vreg no longer lives all of the way through opBlock.
 323       unsigned opBlockNum = opBlock.getNumber();
 324       LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
 325     }
 326   }
 327
 328   // Really delete the PHI instruction now!
 329   MF.DeleteMachineInstr(MPhi);
 330   ++NumAtomic;
 331 }
 332
 333 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 334 /// particular, we want to map the number of uses of a virtual register which is
 335 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 336 /// used later to determine when the vreg is killed in the BB.
 337 ///
 338 void llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) {
 339   for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
 340        I != E; ++I)
 341     for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
 342          BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI)
 343       for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
 344         ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(),
 345                                      BBI->getOperand(i).getReg())];
 346 }
 347
 348 void llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
 349                                          MachineBasicBlock &MBB) {
 350   LiveVariables &LV = getAnalysis<LiveVariables>();
 351   for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
 352        BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
 353     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
 354       unsigned Reg = BBI->getOperand(i).getReg();
 355       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
 356       // We break edges when registers are live out from the predecessor block
 357       // (not considering PHI nodes).
 358       if (isLiveOut(Reg, *PreMBB, LV))
 359         SplitCriticalEdge(PreMBB, &MBB);
 360     }
 361   }
 362 }
 363
 364 bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB,
 365                                      LiveVariables &LV) {
 366   LiveVariables::VarInfo &InRegVI = LV.getVarInfo(Reg);
 367
 368   // Loop over all of the successors of the basic block, checking to see if
 369   // the value is either live in the block, or if it is killed in the block.
 370   std::vector<MachineBasicBlock*> OpSuccBlocks;
 371
 372   // Otherwise, scan successors, including the BB the PHI node lives in.
 373   for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
 374          E = MBB.succ_end(); SI != E; ++SI) {
 375     MachineBasicBlock *SuccMBB = *SI;
 376
 377     // Is it alive in this successor?
 378     unsigned SuccIdx = SuccMBB->getNumber();
 379     if (InRegVI.AliveBlocks.test(SuccIdx))
 380       return true;
 381     OpSuccBlocks.push_back(SuccMBB);
 382   }
 383
 384   // Check to see if this value is live because there is a use in a successor
 385   // that kills it.
 386   switch (OpSuccBlocks.size()) {
 387   case 1: {
 388     MachineBasicBlock *SuccMBB = OpSuccBlocks[0];
 389     for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 390       if (InRegVI.Kills[i]->getParent() == SuccMBB)
 391         return true;
 392     break;
 393   }
 394   case 2: {
 395     MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];
 396     for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 397       if (InRegVI.Kills[i]->getParent() == SuccMBB1 ||
 398           InRegVI.Kills[i]->getParent() == SuccMBB2)
 399         return true;
 400     break;
 401   }
 402   default:
 403     std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
 404     for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 405       if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
 406                              InRegVI.Kills[i]->getParent()))
 407         return true;
 408   }
 409   return false;
 410 }
 411
 412 MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
 413                                                      MachineBasicBlock *B) {
 414   assert(A && B && "Missing MBB end point");
 415   ++NumSplits;
 416
 417   MachineFunction *MF = A->getParent();
 418   MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(B->getBasicBlock());
 419   MF->push_back(NMBB);
 420   const unsigned NewNum = NMBB->getNumber();
 421   DEBUG(errs() << "PHIElimination splitting critical edge:"
 422         " BB#" << A->getNumber()
 423         << " -- BB#" << NewNum
 424         << " -- BB#" << B->getNumber() << '\n');
 425
 426   A->ReplaceUsesOfBlockWith(B, NMBB);
 427   NMBB->addSuccessor(B);
 428
 429   // Insert unconditional "jump B" instruction in NMBB.
 430   SmallVector<MachineOperand, 4> Cond;
 431   MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond);
 432
 433   LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
 434   if (LV)
 435     LV->addNewBlock(NMBB, B);
 436
 437   // Fix PHI nodes in B so they refer to NMBB instead of A
 438   for (MachineBasicBlock::iterator i = B->begin(), e = B->end();
 439        i != e && i->getOpcode() == TargetInstrInfo::PHI; ++i)
 440     for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
 441       if (i->getOperand(ni+1).getMBB() == A) {
 442         i->getOperand(ni+1).setMBB(NMBB);
 443         // Mark PHI sources as passing live through NMBB
 444         if (LV)
 445           LV->getVarInfo(i->getOperand(ni).getReg()).AliveBlocks.set(NewNum);
 446       }
 447   return NMBB;
 448 }
 449
 450