LLVM 18.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 // Increment use count of the newly created virtual register.
334 LV->setPHIJoin(IncomingReg);
335
336 MachineInstr *OldKill = nullptr;
337 bool IsPHICopyAfterOldKill = false;
338
339 if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
340 // Calculate whether the PHICopy is after the OldKill.
341 // In general, the PHICopy is inserted as the first non-phi instruction
342 // by default, so it's before the OldKill. But some Target hooks for
343 // createPHIDestinationCopy() may modify the default insert position of
344 // PHICopy.
345 for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
346 I != E; ++I) {
347 if (I == PHICopy)
348 break;
349
350 if (I == OldKill) {
351 IsPHICopyAfterOldKill = true;
352 break;
353 }
354 }
355 }
356
357 // When we are reusing the incoming register and it has been marked killed
358 // by OldKill, if the PHICopy is after the OldKill, we should remove the
359 // killed flag from OldKill.
360 if (IsPHICopyAfterOldKill) {
361 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
362 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
364 }
365
366 // Add information to LiveVariables to know that the first used incoming
367 // value or the resued incoming value whose PHICopy is after the OldKIll
368 // is killed. Note that because the value is defined in several places
369 // (once each for each incoming block), the "def" block and instruction
370 // fields for the VarInfo is not filled in.
371 if (!OldKill || IsPHICopyAfterOldKill)
372 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
373 }
374
375 // Since we are going to be deleting the PHI node, if it is the last use of
376 // any registers, or if the value itself is dead, we need to move this
377 // information over to the new copy we just inserted.
378 LV->removeVirtualRegistersKilled(*MPhi);
379
380 // If the result is dead, update LV.
381 if (isDead) {
382 LV->addVirtualRegisterDead(DestReg, *PHICopy);
383 LV->removeVirtualRegisterDead(DestReg, *MPhi);
384 }
385 }
386
387 // Update LiveIntervals for the new copy or implicit def.
388 if (LIS) {
389 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
390
391 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
392 if (IncomingReg) {
393 // Add the region from the beginning of MBB to the copy instruction to
394 // IncomingReg's live interval.
395 LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
396 VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
397 if (!IncomingVNI)
398 IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
399 LIS->getVNInfoAllocator());
400 IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
401 DestCopyIndex.getRegSlot(),
402 IncomingVNI));
403 }
404
405 LiveInterval &DestLI = LIS->getInterval(DestReg);
406 assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
407 if (DestLI.endIndex().isDead()) {
408 // A dead PHI's live range begins and ends at the start of the MBB, but
409 // the lowered copy, which will still be dead, needs to begin and end at
410 // the copy instruction.
411 VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
412 assert(OrigDestVNI && "PHI destination should be live at block entry.");
413 DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
414 DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
415 LIS->getVNInfoAllocator());
416 DestLI.removeValNo(OrigDestVNI);
417 } else {
418 // Otherwise, remove the region from the beginning of MBB to the copy
419 // instruction from DestReg's live interval.
420 DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
421 VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
422 assert(DestVNI && "PHI destination should be live at its definition.");
423 DestVNI->def = DestCopyIndex.getRegSlot();
424 }
425 }
426
427 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
428 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
429 if (!MPhi->getOperand(i).isUndef()) {
430 --VRegPHIUseCount[BBVRegPair(
431 MPhi->getOperand(i + 1).getMBB()->getNumber(),
432 MPhi->getOperand(i).getReg())];
433 }
434 }
435
436 // Now loop over all of the incoming arguments, changing them to copy into the
437 // IncomingReg register in the corresponding predecessor basic block.
438 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
439 for (int i = NumSrcs - 1; i >= 0; --i) {
440 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
441 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
442 bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
443 isImplicitlyDefined(SrcReg, *MRI);
444 assert(SrcReg.isVirtual() &&
445 "Machine PHI Operands must all be virtual registers!");
446
447 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
448 // path the PHI.
449 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
450
451 // Check to make sure we haven't already emitted the copy for this block.
452 // This can happen because PHI nodes may have multiple entries for the same
453 // basic block.
454 if (!MBBsInsertedInto.insert(&opBlock).second)
455 continue; // If the copy has already been emitted, we're done.
456
457 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
458 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
459 assert(SrcRegDef->getOperand(0).isReg() &&
460 SrcRegDef->getOperand(0).isDef() &&
461 "Expected operand 0 to be a reg def!");
462 // Now that the PHI's use has been removed (as the instruction was
463 // removed) there should be no other uses of the SrcReg.
464 assert(MRI->use_empty(SrcReg) &&
465 "Expected a single use from UnspillableTerminator");
466 SrcRegDef->getOperand(0).setReg(IncomingReg);
467
468 // Update LiveVariables.
469 if (LV) {
470 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);
471 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);
472 IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);
473 SrcVI.AliveBlocks.clear();
474 }
475
476 continue;
477 }
478
479 // Find a safe location to insert the copy, this may be the first terminator
480 // in the block (or end()).
482 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
483
484 // Insert the copy.
485 MachineInstr *NewSrcInstr = nullptr;
486 if (!reusedIncoming && IncomingReg) {
487 if (SrcUndef) {
488 // The source register is undefined, so there is no need for a real
489 // COPY, but we still need to ensure joint dominance by defs.
490 // Insert an IMPLICIT_DEF instruction.
491 NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
492 TII->get(TargetOpcode::IMPLICIT_DEF),
493 IncomingReg);
494
495 // Clean up the old implicit-def, if there even was one.
496 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
497 if (DefMI->isImplicitDef())
498 ImpDefs.insert(DefMI);
499 } else {
500 // Delete the debug location, since the copy is inserted into a
501 // different basic block.
502 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
503 SrcReg, SrcSubReg, IncomingReg);
504 }
505 }
506
507 // We only need to update the LiveVariables kill of SrcReg if this was the
508 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
509 // out of the predecessor. We can also ignore undef sources.
510 if (LV && !SrcUndef &&
511 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
512 !LV->isLiveOut(SrcReg, opBlock)) {
513 // We want to be able to insert a kill of the register if this PHI (aka,
514 // the copy we just inserted) is the last use of the source value. Live
515 // variable analysis conservatively handles this by saying that the value
516 // is live until the end of the block the PHI entry lives in. If the value
517 // really is dead at the PHI copy, there will be no successor blocks which
518 // have the value live-in.
519
520 // Okay, if we now know that the value is not live out of the block, we
521 // can add a kill marker in this block saying that it kills the incoming
522 // value!
523
524 // In our final twist, we have to decide which instruction kills the
525 // register. In most cases this is the copy, however, terminator
526 // instructions at the end of the block may also use the value. In this
527 // case, we should mark the last such terminator as being the killing
528 // block, not the copy.
529 MachineBasicBlock::iterator KillInst = opBlock.end();
530 for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();
531 ++Term) {
532 if (Term->readsRegister(SrcReg))
533 KillInst = Term;
534 }
535
536 if (KillInst == opBlock.end()) {
537 // No terminator uses the register.
538
539 if (reusedIncoming || !IncomingReg) {
540 // We may have to rewind a bit if we didn't insert a copy this time.
541 KillInst = InsertPos;
542 while (KillInst != opBlock.begin()) {
543 --KillInst;
544 if (KillInst->isDebugInstr())
545 continue;
546 if (KillInst->readsRegister(SrcReg))
547 break;
548 }
549 } else {
550 // We just inserted this copy.
551 KillInst = NewSrcInstr;
552 }
553 }
554 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
555
556 // Finally, mark it killed.
557 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
558
559 // This vreg no longer lives all of the way through opBlock.
560 unsigned opBlockNum = opBlock.getNumber();
561 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
562 }
563
564 if (LIS) {
565 if (NewSrcInstr) {
566 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
567 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
568 }
569
570 if (!SrcUndef &&
571 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
572 LiveInterval &SrcLI = LIS->getInterval(SrcReg);
573
574 bool isLiveOut = false;
575 for (MachineBasicBlock *Succ : opBlock.successors()) {
576 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
577 VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
578
579 // Definitions by other PHIs are not truly live-in for our purposes.
580 if (VNI && VNI->def != startIdx) {
581 isLiveOut = true;
582 break;
583 }
584 }
585
586 if (!isLiveOut) {
587 MachineBasicBlock::iterator KillInst = opBlock.end();
588 for (MachineBasicBlock::iterator Term = InsertPos;
589 Term != opBlock.end(); ++Term) {
590 if (Term->readsRegister(SrcReg))
591 KillInst = Term;
592 }
593
594 if (KillInst == opBlock.end()) {
595 // No terminator uses the register.
596
597 if (reusedIncoming || !IncomingReg) {
598 // We may have to rewind a bit if we didn't just insert a copy.
599 KillInst = InsertPos;
600 while (KillInst != opBlock.begin()) {
601 --KillInst;
602 if (KillInst->isDebugInstr())
603 continue;
604 if (KillInst->readsRegister(SrcReg))
605 break;
606 }
607 } else {
608 // We just inserted this copy.
609 KillInst = std::prev(InsertPos);
610 }
611 }
612 assert(KillInst->readsRegister(SrcReg) &&
613 "Cannot find kill instruction");
614
615 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
616 SrcLI.removeSegment(LastUseIndex.getRegSlot(),
617 LIS->getMBBEndIdx(&opBlock));
618 }
619 }
620 }
621 }
622
623 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
624 if (reusedIncoming || !IncomingReg) {
625 if (LIS)
626 LIS->RemoveMachineInstrFromMaps(*MPhi);
627 MF.deleteMachineInstr(MPhi);
628 }
629}
630
631/// analyzePHINodes - Gather information about the PHI nodes in here. In
632/// particular, we want to map the number of uses of a virtual register which is
633/// used in a PHI node. We map that to the BB the vreg is coming from. This is
634/// used later to determine when the vreg is killed in the BB.
635void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
636 for (const auto &MBB : MF) {
637 for (const auto &BBI : MBB) {
638 if (!BBI.isPHI())
639 break;
640 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
641 if (!BBI.getOperand(i).isUndef()) {
642 ++VRegPHIUseCount[BBVRegPair(
643 BBI.getOperand(i + 1).getMBB()->getNumber(),
644 BBI.getOperand(i).getReg())];
645 }
646 }
647 }
648 }
649}
650
651bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
653 MachineLoopInfo *MLI,
654 std::vector<SparseBitVector<>> *LiveInSets) {
655 if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
656 return false; // Quick exit for basic blocks without PHIs.
657
658 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
659 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
660
661 bool Changed = false;
662 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
663 BBI != BBE && BBI->isPHI(); ++BBI) {
664 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
665 Register Reg = BBI->getOperand(i).getReg();
666 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
667 // Is there a critical edge from PreMBB to MBB?
668 if (PreMBB->succ_size() == 1)
669 continue;
670
671 // Avoid splitting backedges of loops. It would introduce small
672 // out-of-line blocks into the loop which is very bad for code placement.
673 if (PreMBB == &MBB && !SplitAllCriticalEdges)
674 continue;
675 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
676 if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
677 continue;
678
679 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
680 // when the source register is live-out for some other reason than a phi
681 // use. That means the copy we will insert in PreMBB won't be a kill, and
682 // there is a risk it may not be coalesced away.
683 //
684 // If the copy would be a kill, there is no need to split the edge.
685 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
686 if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
687 continue;
688 if (ShouldSplit) {
689 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
690 << printMBBReference(*PreMBB) << " -> "
691 << printMBBReference(MBB) << ": " << *BBI);
692 }
693
694 // If Reg is not live-in to MBB, it means it must be live-in to some
695 // other PreMBB successor, and we can avoid the interference by splitting
696 // the edge.
697 //
698 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
699 // is likely to be left after coalescing. If we are looking at a loop
700 // exiting edge, split it so we won't insert code in the loop, otherwise
701 // don't bother.
702 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
703
704 // Check for a loop exiting edge.
705 if (!ShouldSplit && CurLoop != PreLoop) {
706 LLVM_DEBUG({
707 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
708 if (PreLoop)
709 dbgs() << "PreLoop: " << *PreLoop;
710 if (CurLoop)
711 dbgs() << "CurLoop: " << *CurLoop;
712 });
713 // This edge could be entering a loop, exiting a loop, or it could be
714 // both: Jumping directly form one loop to the header of a sibling
715 // loop.
716 // Split unless this edge is entering CurLoop from an outer loop.
717 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
718 }
719 if (!ShouldSplit && !SplitAllCriticalEdges)
720 continue;
721 if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
722 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
723 continue;
724 }
725 Changed = true;
726 ++NumCriticalEdgesSplit;
727 }
728 }
729 return Changed;
730}
731
732bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
733 assert((LV || LIS) &&
734 "isLiveIn() requires either LiveVariables or LiveIntervals");
735 if (LIS)
736 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
737 else
738 return LV->isLiveIn(Reg, *MBB);
739}
740
741bool PHIElimination::isLiveOutPastPHIs(Register Reg,
742 const MachineBasicBlock *MBB) {
743 assert((LV || LIS) &&
744 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
745 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
746 // so that a register used only in a PHI is not live out of the block. In
747 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
748 // in the predecessor basic block, so that a register used only in a PHI is live
749 // out of the block.
750 if (LIS) {
751 const LiveInterval &LI = LIS->getInterval(Reg);
752 for (const MachineBasicBlock *SI : MBB->successors())
753 if (LI.liveAt(LIS->getMBBStartIdx(SI)))
754 return true;
755 return false;
756 } else {
757 return LV->isLiveOut(Reg, *MBB);
758 }
759}
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:686
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:401
VNInfo * createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc)
createDeadDef - Make sure the range has a value defined at Def.
void removeValNo(VNInfo *ValNo)
removeValNo - Remove all the segments defined by the specified value#.
bool empty() const
Definition: LiveInterval.h:382
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
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 segment from this 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:68
bool isImplicitDef() const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:546
unsigned peekDebugInstrNum() const
Examine the instruction number of this MachineInstr.
Definition: MachineInstr.h:519
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:472
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
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 getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:246
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:241
bool isDead() const
isDead - Returns true if this is a dead def kill slot.
Definition: SlotIndexes.h:223
SlotIndexes pass.
Definition: SlotIndexes.h:301
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
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:445
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