+
+ // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
+ if (reusedIncoming || !IncomingReg)
+ MF.DeleteMachineInstr(MPhi);
+}
+
+/// analyzePHINodes - Gather information about the PHI nodes in here. In
+/// particular, we want to map the number of uses of a virtual register which is
+/// used in a PHI node. We map that to the BB the vreg is coming from. This is
+/// used later to determine when the vreg is killed in the BB.
+///
+void llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) {
+ for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end();
+ I != E; ++I)
+ for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
+ BBI != BBE && BBI->isPHI(); ++BBI)
+ for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
+ ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
+ BBI->getOperand(i).getReg())];
+}
+
+bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
+ MachineBasicBlock &MBB,
+ LiveVariables &LV) {
+ if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
+ return false; // Quick exit for basic blocks without PHIs.
+
+ for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
+ BBI != BBE && BBI->isPHI(); ++BBI) {
+ for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
+ unsigned Reg = BBI->getOperand(i).getReg();
+ MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
+ // We break edges when registers are live out from the predecessor block
+ // (not considering PHI nodes). If the register is live in to this block
+ // anyway, we would gain nothing from splitting.
+ if (!LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB))
+ SplitCriticalEdge(PreMBB, &MBB);
+ }
+ }
+ return true;
+}
+
+MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
+ MachineBasicBlock *B) {
+ assert(A && B && "Missing MBB end point");
+
+ MachineFunction *MF = A->getParent();
+
+ // We may need to update A's terminator, but we can't do that if AnalyzeBranch
+ // fails. If A uses a jump table, we won't touch it.
+ const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
+ MachineBasicBlock *TBB = 0, *FBB = 0;
+ SmallVector<MachineOperand, 4> Cond;
+ if (TII->AnalyzeBranch(*A, TBB, FBB, Cond))
+ return NULL;
+
+ ++NumSplits;
+
+ MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
+ MF->insert(llvm::next(MachineFunction::iterator(A)), NMBB);
+ DEBUG(dbgs() << "PHIElimination splitting critical edge:"
+ " BB#" << A->getNumber()
+ << " -- BB#" << NMBB->getNumber()
+ << " -- BB#" << B->getNumber() << '\n');
+
+ A->ReplaceUsesOfBlockWith(B, NMBB);
+ A->updateTerminator();
+
+ // Insert unconditional "jump B" instruction in NMBB if necessary.
+ NMBB->addSuccessor(B);
+ if (!NMBB->isLayoutSuccessor(B)) {
+ Cond.clear();
+ MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond);
+ }
+
+ // Fix PHI nodes in B so they refer to NMBB instead of A
+ for (MachineBasicBlock::iterator i = B->begin(), e = B->end();
+ i != e && i->isPHI(); ++i)
+ for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
+ if (i->getOperand(ni+1).getMBB() == A)
+ i->getOperand(ni+1).setMBB(NMBB);
+
+ if (LiveVariables *LV=getAnalysisIfAvailable<LiveVariables>())
+ LV->addNewBlock(NMBB, A, B);
+
+ if (MachineDominatorTree *MDT=getAnalysisIfAvailable<MachineDominatorTree>())
+ MDT->addNewBlock(NMBB, A);
+
+ return NMBB;