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>(
252 &DT,
nullptr, DomTreeUpdater::UpdateStrategy::Lazy),
253 std::nullopt, std::nullopt);
261#if defined(EXPENSIVE_CHECKS)
263 DominatorTree::VerificationLevel::Full) &&
264 "DT broken after JumpThreading");
268 "PDT broken after JumpThreading");
271 DominatorTree::VerificationLevel::Fast) &&
272 "DT broken after JumpThreading");
276 "PDT broken after JumpThreading");
279 return getPreservedAnalysis();
286 std::unique_ptr<DomTreeUpdater> DTU_,
287 std::optional<BlockFrequencyInfo *> BFI_,
288 std::optional<BranchProbabilityInfo *> BPI_) {
296 DTU = std::move(DTU_);
301 HasGuards = GuardDecl && !GuardDecl->use_empty();
310 BBDupThreshold = DefaultBBDupThreshold;
315 assert(DTU &&
"DTU isn't passed into JumpThreading before using it.");
316 assert(DTU->hasDomTree() &&
"JumpThreading relies on DomTree to proceed.");
325 bool EverChanged =
false;
329 for (
auto &BB : *
F) {
330 if (Unreachable.
count(&BB))
333 Changed = ChangedSinceLastAnalysisUpdate =
true;
343 if (&BB == &
F->getEntryBlock() || DTU->isBBPendingDeletion(&BB))
350 <<
"' with terminator: " << *BB.getTerminator()
352 LoopHeaders.erase(&BB);
355 Changed = ChangedSinceLastAnalysisUpdate =
true;
361 auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
362 if (BI && BI->isUnconditional()) {
366 BB.getFirstNonPHIOrDbg(
true)->isTerminator() &&
369 !LoopHeaders.count(&BB) && !LoopHeaders.count(Succ) &&
375 Changed = ChangedSinceLastAnalysisUpdate =
true;
379 EverChanged |= Changed;
395 bool Changed =
false;
400 if (
Cond->getParent() == KnownAtEndOfBB)
405 DVR.replaceVariableLocationOp(
Cond, ToVal,
true);
415 Changed |=
I.replaceUsesOfWith(
Cond, ToVal);
417 if (
Cond->use_empty() && !
Cond->mayHaveSideEffects()) {
418 Cond->eraseFromParent();
430 unsigned Threshold) {
431 assert(StopAt->
getParent() == BB &&
"Not an instruction from proper BB?");
436 unsigned PhiCount = 0;
439 if (!isa<PHINode>(&
I)) {
458 if (isa<SwitchInst>(StopAt))
462 if (isa<IndirectBrInst>(StopAt))
473 for (; &*
I != StopAt; ++
I) {
476 if (
Size > Threshold)
481 if (
I->getType()->isTokenTy() &&
I->isUsedOutsideOfBlock(BB))
486 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
487 if (CI->cannotDuplicate() || CI->isConvergent())
501 if (
const CallInst *CI = dyn_cast<CallInst>(
I)) {
502 if (!isa<IntrinsicInst>(CI))
504 else if (!CI->getType()->isVectorTy())
530 for (
const auto &Edge : Edges)
531 LoopHeaders.insert(Edge.second);
544 if (
UndefValue *U = dyn_cast<UndefValue>(Val))
550 return dyn_cast<ConstantInt>(Val);
569 if (!RecursionSet.
insert(V).second)
575 Result.emplace_back(KC, Pred);
577 return !Result.empty();
583 if (!
I ||
I->getParent() != BB) {
588 using namespace PatternMatch;
605 Result.emplace_back(KC,
P);
608 return !Result.empty();
612 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
613 for (
unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
614 Value *InVal = PN->getIncomingValue(i);
616 Result.emplace_back(KC, PN->getIncomingBlock(i));
619 PN->getIncomingBlock(i),
622 Result.emplace_back(KC, PN->getIncomingBlock(i));
626 return !Result.empty();
630 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
631 Value *Source = CI->getOperand(0);
639 for (
auto &Val : Vals)
642 Result.emplace_back(Folded, Val.second);
644 return !Result.empty();
648 Value *Source = FI->getOperand(0);
656 return !Result.empty();
660 if (
I->getType()->getPrimitiveSizeInBits() == 1) {
661 using namespace PatternMatch;
689 for (
const auto &LHSVal : LHSVals)
690 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
691 Result.emplace_back(InterestingVal, LHSVal.second);
692 LHSKnownBBs.
insert(LHSVal.second);
694 for (
const auto &RHSVal : RHSVals)
695 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
698 if (!LHSKnownBBs.
count(RHSVal.second))
699 Result.emplace_back(InterestingVal, RHSVal.second);
702 return !Result.empty();
706 if (
I->getOpcode() == Instruction::Xor &&
707 isa<ConstantInt>(
I->getOperand(1)) &&
708 cast<ConstantInt>(
I->getOperand(1))->isOne()) {
715 for (
auto &R : Result)
725 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
731 for (
const auto &LHSVal : LHSVals) {
737 Result.emplace_back(KC, LHSVal.second);
741 return !Result.empty();
745 if (
CmpInst *Cmp = dyn_cast<CmpInst>(
I)) {
748 Type *CmpType = Cmp->getType();
749 Value *CmpLHS = Cmp->getOperand(0);
750 Value *CmpRHS = Cmp->getOperand(1);
753 PHINode *PN = dyn_cast<PHINode>(CmpLHS);
755 PN = dyn_cast<PHINode>(CmpRHS);
759 if (PN && PN->
getParent() == BB && !LoopHeaders.contains(BB)) {
775 if (!isa<Constant>(
RHS))
779 auto LHSInst = dyn_cast<Instruction>(
LHS);
780 if (LHSInst && LHSInst->getParent() == BB)
785 cast<Constant>(
RHS), PredBB, BB,
793 Result.emplace_back(KC, PredBB);
796 return !Result.empty();
801 if (isa<Constant>(CmpRHS) && !CmpType->
isVectorTy()) {
802 Constant *CmpConst = cast<Constant>(CmpRHS);
804 if (!isa<Instruction>(CmpLHS) ||
805 cast<Instruction>(CmpLHS)->
getParent() != BB) {
811 CmpConst,
P, BB, CxtI ? CxtI : Cmp);
815 Constant *ResC = ConstantInt::get(CmpType, Res);
816 Result.emplace_back(ResC,
P);
819 return !Result.empty();
826 using namespace PatternMatch;
830 if (isa<ConstantInt>(CmpConst) &&
832 if (!isa<Instruction>(AddLHS) ||
833 cast<Instruction>(AddLHS)->
getParent() != BB) {
839 AddLHS,
P, BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
845 Pred, cast<ConstantInt>(CmpConst)->getValue());
855 Result.emplace_back(ResC,
P);
858 return !Result.empty();
869 for (
const auto &LHSVal : LHSVals) {
874 Result.emplace_back(KC, LHSVal.second);
877 return !Result.empty();
887 if ((TrueVal || FalseVal) &&
890 for (
auto &
C : Conds) {
897 KnownCond = CI->isOne();
899 assert(isa<UndefValue>(
Cond) &&
"Unexpected condition value");
903 KnownCond = (TrueVal !=
nullptr);
907 if (
Constant *Val = KnownCond ? TrueVal : FalseVal)
908 Result.emplace_back(Val,
C.second);
911 return !Result.empty();
920 Result.emplace_back(KC, Pred);
923 return !Result.empty();
933 unsigned MinSucc = 0;
936 unsigned MinNumPreds =
pred_size(TestBB);
940 if (NumPreds < MinNumPreds) {
942 MinNumPreds = NumPreds;
964 if (DTU->isBBPendingDeletion(BB) ||
989 if (
BranchInst *BI = dyn_cast<BranchInst>(Terminator)) {
991 if (BI->isUnconditional())
return false;
992 Condition = BI->getCondition();
993 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(Terminator)) {
994 Condition = SI->getCondition();
995 }
else if (
IndirectBrInst *IB = dyn_cast<IndirectBrInst>(Terminator)) {
997 if (IB->getNumSuccessors() == 0)
return false;
998 Condition = IB->getAddress()->stripPointerCasts();
1005 bool ConstantFolded =
false;
1009 if (
Instruction *
I = dyn_cast<Instruction>(Condition)) {
1013 I->replaceAllUsesWith(SimpleVal);
1015 I->eraseFromParent();
1016 Condition = SimpleVal;
1017 ConstantFolded =
true;
1023 auto *FI = dyn_cast<FreezeInst>(Condition);
1024 if (isa<UndefValue>(Condition) ||
1025 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1027 std::vector<DominatorTree::UpdateType> Updates;
1033 if (i == BestSucc)
continue;
1040 <<
"' folding undef terminator: " << *BBTerm <<
'\n');
1045 DTU->applyUpdatesPermissive(Updates);
1047 FI->eraseFromParent();
1060 if (
auto *BPI = getBPI())
1061 BPI->eraseBlock(BB);
1065 Instruction *CondInst = dyn_cast<Instruction>(Condition);
1072 return ConstantFolded;
1076 Value *CondWithoutFreeze = CondInst;
1077 if (
auto *FI = dyn_cast<FreezeInst>(CondInst))
1078 CondWithoutFreeze = FI->getOperand(0);
1080 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(CondWithoutFreeze)) {
1084 if (
Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1086 LVI->
getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1119 Value *SimplifyValue = CondWithoutFreeze;
1121 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1122 if (isa<Constant>(CondCmp->getOperand(1)))
1123 SimplifyValue = CondCmp->getOperand(0);
1127 if (
LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1132 if (
PHINode *PN = dyn_cast<PHINode>(CondInst))
1133 if (PN->getParent() == BB && isa<BranchInst>(BB->
getTerminator()))
1144 PHINode *PN = dyn_cast<PHINode>(CondWithoutFreeze);
1149 if (CondInst->
getOpcode() == Instruction::Xor &&
1163 if (!BI || !BI->isConditional())
1172 auto *FICond = dyn_cast<FreezeInst>(
Cond);
1173 if (FICond && FICond->hasOneUse())
1174 Cond = FICond->getOperand(0);
1185 auto *PBI = dyn_cast<BranchInst>(CurrentPred->
getTerminator());
1186 if (!PBI || !PBI->isConditional())
1188 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1191 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1192 std::optional<bool> Implication =
1197 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1198 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1199 FICond->getOperand(0))
1200 Implication = CondIsTrue;
1204 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1205 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1210 BI->eraseFromParent();
1212 FICond->eraseFromParent();
1215 if (
auto *BPI = getBPI())
1216 BPI->eraseBlock(BB);
1219 CurrentBB = CurrentPred;
1229 if (OpInst->getParent() == BB)
1274 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1281 if (AvailableVal == LoadI)
1283 if (AvailableVal->getType() != LoadI->
getType()) {
1286 cast<Instruction>(AvailableVal)->setDebugLoc(LoadI->
getDebugLoc());
1296 if (BBIt != LoadBB->
begin())
1307 AvailablePredsTy AvailablePreds;
1315 if (!PredsScanned.
insert(PredBB).second)
1318 BBIt = PredBB->
end();
1319 unsigned NumScanedInst = 0;
1320 Value *PredAvailable =
nullptr;
1324 "Attempting to CSE volatile or atomic loads");
1334 &BatchAA, &IsLoadCSE, &NumScanedInst);
1339 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->
begin() &&
1343 BBIt = SinglePredBB->
end();
1345 Loc, AccessTy, LoadI->
isAtomic(), SinglePredBB, BBIt,
1351 if (!PredAvailable) {
1352 OneUnavailablePred = PredBB;
1357 CSELoads.
push_back(cast<LoadInst>(PredAvailable));
1361 AvailablePreds.emplace_back(PredBB, PredAvailable);
1366 if (AvailablePreds.empty())
return false;
1383 if (PredsScanned.
size() != AvailablePreds.size() &&
1385 for (
auto I = LoadBB->
begin(); &*
I != LoadI; ++
I)
1392 if (PredsScanned.
size() == AvailablePreds.size()+1 &&
1394 UnavailablePred = OneUnavailablePred;
1395 }
else if (PredsScanned.
size() != AvailablePreds.size()) {
1401 for (
const auto &AvailablePred : AvailablePreds)
1402 AvailablePredSet.
insert(AvailablePred.first);
1407 if (isa<IndirectBrInst>(
P->getTerminator()))
1410 if (!AvailablePredSet.
count(
P))
1415 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit,
"thread-pre-split");
1421 if (UnavailablePred) {
1423 "Can't handle critical edge here!");
1433 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1449 AvailablePredsTy::iterator
I =
1452 assert(
I != AvailablePreds.end() &&
I->first ==
P &&
1453 "Didn't find entry for predecessor!");
1459 Value *&PredV =
I->second;
1462 PredV, LoadI->
getType(),
"",
P->getTerminator()->getIterator());
1467 for (
LoadInst *PredLoadI : CSELoads) {
1485 assert(!PredToDestList.empty());
1497 DestPopularity[
nullptr] = 0;
1499 DestPopularity[SuccBB] = 0;
1501 for (
const auto &PredToDest : PredToDestList)
1502 if (PredToDest.second)
1503 DestPopularity[PredToDest.second]++;
1509 return MostPopular->first;
1519 assert(PredBB &&
"Expected a single predecessor");
1521 if (
Constant *Cst = dyn_cast<Constant>(V)) {
1527 if (!
I || (
I->getParent() != BB &&
I->getParent() != PredBB)) {
1533 if (
PHI->getParent() == PredBB)
1534 return dyn_cast<Constant>(
PHI->getIncomingValueForBlock(PredPredBB));
1539 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1540 if (CondCmp->getParent() == BB) {
1561 if (LoopHeaders.count(BB))
1573 "computeValueKnownInPredecessors returned true with no values");
1576 for (
const auto &PredValue : PredValues) {
1578 <<
"': FOUND condition = " << *PredValue.first
1579 <<
" for pred '" << PredValue.second->getName() <<
"'.\n";
1594 for (
const auto &PredValue : PredValues) {
1596 if (!SeenPreds.insert(Pred).second)
1602 if (isa<UndefValue>(Val))
1605 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1606 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->
isZero());
1608 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1609 DestBB = SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1612 &&
"Unexpected terminator");
1613 assert(isa<BlockAddress>(Val) &&
"Expecting a constant blockaddress");
1614 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1618 if (PredToDestList.
empty()) {
1622 if (OnlyDest != DestBB)
1623 OnlyDest = MultipleDestSentinel;
1627 OnlyVal = MultipleVal;
1639 if (PredToDestList.
empty())
1645 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1647 bool SeenFirstBranchToOnlyDest =
false;
1648 std::vector <DominatorTree::UpdateType> Updates;
1651 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1652 SeenFirstBranchToOnlyDest =
true;
1654 SuccBB->removePredecessor(BB,
true);
1664 Term->eraseFromParent();
1665 DTU->applyUpdatesPermissive(Updates);
1666 if (
auto *BPI = getBPI())
1667 BPI->eraseBlock(BB);
1671 if (
auto *CondInst = dyn_cast<Instruction>(
Cond)) {
1672 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1673 CondInst->eraseFromParent();
1681 else if (OnlyVal && OnlyVal != MultipleVal)
1694 if (MostPopularDest == MultipleDestSentinel) {
1699 [&](
const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1700 return LoopHeaders.contains(PredToDest.second);
1703 if (PredToDestList.
empty())
1712 for (
const auto &PredToDest : PredToDestList)
1713 if (PredToDest.second == MostPopularDest) {
1726 if (!MostPopularDest)
1755 if (PredBr->isUnconditional()) {
1756 PredBBs[0] = PredBB;
1780 if (!isa<PHINode>(BB->
front()))
1817 "computeValueKnownInPredecessors returned true with no values");
1821 unsigned NumTrue = 0, NumFalse = 0;
1822 for (
const auto &XorOpValue : XorOpValues) {
1823 if (isa<UndefValue>(XorOpValue.first))
1826 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1834 if (NumTrue > NumFalse)
1836 else if (NumTrue != 0 || NumFalse != 0)
1842 for (
const auto &XorOpValue : XorOpValues) {
1843 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1846 BlocksToFoldInto.
push_back(XorOpValue.second);
1851 if (BlocksToFoldInto.
size() ==
1852 cast<PHINode>(BB->
front()).getNumIncomingValues()) {
1890 Value *
IV = PN.getIncomingValueForBlock(OldPred);
1899 PN.addIncoming(
IV, NewPred);
1915 if (LoopHeaders.erase(SinglePred))
1916 LoopHeaders.insert(BB);
1969 for (
Use &U :
I.uses()) {
1972 if (UserPN->getIncomingBlock(U) == BB)
1974 }
else if (
User->getParent() == BB)
1990 if (UsesToRename.
empty() && DbgValues.
empty() && DbgVariableRecords.
empty())
1992 LLVM_DEBUG(
dbgs() <<
"JT: Renaming non-local uses of: " <<
I <<
"\n");
2001 while (!UsesToRename.
empty())
2003 if (!DbgValues.
empty() || !DbgVariableRecords.
empty()) {
2007 DbgVariableRecords.
clear();
2028 auto RetargetDbgValueIfPossible = [&](
Instruction *NewInst) ->
bool {
2029 auto DbgInstruction = dyn_cast<DbgValueInst>(NewInst);
2030 if (!DbgInstruction)
2034 for (
auto DbgOperand : DbgInstruction->location_ops()) {
2035 auto DbgOperandInstruction = dyn_cast<Instruction>(DbgOperand);
2036 if (!DbgOperandInstruction)
2039 auto I = ValueMapping.
find(DbgOperandInstruction);
2040 if (
I != ValueMapping.
end()) {
2042 std::pair<Value *, Value *>(DbgOperand,
I->second));
2046 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2047 DbgInstruction->replaceVariableLocationOp(OldOp, MappedOp);
2055 for (
auto *
Op : DVR->location_ops()) {
2060 auto I = ValueMapping.
find(OpInst);
2061 if (
I != ValueMapping.
end())
2062 OperandsToRemap.
insert({OpInst,
I->second});
2065 for (
auto &[OldOp, MappedOp] : OperandsToRemap)
2066 DVR->replaceVariableLocationOp(OldOp, MappedOp);
2074 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2077 ValueMapping[PN] = NewPN;
2092 RetargetDbgVariableRecordIfPossible(&DVR);
2098 for (; BI != BE; ++BI) {
2100 New->setName(BI->getName());
2101 New->insertInto(NewBB, NewBB->
end());
2102 ValueMapping[&*BI] = New;
2105 CloneAndRemapDbgInfo(New, &*BI);
2107 if (RetargetDbgValueIfPossible(New))
2111 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2112 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2114 if (
I != ValueMapping.
end())
2115 New->setOperand(i,
I->second);
2121 if (BE != RangeBB->
end() && BE->hasDbgRecords()) {
2127 RetargetDbgVariableRecordIfPossible(&DVR);
2187 if (LoopHeaders.count(PredBB))
2197 unsigned ZeroCount = 0;
2198 unsigned OneCount = 0;
2204 if (isa<IndirectBrInst>(
P->getTerminator()))
2206 if (
ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2211 }
else if (CI->isOne()) {
2220 if (ZeroCount == 1) {
2221 PredPredBB = ZeroPred;
2222 }
else if (OneCount == 1) {
2223 PredPredBB = OnePred;
2233 <<
"' - would thread to self!\n");
2239 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2241 bool BBIsHeader = LoopHeaders.count(BB);
2242 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2243 dbgs() <<
" Not threading across "
2244 << (BBIsHeader ?
"loop header BB '" :
"block BB '")
2245 << BB->
getName() <<
"' to dest "
2246 << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2248 <<
"' - it might create an irreducible loop!\n";
2262 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2263 BBCost + PredBBCost > BBDupThreshold) {
2265 <<
"' - Cost is too high: " << PredBBCost
2266 <<
" for PredBB, " << BBCost <<
"for BB\n");
2283 bool HasProfile = doesBlockHaveProfileData(BB);
2284 auto *BFI = getOrCreateBFI(HasProfile);
2285 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2297 assert(BPI &&
"It's expected BPI to exist along with BFI");
2298 auto NewBBFreq = BFI->getBlockFreq(PredPredBB) *
2299 BPI->getEdgeProbability(PredPredBB, PredBB);
2300 BFI->setBlockFreq(NewBB, NewBBFreq);
2312 BPI->copyEdgeProbabilities(PredBB, NewBB);
2329 DTU->applyUpdatesPermissive(
2354 <<
"' - would thread to self!\n");
2360 if (LoopHeaders.count(BB) || LoopHeaders.count(SuccBB)) {
2362 bool BBIsHeader = LoopHeaders.count(BB);
2363 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2364 dbgs() <<
" Not threading across "
2365 << (BBIsHeader ?
"loop header BB '" :
"block BB '") << BB->
getName()
2366 <<
"' to dest " << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2367 << SuccBB->
getName() <<
"' - it might create an irreducible loop!\n";
2374 if (JumpThreadCost > BBDupThreshold) {
2376 <<
"' - Cost is too high: " << JumpThreadCost <<
"\n");
2390 assert(SuccBB != BB &&
"Don't create an infinite loop");
2392 assert(!LoopHeaders.count(BB) && !LoopHeaders.count(SuccBB) &&
2393 "Don't thread across loop headers");
2396 bool HasProfile = doesBlockHaveProfileData(BB);
2397 auto *BFI = getOrCreateBFI(HasProfile);
2398 auto *BPI = getOrCreateBPI(BFI !=
nullptr);
2402 if (PredBBs.
size() == 1)
2403 PredBB = PredBBs[0];
2406 <<
" common predecessors.\n");
2407 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2412 <<
"' to '" << SuccBB->
getName()
2413 <<
", across block:\n " << *BB <<
"\n");
2424 assert(BPI &&
"It's expected BPI to exist along with BFI");
2426 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
2427 BFI->setBlockFreq(NewBB, NewBBFreq);
2467 updateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB, BFI, BPI, HasProfile);
2478 const char *Suffix) {
2484 auto *BFI = getBFI();
2486 auto *BPI = getOrCreateBPI(
true);
2487 for (
auto *Pred : Preds)
2488 FreqMap.
insert(std::make_pair(
2489 Pred, BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB)));
2495 std::string NewName = std::string(Suffix) +
".split-lp";
2501 std::vector<DominatorTree::UpdateType> Updates;
2502 Updates.reserve((2 * Preds.size()) + NewBBs.
size());
2503 for (
auto *NewBB : NewBBs) {
2510 NewBBFreq += FreqMap.
lookup(Pred);
2513 BFI->setBlockFreq(NewBB, NewBBFreq);
2516 DTU->applyUpdatesPermissive(Updates);
2520bool JumpThreadingPass::doesBlockHaveProfileData(
BasicBlock *BB) {
2531void JumpThreadingPass::updateBlockFreqAndEdgeWeight(
BasicBlock *PredBB,
2538 assert(((BFI && BPI) || (!BFI && !BFI)) &&
2539 "Both BFI & BPI should either be set or unset");
2543 "It's expected to have BFI/BPI when profile info exists");
2549 auto BBOrigFreq =
BFI->getBlockFreq(BB);
2550 auto NewBBFreq =
BFI->getBlockFreq(NewBB);
2552 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2553 BFI->setBlockFreq(BB, BBNewFreq);
2559 auto SuccFreq = (Succ == SuccBB)
2560 ? BB2SuccBBFreq - NewBBFreq
2562 BBSuccFreq.
push_back(SuccFreq.getFrequency());
2568 if (MaxBBSuccFreq == 0)
2570 {1, static_cast<unsigned>(BBSuccFreq.size())});
2617 if (BBSuccProbs.
size() >= 2 && HasProfile) {
2619 for (
auto Prob : BBSuccProbs)
2634 assert(!PredBBs.
empty() &&
"Can't handle an empty set");
2639 if (LoopHeaders.count(BB)) {
2641 <<
"' into predecessor block '" << PredBBs[0]->getName()
2642 <<
"' - it might create an irreducible loop!\n");
2648 if (DuplicationCost > BBDupThreshold) {
2650 <<
"' - Cost is too high: " << DuplicationCost <<
"\n");
2655 std::vector<DominatorTree::UpdateType> Updates;
2657 if (PredBBs.
size() == 1)
2658 PredBB = PredBBs[0];
2661 <<
" common predecessors.\n");
2662 PredBB = splitBlockPreds(BB, PredBBs,
".thr_comm");
2669 <<
"' into end of '" << PredBB->
getName()
2670 <<
"' to eliminate branch on phi. Cost: "
2671 << DuplicationCost <<
" block is:" << *BB <<
"\n");
2691 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2695 for (; BI != BB->
end(); ++BI) {
2697 New->insertInto(PredBB, OldPredBranch->
getIterator());
2700 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2701 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(i))) {
2703 if (
I != ValueMapping.
end())
2704 New->setOperand(i,
I->second);
2716 ValueMapping[&*BI] =
IV;
2717 if (!New->mayHaveSideEffects()) {
2718 New->eraseFromParent();
2725 ValueMapping[&*BI] = New;
2729 New->setName(BI->getName());
2731 New->cloneDebugInfoFrom(&*BI);
2733 for (
unsigned i = 0, e = New->getNumOperands(); i != e; ++i)
2734 if (
BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(i)))
2755 if (
auto *BPI = getBPI())
2757 DTU->applyUpdatesPermissive(Updates);
2788 BI->applyMergedLocation(PredTerm->
getDebugLoc(), SI->getDebugLoc());
2789 BI->copyMetadata(*SI, {LLVMContext::MD_prof});
2797 (TrueWeight + FalseWeight) != 0) {
2800 TrueWeight, TrueWeight + FalseWeight));
2802 FalseWeight, TrueWeight + FalseWeight));
2804 if (
auto *BPI = getBPI())
2808 if (
auto *BFI = getBFI()) {
2809 if ((TrueWeight + FalseWeight) == 0) {
2814 TrueWeight, TrueWeight + FalseWeight);
2815 auto NewBBFreq = BFI->getBlockFreq(Pred) * PredToNewBBProb;
2816 BFI->setBlockFreq(NewBB, NewBBFreq);
2820 SI->eraseFromParent();
2826 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2828 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2832 PHINode *CondPHI = dyn_cast<PHINode>(SI->getCondition());
2834 if (!CondPHI || CondPHI->
getParent() != BB)
2884 if (!SI || SI->getParent() != Pred || !SI->hasOneUse())
2896 CondRHS, Pred, BB, CondCmp);
2899 CondRHS, Pred, BB, CondCmp);
2902 LHSFolds != RHSFolds) {
2938 if (LoopHeaders.count(BB))
2942 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2945 [](
Value *V) { return !isa<ConstantInt>(V); }))
2949 using namespace PatternMatch;
2952 if (SI->getParent() != BB)
2956 return Cond &&
Cond == V &&
Cond->getType()->isIntegerTy(1) && !IsAndOr;
2960 for (
Use &U : PN->uses()) {
2961 if (
ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2964 if (Cmp->getParent() == BB && Cmp->hasOneUse() &&
2965 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2966 if (
SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2967 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2971 }
else if (
SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2973 if (isUnfoldCandidate(SelectI, U.get())) {
2992 NewPN->
addIncoming(SI->getTrueValue(), Term->getParent());
2995 SI->replaceAllUsesWith(NewPN);
2996 SI->eraseFromParent();
2998 std::vector<DominatorTree::UpdateType> Updates;
3008 DTU->applyUpdatesPermissive(Updates);
3034 using namespace PatternMatch;
3056 if (
auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
3077 bool TrueDestIsSafe =
false;
3078 bool FalseDestIsSafe =
false;
3083 TrueDestIsSafe =
true;
3088 FalseDestIsSafe =
true;
3091 if (!TrueDestIsSafe && !FalseDestIsSafe)
3094 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3095 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3101 if (
Cost > BBDupThreshold)
3106 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3107 assert(GuardedBlock &&
"Could not create the guarded block?");
3112 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3113 assert(UnguardedBlock &&
"Could not create the unguarded block?");
3115 << GuardedBlock->
getName() <<
"\n");
3120 for (
auto BI = BB->
begin(); &*BI != AfterGuard; ++BI)
3121 if (!isa<PHINode>(&*BI))
3125 assert(InsertionPoint != BB->
end() &&
"Empty block?");
3128 if (!Inst->use_empty()) {
3130 NewPN->
addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3131 NewPN->
addIncoming(GuardedMapping[Inst], GuardedBlock);
3134 Inst->replaceAllUsesWith(NewPN);
3136 Inst->dropDbgRecords();
3137 Inst->eraseFromParent();
3152template <
typename AnalysisT>
3153typename AnalysisT::Result *JumpThreadingPass::runExternalAnalysis() {
3154 assert(FAM &&
"Can't run external analysis without FunctionAnalysisManager");
3159 if (!ChangedSinceLastAnalysisUpdate) {
3160 assert(!DTU->hasPendingUpdates() &&
3161 "Lost update of 'ChangedSinceLastAnalysisUpdate'?");
3165 ChangedSinceLastAnalysisUpdate =
false;
3167 auto PA = getPreservedAnalysis();
3177 assert(DTU->getDomTree().verify(DominatorTree::VerificationLevel::Fast));
3178 assert((!DTU->hasPostDomTree() ||
3179 DTU->getPostDomTree().verify(
3193 assert(FAM &&
"Can't create BPI without FunctionAnalysisManager");
3201 assert(FAM &&
"Can't create BFI without FunctionAnalysisManager");
3211 auto *Res = getBPI();
3216 BPI = runExternalAnalysis<BranchProbabilityAnalysis>();
3222 auto *Res = getBFI();
3227 BFI = runExternalAnalysis<BlockFrequencyAnalysis>();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
static const Function * getParent(const Value *V)
BlockVerifier::State From
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...
static cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)
static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
static cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)
static unsigned getJumpThreadDuplicationCost(const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction...
static void addPHINodeEntriesForMappedBlock(BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, ValueToValueMapTy &ValueMap)
addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
findMostPopularDest - The specified list contains multiple possible threadable destinations.
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
static cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
static bool hasAddressTakenAndUsed(BasicBlock *BB)
See the comments on JumpThreadingPass.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static const uint32_t IV[8]
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
DbgMarker * createMarker(Instruction *I)
Attach a DbgMarker to the given instruction.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator const_iterator
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
DbgMarker * getMarker(InstListType::iterator It)
Return the DbgMarker for the position given by It, so that DbgRecords can be inserted there.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isLandingPad() const
Return true if this basic block is a landing pad.
bool isEHPad() const
Return true if this basic block is an exception handling block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
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.
bool isConditional() const
unsigned getNumSuccessors() const
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
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="", InsertPosition 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 * getNot(Constant *C)
This is the shared class of boolean and integer constants.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Per-instruction record of debug-info.
iterator_range< simple_ilist< DbgRecord >::iterator > cloneDebugInfoFrom(DbgMarker *From, std::optional< simple_ilist< DbgRecord >::iterator > FromHere, bool InsertAtHead=false)
Clone all DbgMarkers from From into this marker.
const BasicBlock * getParent() const
This represents the llvm.dbg.value instruction.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
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.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
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.
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.
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.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
bool isSpecialTerminator() const
InstListType::iterator insertInto(BasicBlock *ParentBB, InstListType::iterator It)
Inserts an unlinked instruction into ParentBB at position It and returns the iterator of the inserted...
A wrapper class for inspecting calls to intrinsic functions.
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, ValueToValueMapTy &ValueMapping)
Update the SSA form.
bool computeValueKnownInPredecessors(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
JumpThreadingPass(int T=-1)
void cloneInstructions(ValueToValueMapTy &ValueMapping, BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool runImpl(Function &F, FunctionAnalysisManager *FAM, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, std::unique_ptr< DomTreeUpdater > DTU, std::optional< BlockFrequencyInfo * > BFI, std::optional< BranchProbabilityInfo * > BPI)
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond, const DataLayout &DL)
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
bool computeValueKnownInPredecessorsImpl(Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, jumpthreading::ConstantPreference Preference, SmallPtrSet< Value *, 4 > &RecursionSet, Instruction *CxtI=nullptr)
computeValueKnownInPredecessors - Given a basic block BB and a value V, see if we can infer that the ...
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
DomTreeUpdater * getDomTreeUpdater() const
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
bool processImpliedCondition(BasicBlock *BB)
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
void threadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
threadEdge - We have decided that it is safe and profitable to factor the blocks in PredBBs to one pr...
bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI)
Try to propagate the guard from BB which is the lower block of a diamond to one of its branches,...
This is an important class for using LLVM in a threaded context.
Analysis to compute lazy value information.
This pass computes, caches, and vends lazy value constraint information.
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc)
Inform the analysis cache that we have threaded an edge from PredBB to OldSucc to be from PredBB to N...
Tristate
This is used to return true/false/dunno results.
Constant * getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value is known to be a constant on the specified edge.
ConstantRange getConstantRangeOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Return the ConstantRage constraint that is known to hold for the specified value on the specified edg...
Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, BasicBlock *FromBB, BasicBlock *ToBB, Instruction *CxtI=nullptr)
Determine whether the specified value comparison with a constant is known to be true or false on the ...
Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, Instruction *CxtI, bool UseBlockValue)
Determine whether the specified value comparison with a constant is known to be true or false at the ...
Constant * getConstant(Value *V, Instruction *CxtI)
Determine whether the specified value is known to be a constant at the specified instruction.
void forgetValue(Value *V)
Remove information related to this value from the cache.
An instruction for reading from memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
This class implements a map that also provides access to all stored values in a deterministic order.
Representation for a specific memory location.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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 PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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.
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
@ C
The default llvm calling convention, compatible with C.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
pred_iterator pred_end(BasicBlock *BB)
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
auto successors(const MachineBasicBlock *BB)
MDNode * getBranchWeightMDNode(const Instruction &I)
Get the branch weights metadata node.
Value * findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy, bool AtLeastAtomic, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan, BatchAAResults *AA, bool *IsLoadCSE, unsigned *NumScanedInst)
Scan backwards to see if we have the value of the given pointer available locally within a small numb...
void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)
Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Value * FindAvailableLoadedValue(LoadInst *Load, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan=DefMaxInstsToScan, BatchAAResults *AA=nullptr, bool *IsLoadCSE=nullptr, unsigned *NumScanedInst=nullptr)
Scan backwards to see if we have the value of the given load available locally within a small number ...
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
pred_iterator pred_begin(BasicBlock *BB)
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
auto reverse(ContainerTy &&C)
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
bool hasValidBranchWeightMD(const Instruction &I)
Checks if an instructions has valid Branch Weight Metadata.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)
Duplicate the specified list of noalias decl scopes.
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
void SplitLandingPadPredecessors(BasicBlock *OrigBB, ArrayRef< BasicBlock * > Preds, const char *Suffix, const char *Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method transforms the landing pad, OrigBB, by introducing two new basic blocks into the function...
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)
This method introduces at least one new basic block into the function and moves some of the predecess...
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)
Adapt the metadata for the specified instruction according to the provided mapping.
auto max_element(R &&Range)
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
unsigned pred_size(const MachineBasicBlock *BB)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Function object to check whether the second component of a container supported by std::get (like std:...