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