LLVM 19.0.0git
PHIElimination.cpp
Go to the documentation of this file.
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 "PHIEliminationUtils.h"
16#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/Statistic.h"
37#include "llvm/Pass.h"
39#include "llvm/Support/Debug.h"
41#include <cassert>
42#include <iterator>
43#include <utility>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "phi-node-elimination"
48
49static cl::opt<bool>
50DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
51 cl::Hidden, cl::desc("Disable critical edge splitting "
52 "during PHI elimination"));
53
54static cl::opt<bool>
55SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
56 cl::Hidden, cl::desc("Split all critical edges during "
57 "PHI elimination"));
58
60 "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
61 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
62
63namespace {
64
65 class PHIElimination : public MachineFunctionPass {
66 MachineRegisterInfo *MRI = nullptr; // Machine register information
67 LiveVariables *LV = nullptr;
68 LiveIntervals *LIS = nullptr;
69
70 public:
71 static char ID; // Pass identification, replacement for typeid
72
73 PHIElimination() : MachineFunctionPass(ID) {
75 }
76
77 bool runOnMachineFunction(MachineFunction &MF) override;
78 void getAnalysisUsage(AnalysisUsage &AU) const override;
79
80 private:
81 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
82 /// in predecessor basic blocks.
83 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
84
85 void LowerPHINode(MachineBasicBlock &MBB,
87
88 /// analyzePHINodes - Gather information about the PHI nodes in
89 /// here. In particular, we want to map the number of uses of a virtual
90 /// register which is used in a PHI node. We map that to the BB the
91 /// vreg is coming from. This is used later to determine when the vreg
92 /// is killed in the BB.
93 void analyzePHINodes(const MachineFunction& MF);
94
95 /// Split critical edges where necessary for good coalescer performance.
96 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
97 MachineLoopInfo *MLI,
98 std::vector<SparseBitVector<>> *LiveInSets);
99
100 // These functions are temporary abstractions around LiveVariables and
101 // LiveIntervals, so they can go away when LiveVariables does.
102 bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
103 bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
104
105 using BBVRegPair = std::pair<unsigned, Register>;
106 using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
107
108 // Count the number of non-undef PHI uses of each register in each BB.
109 VRegPHIUse VRegPHIUseCount;
110
111 // Defs of PHI sources which are implicit_def.
113
114 // Map reusable lowered PHI node -> incoming join register.
115 using LoweredPHIMap =
117 LoweredPHIMap LoweredPHIs;
118 };
119
120} // end anonymous namespace
121
122STATISTIC(NumLowered, "Number of phis lowered");
123STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
124STATISTIC(NumReused, "Number of reused lowered phis");
125
126char PHIElimination::ID = 0;
127
128char& llvm::PHIEliminationID = PHIElimination::ID;
129
131 "Eliminate PHI nodes for register allocation",
132 false, false)
135 "Eliminate PHI nodes for register allocation", false, false)
136
137void 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>();
145}
146
147bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
148 MRI = &MF.getRegInfo();
149 LV = getAnalysisIfAvailable<LiveVariables>();
150 LIS = getAnalysisIfAvailable<LiveIntervals>();
151
152 bool Changed = false;
153
154 // Split critical edges to help the coalescer.
155 if (!DisableEdgeSplitting && (LV || LIS)) {
156 // A set of live-in regs for each MBB which is used to update LV
157 // efficiently also with large functions.
158 std::vector<SparseBitVector<>> LiveInSets;
159 if (LV) {
160 LiveInSets.resize(MF.size());
161 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
162 // Set the bit for this register for each MBB where it is
163 // live-through or live-in (killed).
165 MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
166 if (!DefMI)
167 continue;
168 LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
169 SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
170 SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
171 while (AliveBlockItr != EndItr) {
172 unsigned BlockNum = *(AliveBlockItr++);
173 LiveInSets[BlockNum].set(Index);
174 }
175 // The register is live into an MBB in which it is killed but not
176 // defined. See comment for VarInfo in LiveVariables.h.
177 MachineBasicBlock *DefMBB = DefMI->getParent();
178 if (VI.Kills.size() > 1 ||
179 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
180 for (auto *MI : VI.Kills)
181 LiveInSets[MI->getParent()->getNumber()].set(Index);
182 }
183 }
184
185 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
186 for (auto &MBB : MF)
187 Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
188 }
189
190 // This pass takes the function out of SSA form.
191 MRI->leaveSSA();
192
193 // Populate VRegPHIUseCount
194 analyzePHINodes(MF);
195
196 // Eliminate PHI instructions by inserting copies into predecessor blocks.
197 for (auto &MBB : MF)
198 Changed |= EliminatePHINodes(MF, MBB);
199
200 // Remove dead IMPLICIT_DEF instructions.
201 for (MachineInstr *DefMI : ImpDefs) {
202 Register DefReg = DefMI->getOperand(0).getReg();
203 if (MRI->use_nodbg_empty(DefReg)) {
204 if (LIS)
205 LIS->RemoveMachineInstrFromMaps(*DefMI);
207 }
208 }
209
210 // Clean up the lowered PHI instructions.
211 for (auto &I : LoweredPHIs) {
212 if (LIS)
213 LIS->RemoveMachineInstrFromMaps(*I.first);
214 MF.deleteMachineInstr(I.first);
215 }
216
217 // TODO: we should use the incremental DomTree updater here.
218 if (Changed)
219 if (auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
220 MDT->getBase().recalculate(MF);
221
222 LoweredPHIs.clear();
223 ImpDefs.clear();
224 VRegPHIUseCount.clear();
225
226 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
227
228 return Changed;
229}
230
231/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
232/// predecessor basic blocks.
233bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
235 if (MBB.empty() || !MBB.front().isPHI())
236 return false; // Quick exit for basic blocks without PHIs.
237
238 // Get an iterator to the last PHI node.
240 std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
241
242 while (MBB.front().isPHI())
243 LowerPHINode(MBB, LastPHIIt);
244
245 return true;
246}
247
248/// Return true if all defs of VirtReg are implicit-defs.
249/// This includes registers with no defs.
250static bool isImplicitlyDefined(unsigned VirtReg,
251 const MachineRegisterInfo &MRI) {
252 for (MachineInstr &DI : MRI.def_instructions(VirtReg))
253 if (!DI.isImplicitDef())
254 return false;
255 return true;
256}
257
258/// Return true if all sources of the phi node are implicit_def's, or undef's.
259static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
260 const MachineRegisterInfo &MRI) {
261 for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
262 const MachineOperand &MO = MPhi.getOperand(I);
263 if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
264 return false;
265 }
266 return true;
267}
268/// LowerPHINode - Lower the PHI node at the top of the specified block.
269void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
270 MachineBasicBlock::iterator LastPHIIt) {
271 ++NumLowered;
272
273 MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
274
275 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
276 MachineInstr *MPhi = MBB.remove(&*MBB.begin());
277
278 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
279 Register DestReg = MPhi->getOperand(0).getReg();
280 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
281 bool isDead = MPhi->getOperand(0).isDead();
282
283 // Create a new register for the incoming PHI arguments.
285 unsigned IncomingReg = 0;
286 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
287
288 // Insert a register to register copy at the top of the current block (but
289 // after any remaining phi nodes) which copies the new incoming register
290 // into the phi node destination.
291 MachineInstr *PHICopy = nullptr;
293 if (allPhiOperandsUndefined(*MPhi, *MRI))
294 // If all sources of a PHI node are implicit_def or undef uses, just emit an
295 // implicit_def instead of a copy.
296 PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
297 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
298 else {
299 // Can we reuse an earlier PHI node? This only happens for critical edges,
300 // typically those created by tail duplication.
301 unsigned &entry = LoweredPHIs[MPhi];
302 if (entry) {
303 // An identical PHI node was already lowered. Reuse the incoming register.
304 IncomingReg = entry;
305 reusedIncoming = true;
306 ++NumReused;
307 LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
308 << *MPhi);
309 } else {
310 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
311 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
312 }
313 // Give the target possiblity to handle special cases fallthrough otherwise
314 PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
315 IncomingReg, DestReg);
316 }
317
318 if (MPhi->peekDebugInstrNum()) {
319 // If referred to by debug-info, store where this PHI was.
321 unsigned ID = MPhi->peekDebugInstrNum();
322 auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
323 auto Res = MF->DebugPHIPositions.insert({ID, P});
324 assert(Res.second);
325 (void)Res;
326 }
327
328 // Update live variable information if there is any.
329 if (LV) {
330 if (IncomingReg) {
331 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
332
333 MachineInstr *OldKill = nullptr;
334 bool IsPHICopyAfterOldKill = false;
335
336 if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
337 // Calculate whether the PHICopy is after the OldKill.
338 // In general, the PHICopy is inserted as the first non-phi instruction
339 // by default, so it's before the OldKill. But some Target hooks for
340 // createPHIDestinationCopy() may modify the default insert position of
341 // PHICopy.
342 for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
343 I != E; ++I) {
344 if (I == PHICopy)
345 break;
346
347 if (I == OldKill) {
348 IsPHICopyAfterOldKill = true;
349 break;
350 }
351 }
352 }
353
354 // When we are reusing the incoming register and it has been marked killed
355 // by OldKill, if the PHICopy is after the OldKill, we should remove the
356 // killed flag from OldKill.
357 if (IsPHICopyAfterOldKill) {
358 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
359 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
361 }
362
363 // Add information to LiveVariables to know that the first used incoming
364 // value or the resued incoming value whose PHICopy is after the OldKIll
365 // is killed. Note that because the value is defined in several places
366 // (once each for each incoming block), the "def" block and instruction
367 // fields for the VarInfo is not filled in.
368 if (!OldKill || IsPHICopyAfterOldKill)
369 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
370 }
371
372 // Since we are going to be deleting the PHI node, if it is the last use of
373 // any registers, or if the value itself is dead, we need to move this
374 // information over to the new copy we just inserted.
375 LV->removeVirtualRegistersKilled(*MPhi);
376
377 // If the result is dead, update LV.
378 if (isDead) {
379 LV->addVirtualRegisterDead(DestReg, *PHICopy);
380 LV->removeVirtualRegisterDead(DestReg, *MPhi);
381 }
382 }
383
384 // Update LiveIntervals for the new copy or implicit def.
385 if (LIS) {
386 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
387
388 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
389 if (IncomingReg) {
390 // Add the region from the beginning of MBB to the copy instruction to
391 // IncomingReg's live interval.
392 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);
393 VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
394 if (!IncomingVNI)
395 IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
396 LIS->getVNInfoAllocator());
397 IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
398 DestCopyIndex.getRegSlot(),
399 IncomingVNI));
400 }
401
402 LiveInterval &DestLI = LIS->getInterval(DestReg);
403 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals.");
404
405 SlotIndex NewStart = DestCopyIndex.getRegSlot();
406
407 SmallVector<LiveRange *> ToUpdate({&DestLI});
408 for (auto &SR : DestLI.subranges())
409 ToUpdate.push_back(&SR);
410
411 for (auto LR : ToUpdate) {
412 auto DestSegment = LR->find(MBBStartIndex);
413 assert(DestSegment != LR->end() &&
414 "PHI destination must be live in block");
415
416 if (LR->endIndex().isDead()) {
417 // A dead PHI's live range begins and ends at the start of the MBB, but
418 // the lowered copy, which will still be dead, needs to begin and end at
419 // the copy instruction.
420 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);
421 assert(OrigDestVNI && "PHI destination should be live at block entry.");
422 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());
423 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator());
424 LR->removeValNo(OrigDestVNI);
425 continue;
426 }
427
428 // Destination copies are not inserted in the same order as the PHI nodes
429 // they replace. Hence the start of the live range may need to be adjusted
430 // to match the actual slot index of the copy.
431 if (DestSegment->start > NewStart) {
432 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);
433 assert(VNI && "value should be defined for known segment");
434 LR->addSegment(
435 LiveInterval::Segment(NewStart, DestSegment->start, VNI));
436 } else if (DestSegment->start < NewStart) {
437 assert(DestSegment->start >= MBBStartIndex);
438 assert(DestSegment->end >= DestCopyIndex.getRegSlot());
439 LR->removeSegment(DestSegment->start, NewStart);
440 }
441 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);
442 assert(DestVNI && "PHI destination should be live at its definition.");
443 DestVNI->def = NewStart;
444 }
445 }
446
447 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
448 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
449 if (!MPhi->getOperand(i).isUndef()) {
450 --VRegPHIUseCount[BBVRegPair(
451 MPhi->getOperand(i + 1).getMBB()->getNumber(),
452 MPhi->getOperand(i).getReg())];
453 }
454 }
455
456 // Now loop over all of the incoming arguments, changing them to copy into the
457 // IncomingReg register in the corresponding predecessor basic block.
458 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
459 for (int i = NumSrcs - 1; i >= 0; --i) {
460 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
461 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
462 bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
463 isImplicitlyDefined(SrcReg, *MRI);
464 assert(SrcReg.isVirtual() &&
465 "Machine PHI Operands must all be virtual registers!");
466
467 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
468 // path the PHI.
469 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
470
471 // Check to make sure we haven't already emitted the copy for this block.
472 // This can happen because PHI nodes may have multiple entries for the same
473 // basic block.
474 if (!MBBsInsertedInto.insert(&opBlock).second)
475 continue; // If the copy has already been emitted, we're done.
476
477 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
478 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
479 assert(SrcRegDef->getOperand(0).isReg() &&
480 SrcRegDef->getOperand(0).isDef() &&
481 "Expected operand 0 to be a reg def!");
482 // Now that the PHI's use has been removed (as the instruction was
483 // removed) there should be no other uses of the SrcReg.
484 assert(MRI->use_empty(SrcReg) &&
485 "Expected a single use from UnspillableTerminator");
486 SrcRegDef->getOperand(0).setReg(IncomingReg);
487
488 // Update LiveVariables.
489 if (LV) {
490 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);
491 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);
492 IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);
493 SrcVI.AliveBlocks.clear();
494 }
495
496 continue;
497 }
498
499 // Find a safe location to insert the copy, this may be the first terminator
500 // in the block (or end()).
502 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
503
504 // Insert the copy.
505 MachineInstr *NewSrcInstr = nullptr;
506 if (!reusedIncoming && IncomingReg) {
507 if (SrcUndef) {
508 // The source register is undefined, so there is no need for a real
509 // COPY, but we still need to ensure joint dominance by defs.
510 // Insert an IMPLICIT_DEF instruction.
511 NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
512 TII->get(TargetOpcode::IMPLICIT_DEF),
513 IncomingReg);
514
515 // Clean up the old implicit-def, if there even was one.
516 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
517 if (DefMI->isImplicitDef())
518 ImpDefs.insert(DefMI);
519 } else {
520 // Delete the debug location, since the copy is inserted into a
521 // different basic block.
522 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
523 SrcReg, SrcSubReg, IncomingReg);
524 }
525 }
526
527 // We only need to update the LiveVariables kill of SrcReg if this was the
528 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
529 // out of the predecessor. We can also ignore undef sources.
530 if (LV && !SrcUndef &&
531 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
532 !LV->isLiveOut(SrcReg, opBlock)) {
533 // We want to be able to insert a kill of the register if this PHI (aka,
534 // the copy we just inserted) is the last use of the source value. Live
535 // variable analysis conservatively handles this by saying that the value
536 // is live until the end of the block the PHI entry lives in. If the value
537 // really is dead at the PHI copy, there will be no successor blocks which
538 // have the value live-in.
539
540 // Okay, if we now know that the value is not live out of the block, we
541 // can add a kill marker in this block saying that it kills the incoming
542 // value!
543
544 // In our final twist, we have to decide which instruction kills the
545 // register. In most cases this is the copy, however, terminator
546 // instructions at the end of the block may also use the value. In this
547 // case, we should mark the last such terminator as being the killing
548 // block, not the copy.
549 MachineBasicBlock::iterator KillInst = opBlock.end();
550 for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();
551 ++Term) {
552 if (Term->readsRegister(SrcReg))
553 KillInst = Term;
554 }
555
556 if (KillInst == opBlock.end()) {
557 // No terminator uses the register.
558
559 if (reusedIncoming || !IncomingReg) {
560 // We may have to rewind a bit if we didn't insert a copy this time.
561 KillInst = InsertPos;
562 while (KillInst != opBlock.begin()) {
563 --KillInst;
564 if (KillInst->isDebugInstr())
565 continue;
566 if (KillInst->readsRegister(SrcReg))
567 break;
568 }
569 } else {
570 // We just inserted this copy.
571 KillInst = NewSrcInstr;
572 }
573 }
574 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
575
576 // Finally, mark it killed.
577 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
578
579 // This vreg no longer lives all of the way through opBlock.
580 unsigned opBlockNum = opBlock.getNumber();
581 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
582 }
583
584 if (LIS) {
585 if (NewSrcInstr) {
586 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
587 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
588 }
589
590 if (!SrcUndef &&
591 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
592 LiveInterval &SrcLI = LIS->getInterval(SrcReg);
593
594 bool isLiveOut = false;
595 for (MachineBasicBlock *Succ : opBlock.successors()) {
596 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
597 VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
598
599 // Definitions by other PHIs are not truly live-in for our purposes.
600 if (VNI && VNI->def != startIdx) {
601 isLiveOut = true;
602 break;
603 }
604 }
605
606 if (!isLiveOut) {
607 MachineBasicBlock::iterator KillInst = opBlock.end();
608 for (MachineBasicBlock::iterator Term = InsertPos;
609 Term != opBlock.end(); ++Term) {
610 if (Term->readsRegister(SrcReg))
611 KillInst = Term;
612 }
613
614 if (KillInst == opBlock.end()) {
615 // No terminator uses the register.
616
617 if (reusedIncoming || !IncomingReg) {
618 // We may have to rewind a bit if we didn't just insert a copy.
619 KillInst = InsertPos;
620 while (KillInst != opBlock.begin()) {
621 --KillInst;
622 if (KillInst->isDebugInstr())
623 continue;
624 if (KillInst->readsRegister(SrcReg))
625 break;
626 }
627 } else {
628 // We just inserted this copy.
629 KillInst = std::prev(InsertPos);
630 }
631 }
632 assert(KillInst->readsRegister(SrcReg) &&
633 "Cannot find kill instruction");
634
635 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
636 SrcLI.removeSegment(LastUseIndex.getRegSlot(),
637 LIS->getMBBEndIdx(&opBlock));
638 for (auto &SR : SrcLI.subranges()) {
639 SR.removeSegment(LastUseIndex.getRegSlot(),
640 LIS->getMBBEndIdx(&opBlock));
641 }
642 }
643 }
644 }
645 }
646
647 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
648 if (reusedIncoming || !IncomingReg) {
649 if (LIS)
650 LIS->RemoveMachineInstrFromMaps(*MPhi);
651 MF.deleteMachineInstr(MPhi);
652 }
653}
654
655/// analyzePHINodes - Gather information about the PHI nodes in here. In
656/// particular, we want to map the number of uses of a virtual register which is
657/// used in a PHI node. We map that to the BB the vreg is coming from. This is
658/// used later to determine when the vreg is killed in the BB.
659void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
660 for (const auto &MBB : MF) {
661 for (const auto &BBI : MBB) {
662 if (!BBI.isPHI())
663 break;
664 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
665 if (!BBI.getOperand(i).isUndef()) {
666 ++VRegPHIUseCount[BBVRegPair(
667 BBI.getOperand(i + 1).getMBB()->getNumber(),
668 BBI.getOperand(i).getReg())];
669 }
670 }
671 }
672 }
673}
674
675bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
677 MachineLoopInfo *MLI,
678 std::vector<SparseBitVector<>> *LiveInSets) {
679 if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
680 return false; // Quick exit for basic blocks without PHIs.
681
682 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
683 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
684
685 bool Changed = false;
686 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
687 BBI != BBE && BBI->isPHI(); ++BBI) {
688 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
689 Register Reg = BBI->getOperand(i).getReg();
690 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
691 // Is there a critical edge from PreMBB to MBB?
692 if (PreMBB->succ_size() == 1)
693 continue;
694
695 // Avoid splitting backedges of loops. It would introduce small
696 // out-of-line blocks into the loop which is very bad for code placement.
697 if (PreMBB == &MBB && !SplitAllCriticalEdges)
698 continue;
699 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
700 if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
701 continue;
702
703 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
704 // when the source register is live-out for some other reason than a phi
705 // use. That means the copy we will insert in PreMBB won't be a kill, and
706 // there is a risk it may not be coalesced away.
707 //
708 // If the copy would be a kill, there is no need to split the edge.
709 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
710 if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
711 continue;
712 if (ShouldSplit) {
713 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
714 << printMBBReference(*PreMBB) << " -> "
715 << printMBBReference(MBB) << ": " << *BBI);
716 }
717
718 // If Reg is not live-in to MBB, it means it must be live-in to some
719 // other PreMBB successor, and we can avoid the interference by splitting
720 // the edge.
721 //
722 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
723 // is likely to be left after coalescing. If we are looking at a loop
724 // exiting edge, split it so we won't insert code in the loop, otherwise
725 // don't bother.
726 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
727
728 // Check for a loop exiting edge.
729 if (!ShouldSplit && CurLoop != PreLoop) {
730 LLVM_DEBUG({
731 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
732 if (PreLoop)
733 dbgs() << "PreLoop: " << *PreLoop;
734 if (CurLoop)
735 dbgs() << "CurLoop: " << *CurLoop;
736 });
737 // This edge could be entering a loop, exiting a loop, or it could be
738 // both: Jumping directly form one loop to the header of a sibling
739 // loop.
740 // Split unless this edge is entering CurLoop from an outer loop.
741 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
742 }
743 if (!ShouldSplit && !SplitAllCriticalEdges)
744 continue;
745 if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
746 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
747 continue;
748 }
749 Changed = true;
750 ++NumCriticalEdgesSplit;
751 }
752 }
753 return Changed;
754}
755
756bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
757 assert((LV || LIS) &&
758 "isLiveIn() requires either LiveVariables or LiveIntervals");
759 if (LIS)
760 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
761 else
762 return LV->isLiveIn(Reg, *MBB);
763}
764
765bool PHIElimination::isLiveOutPastPHIs(Register Reg,
766 const MachineBasicBlock *MBB) {
767 assert((LV || LIS) &&
768 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
769 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
770 // so that a register used only in a PHI is not live out of the block. In
771 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
772 // in the predecessor basic block, so that a register used only in a PHI is live
773 // out of the block.
774 if (LIS) {
775 const LiveInterval &LI = LIS->getInterval(Reg);
776 for (const MachineBasicBlock *SI : MBB->successors())
777 if (LI.liveAt(LIS->getMBBStartIdx(SI)))
778 return true;
779 return false;
780 } else {
781 return LV->isLiveOut(Reg, *MBB);
782 }
783}
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder MachineInstrBuilder & DefMI
MachineBasicBlock & MBB
Rewrite undef for PHI
Unify divergent function exit nodes
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
static bool allPhiOperandsUndefined(const MachineInstr &MPhi, const MachineRegisterInfo &MRI)
Return true if all sources of the phi node are implicit_def's, or undef's.
Eliminate PHI nodes for register allocation
static cl::opt< bool > NoPhiElimLiveOutEarlyExit("no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden, cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."))
static bool isImplicitlyDefined(unsigned VirtReg, const MachineRegisterInfo &MRI)
Return true if all defs of VirtReg are implicit-defs.
static cl::opt< bool > DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), cl::Hidden, cl::desc("Disable critical edge splitting " "during PHI elimination"))
static cl::opt< bool > SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), cl::Hidden, cl::desc("Split all critical edges during " "PHI elimination"))
#define DEBUG_TYPE
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Represent the analysis usage information of a pass.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
iterator_range< subrange_iterator > subranges()
Definition: LiveInterval.h:782
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
bool empty() const
Definition: LiveInterval.h:382
VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified interval from this live range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:421
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getHeader() const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
MachineInstr * remove(MachineInstr *I)
Remove the unbundled instruction from the instruction list without deleting it.
unsigned succ_size() const
MachineBasicBlock * SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, std::vector< SparseBitVector<> > *LiveInSets=nullptr)
Split the critical edge from this block to the given successor block, and return the newly created bl...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Location of a PHI instruction that is also a debug-info variable value, for the duration of register ...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void deleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
unsigned size() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
DenseMap< unsigned, DebugPHIRegallocPos > DebugPHIPositions
Map of debug instruction numbers to the position of their PHI instructions during register allocation...
Representation of each machine instruction.
Definition: MachineInstr.h:69
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:547
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
Definition: MachineInstr.h:520
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:473
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineBasicBlock * getMBB() const
void setReg(Register Reg)
Change the register this operand corresponds to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
Definition: SlotIndexes.h:240
SlotIndexes pass.
Definition: SlotIndexes.h:300
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
SparseBitVectorIterator iterator
TargetInstrInfo - Interface to description of machine instruction set.
virtual const TargetInstrInfo * getInstrInfo() const
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void initializePHIEliminationPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
char & PHIEliminationID
PHIElimination - This pass eliminates machine instruction PHI nodes by inserting copy instructions.
MachineBasicBlock::iterator findPHICopyInsertPoint(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, unsigned SrcReg)
findPHICopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg when following the CFG...
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
VarInfo - This represents the regions where a virtual register is live in the program.
Definition: LiveVariables.h:80
SparseBitVector AliveBlocks
AliveBlocks - Set of blocks in which this value is alive completely through.
Definition: LiveVariables.h:85