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 DPV.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) {
873 Result.emplace_back(KC, LHSVal.second);
876 return !Result.empty();
886 if ((TrueVal || FalseVal) &&
889 for (
auto &
C : Conds) {
896 KnownCond = CI->isOne();
898 assert(isa<UndefValue>(
Cond) &&
"Unexpected condition value");
902 KnownCond = (TrueVal !=
nullptr);
906 if (
Constant *Val = KnownCond ? TrueVal : FalseVal)
907 Result.emplace_back(Val,
C.second);
910 return !Result.empty();
919 Result.emplace_back(KC, Pred);
922 return !Result.empty();
932 unsigned MinSucc = 0;
935 unsigned MinNumPreds =
pred_size(TestBB);
939 if (NumPreds < MinNumPreds) {
941 MinNumPreds = NumPreds;
963 if (DTU->isBBPendingDeletion(BB) ||
988 if (
BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
990 if (BI->isUnconditional())
return false;
991 Condition = BI->getCondition();
992 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
993 Condition = SI->getCondition();
994 }
else if (
IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
996 if (IB->getNumSuccessors() == 0)
return false;
997 Condition = IB->getAddress()->stripPointerCasts();
1004 bool ConstantFolded =
false;
1008 if (
Instruction *
I = dyn_cast<Instruction>(Condition)) {
1012 I->replaceAllUsesWith(SimpleVal);
1014 I->eraseFromParent();
1015 Condition = SimpleVal;
1016 ConstantFolded =
true;
1022 auto *FI = dyn_cast<FreezeInst>(Condition);
1023 if (isa<UndefValue>(Condition) ||
1024 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1026 std::vector<DominatorTree::UpdateType> Updates;
1032 if (i == BestSucc)
continue;
1039 <<
"' folding undef terminator: " << *BBTerm <<
'\n');
1043 DTU->applyUpdatesPermissive(Updates);
1045 FI->eraseFromParent();
1058 if (
auto *BPI = getBPI())
1059 BPI->eraseBlock(BB);
1063 Instruction *CondInst = dyn_cast<Instruction>(Condition);
1070 return ConstantFolded;
1074 Value *CondWithoutFreeze = CondInst;
1075 if (
auto *FI = dyn_cast<FreezeInst>(CondInst))
1076 CondWithoutFreeze = FI->getOperand(0);
1078 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(CondWithoutFreeze)) {
1082 if (
Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1084 LVI->
getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1117 Value *SimplifyValue = CondWithoutFreeze;
1119 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1120 if (isa<Constant>(CondCmp->getOperand(1)))
1121 SimplifyValue = CondCmp->getOperand(0);
1125 if (
LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1130 if (
PHINode *PN = dyn_cast<PHINode>(CondInst))
1131 if (PN->getParent() == BB && isa<BranchInst>(BB->
getTerminator()))
1142 PHINode *PN = dyn_cast<PHINode>(CondWithoutFreeze);
1147 if (CondInst->
getOpcode() == Instruction::Xor &&
1161 if (!BI || !BI->isConditional())
1170 auto *FICond = dyn_cast<FreezeInst>(
Cond);
1171 if (FICond && FICond->hasOneUse())
1172 Cond = FICond->getOperand(0);
1183 auto *PBI = dyn_cast<BranchInst>(CurrentPred->
getTerminator());
1184 if (!PBI || !PBI->isConditional())
1186 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1189 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1190 std::optional<bool> Implication =
1195 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1196 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1197 FICond->getOperand(0))
1198 Implication = CondIsTrue;
1202 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1203 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1208 BI->eraseFromParent();
1210 FICond->eraseFromParent();
1213 if (
auto *BPI = getBPI())
1214 BPI->eraseBlock(BB);
1217 CurrentBB = CurrentPred;
1227 if (OpInst->getParent() == BB)
1272 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1279 if (AvailableVal == LoadI)
1281 if (AvailableVal->getType() != LoadI->
getType())
1292 if (BBIt != LoadBB->
begin())
1303 AvailablePredsTy AvailablePreds;
1311 if (!PredsScanned.
insert(PredBB).second)
1314 BBIt = PredBB->
end();
1315 unsigned NumScanedInst = 0;
1316 Value *PredAvailable =
nullptr;
1320 "Attempting to CSE volatile or atomic loads");
1330 &BatchAA, &IsLoadCSE, &NumScanedInst);
1335 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->
begin() &&
1339 BBIt = SinglePredBB->
end();
1341 Loc, AccessTy, LoadI->
isAtomic(), SinglePredBB, BBIt,
1347 if (!PredAvailable) {
1348 OneUnavailablePred = PredBB;
1353 CSELoads.
push_back(cast<LoadInst>(PredAvailable));
1357 AvailablePreds.emplace_back(PredBB, PredAvailable);
1362 if (AvailablePreds.empty())
return false;
1379 if (PredsScanned.
size() != AvailablePreds.size() &&
1381 for (
auto I = LoadBB->
begin(); &*
I != LoadI; ++
I)
1388 if (PredsScanned.
size() == AvailablePreds.size()+1 &&
1390 UnavailablePred = OneUnavailablePred;
1391 }
else if (PredsScanned.
size() != AvailablePreds.size()) {
1397 for (
const auto &AvailablePred : AvailablePreds)
1398 AvailablePredSet.
insert(AvailablePred.first);
1403 if (isa<IndirectBrInst>(
P->getTerminator()))
1406 if (!AvailablePredSet.
count(
P))
1411 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit,
"thread-pre-split");
1417 if (UnavailablePred) {
1419 "Can't handle critical edge here!");
1429 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1445 AvailablePredsTy::iterator
I =
1448 assert(
I != AvailablePreds.end() &&
I->first ==
P &&
1449 "Didn't find entry for predecessor!");
1455 Value *&PredV =
I->second;
1458 PredV, LoadI->
getType(),
"",
P->getTerminator()->getIterator());
1463 for (
LoadInst *PredLoadI : CSELoads) {
1481 assert(!PredToDestList.empty());
1493 DestPopularity[
nullptr] = 0;
1495 DestPopularity[SuccBB] = 0;
1497 for (
const auto &PredToDest : PredToDestList)
1498 if (PredToDest.second)
1499 DestPopularity[PredToDest.second]++;
1505 return MostPopular->first;
1514 assert(PredBB &&
"Expected a single predecessor");
1516 if (
Constant *Cst = dyn_cast<Constant>(V)) {
1522 if (!
I || (
I->getParent() != BB &&
I->getParent() != PredBB)) {
1528 if (
PHI->getParent() == PredBB)
1529 return dyn_cast<Constant>(
PHI->getIncomingValueForBlock(PredPredBB));
1534 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1535 if (CondCmp->getParent() == BB) {
1555 if (LoopHeaders.count(BB))
1567 "computeValueKnownInPredecessors returned true with no values");
1570 for (
const auto &PredValue : PredValues) {
1572 <<
"': FOUND condition = " << *PredValue.first
1573 <<
" for pred '" << PredValue.second->getName() <<
"'.\n";
1588 for (
const auto &PredValue : PredValues) {
1590 if (!SeenPreds.insert(Pred).second)
1596 if (isa<UndefValue>(Val))
1599 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1600 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->
isZero());
1602 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1603 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1606 &&
"Unexpected terminator");
1607 assert(isa<BlockAddress>(Val) &&
"Expecting a constant blockaddress");
1608 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1612 if (PredToDestList.
empty()) {
1616 if (OnlyDest != DestBB)
1617 OnlyDest = MultipleDestSentinel;
1621 OnlyVal = MultipleVal;
1633 if (PredToDestList.
empty())
1639 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1641 bool SeenFirstBranchToOnlyDest =
false;
1642 std::vector <DominatorTree::UpdateType> Updates;
1645 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1646 SeenFirstBranchToOnlyDest =
true;
1648 SuccBB->removePredecessor(BB,
true);
1657 Term->eraseFromParent();
1658 DTU->applyUpdatesPermissive(Updates);
1659 if (
auto *BPI = getBPI())
1660 BPI->eraseBlock(BB);
1664 if (
auto *CondInst = dyn_cast<Instruction>(
Cond)) {
1665 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1666 CondInst->eraseFromParent();
1674 else if (OnlyVal && OnlyVal != MultipleVal)
1687 if (MostPopularDest == MultipleDestSentinel) {
1692 [&](
const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1693 return LoopHeaders.contains(PredToDest.second);
1696 if (PredToDestList.
empty())
1705 for (
const auto &PredToDest : PredToDestList)
1706 if (PredToDest.second == MostPopularDest) {
1719 if (!MostPopularDest)
1748 if (PredBr->isUnconditional()) {
1749 PredBBs[0] = PredBB;
1773 if (!isa<PHINode>(BB->
front()))
1810 "computeValueKnownInPredecessors returned true with no values");
1814 unsigned NumTrue = 0, NumFalse = 0;
1815 for (
const auto &XorOpValue : XorOpValues) {
1816 if (isa<UndefValue>(XorOpValue.first))
1819 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1827 if (NumTrue > NumFalse)
1829 else if (NumTrue != 0 || NumFalse != 0)
1835 for (
const auto &XorOpValue : XorOpValues) {
1836 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1839 BlocksToFoldInto.
push_back(XorOpValue.second);
1844 if (BlocksToFoldInto.
size() ==
1845 cast<PHINode>(BB->
front()).getNumIncomingValues()) {
1883 Value *
IV = PN.getIncomingValueForBlock(OldPred);
1892 PN.addIncoming(
IV, NewPred);
1908 if (LoopHeaders.erase(SinglePred))
1909 LoopHeaders.insert(BB);
1963 for (
Use &U :
I.uses()) {
1966 if (UserPN->getIncomingBlock(U) == BB)
1968 }
else if (
User->getParent() == BB)
1986 LLVM_DEBUG(
dbgs() <<
"JT: Renaming non-local uses of: " <<
I <<
"\n");
1995 while (!UsesToRename.
empty())
1997 if (!DbgValues.
empty() || !DPValues.
empty()) {
2021 auto RetargetDbgValueIfPossible = [&](
Instruction *NewInst) ->
bool {
2022 auto DbgInstruction = dyn_cast<DbgValueInst>(NewInst);
2023 if (!DbgInstruction)
2027 for (
auto DbgOperand : DbgInstruction->location_ops()) {
2028 auto DbgOperandInstruction = dyn_cast<Instruction>(DbgOperand);
2029 if (!DbgOperandInstruction)
2032 auto I = ValueMapping.
find(DbgOperandInstruction);
2033 if (
I != ValueMapping.
end()) {
2035 std::pair<Value *, Value *>(DbgOperand,
I->second));
2039 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2040 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2046 auto RetargetDPValueIfPossible = [&](
DPValue *DPV) {
2048 for (
auto *
Op : DPV->location_ops()) {
2053 auto I = ValueMapping.
find(OpInst);
2054 if (
I != ValueMapping.
end())
2055 OperandsToRemap.
insert({OpInst,
I->second});
2058 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2059 DPV->replaceVariableLocationOp(OldOp, MappedOp);
2067 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2070 ValueMapping[PN] = NewPN;
2085 RetargetDPValueIfPossible(&DPV);
2091 for (; BI != BE; ++BI) {
2093 New->setName(BI->getName());
2094 New->insertInto(NewBB, NewBB->
end());
2095 ValueMapping[&*BI] = New;
2098 CloneAndRemapDbgInfo(New, &*BI);
2100 if (RetargetDbgValueIfPossible(New))
2104 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2105 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2107 if (
I != ValueMapping.
end())
2108 New->setOperand(i,
I->second);
2114 if (BE != RangeBB->
end() && BE->hasDbgRecords()) {
2120 RetargetDPValueIfPossible(&DPV);
2123 return ValueMapping;
2180 if (LoopHeaders.count(PredBB))
2190 unsigned ZeroCount = 0;
2191 unsigned OneCount = 0;
2196 if (isa<IndirectBrInst>(
P->getTerminator()))
2198 if (
ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2203 }
else if (CI->isOne()) {
2212 if (ZeroCount == 1) {
2213 PredPredBB = ZeroPred;
2214 }
else if (OneCount == 1) {
2215 PredPredBB = OnePred;
2225 <<
"' - would thread to self!\n");
2231 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2233 bool BBIsHeader = LoopHeaders.count(BB);
2234 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2235 dbgs() <<
" Not threading across "
2236 << (BBIsHeader ?
"loop header BB '" :
"block BB '")
2237 << BB->
getName() <<
"' to dest "
2238 << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2240 <<
"' - it might create an irreducible loop!\n";
2254 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2255 BBCost + PredBBCost > BBDupThreshold) {
2257 <<
"' - Cost is too high: " << PredBBCost
2258 <<
" for PredBB, " << BBCost <<
"for BB\n");
2275 bool HasProfile = doesBlockHaveProfileData(BB);
2276 auto *BFI = getOrCreateBFI(HasProfile);
2277 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2289 assert(BPI &&
"It's expected BPI to exist along with BFI");
2290 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2291 BPI->getEdgeProbability(PredPredBB, PredBB);
2292 BFI->setBlockFreq(NewBB, NewBBFreq);
2303 BPI->copyEdgeProbabilities(PredBB, NewBB);
2320 DTU->applyUpdatesPermissive(
2345 <<
"' - would thread to self!\n");
2351 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2353 bool BBIsHeader = LoopHeaders.count(BB);
2354 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2355 dbgs() <<
" Not threading across "
2356 << (BBIsHeader ?
"loop header BB '" :
"block BB '") << BB->
getName()
2357 <<
"' to dest " << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2358 << SuccBB->
getName() <<
"' - it might create an irreducible loop!\n";
2365 if (JumpThreadCost > BBDupThreshold) {
2367 <<
"' - Cost is too high: " << JumpThreadCost <<
"\n");
2381 assert(SuccBB != BB &&
"Don't create an infinite loop");
2383 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2384 "Don't thread across loop headers");
2387 bool HasProfile = doesBlockHaveProfileData(BB);
2388 auto *BFI = getOrCreateBFI(HasProfile);
2389 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2393 if (PredBBs.
size() == 1)
2394 PredBB = PredBBs[0];
2397 <<
" common predecessors.\n");
2398 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2403 <<
"' to '" << SuccBB->
getName()
2404 <<
", across block:\n " << *BB <<
"\n");
2415 assert(BPI &&
"It's expected BPI to exist along with BFI");
2417 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2418 BFI->setBlockFreq(NewBB, NewBBFreq);
2457 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2468 const char *Suffix) {
2474 auto *BFI = getBFI();
2476 auto *BPI = getOrCreateBPI(
true);
2477 for (
auto *Pred : Preds)
2478 FreqMap.
insert(std::make_pair(
2479 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2485 std::string NewName = std::string(Suffix) +
".split-lp";
2491 std::vector<DominatorTree::UpdateType> Updates;
2492 Updates.reserve((2 * Preds.size()) + NewBBs.
size());
2493 for (
auto *NewBB : NewBBs) {
2500 NewBBFreq += FreqMap.
lookup(Pred);
2503 BFI->setBlockFreq(NewBB, NewBBFreq);
2506 DTU->applyUpdatesPermissive(Updates);
2510bool JumpThreadingPass::doesBlockHaveProfileData(
BasicBlock *BB) {
2521void JumpThreadingPass::updateBlockFreqAndEdgeWeight(
BasicBlock *PredBB,
2528 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2529 "Both BFI & BPI should either be set or unset");
2533 "It's expected to have BFI/BPI when profile info exists");
2539 auto BBOrigFreq =
BFI->getBlockFreq(BB);
2540 auto NewBBFreq =
BFI->getBlockFreq(NewBB);
2542 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2543 BFI->setBlockFreq(BB, BBNewFreq);
2549 auto SuccFreq = (Succ == SuccBB)
2550 ? BB2SuccBBFreq - NewBBFreq
2552 BBSuccFreq.
push_back(SuccFreq.getFrequency());
2558 if (MaxBBSuccFreq == 0)
2560 {1, static_cast<unsigned>(BBSuccFreq.size())});
2607 if (BBSuccProbs.
size() >= 2 && HasProfile) {
2609 for (
auto Prob : BBSuccProbs)
2624 assert(!PredBBs.
empty() &&
"Can't handle an empty set");
2629 if (LoopHeaders.count(BB)) {
2631 <<
"' into predecessor block '" << PredBBs[0]->getName()
2632 <<
"' - it might create an irreducible loop!\n");
2638 if (DuplicationCost > BBDupThreshold) {
2640 <<
"' - Cost is too high: " << DuplicationCost <<
"\n");
2645 std::vector<DominatorTree::UpdateType> Updates;
2647 if (PredBBs.
size() == 1)
2648 PredBB = PredBBs[0];
2651 <<
" common predecessors.\n");
2652 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2659 <<
"' into end of '" << PredBB->
getName()
2660 <<
"' to eliminate branch on phi. Cost: "
2661 << DuplicationCost <<
" block is:" << *BB <<
"\n");
2681 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2685 for (; BI != BB->
end(); ++BI) {
2687 New->insertInto(PredBB, OldPredBranch->
getIterator());
2690 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2691 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2693 if (
I != ValueMapping.
end())
2694 New->setOperand(i,
I->second);
2702 {BB->
getModule()->getDataLayout(), TLI,
nullptr,
nullptr, New})) {
2703 ValueMapping[&*BI] =
IV;
2704 if (!New->mayHaveSideEffects()) {
2705 New->eraseFromParent();
2712 ValueMapping[&*BI] = New;
2716 New->setName(BI->getName());
2718 New->cloneDebugInfoFrom(&*BI);
2720 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2721 if (
BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2734 updateSSA(BB, PredBB, ValueMapping);
2741 OldPredBranch->eraseFromParent();
2742 if (
auto *BPI = getBPI())
2744 DTU->applyUpdatesPermissive(Updates);
2775 BI->applyMergedLocation(PredTerm->
getDebugLoc(), SI->getDebugLoc());
2776 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2784 (TrueWeight + FalseWeight) != 0) {
2787 TrueWeight, TrueWeight + FalseWeight));
2789 FalseWeight, TrueWeight + FalseWeight));
2791 if (
auto *BPI = getBPI())
2795 if (
auto *BFI = getBFI()) {
2796 if ((TrueWeight + FalseWeight) == 0) {
2801 TrueWeight, TrueWeight + FalseWeight);
2802 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2803 BFI->setBlockFreq(NewBB, NewBBFreq);
2807 SI->eraseFromParent();
2813 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2815 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2819 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2821 if (!CondPHI || CondPHI->
getParent() != BB)
2871 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2883 CondRHS, Pred, BB, CondCmp);
2886 CondRHS, Pred, BB, CondCmp);
2889 LHSFolds != RHSFolds) {
2925 if (LoopHeaders.count(BB))
2929 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2932 [](
Value *V) { return !isa<ConstantInt>(V); }))
2936 using namespace PatternMatch;
2939 if (SI->getParent() != BB)
2943 return Cond &&
Cond == V &&
Cond->getType()->isIntegerTy(1) && !IsAndOr;
2947 for (
Use &U : PN->uses()) {
2948 if (
ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2951 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2952 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2953 if (
SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2954 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2958 }
else if (
SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2960 if (isUnfoldCandidate(SelectI, U.get())) {
2979 NewPN->
addIncoming(SI->getTrueValue(), Term->getParent());
2981 SI->replaceAllUsesWith(NewPN);
2982 SI->eraseFromParent();
2984 std::vector<DominatorTree::UpdateType> Updates;
2994 DTU->applyUpdatesPermissive(Updates);
3020 using namespace PatternMatch;
3042 if (
auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3063 bool TrueDestIsSafe =
false;
3064 bool FalseDestIsSafe =
false;
3069 TrueDestIsSafe =
true;
3074 FalseDestIsSafe =
true;
3077 if (!TrueDestIsSafe && !FalseDestIsSafe)
3080 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3081 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3087 if (
Cost > BBDupThreshold)
3092 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3093 assert(GuardedBlock &&
"Could not create the guarded block?");
3098 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3099 assert(UnguardedBlock &&
"Could not create the unguarded block?");
3101 << GuardedBlock->
getName() <<
"\n");
3106 for (
auto BI = BB->
begin(); &*BI != AfterGuard; ++BI)
3107 if (!isa<PHINode>(&*BI))
3111 assert(InsertionPoint != BB->
end() &&
"Empty block?");
3114 if (!Inst->use_empty()) {
3116 NewPN->
addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3117 NewPN->
addIncoming(GuardedMapping[Inst], GuardedBlock);
3119 Inst->replaceAllUsesWith(NewPN);
3121 Inst->dropDbgRecords();
3122 Inst->eraseFromParent();
3137template <
typename AnalysisT>
3138typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3139 assert(FAM &&
"Can't run external analysis without FunctionAnalysisManager");
3144 if (!ChangedSinceLastAnalysisUpdate) {
3145 assert(!DTU->hasPendingUpdates() &&
3146 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3150 ChangedSinceLastAnalysisUpdate =
false;
3152 auto PA = getPreservedAnalysis();
3162 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3163 assert((!DTU->hasPostDomTree() ||
3164 DTU->getPostDomTree().verify(
3178 assert(FAM &&
"Can't create BPI without FunctionAnalysisManager");
3186 assert(FAM &&
"Can't create BFI without FunctionAnalysisManager");
3196 auto *Res = getBPI();
3201 BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
3207 auto *Res = getBFI();
3212 BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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 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 void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, DenseMap< Instruction *, Value * > &ValueMap)
addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
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.
DPMarker * getMarker(InstListType::iterator It)
Return the DPMarker for the position given by It, so that DbgRecords can be inserted there.
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...
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.
DPMarker * createMarker(Instruction *I)
Attach a DPMarker to the given instruction.
const Function * getParent() const
Return the enclosing method, or null if none.
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)
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
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.
Per-instruction record of debug-info.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DPMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)
Clone all DPMarkers from From into this marker.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
const BasicBlock * getParent() const
This represents the llvm.dbg.value instruction.
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...
iterator find(const_arg_type_t< KeyT > Val)
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...
DenseMap< Instruction *, Value * > cloneInstructions(BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
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)
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)
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
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond)
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 updateSSA(BasicBlock *BB, BasicBlock *NewBB, DenseMap< Instruction *, Value * > &ValueMapping)
Update the SSA form.
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.
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...
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 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.
Interval::pred_iterator pred_end(Interval *I)
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.
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.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
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 findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DPValue * > *DPValues=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
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 DPValue 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:...