LLVM 17.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 ConstrRC = MRI->constrainRegClass(VI->second.Reg, OrigRC);
431 }
432
433 if (ConstrRC) {
434 // If the class constraining succeeded, we can simply replace
435 // the old register with the mapped one.
436 MO.setReg(VI->second.Reg);
437 // We have Reg -> VI.Reg:VI.SubReg, so if Reg is used with a
438 // sub-register, we need to compose the sub-register indices.
440 VI->second.SubReg));
441 } else {
442 // The direct replacement is not possible, due to failing register
443 // class constraints. An explicit COPY is necessary. Create one
444 // that can be reused
445 auto *NewRC = MI->getRegClassConstraint(i, TII, TRI);
446 if (NewRC == nullptr)
447 NewRC = OrigRC;
448 Register NewReg = MRI->createVirtualRegister(NewRC);
449 BuildMI(*PredBB, NewMI, NewMI.getDebugLoc(),
450 TII->get(TargetOpcode::COPY), NewReg)
451 .addReg(VI->second.Reg, 0, VI->second.SubReg);
452 LocalVRMap.erase(VI);
453 LocalVRMap.insert(std::make_pair(Reg, RegSubRegPair(NewReg, 0)));
454 MO.setReg(NewReg);
455 // The composed VI.Reg:VI.SubReg is replaced with NewReg, which
456 // is equivalent to the whole register Reg. Hence, Reg:subreg
457 // is same as NewReg:subreg, so keep the sub-register index
458 // unchanged.
459 }
460 // Clear any kill flags from this operand. The new register could
461 // have uses after this one, so kills are not valid here.
462 MO.setIsKill(false);
463 }
464 }
465 }
466 }
467}
468
469/// After FromBB is tail duplicated into its predecessor blocks, the successors
470/// have gained new predecessors. Update the PHI instructions in them
471/// accordingly.
472void TailDuplicator::updateSuccessorsPHIs(
473 MachineBasicBlock *FromBB, bool isDead,
476 for (MachineBasicBlock *SuccBB : Succs) {
477 for (MachineInstr &MI : *SuccBB) {
478 if (!MI.isPHI())
479 break;
480 MachineInstrBuilder MIB(*FromBB->getParent(), MI);
481 unsigned Idx = 0;
482 for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) {
483 MachineOperand &MO = MI.getOperand(i + 1);
484 if (MO.getMBB() == FromBB) {
485 Idx = i;
486 break;
487 }
488 }
489
490 assert(Idx != 0);
491 MachineOperand &MO0 = MI.getOperand(Idx);
492 Register Reg = MO0.getReg();
493 if (isDead) {
494 // Folded into the previous BB.
495 // There could be duplicate phi source entries. FIXME: Should sdisel
496 // or earlier pass fixed this?
497 for (unsigned i = MI.getNumOperands() - 2; i != Idx; i -= 2) {
498 MachineOperand &MO = MI.getOperand(i + 1);
499 if (MO.getMBB() == FromBB) {
500 MI.removeOperand(i + 1);
501 MI.removeOperand(i);
502 }
503 }
504 } else
505 Idx = 0;
506
507 // If Idx is set, the operands at Idx and Idx+1 must be removed.
508 // We reuse the location to avoid expensive removeOperand calls.
509
511 SSAUpdateVals.find(Reg);
512 if (LI != SSAUpdateVals.end()) {
513 // This register is defined in the tail block.
514 for (const std::pair<MachineBasicBlock *, Register> &J : LI->second) {
515 MachineBasicBlock *SrcBB = J.first;
516 // If we didn't duplicate a bb into a particular predecessor, we
517 // might still have added an entry to SSAUpdateVals to correcly
518 // recompute SSA. If that case, avoid adding a dummy extra argument
519 // this PHI.
520 if (!SrcBB->isSuccessor(SuccBB))
521 continue;
522
523 Register SrcReg = J.second;
524 if (Idx != 0) {
525 MI.getOperand(Idx).setReg(SrcReg);
526 MI.getOperand(Idx + 1).setMBB(SrcBB);
527 Idx = 0;
528 } else {
529 MIB.addReg(SrcReg).addMBB(SrcBB);
530 }
531 }
532 } else {
533 // Live in tail block, must also be live in predecessors.
534 for (MachineBasicBlock *SrcBB : TDBBs) {
535 if (Idx != 0) {
536 MI.getOperand(Idx).setReg(Reg);
537 MI.getOperand(Idx + 1).setMBB(SrcBB);
538 Idx = 0;
539 } else {
540 MIB.addReg(Reg).addMBB(SrcBB);
541 }
542 }
543 }
544 if (Idx != 0) {
545 MI.removeOperand(Idx + 1);
546 MI.removeOperand(Idx);
547 }
548 }
549 }
550}
551
552/// Determine if it is profitable to duplicate this block.
554 MachineBasicBlock &TailBB) {
555 // When doing tail-duplication during layout, the block ordering is in flux,
556 // so canFallThrough returns a result based on incorrect information and
557 // should just be ignored.
558 if (!LayoutMode && TailBB.canFallThrough())
559 return false;
560
561 // Don't try to tail-duplicate single-block loops.
562 if (TailBB.isSuccessor(&TailBB))
563 return false;
564
565 // Set the limit on the cost to duplicate. When optimizing for size,
566 // duplicate only one, because one branch instruction can be eliminated to
567 // compensate for the duplication.
568 unsigned MaxDuplicateCount;
569 bool OptForSize = MF->getFunction().hasOptSize() ||
570 llvm::shouldOptimizeForSize(&TailBB, PSI, MBFI);
571 if (TailDupSize == 0)
572 MaxDuplicateCount = TailDuplicateSize;
573 else
574 MaxDuplicateCount = TailDupSize;
575 if (OptForSize)
576 MaxDuplicateCount = 1;
577
578 // If the block to be duplicated ends in an unanalyzable fallthrough, don't
579 // duplicate it.
580 // A similar check is necessary in MachineBlockPlacement to make sure pairs of
581 // blocks with unanalyzable fallthrough get layed out contiguously.
582 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
584 if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond) &&
585 TailBB.canFallThrough())
586 return false;
587
588 // If the target has hardware branch prediction that can handle indirect
589 // branches, duplicating them can often make them predictable when there
590 // are common paths through the code. The limit needs to be high enough
591 // to allow undoing the effects of tail merging and other optimizations
592 // that rearrange the predecessors of the indirect branch.
593
594 bool HasIndirectbr = false;
595 if (!TailBB.empty())
596 HasIndirectbr = TailBB.back().isIndirectBranch();
597
598 if (HasIndirectbr && PreRegAlloc)
599 MaxDuplicateCount = TailDupIndirectBranchSize;
600
601 // Check the instructions in the block to determine whether tail-duplication
602 // is invalid or unlikely to be profitable.
603 unsigned InstrCount = 0;
604 for (MachineInstr &MI : TailBB) {
605 // Non-duplicable things shouldn't be tail-duplicated.
606 // CFI instructions are marked as non-duplicable, because Darwin compact
607 // unwind info emission can't handle multiple prologue setups. In case of
608 // DWARF, allow them be duplicated, so that their existence doesn't prevent
609 // tail duplication of some basic blocks, that would be duplicated otherwise.
610 if (MI.isNotDuplicable() &&
612 !MI.isCFIInstruction()))
613 return false;
614
615 // Convergent instructions can be duplicated only if doing so doesn't add
616 // new control dependencies, which is what we're going to do here.
617 if (MI.isConvergent())
618 return false;
619
620 // Do not duplicate 'return' instructions if this is a pre-regalloc run.
621 // A return may expand into a lot more instructions (e.g. reload of callee
622 // saved registers) after PEI.
623 if (PreRegAlloc && MI.isReturn())
624 return false;
625
626 // Avoid duplicating calls before register allocation. Calls presents a
627 // barrier to register allocation so duplicating them may end up increasing
628 // spills.
629 if (PreRegAlloc && MI.isCall())
630 return false;
631
632 // TailDuplicator::appendCopies will erroneously place COPYs after
633 // INLINEASM_BR instructions after 4b0aa5724fea, which demonstrates the same
634 // bug that was fixed in f7a53d82c090.
635 // FIXME: Use findPHICopyInsertPoint() to find the correct insertion point
636 // for the COPY when replacing PHIs.
637 if (MI.getOpcode() == TargetOpcode::INLINEASM_BR)
638 return false;
639
640 if (MI.isBundle())
641 InstrCount += MI.getBundleSize();
642 else if (!MI.isPHI() && !MI.isMetaInstruction())
643 InstrCount += 1;
644
645 if (InstrCount > MaxDuplicateCount)
646 return false;
647 }
648
649 // Check if any of the successors of TailBB has a PHI node in which the
650 // value corresponding to TailBB uses a subregister.
651 // If a phi node uses a register paired with a subregister, the actual
652 // "value type" of the phi may differ from the type of the register without
653 // any subregisters. Due to a bug, tail duplication may add a new operand
654 // without a necessary subregister, producing an invalid code. This is
655 // demonstrated by test/CodeGen/Hexagon/tail-dup-subreg-abort.ll.
656 // Disable tail duplication for this case for now, until the problem is
657 // fixed.
658 for (auto *SB : TailBB.successors()) {
659 for (auto &I : *SB) {
660 if (!I.isPHI())
661 break;
662 unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
663 assert(Idx != 0);
664 MachineOperand &PU = I.getOperand(Idx);
665 if (PU.getSubReg() != 0)
666 return false;
667 }
668 }
669
670 if (HasIndirectbr && PreRegAlloc)
671 return true;
672
673 if (IsSimple)
674 return true;
675
676 if (!PreRegAlloc)
677 return true;
678
679 return canCompletelyDuplicateBB(TailBB);
680}
681
682/// True if this BB has only one unconditional jump.
684 if (TailBB->succ_size() != 1)
685 return false;
686 if (TailBB->pred_empty())
687 return false;
689 if (I == TailBB->end())
690 return true;
691 return I->isUnconditionalBranch();
692}
693
696 for (MachineBasicBlock *BB : A.successors())
697 if (SuccsB.count(BB) && !BB->empty() && BB->begin()->isPHI())
698 return true;
699
700 return false;
701}
702
703bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) {
704 for (MachineBasicBlock *PredBB : BB.predecessors()) {
705 if (PredBB->succ_size() > 1)
706 return false;
707
708 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
710 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
711 return false;
712
713 if (!PredCond.empty())
714 return false;
715 }
716 return true;
717}
718
719bool TailDuplicator::duplicateSimpleBB(
721 const DenseSet<Register> &UsedByPhi) {
723 TailBB->succ_end());
725 bool Changed = false;
726 for (MachineBasicBlock *PredBB : Preds) {
727 if (PredBB->hasEHPadSuccessor() || PredBB->mayHaveInlineAsmBr())
728 continue;
729
730 if (bothUsedInPHI(*PredBB, Succs))
731 continue;
732
733 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
735 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
736 continue;
737
738 Changed = true;
739 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
740 << "From simple Succ: " << *TailBB);
741
742 MachineBasicBlock *NewTarget = *TailBB->succ_begin();
743 MachineBasicBlock *NextBB = PredBB->getNextNode();
744
745 // Make PredFBB explicit.
746 if (PredCond.empty())
747 PredFBB = PredTBB;
748
749 // Make fall through explicit.
750 if (!PredTBB)
751 PredTBB = NextBB;
752 if (!PredFBB)
753 PredFBB = NextBB;
754
755 // Redirect
756 if (PredFBB == TailBB)
757 PredFBB = NewTarget;
758 if (PredTBB == TailBB)
759 PredTBB = NewTarget;
760
761 // Make the branch unconditional if possible
762 if (PredTBB == PredFBB) {
763 PredCond.clear();
764 PredFBB = nullptr;
765 }
766
767 // Avoid adding fall through branches.
768 if (PredFBB == NextBB)
769 PredFBB = nullptr;
770 if (PredTBB == NextBB && PredFBB == nullptr)
771 PredTBB = nullptr;
772
773 auto DL = PredBB->findBranchDebugLoc();
774 TII->removeBranch(*PredBB);
775
776 if (!PredBB->isSuccessor(NewTarget))
777 PredBB->replaceSuccessor(TailBB, NewTarget);
778 else {
779 PredBB->removeSuccessor(TailBB, true);
780 assert(PredBB->succ_size() <= 1);
781 }
782
783 if (PredTBB)
784 TII->insertBranch(*PredBB, PredTBB, PredFBB, PredCond, DL);
785
786 TDBBs.push_back(PredBB);
787 }
788 return Changed;
789}
790
792 MachineBasicBlock *PredBB) {
793 // EH edges are ignored by analyzeBranch.
794 if (PredBB->succ_size() > 1)
795 return false;
796
797 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
799 if (TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond))
800 return false;
801 if (!PredCond.empty())
802 return false;
803 // FIXME: This is overly conservative; it may be ok to relax this in the
804 // future under more specific conditions. If TailBB is an INLINEASM_BR
805 // indirect target, we need to see if the edge from PredBB to TailBB is from
806 // an INLINEASM_BR in PredBB, and then also if that edge was from the
807 // indirect target list, fallthrough/default target, or potentially both. If
808 // it's both, TailDuplicator::tailDuplicate will remove the edge, corrupting
809 // the successor list in PredBB and predecessor list in TailBB.
810 if (TailBB->isInlineAsmBrIndirectTarget())
811 return false;
812 return true;
813}
814
815/// If it is profitable, duplicate TailBB's contents in each
816/// of its predecessors.
817/// \p IsSimple result of isSimpleBB
818/// \p TailBB Block to be duplicated.
819/// \p ForcedLayoutPred When non-null, use this block as the layout predecessor
820/// instead of the previous block in MF's order.
821/// \p TDBBs A vector to keep track of all blocks tail-duplicated
822/// into.
823/// \p Copies A vector of copy instructions inserted. Used later to
824/// walk all the inserted copies and remove redundant ones.
825bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
826 MachineBasicBlock *ForcedLayoutPred,
830 LLVM_DEBUG(dbgs() << "\n*** Tail-duplicating " << printMBBReference(*TailBB)
831 << '\n');
832
833 bool ShouldUpdateTerminators = TailBB->canFallThrough();
834
835 DenseSet<Register> UsedByPhi;
836 getRegsUsedByPHIs(*TailBB, &UsedByPhi);
837
838 if (IsSimple)
839 return duplicateSimpleBB(TailBB, TDBBs, UsedByPhi);
840
841 // Iterate through all the unique predecessors and tail-duplicate this
842 // block into them, if possible. Copying the list ahead of time also
843 // avoids trouble with the predecessor list reallocating.
844 bool Changed = false;
846 if (CandidatePtr)
847 Preds.insert(CandidatePtr->begin(), CandidatePtr->end());
848 else
849 Preds.insert(TailBB->pred_begin(), TailBB->pred_end());
850
851 for (MachineBasicBlock *PredBB : Preds) {
852 assert(TailBB != PredBB &&
853 "Single-block loop should have been rejected earlier!");
854
855 if (!canTailDuplicate(TailBB, PredBB))
856 continue;
857
858 // Don't duplicate into a fall-through predecessor (at least for now).
859 // If profile is available, findDuplicateCandidates can choose better
860 // fall-through predecessor.
861 if (!(MF->getFunction().hasProfileData() && LayoutMode)) {
862 bool IsLayoutSuccessor = false;
863 if (ForcedLayoutPred)
864 IsLayoutSuccessor = (ForcedLayoutPred == PredBB);
865 else if (PredBB->isLayoutSuccessor(TailBB) && PredBB->canFallThrough())
866 IsLayoutSuccessor = true;
867 if (IsLayoutSuccessor)
868 continue;
869 }
870
871 LLVM_DEBUG(dbgs() << "\nTail-duplicating into PredBB: " << *PredBB
872 << "From Succ: " << *TailBB);
873
874 TDBBs.push_back(PredBB);
875
876 // Remove PredBB's unconditional branch.
877 TII->removeBranch(*PredBB);
878
879 // Clone the contents of TailBB into PredBB.
882 for (MachineInstr &MI : llvm::make_early_inc_range(*TailBB)) {
883 if (MI.isPHI()) {
884 // Replace the uses of the def of the PHI with the register coming
885 // from PredBB.
886 processPHI(&MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, true);
887 } else {
888 // Replace def of virtual registers with new registers, and update
889 // uses with PHI source register or the new registers.
890 duplicateInstruction(&MI, TailBB, PredBB, LocalVRMap, UsedByPhi);
891 }
892 }
893 appendCopies(PredBB, CopyInfos, Copies);
894
895 NumTailDupAdded += TailBB->size() - 1; // subtract one for removed branch
896
897 // Update the CFG.
898 PredBB->removeSuccessor(PredBB->succ_begin());
899 assert(PredBB->succ_empty() &&
900 "TailDuplicate called on block with multiple successors!");
901 for (MachineBasicBlock *Succ : TailBB->successors())
902 PredBB->addSuccessor(Succ, MBPI->getEdgeProbability(TailBB, Succ));
903
904 // Update branches in pred to jump to tail's layout successor if needed.
905 if (ShouldUpdateTerminators)
906 PredBB->updateTerminator(TailBB->getNextNode());
907
908 Changed = true;
909 ++NumTailDups;
910 }
911
912 // If TailBB was duplicated into all its predecessors except for the prior
913 // block, which falls through unconditionally, move the contents of this
914 // block into the prior block.
915 MachineBasicBlock *PrevBB = ForcedLayoutPred;
916 if (!PrevBB)
917 PrevBB = &*std::prev(TailBB->getIterator());
918 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
920 // This has to check PrevBB->succ_size() because EH edges are ignored by
921 // analyzeBranch.
922 if (PrevBB->succ_size() == 1 &&
923 // Layout preds are not always CFG preds. Check.
924 *PrevBB->succ_begin() == TailBB &&
925 !TII->analyzeBranch(*PrevBB, PriorTBB, PriorFBB, PriorCond) &&
926 PriorCond.empty() &&
927 (!PriorTBB || PriorTBB == TailBB) &&
928 TailBB->pred_size() == 1 &&
929 !TailBB->hasAddressTaken()) {
930 LLVM_DEBUG(dbgs() << "\nMerging into block: " << *PrevBB
931 << "From MBB: " << *TailBB);
932 // There may be a branch to the layout successor. This is unlikely but it
933 // happens. The correct thing to do is to remove the branch before
934 // duplicating the instructions in all cases.
935 bool RemovedBranches = TII->removeBranch(*PrevBB) != 0;
936
937 // If there are still tail instructions, abort the merge
938 if (PrevBB->getFirstTerminator() == PrevBB->end()) {
939 if (PreRegAlloc) {
943 // Process PHI instructions first.
944 while (I != TailBB->end() && I->isPHI()) {
945 // Replace the uses of the def of the PHI with the register coming
946 // from PredBB.
947 MachineInstr *MI = &*I++;
948 processPHI(MI, TailBB, PrevBB, LocalVRMap, CopyInfos, UsedByPhi,
949 true);
950 }
951
952 // Now copy the non-PHI instructions.
953 while (I != TailBB->end()) {
954 // Replace def of virtual registers with new registers, and update
955 // uses with PHI source register or the new registers.
956 MachineInstr *MI = &*I++;
957 assert(!MI->isBundle() && "Not expecting bundles before regalloc!");
958 duplicateInstruction(MI, TailBB, PrevBB, LocalVRMap, UsedByPhi);
959 MI->eraseFromParent();
960 }
961 appendCopies(PrevBB, CopyInfos, Copies);
962 } else {
963 TII->removeBranch(*PrevBB);
964 // No PHIs to worry about, just splice the instructions over.
965 PrevBB->splice(PrevBB->end(), TailBB, TailBB->begin(), TailBB->end());
966 }
967 PrevBB->removeSuccessor(PrevBB->succ_begin());
968 assert(PrevBB->succ_empty());
969 PrevBB->transferSuccessors(TailBB);
970
971 // Update branches in PrevBB based on Tail's layout successor.
972 if (ShouldUpdateTerminators)
973 PrevBB->updateTerminator(TailBB->getNextNode());
974
975 TDBBs.push_back(PrevBB);
976 Changed = true;
977 } else {
978 LLVM_DEBUG(dbgs() << "Abort merging blocks, the predecessor still "
979 "contains terminator instructions");
980 // Return early if no changes were made
981 if (!Changed)
982 return RemovedBranches;
983 }
984 Changed |= RemovedBranches;
985 }
986
987 // If this is after register allocation, there are no phis to fix.
988 if (!PreRegAlloc)
989 return Changed;
990
991 // If we made no changes so far, we are safe.
992 if (!Changed)
993 return Changed;
994
995 // Handle the nasty case in that we duplicated a block that is part of a loop
996 // into some but not all of its predecessors. For example:
997 // 1 -> 2 <-> 3 |
998 // \ |
999 // \---> rest |
1000 // if we duplicate 2 into 1 but not into 3, we end up with
1001 // 12 -> 3 <-> 2 -> rest |
1002 // \ / |
1003 // \----->-----/ |
1004 // If there was a "var = phi(1, 3)" in 2, it has to be ultimately replaced
1005 // with a phi in 3 (which now dominates 2).
1006 // What we do here is introduce a copy in 3 of the register defined by the
1007 // phi, just like when we are duplicating 2 into 3, but we don't copy any
1008 // real instructions or remove the 3 -> 2 edge from the phi in 2.
1009 for (MachineBasicBlock *PredBB : Preds) {
1010 if (is_contained(TDBBs, PredBB))
1011 continue;
1012
1013 // EH edges
1014 if (PredBB->succ_size() != 1)
1015 continue;
1016
1020 // Process PHI instructions first.
1021 while (I != TailBB->end() && I->isPHI()) {
1022 // Replace the uses of the def of the PHI with the register coming
1023 // from PredBB.
1024 MachineInstr *MI = &*I++;
1025 processPHI(MI, TailBB, PredBB, LocalVRMap, CopyInfos, UsedByPhi, false);
1026 }
1027 appendCopies(PredBB, CopyInfos, Copies);
1028 }
1029
1030 return Changed;
1031}
1032
1033/// At the end of the block \p MBB generate COPY instructions between registers
1034/// described by \p CopyInfos. Append resulting instructions to \p Copies.
1035void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
1036 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
1039 const MCInstrDesc &CopyD = TII->get(TargetOpcode::COPY);
1040 for (auto &CI : CopyInfos) {
1041 auto C = BuildMI(*MBB, Loc, DebugLoc(), CopyD, CI.first)
1042 .addReg(CI.second.Reg, 0, CI.second.SubReg);
1043 Copies.push_back(C);
1044 }
1045}
1046
1047/// Remove the specified dead machine basic block from the function, updating
1048/// the CFG.
1049void TailDuplicator::removeDeadBlock(
1051 function_ref<void(MachineBasicBlock *)> *RemovalCallback) {
1052 assert(MBB->pred_empty() && "MBB must be dead!");
1053 LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
1054
1055 MachineFunction *MF = MBB->getParent();
1056 // Update the call site info.
1057 for (const MachineInstr &MI : *MBB)
1058 if (MI.shouldUpdateCallSiteInfo())
1059 MF->eraseCallSiteInfo(&MI);
1060
1061 if (RemovalCallback)
1062 (*RemovalCallback)(MBB);
1063
1064 // Remove all successors.
1065 while (!MBB->succ_empty())
1067
1068 // Remove the block.
1070}
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
@ VI
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:150
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
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:644
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
Definition: Function.h:289
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...
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 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 DBG_VALUE and DBG_LABEL 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:313
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:519
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
bool isDebugValue() const
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
Definition: MachineInstr.h:910
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:141
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
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:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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, or DriverKit).
Definition: Triple.h:518
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:82
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
#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:445
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:386
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:721
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)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
A pair composed of a register and a sub-register index.