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 "PHIEliminationUtils.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/MachineLoopInfo.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/Target/TargetInstrInfo.h"
26 #include "llvm/Function.h"
27 #include "llvm/Target/TargetMachine.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
38 class PHIElimination
: public MachineFunctionPass
{
39 MachineRegisterInfo
*MRI
; // Machine register information
42 static char ID
; // Pass identification, replacement for typeid
43 PHIElimination() : MachineFunctionPass(ID
) {
44 initializePHIEliminationPass(*PassRegistry::getPassRegistry());
47 virtual bool runOnMachineFunction(MachineFunction
&Fn
);
48 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const;
51 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
52 /// in predecessor basic blocks.
54 bool EliminatePHINodes(MachineFunction
&MF
, MachineBasicBlock
&MBB
);
55 void LowerAtomicPHINode(MachineBasicBlock
&MBB
,
56 MachineBasicBlock::iterator AfterPHIsIt
);
58 /// analyzePHINodes - Gather information about the PHI nodes in
59 /// here. In particular, we want to map the number of uses of a virtual
60 /// register which is used in a PHI node. We map that to the BB the
61 /// vreg is coming from. This is used later to determine when the vreg
62 /// is killed in the BB.
64 void analyzePHINodes(const MachineFunction
& Fn
);
66 /// Split critical edges where necessary for good coalescer performance.
67 bool SplitPHIEdges(MachineFunction
&MF
, MachineBasicBlock
&MBB
,
68 LiveVariables
&LV
, MachineLoopInfo
*MLI
);
70 typedef std::pair
<unsigned, unsigned> BBVRegPair
;
71 typedef DenseMap
<BBVRegPair
, unsigned> VRegPHIUse
;
73 VRegPHIUse VRegPHIUseCount
;
75 // Defs of PHI sources which are implicit_def.
76 SmallPtrSet
<MachineInstr
*, 4> ImpDefs
;
78 // Map reusable lowered PHI node -> incoming join register.
79 typedef DenseMap
<MachineInstr
*, unsigned,
80 MachineInstrExpressionTrait
> LoweredPHIMap
;
81 LoweredPHIMap LoweredPHIs
;
85 STATISTIC(NumAtomic
, "Number of atomic phis lowered");
86 STATISTIC(NumReused
, "Number of reused lowered phis");
88 char PHIElimination::ID
= 0;
89 INITIALIZE_PASS(PHIElimination
, "phi-node-elimination",
90 "Eliminate PHI nodes for register allocation", false, false)
92 char& llvm::PHIEliminationID
= PHIElimination::ID
;
94 void PHIElimination::getAnalysisUsage(AnalysisUsage
&AU
) const {
95 AU
.addPreserved
<LiveVariables
>();
96 AU
.addPreserved
<MachineDominatorTree
>();
97 AU
.addPreserved
<MachineLoopInfo
>();
98 MachineFunctionPass::getAnalysisUsage(AU
);
101 bool PHIElimination::runOnMachineFunction(MachineFunction
&MF
) {
102 MRI
= &MF
.getRegInfo();
104 bool Changed
= false;
106 // Split critical edges to help the coalescer
107 if (LiveVariables
*LV
= getAnalysisIfAvailable
<LiveVariables
>()) {
108 MachineLoopInfo
*MLI
= getAnalysisIfAvailable
<MachineLoopInfo
>();
109 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end(); I
!= E
; ++I
)
110 Changed
|= SplitPHIEdges(MF
, *I
, *LV
, MLI
);
113 // Populate VRegPHIUseCount
116 // Eliminate PHI instructions by inserting copies into predecessor blocks.
117 for (MachineFunction::iterator I
= MF
.begin(), E
= MF
.end(); I
!= E
; ++I
)
118 Changed
|= EliminatePHINodes(MF
, *I
);
120 // Remove dead IMPLICIT_DEF instructions.
121 for (SmallPtrSet
<MachineInstr
*, 4>::iterator I
= ImpDefs
.begin(),
122 E
= ImpDefs
.end(); I
!= E
; ++I
) {
123 MachineInstr
*DefMI
= *I
;
124 unsigned DefReg
= DefMI
->getOperand(0).getReg();
125 if (MRI
->use_nodbg_empty(DefReg
))
126 DefMI
->eraseFromParent();
129 // Clean up the lowered PHI instructions.
130 for (LoweredPHIMap::iterator I
= LoweredPHIs
.begin(), E
= LoweredPHIs
.end();
132 MF
.DeleteMachineInstr(I
->first
);
136 VRegPHIUseCount
.clear();
141 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
142 /// predecessor basic blocks.
144 bool PHIElimination::EliminatePHINodes(MachineFunction
&MF
,
145 MachineBasicBlock
&MBB
) {
146 if (MBB
.empty() || !MBB
.front().isPHI())
147 return false; // Quick exit for basic blocks without PHIs.
149 // Get an iterator to the first instruction after the last PHI node (this may
150 // also be the end of the basic block).
151 MachineBasicBlock::iterator AfterPHIsIt
= MBB
.SkipPHIsAndLabels(MBB
.begin());
153 while (MBB
.front().isPHI())
154 LowerAtomicPHINode(MBB
, AfterPHIsIt
);
159 /// isSourceDefinedByImplicitDef - Return true if all sources of the phi node
160 /// are implicit_def's.
161 static bool isSourceDefinedByImplicitDef(const MachineInstr
*MPhi
,
162 const MachineRegisterInfo
*MRI
) {
163 for (unsigned i
= 1; i
!= MPhi
->getNumOperands(); i
+= 2) {
164 unsigned SrcReg
= MPhi
->getOperand(i
).getReg();
165 const MachineInstr
*DefMI
= MRI
->getVRegDef(SrcReg
);
166 if (!DefMI
|| !DefMI
->isImplicitDef())
174 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block,
175 /// under the assuption that it needs to be lowered in a way that supports
176 /// atomic execution of PHIs. This lowering method is always correct all of the
179 void PHIElimination::LowerAtomicPHINode(
180 MachineBasicBlock
&MBB
,
181 MachineBasicBlock::iterator AfterPHIsIt
) {
183 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
184 MachineInstr
*MPhi
= MBB
.remove(MBB
.begin());
186 unsigned NumSrcs
= (MPhi
->getNumOperands() - 1) / 2;
187 unsigned DestReg
= MPhi
->getOperand(0).getReg();
188 assert(MPhi
->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
189 bool isDead
= MPhi
->getOperand(0).isDead();
191 // Create a new register for the incoming PHI arguments.
192 MachineFunction
&MF
= *MBB
.getParent();
193 unsigned IncomingReg
= 0;
194 bool reusedIncoming
= false; // Is IncomingReg reused from an earlier PHI?
196 // Insert a register to register copy at the top of the current block (but
197 // after any remaining phi nodes) which copies the new incoming register
198 // into the phi node destination.
199 const TargetInstrInfo
*TII
= MF
.getTarget().getInstrInfo();
200 if (isSourceDefinedByImplicitDef(MPhi
, MRI
))
201 // If all sources of a PHI node are implicit_def, just emit an
202 // implicit_def instead of a copy.
203 BuildMI(MBB
, AfterPHIsIt
, MPhi
->getDebugLoc(),
204 TII
->get(TargetOpcode::IMPLICIT_DEF
), DestReg
);
206 // Can we reuse an earlier PHI node? This only happens for critical edges,
207 // typically those created by tail duplication.
208 unsigned &entry
= LoweredPHIs
[MPhi
];
210 // An identical PHI node was already lowered. Reuse the incoming register.
212 reusedIncoming
= true;
214 DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg
) << " for " << *MPhi
);
216 const TargetRegisterClass
*RC
= MF
.getRegInfo().getRegClass(DestReg
);
217 entry
= IncomingReg
= MF
.getRegInfo().createVirtualRegister(RC
);
219 BuildMI(MBB
, AfterPHIsIt
, MPhi
->getDebugLoc(),
220 TII
->get(TargetOpcode::COPY
), DestReg
)
221 .addReg(IncomingReg
);
224 // Update live variable information if there is any.
225 LiveVariables
*LV
= getAnalysisIfAvailable
<LiveVariables
>();
227 MachineInstr
*PHICopy
= prior(AfterPHIsIt
);
230 LiveVariables::VarInfo
&VI
= LV
->getVarInfo(IncomingReg
);
232 // Increment use count of the newly created virtual register.
234 LV
->setPHIJoin(IncomingReg
);
236 // When we are reusing the incoming register, it may already have been
237 // killed in this block. The old kill will also have been inserted at
238 // AfterPHIsIt, so it appears before the current PHICopy.
240 if (MachineInstr
*OldKill
= VI
.findKill(&MBB
)) {
241 DEBUG(dbgs() << "Remove old kill from " << *OldKill
);
242 LV
->removeVirtualRegisterKilled(IncomingReg
, OldKill
);
246 // Add information to LiveVariables to know that the incoming value is
247 // killed. Note that because the value is defined in several places (once
248 // each for each incoming block), the "def" block and instruction fields
249 // for the VarInfo is not filled in.
250 LV
->addVirtualRegisterKilled(IncomingReg
, PHICopy
);
253 // Since we are going to be deleting the PHI node, if it is the last use of
254 // any registers, or if the value itself is dead, we need to move this
255 // information over to the new copy we just inserted.
256 LV
->removeVirtualRegistersKilled(MPhi
);
258 // If the result is dead, update LV.
260 LV
->addVirtualRegisterDead(DestReg
, PHICopy
);
261 LV
->removeVirtualRegisterDead(DestReg
, MPhi
);
265 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
266 for (unsigned i
= 1; i
!= MPhi
->getNumOperands(); i
+= 2)
267 --VRegPHIUseCount
[BBVRegPair(MPhi
->getOperand(i
+1).getMBB()->getNumber(),
268 MPhi
->getOperand(i
).getReg())];
270 // Now loop over all of the incoming arguments, changing them to copy into the
271 // IncomingReg register in the corresponding predecessor basic block.
272 SmallPtrSet
<MachineBasicBlock
*, 8> MBBsInsertedInto
;
273 for (int i
= NumSrcs
- 1; i
>= 0; --i
) {
274 unsigned SrcReg
= MPhi
->getOperand(i
*2+1).getReg();
275 unsigned SrcSubReg
= MPhi
->getOperand(i
*2+1).getSubReg();
277 assert(TargetRegisterInfo::isVirtualRegister(SrcReg
) &&
278 "Machine PHI Operands must all be virtual registers!");
280 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
282 MachineBasicBlock
&opBlock
= *MPhi
->getOperand(i
*2+2).getMBB();
284 // If source is defined by an implicit def, there is no need to insert a
286 MachineInstr
*DefMI
= MRI
->getVRegDef(SrcReg
);
287 if (DefMI
->isImplicitDef()) {
288 ImpDefs
.insert(DefMI
);
292 // Check to make sure we haven't already emitted the copy for this block.
293 // This can happen because PHI nodes may have multiple entries for the same
295 if (!MBBsInsertedInto
.insert(&opBlock
))
296 continue; // If the copy has already been emitted, we're done.
298 // Find a safe location to insert the copy, this may be the first terminator
299 // in the block (or end()).
300 MachineBasicBlock::iterator InsertPos
=
301 findPHICopyInsertPoint(&opBlock
, &MBB
, SrcReg
);
304 if (!reusedIncoming
&& IncomingReg
)
305 BuildMI(opBlock
, InsertPos
, MPhi
->getDebugLoc(),
306 TII
->get(TargetOpcode::COPY
), IncomingReg
).addReg(SrcReg
, 0, SrcSubReg
);
308 // Now update live variable information if we have it. Otherwise we're done
311 // We want to be able to insert a kill of the register if this PHI (aka, the
312 // copy we just inserted) is the last use of the source value. Live
313 // variable analysis conservatively handles this by saying that the value is
314 // live until the end of the block the PHI entry lives in. If the value
315 // really is dead at the PHI copy, there will be no successor blocks which
316 // have the value live-in.
318 // Also check to see if this register is in use by another PHI node which
319 // has not yet been eliminated. If so, it will be killed at an appropriate
322 // Is it used by any PHI instructions in this block?
323 bool ValueIsUsed
= VRegPHIUseCount
[BBVRegPair(opBlock
.getNumber(), SrcReg
)];
325 // Okay, if we now know that the value is not live out of the block, we can
326 // add a kill marker in this block saying that it kills the incoming value!
327 if (!ValueIsUsed
&& !LV
->isLiveOut(SrcReg
, opBlock
)) {
328 // In our final twist, we have to decide which instruction kills the
329 // register. In most cases this is the copy, however, the first
330 // terminator instruction at the end of the block may also use the value.
331 // In this case, we should mark *it* as being the killing block, not the
333 MachineBasicBlock::iterator KillInst
;
334 MachineBasicBlock::iterator Term
= opBlock
.getFirstTerminator();
335 if (Term
!= opBlock
.end() && Term
->readsRegister(SrcReg
)) {
338 // Check that no other terminators use values.
340 for (MachineBasicBlock::iterator TI
= llvm::next(Term
);
341 TI
!= opBlock
.end(); ++TI
) {
342 if (TI
->isDebugValue())
344 assert(!TI
->readsRegister(SrcReg
) &&
345 "Terminator instructions cannot use virtual registers unless"
346 "they are the first terminator in a block!");
349 } else if (reusedIncoming
|| !IncomingReg
) {
350 // We may have to rewind a bit if we didn't insert a copy this time.
352 while (KillInst
!= opBlock
.begin()) {
354 if (KillInst
->isDebugValue())
356 if (KillInst
->readsRegister(SrcReg
))
360 // We just inserted this copy.
361 KillInst
= prior(InsertPos
);
363 assert(KillInst
->readsRegister(SrcReg
) && "Cannot find kill instruction");
365 // Finally, mark it killed.
366 LV
->addVirtualRegisterKilled(SrcReg
, KillInst
);
368 // This vreg no longer lives all of the way through opBlock.
369 unsigned opBlockNum
= opBlock
.getNumber();
370 LV
->getVarInfo(SrcReg
).AliveBlocks
.reset(opBlockNum
);
374 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
375 if (reusedIncoming
|| !IncomingReg
)
376 MF
.DeleteMachineInstr(MPhi
);
379 /// analyzePHINodes - Gather information about the PHI nodes in here. In
380 /// particular, we want to map the number of uses of a virtual register which is
381 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
382 /// used later to determine when the vreg is killed in the BB.
384 void PHIElimination::analyzePHINodes(const MachineFunction
& MF
) {
385 for (MachineFunction::const_iterator I
= MF
.begin(), E
= MF
.end();
387 for (MachineBasicBlock::const_iterator BBI
= I
->begin(), BBE
= I
->end();
388 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
)
389 for (unsigned i
= 1, e
= BBI
->getNumOperands(); i
!= e
; i
+= 2)
390 ++VRegPHIUseCount
[BBVRegPair(BBI
->getOperand(i
+1).getMBB()->getNumber(),
391 BBI
->getOperand(i
).getReg())];
394 bool PHIElimination::SplitPHIEdges(MachineFunction
&MF
,
395 MachineBasicBlock
&MBB
,
397 MachineLoopInfo
*MLI
) {
398 if (MBB
.empty() || !MBB
.front().isPHI() || MBB
.isLandingPad())
399 return false; // Quick exit for basic blocks without PHIs.
401 bool Changed
= false;
402 for (MachineBasicBlock::const_iterator BBI
= MBB
.begin(), BBE
= MBB
.end();
403 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
404 for (unsigned i
= 1, e
= BBI
->getNumOperands(); i
!= e
; i
+= 2) {
405 unsigned Reg
= BBI
->getOperand(i
).getReg();
406 MachineBasicBlock
*PreMBB
= BBI
->getOperand(i
+1).getMBB();
407 // We break edges when registers are live out from the predecessor block
408 // (not considering PHI nodes). If the register is live in to this block
409 // anyway, we would gain nothing from splitting.
410 // Avoid splitting backedges of loops. It would introduce small
411 // out-of-line blocks into the loop which is very bad for code placement.
412 if (PreMBB
!= &MBB
&&
413 !LV
.isLiveIn(Reg
, MBB
) && LV
.isLiveOut(Reg
, *PreMBB
)) {
415 !(MLI
->getLoopFor(PreMBB
) == MLI
->getLoopFor(&MBB
) &&
416 MLI
->isLoopHeader(&MBB
)))
417 Changed
|= PreMBB
->SplitCriticalEdge(&MBB
, this) != 0;