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 "print-lvi-after-jump-threading",
107 cl::desc(
"Print the LazyValueInfo cache after JumpThreading"),
cl::init(
false),
111 "jump-threading-across-loop-headers",
112 cl::desc(
"Allow JumpThreading to thread across loop headers, for testing"),
163 if (TrueWeight + FalseWeight == 0)
171 auto GetPredOutEdge =
173 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
174 auto *PredBB = IncomingBB;
175 auto *SuccBB = PhiBB;
178 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
180 return {PredBB, SuccBB};
182 auto *SinglePredBB = PredBB->getSinglePredecessor();
184 return {
nullptr,
nullptr};
188 if (Visited.
count(SinglePredBB))
189 return {
nullptr,
nullptr};
192 PredBB = SinglePredBB;
205 TrueWeight, TrueWeight + FalseWeight)
207 FalseWeight, TrueWeight + FalseWeight));
210 if (!PredOutEdge.first)
218 uint64_t PredTrueWeight, PredFalseWeight;
258 std::make_unique<DomTreeUpdater>(
260 std::nullopt, std::nullopt);
263 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
273#if defined(EXPENSIVE_CHECKS)
275 DominatorTree::VerificationLevel::Full) &&
276 "DT broken after JumpThreading");
280 "PDT broken after JumpThreading");
283 DominatorTree::VerificationLevel::Fast) &&
284 "DT broken after JumpThreading");
288 "PDT broken after JumpThreading");
291 return getPreservedAnalysis();
298 std::unique_ptr<DomTreeUpdater> DTU_,
299 std::optional<BlockFrequencyInfo *> BFI_,
300 std::optional<BranchProbabilityInfo *> BPI_) {
308 DTU = std::move(DTU_);
313 HasGuards = GuardDecl && !GuardDecl->use_empty();
322 BBDupThreshold = DefaultBBDupThreshold;
327 assert(DTU &&
"DTU isn't passed into JumpThreading before using it.");
328 assert(DTU->hasDomTree() &&
"JumpThreading relies on DomTree to proceed.");
337 bool EverChanged =
false;
341 for (
auto &BB : *
F) {
342 if (Unreachable.
count(&BB))
345 Changed = ChangedSinceLastAnalysisUpdate =
true;
355 if (&BB == &
F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
362 <<
"' with terminator: " << *BB.getTerminator()
364 LoopHeaders.erase(&BB);
367 Changed = ChangedSinceLastAnalysisUpdate =
true;
373 auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
374 if (BI && BI->isUnconditional()) {
378 BB.getFirstNonPHIOrDbg(
true)->isTerminator() &&
381 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
387 Changed = ChangedSinceLastAnalysisUpdate =
true;
391 EverChanged |= Changed;
407 bool Changed =
false;
412 if (
Cond->getParent() == KnownAtEndOfBB)
423 Changed |=
I.replaceUsesOfWith(
Cond, ToVal);
425 if (
Cond->use_empty() && !
Cond->mayHaveSideEffects()) {
426 Cond->eraseFromParent();
438 unsigned Threshold) {
439 assert(StopAt->
getParent() == BB &&
"Not an instruction from proper BB?");
444 unsigned PhiCount = 0;
447 if (!isa<PHINode>(&
I)) {
466 if (isa<SwitchInst>(StopAt))
470 if (isa<IndirectBrInst>(StopAt))
481 for (; &*
I != StopAt; ++
I) {
484 if (
Size > Threshold)
489 if (
I->getType()->isTokenTy() &&
I->isUsedOutsideOfBlock(BB))
494 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
495 if (CI->cannotDuplicate() || CI->isConvergent())
509 if (
const CallInst *CI = dyn_cast<CallInst>(
I)) {
510 if (!isa<IntrinsicInst>(CI))
512 else if (!CI->getType()->isVectorTy())
538 for (
const auto &Edge : Edges)
539 LoopHeaders.insert(Edge.second);
552 if (
UndefValue *U = dyn_cast<UndefValue>(Val))
558 return dyn_cast<ConstantInt>(Val);
575 if (!RecursionSet.
insert(V).second)
581 Result.emplace_back(KC, Pred);
583 return !Result.empty();
589 if (!
I ||
I->getParent() != BB) {
594 using namespace PatternMatch;
611 Result.emplace_back(KC,
P);
614 return !Result.empty();
618 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
619 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
620 Value *InVal = PN->getIncomingValue(i);
622 Result.emplace_back(KC, PN->getIncomingBlock(i));
625 PN->getIncomingBlock(i),
628 Result.emplace_back(KC, PN->getIncomingBlock(i));
632 return !Result.empty();
636 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
637 Value *Source = CI->getOperand(0);
644 for (
auto &R : Result)
651 Value *Source = FI->getOperand(0);
659 return !Result.empty();
663 if (
I->getType()->getPrimitiveSizeInBits() == 1) {
664 using namespace PatternMatch;
692 for (
const auto &LHSVal : LHSVals)
693 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
694 Result.emplace_back(InterestingVal, LHSVal.second);
695 LHSKnownBBs.
insert(LHSVal.second);
697 for (
const auto &RHSVal : RHSVals)
698 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
701 if (!LHSKnownBBs.
count(RHSVal.second))
702 Result.emplace_back(InterestingVal, RHSVal.second);
705 return !Result.empty();
709 if (
I->getOpcode() == Instruction::Xor &&
710 isa<ConstantInt>(
I->getOperand(1)) &&
711 cast<ConstantInt>(
I->getOperand(1))->isOne()) {
718 for (
auto &R : Result)
728 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
729 const DataLayout &
DL = BO->getModule()->getDataLayout();
735 for (
const auto &LHSVal : LHSVals) {
741 Result.emplace_back(KC, LHSVal.second);
745 return !Result.empty();
749 if (
CmpInst *Cmp = dyn_cast<CmpInst>(
I)) {
752 Type *CmpType = Cmp->getType();
753 Value *CmpLHS = Cmp->getOperand(0);
754 Value *CmpRHS = Cmp->getOperand(1);
757 PHINode *PN = dyn_cast<PHINode>(CmpLHS);
759 PN = dyn_cast<PHINode>(CmpRHS);
776 if (!isa<Constant>(
RHS))
780 auto LHSInst = dyn_cast<Instruction>(
LHS);
781 if (LHSInst && LHSInst->getParent() == BB)
786 cast<Constant>(
RHS), PredBB, BB,
794 Result.emplace_back(KC, PredBB);
797 return !Result.empty();
802 if (isa<Constant>(CmpRHS) && !CmpType->
isVectorTy()) {
803 Constant *CmpConst = cast<Constant>(CmpRHS);
805 if (!isa<Instruction>(CmpLHS) ||
806 cast<Instruction>(CmpLHS)->
getParent() != BB) {
812 CmpConst,
P, BB, CxtI ? CxtI : Cmp);
817 Result.emplace_back(ResC,
P);
820 return !Result.empty();
827 using namespace PatternMatch;
831 if (isa<ConstantInt>(CmpConst) &&
833 if (!isa<Instruction>(AddLHS) ||
834 cast<Instruction>(AddLHS)->
getParent() != BB) {
840 AddLHS,
P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
846 Pred, cast<ConstantInt>(CmpConst)->getValue());
856 Result.emplace_back(ResC,
P);
859 return !Result.empty();
870 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)
1270 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1277 if (AvailableVal == LoadI)
1279 if (AvailableVal->getType() != LoadI->
getType())
1281 AvailableVal, LoadI->
getType(),
"", LoadI);
1290 if (BBIt != LoadBB->
begin())
1301 AvailablePredsTy AvailablePreds;
1309 if (!PredsScanned.
insert(PredBB).second)
1312 BBIt = PredBB->
end();
1313 unsigned NumScanedInst = 0;
1314 Value *PredAvailable =
nullptr;
1318 "Attempting to CSE volatile or atomic loads");
1328 AA, &IsLoadCSE, &NumScanedInst);
1333 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->
begin() &&
1337 BBIt = SinglePredBB->
end();
1339 Loc, AccessTy, LoadI->
isAtomic(), SinglePredBB, BBIt,
1345 if (!PredAvailable) {
1346 OneUnavailablePred = PredBB;
1351 CSELoads.
push_back(cast<LoadInst>(PredAvailable));
1355 AvailablePreds.emplace_back(PredBB, PredAvailable);
1360 if (AvailablePreds.empty())
return false;
1377 if (PredsScanned.
size() != AvailablePreds.size() &&
1379 for (
auto I = LoadBB->
begin(); &*
I != LoadI; ++
I)
1386 if (PredsScanned.
size() == AvailablePreds.size()+1 &&
1388 UnavailablePred = OneUnavailablePred;
1389 }
else if (PredsScanned.
size() != AvailablePreds.size()) {
1395 for (
const auto &AvailablePred : AvailablePreds)
1396 AvailablePredSet.
insert(AvailablePred.first);
1401 if (isa<IndirectBrInst>(
P->getTerminator()))
1404 if (!AvailablePredSet.
count(
P))
1409 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit,
"thread-pre-split");
1415 if (UnavailablePred) {
1417 "Can't handle critical edge here!");
1427 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 P->getTerminator());
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]++;
1502 auto MostPopular = std::max_element(
1506 return MostPopular->first;
1515 assert(PredBB &&
"Expected a single predecessor");
1517 if (
Constant *Cst = dyn_cast<Constant>(V)) {
1523 if (!
I || (
I->getParent() != BB &&
I->getParent() != PredBB)) {
1529 if (
PHI->getParent() == PredBB)
1530 return dyn_cast<Constant>(
PHI->getIncomingValueForBlock(PredPredBB));
1535 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1536 if (CondCmp->getParent() == BB) {
1556 if (LoopHeaders.count(BB))
1568 "computeValueKnownInPredecessors returned true with no values");
1571 for (
const auto &PredValue : PredValues) {
1573 <<
"': FOUND condition = " << *PredValue.first
1574 <<
" for pred '" << PredValue.second->getName() <<
"'.\n";
1589 for (
const auto &PredValue : PredValues) {
1591 if (!SeenPreds.insert(Pred).second)
1597 if (isa<UndefValue>(Val))
1600 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1601 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->
isZero());
1603 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1604 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1607 &&
"Unexpected terminator");
1608 assert(isa<BlockAddress>(Val) &&
"Expecting a constant blockaddress");
1609 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1613 if (PredToDestList.
empty()) {
1617 if (OnlyDest != DestBB)
1618 OnlyDest = MultipleDestSentinel;
1622 OnlyVal = MultipleVal;
1634 if (PredToDestList.
empty())
1640 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1642 bool SeenFirstBranchToOnlyDest =
false;
1643 std::vector <DominatorTree::UpdateType> Updates;
1646 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1647 SeenFirstBranchToOnlyDest =
true;
1649 SuccBB->removePredecessor(BB,
true);
1658 Term->eraseFromParent();
1659 DTU->applyUpdatesPermissive(Updates);
1660 if (
auto *BPI = getBPI())
1661 BPI->eraseBlock(BB);
1665 if (
auto *CondInst = dyn_cast<Instruction>(
Cond)) {
1666 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1667 CondInst->eraseFromParent();
1675 else if (OnlyVal && OnlyVal != MultipleVal)
1688 if (MostPopularDest == MultipleDestSentinel) {
1693 [&](
const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1694 return LoopHeaders.contains(PredToDest.second);
1697 if (PredToDestList.
empty())
1706 for (
const auto &PredToDest : PredToDestList)
1707 if (PredToDest.second == MostPopularDest) {
1720 if (!MostPopularDest)
1749 if (PredBr->isUnconditional()) {
1750 PredBBs[0] = PredBB;
1774 if (!isa<PHINode>(BB->
front()))
1811 "computeValueKnownInPredecessors returned true with no values");
1815 unsigned NumTrue = 0, NumFalse = 0;
1816 for (
const auto &XorOpValue : XorOpValues) {
1817 if (isa<UndefValue>(XorOpValue.first))
1820 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1828 if (NumTrue > NumFalse)
1830 else if (NumTrue != 0 || NumFalse != 0)
1836 for (
const auto &XorOpValue : XorOpValues) {
1837 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1840 BlocksToFoldInto.
push_back(XorOpValue.second);
1845 if (BlocksToFoldInto.
size() ==
1846 cast<PHINode>(BB->
front()).getNumIncomingValues()) {
1884 Value *
IV = PN.getIncomingValueForBlock(OldPred);
1893 PN.addIncoming(
IV, NewPred);
1909 if (LoopHeaders.erase(SinglePred))
1910 LoopHeaders.insert(BB);
1963 for (
Use &U :
I.uses()) {
1966 if (UserPN->getIncomingBlock(U) == BB)
1968 }
else if (
User->getParent() == BB)
1983 if (UsesToRename.
empty() && DbgValues.
empty())
1985 LLVM_DEBUG(
dbgs() <<
"JT: Renaming non-local uses of: " <<
I <<
"\n");
1994 while (!UsesToRename.
empty())
1996 if (!DbgValues.
empty()) {
2018 auto RetargetDbgValueIfPossible = [&](
Instruction *NewInst) ->
bool {
2019 auto DbgInstruction = dyn_cast<DbgValueInst>(NewInst);
2020 if (!DbgInstruction)
2024 for (
auto DbgOperand : DbgInstruction->location_ops()) {
2025 auto DbgOperandInstruction = dyn_cast<Instruction>(DbgOperand);
2026 if (!DbgOperandInstruction)
2029 auto I = ValueMapping.
find(DbgOperandInstruction);
2030 if (
I != ValueMapping.
end()) {
2032 std::pair<Value *, Value *>(DbgOperand,
I->second));
2036 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2037 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2044 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2047 ValueMapping[PN] = NewPN;
2062 for (; BI != BE; ++BI) {
2064 New->setName(BI->getName());
2065 New->insertInto(NewBB, NewBB->
end());
2066 ValueMapping[&*BI] = New;
2069 if (RetargetDbgValueIfPossible(New))
2073 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2074 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2076 if (
I != ValueMapping.
end())
2077 New->setOperand(i,
I->second);
2081 return ValueMapping;
2138 if (LoopHeaders.count(PredBB))
2148 unsigned ZeroCount = 0;
2149 unsigned OneCount = 0;
2154 if (isa<IndirectBrInst>(
P->getTerminator()))
2156 if (
ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2161 }
else if (CI->isOne()) {
2170 if (ZeroCount == 1) {
2171 PredPredBB = ZeroPred;
2172 }
else if (OneCount == 1) {
2173 PredPredBB = OnePred;
2183 <<
"' - would thread to self!\n");
2189 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2191 bool BBIsHeader = LoopHeaders.count(BB);
2192 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2193 dbgs() <<
" Not threading across "
2194 << (BBIsHeader ?
"loop header BB '" :
"block BB '")
2195 << BB->
getName() <<
"' to dest "
2196 << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2198 <<
"' - it might create an irreducible loop!\n";
2212 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2213 BBCost + PredBBCost > BBDupThreshold) {
2215 <<
"' - Cost is too high: " << PredBBCost
2216 <<
" for PredBB, " << BBCost <<
"for BB\n");
2233 bool HasProfile = doesBlockHaveProfileData(BB);
2234 auto *BFI = getOrCreateBFI(HasProfile);
2235 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2247 assert(BPI &&
"It's expected BPI to exist along with BFI");
2248 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2249 BPI->getEdgeProbability(PredPredBB, PredBB);
2250 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2261 BPI->copyEdgeProbabilities(PredBB, NewBB);
2278 DTU->applyUpdatesPermissive(
2303 <<
"' - would thread to self!\n");
2309 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2311 bool BBIsHeader = LoopHeaders.count(BB);
2312 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2313 dbgs() <<
" Not threading across "
2314 << (BBIsHeader ?
"loop header BB '" :
"block BB '") << BB->
getName()
2315 <<
"' to dest " << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2316 << SuccBB->
getName() <<
"' - it might create an irreducible loop!\n";
2323 if (JumpThreadCost > BBDupThreshold) {
2325 <<
"' - Cost is too high: " << JumpThreadCost <<
"\n");
2339 assert(SuccBB != BB &&
"Don't create an infinite loop");
2341 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2342 "Don't thread across loop headers");
2345 bool HasProfile = doesBlockHaveProfileData(BB);
2346 auto *BFI = getOrCreateBFI(HasProfile);
2347 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2351 if (PredBBs.
size() == 1)
2352 PredBB = PredBBs[0];
2355 <<
" common predecessors.\n");
2356 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2361 <<
"' to '" << SuccBB->
getName()
2362 <<
", across block:\n " << *BB <<
"\n");
2373 assert(BPI &&
"It's expected BPI to exist along with BFI");
2375 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2376 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2415 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2426 const char *Suffix) {
2432 auto *BFI = getBFI();
2434 auto *BPI = getOrCreateBPI(
true);
2435 for (
auto *Pred : Preds)
2436 FreqMap.
insert(std::make_pair(
2437 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2443 std::string NewName = std::string(Suffix) +
".split-lp";
2449 std::vector<DominatorTree::UpdateType> Updates;
2450 Updates.reserve((2 * Preds.size()) + NewBBs.
size());
2451 for (
auto *NewBB : NewBBs) {
2458 NewBBFreq += FreqMap.
lookup(Pred);
2461 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2464 DTU->applyUpdatesPermissive(Updates);
2468bool JumpThreadingPass::doesBlockHaveProfileData(
BasicBlock *BB) {
2479void JumpThreadingPass::updateBlockFreqAndEdgeWeight(
BasicBlock *PredBB,
2486 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2487 "Both BFI & BPI should either be set or unset");
2491 "It's expected to have BFI/BPI when profile info exists");
2497 auto BBOrigFreq =
BFI->getBlockFreq(BB);
2498 auto NewBBFreq =
BFI->getBlockFreq(NewBB);
2500 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2501 BFI->setBlockFreq(BB, BBNewFreq.getFrequency());
2507 auto SuccFreq = (Succ == SuccBB)
2508 ? BB2SuccBBFreq - NewBBFreq
2510 BBSuccFreq.
push_back(SuccFreq.getFrequency());
2514 *std::max_element(BBSuccFreq.
begin(), BBSuccFreq.
end());
2517 if (MaxBBSuccFreq == 0)
2519 {1, static_cast<unsigned>(BBSuccFreq.size())});
2566 if (BBSuccProbs.
size() >= 2 && HasProfile) {
2568 for (
auto Prob : BBSuccProbs)
2573 LLVMContext::MD_prof,
2585 assert(!PredBBs.
empty() &&
"Can't handle an empty set");
2590 if (LoopHeaders.count(BB)) {
2592 <<
"' into predecessor block '" << PredBBs[0]->getName()
2593 <<
"' - it might create an irreducible loop!\n");
2599 if (DuplicationCost > BBDupThreshold) {
2601 <<
"' - Cost is too high: " << DuplicationCost <<
"\n");
2606 std::vector<DominatorTree::UpdateType> Updates;
2608 if (PredBBs.
size() == 1)
2609 PredBB = PredBBs[0];
2612 <<
" common predecessors.\n");
2613 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2620 <<
"' into end of '" << PredBB->
getName()
2621 <<
"' to eliminate branch on phi. Cost: "
2622 << DuplicationCost <<
" block is:" << *BB <<
"\n");
2642 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2646 for (; BI != BB->
end(); ++BI) {
2648 New->insertInto(PredBB, OldPredBranch->
getIterator());
2651 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2652 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2654 if (
I != ValueMapping.
end())
2655 New->setOperand(i,
I->second);
2663 {BB->
getModule()->getDataLayout(), TLI,
nullptr,
nullptr, New})) {
2664 ValueMapping[&*BI] =
IV;
2665 if (!New->mayHaveSideEffects()) {
2666 New->eraseFromParent();
2670 ValueMapping[&*BI] = New;
2674 New->setName(BI->getName());
2676 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2677 if (
BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2690 updateSSA(BB, PredBB, ValueMapping);
2697 OldPredBranch->eraseFromParent();
2698 if (
auto *BPI = getBPI())
2700 DTU->applyUpdatesPermissive(Updates);
2731 BI->applyMergedLocation(PredTerm->
getDebugLoc(), SI->getDebugLoc());
2732 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2740 (TrueWeight + FalseWeight) != 0) {
2743 TrueWeight, TrueWeight + FalseWeight));
2745 FalseWeight, TrueWeight + FalseWeight));
2747 if (
auto *BPI = getBPI())
2751 if (
auto *BFI = getBFI()) {
2752 if ((TrueWeight + FalseWeight) == 0) {
2757 TrueWeight, TrueWeight + FalseWeight);
2758 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2759 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2763 SI->eraseFromParent();
2769 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2771 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2775 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2777 if (!CondPHI || CondPHI->
getParent() != BB)
2827 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2839 CondRHS, Pred, BB, CondCmp);
2842 CondRHS, Pred, BB, CondCmp);
2845 LHSFolds != RHSFolds) {
2881 if (LoopHeaders.count(BB))
2885 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2888 [](
Value *V) { return !isa<ConstantInt>(V); }))
2892 using namespace PatternMatch;
2895 if (SI->getParent() != BB)
2899 return Cond &&
Cond == V &&
Cond->getType()->isIntegerTy(1) && !IsAndOr;
2903 for (
Use &U : PN->uses()) {
2904 if (
ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2907 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2908 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2909 if (
SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2910 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2914 }
else if (
SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2916 if (isUnfoldCandidate(SelectI, U.get())) {
2935 NewPN->
addIncoming(SI->getTrueValue(), Term->getParent());
2937 SI->replaceAllUsesWith(NewPN);
2938 SI->eraseFromParent();
2940 std::vector<DominatorTree::UpdateType> Updates;
2950 DTU->applyUpdatesPermissive(Updates);
2976 using namespace PatternMatch;
2998 if (
auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3019 bool TrueDestIsSafe =
false;
3020 bool FalseDestIsSafe =
false;
3025 TrueDestIsSafe =
true;
3030 FalseDestIsSafe =
true;
3033 if (!TrueDestIsSafe && !FalseDestIsSafe)
3036 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3037 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3043 if (
Cost > BBDupThreshold)
3048 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3049 assert(GuardedBlock &&
"Could not create the guarded block?");
3054 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3055 assert(UnguardedBlock &&
"Could not create the unguarded block?");
3057 << GuardedBlock->
getName() <<
"\n");
3062 for (
auto BI = BB->
begin(); &*BI != AfterGuard; ++BI)
3063 if (!isa<PHINode>(&*BI))
3067 assert(InsertionPoint &&
"Empty block?");
3070 if (!Inst->use_empty()) {
3072 NewPN->
addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3073 NewPN->
addIncoming(GuardedMapping[Inst], GuardedBlock);
3075 Inst->replaceAllUsesWith(NewPN);
3077 Inst->eraseFromParent();
3092template <
typename AnalysisT>
3093typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3094 assert(FAM &&
"Can't run external analysis without FunctionAnalysisManager");
3099 if (!ChangedSinceLastAnalysisUpdate) {
3100 assert(!DTU->hasPendingUpdates() &&
3101 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3105 ChangedSinceLastAnalysisUpdate =
false;
3107 auto PA = getPreservedAnalysis();
3117 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3118 assert((!DTU->hasPostDomTree() ||
3119 DTU->getPostDomTree().verify(
3133 assert(FAM &&
"Can't create BPI without FunctionAnalysisManager");
3141 assert(FAM &&
"Can't create BFI without FunctionAnalysisManager");
3151 auto *Res = getBPI();
3156 BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
3162 auto *Res = getBFI();
3167 BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
static const Function * getParent(const Value *V)
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< bool > PrintLVIAfterJumpThreading("print-lvi-after-jump-threading", cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false), cl::Hidden)
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.
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
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...
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.
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.
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.
bool isConditional() const
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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="", Instruction *InsertBefore=nullptr)
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 * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
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.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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.
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.
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
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
SymbolTableList< Instruction >::iterator insertInto(BasicBlock *ParentBB, SymbolTableList< Instruction >::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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
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)
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
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.
void setIncomingValue(unsigned i, Value *V)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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)
iterator erase(const_iterator CI)
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.
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DominatorTree *DT, 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...
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, AAResults *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 ...
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.
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...
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, AAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
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...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
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().
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...
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
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.
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)
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:...