80using namespace jumpthreading;
82#define DEBUG_TYPE "jump-threading"
86STATISTIC(NumDupes,
"Number of branch blocks duplicated to eliminate phi");
90 cl::desc(
"Max block size to duplicate for jump threading"),
95 "jump-threading-implication-search-threshold",
96 cl::desc(
"The number of predecessors to search for a stronger "
97 "condition to use to thread over a weaker condition"),
101 "jump-threading-phi-threshold",
106 "jump-threading-across-loop-headers",
107 cl::desc(
"Allow JumpThreading to thread across loop headers, for testing"),
158 if (TrueWeight + FalseWeight == 0)
166 auto GetPredOutEdge =
168 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
169 auto *PredBB = IncomingBB;
170 auto *SuccBB = PhiBB;
173 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
175 return {PredBB, SuccBB};
177 auto *SinglePredBB = PredBB->getSinglePredecessor();
179 return {
nullptr,
nullptr};
183 if (Visited.
count(SinglePredBB))
184 return {
nullptr,
nullptr};
187 PredBB = SinglePredBB;
200 TrueWeight, TrueWeight + FalseWeight)
202 FalseWeight, TrueWeight + FalseWeight));
205 if (!PredOutEdge.first)
213 uint64_t PredTrueWeight, PredFalseWeight;
251 std::make_unique<DomTreeUpdater>(
253 std::nullopt, std::nullopt);
261#if defined(EXPENSIVE_CHECKS)
263 DominatorTree::VerificationLevel::Full) &&
264 "DT broken after JumpThreading");
268 "PDT broken after JumpThreading");
271 DominatorTree::VerificationLevel::Fast) &&
272 "DT broken after JumpThreading");
276 "PDT broken after JumpThreading");
279 return getPreservedAnalysis();
286 std::unique_ptr<DomTreeUpdater> DTU_,
287 std::optional<BlockFrequencyInfo *> BFI_,
288 std::optional<BranchProbabilityInfo *> BPI_) {
296 DTU = std::move(DTU_);
301 HasGuards = GuardDecl && !GuardDecl->use_empty();
310 BBDupThreshold = DefaultBBDupThreshold;
315 assert(DTU &&
"DTU isn't passed into JumpThreading before using it.");
316 assert(DTU->hasDomTree() &&
"JumpThreading relies on DomTree to proceed.");
325 bool EverChanged =
false;
329 for (
auto &BB : *
F) {
330 if (Unreachable.
count(&BB))
333 Changed = ChangedSinceLastAnalysisUpdate =
true;
343 if (&BB == &
F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
350 <<
"' with terminator: " << *BB.getTerminator()
352 LoopHeaders.erase(&BB);
355 Changed = ChangedSinceLastAnalysisUpdate =
true;
361 auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
362 if (BI && BI->isUnconditional()) {
366 BB.getFirstNonPHIOrDbg(
true)->isTerminator() &&
369 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
375 Changed = ChangedSinceLastAnalysisUpdate =
true;
379 EverChanged |= Changed;
395 bool Changed =
false;
400 if (
Cond->getParent() == KnownAtEndOfBB)
405 DVR.replaceVariableLocationOp(
Cond, ToVal,
true);
415 Changed |=
I.replaceUsesOfWith(
Cond, ToVal);
417 if (
Cond->use_empty() && !
Cond->mayHaveSideEffects()) {
418 Cond->eraseFromParent();
430 unsigned Threshold) {
431 assert(StopAt->
getParent() == BB &&
"Not an instruction from proper BB?");
436 unsigned PhiCount = 0;
439 if (!isa<PHINode>(&
I)) {
458 if (isa<SwitchInst>(StopAt))
462 if (isa<IndirectBrInst>(StopAt))
473 for (; &*
I != StopAt; ++
I) {
476 if (
Size > Threshold)
481 if (
I->getType()->isTokenTy() &&
I->isUsedOutsideOfBlock(BB))
486 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
487 if (CI->cannotDuplicate() || CI->isConvergent())
501 if (
const CallInst *CI = dyn_cast<CallInst>(
I)) {
502 if (!isa<IntrinsicInst>(CI))
504 else if (!CI->getType()->isVectorTy())
530 for (
const auto &Edge : Edges)
531 LoopHeaders.insert(Edge.second);
544 if (
UndefValue *U = dyn_cast<UndefValue>(Val))
550 return dyn_cast<ConstantInt>(Val);
569 if (!RecursionSet.
insert(V).second)
575 Result.emplace_back(KC, Pred);
577 return !Result.empty();
583 if (!
I ||
I->getParent() != BB) {
588 using namespace PatternMatch;
605 Result.emplace_back(KC,
P);
608 return !Result.empty();
612 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
613 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
614 Value *InVal = PN->getIncomingValue(i);
616 Result.emplace_back(KC, PN->getIncomingBlock(i));
619 PN->getIncomingBlock(i),
622 Result.emplace_back(KC, PN->getIncomingBlock(i));
626 return !Result.empty();
630 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
631 Value *Source = CI->getOperand(0);
639 for (
auto &Val : Vals)
642 Result.emplace_back(Folded, Val.second);
644 return !Result.empty();
648 Value *Source = FI->getOperand(0);
656 return !Result.empty();
660 if (
I->getType()->getPrimitiveSizeInBits() == 1) {
661 using namespace PatternMatch;
689 for (
const auto &LHSVal : LHSVals)
690 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
691 Result.emplace_back(InterestingVal, LHSVal.second);
692 LHSKnownBBs.
insert(LHSVal.second);
694 for (
const auto &RHSVal : RHSVals)
695 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
698 if (!LHSKnownBBs.
count(RHSVal.second))
699 Result.emplace_back(InterestingVal, RHSVal.second);
702 return !Result.empty();
706 if (
I->getOpcode() == Instruction::Xor &&
707 isa<ConstantInt>(
I->getOperand(1)) &&
708 cast<ConstantInt>(
I->getOperand(1))->isOne()) {
715 for (
auto &R : Result)
725 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
731 for (
const auto &LHSVal : LHSVals) {
737 Result.emplace_back(KC, LHSVal.second);
741 return !Result.empty();
745 if (
CmpInst *Cmp = dyn_cast<CmpInst>(
I)) {
748 Type *CmpType = Cmp->getType();
749 Value *CmpLHS = Cmp->getOperand(0);
750 Value *CmpRHS = Cmp->getOperand(1);
753 PHINode *PN = dyn_cast<PHINode>(CmpLHS);
755 PN = dyn_cast<PHINode>(CmpRHS);
759 if (PN && PN->
getParent() == BB && !LoopHeaders.contains(BB)) {
775 if (!isa<Constant>(
RHS))
779 auto LHSInst = dyn_cast<Instruction>(
LHS);
780 if (LHSInst && LHSInst->getParent() == BB)
785 cast<Constant>(
RHS), PredBB, BB,
793 Result.emplace_back(KC, PredBB);
796 return !Result.empty();
801 if (isa<Constant>(CmpRHS) && !CmpType->
isVectorTy()) {
802 Constant *CmpConst = cast<Constant>(CmpRHS);
804 if (!isa<Instruction>(CmpLHS) ||
805 cast<Instruction>(CmpLHS)->
getParent() != BB) {
811 CmpConst,
P, BB, CxtI ? CxtI : Cmp);
815 Constant *ResC = ConstantInt::get(CmpType, Res);
816 Result.emplace_back(ResC,
P);
819 return !Result.empty();
826 using namespace PatternMatch;
830 if (isa<ConstantInt>(CmpConst) &&
832 if (!isa<Instruction>(AddLHS) ||
833 cast<Instruction>(AddLHS)->
getParent() != BB) {
839 AddLHS,
P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
845 Pred, cast<ConstantInt>(CmpConst)->getValue());
855 Result.emplace_back(ResC,
P);
858 return !Result.empty();
869 for (
const auto &LHSVal : LHSVals) {
874 Result.emplace_back(KC, LHSVal.second);
877 return !Result.empty();
887 if ((TrueVal || FalseVal) &&
890 for (
auto &
C : Conds) {
897 KnownCond = CI->isOne();
899 assert(isa<UndefValue>(
Cond) &&
"Unexpected condition value");
903 KnownCond = (TrueVal !=
nullptr);
907 if (
Constant *Val = KnownCond ? TrueVal : FalseVal)
908 Result.emplace_back(Val,
C.second);
911 return !Result.empty();
920 Result.emplace_back(KC, Pred);
923 return !Result.empty();
933 unsigned MinSucc = 0;
936 unsigned MinNumPreds =
pred_size(TestBB);
940 if (NumPreds < MinNumPreds) {
942 MinNumPreds = NumPreds;
964 if (DTU->isBBPendingDeletion(BB) ||
989 if (
BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
991 if (BI->isUnconditional())
return false;
992 Condition = BI->getCondition();
993 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
994 Condition = SI->getCondition();
995 }
else if (
IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
997 if (IB->getNumSuccessors() == 0)
return false;
998 Condition = IB->getAddress()->stripPointerCasts();
1005 bool ConstantFolded =
false;
1009 if (
Instruction *
I = dyn_cast<Instruction>(Condition)) {
1013 I->replaceAllUsesWith(SimpleVal);
1015 I->eraseFromParent();
1016 Condition = SimpleVal;
1017 ConstantFolded =
true;
1023 auto *FI = dyn_cast<FreezeInst>(Condition);
1024 if (isa<UndefValue>(Condition) ||
1025 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1027 std::vector<DominatorTree::UpdateType> Updates;
1033 if (i == BestSucc)
continue;
1040 <<
"' folding undef terminator: " << *BBTerm <<
'\n');
1044 DTU->applyUpdatesPermissive(Updates);
1046 FI->eraseFromParent();
1059 if (
auto *BPI = getBPI())
1060 BPI->eraseBlock(BB);
1064 Instruction *CondInst = dyn_cast<Instruction>(Condition);
1071 return ConstantFolded;
1075 Value *CondWithoutFreeze = CondInst;
1076 if (
auto *FI = dyn_cast<FreezeInst>(CondInst))
1077 CondWithoutFreeze = FI->getOperand(0);
1079 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(CondWithoutFreeze)) {
1083 if (
Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1085 LVI->
getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1118 Value *SimplifyValue = CondWithoutFreeze;
1120 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1121 if (isa<Constant>(CondCmp->getOperand(1)))
1122 SimplifyValue = CondCmp->getOperand(0);
1126 if (
LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1131 if (
PHINode *PN = dyn_cast<PHINode>(CondInst))
1132 if (PN->getParent() == BB && isa<BranchInst>(BB->
getTerminator()))
1143 PHINode *PN = dyn_cast<PHINode>(CondWithoutFreeze);
1148 if (CondInst->
getOpcode() == Instruction::Xor &&
1162 if (!BI || !BI->isConditional())
1171 auto *FICond = dyn_cast<FreezeInst>(
Cond);
1172 if (FICond && FICond->hasOneUse())
1173 Cond = FICond->getOperand(0);
1184 auto *PBI = dyn_cast<BranchInst>(CurrentPred->
getTerminator());
1185 if (!PBI || !PBI->isConditional())
1187 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1190 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1191 std::optional<bool> Implication =
1196 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1197 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1198 FICond->getOperand(0))
1199 Implication = CondIsTrue;
1203 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1204 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1209 BI->eraseFromParent();
1211 FICond->eraseFromParent();
1214 if (
auto *BPI = getBPI())
1215 BPI->eraseBlock(BB);
1218 CurrentBB = CurrentPred;
1228 if (OpInst->getParent() == BB)
1273 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1280 if (AvailableVal == LoadI)
1282 if (AvailableVal->getType() != LoadI->
getType()) {
1285 cast<Instruction>(AvailableVal)->setDebugLoc(LoadI->
getDebugLoc());
1295 if (BBIt != LoadBB->
begin())
1306 AvailablePredsTy AvailablePreds;
1314 if (!PredsScanned.
insert(PredBB).second)
1317 BBIt = PredBB->
end();
1318 unsigned NumScanedInst = 0;
1319 Value *PredAvailable =
nullptr;
1323 "Attempting to CSE volatile or atomic loads");
1333 &BatchAA, &IsLoadCSE, &NumScanedInst);
1338 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->
begin() &&
1342 BBIt = SinglePredBB->
end();
1344 Loc, AccessTy, LoadI->
isAtomic(), SinglePredBB, BBIt,
1350 if (!PredAvailable) {
1351 OneUnavailablePred = PredBB;
1356 CSELoads.
push_back(cast<LoadInst>(PredAvailable));
1360 AvailablePreds.emplace_back(PredBB, PredAvailable);
1365 if (AvailablePreds.empty())
return false;
1382 if (PredsScanned.
size() != AvailablePreds.size() &&
1384 for (
auto I = LoadBB->
begin(); &*
I != LoadI; ++
I)
1391 if (PredsScanned.
size() == AvailablePreds.size()+1 &&
1393 UnavailablePred = OneUnavailablePred;
1394 }
else if (PredsScanned.
size() != AvailablePreds.size()) {
1400 for (
const auto &AvailablePred : AvailablePreds)
1401 AvailablePredSet.
insert(AvailablePred.first);
1406 if (isa<IndirectBrInst>(
P->getTerminator()))
1409 if (!AvailablePredSet.
count(
P))
1414 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit,
"thread-pre-split");
1420 if (UnavailablePred) {
1422 "Can't handle critical edge here!");
1432 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1448 AvailablePredsTy::iterator
I =
1451 assert(
I != AvailablePreds.end() &&
I->first ==
P &&
1452 "Didn't find entry for predecessor!");
1458 Value *&PredV =
I->second;
1461 PredV, LoadI->
getType(),
"",
P->getTerminator()->getIterator());
1466 for (
LoadInst *PredLoadI : CSELoads) {
1484 assert(!PredToDestList.empty());
1496 DestPopularity[
nullptr] = 0;
1498 DestPopularity[SuccBB] = 0;
1500 for (
const auto &PredToDest : PredToDestList)
1501 if (PredToDest.second)
1502 DestPopularity[PredToDest.second]++;
1508 return MostPopular->first;
1518 assert(PredBB &&
"Expected a single predecessor");
1520 if (
Constant *Cst = dyn_cast<Constant>(V)) {
1526 if (!
I || (
I->getParent() != BB &&
I->getParent() != PredBB)) {
1532 if (
PHI->getParent() == PredBB)
1533 return dyn_cast<Constant>(
PHI->getIncomingValueForBlock(PredPredBB));
1538 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1539 if (CondCmp->getParent() == BB) {
1560 if (LoopHeaders.count(BB))
1572 "computeValueKnownInPredecessors returned true with no values");
1575 for (
const auto &PredValue : PredValues) {
1577 <<
"': FOUND condition = " << *PredValue.first
1578 <<
" for pred '" << PredValue.second->getName() <<
"'.\n";
1593 for (
const auto &PredValue : PredValues) {
1595 if (!SeenPreds.insert(Pred).second)
1601 if (isa<UndefValue>(Val))
1604 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1605 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->
isZero());
1607 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1608 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1611 &&
"Unexpected terminator");
1612 assert(isa<BlockAddress>(Val) &&
"Expecting a constant blockaddress");
1613 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1617 if (PredToDestList.
empty()) {
1621 if (OnlyDest != DestBB)
1622 OnlyDest = MultipleDestSentinel;
1626 OnlyVal = MultipleVal;
1638 if (PredToDestList.
empty())
1644 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1646 bool SeenFirstBranchToOnlyDest =
false;
1647 std::vector <DominatorTree::UpdateType> Updates;
1650 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1651 SeenFirstBranchToOnlyDest =
true;
1653 SuccBB->removePredecessor(BB,
true);
1662 Term->eraseFromParent();
1663 DTU->applyUpdatesPermissive(Updates);
1664 if (
auto *BPI = getBPI())
1665 BPI->eraseBlock(BB);
1669 if (
auto *CondInst = dyn_cast<Instruction>(
Cond)) {
1670 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1671 CondInst->eraseFromParent();
1679 else if (OnlyVal && OnlyVal != MultipleVal)
1692 if (MostPopularDest == MultipleDestSentinel) {
1697 [&](
const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1698 return LoopHeaders.contains(PredToDest.second);
1701 if (PredToDestList.
empty())
1710 for (
const auto &PredToDest : PredToDestList)
1711 if (PredToDest.second == MostPopularDest) {
1724 if (!MostPopularDest)
1753 if (PredBr->isUnconditional()) {
1754 PredBBs[0] = PredBB;
1778 if (!isa<PHINode>(BB->
front()))
1815 "computeValueKnownInPredecessors returned true with no values");
1819 unsigned NumTrue = 0, NumFalse = 0;
1820 for (
const auto &XorOpValue : XorOpValues) {
1821 if (isa<UndefValue>(XorOpValue.first))
1824 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1832 if (NumTrue > NumFalse)
1834 else if (NumTrue != 0 || NumFalse != 0)
1840 for (
const auto &XorOpValue : XorOpValues) {
1841 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1844 BlocksToFoldInto.
push_back(XorOpValue.second);
1849 if (BlocksToFoldInto.
size() ==
1850 cast<PHINode>(BB->
front()).getNumIncomingValues()) {
1888 Value *
IV = PN.getIncomingValueForBlock(OldPred);
1897 PN.addIncoming(
IV, NewPred);
1913 if (LoopHeaders.erase(SinglePred))
1914 LoopHeaders.insert(BB);
1967 for (
Use &U :
I.uses()) {
1970 if (UserPN->getIncomingBlock(U) == BB)
1972 }
else if (
User->getParent() == BB)
1988 if (UsesToRename.
empty() && DbgValues.
empty() && DbgVariableRecords.
empty())
1990 LLVM_DEBUG(
dbgs() <<
"JT: Renaming non-local uses of: " <<
I <<
"\n");
1999 while (!UsesToRename.
empty())
2001 if (!DbgValues.
empty() || !DbgVariableRecords.
empty()) {
2005 DbgVariableRecords.
clear();
2026 auto RetargetDbgValueIfPossible = [&](
Instruction *NewInst) ->
bool {
2027 auto DbgInstruction = dyn_cast<DbgValueInst>(NewInst);
2028 if (!DbgInstruction)
2032 for (
auto DbgOperand : DbgInstruction->location_ops()) {
2033 auto DbgOperandInstruction = dyn_cast<Instruction>(DbgOperand);
2034 if (!DbgOperandInstruction)
2037 auto I = ValueMapping.
find(DbgOperandInstruction);
2038 if (
I != ValueMapping.
end()) {
2040 std::pair<Value *, Value *>(DbgOperand,
I->second));
2044 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2045 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2053 for (
auto *
Op : DVR->location_ops()) {
2058 auto I = ValueMapping.
find(OpInst);
2059 if (
I != ValueMapping.
end())
2060 OperandsToRemap.
insert({OpInst,
I->second});
2063 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2064 DVR->replaceVariableLocationOp(OldOp, MappedOp);
2072 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2075 ValueMapping[PN] = NewPN;
2090 RetargetDbgVariableRecordIfPossible(&DVR);
2096 for (; BI != BE; ++BI) {
2098 New->setName(BI->getName());
2099 New->insertInto(NewBB, NewBB->
end());
2100 ValueMapping[&*BI] = New;
2103 CloneAndRemapDbgInfo(New, &*BI);
2105 if (RetargetDbgValueIfPossible(New))
2109 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2110 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2112 if (
I != ValueMapping.
end())
2113 New->setOperand(i,
I->second);
2119 if (BE != RangeBB->
end() && BE->hasDbgRecords()) {
2125 RetargetDbgVariableRecordIfPossible(&DVR);
2185 if (LoopHeaders.count(PredBB))
2195 unsigned ZeroCount = 0;
2196 unsigned OneCount = 0;
2202 if (isa<IndirectBrInst>(
P->getTerminator()))
2204 if (
ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2209 }
else if (CI->isOne()) {
2218 if (ZeroCount == 1) {
2219 PredPredBB = ZeroPred;
2220 }
else if (OneCount == 1) {
2221 PredPredBB = OnePred;
2231 <<
"' - would thread to self!\n");
2237 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2239 bool BBIsHeader = LoopHeaders.count(BB);
2240 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2241 dbgs() <<
" Not threading across "
2242 << (BBIsHeader ?
"loop header BB '" :
"block BB '")
2243 << BB->
getName() <<
"' to dest "
2244 << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2246 <<
"' - it might create an irreducible loop!\n";
2260 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2261 BBCost + PredBBCost > BBDupThreshold) {
2263 <<
"' - Cost is too high: " << PredBBCost
2264 <<
" for PredBB, " << BBCost <<
"for BB\n");
2281 bool HasProfile = doesBlockHaveProfileData(BB);
2282 auto *BFI = getOrCreateBFI(HasProfile);
2283 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2295 assert(BPI &&
"It's expected BPI to exist along with BFI");
2296 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2297 BPI->getEdgeProbability(PredPredBB, PredBB);
2298 BFI->setBlockFreq(NewBB, NewBBFreq);
2310 BPI->copyEdgeProbabilities(PredBB, NewBB);
2327 DTU->applyUpdatesPermissive(
2352 <<
"' - would thread to self!\n");
2358 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2360 bool BBIsHeader = LoopHeaders.count(BB);
2361 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2362 dbgs() <<
" Not threading across "
2363 << (BBIsHeader ?
"loop header BB '" :
"block BB '") << BB->
getName()
2364 <<
"' to dest " << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2365 << SuccBB->
getName() <<
"' - it might create an irreducible loop!\n";
2372 if (JumpThreadCost > BBDupThreshold) {
2374 <<
"' - Cost is too high: " << JumpThreadCost <<
"\n");
2388 assert(SuccBB != BB &&
"Don't create an infinite loop");
2390 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2391 "Don't thread across loop headers");
2394 bool HasProfile = doesBlockHaveProfileData(BB);
2395 auto *BFI = getOrCreateBFI(HasProfile);
2396 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2400 if (PredBBs.
size() == 1)
2401 PredBB = PredBBs[0];
2404 <<
" common predecessors.\n");
2405 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2410 <<
"' to '" << SuccBB->
getName()
2411 <<
", across block:\n " << *BB <<
"\n");
2422 assert(BPI &&
"It's expected BPI to exist along with BFI");
2424 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2425 BFI->setBlockFreq(NewBB, NewBBFreq);
2465 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2476 const char *Suffix) {
2482 auto *BFI = getBFI();
2484 auto *BPI = getOrCreateBPI(
true);
2485 for (
auto *Pred : Preds)
2486 FreqMap.
insert(std::make_pair(
2487 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2493 std::string NewName = std::string(Suffix) +
".split-lp";
2499 std::vector<DominatorTree::UpdateType> Updates;
2500 Updates.reserve((2 * Preds.size()) + NewBBs.
size());
2501 for (
auto *NewBB : NewBBs) {
2508 NewBBFreq += FreqMap.
lookup(Pred);
2511 BFI->setBlockFreq(NewBB, NewBBFreq);
2514 DTU->applyUpdatesPermissive(Updates);
2518bool JumpThreadingPass::doesBlockHaveProfileData(
BasicBlock *BB) {
2529void JumpThreadingPass::updateBlockFreqAndEdgeWeight(
BasicBlock *PredBB,
2536 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2537 "Both BFI & BPI should either be set or unset");
2541 "It's expected to have BFI/BPI when profile info exists");
2547 auto BBOrigFreq =
BFI->getBlockFreq(BB);
2548 auto NewBBFreq =
BFI->getBlockFreq(NewBB);
2550 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2551 BFI->setBlockFreq(BB, BBNewFreq);
2557 auto SuccFreq = (Succ == SuccBB)
2558 ? BB2SuccBBFreq - NewBBFreq
2560 BBSuccFreq.
push_back(SuccFreq.getFrequency());
2566 if (MaxBBSuccFreq == 0)
2568 {1, static_cast<unsigned>(BBSuccFreq.size())});
2615 if (BBSuccProbs.
size() >= 2 && HasProfile) {
2617 for (
auto Prob : BBSuccProbs)
2632 assert(!PredBBs.
empty() &&
"Can't handle an empty set");
2637 if (LoopHeaders.count(BB)) {
2639 <<
"' into predecessor block '" << PredBBs[0]->getName()
2640 <<
"' - it might create an irreducible loop!\n");
2646 if (DuplicationCost > BBDupThreshold) {
2648 <<
"' - Cost is too high: " << DuplicationCost <<
"\n");
2653 std::vector<DominatorTree::UpdateType> Updates;
2655 if (PredBBs.
size() == 1)
2656 PredBB = PredBBs[0];
2659 <<
" common predecessors.\n");
2660 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2667 <<
"' into end of '" << PredBB->
getName()
2668 <<
"' to eliminate branch on phi. Cost: "
2669 << DuplicationCost <<
" block is:" << *BB <<
"\n");
2689 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2693 for (; BI != BB->
end(); ++BI) {
2695 New->insertInto(PredBB, OldPredBranch->
getIterator());
2698 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2699 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2701 if (
I != ValueMapping.
end())
2702 New->setOperand(i,
I->second);
2713 {BB->
getModule()->getDataLayout(), TLI,
nullptr,
nullptr, New})) {
2714 ValueMapping[&*BI] =
IV;
2715 if (!New->mayHaveSideEffects()) {
2716 New->eraseFromParent();
2723 ValueMapping[&*BI] = New;
2727 New->setName(BI->getName());
2729 New->cloneDebugInfoFrom(&*BI);
2731 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2732 if (
BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2753 if (
auto *BPI = getBPI())
2755 DTU->applyUpdatesPermissive(Updates);
2786 BI->applyMergedLocation(PredTerm->
getDebugLoc(), SI->getDebugLoc());
2787 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2795 (TrueWeight + FalseWeight) != 0) {
2798 TrueWeight, TrueWeight + FalseWeight));
2800 FalseWeight, TrueWeight + FalseWeight));
2802 if (
auto *BPI = getBPI())
2806 if (
auto *BFI = getBFI()) {
2807 if ((TrueWeight + FalseWeight) == 0) {
2812 TrueWeight, TrueWeight + FalseWeight);
2813 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2814 BFI->setBlockFreq(NewBB, NewBBFreq);
2818 SI->eraseFromParent();
2824 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2826 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2830 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2832 if (!CondPHI || CondPHI->
getParent() != BB)
2882 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2894 CondRHS, Pred, BB, CondCmp);
2897 CondRHS, Pred, BB, CondCmp);
2900 LHSFolds != RHSFolds) {
2936 if (LoopHeaders.count(BB))
2940 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2943 [](
Value *V) { return !isa<ConstantInt>(V); }))
2947 using namespace PatternMatch;
2950 if (SI->getParent() != BB)
2954 return Cond &&
Cond == V &&
Cond->getType()->isIntegerTy(1) && !IsAndOr;
2958 for (
Use &U : PN->uses()) {
2959 if (
ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2962 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2963 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2964 if (
SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2965 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2969 }
else if (
SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2971 if (isUnfoldCandidate(SelectI, U.get())) {
2990 NewPN->
addIncoming(SI->getTrueValue(), Term->getParent());
2993 SI->replaceAllUsesWith(NewPN);
2994 SI->eraseFromParent();
2996 std::vector<DominatorTree::UpdateType> Updates;
3006 DTU->applyUpdatesPermissive(Updates);
3032 using namespace PatternMatch;
3054 if (
auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3075 bool TrueDestIsSafe =
false;
3076 bool FalseDestIsSafe =
false;
3081 TrueDestIsSafe =
true;
3086 FalseDestIsSafe =
true;
3089 if (!TrueDestIsSafe && !FalseDestIsSafe)
3092 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3093 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3099 if (
Cost > BBDupThreshold)
3104 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3105 assert(GuardedBlock &&
"Could not create the guarded block?");
3110 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3111 assert(UnguardedBlock &&
"Could not create the unguarded block?");
3113 << GuardedBlock->
getName() <<
"\n");
3118 for (
auto BI = BB->
begin(); &*BI != AfterGuard; ++BI)
3119 if (!isa<PHINode>(&*BI))
3123 assert(InsertionPoint != BB->
end() &&
"Empty block?");
3126 if (!Inst->use_empty()) {
3128 NewPN->
addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3129 NewPN->
addIncoming(GuardedMapping[Inst], GuardedBlock);
3132 Inst->replaceAllUsesWith(NewPN);
3134 Inst->dropDbgRecords();
3135 Inst->eraseFromParent();
3150template <
typename AnalysisT>
3151typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3152 assert(FAM &&
"Can't run external analysis without FunctionAnalysisManager");
3157 if (!ChangedSinceLastAnalysisUpdate) {
3158 assert(!DTU->hasPendingUpdates() &&
3159 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3163 ChangedSinceLastAnalysisUpdate =
false;
3165 auto PA = getPreservedAnalysis();
3175 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3176 assert((!DTU->hasPostDomTree() ||
3177 DTU->getPostDomTree().verify(
3191 assert(FAM &&
"Can't create BPI without FunctionAnalysisManager");
3199 assert(FAM &&
"Can't create BFI without FunctionAnalysisManager");
3209 auto *Res = getBPI();
3214 BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
3220 auto *Res = getBFI();
3225 BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
static const Function * getParent(const Value *V)
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...
static cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)
static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
static cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)
static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...
static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, ValueToValueMapTy &ValueMap)
addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
findMostPopularDest - The specified list contains multiple possible threadable destinations.
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
static bool hasAddressTakenAndUsed(BasicBlock *BB)
See the comments on JumpThreadingPass.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet 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)
This defines the Use class.
static const uint32_t IV[8]
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
DbgMarker * createMarker(Instruction *I)
Attach a DbgMarker to the given instruction.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator const_iterator
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isLandingPad() const
Return true if this basic block is a landing pad.
bool isEHPad() const
Return true if this basic block is an exception handling block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
void disableDominatorTree()
Disable the use of the dominator tree during alias analysis queries.
The address of a basic block.
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
bool isConditional() const
unsigned getNumSuccessors() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
uint32_t getNumerator() const
BranchProbability getCompl() const
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
Value * getArgOperand(unsigned i) const
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Predicate getPredicate() const
Return the predicate for this instruction.
static Constant * getNot(Constant *C)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Per-instruction record of debug-info.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DbgMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)
Clone all DbgMarkers from From into this marker.
const BasicBlock * getParent() const
This represents the llvm.dbg.value instruction.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Analysis pass which computes a DominatorTree.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This class represents a freeze function that returns random concrete value if an operand is either a ...
const BasicBlock & getEntryBlock() const
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Module * getParent()
Get the module that this global value is contained inside of...
This instruction compares its operands according to the predicate given to the constructor.
Indirect Branch Instruction.
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(const Instruction *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere=std::nullopt, bool InsertAtHead=false)
Clone any debug-info attached to From onto this instruction.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
bool isSpecialTerminator() const
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
A wrapper class for inspecting calls to intrinsic functions.
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
JumpThreadingPass(int T=-1)
void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, DenseSet< Value * > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
bool processImpliedCondition(BasicBlock *BB)
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
This is an important class for using LLVM in a threaded context.
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
Tristate
This is used to return true/false/dunno results.
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void forgetValue(Value *V)
Remove information related to this value from the cache.
An instruction for reading from memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
This class implements a map that also provides access to all stored values in a deterministic order.
Representation for a specific memory location.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
Helper class for SSA formation on a set of values defined in multiple blocks.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
void UpdateDebugValues(Instruction *I)
Rewrite debug value intrinsics to conform to a new SSA form.
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
This class represents the LLVM 'select' instruction.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
static IntegerType * getInt1Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
'undef' values are things that do not have specified contents.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
iterator find(const KeyT &Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
std::pair< iterator, bool > insert(const ValueT &V)
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
auto successors(const MachineBasicBlock *BB)
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)
Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
pred_iterator pred_begin(BasicBlock *BB)
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
bool hasValidBranchWeightMD(const Instruction &I)
Checks if an instructions has valid Branch Weight Metadata.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)
Duplicate the specified list of noalias decl scopes.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)
Adapt the metadata for the specified instruction according to the provided mapping.
auto max_element(R &&Range)
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
unsigned pred_size(const MachineBasicBlock *BB)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Function object to check whether the second component of a container supported by std::get (like std:...