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"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/CodeGen/LiveInterval.h"
21 #include "llvm/CodeGen/LiveIntervals.h"
22 #include "llvm/CodeGen/LiveVariables.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineDominators.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineFunctionPass.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineLoopInfo.h"
30 #include "llvm/CodeGen/MachineOperand.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/SlotIndexes.h"
33 #include "llvm/CodeGen/TargetInstrInfo.h"
34 #include "llvm/CodeGen/TargetOpcodes.h"
35 #include "llvm/CodeGen/TargetRegisterInfo.h"
36 #include "llvm/CodeGen/TargetSubtargetInfo.h"
37 #include "llvm/Pass.h"
38 #include "llvm/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include <cassert>
42 #include <iterator>
43 #include <utility>
44
45 using namespace llvm;
46
47 #define DEBUG_TYPE "phi-node-elimination"
48
49 static cl::opt<bool>
50 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
51 cl::Hidden, cl::desc("Disable critical edge splitting "
52 "during PHI elimination"));
53
54 static cl::opt<bool>
55 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
56 cl::Hidden, cl::desc("Split all critical edges during "
57 "PHI elimination"));
58
59 static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
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
63 namespace {
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
PHIElimination()73 PHIElimination() : MachineFunctionPass(ID) {
74 initializePHIEliminationPass(*PassRegistry::getPassRegistry());
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,
86 MachineBasicBlock::iterator LastPHIIt);
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.
112 SmallPtrSet<MachineInstr*, 4> ImpDefs;
113
114 // Map reusable lowered PHI node -> incoming join register.
115 using LoweredPHIMap =
116 DenseMap<MachineInstr*, unsigned, MachineInstrExpressionTrait>;
117 LoweredPHIMap LoweredPHIs;
118 };
119
120 } // end anonymous namespace
121
122 STATISTIC(NumLowered, "Number of phis lowered");
123 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
124 STATISTIC(NumReused, "Number of reused lowered phis");
125
126 char PHIElimination::ID = 0;
127
128 char& llvm::PHIEliminationID = PHIElimination::ID;
129
130 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
131 "Eliminate PHI nodes for register allocation",
132 false, false)
INITIALIZE_PASS_DEPENDENCY(LiveVariables)133 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
134 INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
135 "Eliminate PHI nodes for register allocation", false, false)
136
137 void 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>();
144 MachineFunctionPass::getAnalysisUsage(AU);
145 }
146
runOnMachineFunction(MachineFunction & MF)147 bool 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).
164 Register VirtReg = Register::index2VirtReg(Index);
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);
206 DefMI->eraseFromParent();
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.
EliminatePHINodes(MachineFunction & MF,MachineBasicBlock & MBB)233 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
234 MachineBasicBlock &MBB) {
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.
239 MachineBasicBlock::iterator LastPHIIt =
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.
isImplicitlyDefined(unsigned VirtReg,const MachineRegisterInfo & MRI)250 static 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.
allPhiOperandsUndefined(const MachineInstr & MPhi,const MachineRegisterInfo & MRI)259 static 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.
LowerPHINode(MachineBasicBlock & MBB,MachineBasicBlock::iterator LastPHIIt)269 void 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.
284 MachineFunction &MF = *MBB.getParent();
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;
292 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
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.
320 MachineFunction *MF = MBB.getParent();
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);
360 LLVM_DEBUG(MBB.dump());
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()).
501 MachineBasicBlock::iterator InsertPos =
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.
analyzePHINodes(const MachineFunction & MF)659 void 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
SplitPHIEdges(MachineFunction & MF,MachineBasicBlock & MBB,MachineLoopInfo * MLI,std::vector<SparseBitVector<>> * LiveInSets)675 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
676 MachineBasicBlock &MBB,
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
isLiveIn(Register Reg,const MachineBasicBlock * MBB)756 bool 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
isLiveOutPastPHIs(Register Reg,const MachineBasicBlock * MBB)765 bool 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 }
784