1 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "phielim"
17 #include "PHIElimination.h"
18 #include "llvm/CodeGen/LiveVariables.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/CodeGen/MachineDominators.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/Target/TargetInstrInfo.h"
25 #include "llvm/Function.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 "llvm/Support/ErrorHandling.h"
38 STATISTIC(NumAtomic, "Number of atomic phis lowered");
39 STATISTIC(NumSplits, "Number of critical edges split on demand");
40 STATISTIC(NumReused, "Number of reused lowered phis");
42 char PHIElimination::ID = 0;
43 static RegisterPass<PHIElimination>
44 X("phi-node-elimination", "Eliminate PHI nodes for register allocation");
46 const PassInfo *const llvm::PHIEliminationID = &X;
48 void llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
49 AU.addPreserved<LiveVariables>();
50 AU.addPreserved<MachineDominatorTree>();
51 // rdar://7401784 This would be nice:
52 // AU.addPreservedID(MachineLoopInfoID);
53 MachineFunctionPass::getAnalysisUsage(AU);
56 bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) {
57 MRI = &MF.getRegInfo();
61 // Split critical edges to help the coalescer
62 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>())
63 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
64 Changed |= SplitPHIEdges(MF, *I, *LV);
66 // Populate VRegPHIUseCount
69 // Eliminate PHI instructions by inserting copies into predecessor blocks.
70 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
71 Changed |= EliminatePHINodes(MF, *I);
73 // Remove dead IMPLICIT_DEF instructions.
74 for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(),
75 E = ImpDefs.end(); I != E; ++I) {
76 MachineInstr *DefMI = *I;
77 unsigned DefReg = DefMI->getOperand(0).getReg();
78 if (MRI->use_nodbg_empty(DefReg))
79 DefMI->eraseFromParent();
82 // Clean up the lowered PHI instructions.
83 for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end();
85 MF.DeleteMachineInstr(I->first);
89 VRegPHIUseCount.clear();
91 // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve
93 Changed |= EliminateRegSequences(MF);
98 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
99 /// predecessor basic blocks.
101 bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF,
102 MachineBasicBlock &MBB) {
103 if (MBB.empty() || !MBB.front().isPHI())
104 return false; // Quick exit for basic blocks without PHIs.
106 // Get an iterator to the first instruction after the last PHI node (this may
107 // also be the end of the basic block).
108 MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin());
110 while (MBB.front().isPHI())
111 LowerAtomicPHINode(MBB, AfterPHIsIt);
116 /// isSourceDefinedByImplicitDef - Return true if all sources of the phi node
117 /// are implicit_def's.
118 static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi,
119 const MachineRegisterInfo *MRI) {
120 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
121 unsigned SrcReg = MPhi->getOperand(i).getReg();
122 const MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
123 if (!DefMI || !DefMI->isImplicitDef())
129 // FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg
130 // when following the CFG edge to SuccMBB. This needs to be after any def of
131 // SrcReg, but before any subsequent point where control flow might jump out of
133 MachineBasicBlock::iterator
134 llvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB,
135 MachineBasicBlock &SuccMBB,
137 // Handle the trivial case trivially.
141 // Usually, we just want to insert the copy before the first terminator
142 // instruction. However, for the edge going to a landing pad, we must insert
143 // the copy before the call/invoke instruction.
144 if (!SuccMBB.isLandingPad())
145 return MBB.getFirstTerminator();
147 // Discover any defs/uses in this basic block.
148 SmallPtrSet<MachineInstr*, 8> DefUsesInMBB;
149 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
150 RE = MRI->reg_end(); RI != RE; ++RI) {
151 MachineInstr *DefUseMI = &*RI;
152 if (DefUseMI->getParent() == &MBB)
153 DefUsesInMBB.insert(DefUseMI);
156 MachineBasicBlock::iterator InsertPoint;
157 if (DefUsesInMBB.empty()) {
158 // No defs. Insert the copy at the start of the basic block.
159 InsertPoint = MBB.begin();
160 } else if (DefUsesInMBB.size() == 1) {
161 // Insert the copy immediately after the def/use.
162 InsertPoint = *DefUsesInMBB.begin();
165 // Insert the copy immediately after the last def/use.
166 InsertPoint = MBB.end();
167 while (!DefUsesInMBB.count(&*--InsertPoint)) {}
171 // Make sure the copy goes after any phi nodes however.
172 return SkipPHIsAndLabels(MBB, InsertPoint);
175 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
176 /// under the assuption that it needs to be lowered in a way that supports
177 /// atomic execution of PHIs. This lowering method is always correct all of the
180 void llvm::PHIElimination::LowerAtomicPHINode(
181 MachineBasicBlock &MBB,
182 MachineBasicBlock::iterator AfterPHIsIt) {
184 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
185 MachineInstr *MPhi = MBB.remove(MBB.begin());
187 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
188 unsigned DestReg = MPhi->getOperand(0).getReg();
189 bool isDead = MPhi->getOperand(0).isDead();
191 // Create a new register for the incoming PHI arguments.
192 MachineFunction &MF = *MBB.getParent();
193 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
194 unsigned IncomingReg = 0;
195 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
197 // Insert a register to register copy at the top of the current block (but
198 // after any remaining phi nodes) which copies the new incoming register
199 // into the phi node destination.
200 const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
201 if (isSourceDefinedByImplicitDef(MPhi, MRI))
202 // If all sources of a PHI node are implicit_def, just emit an
203 // implicit_def instead of a copy.
204 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
205 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
207 // Can we reuse an earlier PHI node? This only happens for critical edges,
208 // typically those created by tail duplication.
209 unsigned &entry = LoweredPHIs[MPhi];
211 // An identical PHI node was already lowered. Reuse the incoming register.
213 reusedIncoming = true;
215 DEBUG(dbgs() << "Reusing %reg" << IncomingReg << " for " << *MPhi);
217 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
219 TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC);
222 // Update live variable information if there is any.
223 LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
225 MachineInstr *PHICopy = prior(AfterPHIsIt);
228 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
230 // Increment use count of the newly created virtual register.
232 LV->setPHIJoin(IncomingReg);
234 // When we are reusing the incoming register, it may already have been
235 // killed in this block. The old kill will also have been inserted at
236 // AfterPHIsIt, so it appears before the current PHICopy.
238 if (MachineInstr *OldKill = VI.findKill(&MBB)) {
239 DEBUG(dbgs() << "Remove old kill from " << *OldKill);
240 LV->removeVirtualRegisterKilled(IncomingReg, OldKill);
244 // Add information to LiveVariables to know that the incoming value is
245 // killed. Note that because the value is defined in several places (once
246 // each for each incoming block), the "def" block and instruction fields
247 // for the VarInfo is not filled in.
248 LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
251 // Since we are going to be deleting the PHI node, if it is the last use of
252 // any registers, or if the value itself is dead, we need to move this
253 // information over to the new copy we just inserted.
254 LV->removeVirtualRegistersKilled(MPhi);
256 // If the result is dead, update LV.
258 LV->addVirtualRegisterDead(DestReg, PHICopy);
259 LV->removeVirtualRegisterDead(DestReg, MPhi);
263 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
264 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
265 --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
266 MPhi->getOperand(i).getReg())];
268 // Now loop over all of the incoming arguments, changing them to copy into the
269 // IncomingReg register in the corresponding predecessor basic block.
270 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
271 for (int i = NumSrcs - 1; i >= 0; --i) {
272 unsigned SrcReg = MPhi->getOperand(i*2+1).getReg();
273 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
274 "Machine PHI Operands must all be virtual registers!");
276 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
278 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
280 // If source is defined by an implicit def, there is no need to insert a
282 MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
283 if (DefMI->isImplicitDef()) {
284 ImpDefs.insert(DefMI);
288 // Check to make sure we haven't already emitted the copy for this block.
289 // This can happen because PHI nodes may have multiple entries for the same
291 if (!MBBsInsertedInto.insert(&opBlock))
292 continue; // If the copy has already been emitted, we're done.
294 // Find a safe location to insert the copy, this may be the first terminator
295 // in the block (or end()).
296 MachineBasicBlock::iterator InsertPos =
297 FindCopyInsertPoint(opBlock, MBB, SrcReg);
300 if (!reusedIncoming && IncomingReg)
301 TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC);
303 // Now update live variable information if we have it. Otherwise we're done
306 // We want to be able to insert a kill of the register if this PHI (aka, the
307 // copy we just inserted) is the last use of the source value. Live
308 // variable analysis conservatively handles this by saying that the value is
309 // live until the end of the block the PHI entry lives in. If the value
310 // really is dead at the PHI copy, there will be no successor blocks which
311 // have the value live-in.
313 // Also check to see if this register is in use by another PHI node which
314 // has not yet been eliminated. If so, it will be killed at an appropriate
317 // Is it used by any PHI instructions in this block?
318 bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)];
320 // Okay, if we now know that the value is not live out of the block, we can
321 // add a kill marker in this block saying that it kills the incoming value!
322 if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) {
323 // In our final twist, we have to decide which instruction kills the
324 // register. In most cases this is the copy, however, the first
325 // terminator instruction at the end of the block may also use the value.
326 // In this case, we should mark *it* as being the killing block, not the
328 MachineBasicBlock::iterator KillInst;
329 MachineBasicBlock::iterator Term = opBlock.getFirstTerminator();
330 if (Term != opBlock.end() && Term->readsRegister(SrcReg)) {
333 // Check that no other terminators use values.
335 for (MachineBasicBlock::iterator TI = llvm::next(Term);
336 TI != opBlock.end(); ++TI) {
337 assert(!TI->readsRegister(SrcReg) &&
338 "Terminator instructions cannot use virtual registers unless"
339 "they are the first terminator in a block!");
342 } else if (reusedIncoming || !IncomingReg) {
343 // We may have to rewind a bit if we didn't insert a copy this time.
345 while (KillInst != opBlock.begin())
346 if ((--KillInst)->readsRegister(SrcReg))
349 // We just inserted this copy.
350 KillInst = prior(InsertPos);
352 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
354 // Finally, mark it killed.
355 LV->addVirtualRegisterKilled(SrcReg, KillInst);
357 // This vreg no longer lives all of the way through opBlock.
358 unsigned opBlockNum = opBlock.getNumber();
359 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
363 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
364 if (reusedIncoming || !IncomingReg)
365 MF.DeleteMachineInstr(MPhi);
368 /// analyzePHINodes - Gather information about the PHI nodes in here. In
369 /// particular, we want to map the number of uses of a virtual register which is
370 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
371 /// used later to determine when the vreg is killed in the BB.
373 void llvm::PHIElimination::analyzePHINodes(const MachineFunction& MF) {
374 for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
376 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end();
377 BBI != BBE && BBI->isPHI(); ++BBI)
378 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)
379 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(),
380 BBI->getOperand(i).getReg())];
383 bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
384 MachineBasicBlock &MBB,
386 if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad())
387 return false; // Quick exit for basic blocks without PHIs.
389 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
390 BBI != BBE && BBI->isPHI(); ++BBI) {
391 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
392 unsigned Reg = BBI->getOperand(i).getReg();
393 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
394 // We break edges when registers are live out from the predecessor block
395 // (not considering PHI nodes). If the register is live in to this block
396 // anyway, we would gain nothing from splitting.
397 if (!LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB))
398 SplitCriticalEdge(PreMBB, &MBB);
404 MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
405 MachineBasicBlock *B) {
406 assert(A && B && "Missing MBB end point");
408 MachineFunction *MF = A->getParent();
410 // We may need to update A's terminator, but we can't do that if AnalyzeBranch
411 // fails. If A uses a jump table, we won't touch it.
412 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
413 MachineBasicBlock *TBB = 0, *FBB = 0;
414 SmallVector<MachineOperand, 4> Cond;
415 if (TII->AnalyzeBranch(*A, TBB, FBB, Cond))
420 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
421 MF->insert(llvm::next(MachineFunction::iterator(A)), NMBB);
422 DEBUG(dbgs() << "PHIElimination splitting critical edge:"
423 " BB#" << A->getNumber()
424 << " -- BB#" << NMBB->getNumber()
425 << " -- BB#" << B->getNumber() << '\n');
427 A->ReplaceUsesOfBlockWith(B, NMBB);
428 A->updateTerminator();
430 // Insert unconditional "jump B" instruction in NMBB if necessary.
431 NMBB->addSuccessor(B);
432 if (!NMBB->isLayoutSuccessor(B)) {
434 MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond);
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->isPHI(); ++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);
444 if (LiveVariables *LV=getAnalysisIfAvailable<LiveVariables>())
445 LV->addNewBlock(NMBB, A, B);
447 if (MachineDominatorTree *MDT=getAnalysisIfAvailable<MachineDominatorTree>())
448 MDT->addNewBlock(NMBB, A);
453 static void UpdateRegSequenceSrcs(unsigned SrcReg,
454 unsigned DstReg, unsigned SrcIdx,
455 MachineRegisterInfo *MRI) {
456 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
457 UE = MRI->reg_end(); RI != UE; ) {
458 MachineOperand &MO = RI.getOperand();
461 MO.setSubReg(SrcIdx);
465 /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as second part
466 /// of de-ssa process. This replaces sources of REG_SEQUENCE as sub-register
467 /// references of the register defined by REG_SEQUENCE. e.g.
469 /// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ...
470 /// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6
472 /// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
473 bool PHIElimination::EliminateRegSequences(MachineFunction &MF) {
474 bool Changed = false;
476 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
477 for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
479 MachineInstr &MI = *BBI;
481 if (MI.getOpcode() != TargetOpcode::REG_SEQUENCE)
483 unsigned DstReg = MI.getOperand(0).getReg();
484 if (MI.getOperand(0).getSubReg() ||
485 TargetRegisterInfo::isPhysicalRegister(DstReg) ||
486 !(MI.getNumOperands() & 1)) {
487 DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
490 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
491 unsigned SrcReg = MI.getOperand(i).getReg();
492 if (MI.getOperand(i).getSubReg() ||
493 TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
494 DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
497 unsigned SrcIdx = MI.getOperand(i+1).getImm();
498 UpdateRegSequenceSrcs(SrcReg, DstReg, SrcIdx, MRI);
501 MI.eraseFromParent();