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