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