lib/CodeGen/StrongPHIElimination.cpp

   1 //===- StrongPhiElimination.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 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #define DEBUG_TYPE "strongphielim"
  14 #include "PHIEliminationUtils.h"
  15 #include "llvm/CodeGen/Passes.h"
  16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  17 #include "llvm/CodeGen/MachineDominators.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstrBuilder.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Target/TargetInstrInfo.h"
  22 #include "llvm/Support/Debug.h"
  23 using namespace llvm;
  24
  25 namespace {
  26   class StrongPHIElimination : public MachineFunctionPass {
  27   public:
  28     static char ID; // Pass identification, replacement for typeid
  29     StrongPHIElimination() : MachineFunctionPass(ID) {
  30       initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
  31     }
  32
  33     virtual void getAnalysisUsage(AnalysisUsage&) const;
  34     bool runOnMachineFunction(MachineFunction&);
  35
  36   private:
  37     void InsertCopiesForPHI(MachineInstr*, MachineBasicBlock*);
  38
  39     MachineRegisterInfo* MRI;
  40     const TargetInstrInfo* TII;
  41     LiveIntervals* LI;
  42
  43     typedef DenseSet<std::pair<MachineBasicBlock*, unsigned> > CopySet;
  44     CopySet InsertedCopies;
  45   };
  46 } // namespace
  47
  48 char StrongPHIElimination::ID = 0;
  49 INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
  50   "Eliminate PHI nodes for register allocation, intelligently", false, false)
  51 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  52 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  53 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  54 INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
  55   "Eliminate PHI nodes for register allocation, intelligently", false, false)
  56
  57 char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
  58
  59 void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
  60   AU.setPreservesCFG();
  61   AU.addRequired<MachineDominatorTree>();
  62   AU.addRequired<SlotIndexes>();
  63   AU.addPreserved<SlotIndexes>();
  64   AU.addRequired<LiveIntervals>();
  65   AU.addPreserved<LiveIntervals>();
  66   MachineFunctionPass::getAnalysisUsage(AU);
  67 }
  68
  69 static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
  70   // FIXME: This only needs to check from the first terminator, as only the
  71   // first terminator can use a virtual register.
  72   for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
  73     assert (RI != MBB->rend());
  74     MachineInstr* MI = &*RI;
  75
  76     for (MachineInstr::mop_iterator OI = MI->operands_begin(),
  77          OE = MI->operands_end(); OI != OE; ++OI) {
  78       MachineOperand& MO = *OI;
  79       if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
  80         return &MO;
  81     }
  82   }
  83   return NULL;
  84 }
  85
  86 bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
  87   MRI = &MF.getRegInfo();
  88   TII = MF.getTarget().getInstrInfo();
  89   LI = &getAnalysis<LiveIntervals>();
  90
  91   // Insert copies for all PHI source and destination registers.
  92   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
  93        I != E; ++I) {
  94     for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
  95          BBI != BBE && BBI->isPHI(); ++BBI) {
  96       InsertCopiesForPHI(BBI, I);
  97     }
  98   }
  99
 100   // Adjust the live intervals of all PHI source registers to handle the case
 101   // where the PHIs in successor blocks were the only later uses of the source
 102   // register.
 103   for (CopySet::iterator I = InsertedCopies.begin(), E = InsertedCopies.end();
 104        I != E; ++I) {
 105     MachineBasicBlock* MBB = I->first;
 106     unsigned SrcReg = I->second;
 107     LiveInterval& SrcLI = LI->getInterval(SrcReg);
 108
 109     bool isLiveOut = false;
 110     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 111          SE = MBB->succ_end(); SI != SE; ++SI) {
 112       if (SrcLI.liveAt(LI->getMBBStartIdx(*SI))) {
 113         isLiveOut = true;
 114         break;
 115       }
 116     }
 117
 118     if (isLiveOut)
 119       continue;
 120
 121     MachineOperand* LastUse = findLastUse(MBB, SrcReg);
 122     assert(LastUse);
 123     SrcLI.removeRange(LI->getInstructionIndex(LastUse->getParent()).getDefIndex(),
 124                       LI->getMBBEndIdx(MBB));
 125     LastUse->setIsKill(true);
 126   }
 127
 128   // Remove all PHI instructions from the function.
 129   bool Changed = false;
 130   for (MachineFunction::iterator I = MF.begin(), E = MF.end();
 131        I != E; ++I) {
 132     MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
 133     while (BBI != BBE && BBI->isPHI()) {
 134       MachineInstr* PHI = BBI;
 135       ++BBI;
 136       LI->RemoveMachineInstrFromMaps(PHI);
 137       PHI->eraseFromParent();
 138       Changed = true;
 139     }
 140   }
 141
 142   LI->renumber();
 143   MF.verify(this);
 144
 145   InsertedCopies.clear();
 146
 147   return Changed;
 148 }
 149
 150 void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
 151                                               MachineBasicBlock* MBB) {
 152   assert(PHI->isPHI());
 153   unsigned DestReg = PHI->getOperand(0).getReg();
 154
 155   const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
 156   unsigned CopyReg = MRI->createVirtualRegister(RC);
 157
 158   MachineInstr* CopyInstr = BuildMI(*MBB,
 159                                     MBB->SkipPHIsAndLabels(MBB->begin()),
 160                                     PHI->getDebugLoc(),
 161                                     TII->get(TargetOpcode::COPY),
 162                                     DestReg).addReg(CopyReg);
 163   LI->InsertMachineInstrInMaps(CopyInstr);
 164   CopyInstr->getOperand(1).setIsKill(true);
 165
 166   // Add the region from the beginning of MBB to the copy instruction to
 167   // CopyReg's live interval, and give the VNInfo the phidef flag.
 168   LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
 169   SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
 170   SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
 171   VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
 172                                         CopyInstr,
 173                                         LI->getVNInfoAllocator());
 174   CopyVNI->setIsPHIDef(true);
 175   CopyLI.addRange(LiveRange(MBBStartIndex,
 176                             DestCopyIndex.getDefIndex(),
 177                             CopyVNI));
 178
 179   // Adjust DestReg's live interval to adjust for its new definition at
 180   // CopyInstr.
 181   LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
 182   SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
 183   DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
 184
 185   VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
 186   assert(DestVNI);
 187   DestVNI->def = DestCopyIndex.getDefIndex();
 188
 189   SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
 190   for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
 191     MachineOperand& SrcMO = PHI->getOperand(i);
 192     unsigned SrcReg = SrcMO.getReg();
 193     unsigned SrcSubReg = SrcMO.getSubReg();
 194
 195     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
 196            "Machine PHI Operands must all be virtual registers!");
 197
 198     // If source is defined by an implicit def, there is no need to insert a
 199     // copy.
 200     // FIXME: For some reason, if LiveIntervals is run prior to PHI elimination
 201     // implcit defs have no defining instruction. Is this expected?
 202     MachineInstr* DefMI = MRI->getVRegDef(SrcReg);
 203     if (!DefMI)
 204       continue;
 205
 206     MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
 207
 208     // A copy may have already been inserted in the predecessor in the case of a
 209     // block with multiple incoming edges.
 210     if (!MBBsInsertedInto.insert(PredBB))
 211       continue;
 212
 213     MachineBasicBlock::iterator
 214       CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
 215     MachineInstr* CopyInstr = BuildMI(*PredBB,
 216                                       CopyInsertPoint,
 217                                       PHI->getDebugLoc(),
 218                                       TII->get(TargetOpcode::COPY),
 219                                       CopyReg).addReg(SrcReg, 0, SrcSubReg);
 220     LI->InsertMachineInstrInMaps(CopyInstr);
 221
 222     // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
 223     // the newly added range.
 224     LI->addLiveRangeToEndOfBlock(CopyReg, CopyInstr);
 225     InsertedCopies.insert(std::make_pair(PredBB, SrcReg));
 226
 227     // If SrcReg is not live beyond the PHI, trim its interval so that it is no
 228     // longer live-in to MBB. Note that SrcReg may appear in other PHIs that are
 229     // processed later, but this is still correct to do at this point because we
 230     // never rely on LiveIntervals being correct while inserting copies.
 231     // FIXME: Should this just count uses at PHIs like the normal PHIElimination
 232     // pass does?
 233     LiveInterval& SrcLI = LI->getInterval(SrcReg);
 234     SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
 235     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
 236     SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
 237     if (SrcLI.liveAt(MBBStartIndex) && SrcLI.expiredAt(NextInstrIndex))
 238       SrcLI.removeRange(MBBStartIndex, PHIIndex, true);
 239   }
 240 }