LLVM 18.0.0git
BranchFolding.cpp
Go to the documentation of this file.
1//===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
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 pass forwards branches to unconditional branches to make them branch
10// directly to the target block. This pass often results in dead MBB's, which
11// it then removes.
12//
13// Note that this pass must be run after register allocation, it cannot handle
14// SSA form. It also must handle virtual registers for targets that emit virtual
15// ISA (e.g. NVPTX).
16//
17//===----------------------------------------------------------------------===//
18
19#include "BranchFolding.h"
20#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/Statistic.h"
45#include "llvm/IR/DebugLoc.h"
46#include "llvm/IR/Function.h"
48#include "llvm/MC/LaneBitmask.h"
50#include "llvm/Pass.h"
54#include "llvm/Support/Debug.h"
58#include <cassert>
59#include <cstddef>
60#include <iterator>
61#include <numeric>
62
63using namespace llvm;
64
65#define DEBUG_TYPE "branch-folder"
66
67STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
68STATISTIC(NumBranchOpts, "Number of branches optimized");
69STATISTIC(NumTailMerge , "Number of block tails merged");
70STATISTIC(NumHoist , "Number of times common instructions are hoisted");
71STATISTIC(NumTailCalls, "Number of tail calls optimized");
72
75
76// Throttle for huge numbers of predecessors (compile speed problems)
78TailMergeThreshold("tail-merge-threshold",
79 cl::desc("Max number of predecessors to consider tail merging"),
80 cl::init(150), cl::Hidden);
81
82// Heuristic for tail merging (and, inversely, tail duplication).
83// TODO: This should be replaced with a target query.
85TailMergeSize("tail-merge-size",
86 cl::desc("Min number of instructions to consider tail merging"),
88
89namespace {
90
91 /// BranchFolderPass - Wrap branch folder in a machine function pass.
92 class BranchFolderPass : public MachineFunctionPass {
93 public:
94 static char ID;
95
96 explicit BranchFolderPass(): MachineFunctionPass(ID) {}
97
98 bool runOnMachineFunction(MachineFunction &MF) override;
99
100 void getAnalysisUsage(AnalysisUsage &AU) const override {
106 }
107
110 MachineFunctionProperties::Property::NoPHIs);
111 }
112 };
113
114} // end anonymous namespace
115
116char BranchFolderPass::ID = 0;
117
118char &llvm::BranchFolderPassID = BranchFolderPass::ID;
119
120INITIALIZE_PASS(BranchFolderPass, DEBUG_TYPE,
121 "Control Flow Optimizer", false, false)
122
123bool BranchFolderPass::runOnMachineFunction(MachineFunction &MF) {
124 if (skipFunction(MF.getFunction()))
125 return false;
126
127 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>();
128 // TailMerge can create jump into if branches that make CFG irreducible for
129 // HW that requires structurized CFG.
130 bool EnableTailMerge = !MF.getTarget().requiresStructuredCFG() &&
131 PassConfig->getEnableTailMerge();
132 MBFIWrapper MBBFreqInfo(
133 getAnalysis<MachineBlockFrequencyInfo>());
134 BranchFolder Folder(EnableTailMerge, /*CommonHoist=*/true, MBBFreqInfo,
135 getAnalysis<MachineBranchProbabilityInfo>(),
136 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI());
137 return Folder.OptimizeFunction(MF, MF.getSubtarget().getInstrInfo(),
138 MF.getSubtarget().getRegisterInfo());
139}
140
141BranchFolder::BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
142 MBFIWrapper &FreqInfo,
143 const MachineBranchProbabilityInfo &ProbInfo,
144 ProfileSummaryInfo *PSI, unsigned MinTailLength)
145 : EnableHoistCommonCode(CommonHoist), MinCommonTailLength(MinTailLength),
146 MBBFreqInfo(FreqInfo), MBPI(ProbInfo), PSI(PSI) {
147 if (MinCommonTailLength == 0)
148 MinCommonTailLength = TailMergeSize;
149 switch (FlagEnableTailMerge) {
150 case cl::BOU_UNSET:
151 EnableTailMerge = DefaultEnableTailMerge;
152 break;
153 case cl::BOU_TRUE: EnableTailMerge = true; break;
154 case cl::BOU_FALSE: EnableTailMerge = false; break;
155 }
156}
157
158void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) {
159 assert(MBB->pred_empty() && "MBB must be dead!");
160 LLVM_DEBUG(dbgs() << "\nRemoving MBB: " << *MBB);
161
163 // drop all successors.
164 while (!MBB->succ_empty())
166
167 // Avoid matching if this pointer gets reused.
168 TriedMerging.erase(MBB);
169
170 // Update call site info.
171 for (const MachineInstr &MI : *MBB)
172 if (MI.shouldUpdateCallSiteInfo())
173 MF->eraseCallSiteInfo(&MI);
174
175 // Remove the block.
176 MF->erase(MBB);
177 EHScopeMembership.erase(MBB);
178 if (MLI)
179 MLI->removeBlock(MBB);
180}
181
183 const TargetInstrInfo *tii,
184 const TargetRegisterInfo *tri,
185 MachineLoopInfo *mli, bool AfterPlacement) {
186 if (!tii) return false;
187
188 TriedMerging.clear();
189
191 AfterBlockPlacement = AfterPlacement;
192 TII = tii;
193 TRI = tri;
194 MLI = mli;
195 this->MRI = &MRI;
196
197 UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);
198 if (!UpdateLiveIns)
199 MRI.invalidateLiveness();
200
201 bool MadeChange = false;
202
203 // Recalculate EH scope membership.
204 EHScopeMembership = getEHScopeMembership(MF);
205
206 bool MadeChangeThisIteration = true;
207 while (MadeChangeThisIteration) {
208 MadeChangeThisIteration = TailMergeBlocks(MF);
209 // No need to clean up if tail merging does not change anything after the
210 // block placement.
211 if (!AfterBlockPlacement || MadeChangeThisIteration)
212 MadeChangeThisIteration |= OptimizeBranches(MF);
213 if (EnableHoistCommonCode)
214 MadeChangeThisIteration |= HoistCommonCode(MF);
215 MadeChange |= MadeChangeThisIteration;
216 }
217
218 // See if any jump tables have become dead as the code generator
219 // did its thing.
221 if (!JTI)
222 return MadeChange;
223
224 // Walk the function to find jump tables that are live.
225 BitVector JTIsLive(JTI->getJumpTables().size());
226 for (const MachineBasicBlock &BB : MF) {
227 for (const MachineInstr &I : BB)
228 for (const MachineOperand &Op : I.operands()) {
229 if (!Op.isJTI()) continue;
230
231 // Remember that this JT is live.
232 JTIsLive.set(Op.getIndex());
233 }
234 }
235
236 // Finally, remove dead jump tables. This happens when the
237 // indirect jump was unreachable (and thus deleted).
238 for (unsigned i = 0, e = JTIsLive.size(); i != e; ++i)
239 if (!JTIsLive.test(i)) {
240 JTI->RemoveJumpTable(i);
241 MadeChange = true;
242 }
243
244 return MadeChange;
245}
246
247//===----------------------------------------------------------------------===//
248// Tail Merging of Blocks
249//===----------------------------------------------------------------------===//
250
251/// HashMachineInstr - Compute a hash value for MI and its operands.
252static unsigned HashMachineInstr(const MachineInstr &MI) {
253 unsigned Hash = MI.getOpcode();
254 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
255 const MachineOperand &Op = MI.getOperand(i);
256
257 // Merge in bits from the operand if easy. We can't use MachineOperand's
258 // hash_code here because it's not deterministic and we sort by hash value
259 // later.
260 unsigned OperandHash = 0;
261 switch (Op.getType()) {
263 OperandHash = Op.getReg();
264 break;
266 OperandHash = Op.getImm();
267 break;
269 OperandHash = Op.getMBB()->getNumber();
270 break;
274 OperandHash = Op.getIndex();
275 break;
278 // Global address / external symbol are too hard, don't bother, but do
279 // pull in the offset.
280 OperandHash = Op.getOffset();
281 break;
282 default:
283 break;
284 }
285
286 Hash += ((OperandHash << 3) | Op.getType()) << (i & 31);
287 }
288 return Hash;
289}
290
291/// HashEndOfMBB - Hash the last instruction in the MBB.
292static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) {
294 if (I == MBB.end())
295 return 0;
296
297 return HashMachineInstr(*I);
298}
299
300/// Whether MI should be counted as an instruction when calculating common tail.
302 return !(MI.isDebugInstr() || MI.isCFIInstruction());
303}
304
305/// Iterate backwards from the given iterator \p I, towards the beginning of the
306/// block. If a MI satisfying 'countsAsInstruction' is found, return an iterator
307/// pointing to that MI. If no such MI is found, return the end iterator.
311 while (I != MBB->begin()) {
312 --I;
314 return I;
315 }
316 return MBB->end();
317}
318
319/// Given two machine basic blocks, return the number of instructions they
320/// actually have in common together at their end. If a common tail is found (at
321/// least by one instruction), then iterators for the first shared instruction
322/// in each block are returned as well.
323///
324/// Non-instructions according to countsAsInstruction are ignored.
326 MachineBasicBlock *MBB2,
329 MachineBasicBlock::iterator MBBI1 = MBB1->end();
330 MachineBasicBlock::iterator MBBI2 = MBB2->end();
331
332 unsigned TailLen = 0;
333 while (true) {
334 MBBI1 = skipBackwardPastNonInstructions(MBBI1, MBB1);
335 MBBI2 = skipBackwardPastNonInstructions(MBBI2, MBB2);
336 if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())
337 break;
338 if (!MBBI1->isIdenticalTo(*MBBI2) ||
339 // FIXME: This check is dubious. It's used to get around a problem where
340 // people incorrectly expect inline asm directives to remain in the same
341 // relative order. This is untenable because normal compiler
342 // optimizations (like this one) may reorder and/or merge these
343 // directives.
344 MBBI1->isInlineAsm()) {
345 break;
346 }
347 if (MBBI1->getFlag(MachineInstr::NoMerge) ||
348 MBBI2->getFlag(MachineInstr::NoMerge))
349 break;
350 ++TailLen;
351 I1 = MBBI1;
352 I2 = MBBI2;
353 }
354
355 return TailLen;
356}
357
358void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
359 MachineBasicBlock &NewDest) {
360 if (UpdateLiveIns) {
361 // OldInst should always point to an instruction.
362 MachineBasicBlock &OldMBB = *OldInst->getParent();
363 LiveRegs.clear();
364 LiveRegs.addLiveOuts(OldMBB);
365 // Move backward to the place where will insert the jump.
367 do {
368 --I;
369 LiveRegs.stepBackward(*I);
370 } while (I != OldInst);
371
372 // Merging the tails may have switched some undef operand to non-undef ones.
373 // Add IMPLICIT_DEFS into OldMBB as necessary to have a definition of the
374 // register.
376 // We computed the liveins with computeLiveIn earlier and should only see
377 // full registers:
378 assert(P.LaneMask == LaneBitmask::getAll() &&
379 "Can only handle full register.");
380 MCPhysReg Reg = P.PhysReg;
381 if (!LiveRegs.available(*MRI, Reg))
382 continue;
383 DebugLoc DL;
384 BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);
385 }
386 }
387
388 TII->ReplaceTailWithBranchTo(OldInst, &NewDest);
389 ++NumTailMerge;
390}
391
392MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
394 const BasicBlock *BB) {
395 if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))
396 return nullptr;
397
398 MachineFunction &MF = *CurMBB.getParent();
399
400 // Create the fall-through block.
403 CurMBB.getParent()->insert(++MBBI, NewMBB);
404
405 // Move all the successors of this block to the specified block.
406 NewMBB->transferSuccessors(&CurMBB);
407
408 // Add an edge from CurMBB to NewMBB for the fall-through.
409 CurMBB.addSuccessor(NewMBB);
410
411 // Splice the code over.
412 NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());
413
414 // NewMBB belongs to the same loop as CurMBB.
415 if (MLI)
416 if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))
417 ML->addBasicBlockToLoop(NewMBB, MLI->getBase());
418
419 // NewMBB inherits CurMBB's block frequency.
420 MBBFreqInfo.setBlockFreq(NewMBB, MBBFreqInfo.getBlockFreq(&CurMBB));
421
422 if (UpdateLiveIns)
423 computeAndAddLiveIns(LiveRegs, *NewMBB);
424
425 // Add the new block to the EH scope.
426 const auto &EHScopeI = EHScopeMembership.find(&CurMBB);
427 if (EHScopeI != EHScopeMembership.end()) {
428 auto n = EHScopeI->second;
429 EHScopeMembership[NewMBB] = n;
430 }
431
432 return NewMBB;
433}
434
435/// EstimateRuntime - Make a rough estimate for how long it will take to run
436/// the specified code.
439 unsigned Time = 0;
440 for (; I != E; ++I) {
441 if (!countsAsInstruction(*I))
442 continue;
443 if (I->isCall())
444 Time += 10;
445 else if (I->mayLoadOrStore())
446 Time += 2;
447 else
448 ++Time;
449 }
450 return Time;
451}
452
453// CurMBB needs to add an unconditional branch to SuccMBB (we removed these
454// branches temporarily for tail merging). In the case where CurMBB ends
455// with a conditional branch to the next block, optimize by reversing the
456// test and conditionally branching to SuccMBB instead.
457static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
458 const TargetInstrInfo *TII) {
459 MachineFunction *MF = CurMBB->getParent();
461 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
463 DebugLoc dl = CurMBB->findBranchDebugLoc();
464 if (I != MF->end() && !TII->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {
465 MachineBasicBlock *NextBB = &*I;
466 if (TBB == NextBB && !Cond.empty() && !FBB) {
468 TII->removeBranch(*CurMBB);
469 TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);
470 return;
471 }
472 }
473 }
474 TII->insertBranch(*CurMBB, SuccBB, nullptr,
476}
477
478bool
479BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const {
480 if (getHash() < o.getHash())
481 return true;
482 if (getHash() > o.getHash())
483 return false;
484 if (getBlock()->getNumber() < o.getBlock()->getNumber())
485 return true;
486 if (getBlock()->getNumber() > o.getBlock()->getNumber())
487 return false;
488 return false;
489}
490
491/// CountTerminators - Count the number of terminators in the given
492/// block and set I to the position of the first non-terminator, if there
493/// is one, or MBB->end() otherwise.
496 I = MBB->end();
497 unsigned NumTerms = 0;
498 while (true) {
499 if (I == MBB->begin()) {
500 I = MBB->end();
501 break;
502 }
503 --I;
504 if (!I->isTerminator()) break;
505 ++NumTerms;
506 }
507 return NumTerms;
508}
509
510/// A no successor, non-return block probably ends in unreachable and is cold.
511/// Also consider a block that ends in an indirect branch to be a return block,
512/// since many targets use plain indirect branches to return.
514 if (!MBB->succ_empty())
515 return false;
516 if (MBB->empty())
517 return true;
518 return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
519}
520
521/// ProfitableToMerge - Check if two machine basic blocks have a common tail
522/// and decide if it would be profitable to merge those tails. Return the
523/// length of the common tail and iterators to the first common instruction
524/// in each block.
525/// MBB1, MBB2 The blocks to check
526/// MinCommonTailLength Minimum size of tail block to be merged.
527/// CommonTailLen Out parameter to record the size of the shared tail between
528/// MBB1 and MBB2
529/// I1, I2 Iterator references that will be changed to point to the first
530/// instruction in the common tail shared by MBB1,MBB2
531/// SuccBB A common successor of MBB1, MBB2 which are in a canonical form
532/// relative to SuccBB
533/// PredBB The layout predecessor of SuccBB, if any.
534/// EHScopeMembership map from block to EH scope #.
535/// AfterPlacement True if we are merging blocks after layout. Stricter
536/// thresholds apply to prevent undoing tail-duplication.
537static bool
539 unsigned MinCommonTailLength, unsigned &CommonTailLen,
542 MachineBasicBlock *PredBB,
544 bool AfterPlacement,
545 MBFIWrapper &MBBFreqInfo,
546 ProfileSummaryInfo *PSI) {
547 // It is never profitable to tail-merge blocks from two different EH scopes.
548 if (!EHScopeMembership.empty()) {
549 auto EHScope1 = EHScopeMembership.find(MBB1);
550 assert(EHScope1 != EHScopeMembership.end());
551 auto EHScope2 = EHScopeMembership.find(MBB2);
552 assert(EHScope2 != EHScopeMembership.end());
553 if (EHScope1->second != EHScope2->second)
554 return false;
555 }
556
557 CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
558 if (CommonTailLen == 0)
559 return false;
560 LLVM_DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
561 << " and " << printMBBReference(*MBB2) << " is "
562 << CommonTailLen << '\n');
563
564 // Move the iterators to the beginning of the MBB if we only got debug
565 // instructions before the tail. This is to avoid splitting a block when we
566 // only got debug instructions before the tail (to be invariant on -g).
567 if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end(), false) == I1)
568 I1 = MBB1->begin();
569 if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end(), false) == I2)
570 I2 = MBB2->begin();
571
572 bool FullBlockTail1 = I1 == MBB1->begin();
573 bool FullBlockTail2 = I2 == MBB2->begin();
574
575 // It's almost always profitable to merge any number of non-terminator
576 // instructions with the block that falls through into the common successor.
577 // This is true only for a single successor. For multiple successors, we are
578 // trading a conditional branch for an unconditional one.
579 // TODO: Re-visit successor size for non-layout tail merging.
580 if ((MBB1 == PredBB || MBB2 == PredBB) &&
581 (!AfterPlacement || MBB1->succ_size() == 1)) {
583 unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
584 if (CommonTailLen > NumTerms)
585 return true;
586 }
587
588 // If these are identical non-return blocks with no successors, merge them.
589 // Such blocks are typically cold calls to noreturn functions like abort, and
590 // are unlikely to become a fallthrough target after machine block placement.
591 // Tail merging these blocks is unlikely to create additional unconditional
592 // branches, and will reduce the size of this cold code.
593 if (FullBlockTail1 && FullBlockTail2 &&
595 return true;
596
597 // If one of the blocks can be completely merged and happens to be in
598 // a position where the other could fall through into it, merge any number
599 // of instructions, because it can be done without a branch.
600 // TODO: If the blocks are not adjacent, move one of them so that they are?
601 if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)
602 return true;
603 if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)
604 return true;
605
606 // If both blocks are identical and end in a branch, merge them unless they
607 // both have a fallthrough predecessor and successor.
608 // We can only do this after block placement because it depends on whether
609 // there are fallthroughs, and we don't know until after layout.
610 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
611 auto BothFallThrough = [](MachineBasicBlock *MBB) {
612 if (!MBB->succ_empty() && !MBB->canFallThrough())
613 return false;
616 return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();
617 };
618 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
619 return true;
620 }
621
622 // If both blocks have an unconditional branch temporarily stripped out,
623 // count that as an additional common instruction for the following
624 // heuristics. This heuristic is only accurate for single-succ blocks, so to
625 // make sure that during layout merging and duplicating don't crash, we check
626 // for that when merging during layout.
627 unsigned EffectiveTailLen = CommonTailLen;
628 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
629 (MBB1->succ_size() == 1 || !AfterPlacement) &&
630 !MBB1->back().isBarrier() &&
631 !MBB2->back().isBarrier())
632 ++EffectiveTailLen;
633
634 // Check if the common tail is long enough to be worthwhile.
635 if (EffectiveTailLen >= MinCommonTailLength)
636 return true;
637
638 // If we are optimizing for code size, 2 instructions in common is enough if
639 // we don't have to split a block. At worst we will be introducing 1 new
640 // branch instruction, which is likely to be smaller than the 2
641 // instructions that would be deleted in the merge.
642 MachineFunction *MF = MBB1->getParent();
643 bool OptForSize =
644 MF->getFunction().hasOptSize() ||
645 (llvm::shouldOptimizeForSize(MBB1, PSI, &MBBFreqInfo) &&
646 llvm::shouldOptimizeForSize(MBB2, PSI, &MBBFreqInfo));
647 return EffectiveTailLen >= 2 && OptForSize &&
648 (FullBlockTail1 || FullBlockTail2);
649}
650
651unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
652 unsigned MinCommonTailLength,
653 MachineBasicBlock *SuccBB,
654 MachineBasicBlock *PredBB) {
655 unsigned maxCommonTailLength = 0U;
656 SameTails.clear();
657 MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
658 MPIterator HighestMPIter = std::prev(MergePotentials.end());
659 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
660 B = MergePotentials.begin();
661 CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
662 for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
663 unsigned CommonTailLen;
664 if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
665 MinCommonTailLength,
666 CommonTailLen, TrialBBI1, TrialBBI2,
667 SuccBB, PredBB,
668 EHScopeMembership,
669 AfterBlockPlacement, MBBFreqInfo, PSI)) {
670 if (CommonTailLen > maxCommonTailLength) {
671 SameTails.clear();
672 maxCommonTailLength = CommonTailLen;
673 HighestMPIter = CurMPIter;
674 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
675 }
676 if (HighestMPIter == CurMPIter &&
677 CommonTailLen == maxCommonTailLength)
678 SameTails.push_back(SameTailElt(I, TrialBBI2));
679 }
680 if (I == B)
681 break;
682 }
683 }
684 return maxCommonTailLength;
685}
686
687void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
688 MachineBasicBlock *SuccBB,
689 MachineBasicBlock *PredBB) {
690 MPIterator CurMPIter, B;
691 for (CurMPIter = std::prev(MergePotentials.end()),
692 B = MergePotentials.begin();
693 CurMPIter->getHash() == CurHash; --CurMPIter) {
694 // Put the unconditional branch back, if we need one.
695 MachineBasicBlock *CurMBB = CurMPIter->getBlock();
696 if (SuccBB && CurMBB != PredBB)
697 FixTail(CurMBB, SuccBB, TII);
698 if (CurMPIter == B)
699 break;
700 }
701 if (CurMPIter->getHash() != CurHash)
702 CurMPIter++;
703 MergePotentials.erase(CurMPIter, MergePotentials.end());
704}
705
706bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
707 MachineBasicBlock *SuccBB,
708 unsigned maxCommonTailLength,
709 unsigned &commonTailIndex) {
710 commonTailIndex = 0;
711 unsigned TimeEstimate = ~0U;
712 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
713 // Use PredBB if possible; that doesn't require a new branch.
714 if (SameTails[i].getBlock() == PredBB) {
715 commonTailIndex = i;
716 break;
717 }
718 // Otherwise, make a (fairly bogus) choice based on estimate of
719 // how long it will take the various blocks to execute.
720 unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
721 SameTails[i].getTailStartPos());
722 if (t <= TimeEstimate) {
723 TimeEstimate = t;
724 commonTailIndex = i;
725 }
726 }
727
729 SameTails[commonTailIndex].getTailStartPos();
730 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
731
732 LLVM_DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
733 << maxCommonTailLength);
734
735 // If the split block unconditionally falls-thru to SuccBB, it will be
736 // merged. In control flow terms it should then take SuccBB's name. e.g. If
737 // SuccBB is an inner loop, the common tail is still part of the inner loop.
738 const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
739 SuccBB->getBasicBlock() : MBB->getBasicBlock();
740 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
741 if (!newMBB) {
742 LLVM_DEBUG(dbgs() << "... failed!");
743 return false;
744 }
745
746 SameTails[commonTailIndex].setBlock(newMBB);
747 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
748
749 // If we split PredBB, newMBB is the new predecessor.
750 if (PredBB == MBB)
751 PredBB = newMBB;
752
753 return true;
754}
755
756static void
758 MachineBasicBlock &MBBCommon) {
759 MachineBasicBlock *MBB = MBBIStartPos->getParent();
760 // Note CommonTailLen does not necessarily matches the size of
761 // the common BB nor all its instructions because of debug
762 // instructions differences.
763 unsigned CommonTailLen = 0;
764 for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
765 ++CommonTailLen;
766
769 MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
770 MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
771
772 while (CommonTailLen--) {
773 assert(MBBI != MBBIE && "Reached BB end within common tail length!");
774 (void)MBBIE;
775
776 if (!countsAsInstruction(*MBBI)) {
777 ++MBBI;
778 continue;
779 }
780
781 while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
782 ++MBBICommon;
783
784 assert(MBBICommon != MBBIECommon &&
785 "Reached BB end within common tail length!");
786 assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");
787
788 // Merge MMOs from memory operations in the common block.
789 if (MBBICommon->mayLoadOrStore())
790 MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});
791 // Drop undef flags if they aren't present in all merged instructions.
792 for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
793 MachineOperand &MO = MBBICommon->getOperand(I);
794 if (MO.isReg() && MO.isUndef()) {
795 const MachineOperand &OtherMO = MBBI->getOperand(I);
796 if (!OtherMO.isUndef())
797 MO.setIsUndef(false);
798 }
799 }
800
801 ++MBBI;
802 ++MBBICommon;
803 }
804}
805
806void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
807 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
808
809 std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
810 for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
811 if (i != commonTailIndex) {
812 NextCommonInsts[i] = SameTails[i].getTailStartPos();
813 mergeOperations(SameTails[i].getTailStartPos(), *MBB);
814 } else {
815 assert(SameTails[i].getTailStartPos() == MBB->begin() &&
816 "MBB is not a common tail only block");
817 }
818 }
819
820 for (auto &MI : *MBB) {
822 continue;
823 DebugLoc DL = MI.getDebugLoc();
824 for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
825 if (i == commonTailIndex)
826 continue;
827
828 auto &Pos = NextCommonInsts[i];
829 assert(Pos != SameTails[i].getBlock()->end() &&
830 "Reached BB end within common tail");
831 while (!countsAsInstruction(*Pos)) {
832 ++Pos;
833 assert(Pos != SameTails[i].getBlock()->end() &&
834 "Reached BB end within common tail");
835 }
836 assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
837 DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
838 NextCommonInsts[i] = ++Pos;
839 }
840 MI.setDebugLoc(DL);
841 }
842
843 if (UpdateLiveIns) {
844 LivePhysRegs NewLiveIns(*TRI);
845 computeLiveIns(NewLiveIns, *MBB);
846 LiveRegs.init(*TRI);
847
848 // The flag merging may lead to some register uses no longer using the
849 // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
850 for (MachineBasicBlock *Pred : MBB->predecessors()) {
851 LiveRegs.clear();
852 LiveRegs.addLiveOuts(*Pred);
853 MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
854 for (Register Reg : NewLiveIns) {
855 if (!LiveRegs.available(*MRI, Reg))
856 continue;
857
858 // Skip the register if we are about to add one of its super registers.
859 // TODO: Common this up with the same logic in addLineIns().
860 if (any_of(TRI->superregs(Reg), [&](MCPhysReg SReg) {
861 return NewLiveIns.contains(SReg) && !MRI->isReserved(SReg);
862 }))
863 continue;
864
865 DebugLoc DL;
866 BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
867 Reg);
868 }
869 }
870
871 MBB->clearLiveIns();
872 addLiveIns(*MBB, NewLiveIns);
873 }
874}
875
876// See if any of the blocks in MergePotentials (which all have SuccBB as a
877// successor, or all have no successor if it is null) can be tail-merged.
878// If there is a successor, any blocks in MergePotentials that are not
879// tail-merged and are not immediately before Succ must have an unconditional
880// branch to Succ added (but the predecessor/successor lists need no
881// adjustment). The lone predecessor of Succ that falls through into Succ,
882// if any, is given in PredBB.
883// MinCommonTailLength - Except for the special cases below, tail-merge if
884// there are at least this many instructions in common.
885bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
886 MachineBasicBlock *PredBB,
887 unsigned MinCommonTailLength) {
888 bool MadeChange = false;
889
891 dbgs() << "\nTryTailMergeBlocks: ";
892 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
893 << printMBBReference(*MergePotentials[i].getBlock())
894 << (i == e - 1 ? "" : ", ");
895 dbgs() << "\n"; if (SuccBB) {
896 dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
897 if (PredBB)
898 dbgs() << " which has fall-through from "
899 << printMBBReference(*PredBB) << "\n";
900 } dbgs() << "Looking for common tails of at least "
901 << MinCommonTailLength << " instruction"
902 << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
903
904 // Sort by hash value so that blocks with identical end sequences sort
905 // together.
906 array_pod_sort(MergePotentials.begin(), MergePotentials.end());
907
908 // Walk through equivalence sets looking for actual exact matches.
909 while (MergePotentials.size() > 1) {
910 unsigned CurHash = MergePotentials.back().getHash();
911
912 // Build SameTails, identifying the set of blocks with this hash code
913 // and with the maximum number of instructions in common.
914 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
915 MinCommonTailLength,
916 SuccBB, PredBB);
917
918 // If we didn't find any pair that has at least MinCommonTailLength
919 // instructions in common, remove all blocks with this hash code and retry.
920 if (SameTails.empty()) {
921 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
922 continue;
923 }
924
925 // If one of the blocks is the entire common tail (and is not the entry
926 // block/an EH pad, which we can't jump to), we can treat all blocks with
927 // this same tail at once. Use PredBB if that is one of the possibilities,
928 // as that will not introduce any extra branches.
929 MachineBasicBlock *EntryBB =
930 &MergePotentials.front().getBlock()->getParent()->front();
931 unsigned commonTailIndex = SameTails.size();
932 // If there are two blocks, check to see if one can be made to fall through
933 // into the other.
934 if (SameTails.size() == 2 &&
935 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
936 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
937 commonTailIndex = 1;
938 else if (SameTails.size() == 2 &&
939 SameTails[1].getBlock()->isLayoutSuccessor(
940 SameTails[0].getBlock()) &&
941 SameTails[0].tailIsWholeBlock() &&
942 !SameTails[0].getBlock()->isEHPad())
943 commonTailIndex = 0;
944 else {
945 // Otherwise just pick one, favoring the fall-through predecessor if
946 // there is one.
947 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
948 MachineBasicBlock *MBB = SameTails[i].getBlock();
949 if ((MBB == EntryBB || MBB->isEHPad()) &&
950 SameTails[i].tailIsWholeBlock())
951 continue;
952 if (MBB == PredBB) {
953 commonTailIndex = i;
954 break;
955 }
956 if (SameTails[i].tailIsWholeBlock())
957 commonTailIndex = i;
958 }
959 }
960
961 if (commonTailIndex == SameTails.size() ||
962 (SameTails[commonTailIndex].getBlock() == PredBB &&
963 !SameTails[commonTailIndex].tailIsWholeBlock())) {
964 // None of the blocks consist entirely of the common tail.
965 // Split a block so that one does.
966 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
967 maxCommonTailLength, commonTailIndex)) {
968 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
969 continue;
970 }
971 }
972
973 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
974
975 // Recompute common tail MBB's edge weights and block frequency.
976 setCommonTailEdgeWeights(*MBB);
977
978 // Merge debug locations, MMOs and undef flags across identical instructions
979 // for common tail.
980 mergeCommonTails(commonTailIndex);
981
982 // MBB is common tail. Adjust all other BB's to jump to this one.
983 // Traversal must be forwards so erases work.
984 LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
985 << " for ");
986 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
987 if (commonTailIndex == i)
988 continue;
989 LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
990 << (i == e - 1 ? "" : ", "));
991 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
992 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
993 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
994 MergePotentials.erase(SameTails[i].getMPIter());
995 }
996 LLVM_DEBUG(dbgs() << "\n");
997 // We leave commonTailIndex in the worklist in case there are other blocks
998 // that match it with a smaller number of instructions.
999 MadeChange = true;
1000 }
1001 return MadeChange;
1002}
1003
1004bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
1005 bool MadeChange = false;
1006 if (!EnableTailMerge)
1007 return MadeChange;
1008
1009 // First find blocks with no successors.
1010 // Block placement may create new tail merging opportunities for these blocks.
1011 MergePotentials.clear();
1012 for (MachineBasicBlock &MBB : MF) {
1013 if (MergePotentials.size() == TailMergeThreshold)
1014 break;
1015 if (!TriedMerging.count(&MBB) && MBB.succ_empty())
1016 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
1017 }
1018
1019 // If this is a large problem, avoid visiting the same basic blocks
1020 // multiple times.
1021 if (MergePotentials.size() == TailMergeThreshold)
1022 for (const MergePotentialsElt &Elt : MergePotentials)
1023 TriedMerging.insert(Elt.getBlock());
1024
1025 // See if we can do any tail merging on those.
1026 if (MergePotentials.size() >= 2)
1027 MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
1028
1029 // Look at blocks (IBB) with multiple predecessors (PBB).
1030 // We change each predecessor to a canonical form, by
1031 // (1) temporarily removing any unconditional branch from the predecessor
1032 // to IBB, and
1033 // (2) alter conditional branches so they branch to the other block
1034 // not IBB; this may require adding back an unconditional branch to IBB
1035 // later, where there wasn't one coming in. E.g.
1036 // Bcc IBB
1037 // fallthrough to QBB
1038 // here becomes
1039 // Bncc QBB
1040 // with a conceptual B to IBB after that, which never actually exists.
1041 // With those changes, we see whether the predecessors' tails match,
1042 // and merge them if so. We change things out of canonical form and
1043 // back to the way they were later in the process. (OptimizeBranches
1044 // would undo some of this, but we can't use it, because we'd get into
1045 // a compile-time infinite loop repeatedly doing and undoing the same
1046 // transformations.)
1047
1048 for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1049 I != E; ++I) {
1050 if (I->pred_size() < 2) continue;
1052 MachineBasicBlock *IBB = &*I;
1053 MachineBasicBlock *PredBB = &*std::prev(I);
1054 MergePotentials.clear();
1055 MachineLoop *ML;
1056
1057 // Bail if merging after placement and IBB is the loop header because
1058 // -- If merging predecessors that belong to the same loop as IBB, the
1059 // common tail of merged predecessors may become the loop top if block
1060 // placement is called again and the predecessors may branch to this common
1061 // tail and require more branches. This can be relaxed if
1062 // MachineBlockPlacement::findBestLoopTop is more flexible.
1063 // --If merging predecessors that do not belong to the same loop as IBB, the
1064 // loop info of IBB's loop and the other loops may be affected. Calling the
1065 // block placement again may make big change to the layout and eliminate the
1066 // reason to do tail merging here.
1067 if (AfterBlockPlacement && MLI) {
1068 ML = MLI->getLoopFor(IBB);
1069 if (ML && IBB == ML->getHeader())
1070 continue;
1071 }
1072
1073 for (MachineBasicBlock *PBB : I->predecessors()) {
1074 if (MergePotentials.size() == TailMergeThreshold)
1075 break;
1076
1077 if (TriedMerging.count(PBB))
1078 continue;
1079
1080 // Skip blocks that loop to themselves, can't tail merge these.
1081 if (PBB == IBB)
1082 continue;
1083
1084 // Visit each predecessor only once.
1085 if (!UniquePreds.insert(PBB).second)
1086 continue;
1087
1088 // Skip blocks which may jump to a landing pad or jump from an asm blob.
1089 // Can't tail merge these.
1090 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1091 continue;
1092
1093 // After block placement, only consider predecessors that belong to the
1094 // same loop as IBB. The reason is the same as above when skipping loop
1095 // header.
1096 if (AfterBlockPlacement && MLI)
1097 if (ML != MLI->getLoopFor(PBB))
1098 continue;
1099
1100 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1102 if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
1103 // Failing case: IBB is the target of a cbr, and we cannot reverse the
1104 // branch.
1106 if (!Cond.empty() && TBB == IBB) {
1107 if (TII->reverseBranchCondition(NewCond))
1108 continue;
1109 // This is the QBB case described above
1110 if (!FBB) {
1111 auto Next = ++PBB->getIterator();
1112 if (Next != MF.end())
1113 FBB = &*Next;
1114 }
1115 }
1116
1117 // Remove the unconditional branch at the end, if any.
1118 if (TBB && (Cond.empty() || FBB)) {
1119 DebugLoc dl = PBB->findBranchDebugLoc();
1120 TII->removeBranch(*PBB);
1121 if (!Cond.empty())
1122 // reinsert conditional branch only, for now
1123 TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
1124 NewCond, dl);
1125 }
1126
1127 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
1128 }
1129 }
1130
1131 // If this is a large problem, avoid visiting the same basic blocks multiple
1132 // times.
1133 if (MergePotentials.size() == TailMergeThreshold)
1134 for (MergePotentialsElt &Elt : MergePotentials)
1135 TriedMerging.insert(Elt.getBlock());
1136
1137 if (MergePotentials.size() >= 2)
1138 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1139
1140 // Reinsert an unconditional branch if needed. The 1 below can occur as a
1141 // result of removing blocks in TryTailMergeBlocks.
1142 PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
1143 if (MergePotentials.size() == 1 &&
1144 MergePotentials.begin()->getBlock() != PredBB)
1145 FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1146 }
1147
1148 return MadeChange;
1149}
1150
1151void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
1152 SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
1153 BlockFrequency AccumulatedMBBFreq;
1154
1155 // Aggregate edge frequency of successor edge j:
1156 // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
1157 // where bb is a basic block that is in SameTails.
1158 for (const auto &Src : SameTails) {
1159 const MachineBasicBlock *SrcMBB = Src.getBlock();
1160 BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
1161 AccumulatedMBBFreq += BlockFreq;
1162
1163 // It is not necessary to recompute edge weights if TailBB has less than two
1164 // successors.
1165 if (TailMBB.succ_size() <= 1)
1166 continue;
1167
1168 auto EdgeFreq = EdgeFreqLs.begin();
1169
1170 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1171 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1172 *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
1173 }
1174
1175 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1176
1177 if (TailMBB.succ_size() <= 1)
1178 return;
1179
1180 auto SumEdgeFreq =
1181 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
1182 .getFrequency();
1183 auto EdgeFreq = EdgeFreqLs.begin();
1184
1185 if (SumEdgeFreq > 0) {
1186 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1187 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1189 EdgeFreq->getFrequency(), SumEdgeFreq);
1190 TailMBB.setSuccProbability(SuccI, Prob);
1191 }
1192 }
1193}
1194
1195//===----------------------------------------------------------------------===//
1196// Branch Optimization
1197//===----------------------------------------------------------------------===//
1198
1199bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
1200 bool MadeChange = false;
1201
1202 // Make sure blocks are numbered in order
1203 MF.RenumberBlocks();
1204 // Renumbering blocks alters EH scope membership, recalculate it.
1205 EHScopeMembership = getEHScopeMembership(MF);
1206
1207 for (MachineBasicBlock &MBB :
1209 MadeChange |= OptimizeBlock(&MBB);
1210
1211 // If it is dead, remove it.
1213 RemoveDeadBlock(&MBB);
1214 MadeChange = true;
1215 ++NumDeadBlocks;
1216 }
1217 }
1218
1219 return MadeChange;
1220}
1221
1222// Blocks should be considered empty if they contain only debug info;
1223// else the debug info would affect codegen.
1225 return MBB->getFirstNonDebugInstr(true) == MBB->end();
1226}
1227
1228// Blocks with only debug info and branches should be considered the same
1229// as blocks with only branches.
1232 assert(I != MBB->end() && "empty block!");
1233 return I->isBranch();
1234}
1235
1236/// IsBetterFallthrough - Return true if it would be clearly better to
1237/// fall-through to MBB1 than to fall through into MBB2. This has to return
1238/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1239/// result in infinite loops.
1241 MachineBasicBlock *MBB2) {
1242 assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
1243
1244 // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1245 // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1246 // optimize branches that branch to either a return block or an assert block
1247 // into a fallthrough to the return.
1250 if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1251 return false;
1252
1253 // If there is a clear successor ordering we make sure that one block
1254 // will fall through to the next
1255 if (MBB1->isSuccessor(MBB2)) return true;
1256 if (MBB2->isSuccessor(MBB1)) return false;
1257
1258 return MBB2I->isCall() && !MBB1I->isCall();
1259}
1260
1261/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1262/// instructions on the block.
1265 if (I != MBB.end() && I->isBranch())
1266 return I->getDebugLoc();
1267 return DebugLoc();
1268}
1269
1272 MachineBasicBlock &PredMBB) {
1273 auto InsertBefore = PredMBB.getFirstTerminator();
1274 for (MachineInstr &MI : MBB.instrs())
1275 if (MI.isDebugInstr()) {
1276 TII->duplicate(PredMBB, InsertBefore, MI);
1277 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
1278 << MI);
1279 }
1280}
1281
1284 MachineBasicBlock &SuccMBB) {
1285 auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1286 for (MachineInstr &MI : MBB.instrs())
1287 if (MI.isDebugInstr()) {
1288 TII->duplicate(SuccMBB, InsertBefore, MI);
1289 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
1290 << MI);
1291 }
1292}
1293
1294// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1295// a basic block is removed we would lose the debug information unless we have
1296// copied the information to a predecessor/successor.
1297//
1298// TODO: This function only handles some simple cases. An alternative would be
1299// to run a heavier analysis, such as the LiveDebugValues pass, before we do
1300// branch folding.
1303 assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
1304 // If this MBB is the only predecessor of a successor it is legal to copy
1305 // DBG_VALUE instructions to the beginning of the successor.
1306 for (MachineBasicBlock *SuccBB : MBB.successors())
1307 if (SuccBB->pred_size() == 1)
1308 copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1309 // If this MBB is the only successor of a predecessor it is legal to copy the
1310 // DBG_VALUE instructions to the end of the predecessor (just before the
1311 // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1312 for (MachineBasicBlock *PredBB : MBB.predecessors())
1313 if (PredBB->succ_size() == 1)
1315}
1316
1317bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1318 bool MadeChange = false;
1319 MachineFunction &MF = *MBB->getParent();
1320ReoptimizeBlock:
1321
1322 MachineFunction::iterator FallThrough = MBB->getIterator();
1323 ++FallThrough;
1324
1325 // Make sure MBB and FallThrough belong to the same EH scope.
1326 bool SameEHScope = true;
1327 if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1328 auto MBBEHScope = EHScopeMembership.find(MBB);
1329 assert(MBBEHScope != EHScopeMembership.end());
1330 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1331 assert(FallThroughEHScope != EHScopeMembership.end());
1332 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1333 }
1334
1335 // Analyze the branch in the current block. As a side-effect, this may cause
1336 // the block to become empty.
1337 MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1339 bool CurUnAnalyzable =
1340 TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1341
1342 // If this block is empty, make everyone use its fall-through, not the block
1343 // explicitly. Landing pads should not do this since the landing-pad table
1344 // points to this block. Blocks with their addresses taken shouldn't be
1345 // optimized away.
1346 if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
1347 SameEHScope) {
1349 // Dead block? Leave for cleanup later.
1350 if (MBB->pred_empty()) return MadeChange;
1351
1352 if (FallThrough == MF.end()) {
1353 // TODO: Simplify preds to not branch here if possible!
1354 } else if (FallThrough->isEHPad()) {
1355 // Don't rewrite to a landing pad fallthough. That could lead to the case
1356 // where a BB jumps to more than one landing pad.
1357 // TODO: Is it ever worth rewriting predecessors which don't already
1358 // jump to a landing pad, and so can safely jump to the fallthrough?
1359 } else if (MBB->isSuccessor(&*FallThrough)) {
1360 // Rewrite all predecessors of the old block to go to the fallthrough
1361 // instead.
1362 while (!MBB->pred_empty()) {
1363 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1364 Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1365 }
1366 // If MBB was the target of a jump table, update jump tables to go to the
1367 // fallthrough instead.
1368 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1369 MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1370 MadeChange = true;
1371 }
1372 return MadeChange;
1373 }
1374
1375 // Check to see if we can simplify the terminator of the block before this
1376 // one.
1377 MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1378
1379 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1381 bool PriorUnAnalyzable =
1382 TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
1383 if (!PriorUnAnalyzable) {
1384 // If the previous branch is conditional and both conditions go to the same
1385 // destination, remove the branch, replacing it with an unconditional one or
1386 // a fall-through.
1387 if (PriorTBB && PriorTBB == PriorFBB) {
1388 DebugLoc dl = getBranchDebugLoc(PrevBB);
1389 TII->removeBranch(PrevBB);
1390 PriorCond.clear();
1391 if (PriorTBB != MBB)
1392 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1393 MadeChange = true;
1394 ++NumBranchOpts;
1395 goto ReoptimizeBlock;
1396 }
1397
1398 // If the previous block unconditionally falls through to this block and
1399 // this block has no other predecessors, move the contents of this block
1400 // into the prior block. This doesn't usually happen when SimplifyCFG
1401 // has been used, but it can happen if tail merging splits a fall-through
1402 // predecessor of a block.
1403 // This has to check PrevBB->succ_size() because EH edges are ignored by
1404 // analyzeBranch.
1405 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1406 PrevBB.succ_size() == 1 &&
1407 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1408 LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1409 << "From MBB: " << *MBB);
1410 // Remove redundant DBG_VALUEs first.
1411 if (!PrevBB.empty()) {
1412 MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1413 --PrevBBIter;
1415 // Check if DBG_VALUE at the end of PrevBB is identical to the
1416 // DBG_VALUE at the beginning of MBB.
1417 while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1418 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1419 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1420 break;
1421 MachineInstr &DuplicateDbg = *MBBIter;
1422 ++MBBIter; -- PrevBBIter;
1423 DuplicateDbg.eraseFromParent();
1424 }
1425 }
1426 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1427 PrevBB.removeSuccessor(PrevBB.succ_begin());
1428 assert(PrevBB.succ_empty());
1429 PrevBB.transferSuccessors(MBB);
1430 MadeChange = true;
1431 return MadeChange;
1432 }
1433
1434 // If the previous branch *only* branches to *this* block (conditional or
1435 // not) remove the branch.
1436 if (PriorTBB == MBB && !PriorFBB) {
1437 TII->removeBranch(PrevBB);
1438 MadeChange = true;
1439 ++NumBranchOpts;
1440 goto ReoptimizeBlock;
1441 }
1442
1443 // If the prior block branches somewhere else on the condition and here if
1444 // the condition is false, remove the uncond second branch.
1445 if (PriorFBB == MBB) {
1446 DebugLoc dl = getBranchDebugLoc(PrevBB);
1447 TII->removeBranch(PrevBB);
1448 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1449 MadeChange = true;
1450 ++NumBranchOpts;
1451 goto ReoptimizeBlock;
1452 }
1453
1454 // If the prior block branches here on true and somewhere else on false, and
1455 // if the branch condition is reversible, reverse the branch to create a
1456 // fall-through.
1457 if (PriorTBB == MBB) {
1458 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1459 if (!TII->reverseBranchCondition(NewPriorCond)) {
1460 DebugLoc dl = getBranchDebugLoc(PrevBB);
1461 TII->removeBranch(PrevBB);
1462 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1463 MadeChange = true;
1464 ++NumBranchOpts;
1465 goto ReoptimizeBlock;
1466 }
1467 }
1468
1469 // If this block has no successors (e.g. it is a return block or ends with
1470 // a call to a no-return function like abort or __cxa_throw) and if the pred
1471 // falls through into this block, and if it would otherwise fall through
1472 // into the block after this, move this block to the end of the function.
1473 //
1474 // We consider it more likely that execution will stay in the function (e.g.
1475 // due to loops) than it is to exit it. This asserts in loops etc, moving
1476 // the assert condition out of the loop body.
1477 if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
1478 MachineFunction::iterator(PriorTBB) == FallThrough &&
1479 !MBB->canFallThrough()) {
1480 bool DoTransform = true;
1481
1482 // We have to be careful that the succs of PredBB aren't both no-successor
1483 // blocks. If neither have successors and if PredBB is the second from
1484 // last block in the function, we'd just keep swapping the two blocks for
1485 // last. Only do the swap if one is clearly better to fall through than
1486 // the other.
1487 if (FallThrough == --MF.end() &&
1488 !IsBetterFallthrough(PriorTBB, MBB))
1489 DoTransform = false;
1490
1491 if (DoTransform) {
1492 // Reverse the branch so we will fall through on the previous true cond.
1493 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1494 if (!TII->reverseBranchCondition(NewPriorCond)) {
1495 LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1496 << "To make fallthrough to: " << *PriorTBB << "\n");
1497
1498 DebugLoc dl = getBranchDebugLoc(PrevBB);
1499 TII->removeBranch(PrevBB);
1500 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1501
1502 // Move this block to the end of the function.
1503 MBB->moveAfter(&MF.back());
1504 MadeChange = true;
1505 ++NumBranchOpts;
1506 return MadeChange;
1507 }
1508 }
1509 }
1510 }
1511
1512 if (!IsEmptyBlock(MBB)) {
1514 if (TII->isUnconditionalTailCall(TailCall)) {
1516 for (auto &Pred : MBB->predecessors()) {
1517 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1519 bool PredAnalyzable =
1520 !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1521
1522 // Only eliminate if MBB == TBB (Taken Basic Block)
1523 if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1524 PredTBB != PredFBB) {
1525 // The predecessor has a conditional branch to this block which
1526 // consists of only a tail call. Try to fold the tail call into the
1527 // conditional branch.
1528 if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1529 // TODO: It would be nice if analyzeBranch() could provide a pointer
1530 // to the branch instruction so replaceBranchWithTailCall() doesn't
1531 // have to search for it.
1532 TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1533 PredsChanged.push_back(Pred);
1534 }
1535 }
1536 // If the predecessor is falling through to this block, we could reverse
1537 // the branch condition and fold the tail call into that. However, after
1538 // that we might have to re-arrange the CFG to fall through to the other
1539 // block and there is a high risk of regressing code size rather than
1540 // improving it.
1541 }
1542 if (!PredsChanged.empty()) {
1543 NumTailCalls += PredsChanged.size();
1544 for (auto &Pred : PredsChanged)
1545 Pred->removeSuccessor(MBB);
1546
1547 return true;
1548 }
1549 }
1550 }
1551
1552 if (!CurUnAnalyzable) {
1553 // If this is a two-way branch, and the FBB branches to this block, reverse
1554 // the condition so the single-basic-block loop is faster. Instead of:
1555 // Loop: xxx; jcc Out; jmp Loop
1556 // we want:
1557 // Loop: xxx; jncc Loop; jmp Out
1558 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1559 SmallVector<MachineOperand, 4> NewCond(CurCond);
1560 if (!TII->reverseBranchCondition(NewCond)) {
1562 TII->removeBranch(*MBB);
1563 TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1564 MadeChange = true;
1565 ++NumBranchOpts;
1566 goto ReoptimizeBlock;
1567 }
1568 }
1569
1570 // If this branch is the only thing in its block, see if we can forward
1571 // other blocks across it.
1572 if (CurTBB && CurCond.empty() && !CurFBB &&
1573 IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1574 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1576 // This block may contain just an unconditional branch. Because there can
1577 // be 'non-branch terminators' in the block, try removing the branch and
1578 // then seeing if the block is empty.
1579 TII->removeBranch(*MBB);
1580 // If the only things remaining in the block are debug info, remove these
1581 // as well, so this will behave the same as an empty block in non-debug
1582 // mode.
1583 if (IsEmptyBlock(MBB)) {
1584 // Make the block empty, losing the debug info (we could probably
1585 // improve this in some cases.)
1586 MBB->erase(MBB->begin(), MBB->end());
1587 }
1588 // If this block is just an unconditional branch to CurTBB, we can
1589 // usually completely eliminate the block. The only case we cannot
1590 // completely eliminate the block is when the block before this one
1591 // falls through into MBB and we can't understand the prior block's branch
1592 // condition.
1593 if (MBB->empty()) {
1594 bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1595 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1596 !PrevBB.isSuccessor(MBB)) {
1597 // If the prior block falls through into us, turn it into an
1598 // explicit branch to us to make updates simpler.
1599 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1600 PriorTBB != MBB && PriorFBB != MBB) {
1601 if (!PriorTBB) {
1602 assert(PriorCond.empty() && !PriorFBB &&
1603 "Bad branch analysis");
1604 PriorTBB = MBB;
1605 } else {
1606 assert(!PriorFBB && "Machine CFG out of date!");
1607 PriorFBB = MBB;
1608 }
1609 DebugLoc pdl = getBranchDebugLoc(PrevBB);
1610 TII->removeBranch(PrevBB);
1611 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1612 }
1613
1614 // Iterate through all the predecessors, revectoring each in-turn.
1615 size_t PI = 0;
1616 bool DidChange = false;
1617 bool HasBranchToSelf = false;
1618 while(PI != MBB->pred_size()) {
1619 MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1620 if (PMBB == MBB) {
1621 // If this block has an uncond branch to itself, leave it.
1622 ++PI;
1623 HasBranchToSelf = true;
1624 } else {
1625 DidChange = true;
1626 PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1627 // If this change resulted in PMBB ending in a conditional
1628 // branch where both conditions go to the same destination,
1629 // change this to an unconditional branch.
1630 MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1632 bool NewCurUnAnalyzable = TII->analyzeBranch(
1633 *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1634 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1635 DebugLoc pdl = getBranchDebugLoc(*PMBB);
1636 TII->removeBranch(*PMBB);
1637 NewCurCond.clear();
1638 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1639 MadeChange = true;
1640 ++NumBranchOpts;
1641 }
1642 }
1643 }
1644
1645 // Change any jumptables to go to the new MBB.
1646 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1647 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1648 if (DidChange) {
1649 ++NumBranchOpts;
1650 MadeChange = true;
1651 if (!HasBranchToSelf) return MadeChange;
1652 }
1653 }
1654 }
1655
1656 // Add the branch back if the block is more than just an uncond branch.
1657 TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1658 }
1659 }
1660
1661 // If the prior block doesn't fall through into this block, and if this
1662 // block doesn't fall through into some other block, see if we can find a
1663 // place to move this block where a fall-through will happen.
1664 if (!PrevBB.canFallThrough()) {
1665 // Now we know that there was no fall-through into this block, check to
1666 // see if it has a fall-through into its successor.
1667 bool CurFallsThru = MBB->canFallThrough();
1668
1669 if (!MBB->isEHPad()) {
1670 // Check all the predecessors of this block. If one of them has no fall
1671 // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1672 // block, move this block right after it.
1673 for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1674 // Analyze the branch at the end of the pred.
1675 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1677 if (PredBB != MBB && !PredBB->canFallThrough() &&
1678 !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1679 (PredTBB == MBB || PredFBB == MBB) &&
1680 (!CurFallsThru || !CurTBB || !CurFBB) &&
1681 (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1682 // If the current block doesn't fall through, just move it.
1683 // If the current block can fall through and does not end with a
1684 // conditional branch, we need to append an unconditional jump to
1685 // the (current) next block. To avoid a possible compile-time
1686 // infinite loop, move blocks only backward in this case.
1687 // Also, if there are already 2 branches here, we cannot add a third;
1688 // this means we have the case
1689 // Bcc next
1690 // B elsewhere
1691 // next:
1692 if (CurFallsThru) {
1693 MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1694 CurCond.clear();
1695 TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1696 }
1697 MBB->moveAfter(PredBB);
1698 MadeChange = true;
1699 goto ReoptimizeBlock;
1700 }
1701 }
1702 }
1703
1704 if (!CurFallsThru) {
1705 // Check analyzable branch-successors to see if we can move this block
1706 // before one.
1707 if (!CurUnAnalyzable) {
1708 for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1709 if (!SuccBB)
1710 continue;
1711 // Analyze the branch at the end of the block before the succ.
1712 MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1713
1714 // If this block doesn't already fall-through to that successor, and
1715 // if the succ doesn't already have a block that can fall through into
1716 // it, we can arrange for the fallthrough to happen.
1717 if (SuccBB != MBB && &*SuccPrev != MBB &&
1718 !SuccPrev->canFallThrough()) {
1719 MBB->moveBefore(SuccBB);
1720 MadeChange = true;
1721 goto ReoptimizeBlock;
1722 }
1723 }
1724 }
1725
1726 // Okay, there is no really great place to put this block. If, however,
1727 // the block before this one would be a fall-through if this block were
1728 // removed, move this block to the end of the function. There is no real
1729 // advantage in "falling through" to an EH block, so we don't want to
1730 // perform this transformation for that case.
1731 //
1732 // Also, Windows EH introduced the possibility of an arbitrary number of
1733 // successors to a given block. The analyzeBranch call does not consider
1734 // exception handling and so we can get in a state where a block
1735 // containing a call is followed by multiple EH blocks that would be
1736 // rotated infinitely at the end of the function if the transformation
1737 // below were performed for EH "FallThrough" blocks. Therefore, even if
1738 // that appears not to be happening anymore, we should assume that it is
1739 // possible and not remove the "!FallThrough()->isEHPad" condition below.
1740 MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1742 if (FallThrough != MF.end() &&
1743 !FallThrough->isEHPad() &&
1744 !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1745 PrevBB.isSuccessor(&*FallThrough)) {
1746 MBB->moveAfter(&MF.back());
1747 MadeChange = true;
1748 return MadeChange;
1749 }
1750 }
1751 }
1752
1753 return MadeChange;
1754}
1755
1756//===----------------------------------------------------------------------===//
1757// Hoist Common Code
1758//===----------------------------------------------------------------------===//
1759
1760bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1761 bool MadeChange = false;
1763 MadeChange |= HoistCommonCodeInSuccs(&MBB);
1764
1765 return MadeChange;
1766}
1767
1768/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1769/// its 'true' successor.
1771 MachineBasicBlock *TrueBB) {
1772 for (MachineBasicBlock *SuccBB : BB->successors())
1773 if (SuccBB != TrueBB)
1774 return SuccBB;
1775 return nullptr;
1776}
1777
1778template <class Container>
1780 Container &Set) {
1781 if (Reg.isPhysical()) {
1782 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1783 Set.insert(*AI);
1784 } else {
1785 Set.insert(Reg);
1786 }
1787}
1788
1789/// findHoistingInsertPosAndDeps - Find the location to move common instructions
1790/// in successors to. The location is usually just before the terminator,
1791/// however if the terminator is a conditional branch and its previous
1792/// instruction is the flag setting instruction, the previous instruction is
1793/// the preferred location. This function also gathers uses and defs of the
1794/// instructions from the insertion point to the end of the block. The data is
1795/// used by HoistCommonCodeInSuccs to ensure safety.
1796static
1798 const TargetInstrInfo *TII,
1799 const TargetRegisterInfo *TRI,
1801 SmallSet<Register, 4> &Defs) {
1803 if (!TII->isUnpredicatedTerminator(*Loc))
1804 return MBB->end();
1805
1806 for (const MachineOperand &MO : Loc->operands()) {
1807 if (!MO.isReg())
1808 continue;
1809 Register Reg = MO.getReg();
1810 if (!Reg)
1811 continue;
1812 if (MO.isUse()) {
1814 } else {
1815 if (!MO.isDead())
1816 // Don't try to hoist code in the rare case the terminator defines a
1817 // register that is later used.
1818 return MBB->end();
1819
1820 // If the terminator defines a register, make sure we don't hoist
1821 // the instruction whose def might be clobbered by the terminator.
1822 addRegAndItsAliases(Reg, TRI, Defs);
1823 }
1824 }
1825
1826 if (Uses.empty())
1827 return Loc;
1828 // If the terminator is the only instruction in the block and Uses is not
1829 // empty (or we would have returned above), we can still safely hoist
1830 // instructions just before the terminator as long as the Defs/Uses are not
1831 // violated (which is checked in HoistCommonCodeInSuccs).
1832 if (Loc == MBB->begin())
1833 return Loc;
1834
1835 // The terminator is probably a conditional branch, try not to separate the
1836 // branch from condition setting instruction.
1838
1839 bool IsDef = false;
1840 for (const MachineOperand &MO : PI->operands()) {
1841 // If PI has a regmask operand, it is probably a call. Separate away.
1842 if (MO.isRegMask())
1843 return Loc;
1844 if (!MO.isReg() || MO.isUse())
1845 continue;
1846 Register Reg = MO.getReg();
1847 if (!Reg)
1848 continue;
1849 if (Uses.count(Reg)) {
1850 IsDef = true;
1851 break;
1852 }
1853 }
1854 if (!IsDef)
1855 // The condition setting instruction is not just before the conditional
1856 // branch.
1857 return Loc;
1858
1859 // Be conservative, don't insert instruction above something that may have
1860 // side-effects. And since it's potentially bad to separate flag setting
1861 // instruction from the conditional branch, just abort the optimization
1862 // completely.
1863 // Also avoid moving code above predicated instruction since it's hard to
1864 // reason about register liveness with predicated instruction.
1865 bool DontMoveAcrossStore = true;
1866 if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1867 return MBB->end();
1868
1869 // Find out what registers are live. Note this routine is ignoring other live
1870 // registers which are only used by instructions in successor blocks.
1871 for (const MachineOperand &MO : PI->operands()) {
1872 if (!MO.isReg())
1873 continue;
1874 Register Reg = MO.getReg();
1875 if (!Reg)
1876 continue;
1877 if (MO.isUse()) {
1879 } else {
1880 if (Uses.erase(Reg)) {
1881 if (Reg.isPhysical()) {
1882 for (MCPhysReg SubReg : TRI->subregs(Reg))
1883 Uses.erase(SubReg); // Use sub-registers to be conservative
1884 }
1885 }
1886 addRegAndItsAliases(Reg, TRI, Defs);
1887 }
1888 }
1889
1890 return PI;
1891}
1892
1893bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1894 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1896 if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1897 return false;
1898
1899 if (!FBB) FBB = findFalseBlock(MBB, TBB);
1900 if (!FBB)
1901 // Malformed bcc? True and false blocks are the same?
1902 return false;
1903
1904 // Restrict the optimization to cases where MBB is the only predecessor,
1905 // it is an obvious win.
1906 if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1907 return false;
1908
1909 // Find a suitable position to hoist the common instructions to. Also figure
1910 // out which registers are used or defined by instructions from the insertion
1911 // point to the end of the block.
1914 findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1915 if (Loc == MBB->end())
1916 return false;
1917
1918 bool HasDups = false;
1919 SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1921 MachineBasicBlock::iterator FIB = FBB->begin();
1923 MachineBasicBlock::iterator FIE = FBB->end();
1924 while (TIB != TIE && FIB != FIE) {
1925 // Skip dbg_value instructions. These do not count.
1926 TIB = skipDebugInstructionsForward(TIB, TIE, false);
1927 FIB = skipDebugInstructionsForward(FIB, FIE, false);
1928 if (TIB == TIE || FIB == FIE)
1929 break;
1930
1931 if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1932 break;
1933
1934 if (TII->isPredicated(*TIB))
1935 // Hard to reason about register liveness with predicated instruction.
1936 break;
1937
1938 bool IsSafe = true;
1939 for (MachineOperand &MO : TIB->operands()) {
1940 // Don't attempt to hoist instructions with register masks.
1941 if (MO.isRegMask()) {
1942 IsSafe = false;
1943 break;
1944 }
1945 if (!MO.isReg())
1946 continue;
1947 Register Reg = MO.getReg();
1948 if (!Reg)
1949 continue;
1950 if (MO.isDef()) {
1951 if (Uses.count(Reg)) {
1952 // Avoid clobbering a register that's used by the instruction at
1953 // the point of insertion.
1954 IsSafe = false;
1955 break;
1956 }
1957
1958 if (Defs.count(Reg) && !MO.isDead()) {
1959 // Don't hoist the instruction if the def would be clobber by the
1960 // instruction at the point insertion. FIXME: This is overly
1961 // conservative. It should be possible to hoist the instructions
1962 // in BB2 in the following example:
1963 // BB1:
1964 // r1, eflag = op1 r2, r3
1965 // brcc eflag
1966 //
1967 // BB2:
1968 // r1 = op2, ...
1969 // = op3, killed r1
1970 IsSafe = false;
1971 break;
1972 }
1973 } else if (!ActiveDefsSet.count(Reg)) {
1974 if (Defs.count(Reg)) {
1975 // Use is defined by the instruction at the point of insertion.
1976 IsSafe = false;
1977 break;
1978 }
1979
1980 if (MO.isKill() && Uses.count(Reg))
1981 // Kills a register that's read by the instruction at the point of
1982 // insertion. Remove the kill marker.
1983 MO.setIsKill(false);
1984 }
1985 }
1986 if (!IsSafe)
1987 break;
1988
1989 bool DontMoveAcrossStore = true;
1990 if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1991 break;
1992
1993 // Remove kills from ActiveDefsSet, these registers had short live ranges.
1994 for (const MachineOperand &MO : TIB->all_uses()) {
1995 if (!MO.isKill())
1996 continue;
1997 Register Reg = MO.getReg();
1998 if (!Reg)
1999 continue;
2000 if (!AllDefsSet.count(Reg)) {
2001 continue;
2002 }
2003 if (Reg.isPhysical()) {
2004 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2005 ActiveDefsSet.erase(*AI);
2006 } else {
2007 ActiveDefsSet.erase(Reg);
2008 }
2009 }
2010
2011 // Track local defs so we can update liveins.
2012 for (const MachineOperand &MO : TIB->all_defs()) {
2013 if (MO.isDead())
2014 continue;
2015 Register Reg = MO.getReg();
2016 if (!Reg || Reg.isVirtual())
2017 continue;
2018 addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2019 addRegAndItsAliases(Reg, TRI, AllDefsSet);
2020 }
2021
2022 HasDups = true;
2023 ++TIB;
2024 ++FIB;
2025 }
2026
2027 if (!HasDups)
2028 return false;
2029
2030 MBB->splice(Loc, TBB, TBB->begin(), TIB);
2031 FBB->erase(FBB->begin(), FIB);
2032
2033 if (UpdateLiveIns) {
2035 recomputeLiveIns(*FBB);
2036 }
2037
2038 ++NumHoist;
2039 return true;
2040}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
This file implements the BitVector class.
static unsigned EstimateRuntime(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2)
Given two machine basic blocks, return the number of instructions they actually have in common togeth...
static MachineBasicBlock * findFalseBlock(MachineBasicBlock *BB, MachineBasicBlock *TrueBB)
findFalseBlock - BB has a fallthrough.
static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB)
static unsigned HashMachineInstr(const MachineInstr &MI)
HashMachineInstr - Compute a hash value for MI and its operands.
static bool countsAsInstruction(const MachineInstr &MI)
Whether MI should be counted as an instruction when calculating common tail.
static unsigned CountTerminators(MachineBasicBlock *MBB, MachineBasicBlock::iterator &I)
CountTerminators - Count the number of terminators in the given block and set I to the position of th...
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII, MachineBasicBlock &MBB)
static MachineBasicBlock::iterator skipBackwardPastNonInstructions(MachineBasicBlock::iterator I, MachineBasicBlock *MBB)
Iterate backwards from the given iterator I, towards the beginning of the block.
static cl::opt< unsigned > TailMergeThreshold("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden)
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII)
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI, Container &Set)
static cl::opt< cl::boolOrDefault > FlagEnableTailMerge("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden)
static cl::opt< unsigned > TailMergeSize("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden)
static bool IsEmptyBlock(MachineBasicBlock *MBB)
static bool ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, unsigned MinCommonTailLength, unsigned &CommonTailLen, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB, MachineBasicBlock *PredBB, DenseMap< const MachineBasicBlock *, int > &EHScopeMembership, bool AfterPlacement, MBFIWrapper &MBBFreqInfo, ProfileSummaryInfo *PSI)
ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be pr...
static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB)
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB)
static bool IsBetterFallthrough(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2)
IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall ...
#define DEBUG_TYPE
static unsigned HashEndOfMBB(const MachineBasicBlock &MBB)
HashEndOfMBB - Hash the last instruction in the MBB.
static void mergeOperations(MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon)
static MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< Register, 4 > &Uses, SmallSet< Register, 4 > &Defs)
findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to.
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB)
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Rewrite Partial Register Uses
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallSet 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
Target-Independent Code Generator Pass Configuration Options pass.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & set()
Definition: BitVector.h:351
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:159
bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii, const TargetRegisterInfo *tri, MachineLoopInfo *mli=nullptr, bool AfterPlacement=false)
Perhaps branch folding, tail merging and other CFG optimizations on the given function.
BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist, MBFIWrapper &FreqInfo, const MachineBranchProbabilityInfo &ProbInfo, ProfileSummaryInfo *PSI, unsigned MinTailLength=0)
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
static DILocation * getMergedLocation(DILocation *LocA, DILocation *LocB)
When two instructions are combined into a single instruction we also need to combine the original loc...
This class represents an Operation in the Expression.
A debug info location.
Definition: DebugLoc.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool empty() const
Definition: DenseMap.h:98
iterator end()
Definition: DenseMap.h:84
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:677
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const override
Reverses the branch condition of the specified condition list, returning false on success and true if...
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
void clear()
Clears the set.
Definition: LivePhysRegs.h:75
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:68
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
Definition: MBFIWrapper.cpp:20
void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F)
Definition: MBFIWrapper.cpp:29
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
MCRegAliasIterator enumerates all registers aliasing Reg.
iterator_range< MCSuperRegIterator > superregs(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, excluding Reg.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
reverse_iterator rend()
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
iterator_range< livein_iterator > liveins() const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator SkipPHIsAndLabels(iterator I)
Return the first instruction in MBB after I that is not a PHI or a label.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
bool canFallThrough()
Return true if the block can implicitly transfer control to the block after it by falling off the end...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
iterator getFirstNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the first non-debug instruction in the basic block, or end().
void clearLiveIns()
Clear live in list.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...
bool isLayoutSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB will be emitted immediately after this block, such that if this bloc...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
bool isMachineBlockAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
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 '...
void moveAfter(MachineBasicBlock *NewBefore)
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & back() const
void eraseCallSiteInfo(const MachineInstr *MI)
Following functions update call site info.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineJumpTableInfo * getJumpTableInfo() const
getJumpTableInfo - Return the jump table info object for the current function.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void erase(iterator MBBI)
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
Definition: MachineInstr.h:68
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:905
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:930
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
bool isIndirectBranch(QueryType Type=AnyInBundle) const
Return true if this is an indirect branch, such as a branch through a register.
Definition: MachineInstr.h:953
void RemoveJumpTable(unsigned Idx)
RemoveJumpTable - Mark the specific index as being dead.
const std::vector< MachineJumpTableEntry > & getJumpTables() const
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setIsUndef(bool Val=true)
@ MO_Immediate
Immediate operand.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
@ MO_GlobalAddress
Address of a global value.
@ MO_MachineBasicBlock
MachineBasicBlock reference.
@ MO_FrameIndex
Abstract Stack Frame Index.
@ MO_Register
Register operand.
@ MO_ExternalSymbol
Name of external global symbol.
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool erase(const T &V)
Definition: SmallSet.h:207
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
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
TargetInstrInfo - Interface to description of machine instruction set.
virtual bool reverseBranchCondition(SmallVectorImpl< MachineOperand > &Cond) const
Reverses the branch condition of the specified condition list, returning false on success and true if...
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 bool canMakeTailCallConditional(SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Returns true if the tail call can be made conditional on BranchCond.
virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, MachineBasicBlock *NewDest) const
Delete the instruction OldInst and everything after it, replacing it with an unconditional branch to ...
virtual bool isUnconditionalTailCall(const MachineInstr &MI) const
Returns true if MI is an unconditional tail call.
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 bool isPredicated(const MachineInstr &MI) const
Returns true if the instruction is already predicated.
virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB, SmallVectorImpl< MachineOperand > &Cond, const MachineInstr &TailCall) const
Replace the conditional branch in MBB with a conditional tail call.
virtual bool isLegalToSplitMBBAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI) const
Return true if it's legal to split the given basic block at the specified instruction (i....
Target-Independent Code Generator Pass Configuration Options.
bool getEnableTailMerge() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const
Returns true if the live-ins should be tracked after register allocation.
self_iterator getIterator()
Definition: ilist_node.h:109
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:228
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:237
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:197
IterT skipDebugInstructionsForward(IterT It, IterT End, bool SkipPseudoOp=true)
Increment It until it points to a non-debug instruction or to End and return the resulting iterator.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1733
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1611
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date.
char & BranchFolderPassID
BranchFolding - This pass performs machine code CFG based optimizations to delete branches to branche...
IterT prev_nodbg(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It, then continue decrementing it while it points to a debug instruction.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
DenseMap< const MachineBasicBlock *, int > getEHScopeMembership(const MachineFunction &MF)
Definition: Analysis.cpp:807
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
Pair of physical register and lane mask.