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/TargetLowering.h"
35 #include "llvm/CodeGen/TargetOpcodes.h"
36 #include "llvm/CodeGen/TargetPassConfig.h"
37 #include "llvm/CodeGen/TargetRegisterInfo.h"
38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include <cassert>
44 #include <iterator>
45 #include <utility>
46
47 using namespace llvm;
48
49 #define DEBUG_TYPE "phi-node-elimination"
50
51 static cl::opt<bool>
52 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
53 cl::Hidden, cl::desc("Disable critical edge splitting "
54 "during PHI elimination"));
55
56 static cl::opt<bool>
57 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
58 cl::Hidden, cl::desc("Split all critical edges during "
59 "PHI elimination"));
60
61 static cl::opt<bool> NoPhiElimLiveOutEarlyExit(
62 "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
63 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));
64
65 namespace {
66
67 class PHIElimination : public MachineFunctionPass {
68 MachineRegisterInfo *MRI; // Machine register information
69 LiveVariables *LV;
70 LiveIntervals *LIS;
71
72 public:
73 static char ID; // Pass identification, replacement for typeid
74
PHIElimination()75 PHIElimination() : MachineFunctionPass(ID) {
76 initializePHIEliminationPass(*PassRegistry::getPassRegistry());
77 }
78
79 bool runOnMachineFunction(MachineFunction &MF) override;
80 void getAnalysisUsage(AnalysisUsage &AU) const override;
81
82 private:
83 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
84 /// in predecessor basic blocks.
85 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
86
87 void LowerPHINode(MachineBasicBlock &MBB,
88 MachineBasicBlock::iterator LastPHIIt);
89
90 /// analyzePHINodes - Gather information about the PHI nodes in
91 /// here. In particular, we want to map the number of uses of a virtual
92 /// register which is used in a PHI node. We map that to the BB the
93 /// vreg is coming from. This is used later to determine when the vreg
94 /// is killed in the BB.
95 void analyzePHINodes(const MachineFunction& MF);
96
97 /// Split critical edges where necessary for good coalescer performance.
98 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,
99 MachineLoopInfo *MLI,
100 std::vector<SparseBitVector<>> *LiveInSets);
101
102 // These functions are temporary abstractions around LiveVariables and
103 // LiveIntervals, so they can go away when LiveVariables does.
104 bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);
105 bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);
106
107 using BBVRegPair = std::pair<unsigned, Register>;
108 using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
109
110 VRegPHIUse VRegPHIUseCount;
111
112 // Defs of PHI sources which are implicit_def.
113 SmallPtrSet<MachineInstr*, 4> ImpDefs;
114
115 // Map reusable lowered PHI node -> incoming join register.
116 using LoweredPHIMap =
117 DenseMap<MachineInstr*, unsigned, MachineInstrExpressionTrait>;
118 LoweredPHIMap LoweredPHIs;
119 };
120
121 } // end anonymous namespace
122
123 STATISTIC(NumLowered, "Number of phis lowered");
124 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");
125 STATISTIC(NumReused, "Number of reused lowered phis");
126
127 char PHIElimination::ID = 0;
128
129 char& llvm::PHIEliminationID = PHIElimination::ID;
130
131 INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,
132 "Eliminate PHI nodes for register allocation",
133 false, false)
INITIALIZE_PASS_DEPENDENCY(LiveVariables)134 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
135 INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,
136 "Eliminate PHI nodes for register allocation", false, false)
137
138 void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
139 AU.addUsedIfAvailable<LiveVariables>();
140 AU.addPreserved<LiveVariables>();
141 AU.addPreserved<SlotIndexes>();
142 AU.addPreserved<LiveIntervals>();
143 AU.addPreserved<MachineDominatorTree>();
144 AU.addPreserved<MachineLoopInfo>();
145 MachineFunctionPass::getAnalysisUsage(AU);
146 }
147
runOnMachineFunction(MachineFunction & MF)148 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) {
149 MRI = &MF.getRegInfo();
150 LV = getAnalysisIfAvailable<LiveVariables>();
151 LIS = getAnalysisIfAvailable<LiveIntervals>();
152
153 bool Changed = false;
154
155 // Split critical edges to help the coalescer.
156 if (!DisableEdgeSplitting && (LV || LIS)) {
157 // A set of live-in regs for each MBB which is used to update LV
158 // efficiently also with large functions.
159 std::vector<SparseBitVector<>> LiveInSets;
160 if (LV) {
161 LiveInSets.resize(MF.size());
162 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
163 // Set the bit for this register for each MBB where it is
164 // live-through or live-in (killed).
165 unsigned VirtReg = Register::index2VirtReg(Index);
166 MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
167 if (!DefMI)
168 continue;
169 LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
170 SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();
171 SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();
172 while (AliveBlockItr != EndItr) {
173 unsigned BlockNum = *(AliveBlockItr++);
174 LiveInSets[BlockNum].set(Index);
175 }
176 // The register is live into an MBB in which it is killed but not
177 // defined. See comment for VarInfo in LiveVariables.h.
178 MachineBasicBlock *DefMBB = DefMI->getParent();
179 if (VI.Kills.size() > 1 ||
180 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
181 for (auto *MI : VI.Kills)
182 LiveInSets[MI->getParent()->getNumber()].set(Index);
183 }
184 }
185
186 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
187 for (auto &MBB : MF)
188 Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr));
189 }
190
191 // This pass takes the function out of SSA form.
192 MRI->leaveSSA();
193
194 // Populate VRegPHIUseCount
195 analyzePHINodes(MF);
196
197 // Eliminate PHI instructions by inserting copies into predecessor blocks.
198 for (auto &MBB : MF)
199 Changed |= EliminatePHINodes(MF, MBB);
200
201 // Remove dead IMPLICIT_DEF instructions.
202 for (MachineInstr *DefMI : ImpDefs) {
203 Register DefReg = DefMI->getOperand(0).getReg();
204 if (MRI->use_nodbg_empty(DefReg)) {
205 if (LIS)
206 LIS->RemoveMachineInstrFromMaps(*DefMI);
207 DefMI->eraseFromParent();
208 }
209 }
210
211 // Clean up the lowered PHI instructions.
212 for (auto &I : LoweredPHIs) {
213 if (LIS)
214 LIS->RemoveMachineInstrFromMaps(*I.first);
215 MF.DeleteMachineInstr(I.first);
216 }
217
218 // TODO: we should use the incremental DomTree updater here.
219 if (Changed)
220 if (auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>())
221 MDT->getBase().recalculate(MF);
222
223 LoweredPHIs.clear();
224 ImpDefs.clear();
225 VRegPHIUseCount.clear();
226
227 MF.getProperties().set(MachineFunctionProperties::Property::NoPHIs);
228
229 return Changed;
230 }
231
232 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
233 /// predecessor basic blocks.
EliminatePHINodes(MachineFunction & MF,MachineBasicBlock & MBB)234 bool PHIElimination::EliminatePHINodes(MachineFunction &MF,
235 MachineBasicBlock &MBB) {
236 if (MBB.empty() || !MBB.front().isPHI())
237 return false; // Quick exit for basic blocks without PHIs.
238
239 // Get an iterator to the last PHI node.
240 MachineBasicBlock::iterator LastPHIIt =
241 std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));
242
243 while (MBB.front().isPHI())
244 LowerPHINode(MBB, LastPHIIt);
245
246 return true;
247 }
248
249 /// Return true if all defs of VirtReg are implicit-defs.
250 /// This includes registers with no defs.
isImplicitlyDefined(unsigned VirtReg,const MachineRegisterInfo & MRI)251 static bool isImplicitlyDefined(unsigned VirtReg,
252 const MachineRegisterInfo &MRI) {
253 for (MachineInstr &DI : MRI.def_instructions(VirtReg))
254 if (!DI.isImplicitDef())
255 return false;
256 return true;
257 }
258
259 /// Return true if all sources of the phi node are implicit_def's, or undef's.
allPhiOperandsUndefined(const MachineInstr & MPhi,const MachineRegisterInfo & MRI)260 static bool allPhiOperandsUndefined(const MachineInstr &MPhi,
261 const MachineRegisterInfo &MRI) {
262 for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {
263 const MachineOperand &MO = MPhi.getOperand(I);
264 if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())
265 return false;
266 }
267 return true;
268 }
269 /// LowerPHINode - Lower the PHI node at the top of the specified block.
LowerPHINode(MachineBasicBlock & MBB,MachineBasicBlock::iterator LastPHIIt)270 void PHIElimination::LowerPHINode(MachineBasicBlock &MBB,
271 MachineBasicBlock::iterator LastPHIIt) {
272 ++NumLowered;
273
274 MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);
275
276 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
277 MachineInstr *MPhi = MBB.remove(&*MBB.begin());
278
279 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
280 Register DestReg = MPhi->getOperand(0).getReg();
281 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
282 bool isDead = MPhi->getOperand(0).isDead();
283
284 // Create a new register for the incoming PHI arguments.
285 MachineFunction &MF = *MBB.getParent();
286 unsigned IncomingReg = 0;
287 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?
288
289 // Insert a register to register copy at the top of the current block (but
290 // after any remaining phi nodes) which copies the new incoming register
291 // into the phi node destination.
292 MachineInstr *PHICopy = nullptr;
293 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
294 if (allPhiOperandsUndefined(*MPhi, *MRI))
295 // If all sources of a PHI node are implicit_def or undef uses, just emit an
296 // implicit_def instead of a copy.
297 PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
298 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
299 else {
300 // Can we reuse an earlier PHI node? This only happens for critical edges,
301 // typically those created by tail duplication.
302 unsigned &entry = LoweredPHIs[MPhi];
303 if (entry) {
304 // An identical PHI node was already lowered. Reuse the incoming register.
305 IncomingReg = entry;
306 reusedIncoming = true;
307 ++NumReused;
308 LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "
309 << *MPhi);
310 } else {
311 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
312 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
313 }
314 // Give the target possiblity to handle special cases fallthrough otherwise
315 PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
316 IncomingReg, DestReg);
317 }
318
319 // Update live variable information if there is any.
320 if (LV) {
321 if (IncomingReg) {
322 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
323
324 // Increment use count of the newly created virtual register.
325 LV->setPHIJoin(IncomingReg);
326
327 MachineInstr *OldKill = nullptr;
328 bool IsPHICopyAfterOldKill = false;
329
330 if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {
331 // Calculate whether the PHICopy is after the OldKill.
332 // In general, the PHICopy is inserted as the first non-phi instruction
333 // by default, so it's before the OldKill. But some Target hooks for
334 // createPHIDestinationCopy() may modify the default insert position of
335 // PHICopy.
336 for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end();
337 I != E; ++I) {
338 if (I == PHICopy)
339 break;
340
341 if (I == OldKill) {
342 IsPHICopyAfterOldKill = true;
343 break;
344 }
345 }
346 }
347
348 // When we are reusing the incoming register and it has been marked killed
349 // by OldKill, if the PHICopy is after the OldKill, we should remove the
350 // killed flag from OldKill.
351 if (IsPHICopyAfterOldKill) {
352 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);
353 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
354 LLVM_DEBUG(MBB.dump());
355 }
356
357 // Add information to LiveVariables to know that the first used incoming
358 // value or the resued incoming value whose PHICopy is after the OldKIll
359 // is killed. Note that because the value is defined in several places
360 // (once each for each incoming block), the "def" block and instruction
361 // fields for the VarInfo is not filled in.
362 if (!OldKill || IsPHICopyAfterOldKill)
363 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
364 }
365
366 // Since we are going to be deleting the PHI node, if it is the last use of
367 // any registers, or if the value itself is dead, we need to move this
368 // information over to the new copy we just inserted.
369 LV->removeVirtualRegistersKilled(*MPhi);
370
371 // If the result is dead, update LV.
372 if (isDead) {
373 LV->addVirtualRegisterDead(DestReg, *PHICopy);
374 LV->removeVirtualRegisterDead(DestReg, *MPhi);
375 }
376 }
377
378 // Update LiveIntervals for the new copy or implicit def.
379 if (LIS) {
380 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
381
382 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
383 if (IncomingReg) {
384 // Add the region from the beginning of MBB to the copy instruction to
385 // IncomingReg's live interval.
386 LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg);
387 VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);
388 if (!IncomingVNI)
389 IncomingVNI = IncomingLI.getNextValue(MBBStartIndex,
390 LIS->getVNInfoAllocator());
391 IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex,
392 DestCopyIndex.getRegSlot(),
393 IncomingVNI));
394 }
395
396 LiveInterval &DestLI = LIS->getInterval(DestReg);
397 assert(!DestLI.empty() && "PHIs should have nonempty LiveIntervals.");
398 if (DestLI.endIndex().isDead()) {
399 // A dead PHI's live range begins and ends at the start of the MBB, but
400 // the lowered copy, which will still be dead, needs to begin and end at
401 // the copy instruction.
402 VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex);
403 assert(OrigDestVNI && "PHI destination should be live at block entry.");
404 DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot());
405 DestLI.createDeadDef(DestCopyIndex.getRegSlot(),
406 LIS->getVNInfoAllocator());
407 DestLI.removeValNo(OrigDestVNI);
408 } else {
409 // Otherwise, remove the region from the beginning of MBB to the copy
410 // instruction from DestReg's live interval.
411 DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot());
412 VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot());
413 assert(DestVNI && "PHI destination should be live at its definition.");
414 DestVNI->def = DestCopyIndex.getRegSlot();
415 }
416 }
417
418 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
419 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
420 --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
421 MPhi->getOperand(i).getReg())];
422
423 // Now loop over all of the incoming arguments, changing them to copy into the
424 // IncomingReg register in the corresponding predecessor basic block.
425 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto;
426 for (int i = NumSrcs - 1; i >= 0; --i) {
427 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
428 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg();
429 bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() ||
430 isImplicitlyDefined(SrcReg, *MRI);
431 assert(Register::isVirtualRegister(SrcReg) &&
432 "Machine PHI Operands must all be virtual registers!");
433
434 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source
435 // path the PHI.
436 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB();
437
438 // Check to make sure we haven't already emitted the copy for this block.
439 // This can happen because PHI nodes may have multiple entries for the same
440 // basic block.
441 if (!MBBsInsertedInto.insert(&opBlock).second)
442 continue; // If the copy has already been emitted, we're done.
443
444 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
445 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
446 assert(SrcRegDef->getOperand(0).isReg() &&
447 SrcRegDef->getOperand(0).isDef() &&
448 "Expected operand 0 to be a reg def!");
449 // Now that the PHI's use has been removed (as the instruction was
450 // removed) there should be no other uses of the SrcReg.
451 assert(MRI->use_empty(SrcReg) &&
452 "Expected a single use from UnspillableTerminator");
453 SrcRegDef->getOperand(0).setReg(IncomingReg);
454 continue;
455 }
456
457 // Find a safe location to insert the copy, this may be the first terminator
458 // in the block (or end()).
459 MachineBasicBlock::iterator InsertPos =
460 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);
461
462 // Insert the copy.
463 MachineInstr *NewSrcInstr = nullptr;
464 if (!reusedIncoming && IncomingReg) {
465 if (SrcUndef) {
466 // The source register is undefined, so there is no need for a real
467 // COPY, but we still need to ensure joint dominance by defs.
468 // Insert an IMPLICIT_DEF instruction.
469 NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
470 TII->get(TargetOpcode::IMPLICIT_DEF),
471 IncomingReg);
472
473 // Clean up the old implicit-def, if there even was one.
474 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
475 if (DefMI->isImplicitDef())
476 ImpDefs.insert(DefMI);
477 } else {
478 NewSrcInstr =
479 TII->createPHISourceCopy(opBlock, InsertPos, MPhi->getDebugLoc(),
480 SrcReg, SrcSubReg, IncomingReg);
481 }
482 }
483
484 // We only need to update the LiveVariables kill of SrcReg if this was the
485 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live
486 // out of the predecessor. We can also ignore undef sources.
487 if (LV && !SrcUndef &&
488 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&
489 !LV->isLiveOut(SrcReg, opBlock)) {
490 // We want to be able to insert a kill of the register if this PHI (aka,
491 // the copy we just inserted) is the last use of the source value. Live
492 // variable analysis conservatively handles this by saying that the value
493 // is live until the end of the block the PHI entry lives in. If the value
494 // really is dead at the PHI copy, there will be no successor blocks which
495 // have the value live-in.
496
497 // Okay, if we now know that the value is not live out of the block, we
498 // can add a kill marker in this block saying that it kills the incoming
499 // value!
500
501 // In our final twist, we have to decide which instruction kills the
502 // register. In most cases this is the copy, however, terminator
503 // instructions at the end of the block may also use the value. In this
504 // case, we should mark the last such terminator as being the killing
505 // block, not the copy.
506 MachineBasicBlock::iterator KillInst = opBlock.end();
507 MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
508 for (MachineBasicBlock::iterator Term = FirstTerm;
509 Term != opBlock.end(); ++Term) {
510 if (Term->readsRegister(SrcReg))
511 KillInst = Term;
512 }
513
514 if (KillInst == opBlock.end()) {
515 // No terminator uses the register.
516
517 if (reusedIncoming || !IncomingReg) {
518 // We may have to rewind a bit if we didn't insert a copy this time.
519 KillInst = FirstTerm;
520 while (KillInst != opBlock.begin()) {
521 --KillInst;
522 if (KillInst->isDebugInstr())
523 continue;
524 if (KillInst->readsRegister(SrcReg))
525 break;
526 }
527 } else {
528 // We just inserted this copy.
529 KillInst = NewSrcInstr;
530 }
531 }
532 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction");
533
534 // Finally, mark it killed.
535 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
536
537 // This vreg no longer lives all of the way through opBlock.
538 unsigned opBlockNum = opBlock.getNumber();
539 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
540 }
541
542 if (LIS) {
543 if (NewSrcInstr) {
544 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
545 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
546 }
547
548 if (!SrcUndef &&
549 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {
550 LiveInterval &SrcLI = LIS->getInterval(SrcReg);
551
552 bool isLiveOut = false;
553 for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(),
554 SE = opBlock.succ_end(); SI != SE; ++SI) {
555 SlotIndex startIdx = LIS->getMBBStartIdx(*SI);
556 VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);
557
558 // Definitions by other PHIs are not truly live-in for our purposes.
559 if (VNI && VNI->def != startIdx) {
560 isLiveOut = true;
561 break;
562 }
563 }
564
565 if (!isLiveOut) {
566 MachineBasicBlock::iterator KillInst = opBlock.end();
567 MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator();
568 for (MachineBasicBlock::iterator Term = FirstTerm;
569 Term != opBlock.end(); ++Term) {
570 if (Term->readsRegister(SrcReg))
571 KillInst = Term;
572 }
573
574 if (KillInst == opBlock.end()) {
575 // No terminator uses the register.
576
577 if (reusedIncoming || !IncomingReg) {
578 // We may have to rewind a bit if we didn't just insert a copy.
579 KillInst = FirstTerm;
580 while (KillInst != opBlock.begin()) {
581 --KillInst;
582 if (KillInst->isDebugInstr())
583 continue;
584 if (KillInst->readsRegister(SrcReg))
585 break;
586 }
587 } else {
588 // We just inserted this copy.
589 KillInst = std::prev(InsertPos);
590 }
591 }
592 assert(KillInst->readsRegister(SrcReg) &&
593 "Cannot find kill instruction");
594
595 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
596 SrcLI.removeSegment(LastUseIndex.getRegSlot(),
597 LIS->getMBBEndIdx(&opBlock));
598 }
599 }
600 }
601 }
602
603 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.
604 if (reusedIncoming || !IncomingReg) {
605 if (LIS)
606 LIS->RemoveMachineInstrFromMaps(*MPhi);
607 MF.DeleteMachineInstr(MPhi);
608 }
609 }
610
611 /// analyzePHINodes - Gather information about the PHI nodes in here. In
612 /// particular, we want to map the number of uses of a virtual register which is
613 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
614 /// used later to determine when the vreg is killed in the BB.
analyzePHINodes(const MachineFunction & MF)615 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
616 for (const auto &MBB : MF)
617 for (const auto &BBI : MBB) {
618 if (!BBI.isPHI())
619 break;
620 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
621 ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
622 BBI.getOperand(i).getReg())];
623 }
624 }
625
SplitPHIEdges(MachineFunction & MF,MachineBasicBlock & MBB,MachineLoopInfo * MLI,std::vector<SparseBitVector<>> * LiveInSets)626 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
627 MachineBasicBlock &MBB,
628 MachineLoopInfo *MLI,
629 std::vector<SparseBitVector<>> *LiveInSets) {
630 if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())
631 return false; // Quick exit for basic blocks without PHIs.
632
633 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
634 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
635
636 bool Changed = false;
637 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
638 BBI != BBE && BBI->isPHI(); ++BBI) {
639 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
640 Register Reg = BBI->getOperand(i).getReg();
641 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
642 // Is there a critical edge from PreMBB to MBB?
643 if (PreMBB->succ_size() == 1)
644 continue;
645
646 // Avoid splitting backedges of loops. It would introduce small
647 // out-of-line blocks into the loop which is very bad for code placement.
648 if (PreMBB == &MBB && !SplitAllCriticalEdges)
649 continue;
650 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
651 if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)
652 continue;
653
654 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
655 // when the source register is live-out for some other reason than a phi
656 // use. That means the copy we will insert in PreMBB won't be a kill, and
657 // there is a risk it may not be coalesced away.
658 //
659 // If the copy would be a kill, there is no need to split the edge.
660 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);
661 if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)
662 continue;
663 if (ShouldSplit) {
664 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
665 << printMBBReference(*PreMBB) << " -> "
666 << printMBBReference(MBB) << ": " << *BBI);
667 }
668
669 // If Reg is not live-in to MBB, it means it must be live-in to some
670 // other PreMBB successor, and we can avoid the interference by splitting
671 // the edge.
672 //
673 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
674 // is likely to be left after coalescing. If we are looking at a loop
675 // exiting edge, split it so we won't insert code in the loop, otherwise
676 // don't bother.
677 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);
678
679 // Check for a loop exiting edge.
680 if (!ShouldSplit && CurLoop != PreLoop) {
681 LLVM_DEBUG({
682 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";
683 if (PreLoop)
684 dbgs() << "PreLoop: " << *PreLoop;
685 if (CurLoop)
686 dbgs() << "CurLoop: " << *CurLoop;
687 });
688 // This edge could be entering a loop, exiting a loop, or it could be
689 // both: Jumping directly form one loop to the header of a sibling
690 // loop.
691 // Split unless this edge is entering CurLoop from an outer loop.
692 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
693 }
694 if (!ShouldSplit && !SplitAllCriticalEdges)
695 continue;
696 if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) {
697 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");
698 continue;
699 }
700 Changed = true;
701 ++NumCriticalEdgesSplit;
702 }
703 }
704 return Changed;
705 }
706
isLiveIn(Register Reg,const MachineBasicBlock * MBB)707 bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {
708 assert((LV || LIS) &&
709 "isLiveIn() requires either LiveVariables or LiveIntervals");
710 if (LIS)
711 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
712 else
713 return LV->isLiveIn(Reg, *MBB);
714 }
715
isLiveOutPastPHIs(Register Reg,const MachineBasicBlock * MBB)716 bool PHIElimination::isLiveOutPastPHIs(Register Reg,
717 const MachineBasicBlock *MBB) {
718 assert((LV || LIS) &&
719 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");
720 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
721 // so that a register used only in a PHI is not live out of the block. In
722 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than
723 // in the predecessor basic block, so that a register used only in a PHI is live
724 // out of the block.
725 if (LIS) {
726 const LiveInterval &LI = LIS->getInterval(Reg);
727 for (const MachineBasicBlock *SI : MBB->successors())
728 if (LI.liveAt(LIS->getMBBStartIdx(SI)))
729 return true;
730 return false;
731 } else {
732 return LV->isLiveOut(Reg, *MBB);
733 }
734 }
735