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(Val: 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(Val: 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(Val: 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 | |
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) |
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 | |
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(new_size: 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(Reg: VirtReg); |
166 | if (!DefMI) |
167 | continue; |
168 | LiveVariables::VarInfo &VI = LV->getVarInfo(Reg: 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, LiveInSets: (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(i: 0).getReg(); |
203 | if (MRI->use_nodbg_empty(RegNo: DefReg)) { |
204 | if (LIS) |
205 | LIS->RemoveMachineInstrFromMaps(MI&: *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(MI&: *I.first); |
214 | MF.deleteMachineInstr(MI: 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(Func&: 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. |
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(x: MBB.SkipPHIsAndLabels(I: 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. |
250 | static bool isImplicitlyDefined(unsigned VirtReg, |
251 | const MachineRegisterInfo &MRI) { |
252 | for (MachineInstr &DI : MRI.def_instructions(Reg: 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. |
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: I); |
263 | if (!isImplicitlyDefined(VirtReg: 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. |
269 | void PHIElimination::LowerPHINode(MachineBasicBlock &MBB, |
270 | MachineBasicBlock::iterator LastPHIIt) { |
271 | ++NumLowered; |
272 | |
273 | MachineBasicBlock::iterator AfterPHIsIt = std::next(x: LastPHIIt); |
274 | |
275 | // Unlink the PHI node from the basic block, but don't delete the PHI yet. |
276 | MachineInstr *MPhi = MBB.remove(I: &*MBB.begin()); |
277 | |
278 | unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; |
279 | Register DestReg = MPhi->getOperand(i: 0).getReg(); |
280 | assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs" ); |
281 | bool isDead = MPhi->getOperand(i: 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: *MPhi, MRI: *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(BB&: MBB, I: AfterPHIsIt, MIMD: MPhi->getDebugLoc(), |
297 | MCID: TII->get(Opcode: 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(Reg: DestReg); |
311 | entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RegClass: RC); |
312 | } |
313 | // Give the target possiblity to handle special cases fallthrough otherwise |
314 | PHICopy = TII->createPHIDestinationCopy(MBB, InsPt: AfterPHIsIt, DL: MPhi->getDebugLoc(), |
315 | Src: IncomingReg, Dst: 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(KV: {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(Reg: IncomingReg); |
332 | |
333 | MachineInstr *OldKill = nullptr; |
334 | bool IsPHICopyAfterOldKill = false; |
335 | |
336 | if (reusedIncoming && (OldKill = VI.findKill(MBB: &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(I: 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(Reg: IncomingReg, MI&: *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, MI&: *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(MI&: *MPhi); |
376 | |
377 | // If the result is dead, update LV. |
378 | if (isDead) { |
379 | LV->addVirtualRegisterDead(IncomingReg: DestReg, MI&: *PHICopy); |
380 | LV->removeVirtualRegisterDead(Reg: DestReg, MI&: *MPhi); |
381 | } |
382 | } |
383 | |
384 | // Update LiveIntervals for the new copy or implicit def. |
385 | if (LIS) { |
386 | SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(MI&: *PHICopy); |
387 | |
388 | SlotIndex MBBStartIndex = LIS->getMBBStartIdx(mbb: &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(Reg: IncomingReg); |
393 | VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(Idx: MBBStartIndex); |
394 | if (!IncomingVNI) |
395 | IncomingVNI = IncomingLI.getNextValue(Def: MBBStartIndex, |
396 | VNInfoAllocator&: LIS->getVNInfoAllocator()); |
397 | IncomingLI.addSegment(S: LiveInterval::Segment(MBBStartIndex, |
398 | DestCopyIndex.getRegSlot(), |
399 | IncomingVNI)); |
400 | } |
401 | |
402 | LiveInterval &DestLI = LIS->getInterval(Reg: 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(Elt: &SR); |
410 | |
411 | for (auto LR : ToUpdate) { |
412 | auto DestSegment = LR->find(Pos: 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(Idx: DestSegment->start); |
421 | assert(OrigDestVNI && "PHI destination should be live at block entry." ); |
422 | LR->removeSegment(Start: DestSegment->start, End: DestSegment->start.getDeadSlot()); |
423 | LR->createDeadDef(Def: NewStart, VNIAlloc&: LIS->getVNInfoAllocator()); |
424 | LR->removeValNo(ValNo: 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(Idx: DestSegment->start); |
433 | assert(VNI && "value should be defined for known segment" ); |
434 | LR->addSegment( |
435 | S: 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(Start: DestSegment->start, End: NewStart); |
440 | } |
441 | VNInfo *DestVNI = LR->getVNInfoAt(Idx: 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: 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: i * 2 + 1).getReg(); |
461 | unsigned SrcSubReg = MPhi->getOperand(i: i*2+1).getSubReg(); |
462 | bool SrcUndef = MPhi->getOperand(i: i*2+1).isUndef() || |
463 | isImplicitlyDefined(VirtReg: SrcReg, MRI: *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: 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(Ptr: &opBlock).second) |
475 | continue; // If the copy has already been emitted, we're done. |
476 | |
477 | MachineInstr *SrcRegDef = MRI->getVRegDef(Reg: SrcReg); |
478 | if (SrcRegDef && TII->isUnspillableTerminator(MI: 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(i: 0).setReg(IncomingReg); |
487 | |
488 | // Update LiveVariables. |
489 | if (LV) { |
490 | LiveVariables::VarInfo &SrcVI = LV->getVarInfo(Reg: SrcReg); |
491 | LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(Reg: 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(MBB: &opBlock, SuccMBB: &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(BB&: opBlock, I: InsertPos, MIMD: MPhi->getDebugLoc(), |
512 | MCID: TII->get(Opcode: TargetOpcode::IMPLICIT_DEF), |
513 | DestReg: IncomingReg); |
514 | |
515 | // Clean up the old implicit-def, if there even was one. |
516 | if (MachineInstr *DefMI = MRI->getVRegDef(Reg: SrcReg)) |
517 | if (DefMI->isImplicitDef()) |
518 | ImpDefs.insert(Ptr: DefMI); |
519 | } else { |
520 | // Delete the debug location, since the copy is inserted into a |
521 | // different basic block. |
522 | NewSrcInstr = TII->createPHISourceCopy(MBB&: opBlock, InsPt: InsertPos, DL: nullptr, |
523 | Src: SrcReg, SrcSubReg, Dst: 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(Reg: SrcReg, MBB: 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(Reg: SrcReg, /*TRI=*/nullptr)) |
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(Reg: SrcReg, /*TRI=*/nullptr)) |
567 | break; |
568 | } |
569 | } else { |
570 | // We just inserted this copy. |
571 | KillInst = NewSrcInstr; |
572 | } |
573 | } |
574 | assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) && |
575 | "Cannot find kill instruction" ); |
576 | |
577 | // Finally, mark it killed. |
578 | LV->addVirtualRegisterKilled(IncomingReg: SrcReg, MI&: *KillInst); |
579 | |
580 | // This vreg no longer lives all of the way through opBlock. |
581 | unsigned opBlockNum = opBlock.getNumber(); |
582 | LV->getVarInfo(Reg: SrcReg).AliveBlocks.reset(Idx: opBlockNum); |
583 | } |
584 | |
585 | if (LIS) { |
586 | if (NewSrcInstr) { |
587 | LIS->InsertMachineInstrInMaps(MI&: *NewSrcInstr); |
588 | LIS->addSegmentToEndOfBlock(Reg: IncomingReg, startInst&: *NewSrcInstr); |
589 | } |
590 | |
591 | if (!SrcUndef && |
592 | !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) { |
593 | LiveInterval &SrcLI = LIS->getInterval(Reg: SrcReg); |
594 | |
595 | bool isLiveOut = false; |
596 | for (MachineBasicBlock *Succ : opBlock.successors()) { |
597 | SlotIndex startIdx = LIS->getMBBStartIdx(mbb: Succ); |
598 | VNInfo *VNI = SrcLI.getVNInfoAt(Idx: 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(Reg: 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(Reg: SrcReg, /*TRI=*/nullptr)) |
626 | break; |
627 | } |
628 | } else { |
629 | // We just inserted this copy. |
630 | KillInst = std::prev(x: InsertPos); |
631 | } |
632 | } |
633 | assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) && |
634 | "Cannot find kill instruction" ); |
635 | |
636 | SlotIndex LastUseIndex = LIS->getInstructionIndex(Instr: *KillInst); |
637 | SrcLI.removeSegment(Start: LastUseIndex.getRegSlot(), |
638 | End: LIS->getMBBEndIdx(mbb: &opBlock)); |
639 | for (auto &SR : SrcLI.subranges()) { |
640 | SR.removeSegment(Start: LastUseIndex.getRegSlot(), |
641 | End: LIS->getMBBEndIdx(mbb: &opBlock)); |
642 | } |
643 | } |
644 | } |
645 | } |
646 | } |
647 | |
648 | // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. |
649 | if (reusedIncoming || !IncomingReg) { |
650 | if (LIS) |
651 | LIS->RemoveMachineInstrFromMaps(MI&: *MPhi); |
652 | MF.deleteMachineInstr(MI: MPhi); |
653 | } |
654 | } |
655 | |
656 | /// analyzePHINodes - Gather information about the PHI nodes in here. In |
657 | /// particular, we want to map the number of uses of a virtual register which is |
658 | /// used in a PHI node. We map that to the BB the vreg is coming from. This is |
659 | /// used later to determine when the vreg is killed in the BB. |
660 | void PHIElimination::analyzePHINodes(const MachineFunction& MF) { |
661 | for (const auto &MBB : MF) { |
662 | for (const auto &BBI : MBB) { |
663 | if (!BBI.isPHI()) |
664 | break; |
665 | for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) { |
666 | if (!BBI.getOperand(i).isUndef()) { |
667 | ++VRegPHIUseCount[BBVRegPair( |
668 | BBI.getOperand(i: i + 1).getMBB()->getNumber(), |
669 | BBI.getOperand(i).getReg())]; |
670 | } |
671 | } |
672 | } |
673 | } |
674 | } |
675 | |
676 | bool PHIElimination::SplitPHIEdges(MachineFunction &MF, |
677 | MachineBasicBlock &MBB, |
678 | MachineLoopInfo *MLI, |
679 | std::vector<SparseBitVector<>> *LiveInSets) { |
680 | if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad()) |
681 | return false; // Quick exit for basic blocks without PHIs. |
682 | |
683 | const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(BB: &MBB) : nullptr; |
684 | bool = CurLoop && &MBB == CurLoop->getHeader(); |
685 | |
686 | bool Changed = false; |
687 | for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); |
688 | BBI != BBE && BBI->isPHI(); ++BBI) { |
689 | for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { |
690 | Register Reg = BBI->getOperand(i).getReg(); |
691 | MachineBasicBlock *PreMBB = BBI->getOperand(i: i+1).getMBB(); |
692 | // Is there a critical edge from PreMBB to MBB? |
693 | if (PreMBB->succ_size() == 1) |
694 | continue; |
695 | |
696 | // Avoid splitting backedges of loops. It would introduce small |
697 | // out-of-line blocks into the loop which is very bad for code placement. |
698 | if (PreMBB == &MBB && !SplitAllCriticalEdges) |
699 | continue; |
700 | const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(BB: PreMBB) : nullptr; |
701 | if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) |
702 | continue; |
703 | |
704 | // LV doesn't consider a phi use live-out, so isLiveOut only returns true |
705 | // when the source register is live-out for some other reason than a phi |
706 | // use. That means the copy we will insert in PreMBB won't be a kill, and |
707 | // there is a risk it may not be coalesced away. |
708 | // |
709 | // If the copy would be a kill, there is no need to split the edge. |
710 | bool ShouldSplit = isLiveOutPastPHIs(Reg, MBB: PreMBB); |
711 | if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit) |
712 | continue; |
713 | if (ShouldSplit) { |
714 | LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge " |
715 | << printMBBReference(*PreMBB) << " -> " |
716 | << printMBBReference(MBB) << ": " << *BBI); |
717 | } |
718 | |
719 | // If Reg is not live-in to MBB, it means it must be live-in to some |
720 | // other PreMBB successor, and we can avoid the interference by splitting |
721 | // the edge. |
722 | // |
723 | // If Reg *is* live-in to MBB, the interference is inevitable and a copy |
724 | // is likely to be left after coalescing. If we are looking at a loop |
725 | // exiting edge, split it so we won't insert code in the loop, otherwise |
726 | // don't bother. |
727 | ShouldSplit = ShouldSplit && !isLiveIn(Reg, MBB: &MBB); |
728 | |
729 | // Check for a loop exiting edge. |
730 | if (!ShouldSplit && CurLoop != PreLoop) { |
731 | LLVM_DEBUG({ |
732 | dbgs() << "Split wouldn't help, maybe avoid loop copies?\n" ; |
733 | if (PreLoop) |
734 | dbgs() << "PreLoop: " << *PreLoop; |
735 | if (CurLoop) |
736 | dbgs() << "CurLoop: " << *CurLoop; |
737 | }); |
738 | // This edge could be entering a loop, exiting a loop, or it could be |
739 | // both: Jumping directly form one loop to the header of a sibling |
740 | // loop. |
741 | // Split unless this edge is entering CurLoop from an outer loop. |
742 | ShouldSplit = PreLoop && !PreLoop->contains(L: CurLoop); |
743 | } |
744 | if (!ShouldSplit && !SplitAllCriticalEdges) |
745 | continue; |
746 | if (!PreMBB->SplitCriticalEdge(Succ: &MBB, P&: *this, LiveInSets)) { |
747 | LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n" ); |
748 | continue; |
749 | } |
750 | Changed = true; |
751 | ++NumCriticalEdgesSplit; |
752 | } |
753 | } |
754 | return Changed; |
755 | } |
756 | |
757 | bool PHIElimination::isLiveIn(Register Reg, const MachineBasicBlock *MBB) { |
758 | assert((LV || LIS) && |
759 | "isLiveIn() requires either LiveVariables or LiveIntervals" ); |
760 | if (LIS) |
761 | return LIS->isLiveInToMBB(LR: LIS->getInterval(Reg), mbb: MBB); |
762 | else |
763 | return LV->isLiveIn(Reg, MBB: *MBB); |
764 | } |
765 | |
766 | bool PHIElimination::isLiveOutPastPHIs(Register Reg, |
767 | const MachineBasicBlock *MBB) { |
768 | assert((LV || LIS) && |
769 | "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals" ); |
770 | // LiveVariables considers uses in PHIs to be in the predecessor basic block, |
771 | // so that a register used only in a PHI is not live out of the block. In |
772 | // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than |
773 | // in the predecessor basic block, so that a register used only in a PHI is live |
774 | // out of the block. |
775 | if (LIS) { |
776 | const LiveInterval &LI = LIS->getInterval(Reg); |
777 | for (const MachineBasicBlock *SI : MBB->successors()) |
778 | if (LI.liveAt(index: LIS->getMBBStartIdx(mbb: SI))) |
779 | return true; |
780 | return false; |
781 | } else { |
782 | return LV->isLiveOut(Reg, MBB: *MBB); |
783 | } |
784 | } |
785 | |