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