1 | //===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===// |
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 utility class duplicates basic blocks ending in unconditional branches |
10 | // into the tails of their predecessors. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #include "llvm/CodeGen/TailDuplicator.h" |
15 | #include "llvm/ADT/DenseMap.h" |
16 | #include "llvm/ADT/DenseSet.h" |
17 | #include "llvm/ADT/STLExtras.h" |
18 | #include "llvm/ADT/SetVector.h" |
19 | #include "llvm/ADT/SmallPtrSet.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/ADT/Statistic.h" |
22 | #include "llvm/CodeGen/MachineBasicBlock.h" |
23 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
24 | #include "llvm/CodeGen/MachineFunction.h" |
25 | #include "llvm/CodeGen/MachineInstr.h" |
26 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
27 | #include "llvm/CodeGen/MachineOperand.h" |
28 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
29 | #include "llvm/CodeGen/MachineSSAUpdater.h" |
30 | #include "llvm/CodeGen/MachineSizeOpts.h" |
31 | #include "llvm/CodeGen/TargetInstrInfo.h" |
32 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
33 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
34 | #include "llvm/IR/DebugLoc.h" |
35 | #include "llvm/IR/Function.h" |
36 | #include "llvm/Support/CommandLine.h" |
37 | #include "llvm/Support/Debug.h" |
38 | #include "llvm/Support/ErrorHandling.h" |
39 | #include "llvm/Support/raw_ostream.h" |
40 | #include "llvm/Target/TargetMachine.h" |
41 | #include <algorithm> |
42 | #include <cassert> |
43 | #include <iterator> |
44 | #include <utility> |
45 | |
46 | using namespace llvm; |
47 | |
48 | #define DEBUG_TYPE "tailduplication" |
49 | |
50 | STATISTIC(NumTails, "Number of tails duplicated" ); |
51 | STATISTIC(NumTailDups, "Number of tail duplicated blocks" ); |
52 | STATISTIC(NumTailDupAdded, |
53 | "Number of instructions added due to tail duplication" ); |
54 | STATISTIC(NumTailDupRemoved, |
55 | "Number of instructions removed due to tail duplication" ); |
56 | STATISTIC(NumDeadBlocks, "Number of dead blocks removed" ); |
57 | STATISTIC(NumAddedPHIs, "Number of phis added" ); |
58 | |
59 | // Heuristic for tail duplication. |
60 | static cl::opt<unsigned> TailDuplicateSize( |
61 | "tail-dup-size" , |
62 | cl::desc("Maximum instructions to consider tail duplicating" ), cl::init(Val: 2), |
63 | cl::Hidden); |
64 | |
65 | static cl::opt<unsigned> TailDupIndirectBranchSize( |
66 | "tail-dup-indirect-size" , |
67 | cl::desc("Maximum instructions to consider tail duplicating blocks that " |
68 | "end with indirect branches." ), cl::init(Val: 20), |
69 | cl::Hidden); |
70 | |
71 | static cl::opt<bool> |
72 | TailDupVerify("tail-dup-verify" , |
73 | cl::desc("Verify sanity of PHI instructions during taildup" ), |
74 | cl::init(Val: false), cl::Hidden); |
75 | |
76 | static cl::opt<unsigned> TailDupLimit("tail-dup-limit" , cl::init(Val: ~0U), |
77 | cl::Hidden); |
78 | |
79 | void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc, |
80 | const MachineBranchProbabilityInfo *MBPIin, |
81 | MBFIWrapper *MBFIin, |
82 | ProfileSummaryInfo *PSIin, |
83 | bool LayoutModeIn, unsigned TailDupSizeIn) { |
84 | MF = &MFin; |
85 | TII = MF->getSubtarget().getInstrInfo(); |
86 | TRI = MF->getSubtarget().getRegisterInfo(); |
87 | MRI = &MF->getRegInfo(); |
88 | MMI = &MF->getMMI(); |
89 | MBPI = MBPIin; |
90 | MBFI = MBFIin; |
91 | PSI = PSIin; |
92 | TailDupSize = TailDupSizeIn; |
93 | |
94 | assert(MBPI != nullptr && "Machine Branch Probability Info required" ); |
95 | |
96 | LayoutMode = LayoutModeIn; |
97 | this->PreRegAlloc = PreRegAlloc; |
98 | } |
99 | |
100 | static void VerifyPHIs(MachineFunction &MF, bool ) { |
101 | for (MachineBasicBlock &MBB : llvm::drop_begin(RangeOrContainer&: MF)) { |
102 | SmallSetVector<MachineBasicBlock *, 8> Preds(MBB.pred_begin(), |
103 | MBB.pred_end()); |
104 | MachineBasicBlock::iterator MI = MBB.begin(); |
105 | while (MI != MBB.end()) { |
106 | if (!MI->isPHI()) |
107 | break; |
108 | for (MachineBasicBlock *PredBB : Preds) { |
109 | bool Found = false; |
110 | for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { |
111 | MachineBasicBlock *PHIBB = MI->getOperand(i: i + 1).getMBB(); |
112 | if (PHIBB == PredBB) { |
113 | Found = true; |
114 | break; |
115 | } |
116 | } |
117 | if (!Found) { |
118 | dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": " |
119 | << *MI; |
120 | dbgs() << " missing input from predecessor " |
121 | << printMBBReference(MBB: *PredBB) << '\n'; |
122 | llvm_unreachable(nullptr); |
123 | } |
124 | } |
125 | |
126 | for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { |
127 | MachineBasicBlock *PHIBB = MI->getOperand(i: i + 1).getMBB(); |
128 | if (CheckExtra && !Preds.count(key: PHIBB)) { |
129 | dbgs() << "Warning: malformed PHI in " << printMBBReference(MBB) |
130 | << ": " << *MI; |
131 | dbgs() << " extra input from predecessor " |
132 | << printMBBReference(MBB: *PHIBB) << '\n'; |
133 | llvm_unreachable(nullptr); |
134 | } |
135 | if (PHIBB->getNumber() < 0) { |
136 | dbgs() << "Malformed PHI in " << printMBBReference(MBB) << ": " |
137 | << *MI; |
138 | dbgs() << " non-existing " << printMBBReference(MBB: *PHIBB) << '\n'; |
139 | llvm_unreachable(nullptr); |
140 | } |
141 | } |
142 | ++MI; |
143 | } |
144 | } |
145 | } |
146 | |
147 | /// Tail duplicate the block and cleanup. |
148 | /// \p IsSimple - return value of isSimpleBB |
149 | /// \p MBB - block to be duplicated |
150 | /// \p ForcedLayoutPred - If non-null, treat this block as the layout |
151 | /// predecessor, instead of using the ordering in MF |
152 | /// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of |
153 | /// all Preds that received a copy of \p MBB. |
154 | /// \p RemovalCallback - if non-null, called just before MBB is deleted. |
155 | bool TailDuplicator::tailDuplicateAndUpdate( |
156 | bool IsSimple, MachineBasicBlock *MBB, |
157 | MachineBasicBlock *ForcedLayoutPred, |
158 | SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds, |
159 | function_ref<void(MachineBasicBlock *)> *RemovalCallback, |
160 | SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { |
161 | // Save the successors list. |
162 | SmallSetVector<MachineBasicBlock *, 8> Succs(MBB->succ_begin(), |
163 | MBB->succ_end()); |
164 | |
165 | SmallVector<MachineBasicBlock *, 8> TDBBs; |
166 | SmallVector<MachineInstr *, 16> Copies; |
167 | if (!tailDuplicate(IsSimple, TailBB: MBB, ForcedLayoutPred, |
168 | TDBBs, Copies, CandidatePtr)) |
169 | return false; |
170 | |
171 | ++NumTails; |
172 | |
173 | SmallVector<MachineInstr *, 8> NewPHIs; |
174 | MachineSSAUpdater SSAUpdate(*MF, &NewPHIs); |
175 | |
176 | // TailBB's immediate successors are now successors of those predecessors |
177 | // which duplicated TailBB. Add the predecessors as sources to the PHI |
178 | // instructions. |
179 | bool isDead = MBB->pred_empty() && !MBB->hasAddressTaken(); |
180 | if (PreRegAlloc) |
181 | updateSuccessorsPHIs(FromBB: MBB, isDead, TDBBs, Succs); |
182 | |
183 | // If it is dead, remove it. |
184 | if (isDead) { |
185 | NumTailDupRemoved += MBB->size(); |
186 | removeDeadBlock(MBB, RemovalCallback); |
187 | ++NumDeadBlocks; |
188 | } |
189 | |
190 | // Update SSA form. |
191 | if (!SSAUpdateVRs.empty()) { |
192 | for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) { |
193 | unsigned VReg = SSAUpdateVRs[i]; |
194 | SSAUpdate.Initialize(V: VReg); |
195 | |
196 | // If the original definition is still around, add it as an available |
197 | // value. |
198 | MachineInstr *DefMI = MRI->getVRegDef(Reg: VReg); |
199 | MachineBasicBlock *DefBB = nullptr; |
200 | if (DefMI) { |
201 | DefBB = DefMI->getParent(); |
202 | SSAUpdate.AddAvailableValue(BB: DefBB, V: VReg); |
203 | } |
204 | |
205 | // Add the new vregs as available values. |
206 | DenseMap<Register, AvailableValsTy>::iterator LI = |
207 | SSAUpdateVals.find(Val: VReg); |
208 | for (std::pair<MachineBasicBlock *, Register> &J : LI->second) { |
209 | MachineBasicBlock *SrcBB = J.first; |
210 | Register SrcReg = J.second; |
211 | SSAUpdate.AddAvailableValue(BB: SrcBB, V: SrcReg); |
212 | } |
213 | |
214 | SmallVector<MachineOperand *> DebugUses; |
215 | // Rewrite uses that are outside of the original def's block. |
216 | for (MachineOperand &UseMO : |
217 | llvm::make_early_inc_range(Range: MRI->use_operands(Reg: VReg))) { |
218 | MachineInstr *UseMI = UseMO.getParent(); |
219 | // Rewrite debug uses last so that they can take advantage of any |
220 | // register mappings introduced by other users in its BB, since we |
221 | // cannot create new register definitions specifically for the debug |
222 | // instruction (as debug instructions should not affect CodeGen). |
223 | if (UseMI->isDebugValue()) { |
224 | DebugUses.push_back(Elt: &UseMO); |
225 | continue; |
226 | } |
227 | if (UseMI->getParent() == DefBB && !UseMI->isPHI()) |
228 | continue; |
229 | SSAUpdate.RewriteUse(U&: UseMO); |
230 | } |
231 | for (auto *UseMO : DebugUses) { |
232 | MachineInstr *UseMI = UseMO->getParent(); |
233 | UseMO->setReg( |
234 | SSAUpdate.GetValueInMiddleOfBlock(BB: UseMI->getParent(), ExistingValueOnly: true)); |
235 | } |
236 | } |
237 | |
238 | SSAUpdateVRs.clear(); |
239 | SSAUpdateVals.clear(); |
240 | } |
241 | |
242 | // Eliminate some of the copies inserted by tail duplication to maintain |
243 | // SSA form. |
244 | for (unsigned i = 0, e = Copies.size(); i != e; ++i) { |
245 | MachineInstr *Copy = Copies[i]; |
246 | if (!Copy->isCopy()) |
247 | continue; |
248 | Register Dst = Copy->getOperand(i: 0).getReg(); |
249 | Register Src = Copy->getOperand(i: 1).getReg(); |
250 | if (MRI->hasOneNonDBGUse(RegNo: Src) && |
251 | MRI->constrainRegClass(Reg: Src, RC: MRI->getRegClass(Reg: Dst))) { |
252 | // Copy is the only use. Do trivial copy propagation here. |
253 | MRI->replaceRegWith(FromReg: Dst, ToReg: Src); |
254 | Copy->eraseFromParent(); |
255 | } |
256 | } |
257 | |
258 | if (NewPHIs.size()) |
259 | NumAddedPHIs += NewPHIs.size(); |
260 | |
261 | if (DuplicatedPreds) |
262 | *DuplicatedPreds = std::move(TDBBs); |
263 | |
264 | return true; |
265 | } |
266 | |
267 | /// Look for small blocks that are unconditionally branched to and do not fall |
268 | /// through. Tail-duplicate their instructions into their predecessors to |
269 | /// eliminate (dynamic) branches. |
270 | bool TailDuplicator::tailDuplicateBlocks() { |
271 | bool MadeChange = false; |
272 | |
273 | if (PreRegAlloc && TailDupVerify) { |
274 | LLVM_DEBUG(dbgs() << "\n*** Before tail-duplicating\n" ); |
275 | VerifyPHIs(MF&: *MF, CheckExtra: true); |
276 | } |
277 | |
278 | for (MachineBasicBlock &MBB : |
279 | llvm::make_early_inc_range(Range: llvm::drop_begin(RangeOrContainer&: *MF))) { |
280 | if (NumTails == TailDupLimit) |
281 | break; |
282 | |
283 | bool IsSimple = isSimpleBB(TailBB: &MBB); |
284 | |
285 | if (!shouldTailDuplicate(IsSimple, TailBB&: MBB)) |
286 | continue; |
287 | |
288 | MadeChange |= tailDuplicateAndUpdate(IsSimple, MBB: &MBB, ForcedLayoutPred: nullptr); |
289 | } |
290 | |
291 | if (PreRegAlloc && TailDupVerify) |
292 | VerifyPHIs(MF&: *MF, CheckExtra: false); |
293 | |
294 | return MadeChange; |
295 | } |
296 | |
297 | static bool isDefLiveOut(Register Reg, MachineBasicBlock *BB, |
298 | const MachineRegisterInfo *MRI) { |
299 | for (MachineInstr &UseMI : MRI->use_instructions(Reg)) { |
300 | if (UseMI.isDebugValue()) |
301 | continue; |
302 | if (UseMI.getParent() != BB) |
303 | return true; |
304 | } |
305 | return false; |
306 | } |
307 | |
308 | static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { |
309 | for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) |
310 | if (MI->getOperand(i: i + 1).getMBB() == SrcBB) |
311 | return i; |
312 | return 0; |
313 | } |
314 | |
315 | // Remember which registers are used by phis in this block. This is |
316 | // used to determine which registers are liveout while modifying the |
317 | // block (which is why we need to copy the information). |
318 | static void getRegsUsedByPHIs(const MachineBasicBlock &BB, |
319 | DenseSet<Register> *UsedByPhi) { |
320 | for (const auto &MI : BB) { |
321 | if (!MI.isPHI()) |
322 | break; |
323 | for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { |
324 | Register SrcReg = MI.getOperand(i).getReg(); |
325 | UsedByPhi->insert(V: SrcReg); |
326 | } |
327 | } |
328 | } |
329 | |
330 | /// Add a definition and source virtual registers pair for SSA update. |
331 | void TailDuplicator::addSSAUpdateEntry(Register OrigReg, Register NewReg, |
332 | MachineBasicBlock *BB) { |
333 | DenseMap<Register, AvailableValsTy>::iterator LI = |
334 | SSAUpdateVals.find(Val: OrigReg); |
335 | if (LI != SSAUpdateVals.end()) |
336 | LI->second.push_back(x: std::make_pair(x&: BB, y&: NewReg)); |
337 | else { |
338 | AvailableValsTy Vals; |
339 | Vals.push_back(x: std::make_pair(x&: BB, y&: NewReg)); |
340 | SSAUpdateVals.insert(KV: std::make_pair(x&: OrigReg, y&: Vals)); |
341 | SSAUpdateVRs.push_back(Elt: OrigReg); |
342 | } |
343 | } |
344 | |
345 | /// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the |
346 | /// source register that's contributed by PredBB and update SSA update map. |
347 | void TailDuplicator::processPHI( |
348 | MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, |
349 | DenseMap<Register, RegSubRegPair> &LocalVRMap, |
350 | SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies, |
351 | const DenseSet<Register> &RegsUsedByPhi, bool Remove) { |
352 | Register DefReg = MI->getOperand(i: 0).getReg(); |
353 | unsigned SrcOpIdx = getPHISrcRegOpIdx(MI, SrcBB: PredBB); |
354 | assert(SrcOpIdx && "Unable to find matching PHI source?" ); |
355 | Register SrcReg = MI->getOperand(i: SrcOpIdx).getReg(); |
356 | unsigned SrcSubReg = MI->getOperand(i: SrcOpIdx).getSubReg(); |
357 | const TargetRegisterClass *RC = MRI->getRegClass(Reg: DefReg); |
358 | LocalVRMap.insert(KV: std::make_pair(x&: DefReg, y: RegSubRegPair(SrcReg, SrcSubReg))); |
359 | |
360 | // Insert a copy from source to the end of the block. The def register is the |
361 | // available value liveout of the block. |
362 | Register NewDef = MRI->createVirtualRegister(RegClass: RC); |
363 | Copies.push_back(Elt: std::make_pair(x&: NewDef, y: RegSubRegPair(SrcReg, SrcSubReg))); |
364 | if (isDefLiveOut(Reg: DefReg, BB: TailBB, MRI) || RegsUsedByPhi.count(V: DefReg)) |
365 | addSSAUpdateEntry(OrigReg: DefReg, NewReg: NewDef, BB: PredBB); |
366 | |
367 | if (!Remove) |
368 | return; |
369 | |
370 | // Remove PredBB from the PHI node. |
371 | MI->removeOperand(OpNo: SrcOpIdx + 1); |
372 | MI->removeOperand(OpNo: SrcOpIdx); |
373 | if (MI->getNumOperands() == 1 && !TailBB->hasAddressTaken()) |
374 | MI->eraseFromParent(); |
375 | else if (MI->getNumOperands() == 1) |
376 | MI->setDesc(TII->get(Opcode: TargetOpcode::IMPLICIT_DEF)); |
377 | } |
378 | |
379 | /// Duplicate a TailBB instruction to PredBB and update |
380 | /// the source operands due to earlier PHI translation. |
381 | void TailDuplicator::duplicateInstruction( |
382 | MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB, |
383 | DenseMap<Register, RegSubRegPair> &LocalVRMap, |
384 | const DenseSet<Register> &UsedByPhi) { |
385 | // Allow duplication of CFI instructions. |
386 | if (MI->isCFIInstruction()) { |
387 | BuildMI(BB&: *PredBB, I: PredBB->end(), MIMD: PredBB->findDebugLoc(MBBI: PredBB->begin()), |
388 | MCID: TII->get(Opcode: TargetOpcode::CFI_INSTRUCTION)) |
389 | .addCFIIndex(CFIIndex: MI->getOperand(i: 0).getCFIIndex()) |
390 | .setMIFlags(MI->getFlags()); |
391 | return; |
392 | } |
393 | MachineInstr &NewMI = TII->duplicate(MBB&: *PredBB, InsertBefore: PredBB->end(), Orig: *MI); |
394 | if (PreRegAlloc) { |
395 | for (unsigned i = 0, e = NewMI.getNumOperands(); i != e; ++i) { |
396 | MachineOperand &MO = NewMI.getOperand(i); |
397 | if (!MO.isReg()) |
398 | continue; |
399 | Register Reg = MO.getReg(); |
400 | if (!Reg.isVirtual()) |
401 | continue; |
402 | if (MO.isDef()) { |
403 | const TargetRegisterClass *RC = MRI->getRegClass(Reg); |
404 | Register NewReg = MRI->createVirtualRegister(RegClass: RC); |
405 | MO.setReg(NewReg); |
406 | LocalVRMap.insert(KV: std::make_pair(x&: Reg, y: RegSubRegPair(NewReg, 0))); |
407 | if (isDefLiveOut(Reg, BB: TailBB, MRI) || UsedByPhi.count(V: Reg)) |
408 | addSSAUpdateEntry(OrigReg: Reg, NewReg, BB: PredBB); |
409 | } else { |
410 | auto VI = LocalVRMap.find(Val: Reg); |
411 | if (VI != LocalVRMap.end()) { |
412 | // Need to make sure that the register class of the mapped register |
413 | // will satisfy the constraints of the class of the register being |
414 | // replaced. |
415 | auto *OrigRC = MRI->getRegClass(Reg); |
416 | auto *MappedRC = MRI->getRegClass(Reg: VI->second.Reg); |
417 | const TargetRegisterClass *ConstrRC; |
418 | if (VI->second.SubReg != 0) { |
419 | ConstrRC = TRI->getMatchingSuperRegClass(A: MappedRC, B: OrigRC, |
420 | Idx: VI->second.SubReg); |
421 | if (ConstrRC) { |
422 | // The actual constraining (as in "find appropriate new class") |
423 | // is done by getMatchingSuperRegClass, so now we only need to |
424 | // change the class of the mapped register. |
425 | MRI->setRegClass(Reg: VI->second.Reg, RC: ConstrRC); |
426 | } |
427 | } else { |
428 | // For mapped registers that do not have sub-registers, simply |
429 | // restrict their class to match the original one. |
430 | |
431 | // We don't want debug instructions affecting the resulting code so |
432 | // if we're cloning a debug instruction then just use MappedRC |
433 | // rather than constraining the register class further. |
434 | ConstrRC = NewMI.isDebugInstr() |
435 | ? MappedRC |
436 | : MRI->constrainRegClass(Reg: VI->second.Reg, RC: OrigRC); |
437 | } |
438 | |
439 | if (ConstrRC) { |
440 | // If the class constraining succeeded, we can simply replace |
441 | // the old register with the mapped one. |
442 | MO.setReg(VI->second.Reg); |
443 | // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a |
444 | // sub-register, we need to compose the sub-register indices. |
445 | MO.setSubReg( |
446 | TRI->composeSubRegIndices(a: VI->second.SubReg, b: MO.getSubReg())); |
447 | } else { |
448 | // The direct replacement is not possible, due to failing register |
449 | // class constraints. An explicit COPY is necessary. Create one |
450 | // that can be reused. |
451 | Register NewReg = MRI->createVirtualRegister(RegClass: OrigRC); |
452 | BuildMI(BB&: *PredBB, I&: NewMI, MIMD: NewMI.getDebugLoc(), |
453 | MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: NewReg) |
454 | .addReg(RegNo: VI->second.Reg, flags: 0, SubReg: VI->second.SubReg); |
455 | LocalVRMap.erase(I: VI); |
456 | LocalVRMap.insert(KV: std::make_pair(x&: Reg, y: RegSubRegPair(NewReg, 0))); |
457 | MO.setReg(NewReg); |
458 | // The composed VI.Reg:VI.SubReg is replaced with NewReg, which |
459 | // is equivalent to the whole register Reg. Hence, Reg:subreg |
460 | // is same as NewReg:subreg, so keep the sub-register index |
461 | // unchanged. |
462 | } |
463 | // Clear any kill flags from this operand. The new register could |
464 | // have uses after this one, so kills are not valid here. |
465 | MO.setIsKill(false); |
466 | } |
467 | } |
468 | } |
469 | } |
470 | } |
471 | |
472 | /// After FromBB is tail duplicated into its predecessor blocks, the successors |
473 | /// have gained new predecessors. Update the PHI instructions in them |
474 | /// accordingly. |
475 | void TailDuplicator::updateSuccessorsPHIs( |
476 | MachineBasicBlock *FromBB, bool isDead, |
477 | SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
478 | SmallSetVector<MachineBasicBlock *, 8> &Succs) { |
479 | for (MachineBasicBlock *SuccBB : Succs) { |
480 | for (MachineInstr &MI : *SuccBB) { |
481 | if (!MI.isPHI()) |
482 | break; |
483 | MachineInstrBuilder MIB(*FromBB->getParent(), MI); |
484 | unsigned Idx = 0; |
485 | for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) { |
486 | MachineOperand &MO = MI.getOperand(i: i + 1); |
487 | if (MO.getMBB() == FromBB) { |
488 | Idx = i; |
489 | break; |
490 | } |
491 | } |
492 | |
493 | assert(Idx != 0); |
494 | MachineOperand &MO0 = MI.getOperand(i: Idx); |
495 | Register Reg = MO0.getReg(); |
496 | if (isDead) { |
497 | // Folded into the previous BB. |
498 | // There could be duplicate phi source entries. FIXME: Should sdisel |
499 | // or earlier pass fixed this? |
500 | for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) { |
501 | MachineOperand &MO = MI.getOperand(i: i + 1); |
502 | if (MO.getMBB() == FromBB) { |
503 | MI.removeOperand(OpNo: i + 1); |
504 | MI.removeOperand(OpNo: i); |
505 | } |
506 | } |
507 | } else |
508 | Idx = 0; |
509 | |
510 | // If Idx is set, the operands at Idx and Idx+1 must be removed. |
511 | // We reuse the location to avoid expensive removeOperand calls. |
512 | |
513 | DenseMap<Register, AvailableValsTy>::iterator LI = |
514 | SSAUpdateVals.find(Val: Reg); |
515 | if (LI != SSAUpdateVals.end()) { |
516 | // This register is defined in the tail block. |
517 | for (const std::pair<MachineBasicBlock *, Register> &J : LI->second) { |
518 | MachineBasicBlock *SrcBB = J.first; |
519 | // If we didn't duplicate a bb into a particular predecessor, we |
520 | // might still have added an entry to SSAUpdateVals to correcly |
521 | // recompute SSA. If that case, avoid adding a dummy extra argument |
522 | // this PHI. |
523 | if (!SrcBB->isSuccessor(MBB: SuccBB)) |
524 | continue; |
525 | |
526 | Register SrcReg = J.second; |
527 | if (Idx != 0) { |
528 | MI.getOperand(i: Idx).setReg(SrcReg); |
529 | MI.getOperand(i: Idx + 1).setMBB(SrcBB); |
530 | Idx = 0; |
531 | } else { |
532 | MIB.addReg(RegNo: SrcReg).addMBB(MBB: SrcBB); |
533 | } |
534 | } |
535 | } else { |
536 | // Live in tail block, must also be live in predecessors. |
537 | for (MachineBasicBlock *SrcBB : TDBBs) { |
538 | if (Idx != 0) { |
539 | MI.getOperand(i: Idx).setReg(Reg); |
540 | MI.getOperand(i: Idx + 1).setMBB(SrcBB); |
541 | Idx = 0; |
542 | } else { |
543 | MIB.addReg(RegNo: Reg).addMBB(MBB: SrcBB); |
544 | } |
545 | } |
546 | } |
547 | if (Idx != 0) { |
548 | MI.removeOperand(OpNo: Idx + 1); |
549 | MI.removeOperand(OpNo: Idx); |
550 | } |
551 | } |
552 | } |
553 | } |
554 | |
555 | /// Determine if it is profitable to duplicate this block. |
556 | bool TailDuplicator::shouldTailDuplicate(bool IsSimple, |
557 | MachineBasicBlock &TailBB) { |
558 | // When doing tail-duplication during layout, the block ordering is in flux, |
559 | // so canFallThrough returns a result based on incorrect information and |
560 | // should just be ignored. |
561 | if (!LayoutMode && TailBB.canFallThrough()) |
562 | return false; |
563 | |
564 | // Don't try to tail-duplicate single-block loops. |
565 | if (TailBB.isSuccessor(MBB: &TailBB)) |
566 | return false; |
567 | |
568 | // Set the limit on the cost to duplicate. When optimizing for size, |
569 | // duplicate only one, because one branch instruction can be eliminated to |
570 | // compensate for the duplication. |
571 | unsigned MaxDuplicateCount; |
572 | bool OptForSize = MF->getFunction().hasOptSize() || |
573 | llvm::shouldOptimizeForSize(MBB: &TailBB, PSI, MBFIWrapper: MBFI); |
574 | if (TailDupSize == 0) |
575 | MaxDuplicateCount = TailDuplicateSize; |
576 | else |
577 | MaxDuplicateCount = TailDupSize; |
578 | if (OptForSize) |
579 | MaxDuplicateCount = 1; |
580 | |
581 | // If the block to be duplicated ends in an unanalyzable fallthrough, don't |
582 | // duplicate it. |
583 | // A similar check is necessary in MachineBlockPlacement to make sure pairs of |
584 | // blocks with unanalyzable fallthrough get layed out contiguously. |
585 | MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; |
586 | SmallVector<MachineOperand, 4> PredCond; |
587 | if (TII->analyzeBranch(MBB&: TailBB, TBB&: PredTBB, FBB&: PredFBB, Cond&: PredCond) && |
588 | TailBB.canFallThrough()) |
589 | return false; |
590 | |
591 | // If the target has hardware branch prediction that can handle indirect |
592 | // branches, duplicating them can often make them predictable when there |
593 | // are common paths through the code. The limit needs to be high enough |
594 | // to allow undoing the effects of tail merging and other optimizations |
595 | // that rearrange the predecessors of the indirect branch. |
596 | |
597 | bool HasIndirectbr = false; |
598 | if (!TailBB.empty()) |
599 | HasIndirectbr = TailBB.back().isIndirectBranch(); |
600 | |
601 | if (HasIndirectbr && PreRegAlloc) |
602 | MaxDuplicateCount = TailDupIndirectBranchSize; |
603 | |
604 | // Check the instructions in the block to determine whether tail-duplication |
605 | // is invalid or unlikely to be profitable. |
606 | unsigned InstrCount = 0; |
607 | for (MachineInstr &MI : TailBB) { |
608 | // Non-duplicable things shouldn't be tail-duplicated. |
609 | // CFI instructions are marked as non-duplicable, because Darwin compact |
610 | // unwind info emission can't handle multiple prologue setups. In case of |
611 | // DWARF, allow them be duplicated, so that their existence doesn't prevent |
612 | // tail duplication of some basic blocks, that would be duplicated otherwise. |
613 | if (MI.isNotDuplicable() && |
614 | (TailBB.getParent()->getTarget().getTargetTriple().isOSDarwin() || |
615 | !MI.isCFIInstruction())) |
616 | return false; |
617 | |
618 | // Convergent instructions can be duplicated only if doing so doesn't add |
619 | // new control dependencies, which is what we're going to do here. |
620 | if (MI.isConvergent()) |
621 | return false; |
622 | |
623 | // Do not duplicate 'return' instructions if this is a pre-regalloc run. |
624 | // A return may expand into a lot more instructions (e.g. reload of callee |
625 | // saved registers) after PEI. |
626 | if (PreRegAlloc && MI.isReturn()) |
627 | return false; |
628 | |
629 | // Avoid duplicating calls before register allocation. Calls presents a |
630 | // barrier to register allocation so duplicating them may end up increasing |
631 | // spills. |
632 | if (PreRegAlloc && MI.isCall()) |
633 | return false; |
634 | |
635 | // TailDuplicator::appendCopies will erroneously place COPYs after |
636 | // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same |
637 | // bug that was fixed in f7a53d82c090. |
638 | // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point |
639 | // for the COPY when replacing PHIs. |
640 | if (MI.getOpcode() == TargetOpcode::INLINEASM_BR) |
641 | return false; |
642 | |
643 | if (MI.isBundle()) |
644 | InstrCount += MI.getBundleSize(); |
645 | else if (!MI.isPHI() && !MI.isMetaInstruction()) |
646 | InstrCount += 1; |
647 | |
648 | if (InstrCount > MaxDuplicateCount) |
649 | return false; |
650 | } |
651 | |
652 | // Check if any of the successors of TailBB has a PHI node in which the |
653 | // value corresponding to TailBB uses a subregister. |
654 | // If a phi node uses a register paired with a subregister, the actual |
655 | // "value type" of the phi may differ from the type of the register without |
656 | // any subregisters. Due to a bug, tail duplication may add a new operand |
657 | // without a necessary subregister, producing an invalid code. This is |
658 | // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll. |
659 | // Disable tail duplication for this case for now, until the problem is |
660 | // fixed. |
661 | for (auto *SB : TailBB.successors()) { |
662 | for (auto &I : *SB) { |
663 | if (!I.isPHI()) |
664 | break; |
665 | unsigned Idx = getPHISrcRegOpIdx(MI: &I, SrcBB: &TailBB); |
666 | assert(Idx != 0); |
667 | MachineOperand &PU = I.getOperand(i: Idx); |
668 | if (PU.getSubReg() != 0) |
669 | return false; |
670 | } |
671 | } |
672 | |
673 | if (HasIndirectbr && PreRegAlloc) |
674 | return true; |
675 | |
676 | if (IsSimple) |
677 | return true; |
678 | |
679 | if (!PreRegAlloc) |
680 | return true; |
681 | |
682 | return canCompletelyDuplicateBB(BB&: TailBB); |
683 | } |
684 | |
685 | /// True if this BB has only one unconditional jump. |
686 | bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { |
687 | if (TailBB->succ_size() != 1) |
688 | return false; |
689 | if (TailBB->pred_empty()) |
690 | return false; |
691 | MachineBasicBlock::iterator I = TailBB->getFirstNonDebugInstr(SkipPseudoOp: true); |
692 | if (I == TailBB->end()) |
693 | return true; |
694 | return I->isUnconditionalBranch(); |
695 | } |
696 | |
697 | static bool bothUsedInPHI(const MachineBasicBlock &A, |
698 | const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) { |
699 | for (MachineBasicBlock *BB : A.successors()) |
700 | if (SuccsB.count(Ptr: BB) && !BB->empty() && BB->begin()->isPHI()) |
701 | return true; |
702 | |
703 | return false; |
704 | } |
705 | |
706 | bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { |
707 | for (MachineBasicBlock *PredBB : BB.predecessors()) { |
708 | if (PredBB->succ_size() > 1) |
709 | return false; |
710 | |
711 | MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; |
712 | SmallVector<MachineOperand, 4> PredCond; |
713 | if (TII->analyzeBranch(MBB&: *PredBB, TBB&: PredTBB, FBB&: PredFBB, Cond&: PredCond)) |
714 | return false; |
715 | |
716 | if (!PredCond.empty()) |
717 | return false; |
718 | } |
719 | return true; |
720 | } |
721 | |
722 | bool TailDuplicator::duplicateSimpleBB( |
723 | MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
724 | const DenseSet<Register> &UsedByPhi) { |
725 | SmallPtrSet<MachineBasicBlock *, 8> Succs(TailBB->succ_begin(), |
726 | TailBB->succ_end()); |
727 | SmallVector<MachineBasicBlock *, 8> Preds(TailBB->predecessors()); |
728 | bool Changed = false; |
729 | for (MachineBasicBlock *PredBB : Preds) { |
730 | if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr()) |
731 | continue; |
732 | |
733 | if (bothUsedInPHI(A: *PredBB, SuccsB: Succs)) |
734 | continue; |
735 | |
736 | MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; |
737 | SmallVector<MachineOperand, 4> PredCond; |
738 | if (TII->analyzeBranch(MBB&: *PredBB, TBB&: PredTBB, FBB&: PredFBB, Cond&: PredCond)) |
739 | continue; |
740 | |
741 | Changed = true; |
742 | LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB |
743 | << "From simple Succ: " << *TailBB); |
744 | |
745 | MachineBasicBlock *NewTarget = *TailBB->succ_begin(); |
746 | MachineBasicBlock *NextBB = PredBB->getNextNode(); |
747 | |
748 | // Make PredFBB explicit. |
749 | if (PredCond.empty()) |
750 | PredFBB = PredTBB; |
751 | |
752 | // Make fall through explicit. |
753 | if (!PredTBB) |
754 | PredTBB = NextBB; |
755 | if (!PredFBB) |
756 | PredFBB = NextBB; |
757 | |
758 | // Redirect |
759 | if (PredFBB == TailBB) |
760 | PredFBB = NewTarget; |
761 | if (PredTBB == TailBB) |
762 | PredTBB = NewTarget; |
763 | |
764 | // Make the branch unconditional if possible |
765 | if (PredTBB == PredFBB) { |
766 | PredCond.clear(); |
767 | PredFBB = nullptr; |
768 | } |
769 | |
770 | // Avoid adding fall through branches. |
771 | if (PredFBB == NextBB) |
772 | PredFBB = nullptr; |
773 | if (PredTBB == NextBB && PredFBB == nullptr) |
774 | PredTBB = nullptr; |
775 | |
776 | auto DL = PredBB->findBranchDebugLoc(); |
777 | TII->removeBranch(MBB&: *PredBB); |
778 | |
779 | if (!PredBB->isSuccessor(MBB: NewTarget)) |
780 | PredBB->replaceSuccessor(Old: TailBB, New: NewTarget); |
781 | else { |
782 | PredBB->removeSuccessor(Succ: TailBB, NormalizeSuccProbs: true); |
783 | assert(PredBB->succ_size() <= 1); |
784 | } |
785 | |
786 | if (PredTBB) |
787 | TII->insertBranch(MBB&: *PredBB, TBB: PredTBB, FBB: PredFBB, Cond: PredCond, DL); |
788 | |
789 | TDBBs.push_back(Elt: PredBB); |
790 | } |
791 | return Changed; |
792 | } |
793 | |
794 | bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB, |
795 | MachineBasicBlock *PredBB) { |
796 | // EH edges are ignored by analyzeBranch. |
797 | if (PredBB->succ_size() > 1) |
798 | return false; |
799 | |
800 | MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr; |
801 | SmallVector<MachineOperand, 4> PredCond; |
802 | if (TII->analyzeBranch(MBB&: *PredBB, TBB&: PredTBB, FBB&: PredFBB, Cond&: PredCond)) |
803 | return false; |
804 | if (!PredCond.empty()) |
805 | return false; |
806 | // FIXME: This is overly conservative; it may be ok to relax this in the |
807 | // future under more specific conditions. If TailBB is an INLINEASM_BR |
808 | // indirect target, we need to see if the edge from PredBB to TailBB is from |
809 | // an INLINEASM_BR in PredBB, and then also if that edge was from the |
810 | // indirect target list, fallthrough/default target, or potentially both. If |
811 | // it's both, TailDuplicator::tailDuplicate will remove the edge, corrupting |
812 | // the successor list in PredBB and predecessor list in TailBB. |
813 | if (TailBB->isInlineAsmBrIndirectTarget()) |
814 | return false; |
815 | return true; |
816 | } |
817 | |
818 | /// If it is profitable, duplicate TailBB's contents in each |
819 | /// of its predecessors. |
820 | /// \p IsSimple result of isSimpleBB |
821 | /// \p TailBB Block to be duplicated. |
822 | /// \p ForcedLayoutPred When non-null, use this block as the layout predecessor |
823 | /// instead of the previous block in MF's order. |
824 | /// \p TDBBs A vector to keep track of all blocks tail-duplicated |
825 | /// into. |
826 | /// \p Copies A vector of copy instructions inserted. Used later to |
827 | /// walk all the inserted copies and remove redundant ones. |
828 | bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB, |
829 | MachineBasicBlock *ForcedLayoutPred, |
830 | SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
831 | SmallVectorImpl<MachineInstr *> &Copies, |
832 | SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { |
833 | LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB) |
834 | << '\n'); |
835 | |
836 | bool ShouldUpdateTerminators = TailBB->canFallThrough(); |
837 | |
838 | DenseSet<Register> UsedByPhi; |
839 | getRegsUsedByPHIs(BB: *TailBB, UsedByPhi: &UsedByPhi); |
840 | |
841 | if (IsSimple) |
842 | return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi); |
843 | |
844 | // Iterate through all the unique predecessors and tail-duplicate this |
845 | // block into them, if possible. Copying the list ahead of time also |
846 | // avoids trouble with the predecessor list reallocating. |
847 | bool Changed = false; |
848 | SmallSetVector<MachineBasicBlock *, 8> Preds; |
849 | if (CandidatePtr) |
850 | Preds.insert(Start: CandidatePtr->begin(), End: CandidatePtr->end()); |
851 | else |
852 | Preds.insert(Start: TailBB->pred_begin(), End: TailBB->pred_end()); |
853 | |
854 | for (MachineBasicBlock *PredBB : Preds) { |
855 | assert(TailBB != PredBB && |
856 | "Single-block loop should have been rejected earlier!" ); |
857 | |
858 | if (!canTailDuplicate(TailBB, PredBB)) |
859 | continue; |
860 | |
861 | // Don't duplicate into a fall-through predecessor (at least for now). |
862 | // If profile is available, findDuplicateCandidates can choose better |
863 | // fall-through predecessor. |
864 | if (!(MF->getFunction().hasProfileData() && LayoutMode)) { |
865 | bool IsLayoutSuccessor = false; |
866 | if (ForcedLayoutPred) |
867 | IsLayoutSuccessor = (ForcedLayoutPred == PredBB); |
868 | else if (PredBB->isLayoutSuccessor(MBB: TailBB) && PredBB->canFallThrough()) |
869 | IsLayoutSuccessor = true; |
870 | if (IsLayoutSuccessor) |
871 | continue; |
872 | } |
873 | |
874 | LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB |
875 | << "From Succ: " << *TailBB); |
876 | |
877 | TDBBs.push_back(Elt: PredBB); |
878 | |
879 | // Remove PredBB's unconditional branch. |
880 | TII->removeBranch(MBB&: *PredBB); |
881 | |
882 | // Clone the contents of TailBB into PredBB. |
883 | DenseMap<Register, RegSubRegPair> LocalVRMap; |
884 | SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; |
885 | for (MachineInstr &MI : llvm::make_early_inc_range(Range&: *TailBB)) { |
886 | if (MI.isPHI()) { |
887 | // Replace the uses of the def of the PHI with the register coming |
888 | // from PredBB. |
889 | processPHI(MI: &MI, TailBB, PredBB, LocalVRMap, Copies&: CopyInfos, RegsUsedByPhi: UsedByPhi, Remove: true); |
890 | } else { |
891 | // Replace def of virtual registers with new registers, and update |
892 | // uses with PHI source register or the new registers. |
893 | duplicateInstruction(MI: &MI, TailBB, PredBB, LocalVRMap, UsedByPhi); |
894 | } |
895 | } |
896 | appendCopies(MBB: PredBB, CopyInfos, Copies); |
897 | |
898 | NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch |
899 | |
900 | // Update the CFG. |
901 | PredBB->removeSuccessor(I: PredBB->succ_begin()); |
902 | assert(PredBB->succ_empty() && |
903 | "TailDuplicate called on block with multiple successors!" ); |
904 | for (MachineBasicBlock *Succ : TailBB->successors()) |
905 | PredBB->addSuccessor(Succ, Prob: MBPI->getEdgeProbability(Src: TailBB, Dst: Succ)); |
906 | |
907 | // Update branches in pred to jump to tail's layout successor if needed. |
908 | if (ShouldUpdateTerminators) |
909 | PredBB->updateTerminator(PreviousLayoutSuccessor: TailBB->getNextNode()); |
910 | |
911 | Changed = true; |
912 | ++NumTailDups; |
913 | } |
914 | |
915 | // If TailBB was duplicated into all its predecessors except for the prior |
916 | // block, which falls through unconditionally, move the contents of this |
917 | // block into the prior block. |
918 | MachineBasicBlock *PrevBB = ForcedLayoutPred; |
919 | if (!PrevBB) |
920 | PrevBB = &*std::prev(x: TailBB->getIterator()); |
921 | MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr; |
922 | SmallVector<MachineOperand, 4> PriorCond; |
923 | // This has to check PrevBB->succ_size() because EH edges are ignored by |
924 | // analyzeBranch. |
925 | if (PrevBB->succ_size() == 1 && |
926 | // Layout preds are not always CFG preds. Check. |
927 | *PrevBB->succ_begin() == TailBB && |
928 | !TII->analyzeBranch(MBB&: *PrevBB, TBB&: PriorTBB, FBB&: PriorFBB, Cond&: PriorCond) && |
929 | PriorCond.empty() && |
930 | (!PriorTBB || PriorTBB == TailBB) && |
931 | TailBB->pred_size() == 1 && |
932 | !TailBB->hasAddressTaken()) { |
933 | LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB |
934 | << "From MBB: " << *TailBB); |
935 | // There may be a branch to the layout successor. This is unlikely but it |
936 | // happens. The correct thing to do is to remove the branch before |
937 | // duplicating the instructions in all cases. |
938 | bool RemovedBranches = TII->removeBranch(MBB&: *PrevBB) != 0; |
939 | |
940 | // If there are still tail instructions, abort the merge |
941 | if (PrevBB->getFirstTerminator() == PrevBB->end()) { |
942 | if (PreRegAlloc) { |
943 | DenseMap<Register, RegSubRegPair> LocalVRMap; |
944 | SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; |
945 | MachineBasicBlock::iterator I = TailBB->begin(); |
946 | // Process PHI instructions first. |
947 | while (I != TailBB->end() && I->isPHI()) { |
948 | // Replace the uses of the def of the PHI with the register coming |
949 | // from PredBB. |
950 | MachineInstr *MI = &*I++; |
951 | processPHI(MI, TailBB, PredBB: PrevBB, LocalVRMap, Copies&: CopyInfos, RegsUsedByPhi: UsedByPhi, |
952 | Remove: true); |
953 | } |
954 | |
955 | // Now copy the non-PHI instructions. |
956 | while (I != TailBB->end()) { |
957 | // Replace def of virtual registers with new registers, and update |
958 | // uses with PHI source register or the new registers. |
959 | MachineInstr *MI = &*I++; |
960 | assert(!MI->isBundle() && "Not expecting bundles before regalloc!" ); |
961 | duplicateInstruction(MI, TailBB, PredBB: PrevBB, LocalVRMap, UsedByPhi); |
962 | MI->eraseFromParent(); |
963 | } |
964 | appendCopies(MBB: PrevBB, CopyInfos, Copies); |
965 | } else { |
966 | TII->removeBranch(MBB&: *PrevBB); |
967 | // No PHIs to worry about, just splice the instructions over. |
968 | PrevBB->splice(Where: PrevBB->end(), Other: TailBB, From: TailBB->begin(), To: TailBB->end()); |
969 | } |
970 | PrevBB->removeSuccessor(I: PrevBB->succ_begin()); |
971 | assert(PrevBB->succ_empty()); |
972 | PrevBB->transferSuccessors(FromMBB: TailBB); |
973 | |
974 | // Update branches in PrevBB based on Tail's layout successor. |
975 | if (ShouldUpdateTerminators) |
976 | PrevBB->updateTerminator(PreviousLayoutSuccessor: TailBB->getNextNode()); |
977 | |
978 | TDBBs.push_back(Elt: PrevBB); |
979 | Changed = true; |
980 | } else { |
981 | LLVM_DEBUG(dbgs() << "Abort merging blocks, the predecessor still " |
982 | "contains terminator instructions" ); |
983 | // Return early if no changes were made |
984 | if (!Changed) |
985 | return RemovedBranches; |
986 | } |
987 | Changed |= RemovedBranches; |
988 | } |
989 | |
990 | // If this is after register allocation, there are no phis to fix. |
991 | if (!PreRegAlloc) |
992 | return Changed; |
993 | |
994 | // If we made no changes so far, we are safe. |
995 | if (!Changed) |
996 | return Changed; |
997 | |
998 | // Handle the nasty case in that we duplicated a block that is part of a loop |
999 | // into some but not all of its predecessors. For example: |
1000 | // 1 -> 2 <-> 3 | |
1001 | // \ | |
1002 | // \---> rest | |
1003 | // if we duplicate 2 into 1 but not into 3, we end up with |
1004 | // 12 -> 3 <-> 2 -> rest | |
1005 | // \ / | |
1006 | // \----->-----/ | |
1007 | // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced |
1008 | // with a phi in 3 (which now dominates 2). |
1009 | // What we do here is introduce a copy in 3 of the register defined by the |
1010 | // phi, just like when we are duplicating 2 into 3, but we don't copy any |
1011 | // real instructions or remove the 3 -> 2 edge from the phi in 2. |
1012 | for (MachineBasicBlock *PredBB : Preds) { |
1013 | if (is_contained(Range&: TDBBs, Element: PredBB)) |
1014 | continue; |
1015 | |
1016 | // EH edges |
1017 | if (PredBB->succ_size() != 1) |
1018 | continue; |
1019 | |
1020 | DenseMap<Register, RegSubRegPair> LocalVRMap; |
1021 | SmallVector<std::pair<Register, RegSubRegPair>, 4> CopyInfos; |
1022 | // Process PHI instructions first. |
1023 | for (MachineInstr &MI : make_early_inc_range(Range: TailBB->phis())) { |
1024 | // Replace the uses of the def of the PHI with the register coming |
1025 | // from PredBB. |
1026 | processPHI(MI: &MI, TailBB, PredBB, LocalVRMap, Copies&: CopyInfos, RegsUsedByPhi: UsedByPhi, Remove: false); |
1027 | } |
1028 | appendCopies(MBB: PredBB, CopyInfos, Copies); |
1029 | } |
1030 | |
1031 | return Changed; |
1032 | } |
1033 | |
1034 | /// At the end of the block \p MBB generate COPY instructions between registers |
1035 | /// described by \p CopyInfos. Append resulting instructions to \p Copies. |
1036 | void TailDuplicator::appendCopies(MachineBasicBlock *MBB, |
1037 | SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos, |
1038 | SmallVectorImpl<MachineInstr*> &Copies) { |
1039 | MachineBasicBlock::iterator Loc = MBB->getFirstTerminator(); |
1040 | const MCInstrDesc &CopyD = TII->get(Opcode: TargetOpcode::COPY); |
1041 | for (auto &CI : CopyInfos) { |
1042 | auto C = BuildMI(BB&: *MBB, I: Loc, MIMD: DebugLoc(), MCID: CopyD, DestReg: CI.first) |
1043 | .addReg(RegNo: CI.second.Reg, flags: 0, SubReg: CI.second.SubReg); |
1044 | Copies.push_back(Elt: C); |
1045 | } |
1046 | } |
1047 | |
1048 | /// Remove the specified dead machine basic block from the function, updating |
1049 | /// the CFG. |
1050 | void TailDuplicator::removeDeadBlock( |
1051 | MachineBasicBlock *MBB, |
1052 | function_ref<void(MachineBasicBlock *)> *RemovalCallback) { |
1053 | assert(MBB->pred_empty() && "MBB must be dead!" ); |
1054 | LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB); |
1055 | |
1056 | MachineFunction *MF = MBB->getParent(); |
1057 | // Update the call site info. |
1058 | for (const MachineInstr &MI : *MBB) |
1059 | if (MI.shouldUpdateCallSiteInfo()) |
1060 | MF->eraseCallSiteInfo(MI: &MI); |
1061 | |
1062 | if (RemovalCallback) |
1063 | (*RemovalCallback)(MBB); |
1064 | |
1065 | // Remove all successors. |
1066 | while (!MBB->succ_empty()) |
1067 | MBB->removeSuccessor(I: MBB->succ_end() - 1); |
1068 | |
1069 | // Remove the block. |
1070 | MBB->eraseFromParent(); |
1071 | } |
1072 | |