lib/CodeGen/PHIElimination.cpp

   1 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
   2 //
   3 // This pass eliminates machine instruction PHI nodes by inserting copy
   4 // instructions.  This destroys SSA information, but is the desired input for
   5 // some register allocators.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/CodeGen/MachineFunctionPass.h"
  10 #include "llvm/CodeGen/MachineInstr.h"
  11 #include "llvm/CodeGen/SSARegMap.h"
  12 #include "llvm/CodeGen/LiveVariables.h"
  13 #include "llvm/Target/TargetInstrInfo.h"
  14 #include "llvm/Target/TargetMachine.h"
  15 #include "llvm/Support/CFG.h"
  16
  17 namespace {
  18   struct PNE : public MachineFunctionPass {
  19     bool runOnMachineFunction(MachineFunction &Fn) {
  20       bool Changed = false;
  21
  22       // Eliminate PHI instructions by inserting copies into predecessor blocks.
  23       //
  24       for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
  25         Changed |= EliminatePHINodes(Fn, *I);
  26
  27       //std::cerr << "AFTER PHI NODE ELIM:\n";
  28       //Fn.dump();
  29       return Changed;
  30     }
  31
  32     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  33       AU.addPreserved<LiveVariables>();
  34       MachineFunctionPass::getAnalysisUsage(AU);
  35     }
  36
  37   private:
  38     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
  39     /// in predecessor basic blocks.
  40     ///
  41     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
  42   };
  43
  44   RegisterPass<PNE> X("phi-node-elimination",
  45                       "Eliminate PHI nodes for register allocation");
  46 }
  47
  48 const PassInfo *PHIEliminationID = X.getPassInfo();
  49
  50 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
  51 /// predecessor basic blocks.
  52 ///
  53 bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) {
  54   if (MBB.empty() || MBB.front()->getOpcode() != TargetInstrInfo::PHI)
  55     return false;   // Quick exit for normal case...
  56
  57   LiveVariables *LV = getAnalysisToUpdate<LiveVariables>();
  58   const TargetInstrInfo &MII = MF.getTarget().getInstrInfo();
  59   const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo();
  60
  61   while (MBB.front()->getOpcode() == TargetInstrInfo::PHI) {
  62     MachineInstr *MI = MBB.front();
  63     // Unlink the PHI node from the basic block... but don't delete the PHI yet
  64     MBB.erase(MBB.begin());
  65
  66     assert(MI->getOperand(0).isVirtualRegister() &&
  67            "PHI node doesn't write virt reg?");
  68
  69     unsigned DestReg = MI->getOperand(0).getAllocatedRegNum();
  70
  71     // Create a new register for the incoming PHI arguments
  72     const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg);
  73     unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC);
  74
  75     // Insert a register to register copy in the top of the current block (but
  76     // after any remaining phi nodes) which copies the new incoming register
  77     // into the phi node destination.
  78     //
  79     MachineBasicBlock::iterator AfterPHIsIt = MBB.begin();
  80     while (AfterPHIsIt != MBB.end() &&
  81            (*AfterPHIsIt)->getOpcode() == TargetInstrInfo::PHI)
  82       ++AfterPHIsIt;    // Skip over all of the PHI nodes...
  83     RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC);
  84
  85     // Update live variable information if there is any...
  86     if (LV) {
  87       MachineInstr *PHICopy = *(AfterPHIsIt-1);
  88
  89       // Add information to LiveVariables to know that the incoming value is
  90       // killed.  Note that because the value is defined in several places (once
  91       // each for each incoming block), the "def" block and instruction fields
  92       // for the VarInfo is not filled in.
  93       //
  94       LV->addVirtualRegisterKilled(IncomingReg, &MBB, PHICopy);
  95
  96       // Since we are going to be deleting the PHI node, if it is the last use
  97       // of any registers, or if the value itself is dead, we need to move this
  98       // information over to the new copy we just inserted...
  99       //
 100       std::pair<LiveVariables::killed_iterator, LiveVariables::killed_iterator>
 101         RKs = LV->killed_range(MI);
 102       std::vector<std::pair<MachineInstr*, unsigned> > Range;
 103       if (RKs.first != RKs.second) {
 104         // Copy the range into a vector...
 105         Range.assign(RKs.first, RKs.second);
 106
 107         // Delete the range...
 108         LV->removeVirtualRegistersKilled(RKs.first, RKs.second);
 109
 110         // Add all of the kills back, which will update the appropriate info...
 111         for (unsigned i = 0, e = Range.size(); i != e; ++i)
 112           LV->addVirtualRegisterKilled(Range[i].second, &MBB, PHICopy);
 113       }
 114
 115       RKs = LV->dead_range(MI);
 116       if (RKs.first != RKs.second) {
 117         // Works as above...
 118         Range.assign(RKs.first, RKs.second);
 119         LV->removeVirtualRegistersDead(RKs.first, RKs.second);
 120         for (unsigned i = 0, e = Range.size(); i != e; ++i)
 121           LV->addVirtualRegisterDead(Range[i].second, &MBB, PHICopy);
 122       }
 123     }
 124
 125     // Now loop over all of the incoming arguments, changing them to copy into
 126     // the IncomingReg register in the corresponding predecessor basic block.
 127     //
 128     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 129       MachineOperand &opVal = MI->getOperand(i-1);
 130
 131       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 132       // source path the PHI.
 133       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 134
 135       // Figure out where to insert the copy, which is at the end of the
 136       // predecessor basic block, but before any terminator/branch
 137       // instructions...
 138       MachineBasicBlock::iterator I = opBlock.end();
 139       if (I != opBlock.begin()) {  // Handle empty blocks
 140         --I;
 141         // must backtrack over ALL the branches in the previous block
 142         while (MII.isTerminatorInstr((*I)->getOpcode()) &&
 143                I != opBlock.begin())
 144           --I;
 145
 146         // move back to the first branch instruction so new instructions
 147         // are inserted right in front of it and not in front of a non-branch
 148         if (!MII.isTerminatorInstr((*I)->getOpcode()))
 149           ++I;
 150       }
 151
 152       // Check to make sure we haven't already emitted the copy for this block.
 153       // This can happen because PHI nodes may have multiple entries for the
 154       // same basic block.  It doesn't matter which entry we use though, because
 155       // all incoming values are guaranteed to be the same for a particular bb.
 156       //
 157       // If we emitted a copy for this basic block already, it will be right
 158       // where we want to insert one now.  Just check for a definition of the
 159       // register we are interested in!
 160       //
 161       bool HaveNotEmitted = true;
 162
 163       if (I != opBlock.begin()) {
 164         MachineInstr *PrevInst = *(I-1);
 165         for (unsigned i = 0, e = PrevInst->getNumOperands(); i != e; ++i) {
 166           MachineOperand &MO = PrevInst->getOperand(i);
 167           if (MO.isVirtualRegister() && MO.getReg() == IncomingReg)
 168             if (MO.opIsDefOnly() || MO.opIsDefAndUse()) {
 169               HaveNotEmitted = false;
 170               break;
 171             }
 172         }
 173       }
 174
 175       if (HaveNotEmitted) { // If the copy has not already been emitted, do it.
 176         assert(opVal.isVirtualRegister() &&
 177                "Machine PHI Operands must all be virtual registers!");
 178         unsigned SrcReg = opVal.getReg();
 179         RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC);
 180
 181         // Now update live variable information if we have it.
 182         if (LV) {
 183           // We want to be able to insert a kill of the register if this PHI
 184           // (aka, the copy we just inserted) is the last use of the source
 185           // value.  Live variable analysis conservatively handles this by
 186           // saying that the value is live until the end of the block the PHI
 187           // entry lives in.  If the value really is dead at the PHI copy, there
 188           // will be no successor blocks which have the value live-in.
 189           //
 190           // Check to see if the copy is the last use, and if so, update the
 191           // live variables information so that it knows the copy source
 192           // instruction kills the incoming value.
 193           //
 194           LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg);
 195
 196           // Loop over all of the successors of the basic block, checking to
 197           // see if the value is either live in the block, or if it is killed
 198           // in the block.
 199           //
 200           bool ValueIsLive = false;
 201           BasicBlock *BB = opBlock.getBasicBlock();
 202           for (succ_iterator SI = succ_begin(BB), E = succ_end(BB);
 203                SI != E; ++SI) {
 204             const std::pair<MachineBasicBlock*, unsigned> &
 205               SuccInfo = LV->getBasicBlockInfo(*SI);
 206
 207             // Is it alive in this successor?
 208             unsigned SuccIdx = SuccInfo.second;
 209             if (SuccIdx < InRegVI.AliveBlocks.size() &&
 210                 InRegVI.AliveBlocks[SuccIdx]) {
 211               ValueIsLive = true;
 212               break;
 213             }
 214
 215             // Is it killed in this successor?
 216             MachineBasicBlock *MBB = SuccInfo.first;
 217             for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 218               if (InRegVI.Kills[i].first == MBB) {
 219                 ValueIsLive = true;
 220                 break;
 221               }
 222           }
 223
 224           // Okay, if we now know that the value is not live out of the block,
 225           // we can add a kill marker to the copy we inserted saying that it
 226           // kills the incoming value!
 227           //
 228           if (!ValueIsLive) {
 229             // One more complication to worry about.  There may actually be
 230             // multiple PHI nodes using this value on this branch.  If we aren't
 231             // careful, the first PHI node will end up killing the value, not
 232             // letting it get the to the copy for the final PHI node in the
 233             // block.  Therefore we have to check to see if there is already a
 234             // kill in this block, and if so, extend the lifetime to our new
 235             // copy.
 236             //
 237             for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
 238               if (InRegVI.Kills[i].first == &opBlock) {
 239                 std::pair<LiveVariables::killed_iterator,
 240                           LiveVariables::killed_iterator> Range
 241                   = LV->killed_range(InRegVI.Kills[i].second);
 242                 LV->removeVirtualRegistersKilled(Range.first, Range.second);
 243                 break;
 244               }
 245
 246             LV->addVirtualRegisterKilled(SrcReg, &opBlock, *(I-1));
 247           }
 248         }
 249       }
 250     }
 251
 252     // really delete the PHI instruction now!
 253     delete MI;
 254   }
 255
 256   return true;
 257 }