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