1 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass eliminates machine instruction PHI nodes by inserting copy
10 // instructions. This destroys SSA information, but is the desired input for
11 // some register allocators.
13 //===----------------------------------------------------------------------===//
15 #include "PHIEliminationUtils.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/CodeGen/LiveInterval.h"
21 #include "llvm/CodeGen/LiveIntervals.h"
22 #include "llvm/CodeGen/LiveVariables.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineDominators.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineOperand.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/SlotIndexes.h"
33 #include "llvm/CodeGen/TargetInstrInfo.h"
34 #include "llvm/CodeGen/TargetLowering.h"
35 #include "llvm/CodeGen/TargetOpcodes.h"
36 #include "llvm/CodeGen/TargetPassConfig.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
49 #define DEBUG_TYPE "phi-node-elimination"
52 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
53 cl::Hidden
, cl::desc("Disable critical edge splitting "
54 "during PHI elimination"));
57 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
58 cl::Hidden
, cl::desc("Split all critical edges during "
61 static cl::opt
<bool> NoPhiElimLiveOutEarlyExit(
62 "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden
,
63 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
67 class PHIElimination
: public MachineFunctionPass
{
68 MachineRegisterInfo
*MRI
; // Machine register information
73 static char ID
; // Pass identification, replacement for typeid
75 PHIElimination() : MachineFunctionPass(ID
) {
76 initializePHIEliminationPass(*PassRegistry::getPassRegistry());
79 bool runOnMachineFunction(MachineFunction
&MF
) override
;
80 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
83 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
84 /// in predecessor basic blocks.
85 bool EliminatePHINodes(MachineFunction
&MF
, MachineBasicBlock
&MBB
);
87 void LowerPHINode(MachineBasicBlock
&MBB
,
88 MachineBasicBlock::iterator LastPHIIt
);
90 /// analyzePHINodes - Gather information about the PHI nodes in
91 /// here. In particular, we want to map the number of uses of a virtual
92 /// register which is used in a PHI node. We map that to the BB the
93 /// vreg is coming from. This is used later to determine when the vreg
94 /// is killed in the BB.
95 void analyzePHINodes(const MachineFunction
& MF
);
97 /// Split critical edges where necessary for good coalescer performance.
98 bool SplitPHIEdges(MachineFunction
&MF
, MachineBasicBlock
&MBB
,
99 MachineLoopInfo
*MLI
);
101 // These functions are temporary abstractions around LiveVariables and
102 // LiveIntervals, so they can go away when LiveVariables does.
103 bool isLiveIn(unsigned Reg
, const MachineBasicBlock
*MBB
);
104 bool isLiveOutPastPHIs(unsigned Reg
, const MachineBasicBlock
*MBB
);
106 using BBVRegPair
= std::pair
<unsigned, unsigned>;
107 using VRegPHIUse
= DenseMap
<BBVRegPair
, unsigned>;
109 VRegPHIUse VRegPHIUseCount
;
111 // Defs of PHI sources which are implicit_def.
112 SmallPtrSet
<MachineInstr
*, 4> ImpDefs
;
114 // Map reusable lowered PHI node -> incoming join register.
115 using LoweredPHIMap
=
116 DenseMap
<MachineInstr
*, unsigned, MachineInstrExpressionTrait
>;
117 LoweredPHIMap LoweredPHIs
;
120 } // end anonymous namespace
122 STATISTIC(NumLowered
, "Number of phis lowered");
123 STATISTIC(NumCriticalEdgesSplit
, "Number of critical edges split");
124 STATISTIC(NumReused
, "Number of reused lowered phis");
126 char PHIElimination::ID
= 0;
128 char& llvm::PHIEliminationID
= PHIElimination::ID
;
130 INITIALIZE_PASS_BEGIN(PHIElimination
, DEBUG_TYPE
,
131 "Eliminate PHI nodes for register allocation",
133 INITIALIZE_PASS_DEPENDENCY(LiveVariables
)
134 INITIALIZE_PASS_END(PHIElimination
, DEBUG_TYPE
,
135 "Eliminate PHI nodes for register allocation", false, false)
137 void PHIElimination::getAnalysisUsage(AnalysisUsage
&AU
) const {
138 AU
.addUsedIfAvailable
<LiveVariables
>();
139 AU
.addPreserved
<LiveVariables
>();
140 AU
.addPreserved
<SlotIndexes
>();
141 AU
.addPreserved
<LiveIntervals
>();
142 AU
.addPreserved
<MachineDominatorTree
>();
143 AU
.addPreserved
<MachineLoopInfo
>();
144 MachineFunctionPass::getAnalysisUsage(AU
);
147 bool PHIElimination::runOnMachineFunction(MachineFunction
&MF
) {
148 MRI
= &MF
.getRegInfo();
149 LV
= getAnalysisIfAvailable
<LiveVariables
>();
150 LIS
= getAnalysisIfAvailable
<LiveIntervals
>();
152 bool Changed
= false;
154 // This pass takes the function out of SSA form.
157 // Split critical edges to help the coalescer.
158 if (!DisableEdgeSplitting
&& (LV
|| LIS
)) {
159 MachineLoopInfo
*MLI
= getAnalysisIfAvailable
<MachineLoopInfo
>();
161 Changed
|= SplitPHIEdges(MF
, MBB
, MLI
);
164 // Populate VRegPHIUseCount
167 // Eliminate PHI instructions by inserting copies into predecessor blocks.
169 Changed
|= EliminatePHINodes(MF
, MBB
);
171 // Remove dead IMPLICIT_DEF instructions.
172 for (MachineInstr
*DefMI
: ImpDefs
) {
173 Register DefReg
= DefMI
->getOperand(0).getReg();
174 if (MRI
->use_nodbg_empty(DefReg
)) {
176 LIS
->RemoveMachineInstrFromMaps(*DefMI
);
177 DefMI
->eraseFromParent();
181 // Clean up the lowered PHI instructions.
182 for (auto &I
: LoweredPHIs
) {
184 LIS
->RemoveMachineInstrFromMaps(*I
.first
);
185 MF
.DeleteMachineInstr(I
.first
);
190 VRegPHIUseCount
.clear();
192 MF
.getProperties().set(MachineFunctionProperties::Property::NoPHIs
);
197 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
198 /// predecessor basic blocks.
199 bool PHIElimination::EliminatePHINodes(MachineFunction
&MF
,
200 MachineBasicBlock
&MBB
) {
201 if (MBB
.empty() || !MBB
.front().isPHI())
202 return false; // Quick exit for basic blocks without PHIs.
204 // Get an iterator to the last PHI node.
205 MachineBasicBlock::iterator LastPHIIt
=
206 std::prev(MBB
.SkipPHIsAndLabels(MBB
.begin()));
208 while (MBB
.front().isPHI())
209 LowerPHINode(MBB
, LastPHIIt
);
214 /// Return true if all defs of VirtReg are implicit-defs.
215 /// This includes registers with no defs.
216 static bool isImplicitlyDefined(unsigned VirtReg
,
217 const MachineRegisterInfo
&MRI
) {
218 for (MachineInstr
&DI
: MRI
.def_instructions(VirtReg
))
219 if (!DI
.isImplicitDef())
224 /// Return true if all sources of the phi node are implicit_def's, or undef's.
225 static bool allPhiOperandsUndefined(const MachineInstr
&MPhi
,
226 const MachineRegisterInfo
&MRI
) {
227 for (unsigned I
= 1, E
= MPhi
.getNumOperands(); I
!= E
; I
+= 2) {
228 const MachineOperand
&MO
= MPhi
.getOperand(I
);
229 if (!isImplicitlyDefined(MO
.getReg(), MRI
) && !MO
.isUndef())
234 /// LowerPHINode - Lower the PHI node at the top of the specified block.
235 void PHIElimination::LowerPHINode(MachineBasicBlock
&MBB
,
236 MachineBasicBlock::iterator LastPHIIt
) {
239 MachineBasicBlock::iterator AfterPHIsIt
= std::next(LastPHIIt
);
241 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
242 MachineInstr
*MPhi
= MBB
.remove(&*MBB
.begin());
244 unsigned NumSrcs
= (MPhi
->getNumOperands() - 1) / 2;
245 Register DestReg
= MPhi
->getOperand(0).getReg();
246 assert(MPhi
->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
247 bool isDead
= MPhi
->getOperand(0).isDead();
249 // Create a new register for the incoming PHI arguments.
250 MachineFunction
&MF
= *MBB
.getParent();
251 unsigned IncomingReg
= 0;
252 bool reusedIncoming
= false; // Is IncomingReg reused from an earlier PHI?
254 // Insert a register to register copy at the top of the current block (but
255 // after any remaining phi nodes) which copies the new incoming register
256 // into the phi node destination.
257 MachineInstr
*PHICopy
= nullptr;
258 const TargetInstrInfo
*TII
= MF
.getSubtarget().getInstrInfo();
259 if (allPhiOperandsUndefined(*MPhi
, *MRI
))
260 // If all sources of a PHI node are implicit_def or undef uses, just emit an
261 // implicit_def instead of a copy.
262 PHICopy
= BuildMI(MBB
, AfterPHIsIt
, MPhi
->getDebugLoc(),
263 TII
->get(TargetOpcode::IMPLICIT_DEF
), DestReg
);
265 // Can we reuse an earlier PHI node? This only happens for critical edges,
266 // typically those created by tail duplication.
267 unsigned &entry
= LoweredPHIs
[MPhi
];
269 // An identical PHI node was already lowered. Reuse the incoming register.
271 reusedIncoming
= true;
273 LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg
) << " for "
276 const TargetRegisterClass
*RC
= MF
.getRegInfo().getRegClass(DestReg
);
277 entry
= IncomingReg
= MF
.getRegInfo().createVirtualRegister(RC
);
279 // Give the target possiblity to handle special cases fallthrough otherwise
280 PHICopy
= TII
->createPHIDestinationCopy(MBB
, AfterPHIsIt
, MPhi
->getDebugLoc(),
281 IncomingReg
, DestReg
);
284 // Update live variable information if there is any.
287 LiveVariables::VarInfo
&VI
= LV
->getVarInfo(IncomingReg
);
289 // Increment use count of the newly created virtual register.
290 LV
->setPHIJoin(IncomingReg
);
292 // When we are reusing the incoming register, it may already have been
293 // killed in this block. The old kill will also have been inserted at
294 // AfterPHIsIt, so it appears before the current PHICopy.
296 if (MachineInstr
*OldKill
= VI
.findKill(&MBB
)) {
297 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill
);
298 LV
->removeVirtualRegisterKilled(IncomingReg
, *OldKill
);
299 LLVM_DEBUG(MBB
.dump());
302 // Add information to LiveVariables to know that the incoming value is
303 // killed. Note that because the value is defined in several places (once
304 // each for each incoming block), the "def" block and instruction fields
305 // for the VarInfo is not filled in.
306 LV
->addVirtualRegisterKilled(IncomingReg
, *PHICopy
);
309 // Since we are going to be deleting the PHI node, if it is the last use of
310 // any registers, or if the value itself is dead, we need to move this
311 // information over to the new copy we just inserted.
312 LV
->removeVirtualRegistersKilled(*MPhi
);
314 // If the result is dead, update LV.
316 LV
->addVirtualRegisterDead(DestReg
, *PHICopy
);
317 LV
->removeVirtualRegisterDead(DestReg
, *MPhi
);
321 // Update LiveIntervals for the new copy or implicit def.
323 SlotIndex DestCopyIndex
= LIS
->InsertMachineInstrInMaps(*PHICopy
);
325 SlotIndex MBBStartIndex
= LIS
->getMBBStartIdx(&MBB
);
327 // Add the region from the beginning of MBB to the copy instruction to
328 // IncomingReg's live interval.
329 LiveInterval
&IncomingLI
= LIS
->createEmptyInterval(IncomingReg
);
330 VNInfo
*IncomingVNI
= IncomingLI
.getVNInfoAt(MBBStartIndex
);
332 IncomingVNI
= IncomingLI
.getNextValue(MBBStartIndex
,
333 LIS
->getVNInfoAllocator());
334 IncomingLI
.addSegment(LiveInterval::Segment(MBBStartIndex
,
335 DestCopyIndex
.getRegSlot(),
339 LiveInterval
&DestLI
= LIS
->getInterval(DestReg
);
340 assert(DestLI
.begin() != DestLI
.end() &&
341 "PHIs should have nonempty LiveIntervals.");
342 if (DestLI
.endIndex().isDead()) {
343 // A dead PHI's live range begins and ends at the start of the MBB, but
344 // the lowered copy, which will still be dead, needs to begin and end at
345 // the copy instruction.
346 VNInfo
*OrigDestVNI
= DestLI
.getVNInfoAt(MBBStartIndex
);
347 assert(OrigDestVNI
&& "PHI destination should be live at block entry.");
348 DestLI
.removeSegment(MBBStartIndex
, MBBStartIndex
.getDeadSlot());
349 DestLI
.createDeadDef(DestCopyIndex
.getRegSlot(),
350 LIS
->getVNInfoAllocator());
351 DestLI
.removeValNo(OrigDestVNI
);
353 // Otherwise, remove the region from the beginning of MBB to the copy
354 // instruction from DestReg's live interval.
355 DestLI
.removeSegment(MBBStartIndex
, DestCopyIndex
.getRegSlot());
356 VNInfo
*DestVNI
= DestLI
.getVNInfoAt(DestCopyIndex
.getRegSlot());
357 assert(DestVNI
&& "PHI destination should be live at its definition.");
358 DestVNI
->def
= DestCopyIndex
.getRegSlot();
362 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
363 for (unsigned i
= 1; i
!= MPhi
->getNumOperands(); i
+= 2)
364 --VRegPHIUseCount
[BBVRegPair(MPhi
->getOperand(i
+1).getMBB()->getNumber(),
365 MPhi
->getOperand(i
).getReg())];
367 // Now loop over all of the incoming arguments, changing them to copy into the
368 // IncomingReg register in the corresponding predecessor basic block.
369 SmallPtrSet
<MachineBasicBlock
*, 8> MBBsInsertedInto
;
370 for (int i
= NumSrcs
- 1; i
>= 0; --i
) {
371 Register SrcReg
= MPhi
->getOperand(i
* 2 + 1).getReg();
372 unsigned SrcSubReg
= MPhi
->getOperand(i
*2+1).getSubReg();
373 bool SrcUndef
= MPhi
->getOperand(i
*2+1).isUndef() ||
374 isImplicitlyDefined(SrcReg
, *MRI
);
375 assert(Register::isVirtualRegister(SrcReg
) &&
376 "Machine PHI Operands must all be virtual registers!");
378 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
380 MachineBasicBlock
&opBlock
= *MPhi
->getOperand(i
*2+2).getMBB();
382 // Check to make sure we haven't already emitted the copy for this block.
383 // This can happen because PHI nodes may have multiple entries for the same
385 if (!MBBsInsertedInto
.insert(&opBlock
).second
)
386 continue; // If the copy has already been emitted, we're done.
388 // Find a safe location to insert the copy, this may be the first terminator
389 // in the block (or end()).
390 MachineBasicBlock::iterator InsertPos
=
391 findPHICopyInsertPoint(&opBlock
, &MBB
, SrcReg
);
394 MachineInstr
*NewSrcInstr
= nullptr;
395 if (!reusedIncoming
&& IncomingReg
) {
397 // The source register is undefined, so there is no need for a real
398 // COPY, but we still need to ensure joint dominance by defs.
399 // Insert an IMPLICIT_DEF instruction.
400 NewSrcInstr
= BuildMI(opBlock
, InsertPos
, MPhi
->getDebugLoc(),
401 TII
->get(TargetOpcode::IMPLICIT_DEF
),
404 // Clean up the old implicit-def, if there even was one.
405 if (MachineInstr
*DefMI
= MRI
->getVRegDef(SrcReg
))
406 if (DefMI
->isImplicitDef())
407 ImpDefs
.insert(DefMI
);
410 TII
->createPHISourceCopy(opBlock
, InsertPos
, MPhi
->getDebugLoc(),
411 SrcReg
, SrcSubReg
, IncomingReg
);
415 // We only need to update the LiveVariables kill of SrcReg if this was the
416 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
417 // out of the predecessor. We can also ignore undef sources.
418 if (LV
&& !SrcUndef
&&
419 !VRegPHIUseCount
[BBVRegPair(opBlock
.getNumber(), SrcReg
)] &&
420 !LV
->isLiveOut(SrcReg
, opBlock
)) {
421 // We want to be able to insert a kill of the register if this PHI (aka,
422 // the copy we just inserted) is the last use of the source value. Live
423 // variable analysis conservatively handles this by saying that the value
424 // is live until the end of the block the PHI entry lives in. If the value
425 // really is dead at the PHI copy, there will be no successor blocks which
426 // have the value live-in.
428 // Okay, if we now know that the value is not live out of the block, we
429 // can add a kill marker in this block saying that it kills the incoming
432 // In our final twist, we have to decide which instruction kills the
433 // register. In most cases this is the copy, however, terminator
434 // instructions at the end of the block may also use the value. In this
435 // case, we should mark the last such terminator as being the killing
436 // block, not the copy.
437 MachineBasicBlock::iterator KillInst
= opBlock
.end();
438 MachineBasicBlock::iterator FirstTerm
= opBlock
.getFirstTerminator();
439 for (MachineBasicBlock::iterator Term
= FirstTerm
;
440 Term
!= opBlock
.end(); ++Term
) {
441 if (Term
->readsRegister(SrcReg
))
445 if (KillInst
== opBlock
.end()) {
446 // No terminator uses the register.
448 if (reusedIncoming
|| !IncomingReg
) {
449 // We may have to rewind a bit if we didn't insert a copy this time.
450 KillInst
= FirstTerm
;
451 while (KillInst
!= opBlock
.begin()) {
453 if (KillInst
->isDebugInstr())
455 if (KillInst
->readsRegister(SrcReg
))
459 // We just inserted this copy.
460 KillInst
= NewSrcInstr
;
463 assert(KillInst
->readsRegister(SrcReg
) && "Cannot find kill instruction");
465 // Finally, mark it killed.
466 LV
->addVirtualRegisterKilled(SrcReg
, *KillInst
);
468 // This vreg no longer lives all of the way through opBlock.
469 unsigned opBlockNum
= opBlock
.getNumber();
470 LV
->getVarInfo(SrcReg
).AliveBlocks
.reset(opBlockNum
);
475 LIS
->InsertMachineInstrInMaps(*NewSrcInstr
);
476 LIS
->addSegmentToEndOfBlock(IncomingReg
, *NewSrcInstr
);
480 !VRegPHIUseCount
[BBVRegPair(opBlock
.getNumber(), SrcReg
)]) {
481 LiveInterval
&SrcLI
= LIS
->getInterval(SrcReg
);
483 bool isLiveOut
= false;
484 for (MachineBasicBlock::succ_iterator SI
= opBlock
.succ_begin(),
485 SE
= opBlock
.succ_end(); SI
!= SE
; ++SI
) {
486 SlotIndex startIdx
= LIS
->getMBBStartIdx(*SI
);
487 VNInfo
*VNI
= SrcLI
.getVNInfoAt(startIdx
);
489 // Definitions by other PHIs are not truly live-in for our purposes.
490 if (VNI
&& VNI
->def
!= startIdx
) {
497 MachineBasicBlock::iterator KillInst
= opBlock
.end();
498 MachineBasicBlock::iterator FirstTerm
= opBlock
.getFirstTerminator();
499 for (MachineBasicBlock::iterator Term
= FirstTerm
;
500 Term
!= opBlock
.end(); ++Term
) {
501 if (Term
->readsRegister(SrcReg
))
505 if (KillInst
== opBlock
.end()) {
506 // No terminator uses the register.
508 if (reusedIncoming
|| !IncomingReg
) {
509 // We may have to rewind a bit if we didn't just insert a copy.
510 KillInst
= FirstTerm
;
511 while (KillInst
!= opBlock
.begin()) {
513 if (KillInst
->isDebugInstr())
515 if (KillInst
->readsRegister(SrcReg
))
519 // We just inserted this copy.
520 KillInst
= std::prev(InsertPos
);
523 assert(KillInst
->readsRegister(SrcReg
) &&
524 "Cannot find kill instruction");
526 SlotIndex LastUseIndex
= LIS
->getInstructionIndex(*KillInst
);
527 SrcLI
.removeSegment(LastUseIndex
.getRegSlot(),
528 LIS
->getMBBEndIdx(&opBlock
));
534 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
535 if (reusedIncoming
|| !IncomingReg
) {
537 LIS
->RemoveMachineInstrFromMaps(*MPhi
);
538 MF
.DeleteMachineInstr(MPhi
);
542 /// analyzePHINodes - Gather information about the PHI nodes in here. In
543 /// particular, we want to map the number of uses of a virtual register which is
544 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
545 /// used later to determine when the vreg is killed in the BB.
546 void PHIElimination::analyzePHINodes(const MachineFunction
& MF
) {
547 for (const auto &MBB
: MF
)
548 for (const auto &BBI
: MBB
) {
551 for (unsigned i
= 1, e
= BBI
.getNumOperands(); i
!= e
; i
+= 2)
552 ++VRegPHIUseCount
[BBVRegPair(BBI
.getOperand(i
+1).getMBB()->getNumber(),
553 BBI
.getOperand(i
).getReg())];
557 bool PHIElimination::SplitPHIEdges(MachineFunction
&MF
,
558 MachineBasicBlock
&MBB
,
559 MachineLoopInfo
*MLI
) {
560 if (MBB
.empty() || !MBB
.front().isPHI() || MBB
.isEHPad())
561 return false; // Quick exit for basic blocks without PHIs.
563 const MachineLoop
*CurLoop
= MLI
? MLI
->getLoopFor(&MBB
) : nullptr;
564 bool IsLoopHeader
= CurLoop
&& &MBB
== CurLoop
->getHeader();
566 bool Changed
= false;
567 for (MachineBasicBlock::iterator BBI
= MBB
.begin(), BBE
= MBB
.end();
568 BBI
!= BBE
&& BBI
->isPHI(); ++BBI
) {
569 for (unsigned i
= 1, e
= BBI
->getNumOperands(); i
!= e
; i
+= 2) {
570 Register Reg
= BBI
->getOperand(i
).getReg();
571 MachineBasicBlock
*PreMBB
= BBI
->getOperand(i
+1).getMBB();
572 // Is there a critical edge from PreMBB to MBB?
573 if (PreMBB
->succ_size() == 1)
576 // Avoid splitting backedges of loops. It would introduce small
577 // out-of-line blocks into the loop which is very bad for code placement.
578 if (PreMBB
== &MBB
&& !SplitAllCriticalEdges
)
580 const MachineLoop
*PreLoop
= MLI
? MLI
->getLoopFor(PreMBB
) : nullptr;
581 if (IsLoopHeader
&& PreLoop
== CurLoop
&& !SplitAllCriticalEdges
)
584 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
585 // when the source register is live-out for some other reason than a phi
586 // use. That means the copy we will insert in PreMBB won't be a kill, and
587 // there is a risk it may not be coalesced away.
589 // If the copy would be a kill, there is no need to split the edge.
590 bool ShouldSplit
= isLiveOutPastPHIs(Reg
, PreMBB
);
591 if (!ShouldSplit
&& !NoPhiElimLiveOutEarlyExit
)
594 LLVM_DEBUG(dbgs() << printReg(Reg
) << " live-out before critical edge "
595 << printMBBReference(*PreMBB
) << " -> "
596 << printMBBReference(MBB
) << ": " << *BBI
);
599 // If Reg is not live-in to MBB, it means it must be live-in to some
600 // other PreMBB successor, and we can avoid the interference by splitting
603 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
604 // is likely to be left after coalescing. If we are looking at a loop
605 // exiting edge, split it so we won't insert code in the loop, otherwise
607 ShouldSplit
= ShouldSplit
&& !isLiveIn(Reg
, &MBB
);
609 // Check for a loop exiting edge.
610 if (!ShouldSplit
&& CurLoop
!= PreLoop
) {
612 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
614 dbgs() << "PreLoop: " << *PreLoop
;
616 dbgs() << "CurLoop: " << *CurLoop
;
618 // This edge could be entering a loop, exiting a loop, or it could be
619 // both: Jumping directly form one loop to the header of a sibling
621 // Split unless this edge is entering CurLoop from an outer loop.
622 ShouldSplit
= PreLoop
&& !PreLoop
->contains(CurLoop
);
624 if (!ShouldSplit
&& !SplitAllCriticalEdges
)
626 if (!PreMBB
->SplitCriticalEdge(&MBB
, *this)) {
627 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
631 ++NumCriticalEdgesSplit
;
637 bool PHIElimination::isLiveIn(unsigned Reg
, const MachineBasicBlock
*MBB
) {
638 assert((LV
|| LIS
) &&
639 "isLiveIn() requires either LiveVariables or LiveIntervals");
641 return LIS
->isLiveInToMBB(LIS
->getInterval(Reg
), MBB
);
643 return LV
->isLiveIn(Reg
, *MBB
);
646 bool PHIElimination::isLiveOutPastPHIs(unsigned Reg
,
647 const MachineBasicBlock
*MBB
) {
648 assert((LV
|| LIS
) &&
649 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
650 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
651 // so that a register used only in a PHI is not live out of the block. In
652 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
653 // in the predecessor basic block, so that a register used only in a PHI is live
656 const LiveInterval
&LI
= LIS
->getInterval(Reg
);
657 for (const MachineBasicBlock
*SI
: MBB
->successors())
658 if (LI
.liveAt(LIS
->getMBBStartIdx(SI
)))
662 return LV
->isLiveOut(Reg
, *MBB
);