1 //===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
17 //===----------------------------------------------------------------------===//
65 #define DEBUG_TYPE "branch-folder"
73 static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
78 TailMergeThreshold("tail-merge-threshold",
84 TailMergeSize("tail-merge-size",
90   /// BranchFolderPass - Wrap branch folder in a machine function pass.
130                          PassConfig->getEnableTailMerge();  in runOnMachineFunction()
157   assert(MBB->pred_empty() && "MBB must be dead!");  in RemoveDeadBlock()
160   MachineFunction *MF = MBB->getParent();  in RemoveDeadBlock()
162   while (!MBB->succ_empty())  in RemoveDeadBlock()
163     MBB->removeSuccessor(MBB->succ_end()-1);  in RemoveDeadBlock()
171       MF->eraseCallSiteInfo(&MI);  in RemoveDeadBlock()
174   MF->erase(MBB);  in RemoveDeadBlock()
177     MLI->removeBlock(MBB);  in RemoveDeadBlock()
193   this->MRI = &MRI;  in OptimizeFunction()
198                               : TII->getTailMergeSize(MF);  in OptimizeFunction()
201   UpdateLiveIns = MRI.tracksLiveness() && TRI->trackLivenessAfterRegAlloc(MF);  in OptimizeFunction()
229   BitVector JTIsLive(JTI->getJumpTables().size());  in OptimizeFunction()
244       JTI->RemoveJumpTable(i);  in OptimizeFunction()
251 //===----------------------------------------------------------------------===//
253 //===----------------------------------------------------------------------===//
255 /// HashMachineInstr - Compute a hash value for MI and its operands.
273       OperandHash = Op.getMBB()->getNumber();  in HashMachineInstr()
295 /// HashEndOfMBB - Hash the last instruction in the MBB.
315   while (I != MBB->begin()) {  in skipBackwardPastNonInstructions()
316     --I;  in skipBackwardPastNonInstructions()
320   return MBB->end();  in skipBackwardPastNonInstructions()
328 /// Non-instructions according to countsAsInstruction are ignored.
333   MachineBasicBlock::iterator MBBI1 = MBB1->end();  in ComputeCommonTailLength()
334   MachineBasicBlock::iterator MBBI2 = MBB2->end();  in ComputeCommonTailLength()
340     if (MBBI1 == MBB1->end() || MBBI2 == MBB2->end())  in ComputeCommonTailLength()
342     if (!MBBI1->isIdenticalTo(*MBBI2) ||  in ComputeCommonTailLength()
348         MBBI1->isInlineAsm()) {  in ComputeCommonTailLength()
351     if (MBBI1->getFlag(MachineInstr::NoMerge) ||  in ComputeCommonTailLength()
352         MBBI2->getFlag(MachineInstr::NoMerge))  in ComputeCommonTailLength()
366     MachineBasicBlock &OldMBB = *OldInst->getParent();  in replaceTailWithBranchTo()
372       --I;  in replaceTailWithBranchTo()
376     // Merging the tails may have switched some undef operand to non-undef ones.  in replaceTailWithBranchTo()
388       BuildMI(OldMBB, OldInst, DL, TII->get(TargetOpcode::IMPLICIT_DEF), Reg);  in replaceTailWithBranchTo()
392   TII->ReplaceTailWithBranchTo(OldInst, &NewDest);  in replaceTailWithBranchTo()
399   if (!TII->isLegalToSplitMBBAt(CurMBB, BBI1))  in SplitMBBAt()
404   // Create the fall-through block.  in SplitMBBAt()
407   CurMBB.getParent()->insert(++MBBI, NewMBB);  in SplitMBBAt()
410   NewMBB->transferSuccessors(&CurMBB);  in SplitMBBAt()
412   // Add an edge from CurMBB to NewMBB for the fall-through.  in SplitMBBAt()
416   NewMBB->splice(NewMBB->end(), &CurMBB, BBI1, CurMBB.end());  in SplitMBBAt()
420     if (MachineLoop *ML = MLI->getLoopFor(&CurMBB))  in SplitMBBAt()
421       ML->addBasicBlockToLoop(NewMBB, *MLI);  in SplitMBBAt()
432     auto n = EHScopeI->second;  in SplitMBBAt()
439 /// EstimateRuntime - Make a rough estimate for how long it will take to run
447     if (I->isCall())  in EstimateRuntime()
449     else if (I->mayLoadOrStore())  in EstimateRuntime()
463   MachineFunction *MF = CurMBB->getParent();  in FixTail()
467   DebugLoc dl = CurMBB->findBranchDebugLoc();  in FixTail()
470   if (I != MF->end() && !TII->analyzeBranch(*CurMBB, TBB, FBB, Cond, true)) {  in FixTail()
473       if (!TII->reverseBranchCondition(Cond)) {  in FixTail()
474         TII->removeBranch(*CurMBB);  in FixTail()
475         TII->insertBranch(*CurMBB, SuccBB, nullptr, Cond, dl);  in FixTail()
480   TII->insertBranch(*CurMBB, SuccBB, nullptr,  in FixTail()
490   if (getBlock()->getNumber() < o.getBlock()->getNumber())  in operator <()
492   if (getBlock()->getNumber() > o.getBlock()->getNumber())  in operator <()
497 /// CountTerminators - Count the number of terminators in the given
498 /// block and set I to the position of the first non-terminator, if there
499 /// is one, or MBB->end() otherwise.
502   I = MBB->end();  in CountTerminators()
505     if (I == MBB->begin()) {  in CountTerminators()
506       I = MBB->end();  in CountTerminators()
509     --I;  in CountTerminators()
510     if (!I->isTerminator()) break;  in CountTerminators()
516 /// A no successor, non-return block probably ends in unreachable and is cold.
520   if (!MBB->succ_empty())  in blockEndsInUnreachable()
522   if (MBB->empty())  in blockEndsInUnreachable()
524   return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());  in blockEndsInUnreachable()
527 /// ProfitableToMerge - Check if two machine basic blocks have a common tail
542 ///                 thresholds apply to prevent undoing tail-duplication.
553   // It is never profitable to tail-merge blocks from two different EH scopes.  in ProfitableToMerge()
559     if (EHScope1->second != EHScope2->second)  in ProfitableToMerge()
572   // only got debug instructions before the tail (to be invariant on -g).  in ProfitableToMerge()
573   if (skipDebugInstructionsForward(MBB1->begin(), MBB1->end(), false) == I1)  in ProfitableToMerge()
574     I1 = MBB1->begin();  in ProfitableToMerge()
575   if (skipDebugInstructionsForward(MBB2->begin(), MBB2->end(), false) == I2)  in ProfitableToMerge()
576     I2 = MBB2->begin();  in ProfitableToMerge()
578   bool FullBlockTail1 = I1 == MBB1->begin();  in ProfitableToMerge()
579   bool FullBlockTail2 = I2 == MBB2->begin();  in ProfitableToMerge()
581   // It's almost always profitable to merge any number of non-terminator  in ProfitableToMerge()
585   // TODO: Re-visit successor size for non-layout tail merging.  in ProfitableToMerge()
587       (!AfterPlacement || MBB1->succ_size() == 1)) {  in ProfitableToMerge()
594   // If these are identical non-return blocks with no successors, merge them.  in ProfitableToMerge()
607   if (MBB1->isLayoutSuccessor(MBB2) && FullBlockTail2)  in ProfitableToMerge()
609   if (MBB2->isLayoutSuccessor(MBB1) && FullBlockTail1)  in ProfitableToMerge()
618       if (!MBB->succ_empty() && !MBB->canFallThrough())  in ProfitableToMerge()
621       MachineFunction *MF = MBB->getParent();  in ProfitableToMerge()
622       return (MBB != &*MF->begin()) && std::prev(I)->canFallThrough();  in ProfitableToMerge()
630   // heuristics. This heuristic is only accurate for single-succ blocks, so to  in ProfitableToMerge()
635       (MBB1->succ_size() == 1 || !AfterPlacement) &&  in ProfitableToMerge()
636       !MBB1->back().isBarrier() &&  in ProfitableToMerge()
637       !MBB2->back().isBarrier())  in ProfitableToMerge()
648   MachineFunction *MF = MBB1->getParent();  in ProfitableToMerge()
650       MF->getFunction().hasOptSize() ||  in ProfitableToMerge()
667        CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {  in ComputeSameTails()
668     for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {  in ComputeSameTails()
670       if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),  in ComputeSameTails()
700        CurMPIter->getHash() == CurHash; --CurMPIter) {  in RemoveBlocksWithHash()
702     MachineBasicBlock *CurMBB = CurMPIter->getBlock();  in RemoveBlocksWithHash()
708   if (CurMPIter->getHash() != CurHash)  in RemoveBlocksWithHash()
727     unsigned t = EstimateRuntime(SameTails[i].getBlock()->begin(),  in CreateCommonTailOnlyBlock()
742   // If the split block unconditionally falls-thru to SuccBB, it will be  in CreateCommonTailOnlyBlock()
745   const BasicBlock *BB = (SuccBB && MBB->succ_size() == 1) ?  in CreateCommonTailOnlyBlock()
746     SuccBB->getBasicBlock() : MBB->getBasicBlock();  in CreateCommonTailOnlyBlock()
754   SameTails[commonTailIndex].setTailStartPos(newMBB->begin());  in CreateCommonTailOnlyBlock()
766   MachineBasicBlock *MBB = MBBIStartPos->getParent();  in mergeOperations()
771   for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)  in mergeOperations()
774   MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin();  in mergeOperations()
775   MachineBasicBlock::reverse_iterator MBBIE = MBB->rend();  in mergeOperations()
779   while (CommonTailLen--) {  in mergeOperations()
793     assert(MBBICommon->isIdenticalTo(*MBBI) && "Expected matching MIIs!");  in mergeOperations()
796     if (MBBICommon->mayLoadOrStore())  in mergeOperations()
797       MBBICommon->cloneMergedMemRefs(*MBB->getParent(), {&*MBBICommon, &*MBBI});  in mergeOperations()
799     for (unsigned I = 0, E = MBBICommon->getNumOperands(); I != E; ++I) {  in mergeOperations()
800       MachineOperand &MO = MBBICommon->getOperand(I);  in mergeOperations()
802         const MachineOperand &OtherMO = MBBI->getOperand(I);  in mergeOperations()
822       assert(SameTails[i].getTailStartPos() == MBB->begin() &&  in mergeCommonTails()
835       auto &Pos = NextCommonInsts[i];  in mergeCommonTails()  local
836       assert(Pos != SameTails[i].getBlock()->end() &&  in mergeCommonTails()
838       while (!countsAsInstruction(*Pos)) {  in mergeCommonTails()
839         ++Pos;  in mergeCommonTails()
840         assert(Pos != SameTails[i].getBlock()->end() &&  in mergeCommonTails()
843       assert(MI.isIdenticalTo(*Pos) && "Expected matching MIIs!");  in mergeCommonTails()
844       DL = DILocation::getMergedLocation(DL, Pos->getDebugLoc());  in mergeCommonTails()
845       NextCommonInsts[i] = ++Pos;  in mergeCommonTails()
857     for (MachineBasicBlock *Pred : MBB->predecessors()) {  in mergeCommonTails()
860       MachineBasicBlock::iterator InsertBefore = Pred->getFirstTerminator();  in mergeCommonTails()
867         if (any_of(TRI->superregs(Reg), [&](MCPhysReg SReg) {  in mergeCommonTails()
868               return NewLiveIns.contains(SReg) && !MRI->isReserved(SReg);  in mergeCommonTails()
873         BuildMI(*Pred, InsertBefore, DL, TII->get(TargetOpcode::IMPLICIT_DEF),  in mergeCommonTails()
878     MBB->clearLiveIns();  in mergeCommonTails()
884 // successor, or all have no successor if it is null) can be tail-merged.
886 // tail-merged and are not immediately before Succ must have an unconditional
890 // MinCommonTailLength - Except for the special cases below, tail-merge if
901       << (i == e - 1 ? "" : ", ");  in TryTailMergeBlocks()
905           dbgs() << "  which has fall-through from "  in TryTailMergeBlocks()
938         &MergePotentials.front().getBlock()->getParent()->front();  in TryTailMergeBlocks()
943         SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&  in TryTailMergeBlocks()
944         SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())  in TryTailMergeBlocks()
947              SameTails[1].getBlock()->isLayoutSuccessor(  in TryTailMergeBlocks()
950              !SameTails[0].getBlock()->isEHPad())  in TryTailMergeBlocks()
953       // Otherwise just pick one, favoring the fall-through predecessor if  in TryTailMergeBlocks()
957         if ((MBB == EntryBB || MBB->isEHPad()) &&  in TryTailMergeBlocks()
998                         << (i == e - 1 ? "" : ", "));  in TryTailMergeBlocks()
1054   // a compile-time infinite loop repeatedly doing and undoing the same  in TailMergeBlocks()
1059     if (I->pred_size() < 2) continue;  in TailMergeBlocks()
1067     // -- If merging predecessors that belong to the same loop as IBB, the  in TailMergeBlocks()
1072     // --If merging predecessors that do not belong to the same loop as IBB, the  in TailMergeBlocks()
1077       ML = MLI->getLoopFor(IBB);  in TailMergeBlocks()
1078       if (ML && IBB == ML->getHeader())  in TailMergeBlocks()
1082     for (MachineBasicBlock *PBB : I->predecessors()) {  in TailMergeBlocks()
1099       if (PBB->hasEHPadSuccessor() || PBB->mayHaveInlineAsmBr())  in TailMergeBlocks()
1106         if (ML != MLI->getLoopFor(PBB))  in TailMergeBlocks()
1111       if (!TII->analyzeBranch(*PBB, TBB, FBB, Cond, true)) {  in TailMergeBlocks()
1116           if (TII->reverseBranchCondition(NewCond))  in TailMergeBlocks()
1120             auto Next = ++PBB->getIterator();  in TailMergeBlocks()
1127         DebugLoc dl = PBB->findBranchDebugLoc();  in TailMergeBlocks()
1129           TII->removeBranch(*PBB);  in TailMergeBlocks()
1132             TII->insertBranch(*PBB, (TBB == IBB) ? FBB : TBB, nullptr,  in TailMergeBlocks()
1154         MergePotentials.begin()->getBlock() != PredBB)  in TailMergeBlocks()
1155       FixTail(MergePotentials.begin()->getBlock(), IBB, TII,  in TailMergeBlocks()
1156               MergePotentials.begin()->getBranchDebugLoc());  in TailMergeBlocks()
1200           EdgeFreq->getFrequency(), SumEdgeFreq);  in setCommonTailEdgeWeights()
1206 //===----------------------------------------------------------------------===//
1208 //===----------------------------------------------------------------------===//
1236   return MBB->getFirstNonDebugInstr(true) == MBB->end();  in IsEmptyBlock()
1242   MachineBasicBlock::iterator I = MBB->getFirstNonDebugInstr();  in IsBranchOnlyBlock()
1243   assert(I != MBB->end() && "empty block!");  in IsBranchOnlyBlock()
1244   return I->isBranch();  in IsBranchOnlyBlock()
1247 /// IsBetterFallthrough - Return true if it would be clearly better to
1248 /// fall-through to MBB1 than to fall through into MBB2.  This has to return
1259   MachineBasicBlock::iterator MBB1I = MBB1->getLastNonDebugInstr();  in IsBetterFallthrough()
1260   MachineBasicBlock::iterator MBB2I = MBB2->getLastNonDebugInstr();  in IsBetterFallthrough()
1261   if (MBB1I == MBB1->end() || MBB2I == MBB2->end())  in IsBetterFallthrough()
1266   if (MBB1->isSuccessor(MBB2)) return true;  in IsBetterFallthrough()
1267   if (MBB2->isSuccessor(MBB1)) return false;  in IsBetterFallthrough()
1269   return MBB2I->isCall() && !MBB1I->isCall();  in IsBetterFallthrough()
1272 /// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
1276   if (I != MBB.end() && I->isBranch())  in getBranchDebugLoc()
1277     return I->getDebugLoc();  in getBranchDebugLoc()
1287       TII->duplicate(PredMBB, InsertBefore, MI);  in copyDebugInfoToPredecessor()
1299       TII->duplicate(SuccMBB, InsertBefore, MI);  in copyDebugInfoToSuccessor()
1318     if (SuccBB->pred_size() == 1)  in salvageDebugInfoFromEmptyBlock()
1324     if (PredBB->succ_size() == 1)  in salvageDebugInfoFromEmptyBlock()
1330   MachineFunction &MF = *MBB->getParent();  in OptimizeBlock()
1333   MachineFunction::iterator FallThrough = MBB->getIterator();  in OptimizeBlock()
1343     SameEHScope = MBBEHScope->second == FallThroughEHScope->second;  in OptimizeBlock()
1346   // Analyze the branch in the current block. As a side-effect, this may cause  in OptimizeBlock()
1351       TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);  in OptimizeBlock()
1353   // If this block is empty, make everyone use its fall-through, not the block  in OptimizeBlock()
1354   // explicitly.  Landing pads should not do this since the landing-pad table  in OptimizeBlock()
1357   if (IsEmptyBlock(MBB) && !MBB->isEHPad() && !MBB->hasAddressTaken() &&  in OptimizeBlock()
1361     if (MBB->pred_empty()) return MadeChange;  in OptimizeBlock()
1365     } else if (FallThrough->isEHPad()) {  in OptimizeBlock()
1370     } else if (MBB->isSuccessor(&*FallThrough)) {  in OptimizeBlock()
1373       while (!MBB->pred_empty()) {  in OptimizeBlock()
1374         MachineBasicBlock *Pred = *(MBB->pred_end()-1);  in OptimizeBlock()
1375         Pred->ReplaceUsesOfBlockWith(MBB, &*FallThrough);  in OptimizeBlock()
1379       // landing-pad.  in OptimizeBlock()
1380       for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE; ++SI)  in OptimizeBlock()  local
1381         if (*SI != &*FallThrough && !FallThrough->isSuccessor(*SI)) {  in OptimizeBlock()
1382           assert((*SI)->isEHPad() && "Bad CFG");  in OptimizeBlock()
1383           FallThrough->copySuccessor(MBB, SI);  in OptimizeBlock()
1388         MJTI->ReplaceMBBInJumpTables(MBB, &*FallThrough);  in OptimizeBlock()
1401       TII->analyzeBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, true);  in OptimizeBlock()
1405     // a fall-through.  in OptimizeBlock()
1408       TII->removeBranch(PrevBB);  in OptimizeBlock()
1411         TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);  in OptimizeBlock()
1420     // has been used, but it can happen if tail merging splits a fall-through  in OptimizeBlock()
1422     // This has to check PrevBB->succ_size() because EH edges are ignored by  in OptimizeBlock()
1424     if (PriorCond.empty() && !PriorTBB && MBB->pred_size() == 1 &&  in OptimizeBlock()
1426         !MBB->hasAddressTaken() && !MBB->isEHPad()) {  in OptimizeBlock()
1432         --PrevBBIter;  in OptimizeBlock()
1433         MachineBasicBlock::iterator MBBIter = MBB->begin();  in OptimizeBlock()
1436         while (PrevBBIter != PrevBB.begin() && MBBIter != MBB->end()  in OptimizeBlock()
1437                && PrevBBIter->isDebugInstr() && MBBIter->isDebugInstr()) {  in OptimizeBlock()
1438           if (!MBBIter->isIdenticalTo(*PrevBBIter))  in OptimizeBlock()
1441           ++MBBIter; -- PrevBBIter;  in OptimizeBlock()
1445       PrevBB.splice(PrevBB.end(), MBB, MBB->begin(), MBB->end());  in OptimizeBlock()
1456       TII->removeBranch(PrevBB);  in OptimizeBlock()
1466       TII->removeBranch(PrevBB);  in OptimizeBlock()
1467       TII->insertBranch(PrevBB, PriorTBB, nullptr, PriorCond, dl);  in OptimizeBlock()
1475     // fall-through.  in OptimizeBlock()
1478       if (!TII->reverseBranchCondition(NewPriorCond)) {  in OptimizeBlock()
1480         TII->removeBranch(PrevBB);  in OptimizeBlock()
1481         TII->insertBranch(PrevBB, PriorFBB, nullptr, NewPriorCond, dl);  in OptimizeBlock()
1489     // a call to a no-return function like abort or __cxa_throw) and if the pred  in OptimizeBlock()
1496     if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&  in OptimizeBlock()
1498         !MBB->canFallThrough()) {  in OptimizeBlock()
1501       // We have to be careful that the succs of PredBB aren't both no-successor  in OptimizeBlock()
1506       if (FallThrough == --MF.end() &&  in OptimizeBlock()
1513         if (!TII->reverseBranchCondition(NewPriorCond)) {  in OptimizeBlock()
1518           TII->removeBranch(PrevBB);  in OptimizeBlock()
1519           TII->insertBranch(PrevBB, MBB, nullptr, NewPriorCond, dl);  in OptimizeBlock()
1522           MBB->moveAfter(&MF.back());  in OptimizeBlock()
1532     MachineInstr &TailCall = *MBB->getFirstNonDebugInstr();  in OptimizeBlock()
1533     if (TII->isUnconditionalTailCall(TailCall)) {  in OptimizeBlock()
1535       for (auto &Pred : MBB->predecessors()) {  in OptimizeBlock()
1539             !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);  in OptimizeBlock()
1547           if (TII->canMakeTailCallConditional(PredCond, TailCall)) {  in OptimizeBlock()
1551             TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);  in OptimizeBlock()
1557         // that we might have to re-arrange the CFG to fall through to the other  in OptimizeBlock()
1564           Pred->removeSuccessor(MBB);  in OptimizeBlock()
1572     // If this is a two-way branch, and the FBB branches to this block, reverse  in OptimizeBlock()
1573     // the condition so the single-basic-block loop is faster.  Instead of:  in OptimizeBlock()
1579       if (!TII->reverseBranchCondition(NewCond)) {  in OptimizeBlock()
1581         TII->removeBranch(*MBB);  in OptimizeBlock()
1582         TII->insertBranch(*MBB, CurFBB, CurTBB, NewCond, dl);  in OptimizeBlock()
1593         !MBB->hasAddressTaken() && !MBB->isEHPad()) {  in OptimizeBlock()
1596       // be 'non-branch terminators' in the block, try removing the branch and  in OptimizeBlock()
1598       TII->removeBranch(*MBB);  in OptimizeBlock()
1600       // as well, so this will behave the same as an empty block in non-debug  in OptimizeBlock()
1605         MBB->erase(MBB->begin(), MBB->end());  in OptimizeBlock()
1612       if (MBB->empty()) {  in OptimizeBlock()
1629             TII->removeBranch(PrevBB);  in OptimizeBlock()
1630             TII->insertBranch(PrevBB, PriorTBB, PriorFBB, PriorCond, pdl);  in OptimizeBlock()
1633           // Iterate through all the predecessors, revectoring each in-turn.  in OptimizeBlock()
1637           while(PI != MBB->pred_size()) {  in OptimizeBlock()
1638             MachineBasicBlock *PMBB = *(MBB->pred_begin() + PI);  in OptimizeBlock()
1645               PMBB->ReplaceUsesOfBlockWith(MBB, CurTBB);  in OptimizeBlock()
1648               // landing-pad.  in OptimizeBlock()
1649               for (auto SI = MBB->succ_begin(), SE = MBB->succ_end(); SI != SE;  in OptimizeBlock()  local
1651                 if (*SI != CurTBB && !CurTBB->isSuccessor(*SI)) {  in OptimizeBlock()
1652                   assert((*SI)->isEHPad() && "Bad CFG");  in OptimizeBlock()
1653                   CurTBB->copySuccessor(MBB, SI);  in OptimizeBlock()
1660               bool NewCurUnAnalyzable = TII->analyzeBranch(  in OptimizeBlock()
1664                 TII->removeBranch(*PMBB);  in OptimizeBlock()
1666                 TII->insertBranch(*PMBB, NewCurTBB, nullptr, NewCurCond, pdl);  in OptimizeBlock()
1675             MJTI->ReplaceMBBInJumpTables(MBB, CurTBB);  in OptimizeBlock()
1685       TII->insertBranch(*MBB, CurTBB, nullptr, CurCond, dl);  in OptimizeBlock()
1691   // place to move this block where a fall-through will happen.  in OptimizeBlock()
1693     // Now we know that there was no fall-through into this block, check to  in OptimizeBlock()
1694     // see if it has a fall-through into its successor.  in OptimizeBlock()
1695     bool CurFallsThru = MBB->canFallThrough();  in OptimizeBlock()
1697     if (!MBB->isEHPad()) {  in OptimizeBlock()
1701       for (MachineBasicBlock *PredBB : MBB->predecessors()) {  in OptimizeBlock()
1705         if (PredBB != MBB && !PredBB->canFallThrough() &&  in OptimizeBlock()
1706             !TII->analyzeBranch(*PredBB, PredTBB, PredFBB, PredCond, true) &&  in OptimizeBlock()
1709             (!CurFallsThru || MBB->getNumber() >= PredBB->getNumber())) {  in OptimizeBlock()
1713           // the (current) next block.  To avoid a possible compile-time  in OptimizeBlock()
1721             MachineBasicBlock *NextBB = &*std::next(MBB->getIterator());  in OptimizeBlock()
1723             TII->insertBranch(*MBB, NextBB, nullptr, CurCond, DebugLoc());  in OptimizeBlock()
1725           MBB->moveAfter(PredBB);  in OptimizeBlock()
1733       // Check analyzable branch-successors to see if we can move this block  in OptimizeBlock()
1740           MachineFunction::iterator SuccPrev = --SuccBB->getIterator();  in OptimizeBlock()
1742           // If this block doesn't already fall-through to that successor, and  in OptimizeBlock()
1746               !SuccPrev->canFallThrough()) {  in OptimizeBlock()
1747             MBB->moveBefore(SuccBB);  in OptimizeBlock()
1755       // the block before this one would be a fall-through if this block were  in OptimizeBlock()
1767       // possible and not remove the "!FallThrough()->isEHPad" condition below.  in OptimizeBlock()
1771           !FallThrough->isEHPad() &&  in OptimizeBlock()
1772           !TII->analyzeBranch(PrevBB, PrevTBB, PrevFBB, PrevCond, true) &&  in OptimizeBlock()
1774         MBB->moveAfter(&MF.back());  in OptimizeBlock()
1784 //===----------------------------------------------------------------------===//
1786 //===----------------------------------------------------------------------===//
1796 /// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
1800   for (MachineBasicBlock *SuccBB : BB->successors())  in findFalseBlock()
1817 /// findHoistingInsertPosAndDeps - Find the location to move common instructions
1830   MachineBasicBlock::iterator Loc = MBB->getFirstTerminator();  in findHoistingInsertPosAndDeps()
1831   if (!TII->isUnpredicatedTerminator(*Loc))  in findHoistingInsertPosAndDeps()
1832     return MBB->end();  in findHoistingInsertPosAndDeps()
1834   for (const MachineOperand &MO : Loc->operands()) {  in findHoistingInsertPosAndDeps()
1846         return MBB->end();  in findHoistingInsertPosAndDeps()
1860   if (Loc == MBB->begin())  in findHoistingInsertPosAndDeps()
1865   MachineBasicBlock::iterator PI = prev_nodbg(Loc, MBB->begin());  in findHoistingInsertPosAndDeps()
1868   for (const MachineOperand &MO : PI->operands()) {  in findHoistingInsertPosAndDeps()
1888   // side-effects. And since it's potentially bad to separate flag setting  in findHoistingInsertPosAndDeps()
1894   if (!PI->isSafeToMove(nullptr, DontMoveAcrossStore) || TII->isPredicated(*PI))  in findHoistingInsertPosAndDeps()
1895     return MBB->end();  in findHoistingInsertPosAndDeps()
1899   for (const MachineOperand &MO : PI->operands()) {  in findHoistingInsertPosAndDeps()
1910           for (MCPhysReg SubReg : TRI->subregs(Reg))  in findHoistingInsertPosAndDeps()
1911             Uses.erase(SubReg); // Use sub-registers to be conservative  in findHoistingInsertPosAndDeps()
1924   if (TII->analyzeBranch(*MBB, TBB, FBB, Cond, true) || !TBB || Cond.empty())  in HoistCommonCodeInSuccs()
1934   if (TBB->pred_size() > 1 || FBB->pred_size() > 1)  in HoistCommonCodeInSuccs()
1943   if (Loc == MBB->end())  in HoistCommonCodeInSuccs()
1948   MachineBasicBlock::iterator TIB = TBB->begin();  in HoistCommonCodeInSuccs()
1949   MachineBasicBlock::iterator FIB = FBB->begin();  in HoistCommonCodeInSuccs()
1950   MachineBasicBlock::iterator TIE = TBB->end();  in HoistCommonCodeInSuccs()
1951   MachineBasicBlock::iterator FIE = FBB->end();  in HoistCommonCodeInSuccs()
1959     if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))  in HoistCommonCodeInSuccs()
1962     if (TII->isPredicated(*TIB))  in HoistCommonCodeInSuccs()
1967     for (MachineOperand &MO : TIB->operands()) {  in HoistCommonCodeInSuccs()
2018     if (!TIB->isSafeToMove(nullptr, DontMoveAcrossStore))  in HoistCommonCodeInSuccs()
2022     for (const MachineOperand &MO : TIB->all_uses()) {  in HoistCommonCodeInSuccs()
2040     for (const MachineOperand &MO : TIB->all_defs()) {  in HoistCommonCodeInSuccs()
2058   MBB->splice(Loc, TBB, TBB->begin(), TIB);  in HoistCommonCodeInSuccs()
2059   FBB->erase(FBB->begin(), FIB);  in HoistCommonCodeInSuccs()