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 DebugLoc DL;
864 BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),
865 Reg);
866 }
867 }
868
869 MBB->clearLiveIns();
870 addLiveIns(*MBB, NewLiveIns);
871 }
872}
873
874// See if any of the blocks in MergePotentials (which all have SuccBB as a
875// successor, or all have no successor if it is null) can be tail-merged.
876// If there is a successor, any blocks in MergePotentials that are not
877// tail-merged and are not immediately before Succ must have an unconditional
878// branch to Succ added (but the predecessor/successor lists need no
879// adjustment). The lone predecessor of Succ that falls through into Succ,
880// if any, is given in PredBB.
881// MinCommonTailLength - Except for the special cases below, tail-merge if
882// there are at least this many instructions in common.
883bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
884 MachineBasicBlock *PredBB,
885 unsigned MinCommonTailLength) {
886 bool MadeChange = false;
887
889 dbgs() << "\nTryTailMergeBlocks: ";
890 for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i) dbgs()
891 << printMBBReference(*MergePotentials[i].getBlock())
892 << (i == e - 1 ? "" : ", ");
893 dbgs() << "\n"; if (SuccBB) {
894 dbgs() << " with successor " << printMBBReference(*SuccBB) << '\n';
895 if (PredBB)
896 dbgs() << " which has fall-through from "
897 << printMBBReference(*PredBB) << "\n";
898 } dbgs() << "Looking for common tails of at least "
899 << MinCommonTailLength << " instruction"
900 << (MinCommonTailLength == 1 ? "" : "s") << '\n';);
901
902 // Sort by hash value so that blocks with identical end sequences sort
903 // together.
904 array_pod_sort(MergePotentials.begin(), MergePotentials.end());
905
906 // Walk through equivalence sets looking for actual exact matches.
907 while (MergePotentials.size() > 1) {
908 unsigned CurHash = MergePotentials.back().getHash();
909
910 // Build SameTails, identifying the set of blocks with this hash code
911 // and with the maximum number of instructions in common.
912 unsigned maxCommonTailLength = ComputeSameTails(CurHash,
913 MinCommonTailLength,
914 SuccBB, PredBB);
915
916 // If we didn't find any pair that has at least MinCommonTailLength
917 // instructions in common, remove all blocks with this hash code and retry.
918 if (SameTails.empty()) {
919 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
920 continue;
921 }
922
923 // If one of the blocks is the entire common tail (and is not the entry
924 // block/an EH pad, which we can't jump to), we can treat all blocks with
925 // this same tail at once. Use PredBB if that is one of the possibilities,
926 // as that will not introduce any extra branches.
927 MachineBasicBlock *EntryBB =
928 &MergePotentials.front().getBlock()->getParent()->front();
929 unsigned commonTailIndex = SameTails.size();
930 // If there are two blocks, check to see if one can be made to fall through
931 // into the other.
932 if (SameTails.size() == 2 &&
933 SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
934 SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
935 commonTailIndex = 1;
936 else if (SameTails.size() == 2 &&
937 SameTails[1].getBlock()->isLayoutSuccessor(
938 SameTails[0].getBlock()) &&
939 SameTails[0].tailIsWholeBlock() &&
940 !SameTails[0].getBlock()->isEHPad())
941 commonTailIndex = 0;
942 else {
943 // Otherwise just pick one, favoring the fall-through predecessor if
944 // there is one.
945 for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
946 MachineBasicBlock *MBB = SameTails[i].getBlock();
947 if ((MBB == EntryBB || MBB->isEHPad()) &&
948 SameTails[i].tailIsWholeBlock())
949 continue;
950 if (MBB == PredBB) {
951 commonTailIndex = i;
952 break;
953 }
954 if (SameTails[i].tailIsWholeBlock())
955 commonTailIndex = i;
956 }
957 }
958
959 if (commonTailIndex == SameTails.size() ||
960 (SameTails[commonTailIndex].getBlock() == PredBB &&
961 !SameTails[commonTailIndex].tailIsWholeBlock())) {
962 // None of the blocks consist entirely of the common tail.
963 // Split a block so that one does.
964 if (!CreateCommonTailOnlyBlock(PredBB, SuccBB,
965 maxCommonTailLength, commonTailIndex)) {
966 RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
967 continue;
968 }
969 }
970
971 MachineBasicBlock *MBB = SameTails[commonTailIndex].getBlock();
972
973 // Recompute common tail MBB's edge weights and block frequency.
974 setCommonTailEdgeWeights(*MBB);
975
976 // Merge debug locations, MMOs and undef flags across identical instructions
977 // for common tail.
978 mergeCommonTails(commonTailIndex);
979
980 // MBB is common tail. Adjust all other BB's to jump to this one.
981 // Traversal must be forwards so erases work.
982 LLVM_DEBUG(dbgs() << "\nUsing common tail in " << printMBBReference(*MBB)
983 << " for ");
984 for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
985 if (commonTailIndex == i)
986 continue;
987 LLVM_DEBUG(dbgs() << printMBBReference(*SameTails[i].getBlock())
988 << (i == e - 1 ? "" : ", "));
989 // Hack the end off BB i, making it jump to BB commonTailIndex instead.
990 replaceTailWithBranchTo(SameTails[i].getTailStartPos(), *MBB);
991 // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
992 MergePotentials.erase(SameTails[i].getMPIter());
993 }
994 LLVM_DEBUG(dbgs() << "\n");
995 // We leave commonTailIndex in the worklist in case there are other blocks
996 // that match it with a smaller number of instructions.
997 MadeChange = true;
998 }
999 return MadeChange;
1000}
1001
1002bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
1003 bool MadeChange = false;
1004 if (!EnableTailMerge)
1005 return MadeChange;
1006
1007 // First find blocks with no successors.
1008 // Block placement may create new tail merging opportunities for these blocks.
1009 MergePotentials.clear();
1010 for (MachineBasicBlock &MBB : MF) {
1011 if (MergePotentials.size() == TailMergeThreshold)
1012 break;
1013 if (!TriedMerging.count(&MBB) && MBB.succ_empty())
1014 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(MBB), &MBB));
1015 }
1016
1017 // If this is a large problem, avoid visiting the same basic blocks
1018 // multiple times.
1019 if (MergePotentials.size() == TailMergeThreshold)
1020 for (const MergePotentialsElt &Elt : MergePotentials)
1021 TriedMerging.insert(Elt.getBlock());
1022
1023 // See if we can do any tail merging on those.
1024 if (MergePotentials.size() >= 2)
1025 MadeChange |= TryTailMergeBlocks(nullptr, nullptr, MinCommonTailLength);
1026
1027 // Look at blocks (IBB) with multiple predecessors (PBB).
1028 // We change each predecessor to a canonical form, by
1029 // (1) temporarily removing any unconditional branch from the predecessor
1030 // to IBB, and
1031 // (2) alter conditional branches so they branch to the other block
1032 // not IBB; this may require adding back an unconditional branch to IBB
1033 // later, where there wasn't one coming in. E.g.
1034 // Bcc IBB
1035 // fallthrough to QBB
1036 // here becomes
1037 // Bncc QBB
1038 // with a conceptual B to IBB after that, which never actually exists.
1039 // With those changes, we see whether the predecessors' tails match,
1040 // and merge them if so. We change things out of canonical form and
1041 // back to the way they were later in the process. (OptimizeBranches
1042 // would undo some of this, but we can't use it, because we'd get into
1043 // a compile-time infinite loop repeatedly doing and undoing the same
1044 // transformations.)
1045
1046 for (MachineFunction::iterator I = std::next(MF.begin()), E = MF.end();
1047 I != E; ++I) {
1048 if (I->pred_size() < 2) continue;
1050 MachineBasicBlock *IBB = &*I;
1051 MachineBasicBlock *PredBB = &*std::prev(I);
1052 MergePotentials.clear();
1053 MachineLoop *ML;
1054
1055 // Bail if merging after placement and IBB is the loop header because
1056 // -- If merging predecessors that belong to the same loop as IBB, the
1057 // common tail of merged predecessors may become the loop top if block
1058 // placement is called again and the predecessors may branch to this common
1059 // tail and require more branches. This can be relaxed if
1060 // MachineBlockPlacement::findBestLoopTop is more flexible.
1061 // --If merging predecessors that do not belong to the same loop as IBB, the
1062 // loop info of IBB's loop and the other loops may be affected. Calling the
1063 // block placement again may make big change to the layout and eliminate the
1064 // reason to do tail merging here.
1065 if (AfterBlockPlacement && MLI) {
1066 ML = MLI->getLoopFor(IBB);
1067 if (ML && IBB == ML->getHeader())
1068 continue;
1069 }
1070
1071 for (MachineBasicBlock *PBB : I->predecessors()) {
1072 if (MergePotentials.size() == TailMergeThreshold)
1073 break;
1074
1075 if (TriedMerging.count(PBB))
1076 continue;
1077
1078 // Skip blocks that loop to themselves, can't tail merge these.
1079 if (PBB == IBB)
1080 continue;
1081
1082 // Visit each predecessor only once.
1083 if (!UniquePreds.insert(PBB).second)
1084 continue;
1085
1086 // Skip blocks which may jump to a landing pad or jump from an asm blob.
1087 // Can't tail merge these.
1088 if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())
1089 continue;
1090
1091 // After block placement, only consider predecessors that belong to the
1092 // same loop as IBB. The reason is the same as above when skipping loop
1093 // header.
1094 if (AfterBlockPlacement && MLI)
1095 if (ML != MLI->getLoopFor(PBB))
1096 continue;
1097
1098 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1100 if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {
1101 // Failing case: IBB is the target of a cbr, and we cannot reverse the
1102 // branch.
1104 if (!Cond.empty() && TBB == IBB) {
1105 if (TII->reverseBranchCondition(NewCond))
1106 continue;
1107 // This is the QBB case described above
1108 if (!FBB) {
1109 auto Next = ++PBB->getIterator();
1110 if (Next != MF.end())
1111 FBB = &*Next;
1112 }
1113 }
1114
1115 // Remove the unconditional branch at the end, if any.
1116 if (TBB && (Cond.empty() || FBB)) {
1117 DebugLoc dl = PBB->findBranchDebugLoc();
1118 TII->removeBranch(*PBB);
1119 if (!Cond.empty())
1120 // reinsert conditional branch only, for now
1121 TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,
1122 NewCond, dl);
1123 }
1124
1125 MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(*PBB), PBB));
1126 }
1127 }
1128
1129 // If this is a large problem, avoid visiting the same basic blocks multiple
1130 // times.
1131 if (MergePotentials.size() == TailMergeThreshold)
1132 for (MergePotentialsElt &Elt : MergePotentials)
1133 TriedMerging.insert(Elt.getBlock());
1134
1135 if (MergePotentials.size() >= 2)
1136 MadeChange |= TryTailMergeBlocks(IBB, PredBB, MinCommonTailLength);
1137
1138 // Reinsert an unconditional branch if needed. The 1 below can occur as a
1139 // result of removing blocks in TryTailMergeBlocks.
1140 PredBB = &*std::prev(I); // this may have been changed in TryTailMergeBlocks
1141 if (MergePotentials.size() == 1 &&
1142 MergePotentials.begin()->getBlock() != PredBB)
1143 FixTail(MergePotentials.begin()->getBlock(), IBB, TII);
1144 }
1145
1146 return MadeChange;
1147}
1148
1149void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) {
1150 SmallVector<BlockFrequency, 2> EdgeFreqLs(TailMBB.succ_size());
1151 BlockFrequency AccumulatedMBBFreq;
1152
1153 // Aggregate edge frequency of successor edge j:
1154 // edgeFreq(j) = sum (freq(bb) * edgeProb(bb, j)),
1155 // where bb is a basic block that is in SameTails.
1156 for (const auto &Src : SameTails) {
1157 const MachineBasicBlock *SrcMBB = Src.getBlock();
1158 BlockFrequency BlockFreq = MBBFreqInfo.getBlockFreq(SrcMBB);
1159 AccumulatedMBBFreq += BlockFreq;
1160
1161 // It is not necessary to recompute edge weights if TailBB has less than two
1162 // successors.
1163 if (TailMBB.succ_size() <= 1)
1164 continue;
1165
1166 auto EdgeFreq = EdgeFreqLs.begin();
1167
1168 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1169 SuccI != SuccE; ++SuccI, ++EdgeFreq)
1170 *EdgeFreq += BlockFreq * MBPI.getEdgeProbability(SrcMBB, *SuccI);
1171 }
1172
1173 MBBFreqInfo.setBlockFreq(&TailMBB, AccumulatedMBBFreq);
1174
1175 if (TailMBB.succ_size() <= 1)
1176 return;
1177
1178 auto SumEdgeFreq =
1179 std::accumulate(EdgeFreqLs.begin(), EdgeFreqLs.end(), BlockFrequency(0))
1180 .getFrequency();
1181 auto EdgeFreq = EdgeFreqLs.begin();
1182
1183 if (SumEdgeFreq > 0) {
1184 for (auto SuccI = TailMBB.succ_begin(), SuccE = TailMBB.succ_end();
1185 SuccI != SuccE; ++SuccI, ++EdgeFreq) {
1187 EdgeFreq->getFrequency(), SumEdgeFreq);
1188 TailMBB.setSuccProbability(SuccI, Prob);
1189 }
1190 }
1191}
1192
1193//===----------------------------------------------------------------------===//
1194// Branch Optimization
1195//===----------------------------------------------------------------------===//
1196
1197bool BranchFolder::OptimizeBranches(MachineFunction &MF) {
1198 bool MadeChange = false;
1199
1200 // Make sure blocks are numbered in order
1201 MF.RenumberBlocks();
1202 // Renumbering blocks alters EH scope membership, recalculate it.
1203 EHScopeMembership = getEHScopeMembership(MF);
1204
1205 for (MachineBasicBlock &MBB :
1207 MadeChange |= OptimizeBlock(&MBB);
1208
1209 // If it is dead, remove it.
1210 if (MBB.pred_empty()) {
1211 RemoveDeadBlock(&MBB);
1212 MadeChange = true;
1213 ++NumDeadBlocks;
1214 }
1215 }
1216
1217 return MadeChange;
1218}
1219
1220// Blocks should be considered empty if they contain only debug info;
1221// else the debug info would affect codegen.
1223 return MBB->getFirstNonDebugInstr(true) == MBB->end();
1224}
1225
1226// Blocks with only debug info and branches should be considered the same
1227// as blocks with only branches.
1230 assert(I != MBB->end() && "empty block!");
1231 return I->isBranch();
1232}
1233
1234/// IsBetterFallthrough - Return true if it would be clearly better to
1235/// fall-through to MBB1 than to fall through into MBB2. This has to return
1236/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
1237/// result in infinite loops.
1239 MachineBasicBlock *MBB2) {
1240 assert(MBB1 && MBB2 && "Unknown MachineBasicBlock");
1241
1242 // Right now, we use a simple heuristic. If MBB2 ends with a call, and
1243 // MBB1 doesn't, we prefer to fall through into MBB1. This allows us to
1244 // optimize branches that branch to either a return block or an assert block
1245 // into a fallthrough to the return.
1248 if (MBB1I == MBB1->end() || MBB2I == MBB2->end())
1249 return false;
1250
1251 // If there is a clear successor ordering we make sure that one block
1252 // will fall through to the next
1253 if (MBB1->isSuccessor(MBB2)) return true;
1254 if (MBB2->isSuccessor(MBB1)) return false;
1255
1256 return MBB2I->isCall() && !MBB1I->isCall();
1257}
1258
1259/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1260/// instructions on the block.
1263 if (I != MBB.end() && I->isBranch())
1264 return I->getDebugLoc();
1265 return DebugLoc();
1266}
1267
1270 MachineBasicBlock &PredMBB) {
1271 auto InsertBefore = PredMBB.getFirstTerminator();
1272 for (MachineInstr &MI : MBB.instrs())
1273 if (MI.isDebugInstr()) {
1274 TII->duplicate(PredMBB, InsertBefore, MI);
1275 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to pred: "
1276 << MI);
1277 }
1278}
1279
1282 MachineBasicBlock &SuccMBB) {
1283 auto InsertBefore = SuccMBB.SkipPHIsAndLabels(SuccMBB.begin());
1284 for (MachineInstr &MI : MBB.instrs())
1285 if (MI.isDebugInstr()) {
1286 TII->duplicate(SuccMBB, InsertBefore, MI);
1287 LLVM_DEBUG(dbgs() << "Copied debug entity from empty block to succ: "
1288 << MI);
1289 }
1290}
1291
1292// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
1293// a basic block is removed we would lose the debug information unless we have
1294// copied the information to a predecessor/successor.
1295//
1296// TODO: This function only handles some simple cases. An alternative would be
1297// to run a heavier analysis, such as the LiveDebugValues pass, before we do
1298// branch folding.
1301 assert(IsEmptyBlock(&MBB) && "Expected an empty block (except debug info).");
1302 // If this MBB is the only predecessor of a successor it is legal to copy
1303 // DBG_VALUE instructions to the beginning of the successor.
1304 for (MachineBasicBlock *SuccBB : MBB.successors())
1305 if (SuccBB->pred_size() == 1)
1306 copyDebugInfoToSuccessor(TII, MBB, *SuccBB);
1307 // If this MBB is the only successor of a predecessor it is legal to copy the
1308 // DBG_VALUE instructions to the end of the predecessor (just before the
1309 // terminators, assuming that the terminator isn't affecting the DBG_VALUE).
1310 for (MachineBasicBlock *PredBB : MBB.predecessors())
1311 if (PredBB->succ_size() == 1)
1313}
1314
1315bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {
1316 bool MadeChange = false;
1317 MachineFunction &MF = *MBB->getParent();
1318ReoptimizeBlock:
1319
1320 MachineFunction::iterator FallThrough = MBB->getIterator();
1321 ++FallThrough;
1322
1323 // Make sure MBB and FallThrough belong to the same EH scope.
1324 bool SameEHScope = true;
1325 if (!EHScopeMembership.empty() && FallThrough != MF.end()) {
1326 auto MBBEHScope = EHScopeMembership.find(MBB);
1327 assert(MBBEHScope != EHScopeMembership.end());
1328 auto FallThroughEHScope = EHScopeMembership.find(&*FallThrough);
1329 assert(FallThroughEHScope != EHScopeMembership.end());
1330 SameEHScope = MBBEHScope->second == FallThroughEHScope->second;
1331 }
1332
1333 // Analyze the branch in the current block. As a side-effect, this may cause
1334 // the block to become empty.
1335 MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
1337 bool CurUnAnalyzable =
1338 TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
1339
1340 // If this block is empty, make everyone use its fall-through, not the block
1341 // explicitly. Landing pads should not do this since the landing-pad table
1342 // points to this block. Blocks with their addresses taken shouldn't be
1343 // optimized away.
1344 if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&
1345 SameEHScope) {
1347 // Dead block? Leave for cleanup later.
1348 if (MBB->pred_empty()) return MadeChange;
1349
1350 if (FallThrough == MF.end()) {
1351 // TODO: Simplify preds to not branch here if possible!
1352 } else if (FallThrough->isEHPad()) {
1353 // Don't rewrite to a landing pad fallthough. That could lead to the case
1354 // where a BB jumps to more than one landing pad.
1355 // TODO: Is it ever worth rewriting predecessors which don't already
1356 // jump to a landing pad, and so can safely jump to the fallthrough?
1357 } else if (MBB->isSuccessor(&*FallThrough)) {
1358 // Rewrite all predecessors of the old block to go to the fallthrough
1359 // instead.
1360 while (!MBB->pred_empty()) {
1361 MachineBasicBlock *Pred = *(MBB->pred_end()-1);
1362 Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);
1363 }
1364 // If MBB was the target of a jump table, update jump tables to go to the
1365 // fallthrough instead.
1366 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1367 MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);
1368 MadeChange = true;
1369 }
1370 return MadeChange;
1371 }
1372
1373 // Check to see if we can simplify the terminator of the block before this
1374 // one.
1375 MachineBasicBlock &PrevBB = *std::prev(MachineFunction::iterator(MBB));
1376
1377 MachineBasicBlock *PriorTBB = nullptr, *PriorFBB = nullptr;
1379 bool PriorUnAnalyzable =
1380 TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);
1381 if (!PriorUnAnalyzable) {
1382 // If the previous branch is conditional and both conditions go to the same
1383 // destination, remove the branch, replacing it with an unconditional one or
1384 // a fall-through.
1385 if (PriorTBB && PriorTBB == PriorFBB) {
1386 DebugLoc dl = getBranchDebugLoc(PrevBB);
1387 TII->removeBranch(PrevBB);
1388 PriorCond.clear();
1389 if (PriorTBB != MBB)
1390 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1391 MadeChange = true;
1392 ++NumBranchOpts;
1393 goto ReoptimizeBlock;
1394 }
1395
1396 // If the previous block unconditionally falls through to this block and
1397 // this block has no other predecessors, move the contents of this block
1398 // into the prior block. This doesn't usually happen when SimplifyCFG
1399 // has been used, but it can happen if tail merging splits a fall-through
1400 // predecessor of a block.
1401 // This has to check PrevBB->succ_size() because EH edges are ignored by
1402 // analyzeBranch.
1403 if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&
1404 PrevBB.succ_size() == 1 &&
1405 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1406 LLVM_DEBUG(dbgs() << "\nMerging into block: " << PrevBB
1407 << "From MBB: " << *MBB);
1408 // Remove redundant DBG_VALUEs first.
1409 if (!PrevBB.empty()) {
1410 MachineBasicBlock::iterator PrevBBIter = PrevBB.end();
1411 --PrevBBIter;
1413 // Check if DBG_VALUE at the end of PrevBB is identical to the
1414 // DBG_VALUE at the beginning of MBB.
1415 while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()
1416 && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {
1417 if (!MBBIter->isIdenticalTo(*PrevBBIter))
1418 break;
1419 MachineInstr &DuplicateDbg = *MBBIter;
1420 ++MBBIter; -- PrevBBIter;
1421 DuplicateDbg.eraseFromParent();
1422 }
1423 }
1424 PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());
1425 PrevBB.removeSuccessor(PrevBB.succ_begin());
1426 assert(PrevBB.succ_empty());
1427 PrevBB.transferSuccessors(MBB);
1428 MadeChange = true;
1429 return MadeChange;
1430 }
1431
1432 // If the previous branch *only* branches to *this* block (conditional or
1433 // not) remove the branch.
1434 if (PriorTBB == MBB && !PriorFBB) {
1435 TII->removeBranch(PrevBB);
1436 MadeChange = true;
1437 ++NumBranchOpts;
1438 goto ReoptimizeBlock;
1439 }
1440
1441 // If the prior block branches somewhere else on the condition and here if
1442 // the condition is false, remove the uncond second branch.
1443 if (PriorFBB == MBB) {
1444 DebugLoc dl = getBranchDebugLoc(PrevBB);
1445 TII->removeBranch(PrevBB);
1446 TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);
1447 MadeChange = true;
1448 ++NumBranchOpts;
1449 goto ReoptimizeBlock;
1450 }
1451
1452 // If the prior block branches here on true and somewhere else on false, and
1453 // if the branch condition is reversible, reverse the branch to create a
1454 // fall-through.
1455 if (PriorTBB == MBB) {
1456 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1457 if (!TII->reverseBranchCondition(NewPriorCond)) {
1458 DebugLoc dl = getBranchDebugLoc(PrevBB);
1459 TII->removeBranch(PrevBB);
1460 TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);
1461 MadeChange = true;
1462 ++NumBranchOpts;
1463 goto ReoptimizeBlock;
1464 }
1465 }
1466
1467 // If this block has no successors (e.g. it is a return block or ends with
1468 // a call to a no-return function like abort or __cxa_throw) and if the pred
1469 // falls through into this block, and if it would otherwise fall through
1470 // into the block after this, move this block to the end of the function.
1471 //
1472 // We consider it more likely that execution will stay in the function (e.g.
1473 // due to loops) than it is to exit it. This asserts in loops etc, moving
1474 // the assert condition out of the loop body.
1475 if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
1476 MachineFunction::iterator(PriorTBB) == FallThrough &&
1477 !MBB->canFallThrough()) {
1478 bool DoTransform = true;
1479
1480 // We have to be careful that the succs of PredBB aren't both no-successor
1481 // blocks. If neither have successors and if PredBB is the second from
1482 // last block in the function, we'd just keep swapping the two blocks for
1483 // last. Only do the swap if one is clearly better to fall through than
1484 // the other.
1485 if (FallThrough == --MF.end() &&
1486 !IsBetterFallthrough(PriorTBB, MBB))
1487 DoTransform = false;
1488
1489 if (DoTransform) {
1490 // Reverse the branch so we will fall through on the previous true cond.
1491 SmallVector<MachineOperand, 4> NewPriorCond(PriorCond);
1492 if (!TII->reverseBranchCondition(NewPriorCond)) {
1493 LLVM_DEBUG(dbgs() << "\nMoving MBB: " << *MBB
1494 << "To make fallthrough to: " << *PriorTBB << "\n");
1495
1496 DebugLoc dl = getBranchDebugLoc(PrevBB);
1497 TII->removeBranch(PrevBB);
1498 TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);
1499
1500 // Move this block to the end of the function.
1501 MBB->moveAfter(&MF.back());
1502 MadeChange = true;
1503 ++NumBranchOpts;
1504 return MadeChange;
1505 }
1506 }
1507 }
1508 }
1509
1510 if (!IsEmptyBlock(MBB)) {
1512 if (TII->isUnconditionalTailCall(TailCall)) {
1514 for (auto &Pred : MBB->predecessors()) {
1515 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1517 bool PredAnalyzable =
1518 !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
1519
1520 // Only eliminate if MBB == TBB (Taken Basic Block)
1521 if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB &&
1522 PredTBB != PredFBB) {
1523 // The predecessor has a conditional branch to this block which
1524 // consists of only a tail call. Try to fold the tail call into the
1525 // conditional branch.
1526 if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
1527 // TODO: It would be nice if analyzeBranch() could provide a pointer
1528 // to the branch instruction so replaceBranchWithTailCall() doesn't
1529 // have to search for it.
1530 TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
1531 PredsChanged.push_back(Pred);
1532 }
1533 }
1534 // If the predecessor is falling through to this block, we could reverse
1535 // the branch condition and fold the tail call into that. However, after
1536 // that we might have to re-arrange the CFG to fall through to the other
1537 // block and there is a high risk of regressing code size rather than
1538 // improving it.
1539 }
1540 if (!PredsChanged.empty()) {
1541 NumTailCalls += PredsChanged.size();
1542 for (auto &Pred : PredsChanged)
1543 Pred->removeSuccessor(MBB);
1544
1545 return true;
1546 }
1547 }
1548 }
1549
1550 if (!CurUnAnalyzable) {
1551 // If this is a two-way branch, and the FBB branches to this block, reverse
1552 // the condition so the single-basic-block loop is faster. Instead of:
1553 // Loop: xxx; jcc Out; jmp Loop
1554 // we want:
1555 // Loop: xxx; jncc Loop; jmp Out
1556 if (CurTBB && CurFBB && CurFBB == MBB && CurTBB != MBB) {
1557 SmallVector<MachineOperand, 4> NewCond(CurCond);
1558 if (!TII->reverseBranchCondition(NewCond)) {
1560 TII->removeBranch(*MBB);
1561 TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);
1562 MadeChange = true;
1563 ++NumBranchOpts;
1564 goto ReoptimizeBlock;
1565 }
1566 }
1567
1568 // If this branch is the only thing in its block, see if we can forward
1569 // other blocks across it.
1570 if (CurTBB && CurCond.empty() && !CurFBB &&
1571 IsBranchOnlyBlock(MBB) && CurTBB != MBB &&
1572 !MBB->hasAddressTaken() && !MBB->isEHPad()) {
1574 // This block may contain just an unconditional branch. Because there can
1575 // be 'non-branch terminators' in the block, try removing the branch and
1576 // then seeing if the block is empty.
1577 TII->removeBranch(*MBB);
1578 // If the only things remaining in the block are debug info, remove these
1579 // as well, so this will behave the same as an empty block in non-debug
1580 // mode.
1581 if (IsEmptyBlock(MBB)) {
1582 // Make the block empty, losing the debug info (we could probably
1583 // improve this in some cases.)
1584 MBB->erase(MBB->begin(), MBB->end());
1585 }
1586 // If this block is just an unconditional branch to CurTBB, we can
1587 // usually completely eliminate the block. The only case we cannot
1588 // completely eliminate the block is when the block before this one
1589 // falls through into MBB and we can't understand the prior block's branch
1590 // condition.
1591 if (MBB->empty()) {
1592 bool PredHasNoFallThrough = !PrevBB.canFallThrough();
1593 if (PredHasNoFallThrough || !PriorUnAnalyzable ||
1594 !PrevBB.isSuccessor(MBB)) {
1595 // If the prior block falls through into us, turn it into an
1596 // explicit branch to us to make updates simpler.
1597 if (!PredHasNoFallThrough && PrevBB.isSuccessor(MBB) &&
1598 PriorTBB != MBB && PriorFBB != MBB) {
1599 if (!PriorTBB) {
1600 assert(PriorCond.empty() && !PriorFBB &&
1601 "Bad branch analysis");
1602 PriorTBB = MBB;
1603 } else {
1604 assert(!PriorFBB && "Machine CFG out of date!");
1605 PriorFBB = MBB;
1606 }
1607 DebugLoc pdl = getBranchDebugLoc(PrevBB);
1608 TII->removeBranch(PrevBB);
1609 TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);
1610 }
1611
1612 // Iterate through all the predecessors, revectoring each in-turn.
1613 size_t PI = 0;
1614 bool DidChange = false;
1615 bool HasBranchToSelf = false;
1616 while(PI != MBB->pred_size()) {
1617 MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);
1618 if (PMBB == MBB) {
1619 // If this block has an uncond branch to itself, leave it.
1620 ++PI;
1621 HasBranchToSelf = true;
1622 } else {
1623 DidChange = true;
1624 PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);
1625 // If this change resulted in PMBB ending in a conditional
1626 // branch where both conditions go to the same destination,
1627 // change this to an unconditional branch.
1628 MachineBasicBlock *NewCurTBB = nullptr, *NewCurFBB = nullptr;
1630 bool NewCurUnAnalyzable = TII->analyzeBranch(
1631 *PMBB, NewCurTBB, NewCurFBB, NewCurCond, true);
1632 if (!NewCurUnAnalyzable && NewCurTBB && NewCurTBB == NewCurFBB) {
1633 DebugLoc pdl = getBranchDebugLoc(*PMBB);
1634 TII->removeBranch(*PMBB);
1635 NewCurCond.clear();
1636 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);
1637 MadeChange = true;
1638 ++NumBranchOpts;
1639 }
1640 }
1641 }
1642
1643 // Change any jumptables to go to the new MBB.
1644 if (MachineJumpTableInfo *MJTI = MF.getJumpTableInfo())
1645 MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);
1646 if (DidChange) {
1647 ++NumBranchOpts;
1648 MadeChange = true;
1649 if (!HasBranchToSelf) return MadeChange;
1650 }
1651 }
1652 }
1653
1654 // Add the branch back if the block is more than just an uncond branch.
1655 TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);
1656 }
1657 }
1658
1659 // If the prior block doesn't fall through into this block, and if this
1660 // block doesn't fall through into some other block, see if we can find a
1661 // place to move this block where a fall-through will happen.
1662 if (!PrevBB.canFallThrough()) {
1663 // Now we know that there was no fall-through into this block, check to
1664 // see if it has a fall-through into its successor.
1665 bool CurFallsThru = MBB->canFallThrough();
1666
1667 if (!MBB->isEHPad()) {
1668 // Check all the predecessors of this block. If one of them has no fall
1669 // throughs, and analyzeBranch thinks it _could_ fallthrough to this
1670 // block, move this block right after it.
1671 for (MachineBasicBlock *PredBB : MBB->predecessors()) {
1672 // Analyze the branch at the end of the pred.
1673 MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
1675 if (PredBB != MBB && !PredBB->canFallThrough() &&
1676 !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&
1677 (PredTBB == MBB || PredFBB == MBB) &&
1678 (!CurFallsThru || !CurTBB || !CurFBB) &&
1679 (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {
1680 // If the current block doesn't fall through, just move it.
1681 // If the current block can fall through and does not end with a
1682 // conditional branch, we need to append an unconditional jump to
1683 // the (current) next block. To avoid a possible compile-time
1684 // infinite loop, move blocks only backward in this case.
1685 // Also, if there are already 2 branches here, we cannot add a third;
1686 // this means we have the case
1687 // Bcc next
1688 // B elsewhere
1689 // next:
1690 if (CurFallsThru) {
1691 MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());
1692 CurCond.clear();
1693 TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());
1694 }
1695 MBB->moveAfter(PredBB);
1696 MadeChange = true;
1697 goto ReoptimizeBlock;
1698 }
1699 }
1700 }
1701
1702 if (!CurFallsThru) {
1703 // Check analyzable branch-successors to see if we can move this block
1704 // before one.
1705 if (!CurUnAnalyzable) {
1706 for (MachineBasicBlock *SuccBB : {CurFBB, CurTBB}) {
1707 if (!SuccBB)
1708 continue;
1709 // Analyze the branch at the end of the block before the succ.
1710 MachineFunction::iterator SuccPrev = --SuccBB->getIterator();
1711
1712 // If this block doesn't already fall-through to that successor, and
1713 // if the succ doesn't already have a block that can fall through into
1714 // it, we can arrange for the fallthrough to happen.
1715 if (SuccBB != MBB && &*SuccPrev != MBB &&
1716 !SuccPrev->canFallThrough()) {
1717 MBB->moveBefore(SuccBB);
1718 MadeChange = true;
1719 goto ReoptimizeBlock;
1720 }
1721 }
1722 }
1723
1724 // Okay, there is no really great place to put this block. If, however,
1725 // the block before this one would be a fall-through if this block were
1726 // removed, move this block to the end of the function. There is no real
1727 // advantage in "falling through" to an EH block, so we don't want to
1728 // perform this transformation for that case.
1729 //
1730 // Also, Windows EH introduced the possibility of an arbitrary number of
1731 // successors to a given block. The analyzeBranch call does not consider
1732 // exception handling and so we can get in a state where a block
1733 // containing a call is followed by multiple EH blocks that would be
1734 // rotated infinitely at the end of the function if the transformation
1735 // below were performed for EH "FallThrough" blocks. Therefore, even if
1736 // that appears not to be happening anymore, we should assume that it is
1737 // possible and not remove the "!FallThrough()->isEHPad" condition below.
1738 MachineBasicBlock *PrevTBB = nullptr, *PrevFBB = nullptr;
1740 if (FallThrough != MF.end() &&
1741 !FallThrough->isEHPad() &&
1742 !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&
1743 PrevBB.isSuccessor(&*FallThrough)) {
1744 MBB->moveAfter(&MF.back());
1745 MadeChange = true;
1746 return MadeChange;
1747 }
1748 }
1749 }
1750
1751 return MadeChange;
1752}
1753
1754//===----------------------------------------------------------------------===//
1755// Hoist Common Code
1756//===----------------------------------------------------------------------===//
1757
1758bool BranchFolder::HoistCommonCode(MachineFunction &MF) {
1759 bool MadeChange = false;
1761 MadeChange |= HoistCommonCodeInSuccs(&MBB);
1762
1763 return MadeChange;
1764}
1765
1766/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1767/// its 'true' successor.
1769 MachineBasicBlock *TrueBB) {
1770 for (MachineBasicBlock *SuccBB : BB->successors())
1771 if (SuccBB != TrueBB)
1772 return SuccBB;
1773 return nullptr;
1774}
1775
1776template <class Container>
1778 Container &Set) {
1779 if (Reg.isPhysical()) {
1780 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
1781 Set.insert(*AI);
1782 } else {
1783 Set.insert(Reg);
1784 }
1785}
1786
1787/// findHoistingInsertPosAndDeps - Find the location to move common instructions
1788/// in successors to. The location is usually just before the terminator,
1789/// however if the terminator is a conditional branch and its previous
1790/// instruction is the flag setting instruction, the previous instruction is
1791/// the preferred location. This function also gathers uses and defs of the
1792/// instructions from the insertion point to the end of the block. The data is
1793/// used by HoistCommonCodeInSuccs to ensure safety.
1794static
1796 const TargetInstrInfo *TII,
1797 const TargetRegisterInfo *TRI,
1799 SmallSet<Register, 4> &Defs) {
1801 if (!TII->isUnpredicatedTerminator(*Loc))
1802 return MBB->end();
1803
1804 for (const MachineOperand &MO : Loc->operands()) {
1805 if (!MO.isReg())
1806 continue;
1807 Register Reg = MO.getReg();
1808 if (!Reg)
1809 continue;
1810 if (MO.isUse()) {
1812 } else {
1813 if (!MO.isDead())
1814 // Don't try to hoist code in the rare case the terminator defines a
1815 // register that is later used.
1816 return MBB->end();
1817
1818 // If the terminator defines a register, make sure we don't hoist
1819 // the instruction whose def might be clobbered by the terminator.
1820 addRegAndItsAliases(Reg, TRI, Defs);
1821 }
1822 }
1823
1824 if (Uses.empty())
1825 return Loc;
1826 // If the terminator is the only instruction in the block and Uses is not
1827 // empty (or we would have returned above), we can still safely hoist
1828 // instructions just before the terminator as long as the Defs/Uses are not
1829 // violated (which is checked in HoistCommonCodeInSuccs).
1830 if (Loc == MBB->begin())
1831 return Loc;
1832
1833 // The terminator is probably a conditional branch, try not to separate the
1834 // branch from condition setting instruction.
1836
1837 bool IsDef = false;
1838 for (const MachineOperand &MO : PI->operands()) {
1839 // If PI has a regmask operand, it is probably a call. Separate away.
1840 if (MO.isRegMask())
1841 return Loc;
1842 if (!MO.isReg() || MO.isUse())
1843 continue;
1844 Register Reg = MO.getReg();
1845 if (!Reg)
1846 continue;
1847 if (Uses.count(Reg)) {
1848 IsDef = true;
1849 break;
1850 }
1851 }
1852 if (!IsDef)
1853 // The condition setting instruction is not just before the conditional
1854 // branch.
1855 return Loc;
1856
1857 // Be conservative, don't insert instruction above something that may have
1858 // side-effects. And since it's potentially bad to separate flag setting
1859 // instruction from the conditional branch, just abort the optimization
1860 // completely.
1861 // Also avoid moving code above predicated instruction since it's hard to
1862 // reason about register liveness with predicated instruction.
1863 bool DontMoveAcrossStore = true;
1864 if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))
1865 return MBB->end();
1866
1867 // Find out what registers are live. Note this routine is ignoring other live
1868 // registers which are only used by instructions in successor blocks.
1869 for (const MachineOperand &MO : PI->operands()) {
1870 if (!MO.isReg())
1871 continue;
1872 Register Reg = MO.getReg();
1873 if (!Reg)
1874 continue;
1875 if (MO.isUse()) {
1877 } else {
1878 if (Uses.erase(Reg)) {
1879 if (Reg.isPhysical()) {
1880 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
1881 Uses.erase(*SubRegs); // Use sub-registers to be conservative
1882 }
1883 }
1884 addRegAndItsAliases(Reg, TRI, Defs);
1885 }
1886 }
1887
1888 return PI;
1889}
1890
1891bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
1892 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1894 if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())
1895 return false;
1896
1897 if (!FBB) FBB = findFalseBlock(MBB, TBB);
1898 if (!FBB)
1899 // Malformed bcc? True and false blocks are the same?
1900 return false;
1901
1902 // Restrict the optimization to cases where MBB is the only predecessor,
1903 // it is an obvious win.
1904 if (TBB->pred_size() > 1 || FBB->pred_size() > 1)
1905 return false;
1906
1907 // Find a suitable position to hoist the common instructions to. Also figure
1908 // out which registers are used or defined by instructions from the insertion
1909 // point to the end of the block.
1912 findHoistingInsertPosAndDeps(MBB, TII, TRI, Uses, Defs);
1913 if (Loc == MBB->end())
1914 return false;
1915
1916 bool HasDups = false;
1917 SmallSet<Register, 4> ActiveDefsSet, AllDefsSet;
1919 MachineBasicBlock::iterator FIB = FBB->begin();
1921 MachineBasicBlock::iterator FIE = FBB->end();
1922 while (TIB != TIE && FIB != FIE) {
1923 // Skip dbg_value instructions. These do not count.
1924 TIB = skipDebugInstructionsForward(TIB, TIE, false);
1925 FIB = skipDebugInstructionsForward(FIB, FIE, false);
1926 if (TIB == TIE || FIB == FIE)
1927 break;
1928
1929 if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
1930 break;
1931
1932 if (TII->isPredicated(*TIB))
1933 // Hard to reason about register liveness with predicated instruction.
1934 break;
1935
1936 bool IsSafe = true;
1937 for (MachineOperand &MO : TIB->operands()) {
1938 // Don't attempt to hoist instructions with register masks.
1939 if (MO.isRegMask()) {
1940 IsSafe = false;
1941 break;
1942 }
1943 if (!MO.isReg())
1944 continue;
1945 Register Reg = MO.getReg();
1946 if (!Reg)
1947 continue;
1948 if (MO.isDef()) {
1949 if (Uses.count(Reg)) {
1950 // Avoid clobbering a register that's used by the instruction at
1951 // the point of insertion.
1952 IsSafe = false;
1953 break;
1954 }
1955
1956 if (Defs.count(Reg) && !MO.isDead()) {
1957 // Don't hoist the instruction if the def would be clobber by the
1958 // instruction at the point insertion. FIXME: This is overly
1959 // conservative. It should be possible to hoist the instructions
1960 // in BB2 in the following example:
1961 // BB1:
1962 // r1, eflag = op1 r2, r3
1963 // brcc eflag
1964 //
1965 // BB2:
1966 // r1 = op2, ...
1967 // = op3, killed r1
1968 IsSafe = false;
1969 break;
1970 }
1971 } else if (!ActiveDefsSet.count(Reg)) {
1972 if (Defs.count(Reg)) {
1973 // Use is defined by the instruction at the point of insertion.
1974 IsSafe = false;
1975 break;
1976 }
1977
1978 if (MO.isKill() && Uses.count(Reg))
1979 // Kills a register that's read by the instruction at the point of
1980 // insertion. Remove the kill marker.
1981 MO.setIsKill(false);
1982 }
1983 }
1984 if (!IsSafe)
1985 break;
1986
1987 bool DontMoveAcrossStore = true;
1988 if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))
1989 break;
1990
1991 // Remove kills from ActiveDefsSet, these registers had short live ranges.
1992 for (const MachineOperand &MO : TIB->operands()) {
1993 if (!MO.isReg() || !MO.isUse() || !MO.isKill())
1994 continue;
1995 Register Reg = MO.getReg();
1996 if (!Reg)
1997 continue;
1998 if (!AllDefsSet.count(Reg)) {
1999 continue;
2000 }
2001 if (Reg.isPhysical()) {
2002 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
2003 ActiveDefsSet.erase(*AI);
2004 } else {
2005 ActiveDefsSet.erase(Reg);
2006 }
2007 }
2008
2009 // Track local defs so we can update liveins.
2010 for (const MachineOperand &MO : TIB->operands()) {
2011 if (!MO.isReg() || !MO.isDef() || MO.isDead())
2012 continue;
2013 Register Reg = MO.getReg();
2014 if (!Reg || Reg.isVirtual())
2015 continue;
2016 addRegAndItsAliases(Reg, TRI, ActiveDefsSet);
2017 addRegAndItsAliases(Reg, TRI, AllDefsSet);
2018 }
2019
2020 HasDups = true;
2021 ++TIB;
2022 ++FIB;
2023 }
2024
2025 if (!HasDups)
2026 return false;
2027
2028 MBB->splice(Loc, TBB, TBB->begin(), TIB);
2029 FBB->erase(FBB->begin(), FIB);
2030
2031 if (UpdateLiveIns) {
2033 recomputeLiveIns(*FBB);
2034 }
2035
2036 ++NumHoist;
2037 return true;
2038}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
SmallPtrSet< MachineInstr *, 2 > Uses
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
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:454
BitVector & set()
Definition: BitVector.h:344
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:152
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 const DILocation * getMergedLocation(const DILocation *LocA, const 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:150
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:644
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.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MCSubRegIterator enumerates all sub-registers of 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 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:862
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:887
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:910
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:164
bool erase(const T &V)
Definition: SmallSet.h:205
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:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:386
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:721
static void recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for MBB.
Definition: LivePhysRegs.h:198
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.
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:1643
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:758
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
Pair of physical register and lane mask.