1//===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
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.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/CodeGen/PHIElimination.h"
16#include "PHIEliminationUtils.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/LoopInfo.h"
21#include "llvm/CodeGen/LiveInterval.h"
22#include "llvm/CodeGen/LiveIntervals.h"
23#include "llvm/CodeGen/LiveVariables.h"
24#include "llvm/CodeGen/MachineBasicBlock.h"
25#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
26#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
27#include "llvm/CodeGen/MachineDomTreeUpdater.h"
28#include "llvm/CodeGen/MachineDominators.h"
29#include "llvm/CodeGen/MachineFunction.h"
30#include "llvm/CodeGen/MachineFunctionPass.h"
31#include "llvm/CodeGen/MachineInstr.h"
32#include "llvm/CodeGen/MachineInstrBuilder.h"
33#include "llvm/CodeGen/MachineLoopInfo.h"
34#include "llvm/CodeGen/MachineOperand.h"
35#include "llvm/CodeGen/MachinePostDominators.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/SlotIndexes.h"
38#include "llvm/CodeGen/TargetInstrInfo.h"
39#include "llvm/CodeGen/TargetOpcodes.h"
40#include "llvm/CodeGen/TargetRegisterInfo.h"
41#include "llvm/CodeGen/TargetSubtargetInfo.h"
42#include "llvm/InitializePasses.h"
43#include "llvm/Pass.h"
44#include "llvm/Support/CommandLine.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/raw_ostream.h"
47#include <cassert>
48#include <iterator>
49#include <utility>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "phi-node-elimination"
54
55static cl::opt<bool>
56 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(Val: false),
57 cl::Hidden,
58 cl::desc("Disable critical edge splitting "
59 "during PHI elimination"));
60
61static cl::opt<bool>
62 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(Val: false),
63 cl::Hidden,
64 cl::desc("Split all critical edges during "
65 "PHI elimination"));
66
67static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
68 "no-phi-elim-live-out-early-exit", cl::init(Val: false), cl::Hidden,
69 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
70
71namespace {
72
73class PHIEliminationImpl {
74 MachineRegisterInfo *MRI = nullptr; // Machine register information
75 LiveVariables *LV = nullptr;
76 LiveIntervals *LIS = nullptr;
77 MachineLoopInfo *MLI = nullptr;
78 MachineDominatorTree *MDT = nullptr;
79 MachinePostDominatorTree *PDT = nullptr;
80 const MachineBranchProbabilityInfo *MBPI = nullptr;
81 MachineBlockFrequencyInfo *MBFI = nullptr;
82
83 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
84 /// in predecessor basic blocks.
85 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
86
87 void LowerPHINode(MachineBasicBlock &MBB,
88 MachineBasicBlock::iterator LastPHIIt,
89 bool AllEdgesCritical);
90
91 /// analyzePHINodes - Gather information about the PHI nodes in
92 /// here. In particular, we want to map the number of uses of a virtual
93 /// register which is used in a PHI node. We map that to the BB the
94 /// vreg is coming from. This is used later to determine when the vreg
95 /// is killed in the BB.
96 void analyzePHINodes(const MachineFunction &MF);
97
98 /// Split critical edges where necessary for good coalescer performance.
99 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
100 MachineLoopInfo *MLI,
101 std::vector<SparseBitVector<>> *LiveInSets,
102 MachineDomTreeUpdater &MDTU);
103
104 // These functions are temporary abstractions around LiveVariables and
105 // LiveIntervals, so they can go away when LiveVariables does.
106 bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
107 bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
108
109 using BBVRegPair = std::pair<unsigned, Register>;
110 using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
111
112 // Count the number of non-undef PHI uses of each register in each BB.
113 VRegPHIUse VRegPHIUseCount;
114
115 // Defs of PHI sources which are implicit_def.
116 SmallPtrSet<MachineInstr *, 4> ImpDefs;
117
118 // Map reusable lowered PHI node -> incoming join register.
119 using LoweredPHIMap =
120 DenseMap<MachineInstr *, Register, MachineInstrExpressionTrait>;
121 LoweredPHIMap LoweredPHIs;
122
123 MachineFunctionPass *P = nullptr;
124 MachineFunctionAnalysisManager *MFAM = nullptr;
125
126public:
127 PHIEliminationImpl(MachineFunctionPass *P) : P(P) {
128 auto *LVWrapper = P->getAnalysisIfAvailable<LiveVariablesWrapperPass>();
129 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
130 auto *MLIWrapper = P->getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
131 auto *MDTWrapper =
132 P->getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();
133 auto *PDTWrapper =
134 P->getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();
135 auto *MBPIWrapper =
136 P->getAnalysisIfAvailable<MachineBranchProbabilityInfoWrapperPass>();
137 auto *MBFIWrapper =
138 P->getAnalysisIfAvailable<MachineBlockFrequencyInfoWrapperPass>();
139
140 LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
141 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
142 MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
143 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;
144 PDT = PDTWrapper ? &PDTWrapper->getPostDomTree() : nullptr;
145 MBPI = MBPIWrapper ? &MBPIWrapper->getMBPI() : nullptr;
146 MBFI = MBFIWrapper ? &MBFIWrapper->getMBFI() : nullptr;
147 }
148
149 PHIEliminationImpl(MachineFunction &MF, MachineFunctionAnalysisManager &AM)
150 : LV(AM.getCachedResult<LiveVariablesAnalysis>(IR&: MF)),
151 LIS(AM.getCachedResult<LiveIntervalsAnalysis>(IR&: MF)),
152 MLI(AM.getCachedResult<MachineLoopAnalysis>(IR&: MF)),
153 MDT(AM.getCachedResult<MachineDominatorTreeAnalysis>(IR&: MF)),
154 PDT(AM.getCachedResult<MachinePostDominatorTreeAnalysis>(IR&: MF)),
155 MBPI(AM.getCachedResult<MachineBranchProbabilityAnalysis>(IR&: MF)),
156 MBFI(AM.getCachedResult<MachineBlockFrequencyAnalysis>(IR&: MF)), MFAM(&AM) {
157 }
158
159 bool run(MachineFunction &MF);
160};
161
162class PHIElimination : public MachineFunctionPass {
163public:
164 static char ID; // Pass identification, replacement for typeid
165
166 PHIElimination() : MachineFunctionPass(ID) {}
167
168 bool runOnMachineFunction(MachineFunction &MF) override {
169 PHIEliminationImpl Impl(this);
170 return Impl.run(MF);
171 }
172
173 MachineFunctionProperties getSetProperties() const override {
174 return MachineFunctionProperties().setNoPHIs();
175 }
176
177 void getAnalysisUsage(AnalysisUsage &AU) const override;
178};
179
180} // end anonymous namespace
181
182PreservedAnalyses
183PHIEliminationPass::run(MachineFunction &MF,
184 MachineFunctionAnalysisManager &MFAM) {
185 PHIEliminationImpl Impl(MF, MFAM);
186 bool Changed = Impl.run(MF);
187 if (!Changed)
188 return PreservedAnalyses::all();
189 auto PA = getMachineFunctionPassPreservedAnalyses();
190 PA.preserve<LiveIntervalsAnalysis>();
191 PA.preserve<LiveVariablesAnalysis>();
192 PA.preserve<SlotIndexesAnalysis>();
193 PA.preserve<MachineDominatorTreeAnalysis>();
194 PA.preserve<MachinePostDominatorTreeAnalysis>();
195 PA.preserve<MachineLoopAnalysis>();
196 PA.preserve<MachineBlockFrequencyAnalysis>();
197 return PA;
198}
199
200STATISTIC(NumLowered, "Number of phis lowered");
201STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
202STATISTIC(NumReused, "Number of reused lowered phis");
203
204char PHIElimination::ID = 0;
205
206char &llvm::PHIEliminationID = PHIElimination::ID;
207
208INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
209 "Eliminate PHI nodes for register allocation", false,
210 false)
211INITIALIZE_PASS_DEPENDENCY(LiveVariablesWrapperPass)
212INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
213INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
214INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
215 "Eliminate PHI nodes for register allocation", false, false)
216
217void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
218 AU.addUsedIfAvailable<LiveVariablesWrapperPass>();
219 AU.addUsedIfAvailable<MachineLoopInfoWrapperPass>();
220 AU.addPreserved<LiveVariablesWrapperPass>();
221 AU.addPreserved<SlotIndexesWrapperPass>();
222 AU.addPreserved<LiveIntervalsWrapperPass>();
223 AU.addPreserved<MachineDominatorTreeWrapperPass>();
224 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();
225 AU.addPreserved<MachineLoopInfoWrapperPass>();
226 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
227 MachineFunctionPass::getAnalysisUsage(AU);
228}
229
230bool PHIEliminationImpl::run(MachineFunction &MF) {
231 MRI = &MF.getRegInfo();
232
233 MachineDomTreeUpdater MDTU(MDT, PDT,
234 MachineDomTreeUpdater::UpdateStrategy::Lazy);
235
236 bool Changed = false;
237
238 // Split critical edges to help the coalescer.
239 if (!DisableEdgeSplitting && (LV || LIS)) {
240 // A set of live-in regs for each MBB which is used to update LV
241 // efficiently also with large functions.
242 std::vector<SparseBitVector<>> LiveInSets;
243 if (LV) {
244 LiveInSets.resize(new_size: MF.size());
245 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
246 // Set the bit for this register for each MBB where it is
247 // live-through or live-in (killed).
248 Register VirtReg = Register::index2VirtReg(Index);
249 MachineInstr *DefMI = MRI->getVRegDef(Reg: VirtReg);
250 if (!DefMI)
251 continue;
252 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg: VirtReg);
253 SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
254 SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
255 while (AliveBlockItr != EndItr) {
256 unsigned BlockNum = *(AliveBlockItr++);
257 LiveInSets[BlockNum].set(Index);
258 }
259 // The register is live into an MBB in which it is killed but not
260 // defined. See comment for VarInfo in LiveVariables.h.
261 MachineBasicBlock *DefMBB = DefMI->getParent();
262 if (VI.Kills.size() > 1 ||
263 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
264 for (auto *MI : VI.Kills)
265 LiveInSets[MI->getParent()->getNumber()].set(Index);
266 }
267 }
268
269 for (auto &MBB : MF)
270 Changed |=
271 SplitPHIEdges(MF, MBB, MLI, LiveInSets: (LV ? &LiveInSets : nullptr), MDTU);
272 }
273
274 // This pass takes the function out of SSA form.
275 MRI->leaveSSA();
276
277 // Populate VRegPHIUseCount
278 if (LV || LIS)
279 analyzePHINodes(MF);
280
281 // Eliminate PHI instructions by inserting copies into predecessor blocks.
282 for (auto &MBB : MF)
283 Changed |= EliminatePHINodes(MF, MBB);
284
285 // Remove dead IMPLICIT_DEF instructions.
286 for (MachineInstr *DefMI : ImpDefs) {
287 Register DefReg = DefMI->getOperand(i: 0).getReg();
288 if (MRI->use_nodbg_empty(RegNo: DefReg)) {
289 if (LIS)
290 LIS->RemoveMachineInstrFromMaps(MI&: *DefMI);
291 DefMI->eraseFromParent();
292 }
293 }
294
295 // Clean up the lowered PHI instructions.
296 for (auto &I : LoweredPHIs) {
297 if (LIS)
298 LIS->RemoveMachineInstrFromMaps(MI&: *I.first);
299 MF.deleteMachineInstr(MI: I.first);
300 }
301
302 LoweredPHIs.clear();
303 ImpDefs.clear();
304 VRegPHIUseCount.clear();
305
306 MF.getProperties().setNoPHIs();
307
308 return Changed;
309}
310
311/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
312/// predecessor basic blocks.
313bool PHIEliminationImpl::EliminatePHINodes(MachineFunction &MF,
314 MachineBasicBlock &MBB) {
315 if (MBB.empty() || !MBB.front().isPHI())
316 return false; // Quick exit for basic blocks without PHIs.
317
318 // Get an iterator to the last PHI node.
319 MachineBasicBlock::iterator LastPHIIt =
320 std::prev(x: MBB.SkipPHIsAndLabels(I: MBB.begin()));
321
322 // If all incoming edges are critical, we try to deduplicate identical PHIs so
323 // that we generate fewer copies. If at any edge is non-critical, we either
324 // have less than two predecessors (=> no PHIs) or a predecessor has only us
325 // as a successor (=> identical PHI node can't occur in different block).
326 bool AllEdgesCritical = MBB.pred_size() >= 2;
327 for (MachineBasicBlock *Pred : MBB.predecessors()) {
328 if (Pred->succ_size() < 2) {
329 AllEdgesCritical = false;
330 break;
331 }
332 }
333
334 while (MBB.front().isPHI())
335 LowerPHINode(MBB, LastPHIIt, AllEdgesCritical);
336
337 return true;
338}
339
340/// Return true if all defs of VirtReg are implicit-defs.
341/// This includes registers with no defs.
342static bool isImplicitlyDefined(Register VirtReg,
343 const MachineRegisterInfo &MRI) {
344 for (MachineInstr &DI : MRI.def_instructions(Reg: VirtReg))
345 if (!DI.isImplicitDef())
346 return false;
347 return true;
348}
349
350/// Return true if all sources of the phi node are implicit_def's, or undef's.
351static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
352 const MachineRegisterInfo &MRI) {
353 for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
354 const MachineOperand &MO = MPhi.getOperand(i: I);
355 if (!isImplicitlyDefined(VirtReg: MO.getReg(), MRI) && !MO.isUndef())
356 return false;
357 }
358 return true;
359}
360/// LowerPHINode - Lower the PHI node at the top of the specified block.
361void PHIEliminationImpl::LowerPHINode(MachineBasicBlock &MBB,
362 MachineBasicBlock::iterator LastPHIIt,
363 bool AllEdgesCritical) {
364 ++NumLowered;
365
366 MachineBasicBlock::iterator AfterPHIsIt = std::next(x: LastPHIIt);
367
368 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
369 MachineInstr *MPhi = MBB.remove(I: &*MBB.begin());
370
371 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
372 Register DestReg = MPhi->getOperand(i: 0).getReg();
373 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
374 bool isDead = MPhi->getOperand(i: 0).isDead();
375
376 // Create a new register for the incoming PHI arguments.
377 MachineFunction &MF = *MBB.getParent();
378 Register IncomingReg;
379 bool EliminateNow = true; // delay elimination of nodes in LoweredPHIs
380 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
381
382 // Insert a register to register copy at the top of the current block (but
383 // after any remaining phi nodes) which copies the new incoming register
384 // into the phi node destination.
385 MachineInstr *PHICopy = nullptr;
386 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
387 if (allPhiOperandsUndefined(MPhi: *MPhi, MRI: *MRI))
388 // If all sources of a PHI node are implicit_def or undef uses, just emit an
389 // implicit_def instead of a copy.
390 PHICopy = BuildMI(BB&: MBB, I: AfterPHIsIt, MIMD: MPhi->getDebugLoc(),
391 MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF), DestReg);
392 else {
393 // Can we reuse an earlier PHI node? This only happens for critical edges,
394 // typically those created by tail duplication. Typically, an identical PHI
395 // node can't occur, so avoid hashing/storing such PHIs, which is somewhat
396 // expensive.
397 Register *Entry = nullptr;
398 if (AllEdgesCritical)
399 Entry = &LoweredPHIs[MPhi];
400 if (Entry && *Entry) {
401 // An identical PHI node was already lowered. Reuse the incoming register.
402 IncomingReg = *Entry;
403 reusedIncoming = true;
404 ++NumReused;
405 LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
406 << *MPhi);
407 } else {
408 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg: DestReg);
409 IncomingReg = MF.getRegInfo().createVirtualRegister(RegClass: RC);
410 if (Entry) {
411 EliminateNow = false;
412 *Entry = IncomingReg;
413 }
414 }
415
416 // Give the target possiblity to handle special cases fallthrough otherwise
417 PHICopy = TII->createPHIDestinationCopy(
418 MBB, InsPt: AfterPHIsIt, DL: MPhi->getDebugLoc(), Src: IncomingReg, Dst: DestReg);
419 }
420
421 if (MPhi->peekDebugInstrNum()) {
422 // If referred to by debug-info, store where this PHI was.
423 MachineFunction *MF = MBB.getParent();
424 unsigned ID = MPhi->peekDebugInstrNum();
425 auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
426 auto Res = MF->DebugPHIPositions.insert(KV: {ID, P});
427 assert(Res.second);
428 (void)Res;
429 }
430
431 // Update live variable information if there is any.
432 if (LV) {
433 if (IncomingReg) {
434 LiveVariables::VarInfo &VI = LV->getVarInfo(Reg: IncomingReg);
435
436 MachineInstr *OldKill = nullptr;
437 bool IsPHICopyAfterOldKill = false;
438
439 if (reusedIncoming && (OldKill = VI.findKill(MBB: &MBB))) {
440 // Calculate whether the PHICopy is after the OldKill.
441 // In general, the PHICopy is inserted as the first non-phi instruction
442 // by default, so it's before the OldKill. But some Target hooks for
443 // createPHIDestinationCopy() may modify the default insert position of
444 // PHICopy.
445 for (auto I = MBB.SkipPHIsAndLabels(I: MBB.begin()), E = MBB.end(); I != E;
446 ++I) {
447 if (I == PHICopy)
448 break;
449
450 if (I == OldKill) {
451 IsPHICopyAfterOldKill = true;
452 break;
453 }
454 }
455 }
456
457 // When we are reusing the incoming register and it has been marked killed
458 // by OldKill, if the PHICopy is after the OldKill, we should remove the
459 // killed flag from OldKill.
460 if (IsPHICopyAfterOldKill) {
461 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
462 LV->removeVirtualRegisterKilled(Reg: IncomingReg, MI&: *OldKill);
463 LLVM_DEBUG(MBB.dump());
464 }
465
466 // Add information to LiveVariables to know that the first used incoming
467 // value or the resued incoming value whose PHICopy is after the OldKIll
468 // is killed. Note that because the value is defined in several places
469 // (once each for each incoming block), the "def" block and instruction
470 // fields for the VarInfo is not filled in.
471 if (!OldKill || IsPHICopyAfterOldKill)
472 LV->addVirtualRegisterKilled(IncomingReg, MI&: *PHICopy);
473 }
474
475 // Since we are going to be deleting the PHI node, if it is the last use of
476 // any registers, or if the value itself is dead, we need to move this
477 // information over to the new copy we just inserted.
478 LV->removeVirtualRegistersKilled(MI&: *MPhi);
479
480 // If the result is dead, update LV.
481 if (isDead) {
482 LV->addVirtualRegisterDead(IncomingReg: DestReg, MI&: *PHICopy);
483 LV->removeVirtualRegisterDead(Reg: DestReg, MI&: *MPhi);
484 }
485 }
486
487 // Update LiveIntervals for the new copy or implicit def.
488 if (LIS) {
489 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(MI&: *PHICopy);
490
491 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(mbb: &MBB);
492 if (IncomingReg) {
493 // Add the region from the beginning of MBB to the copy instruction to
494 // IncomingReg's live interval.
495 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(Reg: IncomingReg);
496 VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(Idx: MBBStartIndex);
497 if (!IncomingVNI)
498 IncomingVNI =
499 IncomingLI.getNextValue(Def: MBBStartIndex, VNInfoAllocator&: LIS->getVNInfoAllocator());
500 IncomingLI.addSegment(S: LiveInterval::Segment(
501 MBBStartIndex, DestCopyIndex.getRegSlot(), IncomingVNI));
502 }
503
504 LiveInterval &DestLI = LIS->getInterval(Reg: DestReg);
505 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals.");
506
507 SlotIndex NewStart = DestCopyIndex.getRegSlot();
508
509 SmallVector<LiveRange *> ToUpdate({&DestLI});
510 for (auto &SR : DestLI.subranges())
511 ToUpdate.push_back(Elt: &SR);
512
513 for (auto LR : ToUpdate) {
514 auto DestSegment = LR->find(Pos: MBBStartIndex);
515 assert(DestSegment != LR->end() &&
516 "PHI destination must be live in block");
517
518 if (LR->endIndex().isDead()) {
519 // A dead PHI's live range begins and ends at the start of the MBB, but
520 // the lowered copy, which will still be dead, needs to begin and end at
521 // the copy instruction.
522 VNInfo *OrigDestVNI = LR->getVNInfoAt(Idx: DestSegment->start);
523 assert(OrigDestVNI && "PHI destination should be live at block entry.");
524 LR->removeSegment(Start: DestSegment->start, End: DestSegment->start.getDeadSlot());
525 LR->createDeadDef(Def: NewStart, VNIAlloc&: LIS->getVNInfoAllocator());
526 LR->removeValNo(ValNo: OrigDestVNI);
527 continue;
528 }
529
530 // Destination copies are not inserted in the same order as the PHI nodes
531 // they replace. Hence the start of the live range may need to be adjusted
532 // to match the actual slot index of the copy.
533 if (DestSegment->start > NewStart) {
534 VNInfo *VNI = LR->getVNInfoAt(Idx: DestSegment->start);
535 assert(VNI && "value should be defined for known segment");
536 LR->addSegment(
537 S: LiveInterval::Segment(NewStart, DestSegment->start, VNI));
538 } else if (DestSegment->start < NewStart) {
539 assert(DestSegment->start >= MBBStartIndex);
540 assert(DestSegment->end >= DestCopyIndex.getRegSlot());
541 LR->removeSegment(Start: DestSegment->start, End: NewStart);
542 }
543 VNInfo *DestVNI = LR->getVNInfoAt(Idx: NewStart);
544 assert(DestVNI && "PHI destination should be live at its definition.");
545 DestVNI->def = NewStart;
546 }
547 }
548
549 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
550 if (LV || LIS) {
551 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
552 if (!MPhi->getOperand(i).isUndef()) {
553 --VRegPHIUseCount[BBVRegPair(
554 MPhi->getOperand(i: i + 1).getMBB()->getNumber(),
555 MPhi->getOperand(i).getReg())];
556 }
557 }
558 }
559
560 // Now loop over all of the incoming arguments, changing them to copy into the
561 // IncomingReg register in the corresponding predecessor basic block.
562 SmallPtrSet<MachineBasicBlock *, 8> MBBsInsertedInto;
563 for (int i = NumSrcs - 1; i >= 0; --i) {
564 Register SrcReg = MPhi->getOperand(i: i * 2 + 1).getReg();
565 unsigned SrcSubReg = MPhi->getOperand(i: i * 2 + 1).getSubReg();
566 bool SrcUndef = MPhi->getOperand(i: i * 2 + 1).isUndef() ||
567 isImplicitlyDefined(VirtReg: SrcReg, MRI: *MRI);
568 assert(SrcReg.isVirtual() &&
569 "Machine PHI Operands must all be virtual registers!");
570
571 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
572 // path the PHI.
573 MachineBasicBlock &opBlock = *MPhi->getOperand(i: i * 2 + 2).getMBB();
574
575 // Check to make sure we haven't already emitted the copy for this block.
576 // This can happen because PHI nodes may have multiple entries for the same
577 // basic block.
578 if (!MBBsInsertedInto.insert(Ptr: &opBlock).second)
579 continue; // If the copy has already been emitted, we're done.
580
581 MachineInstr *SrcRegDef = MRI->getVRegDef(Reg: SrcReg);
582 if (SrcRegDef && TII->isUnspillableTerminator(MI: SrcRegDef)) {
583 assert(SrcRegDef->getOperand(0).isReg() &&
584 SrcRegDef->getOperand(0).isDef() &&
585 "Expected operand 0 to be a reg def!");
586 // Now that the PHI's use has been removed (as the instruction was
587 // removed) there should be no other uses of the SrcReg.
588 assert(MRI->use_empty(SrcReg) &&
589 "Expected a single use from UnspillableTerminator");
590 SrcRegDef->getOperand(i: 0).setReg(IncomingReg);
591
592 // Update LiveVariables.
593 if (LV) {
594 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(Reg: SrcReg);
595 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(Reg: IncomingReg);
596 IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);
597 SrcVI.AliveBlocks.clear();
598 }
599
600 continue;
601 }
602
603 // Find a safe location to insert the copy, this may be the first terminator
604 // in the block (or end()).
605 MachineBasicBlock::iterator InsertPos =
606 findPHICopyInsertPoint(MBB: &opBlock, SuccMBB: &MBB, SrcReg);
607
608 // Insert the copy.
609 MachineInstr *NewSrcInstr = nullptr;
610 if (!reusedIncoming && IncomingReg) {
611 if (SrcUndef) {
612 // The source register is undefined, so there is no need for a real
613 // COPY, but we still need to ensure joint dominance by defs.
614 // Insert an IMPLICIT_DEF instruction.
615 NewSrcInstr =
616 BuildMI(BB&: opBlock, I: InsertPos, MIMD: MPhi->getDebugLoc(),
617 MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF), DestReg: IncomingReg);
618
619 // Clean up the old implicit-def, if there even was one.
620 if (MachineInstr *DefMI = MRI->getVRegDef(Reg: SrcReg))
621 if (DefMI->isImplicitDef())
622 ImpDefs.insert(Ptr: DefMI);
623 } else {
624 // Delete the debug location, since the copy is inserted into a
625 // different basic block.
626 NewSrcInstr = TII->createPHISourceCopy(MBB&: opBlock, InsPt: InsertPos, DL: nullptr,
627 Src: SrcReg, SrcSubReg, Dst: IncomingReg);
628 }
629 }
630
631 // We only need to update the LiveVariables kill of SrcReg if this was the
632 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
633 // out of the predecessor. We can also ignore undef sources.
634 if (LV && !SrcUndef &&
635 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
636 !LV->isLiveOut(Reg: SrcReg, MBB: opBlock)) {
637 // We want to be able to insert a kill of the register if this PHI (aka,
638 // the copy we just inserted) is the last use of the source value. Live
639 // variable analysis conservatively handles this by saying that the value
640 // is live until the end of the block the PHI entry lives in. If the value
641 // really is dead at the PHI copy, there will be no successor blocks which
642 // have the value live-in.
643
644 // Okay, if we now know that the value is not live out of the block, we
645 // can add a kill marker in this block saying that it kills the incoming
646 // value!
647
648 // In our final twist, we have to decide which instruction kills the
649 // register. In most cases this is the copy, however, terminator
650 // instructions at the end of the block may also use the value. In this
651 // case, we should mark the last such terminator as being the killing
652 // block, not the copy.
653 MachineBasicBlock::iterator KillInst = opBlock.end();
654 for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();
655 ++Term) {
656 if (Term->readsRegister(Reg: SrcReg, /*TRI=*/nullptr))
657 KillInst = Term;
658 }
659
660 if (KillInst == opBlock.end()) {
661 // No terminator uses the register.
662
663 if (reusedIncoming || !IncomingReg) {
664 // We may have to rewind a bit if we didn't insert a copy this time.
665 KillInst = InsertPos;
666 while (KillInst != opBlock.begin()) {
667 --KillInst;
668 if (KillInst->isDebugInstr())
669 continue;
670 if (KillInst->readsRegister(Reg: SrcReg, /*TRI=*/nullptr))
671 break;
672 }
673 } else {
674 // We just inserted this copy.
675 KillInst = NewSrcInstr;
676 }
677 }
678 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&
679 "Cannot find kill instruction");
680
681 // Finally, mark it killed.
682 LV->addVirtualRegisterKilled(IncomingReg: SrcReg, MI&: *KillInst);
683
684 // This vreg no longer lives all of the way through opBlock.
685 unsigned opBlockNum = opBlock.getNumber();
686 LV->getVarInfo(Reg: SrcReg).AliveBlocks.reset(Idx: opBlockNum);
687 }
688
689 if (LIS) {
690 if (NewSrcInstr) {
691 LIS->InsertMachineInstrInMaps(MI&: *NewSrcInstr);
692 LIS->addSegmentToEndOfBlock(Reg: IncomingReg, startInst&: *NewSrcInstr);
693 }
694
695 if (!SrcUndef &&
696 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
697 LiveInterval &SrcLI = LIS->getInterval(Reg: SrcReg);
698
699 bool isLiveOut = false;
700 for (MachineBasicBlock *Succ : opBlock.successors()) {
701 SlotIndex startIdx = LIS->getMBBStartIdx(mbb: Succ);
702 VNInfo *VNI = SrcLI.getVNInfoAt(Idx: startIdx);
703
704 // Definitions by other PHIs are not truly live-in for our purposes.
705 if (VNI && VNI->def != startIdx) {
706 isLiveOut = true;
707 break;
708 }
709 }
710
711 if (!isLiveOut) {
712 MachineBasicBlock::iterator KillInst = opBlock.end();
713 for (MachineBasicBlock::iterator Term = InsertPos;
714 Term != opBlock.end(); ++Term) {
715 if (Term->readsRegister(Reg: SrcReg, /*TRI=*/nullptr))
716 KillInst = Term;
717 }
718
719 if (KillInst == opBlock.end()) {
720 // No terminator uses the register.
721
722 if (reusedIncoming || !IncomingReg) {
723 // We may have to rewind a bit if we didn't just insert a copy.
724 KillInst = InsertPos;
725 while (KillInst != opBlock.begin()) {
726 --KillInst;
727 if (KillInst->isDebugInstr())
728 continue;
729 if (KillInst->readsRegister(Reg: SrcReg, /*TRI=*/nullptr))
730 break;
731 }
732 } else {
733 // We just inserted this copy.
734 KillInst = std::prev(x: InsertPos);
735 }
736 }
737 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&
738 "Cannot find kill instruction");
739
740 SlotIndex LastUseIndex = LIS->getInstructionIndex(Instr: *KillInst);
741 SrcLI.removeSegment(Start: LastUseIndex.getRegSlot(),
742 End: LIS->getMBBEndIdx(mbb: &opBlock));
743 for (auto &SR : SrcLI.subranges()) {
744 SR.removeSegment(Start: LastUseIndex.getRegSlot(),
745 End: LIS->getMBBEndIdx(mbb: &opBlock));
746 }
747 }
748 }
749 }
750 }
751
752 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
753 if (EliminateNow) {
754 if (LIS)
755 LIS->RemoveMachineInstrFromMaps(MI&: *MPhi);
756 MF.deleteMachineInstr(MI: MPhi);
757 }
758}
759
760/// analyzePHINodes - Gather information about the PHI nodes in here. In
761/// particular, we want to map the number of uses of a virtual register which is
762/// used in a PHI node. We map that to the BB the vreg is coming from. This is
763/// used later to determine when the vreg is killed in the BB.
764void PHIEliminationImpl::analyzePHINodes(const MachineFunction &MF) {
765 for (const auto &MBB : MF) {
766 for (const auto &BBI : MBB) {
767 if (!BBI.isPHI())
768 break;
769 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
770 if (!BBI.getOperand(i).isUndef()) {
771 ++VRegPHIUseCount[BBVRegPair(
772 BBI.getOperand(i: i + 1).getMBB()->getNumber(),
773 BBI.getOperand(i).getReg())];
774 }
775 }
776 }
777 }
778}
779
780bool PHIEliminationImpl::SplitPHIEdges(
781 MachineFunction &MF, MachineBasicBlock &MBB, MachineLoopInfo *MLI,
782 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater &MDTU) {
783 if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
784 return false; // Quick exit for basic blocks without PHIs.
785
786 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(BB: &MBB) : nullptr;
787 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
788
789 bool Changed = false;
790 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
791 BBI != BBE && BBI->isPHI(); ++BBI) {
792 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
793 Register Reg = BBI->getOperand(i).getReg();
794 MachineBasicBlock *PreMBB = BBI->getOperand(i: i + 1).getMBB();
795 // Is there a critical edge from PreMBB to MBB?
796 if (PreMBB->succ_size() == 1)
797 continue;
798
799 // Avoid splitting backedges of loops. It would introduce small
800 // out-of-line blocks into the loop which is very bad for code placement.
801 if (PreMBB == &MBB && !SplitAllCriticalEdges)
802 continue;
803 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(BB: PreMBB) : nullptr;
804 if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
805 continue;
806
807 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
808 // when the source register is live-out for some other reason than a phi
809 // use. That means the copy we will insert in PreMBB won't be a kill, and
810 // there is a risk it may not be coalesced away.
811 //
812 // If the copy would be a kill, there is no need to split the edge.
813 bool ShouldSplit = isLiveOutPastPHIs(Reg, MBB: PreMBB);
814 if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
815 continue;
816 if (ShouldSplit) {
817 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
818 << printMBBReference(*PreMBB) << " -> "
819 << printMBBReference(MBB) << ": " << *BBI);
820 }
821
822 // If Reg is not live-in to MBB, it means it must be live-in to some
823 // other PreMBB successor, and we can avoid the interference by splitting
824 // the edge.
825 //
826 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
827 // is likely to be left after coalescing. If we are looking at a loop
828 // exiting edge, split it so we won't insert code in the loop, otherwise
829 // don't bother.
830 ShouldSplit = ShouldSplit && !isLiveIn(Reg, MBB: &MBB);
831
832 // Check for a loop exiting edge.
833 if (!ShouldSplit && CurLoop != PreLoop) {
834 LLVM_DEBUG({
835 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
836 if (PreLoop)
837 dbgs() << "PreLoop: " << *PreLoop;
838 if (CurLoop)
839 dbgs() << "CurLoop: " << *CurLoop;
840 });
841 // This edge could be entering a loop, exiting a loop, or it could be
842 // both: Jumping directly form one loop to the header of a sibling
843 // loop.
844 // Split unless this edge is entering CurLoop from an outer loop.
845 ShouldSplit = PreLoop && !PreLoop->contains(L: CurLoop);
846 }
847 if (!ShouldSplit && !SplitAllCriticalEdges)
848 continue;
849 MachineBasicBlock *NewBB;
850 if (P)
851 NewBB = PreMBB->SplitCriticalEdge(Succ: &MBB, P&: *P, LiveInSets, MDTU: &MDTU);
852 else
853 NewBB = PreMBB->SplitCriticalEdge(Succ: &MBB, MFAM&: *MFAM, LiveInSets, MDTU: &MDTU);
854 if (!NewBB) {
855 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
856 continue;
857 }
858
859 // Patch up MBFI after split if it is available.
860 if (MBFI) {
861 assert(MBPI);
862 MBFI->onEdgeSplit(NewPredecessor: *PreMBB, NewSuccessor: *NewBB, MBPI: *MBPI);
863 }
864
865 Changed = true;
866 ++NumCriticalEdgesSplit;
867 }
868 }
869 return Changed;
870}
871
872bool PHIEliminationImpl::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
873 assert((LV || LIS) &&
874 "isLiveIn() requires either LiveVariables or LiveIntervals");
875 if (LIS)
876 return LIS->isLiveInToMBB(LR: LIS->getInterval(Reg), mbb: MBB);
877 else
878 return LV->isLiveIn(Reg, MBB: *MBB);
879}
880
881bool PHIEliminationImpl::isLiveOutPastPHIs(Register Reg,
882 const MachineBasicBlock *MBB) {
883 assert((LV || LIS) &&
884 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
885 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
886 // so that a register used only in a PHI is not live out of the block. In
887 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather
888 // than in the predecessor basic block, so that a register used only in a PHI
889 // is live out of the block.
890 if (LIS) {
891 const LiveInterval &LI = LIS->getInterval(Reg);
892 for (const MachineBasicBlock *SI : MBB->successors())
893 if (LI.liveAt(index: LIS->getMBBStartIdx(mbb: SI)))
894 return true;
895 return false;
896 } else {
897 return LV->isLiveOut(Reg, MBB: *MBB);
898 }
899}
900