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