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