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