Lines Matching +full:batch +full:- +full:reduce
1 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
80 #define DEBUG_TYPE "jump-threading"
87 BBDuplicateThreshold("jump-threading-threshold",
93 "jump-threading-implication-search-threshold",
99 "jump-threading-phi-threshold",
104 "jump-threading-across-loop-headers",
109 DefaultBBDupThreshold = (T == -1) ? BBDuplicateThreshold : unsigned(T);
148 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
166 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
171 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
172 if (PredBr && PredBr->isConditional())
175 auto *SinglePredBB = PredBB->getSinglePredecessor();
189 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
190 Value *PhiOpnd = PN->getIncomingValue(i);
193 if (!CI || !CI->getType()->isIntegerTy(1))
197 (CI->isOne() ? BranchProbability::getBranchProbability(
202 auto PredOutEdge = GetPredOutEdge(PN->getIncomingBlock(i), BB);
207 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
225 if (PredBr->getSuccessor(0) == PredOutEdge.second) {
257 getDomTreeUpdater()->flush();
260 assert(getDomTreeUpdater()->getDomTree().verify(
263 assert((!getDomTreeUpdater()->hasPostDomTree() ||
264 getDomTreeUpdater()->getPostDomTree().verify(
268 assert(getDomTreeUpdater()->getDomTree().verify(
271 assert((!getDomTreeUpdater()->hasPostDomTree() ||
272 getDomTreeUpdater()->getPostDomTree().verify(
298 F->getParent(), Intrinsic::experimental_guard);
299 HasGuards = GuardDecl && !GuardDecl->use_empty();
301 // Reduce the number of instructions duplicated when optimizing strictly for
305 else if (F->hasFnAttribute(Attribute::MinSize))
314 assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
315 DominatorTree &DT = DTU->getDomTree();
335 // for the entry is non-trivial.
336 if (&BB == &F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
346 LVI->eraseBlock(&BB);
355 if (BI && BI->isUnconditional()) {
356 BasicBlock *Succ = BI->getSuccessor(0);
358 // The terminator must be the only non-phi instruction in BB.
359 BB.getFirstNonPHIOrDbg(true)->isTerminator() &&
365 // BB's parent until a DTU->getDomTree() event.
366 LVI->eraseBlock(&BB);
395 assert(Cond->getType() == ToVal->getType());
396 // We can unconditionally replace all uses in non-local blocks (i.e. uses
399 if (Cond->getParent() == KnownAtEndOfBB)
402 // Replace any debug-info record users of Cond with ToVal.
416 if (Cond->use_empty() && !Cond->mayHaveSideEffects()) {
417 Cond->eraseFromParent();
423 /// Return the cost of duplicating a piece of this block from first non-phi
430 assert(StopAt->getParent() == BB && "Not an instruction from proper BB?");
453 if (BB->getTerminator() == StopAt) {
466 // terminator-based Size adjustment at the end.
480 if (I->getType()->isTokenTy() && I->isUsedOutsideOfBlock(BB))
486 if (CI->cannotDuplicate() || CI->isConvergent())
489 if (TTI->getInstructionCost(&*I, TargetTransformInfo::TCK_SizeAndLatency) ==
496 // Calls are more expensive. If they are non-intrinsic calls, we model them
497 // as having cost of 4. If they are a non-vector intrinsic, we model them
503 else if (!CI->getType()->isVectorTy())
508 return Size > Bonus ? Size - Bonus : 0;
511 /// findLoopHeaders - We do not want jump threading to turn proper loop
523 /// enough to track all of these properties and keep it up-to-date as the CFG
533 /// getKnownConstant - Helper method to determine if we can thread over a
547 return dyn_cast<BlockAddress>(Val->stripPointerCasts());
552 /// computeValueKnownInPredecessors - Given a basic block BB and a value V, see
562 const DataLayout &DL = BB->getDataLayout();
564 // This method walks up use-def chains recursively. Because of this, we could
565 // get into an infinite loop going around loops in the use-def chain. To
579 // If V is a non-instruction value, or an instruction in a different block,
582 if (!I || I->getParent() != BB) {
584 // Okay, if this is a live-in value, see if it has a known value at the any
590 Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI);
591 // If I is a non-local compare-with-constant instruction, use more-rich
599 PredCst = LVI->getPredicateOnEdge(Pred, Val, Cst, P, BB, CxtI);
609 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
610 Value *InVal = PN->getIncomingValue(i);
612 Result.emplace_back(KC, PN->getIncomingBlock(i));
614 Constant *CI = LVI->getConstantOnEdge(InVal,
615 PN->getIncomingBlock(i),
618 Result.emplace_back(KC, PN->getIncomingBlock(i));
627 Value *Source = CI->getOperand(0);
636 if (Constant *Folded = ConstantFoldCastOperand(CI->getOpcode(), Val.first,
637 CI->getType(), DL))
644 Value *Source = FI->getOperand(0);
656 if (I->getType()->getPrimitiveSizeInBits() == 1) {
660 // X | true -> true
661 // X & false -> false
677 InterestingVal = ConstantInt::getTrue(I->getContext());
679 InterestingVal = ConstantInt::getFalse(I->getContext());
684 // interesting value: x|undef -> true and x&undef -> false.
693 // re-add it.
702 if (I->getOpcode() == Instruction::Xor &&
703 isa<ConstantInt>(I->getOperand(1)) &&
704 cast<ConstantInt>(I->getOperand(1))->isOne()) {
705 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, Result,
721 if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
723 computeValueKnownInPredecessorsImpl(BO->getOperand(0), BB, LHSVals,
730 ConstantFoldBinaryOpOperands(BO->getOpcode(), V, CI, DL);
744 Type *CmpType = Cmp->getType();
745 Value *CmpLHS = Cmp->getOperand(0);
746 Value *CmpRHS = Cmp->getOperand(1);
747 CmpInst::Predicate Pred = Cmp->getPredicate();
755 if (PN && PN->getParent() == BB && !LoopHeaders.contains(BB)) {
756 const DataLayout &DL = PN->getDataLayout();
759 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
760 BasicBlock *PredBB = PN->getIncomingBlock(i);
763 LHS = PN->getIncomingValue(i);
764 RHS = CmpRHS->DoPHITranslation(BB, PredBB);
766 LHS = CmpLHS->DoPHITranslation(BB, PredBB);
767 RHS = PN->getIncomingValue(i);
776 if (LHSInst && LHSInst->getParent() == BB)
779 Res = LVI->getPredicateOnEdge(Pred, LHS, cast<Constant>(RHS), PredBB,
790 // If comparing a live-in value against a constant, see if we know the
791 // live-in value on any predecessors.
792 if (isa<Constant>(CmpRHS) && !CmpType->isVectorTy()) {
796 cast<Instruction>(CmpLHS)->getParent() != BB) {
800 Constant *Res = LVI->getPredicateOnEdge(Pred, CmpLHS, CmpConst, P, BB,
811 // x as a live-in.
820 cast<Instruction>(AddLHS)->getParent() != BB) {
825 ConstantRange CR = LVI->getConstantRangeOnEdge(
828 CR = CR.add(AddConst->getValue());
832 Pred, cast<ConstantInt>(CmpConst)->getValue());
853 computeValueKnownInPredecessorsImpl(I->getOperand(0), BB, LHSVals,
871 Constant *TrueVal = getKnownConstant(SI->getTrueValue(), Preference);
872 Constant *FalseVal = getKnownConstant(SI->getFalseValue(), Preference);
875 computeValueKnownInPredecessorsImpl(SI->getCondition(), BB, Conds,
884 KnownCond = CI->isOne();
903 assert(CxtI->getParent() == BB && "CxtI should be in BB");
904 Constant *CI = LVI->getConstant(V, CxtI);
913 /// GetBestDestForBranchOnUndef - If we determine that the specified block ends
917 /// fewest predecessors. This should reduce the in-degree of the others.
919 Instruction *BBTerm = BB->getTerminator();
921 BasicBlock *TestBB = BBTerm->getSuccessor(MinSucc);
924 for (unsigned i = 1, e = BBTerm->getNumSuccessors(); i != e; ++i) {
925 TestBB = BBTerm->getSuccessor(i);
937 if (!BB->hasAddressTaken()) return false;
942 BA->removeDeadConstantUsers();
943 return !BA->use_empty();
946 /// processBlock - If there are any predecessors whose control can be threaded
951 if (DTU->isBBPendingDeletion(BB) ||
952 (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
975 Instruction *Terminator = BB->getTerminator();
978 if (BI->isUnconditional()) return false;
979 Condition = BI->getCondition();
981 Condition = SI->getCondition();
984 if (IB->getNumSuccessors() == 0) return false;
985 Condition = IB->getAddress()->stripPointerCasts();
994 // Run constant folding to see if we can reduce the condition to a simple
998 ConstantFoldInstruction(I, BB->getDataLayout(), TLI);
1000 I->replaceAllUsesWith(SimpleVal);
1002 I->eraseFromParent();
1012 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1017 Instruction *BBTerm = BB->getTerminator();
1018 Updates.reserve(BBTerm->getNumSuccessors());
1019 for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
1021 BasicBlock *Succ = BBTerm->getSuccessor(i);
1022 Succ->removePredecessor(BB, true);
1026 LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1028 Instruction *NewBI = BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm->getIterator());
1029 NewBI->setDebugLoc(BBTerm->getDebugLoc());
1031 BBTerm->eraseFromParent();
1032 DTU->applyUpdatesPermissive(Updates);
1034 FI->eraseFromParent();
1042 LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
1043 << "' folding terminator: " << *BB->getTerminator()
1048 BPI->eraseBlock(BB);
1065 CondWithoutFreeze = FI->getOperand(0);
1071 if (Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1073 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1074 CondConst, BB->getTerminator(),
1089 // CondCmp depends on a known phi-select pattern.
1095 if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator()))
1106 if (isa<Constant>(CondCmp->getOperand(1)))
1107 SimplifyValue = CondCmp->getOperand(0);
1117 if (PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1126 // If this is an otherwise-unfoldable branch on a phi node or freeze(phi) in
1129 if (PN && PN->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1132 // If this is an otherwise-unfoldable branch on a XOR, see if we can simplify.
1133 if (CondInst->getOpcode() == Instruction::Xor &&
1134 CondInst->getParent() == BB && isa<BranchInst>(BB->getTerminator()))
1146 auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
1147 if (!BI || !BI->isConditional())
1150 Value *Cond = BI->getCondition();
1157 if (FICond && FICond->hasOneUse())
1158 Cond = FICond->getOperand(0);
1163 BasicBlock *CurrentPred = BB->getSinglePredecessor();
1166 auto &DL = BB->getDataLayout();
1169 auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
1170 if (!PBI || !PBI->isConditional())
1172 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1175 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1177 isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
1181 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1182 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1183 FICond->getOperand(0))
1188 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1189 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1190 RemoveSucc->removePredecessor(BB);
1191 BranchInst *UncondBI = BranchInst::Create(KeepSucc, BI->getIterator());
1192 UncondBI->setDebugLoc(BI->getDebugLoc());
1194 BI->eraseFromParent();
1196 FICond->eraseFromParent();
1198 DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
1200 BPI->eraseBlock(BB);
1204 CurrentPred = CurrentBB->getSinglePredecessor();
1213 if (OpInst->getParent() == BB)
1218 /// simplifyPartiallyRedundantLoad - If LoadI is an obviously partially
1224 if (!LoadI->isUnordered()) return false;
1228 BasicBlock *LoadBB = LoadI->getParent();
1229 if (LoadBB->getSinglePredecessor())
1235 if (LoadBB->isEHPad())
1238 Value *LoadedPtr = LoadI->getOperand(0);
1260 LVI->forgetValue(NLoadI);
1266 AvailableVal = PoisonValue::get(LoadI->getType());
1267 if (AvailableVal->getType() != LoadI->getType()) {
1269 AvailableVal, LoadI->getType(), "", LoadI->getIterator());
1270 cast<Instruction>(AvailableVal)->setDebugLoc(LoadI->getDebugLoc());
1272 LoadI->replaceAllUsesWith(AvailableVal);
1273 LoadI->eraseFromParent();
1280 if (BBIt != LoadBB->begin())
1285 AAMDNodes AATags = LoadI->getAAMetadata();
1302 BBIt = PredBB->end();
1307 assert(LoadI->isUnordered() &&
1309 // If this is a load on a phi pointer, phi-translate it and search
1311 Type *AccessTy = LoadI->getType();
1312 const auto &DL = LoadI->getDataLayout();
1313 MemoryLocation Loc(LoadedPtr->DoPHITranslation(LoadBB, PredBB),
1317 Loc, AccessTy, LoadI->isAtomic(), PredBB, BBIt, DefMaxInstsToScan,
1323 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
1325 SinglePredBB = SinglePredBB->getSinglePredecessor();
1327 BBIt = SinglePredBB->end();
1329 Loc, AccessTy, LoadI->isAtomic(), SinglePredBB, BBIt,
1330 (DefMaxInstsToScan - NumScanedInst), &BatchAA, &IsLoadCSE,
1369 for (auto I = LoadBB->begin(); &*I != LoadI; ++I)
1377 OneUnavailablePred->getTerminator()->getNumSuccessors() == 1) {
1391 if (isa<IndirectBrInst>(P->getTerminator()))
1399 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit, "thread-pre-split");
1406 assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
1409 LoadI->getType(), LoadedPtr->DoPHITranslation(LoadBB, UnavailablePred),
1410 LoadI->getName() + ".pr", false, LoadI->getAlign(),
1411 LoadI->getOrdering(), LoadI->getSyncScopeID(),
1412 UnavailablePred->getTerminator()->getIterator());
1413 NewVal->setDebugLoc(LoadI->getDebugLoc());
1415 NewVal->setAAMetadata(AATags);
1425 PHINode *PN = PHINode::Create(LoadI->getType(), pred_size(LoadBB), "");
1426 PN->insertBefore(LoadBB->begin());
1427 PN->takeName(LoadI);
1428 PN->setDebugLoc(LoadI->getDebugLoc());
1436 assert(I != AvailablePreds.end() && I->first == P &&
1443 Value *&PredV = I->second;
1444 if (PredV->getType() != LoadI->getType())
1446 PredV, LoadI->getType(), "", P->getTerminator()->getIterator());
1448 PN->addIncoming(PredV, I->first);
1453 LVI->forgetValue(PredLoadI);
1456 LoadI->replaceAllUsesWith(PN);
1457 LoadI->eraseFromParent();
1462 /// findMostPopularDest - The specified list contains multiple possible
1493 return MostPopular->first;
1497 // BB->getSinglePredecessor() and then on to BB.
1502 BasicBlock *PredBB = BB->getSinglePredecessor();
1511 if (!I || (I->getParent() != BB && I->getParent() != PredBB)) {
1512 return LVI->getConstantOnEdge(V, PredPredBB, PredBB, nullptr);
1517 if (PHI->getParent() == PredBB)
1518 return dyn_cast<Constant>(PHI->getIncomingValueForBlock(PredPredBB));
1524 if (CondCmp->getParent() == BB) {
1526 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(0), DL);
1528 evaluateOnPredecessorEdge(BB, PredPredBB, CondCmp->getOperand(1), DL);
1530 return ConstantFoldCompareInstOperands(CondCmp->getPredicate(), Op0,
1561 dbgs() << " BB '" << BB->getName()
1563 << " for pred '" << PredValue.second->getName() << "'.\n";
1588 else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
1590 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->isZero());
1591 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
1593 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1595 assert(isa<IndirectBrInst>(BB->getTerminator())
1598 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1616 if (isa<IndirectBrInst>(Pred->getTerminator()))
1630 if (BB->hasNPredecessors(PredToDestList.size())) {
1633 Updates.reserve(BB->getTerminator()->getNumSuccessors() - 1);
1638 SuccBB->removePredecessor(BB, true); // This is unreachable successor.
1644 Instruction *Term = BB->getTerminator();
1645 Instruction *NewBI = BranchInst::Create(OnlyDest, Term->getIterator());
1646 NewBI->setDebugLoc(Term->getDebugLoc());
1648 Term->eraseFromParent();
1649 DTU->applyUpdatesPermissive(Updates);
1651 BPI->eraseBlock(BB);
1656 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1657 CondInst->eraseFromParent();
1673 // this block is a switch, we want to start by threading the batch that goes
1711 MostPopularDest = BB->getTerminator()->
1718 /// processBranchOnPHI - We have an otherwise unthreadable conditional branch on
1722 BasicBlock *BB = PN->getParent();
1736 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1737 BasicBlock *PredBB = PN->getIncomingBlock(i);
1738 if (BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator()))
1739 if (PredBr->isUnconditional()) {
1750 /// processBranchOnXOR - We have an otherwise unthreadable conditional branch on
1754 BasicBlock *BB = BO->getParent();
1758 if (isa<ConstantInt>(BO->getOperand(0)) ||
1759 isa<ConstantInt>(BO->getOperand(1)))
1764 if (!isa<PHINode>(BB->front()))
1768 if (BB->isEHPad())
1791 if (!computeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues,
1794 if (!computeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues,
1810 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1819 SplitVal = ConstantInt::getTrue(BB->getContext());
1821 SplitVal = ConstantInt::getFalse(BB->getContext());
1836 cast<PHINode>(BB->front()).getNumIncomingValues()) {
1839 BO->replaceAllUsesWith(UndefValue::get(BO->getType()));
1840 BO->eraseFromParent();
1841 } else if (SplitVal->isZero() && BO != BO->getOperand(isLHS)) {
1843 BO->replaceAllUsesWith(BO->getOperand(isLHS));
1844 BO->eraseFromParent();
1847 BO->setOperand(!isLHS, SplitVal);
1856 return isa<IndirectBrInst>(Pred->getTerminator());
1864 /// addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new
1871 for (PHINode &PN : PHIBB->phis()) {
1880 IV = I->second;
1889 BasicBlock *SinglePred = BB->getSinglePredecessor();
1893 const Instruction *TI = SinglePred->getTerminator();
1894 if (TI->isSpecialTerminator() || TI->getNumSuccessors() != 1 ||
1902 LVI->eraseBlock(SinglePred);
1926 // %x = use of %p <-- LVI info2 is correct from here onwards.
1933 LVI->eraseBlock(BB);
1956 if (UserPN->getIncomingBlock(U) == BB)
1958 } else if (User->getParent() == BB)
1967 return DbgVal->getParent() == BB;
1970 return DbgVarRec->getParent() == BB;
1976 LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
2012 auto RetargetDbgValueIfPossible = [&](Instruction *NewInst) -> bool {
2018 for (auto DbgOperand : DbgInstruction->location_ops()) {
2026 std::pair<Value *, Value *>(DbgOperand, I->second));
2031 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2039 for (auto *Op : DVR->location_ops()) {
2046 OperandsToRemap.insert({OpInst, I->second});
2050 DVR->replaceVariableLocationOp(OldOp, MappedOp);
2053 BasicBlock *RangeBB = BI->getParent();
2059 PHINode *NewPN = PHINode::Create(PN->getType(), 1, PN->getName(), NewBB);
2060 NewPN->addIncoming(PN->getIncomingValueForBlock(PredBB), PredBB);
2069 LLVMContext &Context = PredBB->getContext();
2074 auto DVRRange = NewInst->cloneDebugInfoFrom(From);
2079 // Clone the non-phi instructions of the source basic block into NewBB,
2083 Instruction *New = BI->clone();
2084 New->setName(BI->getName());
2085 New->insertInto(NewBB, NewBB->end());
2094 // Remap operands to patch up intra-block references.
2095 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2096 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2099 New->setOperand(i, I->second);
2105 if (BE != RangeBB->end() && BE->hasDbgRecords()) {
2107 DbgMarker *Marker = RangeBB->getMarker(BE);
2108 DbgMarker *EndMarker = NewBB->createMarker(NewBB->end());
2109 auto DVRRange = EndMarker->cloneDebugInfoFrom(Marker, std::nullopt);
2132 // PredBB. Then we can thread edges PredBB1->BB and PredBB2->BB through BB.
2135 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2140 BasicBlock *PredBB = BB->getSinglePredecessor();
2147 BranchInst *PredBBBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2148 if (!PredBBBranch || PredBBBranch->isUnconditional())
2153 if (PredBB->getSinglePredecessor())
2173 if (PredBB->isEHPad())
2183 const DataLayout &DL = BB->getDataLayout();
2186 if (isa<IndirectBrInst>(P->getTerminator()))
2190 if (CI->isZero()) {
2193 } else if (CI->isOne()) {
2210 BasicBlock *SuccBB = CondBr->getSuccessor(PredPredBB == ZeroPred);
2214 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2215 << "' - would thread to self!\n");
2227 << BB->getName() << "' to dest "
2229 << SuccBB->getName()
2230 << "' - it might create an irreducible loop!\n";
2237 TTI, BB, BB->getTerminator(), BBDupThreshold);
2239 TTI, PredBB, PredBB->getTerminator(), BBDupThreshold);
2246 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2247 << "' - Cost is too high: " << PredBBCost
2261 LLVM_DEBUG(dbgs() << " Threading through '" << PredBB->getName() << "' and '"
2262 << BB->getName() << "'\n");
2269 BranchInst *CondBr = cast<BranchInst>(BB->getTerminator());
2270 BranchInst *PredBBBranch = cast<BranchInst>(PredBB->getTerminator());
2273 BasicBlock::Create(PredBB->getContext(), PredBB->getName() + ".thread",
2274 PredBB->getParent(), PredBB);
2275 NewBB->moveAfter(PredBB);
2280 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2281 BPI->getEdgeProbability(PredPredBB, PredBB);
2282 BFI->setBlockFreq(NewBB, NewBBFreq);
2289 cloneInstructions(ValueMapping, PredBB->begin(), PredBB->end(), NewBB,
2294 BPI->copyEdgeProbabilities(PredBB, NewBB);
2299 Instruction *PredPredTerm = PredPredBB->getTerminator();
2300 for (unsigned i = 0, e = PredPredTerm->getNumSuccessors(); i != e; ++i)
2301 if (PredPredTerm->getSuccessor(i) == PredBB) {
2302 PredBB->removePredecessor(PredPredBB, true);
2303 PredPredTerm->setSuccessor(i, NewBB);
2306 addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(0), PredBB, NewBB,
2308 addPHINodeEntriesForMappedBlock(PredBBBranch->getSuccessor(1), PredBB, NewBB,
2311 DTU->applyUpdatesPermissive(
2312 {{DominatorTree::Insert, NewBB, CondBr->getSuccessor(0)},
2313 {DominatorTree::Insert, NewBB, CondBr->getSuccessor(1)},
2329 /// tryThreadEdge - Thread an edge if it's safe and profitable to do so.
2335 LLVM_DEBUG(dbgs() << " Not threading across BB '" << BB->getName()
2336 << "' - would thread to self!\n");
2347 << (BBIsHeader ? "loop header BB '" : "block BB '") << BB->getName()
2349 << SuccBB->getName() << "' - it might create an irreducible loop!\n";
2355 TTI, BB, BB->getTerminator(), BBDupThreshold);
2357 LLVM_DEBUG(dbgs() << " Not threading BB '" << BB->getName()
2358 << "' - Cost is too high: " << JumpThreadCost << "\n");
2366 /// threadEdge - We have decided that it is safe and profitable to factor the
2393 LLVM_DEBUG(dbgs() << " Threading edge from '" << PredBB->getName()
2394 << "' to '" << SuccBB->getName()
2397 LVI->threadEdge(PredBB, BB, SuccBB);
2399 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(),
2400 BB->getName()+".thread",
2401 BB->getParent(), BB);
2402 NewBB->moveAfter(PredBB);
2408 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2409 BFI->setBlockFreq(NewBB, NewBBFreq);
2414 cloneInstructions(ValueMapping, BB->begin(), std::prev(BB->end()), NewBB,
2420 NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
2429 Instruction *PredTerm = PredBB->getTerminator();
2430 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
2431 if (PredTerm->getSuccessor(i) == BB) {
2432 BB->removePredecessor(PredBB, true);
2433 PredTerm->setSuccessor(i, NewBB);
2437 DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
2471 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2476 if (BB->isLandingPad()) {
2477 std::string NewName = std::string(Suffix) + ".split-lp";
2491 if (BFI) // Update frequencies between Pred -> NewBB.
2495 BFI->setBlockFreq(NewBB, NewBBFreq);
2498 DTU->applyUpdatesPermissive(Updates);
2503 const Instruction *TI = BB->getTerminator();
2504 if (!TI || TI->getNumSuccessors() < 2)
2511 /// edge BB->SuccBB. This is done by scaling the weight of BB->SuccBB by 1 -
2512 /// Freq(PredBB->BB) / Freq(BB->SuccBB).
2531 auto BBOrigFreq = BFI->getBlockFreq(BB);
2532 auto NewBBFreq = BFI->getBlockFreq(NewBB);
2533 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(BB, SuccBB);
2534 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2535 BFI->setBlockFreq(BB, BBNewFreq);
2542 ? BB2SuccBBFreq - NewBBFreq
2543 : BBOrigFreq * BPI->getEdgeProbability(BB, Succ);
2563 BPI->setEdgeProbability(BB, BBSuccProbs);
2591 // As a consequence if we thread eq_1 -> check_2 to check_3, check_2->check_3
2604 auto TI = BB->getTerminator();
2609 /// duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch
2622 LLVM_DEBUG(dbgs() << " Not duplicating loop header '" << BB->getName()
2623 << "' into predecessor block '" << PredBBs[0]->getName()
2624 << "' - it might create an irreducible loop!\n");
2629 TTI, BB, BB->getTerminator(), BBDupThreshold);
2631 LLVM_DEBUG(dbgs() << " Not duplicating BB '" << BB->getName()
2632 << "' - Cost is too high: " << DuplicationCost << "\n");
2650 LLVM_DEBUG(dbgs() << " Duplicating block '" << BB->getName()
2651 << "' into end of '" << PredBB->getName()
2657 BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
2659 if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
2665 OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
2672 BasicBlock::iterator BI = BB->begin();
2674 ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
2675 // Clone the non-phi instructions of BB into PredBB, keeping track of the
2677 for (; BI != BB->end(); ++BI) {
2678 Instruction *New = BI->clone();
2679 New->insertInto(PredBB, OldPredBranch->getIterator());
2681 // Remap operands to patch up intra-block references.
2682 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2683 if (Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2686 New->setOperand(i, I->second);
2697 {BB->getDataLayout(), TLI, nullptr, nullptr, New})) {
2699 if (!New->mayHaveSideEffects()) {
2700 New->eraseFromParent();
2702 // Clone debug-info on the elided instruction to the destination
2704 OldPredBranch->cloneDebugInfoFrom(&*BI, std::nullopt, true);
2711 New->setName(BI->getName());
2712 // Clone across any debug-info attached to the old instruction.
2713 New->cloneDebugInfoFrom(&*BI);
2715 for (unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2716 if (BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2723 BranchInst *BBBranch = cast<BranchInst>(BB->getTerminator());
2724 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(0), BB, PredBB,
2726 addPHINodeEntriesForMappedBlock(BBBranch->getSuccessor(1), BB, PredBB,
2733 BB->removePredecessor(PredBB, true);
2736 OldPredBranch->eraseFromParent();
2738 BPI->copyEdgeProbabilities(BB, PredBB);
2739 DTU->applyUpdatesPermissive(Updates);
2755 // Pred --
2759 // |-----
2762 BranchInst *PredTerm = cast<BranchInst>(Pred->getTerminator());
2763 BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
2764 BB->getParent(), BB);
2766 PredTerm->removeFromParent();
2767 PredTerm->insertInto(NewBB, NewBB->end());
2769 auto *BI = BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
2770 BI->applyMergedLocation(PredTerm->getDebugLoc(), SI->getDebugLoc());
2771 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2772 SIUse->setIncomingValue(Idx, SI->getFalseValue());
2773 SIUse->addIncoming(SI->getTrueValue(), NewBB);
2787 BPI->setEdgeProbability(Pred, BP);
2797 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2798 BFI->setBlockFreq(NewBB, NewBBFreq);
2802 SI->eraseFromParent();
2803 DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
2807 for (BasicBlock::iterator BI = BB->begin();
2810 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2814 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2816 if (!CondPHI || CondPHI->getParent() != BB)
2819 for (unsigned I = 0, E = CondPHI->getNumIncomingValues(); I != E; ++I) {
2820 BasicBlock *Pred = CondPHI->getIncomingBlock(I);
2821 SelectInst *PredSI = dyn_cast<SelectInst>(CondPHI->getIncomingValue(I));
2826 if (!PredSI || PredSI->getParent() != Pred || !PredSI->hasOneUse())
2829 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2830 if (!PredTerm || !PredTerm->isUnconditional())
2839 /// tryToUnfoldSelect - Look for blocks of the form
2852 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
2853 PHINode *CondLHS = dyn_cast<PHINode>(CondCmp->getOperand(0));
2854 Constant *CondRHS = cast<Constant>(CondCmp->getOperand(1));
2856 if (!CondBr || !CondBr->isConditional() || !CondLHS ||
2857 CondLHS->getParent() != BB)
2860 for (unsigned I = 0, E = CondLHS->getNumIncomingValues(); I != E; ++I) {
2861 BasicBlock *Pred = CondLHS->getIncomingBlock(I);
2862 SelectInst *SI = dyn_cast<SelectInst>(CondLHS->getIncomingValue(I));
2866 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2869 BranchInst *PredTerm = dyn_cast<BranchInst>(Pred->getTerminator());
2870 if (!PredTerm || !PredTerm->isUnconditional())
2877 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1),
2880 LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2),
2890 /// tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the
2904 /// jump-threading over bb in this pass.
2908 /// select is not jump-threaded, it will be folded again in the later
2911 // This transform would reduce the quality of msan diagnostics.
2913 if (BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
2921 for (BasicBlock::iterator BI = BB->begin();
2924 if (llvm::all_of(PN->incoming_values(),
2932 if (SI->getParent() != BB)
2934 Value *Cond = SI->getCondition();
2936 return Cond && Cond == V && Cond->getType()->isIntegerTy(1) && !IsAndOr;
2940 for (Use &U : PN->uses()) {
2944 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2945 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2946 if (SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2947 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2963 Value *Cond = SI->getCondition();
2965 Cond = new FreezeInst(Cond, "cond.fr", SI->getIterator());
2969 BasicBlock *SplitBB = SI->getParent();
2970 BasicBlock *NewBB = Term->getParent();
2971 PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI->getIterator());
2972 NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
2973 NewPN->addIncoming(SI->getFalseValue(), BB);
2974 NewPN->setDebugLoc(SI->getDebugLoc());
2975 SI->replaceAllUsesWith(NewPN);
2976 SI->eraseFromParent();
2979 Updates.reserve((2 * SplitBB->getTerminator()->getNumSuccessors()) + 3);
2988 DTU->applyUpdatesPermissive(Updates);
3032 auto *Parent = Pred1->getSinglePredecessor();
3033 if (!Parent || Parent != Pred2->getSinglePredecessor())
3036 if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3049 assert(BI->getNumSuccessors() == 2 && "Wrong number of successors?");
3050 assert(BI->isConditional() && "Unconditional branch has 2 successors?");
3051 Value *GuardCond = Guard->getArgOperand(0);
3052 Value *BranchCond = BI->getCondition();
3053 BasicBlock *TrueDest = BI->getSuccessor(0);
3054 BasicBlock *FalseDest = BI->getSuccessor(1);
3056 auto &DL = BB->getDataLayout();
3078 Instruction *AfterGuard = Guard->getNextNode();
3095 << GuardedBlock->getName() << "\n");
3100 for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
3104 BasicBlock::iterator InsertionPoint = BB->getFirstInsertionPt();
3105 assert(InsertionPoint != BB->end() && "Empty block?");
3108 if (!Inst->use_empty()) {
3109 PHINode *NewPN = PHINode::Create(Inst->getType(), 2);
3110 NewPN->addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3111 NewPN->addIncoming(GuardedMapping[Inst], GuardedBlock);
3112 NewPN->setDebugLoc(Inst->getDebugLoc());
3113 NewPN->insertBefore(InsertionPoint);
3114 Inst->replaceAllUsesWith(NewPN);
3116 Inst->dropDbgRecords();
3117 Inst->eraseFromParent();
3140 assert(!DTU->hasPendingUpdates() &&
3143 return &FAM->getResult<AnalysisT>(*F);
3153 FAM->invalidate(*F, PA);
3155 DTU->flush();
3157 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3158 assert((!DTU->hasPostDomTree() ||
3159 DTU->getPostDomTree().verify(
3162 auto *Result = &FAM->getResult<AnalysisT>(*F);
3164 TTI = &FAM->getResult<TargetIRAnalysis>(*F);
3165 TLI = &FAM->getResult<TargetLibraryAnalysis>(*F);
3166 AA = &FAM->getResult<AAManager>(*F);
3174 BPI = FAM->getCachedResult<BranchProbabilityAnalysis>(*F);
3182 BFI = FAM->getCachedResult<BlockFrequencyAnalysis>(*F);