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