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