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