LLVM 17.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 // _GLIBCXX_DEBUG checks strict weak ordering, which involves comparing
489 // an object with itself.
490#ifndef _GLIBCXX_DEBUG
491 llvm_unreachable("Predecessor appears twice");
492#else
493 return false;
494#endif
495}
496
497/// CountTerminators - Count the number of terminators in the given
498/// block and set I to the position of the first non-terminator, if there
499/// is one, or MBB->end() otherwise.
502 I = MBB->end();
503 unsigned NumTerms = 0;
504 while (true) {
505 if (I == MBB->begin()) {
506 I = MBB->end();
507 break;
508 }
509 --I;
510 if (!I->isTerminator()) break;
511 ++NumTerms;
512 }
513 return NumTerms;
514}
515
516/// A no successor, non-return block probably ends in unreachable and is cold.
517/// Also consider a block that ends in an indirect branch to be a return block,
518/// since many targets use plain indirect branches to return.
520 if (!MBB->succ_empty())
521 return false;
522 if (MBB->empty())
523 return true;
524 return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
525}
526
527/// ProfitableToMerge - Check if two machine basic blocks have a common tail
528/// and decide if it would be profitable to merge those tails. Return the
529/// length of the common tail and iterators to the first common instruction
530/// in each block.
531/// MBB1, MBB2 The blocks to check
532/// MinCommonTailLength Minimum size of tail block to be merged.
533/// CommonTailLen Out parameter to record the size of the shared tail between
534/// MBB1 and MBB2
535/// I1, I2 Iterator references that will be changed to point to the first
536/// instruction in the common tail shared by MBB1,MBB2
537/// SuccBB A common successor of MBB1, MBB2 which are in a canonical form
538/// relative to SuccBB
539/// PredBB The layout predecessor of SuccBB, if any.
540/// EHScopeMembership map from block to EH scope #.
541/// AfterPlacement True if we are merging blocks after layout. Stricter
542/// thresholds apply to prevent undoing tail-duplication.
543static bool
545 unsigned MinCommonTailLength, unsigned &CommonTailLen,
548 MachineBasicBlock *PredBB,
550 bool AfterPlacement,
551 MBFIWrapper &MBBFreqInfo,
552 ProfileSummaryInfo *PSI) {
553 // It is never profitable to tail-merge blocks from two different EH scopes.
554 if (!EHScopeMembership.empty()) {
555 auto EHScope1 = EHScopeMembership.find(MBB1);
556 assert(EHScope1 != EHScopeMembership.end());
557 auto EHScope2 = EHScopeMembership.find(MBB2);
558 assert(EHScope2 != EHScopeMembership.end());
559 if (EHScope1->second != EHScope2->second)
560 return false;
561 }
562
563 CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
564 if (CommonTailLen == 0)
565 return false;
566 LLVM_DEBUG(dbgs() << "Common tail length of " << printMBBReference(*MBB1)
567 << " and " << printMBBReference(*MBB2) << " is "
568 << CommonTailLen << '\n');
569
570 // Move the iterators to the beginning of the MBB if we only got debug
571 // instructions before the tail. This is to avoid splitting a block when we
572 // only got debug instructions before the tail (to be invariant on -g).
573 if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end(), false) == I1)
574 I1 = MBB1->begin();
575 if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end(), false) == I2)
576 I2 = MBB2->begin();
577
578 bool FullBlockTail1 = I1 == MBB1->begin();
579 bool FullBlockTail2 = I2 == MBB2->begin();
580
581 // It's almost always profitable to merge any number of non-terminator
582 // instructions with the block that falls through into the common successor.
583 // This is true only for a single successor. For multiple successors, we are
584 // trading a conditional branch for an unconditional one.
585 // TODO: Re-visit successor size for non-layout tail merging.
586 if ((MBB1 == PredBB || MBB2 == PredBB) &&
587 (!AfterPlacement || MBB1->succ_size() == 1)) {
589 unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
590 if (CommonTailLen > NumTerms)
591 return true;
592 }
593
594 // If these are identical non-return blocks with no successors, merge them.
595 // Such blocks are typically cold calls to noreturn functions like abort, and
596 // are unlikely to become a fallthrough target after machine block placement.
597 // Tail merging these blocks is unlikely to create additional unconditional
598 // branches, and will reduce the size of this cold code.
599 if (FullBlockTail1 && FullBlockTail2 &&
601 return true;
602
603 // If one of the blocks can be completely merged and happens to be in
604 // a position where the other could fall through into it, merge any number
605 // of instructions, because it can be done without a branch.
606 // TODO: If the blocks are not adjacent, move one of them so that they are?
607 if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)
608 return true;
609 if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)
610 return true;
611
612 // If both blocks are identical and end in a branch, merge them unless they
613 // both have a fallthrough predecessor and successor.
614 // We can only do this after block placement because it depends on whether
615 // there are fallthroughs, and we don't know until after layout.
616 if (AfterPlacement && FullBlockTail1 && FullBlockTail2) {
617 auto BothFallThrough = [](MachineBasicBlock *MBB) {
618 if (!MBB->succ_empty() && !MBB->canFallThrough())
619 return false;
622 return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();
623 };
624 if (!BothFallThrough(MBB1) || !BothFallThrough(MBB2))
625 return true;
626 }
627
628 // If both blocks have an unconditional branch temporarily stripped out,
629 // count that as an additional common instruction for the following
630 // heuristics. This heuristic is only accurate for single-succ blocks, so to
631 // make sure that during layout merging and duplicating don't crash, we check
632 // for that when merging during layout.
633 unsigned EffectiveTailLen = CommonTailLen;
634 if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
635 (MBB1->succ_size() == 1 || !AfterPlacement) &&
636 !MBB1->back().isBarrier() &&
637 !MBB2->back().isBarrier())
638 ++EffectiveTailLen;
639
640 // Check if the common tail is long enough to be worthwhile.
641 if (EffectiveTailLen >= MinCommonTailLength)
642 return true;
643
644 // If we are optimizing for code size, 2 instructions in common is enough if
645 // we don't have to split a block. At worst we will be introducing 1 new
646 // branch instruction, which is likely to be smaller than the 2
647 // instructions that would be deleted in the merge.
648 MachineFunction *MF = MBB1->getParent();
649 bool OptForSize =
650 MF->getFunction().hasOptSize() ||
651 (llvm::shouldOptimizeForSize(MBB1, PSI, &MBBFreqInfo) &&
652 llvm::shouldOptimizeForSize(MBB2, PSI, &MBBFreqInfo));
653 return EffectiveTailLen >= 2 && OptForSize &&
654 (FullBlockTail1 || FullBlockTail2);
655}
656
657unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
658 unsigned MinCommonTailLength,
659 MachineBasicBlock *SuccBB,
660 MachineBasicBlock *PredBB) {
661 unsigned maxCommonTailLength = 0U;
662 SameTails.clear();
663 MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
664 MPIterator HighestMPIter = std::prev(MergePotentials.end());
665 for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
666 B = MergePotentials.begin();
667 CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
668 for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
669 unsigned CommonTailLen;
670 if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
671 MinCommonTailLength,
672 CommonTailLen, TrialBBI1, TrialBBI2,
673 SuccBB, PredBB,
674 EHScopeMembership,
675 AfterBlockPlacement, MBBFreqInfo, PSI)) {
676 if (CommonTailLen > maxCommonTailLength) {
677 SameTails.clear();
678 maxCommonTailLength = CommonTailLen;
679 HighestMPIter = CurMPIter;
680 SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
681 }
682 if (HighestMPIter == CurMPIter &&
683 CommonTailLen == maxCommonTailLength)
684 SameTails.push_back(SameTailElt(I, TrialBBI2));
685 }
686 if (I == B)
687 break;
688 }
689 }
690 return maxCommonTailLength;
691}
692
693void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
694 MachineBasicBlock *SuccBB,
695 MachineBasicBlock *PredBB) {
696 MPIterator CurMPIter, B;
697 for (CurMPIter = std::prev(MergePotentials.end()),
698 B = MergePotentials.begin();
699 CurMPIter->getHash() == CurHash; --CurMPIter) {
700 // Put the unconditional branch back, if we need one.
701 MachineBasicBlock *CurMBB = CurMPIter->getBlock();
702 if (SuccBB && CurMBB != PredBB)
703 FixTail(CurMBB, SuccBB, TII);
704 if (CurMPIter == B)
705 break;
706 }
707 if (CurMPIter->getHash() != CurHash)
708 CurMPIter++;
709 MergePotentials.erase(CurMPIter, MergePotentials.end());
710}
711
712bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
713 MachineBasicBlock *SuccBB,
714 unsigned maxCommonTailLength,
715 unsigned &commonTailIndex) {
716 commonTailIndex = 0;
717 unsigned TimeEstimate = ~0U;
718 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
719 // Use PredBB if possible; that doesn't require a new branch.
720 if (SameTails[i].getBlock() == PredBB) {
721 commonTailIndex = i;
722 break;
723 }
724 // Otherwise, make a (fairly bogus) choice based on estimate of
725 // how long it will take the various blocks to execute.
726 unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),
727 SameTails[i].getTailStartPos());
728 if (t <= TimeEstimate) {
729 TimeEstimate = t;
730 commonTailIndex = i;
731 }
732 }
733
735 SameTails[commonTailIndex].getTailStartPos();
736 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
737
738 LLVM_DEBUG(dbgs() << "\nSplitting " << printMBBReference(*MBB) << ", size "
739 << maxCommonTailLength);
740
741 // If the split block unconditionally falls-thru to SuccBB, it will be
742 // merged. In control flow terms it should then take SuccBB's name. e.g. If
743 // SuccBB is an inner loop, the common tail is still part of the inner loop.
744 const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?
745 SuccBB->getBasicBlock() : MBB->getBasicBlock();
746 MachineBasicBlock *newMBB = SplitMBBAt(*MBB, BBI, BB);
747 if (!newMBB) {
748 LLVM_DEBUG(dbgs() << "... failed!");
749 return false;
750 }
751
752 SameTails[commonTailIndex].setBlock(newMBB);
753 SameTails[commonTailIndex].setTailStartPos(newMBB->begin());
754
755 // If we split PredBB, newMBB is the new predecessor.
756 if (PredBB == MBB)
757 PredBB = newMBB;
758
759 return true;
760}
761
762static void
764 MachineBasicBlock &MBBCommon) {
765 MachineBasicBlock *MBB = MBBIStartPos->getParent();
766 // Note CommonTailLen does not necessarily matches the size of
767 // the common BB nor all its instructions because of debug
768 // instructions differences.
769 unsigned CommonTailLen = 0;
770 for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
771 ++CommonTailLen;
772
775 MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
776 MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
777
778 while (CommonTailLen--) {
779 assert(MBBI != MBBIE && "Reached BB end within common tail length!");
780 (void)MBBIE;
781
782 if (!countsAsInstruction(*MBBI)) {
783 ++MBBI;
784 continue;
785 }
786
787 while ((MBBICommon != MBBIECommon) && !countsAsInstruction(*MBBICommon))
788 ++MBBICommon;
789
790 assert(MBBICommon != MBBIECommon &&
791 "Reached BB end within common tail length!");
792 assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");
793
794 // Merge MMOs from memory operations in the common block.
795 if (MBBICommon->mayLoadOrStore())
796 MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});
797 // Drop undef flags if they aren't present in all merged instructions.
798 for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {
799 MachineOperand &MO = MBBICommon->getOperand(I);
800 if (MO.isReg() && MO.isUndef()) {
801 const MachineOperand &OtherMO = MBBI->getOperand(I);
802 if (!OtherMO.isUndef())
803 MO.setIsUndef(false);
804 }
805 }
806
807 ++MBBI;
808 ++MBBICommon;
809 }
810}
811
812void BranchFolder::mergeCommonTails(unsigned commonTailIndex) {
813 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
814
815 std::vector<MachineBasicBlock::iterator> NextCommonInsts(SameTails.size());
816 for (unsigned int i = 0 ; i != SameTails.size() ; ++i) {
817 if (i != commonTailIndex) {
818 NextCommonInsts[i] = SameTails[i].getTailStartPos();
819 mergeOperations(SameTails[i].getTailStartPos(), *MBB);
820 } else {
821 assert(SameTails[i].getTailStartPos() == MBB->begin() &&
822 "MBB is not a common tail only block");
823 }
824 }
825
826 for (auto &MI : *MBB) {
828 continue;
829 DebugLoc DL = MI.getDebugLoc();
830 for (unsigned int i = 0 ; i < NextCommonInsts.size() ; i++) {
831 if (i == commonTailIndex)
832 continue;
833
834 auto &Pos = NextCommonInsts[i];
835 assert(Pos != SameTails[i].getBlock()->end() &&
836 "Reached BB end within common tail");
837 while (!countsAsInstruction(*Pos)) {
838 ++Pos;
839 assert(Pos != SameTails[i].getBlock()->end() &&
840 "Reached BB end within common tail");
841 }
842 assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");
843 DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());
844 NextCommonInsts[i] = ++Pos;
845 }
846 MI.setDebugLoc(DL);
847 }
848
849 if (UpdateLiveIns) {
850 LivePhysRegs NewLiveIns(*TRI);
851 computeLiveIns(NewLiveIns, *MBB);
852 LiveRegs.init(*TRI);
853
854 // The flag merging may lead to some register uses no longer using the
855 // <undef> flag, add IMPLICIT_DEFs in the predecessors as necessary.
856 for (MachineBasicBlock *Pred : MBB->predecessors()) {
857 LiveRegs.clear();
858 LiveRegs.addLiveOuts(*Pred);
859 MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();
860 for (Register Reg : NewLiveIns) {
861 if (!LiveRegs.available(*MRI, Reg))
862 continue;
863
864 // Skip the register if we are about to add one of its super registers.
865 // TODO: Common this up with the same logic in addLineIns().
866 if (any_of(TRI->superregs(Reg), [&](MCPhysReg SReg) {
867 return NewLiveIns.contains(SReg) && !MRI->isReserved(SReg);
868 }))
869 continue;
870
871 DebugLoc DL;
872 BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
873 Reg);
874 }
875 }
876
877 MBB->clearLiveIns();
878 addLiveIns(*MBB, NewLiveIns);
879 }
880}
881
882// See if any of the blocks in MergePotentials (which all have SuccBB as a
883// successor, or all have no successor if it is null) can be tail-merged.
884// If there is a successor, any blocks in MergePotentials that are not
885// tail-merged and are not immediately before Succ must have an unconditional
886// branch to Succ added (but the predecessor/successor lists need no
887// adjustment). The lone predecessor of Succ that falls through into Succ,
888// if any, is given in PredBB.
889// MinCommonTailLength - Except for the special cases below, tail-merge if
890// there are at least this many instructions in common.
891bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
892 MachineBasicBlock *PredBB,
893 unsigned MinCommonTailLength) {
894 bool MadeChange = false;
895
897 dbgs() << "\nTryTailMergeBlocks: ";
898 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
899 << printMBBReference(*MergePotentials[i].getBlock())
900 << (i == e - 1 ? "" : ", ");
901 dbgs() << "\n"; if (SuccBB) {
902 dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
903 if (PredBB)
904 dbgs() << " which has fall-through from "
905 << printMBBReference(*PredBB) << "\n";
906 } dbgs() << "Looking for common tails of at least "
907 << MinCommonTailLength << " instruction"
908 << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
909
910 // Sort by hash value so that blocks with identical end sequences sort
911 // together.
912 array_pod_sort(MergePotentials.begin(), MergePotentials.end());
913
914 // Walk through equivalence sets looking for actual exact matches.
915 while (MergePotentials.size() > 1) {
916 unsigned CurHash = MergePotentials.back().getHash();
917
918 // Build SameTails, identifying the set of blocks with this hash code
919 // and with the maximum number of instructions in common.
920 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
921 MinCommonTailLength,
922 SuccBB, PredBB);
923
924 // If we didn't find any pair that has at least MinCommonTailLength
925 // instructions in common, remove all blocks with this hash code and retry.
926 if (SameTails.empty()) {
927 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
928 continue;
929 }
930
931 // If one of the blocks is the entire common tail (and is not the entry
932 // block/an EH pad, which we can't jump to), we can treat all blocks with
933 // this same tail at once. Use PredBB if that is one of the possibilities,
934 // as that will not introduce any extra branches.
935 MachineBasicBlock *EntryBB =
936 &MergePotentials.front().getBlock()->getParent()->front();
937 unsigned commonTailIndex = SameTails.size();
938 // If there are two blocks, check to see if one can be made to fall through
939 // into the other.
940 if (SameTails.size() == 2 &&
941 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
942 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
943 commonTailIndex = 1;
944 else if (SameTails.size() == 2 &&
945 SameTails[1].getBlock()->isLayoutSuccessor(
946 SameTails[0].getBlock()) &&
947 SameTails[0].tailIsWholeBlock() &&
948 !SameTails[0].getBlock()->isEHPad())
949 commonTailIndex = 0;
950 else {
951 // Otherwise just pick one, favoring the fall-through predecessor if
952 // there is one.
953 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
954 MachineBasicBlock *MBB = SameTails[i].getBlock();
955 if ((MBB == EntryBB || MBB->isEHPad()) &&
956 SameTails[i].tailIsWholeBlock())
957 continue;
958 if (MBB == PredBB) {
959 commonTailIndex = i;
960 break;
961 }
962 if (SameTails[i].tailIsWholeBlock())
963 commonTailIndex = i;
964 }
965 }
966
967 if (commonTailIndex == SameTails.size() ||
968 (SameTails[commonTailIndex].getBlock() == PredBB &&
969 !SameTails[commonTailIndex].tailIsWholeBlock())) {
970 // None of the blocks consist entirely of the common tail.
971 // Split a block so that one does.
972 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
973 maxCommonTailLength, commonTailIndex)) {
974 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
975 continue;
976 }
977 }
978
979 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
980
981 // Recompute common tail MBB's edge weights and block frequency.
982 setCommonTailEdgeWeights(*MBB);
983
984 // Merge debug locations, MMOs and undef flags across identical instructions
985 // for common tail.
986 mergeCommonTails(commonTailIndex);
987
988 // MBB is common tail. Adjust all other BB's to jump to this one.
989 // Traversal must be forwards so erases work.
990 LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
991 << " for ");
992 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
993 if (commonTailIndex == i)
994 continue;
995 LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
996 << (i == e - 1 ? "" : ", "));
997 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
998 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
999 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
1000 MergePotentials.erase(SameTails[i].getMPIter());
1001 }
1002 LLVM_DEBUG(dbgs() << "\n");
1003 // We leave commonTailIndex in the worklist in case there are other blocks
1004 // that match it with a smaller number of instructions.
1005 MadeChange = true;
1006 }
1007 return MadeChange;
1008}
1009
1010bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
1011 bool MadeChange = false;
1012 if (!EnableTailMerge)
1013 return MadeChange;
1014
1015 // First find blocks with no successors.
1016 // Block placement may create new tail merging opportunities for these blocks.
1017 MergePotentials.clear();
1018 for (MachineBasicBlock &MBB : MF) {
1019 if (MergePotentials.size() == TailMergeThreshold)
1020 break;
1021 if (!TriedMerging.count(&MBB) && MBB.succ_empty())
1022 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
1023 }
1024
1025 // If this is a large problem, avoid visiting the same basic blocks
1026 // multiple times.
1027 if (MergePotentials.size() == TailMergeThreshold)
1028 for (const MergePotentialsElt &Elt : MergePotentials)
1029 TriedMerging.insert(Elt.getBlock());
1030
1031 // See if we can do any tail merging on those.
1032 if (MergePotentials.size() >= 2)
1033 MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
1034
1035 // Look at blocks (IBB) with multiple predecessors (PBB).
1036 // We change each predecessor to a canonical form, by
1037 // (1) temporarily removing any unconditional branch from the predecessor
1038 // to IBB, and
1039 // (2) alter conditional branches so they branch to the other block
1040 // not IBB; this may require adding back an unconditional branch to IBB
1041 // later, where there wasn't one coming in. E.g.
1042 // Bcc IBB
1043 // fallthrough to QBB
1044 // here becomes
1045 // Bncc QBB
1046 // with a conceptual B to IBB after that, which never actually exists.
1047 // With those changes, we see whether the predecessors' tails match,
1048 // and merge them if so. We change things out of canonical form and
1049 // back to the way they were later in the process. (OptimizeBranches
1050 // would undo some of this, but we can't use it, because we'd get into
1051 // a compile-time infinite loop repeatedly doing and undoing the same
1052 // transformations.)
1053
1054 for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1055 I != E; ++I) {
1056 if (I->pred_size() < 2) continue;
1058 MachineBasicBlock *IBB = &*I;
1059 MachineBasicBlock *PredBB = &*std::prev(I);
1060 MergePotentials.clear();
1061 MachineLoop *ML;
1062
1063 // Bail if merging after placement and IBB is the loop header because
1064 // -- If merging predecessors that belong to the same loop as IBB, the
1065 // common tail of merged predecessors may become the loop top if block
1066 // placement is called again and the predecessors may branch to this common
1067 // tail and require more branches. This can be relaxed if
1068 // MachineBlockPlacement::findBestLoopTop is more flexible.
1069 // --If merging predecessors that do not belong to the same loop as IBB, the
1070 // loop info of IBB's loop and the other loops may be affected. Calling the
1071 // block placement again may make big change to the layout and eliminate the
1072 // reason to do tail merging here.
1073 if (AfterBlockPlacement && MLI) {
1074 ML = MLI->getLoopFor(IBB);
1075 if (ML && IBB == ML->getHeader())
1076 continue;
1077 }
1078
1079 for (MachineBasicBlock *PBB : I->predecessors()) {
1080 if (MergePotentials.size() == TailMergeThreshold)
1081 break;
1082
1083 if (TriedMerging.count(PBB))
1084 continue;
1085
1086 // Skip blocks that loop to themselves, can't tail merge these.
1087 if (PBB == IBB)
1088 continue;
1089
1090 // Visit each predecessor only once.
1091 if (!UniquePreds.insert(PBB).second)
1092 continue;
1093
1094 // Skip blocks which may jump to a landing pad or jump from an asm blob.
1095 // Can't tail merge these.
1096 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1097 continue;
1098
1099 // After block placement, only consider predecessors that belong to the
1100 // same loop as IBB. The reason is the same as above when skipping loop
1101 // header.
1102 if (AfterBlockPlacement && MLI)
1103 if (ML != MLI->getLoopFor(PBB))
1104 continue;
1105
1106 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1108 if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
1109 // Failing case: IBB is the target of a cbr, and we cannot reverse the
1110 // branch.
1112 if (!Cond.empty() && TBB == IBB) {
1113 if (TII->reverseBranchCondition(NewCond))
1114 continue;
1115 // This is the QBB case described above
1116 if (!FBB) {
1117 auto Next = ++PBB->getIterator();
1118 if (Next != MF.end())
1119 FBB = &*Next;
1120 }
1121 }
1122
1123 // Remove the unconditional branch at the end, if any.
1124 if (TBB && (Cond.empty() || FBB)) {
1125 DebugLoc dl = PBB->findBranchDebugLoc();
1126 TII->removeBranch(*PBB);
1127 if (!Cond.empty())
1128 // reinsert conditional branch only, for now
1129 TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
1130 NewCond, dl);
1131 }
1132
1133 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
1134 }
1135 }
1136
1137 // If this is a large problem, avoid visiting the same basic blocks multiple
1138 // times.
1139 if (MergePotentials.size() == TailMergeThreshold)
1140 for (MergePotentialsElt &Elt : MergePotentials)
1141 TriedMerging.insert(Elt.getBlock());
1142
1143 if (MergePotentials.size() >= 2)
1144 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1145
1146 // Reinsert an unconditional branch if needed. The 1 below can occur as a
1147 // result of removing blocks in TryTailMergeBlocks.
1148 PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
1149 if (MergePotentials.size() == 1 &&
1150 MergePotentials.begin()->getBlock() != PredBB)
1151 FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1152 }
1153
1154 return MadeChange;
1155}
1156
1157void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
1158 SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
1159 BlockFrequency AccumulatedMBBFreq;
1160
1161 // Aggregate edge frequency of successor edge j:
1162 // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
1163 // where bb is a basic block that is in SameTails.
1164 for (const auto &Src : SameTails) {
1165 const MachineBasicBlock *SrcMBB = Src.getBlock();
1166 BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
1167 AccumulatedMBBFreq += BlockFreq;
1168
1169 // It is not necessary to recompute edge weights if TailBB has less than two
1170 // successors.
1171 if (TailMBB.succ_size() <= 1)
1172 continue;
1173
1174 auto EdgeFreq = EdgeFreqLs.begin();
1175
1176 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1177 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1178 *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
1179 }
1180
1181 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1182
1183 if (TailMBB.succ_size() <= 1)
1184 return;
1185
1186 auto SumEdgeFreq =
1187 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
1188 .getFrequency();
1189 auto EdgeFreq = EdgeFreqLs.begin();
1190
1191 if (SumEdgeFreq > 0) {
1192 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1193 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1195 EdgeFreq->getFrequency(), SumEdgeFreq);
1196 TailMBB.setSuccProbability(SuccI, Prob);
1197 }
1198 }
1199}
1200
1201//===----------------------------------------------------------------------===//
1202// Branch Optimization
1203//===----------------------------------------------------------------------===//
1204
1205bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
1206 bool MadeChange = false;
1207
1208 // Make sure blocks are numbered in order
1209 MF.RenumberBlocks();
1210 // Renumbering blocks alters EH scope membership, recalculate it.
1211 EHScopeMembership = getEHScopeMembership(MF);
1212
1213 for (MachineBasicBlock &MBB :
1215 MadeChange |= OptimizeBlock(&MBB);
1216
1217 // If it is dead, remove it.
1219 RemoveDeadBlock(&MBB);
1220 MadeChange = true;
1221 ++NumDeadBlocks;
1222 }
1223 }
1224
1225 return MadeChange;
1226}
1227
1228// Blocks should be considered empty if they contain only debug info;
1229// else the debug info would affect codegen.
1231 return MBB->getFirstNonDebugInstr(true) == MBB->end();
1232}
1233
1234// Blocks with only debug info and branches should be considered the same
1235// as blocks with only branches.
1238 assert(I != MBB->end() && "empty block!");
1239 return I->isBranch();
1240}
1241
1242/// IsBetterFallthrough - Return true if it would be clearly better to
1243/// fall-through to MBB1 than to fall through into MBB2. This has to return
1244/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1245/// result in infinite loops.
1247 MachineBasicBlock *MBB2) {
1248 assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
1249
1250 // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1251 // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1252 // optimize branches that branch to either a return block or an assert block
1253 // into a fallthrough to the return.
1256 if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1257 return false;
1258
1259 // If there is a clear successor ordering we make sure that one block
1260 // will fall through to the next
1261 if (MBB1->isSuccessor(MBB2)) return true;
1262 if (MBB2->isSuccessor(MBB1)) return false;
1263
1264 return MBB2I->isCall() && !MBB1I->isCall();
1265}
1266
1267/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1268/// instructions on the block.
1271 if (I != MBB.end() && I->isBranch())
1272 return I->getDebugLoc();
1273 return DebugLoc();
1274}
1275
1278 MachineBasicBlock &PredMBB) {
1279 auto InsertBefore = PredMBB.getFirstTerminator();
1280 for (MachineInstr &MI : MBB.instrs())
1281 if (MI.isDebugInstr()) {
1282 TII->duplicate(PredMBB, InsertBefore, MI);
1283 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
1284 << MI);
1285 }
1286}
1287
1290 MachineBasicBlock &SuccMBB) {
1291 auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1292 for (MachineInstr &MI : MBB.instrs())
1293 if (MI.isDebugInstr()) {
1294 TII->duplicate(SuccMBB, InsertBefore, MI);
1295 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
1296 << MI);
1297 }
1298}
1299
1300// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1301// a basic block is removed we would lose the debug information unless we have
1302// copied the information to a predecessor/successor.
1303//
1304// TODO: This function only handles some simple cases. An alternative would be
1305// to run a heavier analysis, such as the LiveDebugValues pass, before we do
1306// branch folding.
1309 assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
1310 // If this MBB is the only predecessor of a successor it is legal to copy
1311 // DBG_VALUE instructions to the beginning of the successor.
1312 for (MachineBasicBlock *SuccBB : MBB.successors())
1313 if (SuccBB->pred_size() == 1)
1314 copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1315 // If this MBB is the only successor of a predecessor it is legal to copy the
1316 // DBG_VALUE instructions to the end of the predecessor (just before the
1317 // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1318 for (MachineBasicBlock *PredBB : MBB.predecessors())
1319 if (PredBB->succ_size() == 1)
1321}
1322
1323bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1324 bool MadeChange = false;
1325 MachineFunction &MF = *MBB->getParent();
1326ReoptimizeBlock:
1327
1328 MachineFunction::iterator FallThrough = MBB->getIterator();
1329 ++FallThrough;
1330
1331 // Make sure MBB and FallThrough belong to the same EH scope.
1332 bool SameEHScope = true;
1333 if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1334 auto MBBEHScope = EHScopeMembership.find(MBB);
1335 assert(MBBEHScope != EHScopeMembership.end());
1336 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1337 assert(FallThroughEHScope != EHScopeMembership.end());
1338 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1339 }
1340
1341 // Analyze the branch in the current block. As a side-effect, this may cause
1342 // the block to become empty.
1343 MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1345 bool CurUnAnalyzable =
1346 TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1347
1348 // If this block is empty, make everyone use its fall-through, not the block
1349 // explicitly. Landing pads should not do this since the landing-pad table
1350 // points to this block. Blocks with their addresses taken shouldn't be
1351 // optimized away.
1352 if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
1353 SameEHScope) {
1355 // Dead block? Leave for cleanup later.
1356 if (MBB->pred_empty()) return MadeChange;
1357
1358 if (FallThrough == MF.end()) {
1359 // TODO: Simplify preds to not branch here if possible!
1360 } else if (FallThrough->isEHPad()) {
1361 // Don't rewrite to a landing pad fallthough. That could lead to the case
1362 // where a BB jumps to more than one landing pad.
1363 // TODO: Is it ever worth rewriting predecessors which don't already
1364 // jump to a landing pad, and so can safely jump to the fallthrough?
1365 } else if (MBB->isSuccessor(&*FallThrough)) {
1366 // Rewrite all predecessors of the old block to go to the fallthrough
1367 // instead.
1368 while (!MBB->pred_empty()) {
1369 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1370 Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1371 }
1372 // If MBB was the target of a jump table, update jump tables to go to the
1373 // fallthrough instead.
1374 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1375 MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1376 MadeChange = true;
1377 }
1378 return MadeChange;
1379 }
1380
1381 // Check to see if we can simplify the terminator of the block before this
1382 // one.
1383 MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1384
1385 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1387 bool PriorUnAnalyzable =
1388 TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
1389 if (!PriorUnAnalyzable) {
1390 // If the previous branch is conditional and both conditions go to the same
1391 // destination, remove the branch, replacing it with an unconditional one or
1392 // a fall-through.
1393 if (PriorTBB && PriorTBB == PriorFBB) {
1394 DebugLoc dl = getBranchDebugLoc(PrevBB);
1395 TII->removeBranch(PrevBB);
1396 PriorCond.clear();
1397 if (PriorTBB != MBB)
1398 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1399 MadeChange = true;
1400 ++NumBranchOpts;
1401 goto ReoptimizeBlock;
1402 }
1403
1404 // If the previous block unconditionally falls through to this block and
1405 // this block has no other predecessors, move the contents of this block
1406 // into the prior block. This doesn't usually happen when SimplifyCFG
1407 // has been used, but it can happen if tail merging splits a fall-through
1408 // predecessor of a block.
1409 // This has to check PrevBB->succ_size() because EH edges are ignored by
1410 // analyzeBranch.
1411 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1412 PrevBB.succ_size() == 1 &&
1413 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1414 LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1415 << "From MBB: " << *MBB);
1416 // Remove redundant DBG_VALUEs first.
1417 if (!PrevBB.empty()) {
1418 MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1419 --PrevBBIter;
1421 // Check if DBG_VALUE at the end of PrevBB is identical to the
1422 // DBG_VALUE at the beginning of MBB.
1423 while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1424 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1425 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1426 break;
1427 MachineInstr &DuplicateDbg = *MBBIter;
1428 ++MBBIter; -- PrevBBIter;
1429 DuplicateDbg.eraseFromParent();
1430 }
1431 }
1432 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1433 PrevBB.removeSuccessor(PrevBB.succ_begin());
1434 assert(PrevBB.succ_empty());
1435 PrevBB.transferSuccessors(MBB);
1436 MadeChange = true;
1437 return MadeChange;
1438 }
1439
1440 // If the previous branch *only* branches to *this* block (conditional or
1441 // not) remove the branch.
1442 if (PriorTBB == MBB && !PriorFBB) {
1443 TII->removeBranch(PrevBB);
1444 MadeChange = true;
1445 ++NumBranchOpts;
1446 goto ReoptimizeBlock;
1447 }
1448
1449 // If the prior block branches somewhere else on the condition and here if
1450 // the condition is false, remove the uncond second branch.
1451 if (PriorFBB == MBB) {
1452 DebugLoc dl = getBranchDebugLoc(PrevBB);
1453 TII->removeBranch(PrevBB);
1454 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1455 MadeChange = true;
1456 ++NumBranchOpts;
1457 goto ReoptimizeBlock;
1458 }
1459
1460 // If the prior block branches here on true and somewhere else on false, and
1461 // if the branch condition is reversible, reverse the branch to create a
1462 // fall-through.
1463 if (PriorTBB == MBB) {
1464 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1465 if (!TII->reverseBranchCondition(NewPriorCond)) {
1466 DebugLoc dl = getBranchDebugLoc(PrevBB);
1467 TII->removeBranch(PrevBB);
1468 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1469 MadeChange = true;
1470 ++NumBranchOpts;
1471 goto ReoptimizeBlock;
1472 }
1473 }
1474
1475 // If this block has no successors (e.g. it is a return block or ends with
1476 // a call to a no-return function like abort or __cxa_throw) and if the pred
1477 // falls through into this block, and if it would otherwise fall through
1478 // into the block after this, move this block to the end of the function.
1479 //
1480 // We consider it more likely that execution will stay in the function (e.g.
1481 // due to loops) than it is to exit it. This asserts in loops etc, moving
1482 // the assert condition out of the loop body.
1483 if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
1484 MachineFunction::iterator(PriorTBB) == FallThrough &&
1485 !MBB->canFallThrough()) {
1486 bool DoTransform = true;
1487
1488 // We have to be careful that the succs of PredBB aren't both no-successor
1489 // blocks. If neither have successors and if PredBB is the second from
1490 // last block in the function, we'd just keep swapping the two blocks for
1491 // last. Only do the swap if one is clearly better to fall through than
1492 // the other.
1493 if (FallThrough == --MF.end() &&
1494 !IsBetterFallthrough(PriorTBB, MBB))
1495 DoTransform = false;
1496
1497 if (DoTransform) {
1498 // Reverse the branch so we will fall through on the previous true cond.
1499 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1500 if (!TII->reverseBranchCondition(NewPriorCond)) {
1501 LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1502 << "To make fallthrough to: " << *PriorTBB << "\n");
1503
1504 DebugLoc dl = getBranchDebugLoc(PrevBB);
1505 TII->removeBranch(PrevBB);
1506 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1507
1508 // Move this block to the end of the function.
1509 MBB->moveAfter(&MF.back());
1510 MadeChange = true;
1511 ++NumBranchOpts;
1512 return MadeChange;
1513 }
1514 }
1515 }
1516 }
1517
1518 if (!IsEmptyBlock(MBB)) {
1520 if (TII->isUnconditionalTailCall(TailCall)) {
1522 for (auto &Pred : MBB->predecessors()) {
1523 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1525 bool PredAnalyzable =
1526 !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1527
1528 // Only eliminate if MBB == TBB (Taken Basic Block)
1529 if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1530 PredTBB != PredFBB) {
1531 // The predecessor has a conditional branch to this block which
1532 // consists of only a tail call. Try to fold the tail call into the
1533 // conditional branch.
1534 if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1535 // TODO: It would be nice if analyzeBranch() could provide a pointer
1536 // to the branch instruction so replaceBranchWithTailCall() doesn't
1537 // have to search for it.
1538 TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1539 PredsChanged.push_back(Pred);
1540 }
1541 }
1542 // If the predecessor is falling through to this block, we could reverse
1543 // the branch condition and fold the tail call into that. However, after
1544 // that we might have to re-arrange the CFG to fall through to the other
1545 // block and there is a high risk of regressing code size rather than
1546 // improving it.
1547 }
1548 if (!PredsChanged.empty()) {
1549 NumTailCalls += PredsChanged.size();
1550 for (auto &Pred : PredsChanged)
1551 Pred->removeSuccessor(MBB);
1552
1553 return true;
1554 }
1555 }
1556 }
1557
1558 if (!CurUnAnalyzable) {
1559 // If this is a two-way branch, and the FBB branches to this block, reverse
1560 // the condition so the single-basic-block loop is faster. Instead of:
1561 // Loop: xxx; jcc Out; jmp Loop
1562 // we want:
1563 // Loop: xxx; jncc Loop; jmp Out
1564 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1565 SmallVector<MachineOperand, 4> NewCond(CurCond);
1566 if (!TII->reverseBranchCondition(NewCond)) {
1568 TII->removeBranch(*MBB);
1569 TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1570 MadeChange = true;
1571 ++NumBranchOpts;
1572 goto ReoptimizeBlock;
1573 }
1574 }
1575
1576 // If this branch is the only thing in its block, see if we can forward
1577 // other blocks across it.
1578 if (CurTBB && CurCond.empty() && !CurFBB &&
1579 IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1580 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1582 // This block may contain just an unconditional branch. Because there can
1583 // be 'non-branch terminators' in the block, try removing the branch and
1584 // then seeing if the block is empty.
1585 TII->removeBranch(*MBB);
1586 // If the only things remaining in the block are debug info, remove these
1587 // as well, so this will behave the same as an empty block in non-debug
1588 // mode.
1589 if (IsEmptyBlock(MBB)) {
1590 // Make the block empty, losing the debug info (we could probably
1591 // improve this in some cases.)
1592 MBB->erase(MBB->begin(), MBB->end());
1593 }
1594 // If this block is just an unconditional branch to CurTBB, we can
1595 // usually completely eliminate the block. The only case we cannot
1596 // completely eliminate the block is when the block before this one
1597 // falls through into MBB and we can't understand the prior block's branch
1598 // condition.
1599 if (MBB->empty()) {
1600 bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1601 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1602 !PrevBB.isSuccessor(MBB)) {
1603 // If the prior block falls through into us, turn it into an
1604 // explicit branch to us to make updates simpler.
1605 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1606 PriorTBB != MBB && PriorFBB != MBB) {
1607 if (!PriorTBB) {
1608 assert(PriorCond.empty() && !PriorFBB &&
1609 "Bad branch analysis");
1610 PriorTBB = MBB;
1611 } else {
1612 assert(!PriorFBB && "Machine CFG out of date!");
1613 PriorFBB = MBB;
1614 }
1615 DebugLoc pdl = getBranchDebugLoc(PrevBB);
1616 TII->removeBranch(PrevBB);
1617 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1618 }
1619
1620 // Iterate through all the predecessors, revectoring each in-turn.
1621 size_t PI = 0;
1622 bool DidChange = false;
1623 bool HasBranchToSelf = false;
1624 while(PI != MBB->pred_size()) {
1625 MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1626 if (PMBB == MBB) {
1627 // If this block has an uncond branch to itself, leave it.
1628 ++PI;
1629 HasBranchToSelf = true;
1630 } else {
1631 DidChange = true;
1632 PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1633 // If this change resulted in PMBB ending in a conditional
1634 // branch where both conditions go to the same destination,
1635 // change this to an unconditional branch.
1636 MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1638 bool NewCurUnAnalyzable = TII->analyzeBranch(
1639 *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1640 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1641 DebugLoc pdl = getBranchDebugLoc(*PMBB);
1642 TII->removeBranch(*PMBB);
1643 NewCurCond.clear();
1644 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1645 MadeChange = true;
1646 ++NumBranchOpts;
1647 }
1648 }
1649 }
1650
1651 // Change any jumptables to go to the new MBB.
1652 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1653 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1654 if (DidChange) {
1655 ++NumBranchOpts;
1656 MadeChange = true;
1657 if (!HasBranchToSelf) return MadeChange;
1658 }
1659 }
1660 }
1661
1662 // Add the branch back if the block is more than just an uncond branch.
1663 TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1664 }
1665 }
1666
1667 // If the prior block doesn't fall through into this block, and if this
1668 // block doesn't fall through into some other block, see if we can find a
1669 // place to move this block where a fall-through will happen.
1670 if (!PrevBB.canFallThrough()) {
1671 // Now we know that there was no fall-through into this block, check to
1672 // see if it has a fall-through into its successor.
1673 bool CurFallsThru = MBB->canFallThrough();
1674
1675 if (!MBB->isEHPad()) {
1676 // Check all the predecessors of this block. If one of them has no fall
1677 // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1678 // block, move this block right after it.
1679 for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1680 // Analyze the branch at the end of the pred.
1681 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1683 if (PredBB != MBB && !PredBB->canFallThrough() &&
1684 !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1685 (PredTBB == MBB || PredFBB == MBB) &&
1686 (!CurFallsThru || !CurTBB || !CurFBB) &&
1687 (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1688 // If the current block doesn't fall through, just move it.
1689 // If the current block can fall through and does not end with a
1690 // conditional branch, we need to append an unconditional jump to
1691 // the (current) next block. To avoid a possible compile-time
1692 // infinite loop, move blocks only backward in this case.
1693 // Also, if there are already 2 branches here, we cannot add a third;
1694 // this means we have the case
1695 // Bcc next
1696 // B elsewhere
1697 // next:
1698 if (CurFallsThru) {
1699 MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1700 CurCond.clear();
1701 TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1702 }
1703 MBB->moveAfter(PredBB);
1704 MadeChange = true;
1705 goto ReoptimizeBlock;
1706 }
1707 }
1708 }
1709
1710 if (!CurFallsThru) {
1711 // Check analyzable branch-successors to see if we can move this block
1712 // before one.
1713 if (!CurUnAnalyzable) {
1714 for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1715 if (!SuccBB)
1716 continue;
1717 // Analyze the branch at the end of the block before the succ.
1718 MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1719
1720 // If this block doesn't already fall-through to that successor, and
1721 // if the succ doesn't already have a block that can fall through into
1722 // it, we can arrange for the fallthrough to happen.
1723 if (SuccBB != MBB && &*SuccPrev != MBB &&
1724 !SuccPrev->canFallThrough()) {
1725 MBB->moveBefore(SuccBB);
1726 MadeChange = true;
1727 goto ReoptimizeBlock;
1728 }
1729 }
1730 }
1731
1732 // Okay, there is no really great place to put this block. If, however,
1733 // the block before this one would be a fall-through if this block were
1734 // removed, move this block to the end of the function. There is no real
1735 // advantage in "falling through" to an EH block, so we don't want to
1736 // perform this transformation for that case.
1737 //
1738 // Also, Windows EH introduced the possibility of an arbitrary number of
1739 // successors to a given block. The analyzeBranch call does not consider
1740 // exception handling and so we can get in a state where a block
1741 // containing a call is followed by multiple EH blocks that would be
1742 // rotated infinitely at the end of the function if the transformation
1743 // below were performed for EH "FallThrough" blocks. Therefore, even if
1744 // that appears not to be happening anymore, we should assume that it is
1745 // possible and not remove the "!FallThrough()->isEHPad" condition below.
1746 MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1748 if (FallThrough != MF.end() &&
1749 !FallThrough->isEHPad() &&
1750 !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1751 PrevBB.isSuccessor(&*FallThrough)) {
1752 MBB->moveAfter(&MF.back());
1753 MadeChange = true;
1754 return MadeChange;
1755 }
1756 }
1757 }
1758
1759 return MadeChange;
1760}
1761
1762//===----------------------------------------------------------------------===//
1763// Hoist Common Code
1764//===----------------------------------------------------------------------===//
1765
1766bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1767 bool MadeChange = false;
1769 MadeChange |= HoistCommonCodeInSuccs(&MBB);
1770
1771 return MadeChange;
1772}
1773
1774/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1775/// its 'true' successor.
1777 MachineBasicBlock *TrueBB) {
1778 for (MachineBasicBlock *SuccBB : BB->successors())
1779 if (SuccBB != TrueBB)
1780 return SuccBB;
1781 return nullptr;
1782}
1783
1784template <class Container>
1786 Container &Set) {
1787 if (Reg.isPhysical()) {
1788 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1789 Set.insert(*AI);
1790 } else {
1791 Set.insert(Reg);
1792 }
1793}
1794
1795/// findHoistingInsertPosAndDeps - Find the location to move common instructions
1796/// in successors to. The location is usually just before the terminator,
1797/// however if the terminator is a conditional branch and its previous
1798/// instruction is the flag setting instruction, the previous instruction is
1799/// the preferred location. This function also gathers uses and defs of the
1800/// instructions from the insertion point to the end of the block. The data is
1801/// used by HoistCommonCodeInSuccs to ensure safety.
1802static
1804 const TargetInstrInfo *TII,
1805 const TargetRegisterInfo *TRI,
1807 SmallSet<Register, 4> &Defs) {
1809 if (!TII->isUnpredicatedTerminator(*Loc))
1810 return MBB->end();
1811
1812 for (const MachineOperand &MO : Loc->operands()) {
1813 if (!MO.isReg())
1814 continue;
1815 Register Reg = MO.getReg();
1816 if (!Reg)
1817 continue;
1818 if (MO.isUse()) {
1820 } else {
1821 if (!MO.isDead())
1822 // Don't try to hoist code in the rare case the terminator defines a
1823 // register that is later used.
1824 return MBB->end();
1825
1826 // If the terminator defines a register, make sure we don't hoist
1827 // the instruction whose def might be clobbered by the terminator.
1828 addRegAndItsAliases(Reg, TRI, Defs);
1829 }
1830 }
1831
1832 if (Uses.empty())
1833 return Loc;
1834 // If the terminator is the only instruction in the block and Uses is not
1835 // empty (or we would have returned above), we can still safely hoist
1836 // instructions just before the terminator as long as the Defs/Uses are not
1837 // violated (which is checked in HoistCommonCodeInSuccs).
1838 if (Loc == MBB->begin())
1839 return Loc;
1840
1841 // The terminator is probably a conditional branch, try not to separate the
1842 // branch from condition setting instruction.
1844
1845 bool IsDef = false;
1846 for (const MachineOperand &MO : PI->operands()) {
1847 // If PI has a regmask operand, it is probably a call. Separate away.
1848 if (MO.isRegMask())
1849 return Loc;
1850 if (!MO.isReg() || MO.isUse())
1851 continue;
1852 Register Reg = MO.getReg();
1853 if (!Reg)
1854 continue;
1855 if (Uses.count(Reg)) {
1856 IsDef = true;
1857 break;
1858 }
1859 }
1860 if (!IsDef)
1861 // The condition setting instruction is not just before the conditional
1862 // branch.
1863 return Loc;
1864
1865 // Be conservative, don't insert instruction above something that may have
1866 // side-effects. And since it's potentially bad to separate flag setting
1867 // instruction from the conditional branch, just abort the optimization
1868 // completely.
1869 // Also avoid moving code above predicated instruction since it's hard to
1870 // reason about register liveness with predicated instruction.
1871 bool DontMoveAcrossStore = true;
1872 if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1873 return MBB->end();
1874
1875 // Find out what registers are live. Note this routine is ignoring other live
1876 // registers which are only used by instructions in successor blocks.
1877 for (const MachineOperand &MO : PI->operands()) {
1878 if (!MO.isReg())
1879 continue;
1880 Register Reg = MO.getReg();
1881 if (!Reg)
1882 continue;
1883 if (MO.isUse()) {
1885 } else {
1886 if (Uses.erase(Reg)) {
1887 if (Reg.isPhysical()) {
1888 for (MCPhysReg SubReg : TRI->subregs(Reg))
1889 Uses.erase(SubReg); // Use sub-registers to be conservative
1890 }
1891 }
1892 addRegAndItsAliases(Reg, TRI, Defs);
1893 }
1894 }
1895
1896 return PI;
1897}
1898
1899bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1900 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1902 if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1903 return false;
1904
1905 if (!FBB) FBB = findFalseBlock(MBB, TBB);
1906 if (!FBB)
1907 // Malformed bcc? True and false blocks are the same?
1908 return false;
1909
1910 // Restrict the optimization to cases where MBB is the only predecessor,
1911 // it is an obvious win.
1912 if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1913 return false;
1914
1915 // Find a suitable position to hoist the common instructions to. Also figure
1916 // out which registers are used or defined by instructions from the insertion
1917 // point to the end of the block.
1920 findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1921 if (Loc == MBB->end())
1922 return false;
1923
1924 bool HasDups = false;
1925 SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1927 MachineBasicBlock::iterator FIB = FBB->begin();
1929 MachineBasicBlock::iterator FIE = FBB->end();
1930 while (TIB != TIE && FIB != FIE) {
1931 // Skip dbg_value instructions. These do not count.
1932 TIB = skipDebugInstructionsForward(TIB, TIE, false);
1933 FIB = skipDebugInstructionsForward(FIB, FIE, false);
1934 if (TIB == TIE || FIB == FIE)
1935 break;
1936
1937 if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1938 break;
1939
1940 if (TII->isPredicated(*TIB))
1941 // Hard to reason about register liveness with predicated instruction.
1942 break;
1943
1944 bool IsSafe = true;
1945 for (MachineOperand &MO : TIB->operands()) {
1946 // Don't attempt to hoist instructions with register masks.
1947 if (MO.isRegMask()) {
1948 IsSafe = false;
1949 break;
1950 }
1951 if (!MO.isReg())
1952 continue;
1953 Register Reg = MO.getReg();
1954 if (!Reg)
1955 continue;
1956 if (MO.isDef()) {
1957 if (Uses.count(Reg)) {
1958 // Avoid clobbering a register that's used by the instruction at
1959 // the point of insertion.
1960 IsSafe = false;
1961 break;
1962 }
1963
1964 if (Defs.count(Reg) && !MO.isDead()) {
1965 // Don't hoist the instruction if the def would be clobber by the
1966 // instruction at the point insertion. FIXME: This is overly
1967 // conservative. It should be possible to hoist the instructions
1968 // in BB2 in the following example:
1969 // BB1:
1970 // r1, eflag = op1 r2, r3
1971 // brcc eflag
1972 //
1973 // BB2:
1974 // r1 = op2, ...
1975 // = op3, killed r1
1976 IsSafe = false;
1977 break;
1978 }
1979 } else if (!ActiveDefsSet.count(Reg)) {
1980 if (Defs.count(Reg)) {
1981 // Use is defined by the instruction at the point of insertion.
1982 IsSafe = false;
1983 break;
1984 }
1985
1986 if (MO.isKill() && Uses.count(Reg))
1987 // Kills a register that's read by the instruction at the point of
1988 // insertion. Remove the kill marker.
1989 MO.setIsKill(false);
1990 }
1991 }
1992 if (!IsSafe)
1993 break;
1994
1995 bool DontMoveAcrossStore = true;
1996 if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1997 break;
1998
1999 // Remove kills from ActiveDefsSet, these registers had short live ranges.
2000 for (const MachineOperand &MO : TIB->all_uses()) {
2001 if (!MO.isKill())
2002 continue;
2003 Register Reg = MO.getReg();
2004 if (!Reg)
2005 continue;
2006 if (!AllDefsSet.count(Reg)) {
2007 continue;
2008 }
2009 if (Reg.isPhysical()) {
2010 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2011 ActiveDefsSet.erase(*AI);
2012 } else {
2013 ActiveDefsSet.erase(Reg);
2014 }
2015 }
2016
2017 // Track local defs so we can update liveins.
2018 for (const MachineOperand &MO : TIB->all_defs()) {
2019 if (MO.isDead())
2020 continue;
2021 Register Reg = MO.getReg();
2022 if (!Reg || Reg.isVirtual())
2023 continue;
2024 addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2025 addRegAndItsAliases(Reg, TRI, AllDefsSet);
2026 }
2027
2028 HasDups = true;
2029 ++TIB;
2030 ++FIB;
2031 }
2032
2033 if (!HasDups)
2034 return false;
2035
2036 MBB->splice(Loc, TBB, TBB->begin(), TIB);
2037 FBB->erase(FBB->begin(), FIB);
2038
2039 if (UpdateLiveIns) {
2041 recomputeLiveIns(*FBB);
2042 }
2043
2044 ++NumHoist;
2045 return true;
2046}
unsigned SubReg
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
SmallVector< MachineOperand, 4 > Cond
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
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:56
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...
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:645
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< mc_superreg_iterator > 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 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)
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
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.
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:894
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:919
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:942
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:82
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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:227
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:413
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
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:1826
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:1704
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:809
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
Pair of physical register and lane mask.