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