Go to the documentation of this file.
82 using namespace jumpthreading;
84 #define DEBUG_TYPE "jump-threading"
86 STATISTIC(NumThreads,
"Number of jumps threaded");
87 STATISTIC(NumFolds,
"Number of terminators folded");
88 STATISTIC(NumDupes,
"Number of branch blocks duplicated to eliminate phi");
92 cl::desc(
"Max block size to duplicate for jump threading"),
97 "jump-threading-implication-search-threshold",
98 cl::desc(
"The number of predecessors to search for a stronger "
99 "condition to use to thread over a weaker condition"),
103 "print-lvi-after-jump-threading",
104 cl::desc(
"Print the LazyValueInfo cache after JumpThreading"),
cl::init(
false),
108 "jump-threading-across-loop-headers",
109 cl::desc(
"Allow JumpThreading to thread across loop headers, for testing"),
161 "Jump Threading",
false,
false)
171 return new JumpThreading(Threshold);
214 BranchInst *CondBr = dyn_cast<BranchInst>(
BB->getTerminator());
222 if (TrueWeight + FalseWeight == 0)
230 auto GetPredOutEdge =
232 BasicBlock *PhiBB) -> std::pair<BasicBlock *, BasicBlock *> {
233 auto *PredBB = IncomingBB;
234 auto *SuccBB = PhiBB;
237 BranchInst *PredBr = dyn_cast<BranchInst>(PredBB->getTerminator());
239 return {PredBB, SuccBB};
241 auto *SinglePredBB = PredBB->getSinglePredecessor();
243 return {
nullptr,
nullptr};
247 if (Visited.
count(SinglePredBB))
248 return {
nullptr,
nullptr};
251 PredBB = SinglePredBB;
264 TrueWeight, TrueWeight + FalseWeight)
266 FalseWeight, TrueWeight + FalseWeight));
269 if (!PredOutEdge.first)
277 uint64_t PredTrueWeight, PredFalseWeight;
308 auto TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
312 auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
313 auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
314 auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
315 auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
317 std::unique_ptr<BlockFrequencyInfo>
BFI;
318 std::unique_ptr<BranchProbabilityInfo> BPI;
319 if (
F.hasProfileData()) {
325 bool Changed = Impl.
runImpl(
F, TLI,
TTI, LVI,
AA, &DTU,
F.hasProfileData(),
328 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
329 LVI->printLVI(
F, DTU.getDomTree(),
dbgs());
346 std::unique_ptr<BlockFrequencyInfo>
BFI;
347 std::unique_ptr<BranchProbabilityInfo> BPI;
348 if (
F.hasProfileData()) {
354 bool Changed =
runImpl(
F, &TLI, &
TTI, &LVI, &
AA, &DTU,
F.hasProfileData(),
358 dbgs() <<
"LVI for function '" <<
F.getName() <<
"':\n";
359 LVI.printLVI(
F, DTU.getDomTree(),
dbgs());
373 bool HasProfileData_,
374 std::unique_ptr<BlockFrequencyInfo> BFI_,
375 std::unique_ptr<BranchProbabilityInfo> BPI_) {
376 LLVM_DEBUG(
dbgs() <<
"Jump threading on function '" <<
F.getName() <<
"'\n");
386 HasProfileData = HasProfileData_;
387 auto *GuardDecl =
F.getParent()->getFunction(
389 HasGuards = GuardDecl && !GuardDecl->use_empty();
390 if (HasProfileData) {
399 else if (
F.hasFnAttribute(Attribute::MinSize))
402 BBDupThreshold = DefaultBBDupThreshold;
407 assert(DTU &&
"DTU isn't passed into JumpThreading before using it.");
408 assert(DTU->hasDomTree() &&
"JumpThreading relies on DomTree to proceed.");
417 bool EverChanged =
false;
424 while (processBlock(&
BB))
435 if (&
BB == &
F.getEntryBlock() || DTU->isBBPendingDeletion(&
BB))
442 <<
"' with terminator: " << *
BB.getTerminator()
444 LoopHeaders.erase(&
BB);
445 LVI->eraseBlock(&
BB);
453 auto *BI = dyn_cast<BranchInst>(
BB.getTerminator());
454 if (BI && BI->isUnconditional()) {
458 BB.getFirstNonPHIOrDbg(
true)->isTerminator() &&
461 !LoopHeaders.count(&
BB) && !LoopHeaders.count(Succ) &&
466 LVI->eraseBlock(&
BB);
471 EverChanged |= Changed;
487 bool Changed =
false;
492 if (
Cond->getParent() == KnownAtEndOfBB)
503 Changed |=
I.replaceUsesOfWith(
Cond, ToVal);
505 if (
Cond->use_empty() && !
Cond->mayHaveSideEffects()) {
506 Cond->eraseFromParent();
518 unsigned Threshold) {
527 if (
BB->getTerminator() == StopAt) {
531 if (isa<SwitchInst>(StopAt))
535 if (isa<IndirectBrInst>(StopAt))
546 for (; &*
I != StopAt; ++
I) {
549 if (Size > Threshold)
554 if (
I->getType()->isTokenTy() &&
I->isUsedOutsideOfBlock(
BB))
559 if (
const CallInst *CI = dyn_cast<CallInst>(
I))
560 if (CI->cannotDuplicate() || CI->isConvergent())
574 if (
const CallInst *CI = dyn_cast<CallInst>(
I)) {
575 if (!isa<IntrinsicInst>(CI))
577 else if (!CI->getType()->isVectorTy())
582 return Size > Bonus ? Size - Bonus : 0;
603 for (
const auto &Edge : Edges)
604 LoopHeaders.insert(Edge.second);
617 if (
UndefValue *U = dyn_cast<UndefValue>(Val))
623 return dyn_cast<ConstantInt>(Val);
640 if (!RecursionSet.
insert(V).second)
646 Result.emplace_back(KC, Pred);
648 return !Result.empty();
654 if (!
I ||
I->getParent() !=
BB) {
671 Constant *PredCst = LVI->getConstantOnEdge(V,
P,
BB, CxtI);
673 Result.emplace_back(KC,
P);
676 return !Result.empty();
680 if (
PHINode *PN = dyn_cast<PHINode>(
I)) {
681 for (
unsigned i = 0,
e = PN->getNumIncomingValues();
i !=
e; ++
i) {
682 Value *InVal = PN->getIncomingValue(
i);
684 Result.emplace_back(KC, PN->getIncomingBlock(
i));
686 Constant *CI = LVI->getConstantOnEdge(InVal,
687 PN->getIncomingBlock(
i),
690 Result.emplace_back(KC, PN->getIncomingBlock(
i));
694 return !Result.empty();
698 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
706 for (
auto &R : Result)
721 return !Result.empty();
725 if (
I->getType()->getPrimitiveSizeInBits() == 1) {
726 using namespace PatternMatch;
736 computeValueKnownInPredecessorsImpl(Op0,
BB, LHSVals,
WantInteger,
738 computeValueKnownInPredecessorsImpl(Op1,
BB, RHSVals,
WantInteger,
741 if (LHSVals.empty() && RHSVals.empty())
754 for (
const auto &LHSVal : LHSVals)
755 if (LHSVal.first == InterestingVal || isa<UndefValue>(LHSVal.first)) {
756 Result.emplace_back(InterestingVal, LHSVal.second);
757 LHSKnownBBs.
insert(LHSVal.second);
759 for (
const auto &RHSVal : RHSVals)
760 if (RHSVal.first == InterestingVal || isa<UndefValue>(RHSVal.first)) {
763 if (!LHSKnownBBs.
count(RHSVal.second))
764 Result.emplace_back(InterestingVal, RHSVal.second);
767 return !Result.empty();
771 if (
I->getOpcode() == Instruction::Xor &&
772 isa<ConstantInt>(
I->getOperand(1)) &&
773 cast<ConstantInt>(
I->getOperand(1))->isOne()) {
774 computeValueKnownInPredecessorsImpl(
I->getOperand(0),
BB, Result,
780 for (
auto &R : Result)
790 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
792 computeValueKnownInPredecessorsImpl(BO->getOperand(0),
BB, LHSVals,
796 for (
const auto &LHSVal : LHSVals) {
801 Result.emplace_back(KC, LHSVal.second);
805 return !Result.empty();
809 if (
CmpInst *Cmp = dyn_cast<CmpInst>(
I)) {
812 Type *CmpType = Cmp->getType();
813 Value *CmpLHS = Cmp->getOperand(0);
814 Value *CmpRHS = Cmp->getOperand(1);
817 PHINode *PN = dyn_cast<PHINode>(CmpLHS);
819 PN = dyn_cast<PHINode>(CmpRHS);
836 if (!isa<Constant>(
RHS))
840 auto LHSInst = dyn_cast<Instruction>(
LHS);
841 if (LHSInst && LHSInst->getParent() ==
BB)
845 ResT = LVI->getPredicateOnEdge(Pred,
LHS,
846 cast<Constant>(
RHS), PredBB,
BB,
854 Result.emplace_back(KC, PredBB);
857 return !Result.empty();
862 if (isa<Constant>(CmpRHS) && !CmpType->
isVectorTy()) {
863 Constant *CmpConst = cast<Constant>(CmpRHS);
865 if (!isa<Instruction>(CmpLHS) ||
871 LVI->getPredicateOnEdge(Pred, CmpLHS,
872 CmpConst,
P,
BB, CxtI ? CxtI : Cmp);
877 Result.emplace_back(ResC,
P);
880 return !Result.empty();
887 using namespace PatternMatch;
891 if (isa<ConstantInt>(CmpConst) &&
893 if (!isa<Instruction>(AddLHS) ||
900 AddLHS,
P,
BB, CxtI ? CxtI : cast<Instruction>(CmpLHS));
906 Pred, cast<ConstantInt>(CmpConst)->getValue());
916 Result.emplace_back(ResC,
P);
919 return !Result.empty();
927 computeValueKnownInPredecessorsImpl(
I->getOperand(0),
BB, LHSVals,
930 for (
const auto &LHSVal : LHSVals) {
934 Result.emplace_back(KC, LHSVal.second);
937 return !Result.empty();
948 computeValueKnownInPredecessorsImpl(
SI->getCondition(),
BB, Conds,
950 for (
auto &
C : Conds) {
957 KnownCond = CI->isOne();
959 assert(isa<UndefValue>(
Cond) &&
"Unexpected condition value");
963 KnownCond = (
TrueVal !=
nullptr);
968 Result.emplace_back(Val,
C.second);
971 return !Result.empty();
977 Constant *CI = LVI->getConstant(V, CxtI);
980 Result.emplace_back(KC, Pred);
983 return !Result.empty();
993 unsigned MinSucc = 0;
996 unsigned MinNumPreds =
pred_size(TestBB);
1000 if (NumPreds < MinNumPreds) {
1002 MinNumPreds = NumPreds;
1010 if (!
BB->hasAddressTaken())
return false;
1024 if (DTU->isBBPendingDeletion(
BB) ||
1032 if (maybeMergeBasicBlockIntoOnlyPred(
BB))
1035 if (tryToUnfoldSelectInCurrBB(
BB))
1039 if (HasGuards && processGuards(
BB))
1051 if (BI->isUnconditional())
return false;
1052 Condition = BI->getCondition();
1054 Condition =
SI->getCondition();
1057 if (IB->getNumSuccessors() == 0)
return false;
1065 bool ConstantFolded =
false;
1069 if (
Instruction *
I = dyn_cast<Instruction>(Condition)) {
1073 I->replaceAllUsesWith(SimpleVal);
1075 I->eraseFromParent();
1076 Condition = SimpleVal;
1077 ConstantFolded =
true;
1083 auto *FI = dyn_cast<FreezeInst>(Condition);
1084 if (isa<UndefValue>(Condition) ||
1085 (FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
1087 std::vector<DominatorTree::UpdateType> Updates;
1093 if (
i == BestSucc)
continue;
1100 <<
"' folding undef terminator: " << *BBTerm <<
'\n');
1104 DTU->applyUpdatesPermissive(Updates);
1106 FI->eraseFromParent();
1115 <<
"' folding terminator: " << *
BB->getTerminator()
1120 BPI->eraseBlock(
BB);
1124 Instruction *CondInst = dyn_cast<Instruction>(Condition);
1131 return ConstantFolded;
1135 Value *CondWithoutFreeze = CondInst;
1136 if (
auto *FI = dyn_cast<FreezeInst>(CondInst))
1137 CondWithoutFreeze = FI->getOperand(0);
1139 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(CondWithoutFreeze)) {
1143 if (
Constant *CondConst = dyn_cast<Constant>(CondCmp->getOperand(1))) {
1145 LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
1146 CondConst,
BB->getTerminator(),
1165 if (tryToUnfoldSelect(CondCmp,
BB))
1171 if (tryToUnfoldSelect(
SI,
BB))
1178 Value *SimplifyValue = CondWithoutFreeze;
1180 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(SimplifyValue))
1181 if (isa<Constant>(CondCmp->getOperand(1)))
1182 SimplifyValue = CondCmp->getOperand(0);
1186 if (
LoadInst *LoadI = dyn_cast<LoadInst>(SimplifyValue))
1187 if (simplifyPartiallyRedundantLoad(LoadI))
1191 if (
PHINode *PN = dyn_cast<PHINode>(CondInst))
1192 if (PN->getParent() ==
BB && isa<BranchInst>(
BB->getTerminator()))
1203 PHINode *PN = dyn_cast<PHINode>(CondWithoutFreeze);
1204 if (PN && PN->
getParent() ==
BB && isa<BranchInst>(
BB->getTerminator()))
1205 return processBranchOnPHI(PN);
1208 if (CondInst->
getOpcode() == Instruction::Xor &&
1209 CondInst->
getParent() ==
BB && isa<BranchInst>(
BB->getTerminator()))
1210 return processBranchOnXOR(cast<BinaryOperator>(CondInst));
1214 if (processImpliedCondition(
BB))
1221 auto *BI = dyn_cast<BranchInst>(
BB->getTerminator());
1222 if (!BI || !BI->isConditional())
1231 auto *FICond = dyn_cast<FreezeInst>(
Cond);
1232 if (FICond && FICond->hasOneUse())
1233 Cond = FICond->getOperand(0);
1241 auto &
DL =
BB->getModule()->getDataLayout();
1244 auto *PBI = dyn_cast<BranchInst>(CurrentPred->
getTerminator());
1245 if (!PBI || !PBI->isConditional())
1247 if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
1250 bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
1256 if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
1257 if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
1258 FICond->getOperand(0))
1259 Implication = CondIsTrue;
1263 BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
1264 BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
1269 BI->eraseFromParent();
1271 FICond->eraseFromParent();
1275 BPI->eraseBlock(
BB);
1278 CurrentBB = CurrentPred;
1288 if (OpInst->getParent() ==
BB)
1330 LoadInst *NLoadI = cast<LoadInst>(AvailableVal);
1336 if (AvailableVal == LoadI)
1338 if (AvailableVal->getType() != LoadI->
getType())
1340 AvailableVal, LoadI->
getType(),
"", LoadI);
1349 if (BBIt != LoadBB->
begin())
1360 AvailablePredsTy AvailablePreds;
1368 if (!PredsScanned.
insert(PredBB).second)
1371 BBIt = PredBB->end();
1372 unsigned NumScanedInst = 0;
1373 Value *PredAvailable =
nullptr;
1377 "Attempting to CSE volatile or atomic loads");
1387 AA, &IsLoadCSE, &NumScanedInst);
1392 while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->
begin() &&
1396 BBIt = SinglePredBB->
end();
1398 Loc, AccessTy, LoadI->
isAtomic(), SinglePredBB, BBIt,
1404 if (!PredAvailable) {
1405 OneUnavailablePred = PredBB;
1410 CSELoads.push_back(cast<LoadInst>(PredAvailable));
1419 if (AvailablePreds.empty())
return false;
1436 if (PredsScanned.
size() != AvailablePreds.size() &&
1438 for (
auto I = LoadBB->
begin(); &*
I != LoadI; ++
I)
1445 if (PredsScanned.
size() == AvailablePreds.size()+1 &&
1447 UnavailablePred = OneUnavailablePred;
1448 }
else if (PredsScanned.
size() != AvailablePreds.size()) {
1454 for (
const auto &AvailablePred : AvailablePreds)
1455 AvailablePredSet.
insert(AvailablePred.first);
1461 if (isa<IndirectBrInst>(
P->getTerminator()) ||
1462 isa<CallBrInst>(
P->getTerminator()))
1465 if (!AvailablePredSet.
count(
P))
1466 PredsToSplit.push_back(
P);
1470 UnavailablePred = splitBlockPreds(LoadBB, PredsToSplit,
"thread-pre-split");
1476 if (UnavailablePred) {
1478 "Can't handle critical edge here!");
1488 AvailablePreds.emplace_back(UnavailablePred, NewVal);
1506 AvailablePredsTy::iterator
I =
1509 assert(
I != AvailablePreds.end() &&
I->first ==
P &&
1510 "Didn't find entry for predecessor!");
1516 Value *&PredV =
I->second;
1519 P->getTerminator());
1524 for (
LoadInst *PredLoadI : CSELoads) {
1541 assert(!PredToDestList.empty());
1553 DestPopularity[
nullptr] = 0;
1555 DestPopularity[SuccBB] = 0;
1557 for (
const auto &PredToDest : PredToDestList)
1558 if (PredToDest.second)
1559 DestPopularity[PredToDest.second]++;
1562 using VT = decltype(DestPopularity)::value_type;
1563 auto MostPopular = std::max_element(
1564 DestPopularity.
begin(), DestPopularity.
end(),
1565 [](
const VT &L,
const VT &R) { return L.second < R.second; });
1568 return MostPopular->first;
1577 assert(PredBB &&
"Expected a single predecessor");
1579 if (
Constant *Cst = dyn_cast<Constant>(V)) {
1585 if (!
I || (
I->getParent() !=
BB &&
I->getParent() != PredBB)) {
1586 return LVI->getConstantOnEdge(V, PredPredBB, PredBB,
nullptr);
1590 if (
PHINode *PHI = dyn_cast<PHINode>(V)) {
1591 if (PHI->getParent() == PredBB)
1592 return dyn_cast<Constant>(PHI->getIncomingValueForBlock(PredPredBB));
1597 if (
CmpInst *CondCmp = dyn_cast<CmpInst>(V)) {
1598 if (CondCmp->getParent() ==
BB) {
1600 evaluateOnPredecessorEdge(
BB, PredPredBB, CondCmp->getOperand(0));
1602 evaluateOnPredecessorEdge(
BB, PredPredBB, CondCmp->getOperand(1));
1618 if (LoopHeaders.count(
BB))
1626 return maybethreadThroughTwoBasicBlocks(
BB,
Cond);
1629 assert(!PredValues.empty() &&
1630 "computeValueKnownInPredecessors returned true with no values");
1633 for (
const auto &PredValue : PredValues) {
1634 dbgs() <<
" BB '" <<
BB->getName()
1635 <<
"': FOUND condition = " << *PredValue.first
1636 <<
" for pred '" << PredValue.second->getName() <<
"'.\n";
1651 for (
const auto &PredValue : PredValues) {
1653 if (!SeenPreds.insert(Pred).second)
1659 if (isa<UndefValue>(Val))
1661 else if (
BranchInst *BI = dyn_cast<BranchInst>(
BB->getTerminator())) {
1662 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1663 DestBB = BI->getSuccessor(cast<ConstantInt>(Val)->
isZero());
1664 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(
BB->getTerminator())) {
1665 assert(isa<ConstantInt>(Val) &&
"Expecting a constant integer");
1666 DestBB =
SI->findCaseValue(cast<ConstantInt>(Val))->getCaseSuccessor();
1668 assert(isa<IndirectBrInst>(
BB->getTerminator())
1669 &&
"Unexpected terminator");
1670 assert(isa<BlockAddress>(Val) &&
"Expecting a constant blockaddress");
1671 DestBB = cast<BlockAddress>(Val)->getBasicBlock();
1675 if (PredToDestList.empty()) {
1679 if (OnlyDest != DestBB)
1680 OnlyDest = MultipleDestSentinel;
1684 OnlyVal = MultipleVal;
1697 if (PredToDestList.empty())
1703 if (OnlyDest && OnlyDest != MultipleDestSentinel) {
1704 if (
BB->hasNPredecessors(PredToDestList.size())) {
1705 bool SeenFirstBranchToOnlyDest =
false;
1706 std::vector <DominatorTree::UpdateType> Updates;
1707 Updates.reserve(
BB->getTerminator()->getNumSuccessors() - 1);
1709 if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
1710 SeenFirstBranchToOnlyDest =
true;
1712 SuccBB->removePredecessor(
BB,
true);
1721 Term->eraseFromParent();
1722 DTU->applyUpdatesPermissive(Updates);
1724 BPI->eraseBlock(
BB);
1728 if (
auto *CondInst = dyn_cast<Instruction>(
Cond)) {
1729 if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
1730 CondInst->eraseFromParent();
1738 else if (OnlyVal && OnlyVal != MultipleVal)
1751 if (MostPopularDest == MultipleDestSentinel) {
1756 [&](
const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
1757 return LoopHeaders.contains(PredToDest.second);
1760 if (PredToDestList.empty())
1769 for (
const auto &PredToDest : PredToDestList)
1770 if (PredToDest.second == MostPopularDest) {
1778 PredsToFactor.push_back(Pred);
1783 if (!MostPopularDest)
1784 MostPopularDest =
BB->getTerminator()->
1788 return tryThreadEdge(
BB, PredsToFactor, MostPopularDest);
1812 if (PredBr->isUnconditional()) {
1813 PredBBs[0] = PredBB;
1815 if (duplicateCondBranchOnPHIIntoPred(
BB, PredBBs))
1837 if (!isa<PHINode>(
BB->front()))
1864 if (!computeValueKnownInPredecessors(BO->
getOperand(0),
BB, XorOpValues,
1866 assert(XorOpValues.empty());
1867 if (!computeValueKnownInPredecessors(BO->
getOperand(1),
BB, XorOpValues,
1873 assert(!XorOpValues.empty() &&
1874 "computeValueKnownInPredecessors returned true with no values");
1878 unsigned NumTrue = 0, NumFalse = 0;
1879 for (
const auto &XorOpValue : XorOpValues) {
1880 if (isa<UndefValue>(XorOpValue.first))
1883 if (cast<ConstantInt>(XorOpValue.first)->isZero())
1891 if (NumTrue > NumFalse)
1893 else if (NumTrue != 0 || NumFalse != 0)
1899 for (
const auto &XorOpValue : XorOpValues) {
1900 if (XorOpValue.first != SplitVal && !isa<UndefValue>(XorOpValue.first))
1903 BlocksToFoldInto.push_back(XorOpValue.second);
1908 if (BlocksToFoldInto.size() ==
1909 cast<PHINode>(
BB->front()).getNumIncomingValues()) {
1914 }
else if (SplitVal->
isZero()) {
1935 return duplicateCondBranchOnPHIIntoPred(
BB, BlocksToFoldInto);
1948 Value *
IV = PN.getIncomingValueForBlock(OldPred);
1957 PN.addIncoming(
IV, NewPred);
1973 if (LoopHeaders.erase(SinglePred))
1974 LoopHeaders.insert(
BB);
1976 LVI->eraseBlock(SinglePred);
2007 LVI->eraseBlock(
BB);
2026 for (
Use &U :
I.uses()) {
2029 if (UserPN->getIncomingBlock(U) ==
BB)
2031 }
else if (
User->getParent() ==
BB)
2034 UsesToRename.push_back(&U);
2038 if (UsesToRename.empty())
2040 LLVM_DEBUG(
dbgs() <<
"JT: Renaming non-local uses of: " <<
I <<
"\n");
2049 while (!UsesToRename.empty())
2070 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2073 ValueMapping[PN] = NewPN;
2088 for (; BI != BE; ++BI) {
2090 New->setName(BI->getName());
2092 ValueMapping[&*BI] = New;
2096 for (
unsigned i = 0,
e = New->getNumOperands();
i !=
e; ++
i)
2097 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(
i))) {
2099 if (
I != ValueMapping.
end())
2100 New->setOperand(
i,
I->second);
2104 return ValueMapping;
2127 BranchInst *CondBr = dyn_cast<BranchInst>(
BB->getTerminator());
2161 if (LoopHeaders.count(PredBB))
2171 unsigned ZeroCount = 0;
2172 unsigned OneCount = 0;
2176 if (
ConstantInt *CI = dyn_cast_or_null<ConstantInt>(
2177 evaluateOnPredecessorEdge(
BB,
P,
Cond))) {
2181 }
else if (CI->isOne()) {
2190 if (ZeroCount == 1) {
2191 PredPredBB = ZeroPred;
2192 }
else if (OneCount == 1) {
2193 PredPredBB = OnePred;
2203 <<
"' - would thread to self!\n");
2209 if (LoopHeaders.count(
BB) || LoopHeaders.count(SuccBB)) {
2211 bool BBIsHeader = LoopHeaders.count(
BB);
2212 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2213 dbgs() <<
" Not threading across "
2214 << (BBIsHeader ?
"loop header BB '" :
"block BB '")
2215 <<
BB->getName() <<
"' to dest "
2216 << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2218 <<
"' - it might create an irreducible loop!\n";
2225 TTI,
BB,
BB->getTerminator(), BBDupThreshold);
2232 if (BBCost > BBDupThreshold || PredBBCost > BBDupThreshold ||
2233 BBCost + PredBBCost > BBDupThreshold) {
2235 <<
"' - Cost is too high: " << PredBBCost
2236 <<
" for PredBB, " << BBCost <<
"for BB\n");
2241 threadThroughTwoBasicBlocks(PredPredBB, PredBB,
BB, SuccBB);
2250 <<
BB->getName() <<
"'\n");
2252 BranchInst *CondBr = cast<BranchInst>(
BB->getTerminator());
2261 if (HasProfileData) {
2262 auto NewBBFreq =
BFI->getBlockFreq(PredPredBB) *
2263 BPI->getEdgeProbability(PredPredBB, PredBB);
2264 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2271 cloneInstructions(PredBB->
begin(), PredBB->
end(), NewBB, PredPredBB);
2275 BPI->copyEdgeProbabilities(PredBB, NewBB);
2292 DTU->applyUpdatesPermissive(
2298 updateSSA(PredBB, NewBB, ValueMapping);
2306 PredsToFactor.push_back(NewBB);
2307 threadEdge(
BB, PredsToFactor, SuccBB);
2317 <<
"' - would thread to self!\n");
2323 if (LoopHeaders.count(
BB) || LoopHeaders.count(SuccBB)) {
2325 bool BBIsHeader = LoopHeaders.count(
BB);
2326 bool SuccIsHeader = LoopHeaders.count(SuccBB);
2327 dbgs() <<
" Not threading across "
2328 << (BBIsHeader ?
"loop header BB '" :
"block BB '") <<
BB->getName()
2329 <<
"' to dest " << (SuccIsHeader ?
"loop header BB '" :
"block BB '")
2330 << SuccBB->
getName() <<
"' - it might create an irreducible loop!\n";
2336 TTI,
BB,
BB->getTerminator(), BBDupThreshold);
2337 if (JumpThreadCost > BBDupThreshold) {
2339 <<
"' - Cost is too high: " << JumpThreadCost <<
"\n");
2343 threadEdge(
BB, PredBBs, SuccBB);
2353 assert(SuccBB !=
BB &&
"Don't create an infinite loop");
2355 assert(!LoopHeaders.count(
BB) && !LoopHeaders.count(SuccBB) &&
2356 "Don't thread across loop headers");
2360 if (PredBBs.size() == 1)
2361 PredBB = PredBBs[0];
2364 <<
" common predecessors.\n");
2365 PredBB = splitBlockPreds(
BB, PredBBs,
".thr_comm");
2370 <<
"' to '" << SuccBB->
getName()
2371 <<
", across block:\n " << *
BB <<
"\n");
2373 LVI->threadEdge(PredBB,
BB, SuccBB);
2376 BB->getName()+
".thread",
2377 BB->getParent(),
BB);
2381 if (HasProfileData) {
2383 BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB,
BB);
2384 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2389 cloneInstructions(
BB->begin(), std::prev(
BB->end()), NewBB, PredBB);
2406 BB->removePredecessor(PredBB,
true);
2415 updateSSA(
BB, NewBB, ValueMapping);
2423 updateBlockFreqAndEdgeWeight(PredBB,
BB, NewBB, SuccBB);
2434 const char *Suffix) {
2441 for (
auto Pred : Preds)
2442 FreqMap.
insert(std::make_pair(
2443 Pred,
BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred,
BB)));
2447 if (
BB->isLandingPad()) {
2448 std::string NewName = std::string(Suffix) +
".split-lp";
2454 std::vector<DominatorTree::UpdateType> Updates;
2455 Updates.
reserve((2 * Preds.size()) + NewBBs.size());
2456 for (
auto NewBB : NewBBs) {
2463 NewBBFreq += FreqMap.
lookup(Pred);
2466 BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
2469 DTU->applyUpdatesPermissive(Updates);
2473 bool JumpThreadingPass::doesBlockHaveProfileData(
BasicBlock *
BB) {
2482 if (MDName->
getString() !=
"branch_weights")
2493 void JumpThreadingPass::updateBlockFreqAndEdgeWeight(
BasicBlock *PredBB,
2497 if (!HasProfileData)
2500 assert(
BFI && BPI &&
"BFI & BPI should have been created here");
2504 auto BBOrigFreq =
BFI->getBlockFreq(
BB);
2505 auto NewBBFreq =
BFI->getBlockFreq(NewBB);
2506 auto BB2SuccBBFreq = BBOrigFreq * BPI->getEdgeProbability(
BB, SuccBB);
2507 auto BBNewFreq = BBOrigFreq - NewBBFreq;
2508 BFI->setBlockFreq(
BB, BBNewFreq.getFrequency());
2514 auto SuccFreq = (Succ == SuccBB)
2515 ? BB2SuccBBFreq - NewBBFreq
2516 : BBOrigFreq * BPI->getEdgeProbability(
BB, Succ);
2517 BBSuccFreq.push_back(SuccFreq.getFrequency());
2521 *std::max_element(BBSuccFreq.begin(), BBSuccFreq.end());
2524 if (MaxBBSuccFreq == 0)
2525 BBSuccProbs.
assign(BBSuccFreq.size(),
2526 {1, static_cast<unsigned>(BBSuccFreq.size())});
2529 BBSuccProbs.push_back(
2537 BPI->setEdgeProbability(
BB, BBSuccProbs);
2573 if (BBSuccProbs.size() >= 2 && doesBlockHaveProfileData(
BB)) {
2575 for (
auto Prob : BBSuccProbs)
2576 Weights.push_back(Prob.getNumerator());
2578 auto TI =
BB->getTerminator();
2580 LLVMContext::MD_prof,
2592 assert(!PredBBs.empty() &&
"Can't handle an empty set");
2597 if (LoopHeaders.count(
BB)) {
2599 <<
"' into predecessor block '" << PredBBs[0]->getName()
2600 <<
"' - it might create an irreducible loop!\n");
2605 TTI,
BB,
BB->getTerminator(), BBDupThreshold);
2606 if (DuplicationCost > BBDupThreshold) {
2608 <<
"' - Cost is too high: " << DuplicationCost <<
"\n");
2613 std::vector<DominatorTree::UpdateType> Updates;
2615 if (PredBBs.size() == 1)
2616 PredBB = PredBBs[0];
2619 <<
" common predecessors.\n");
2620 PredBB = splitBlockPreds(
BB, PredBBs,
".thr_comm");
2627 <<
"' into end of '" << PredBB->
getName()
2628 <<
"' to eliminate branch on phi. Cost: "
2629 << DuplicationCost <<
" block is:" << *
BB <<
"\n");
2649 for (;
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
2653 for (; BI !=
BB->end(); ++BI) {
2657 for (
unsigned i = 0,
e = New->getNumOperands();
i !=
e; ++
i)
2658 if (
Instruction *Inst = dyn_cast<Instruction>(New->getOperand(
i))) {
2660 if (
I != ValueMapping.
end())
2661 New->setOperand(
i,
I->second);
2669 {
BB->getModule()->getDataLayout(), TLI,
nullptr,
nullptr, New})) {
2670 ValueMapping[&*BI] =
IV;
2671 if (!New->mayHaveSideEffects()) {
2676 ValueMapping[&*BI] = New;
2680 New->setName(BI->getName());
2683 for (
unsigned i = 0,
e = New->getNumOperands();
i !=
e; ++
i)
2684 if (
BasicBlock *SuccBB = dyn_cast<BasicBlock>(New->getOperand(
i)))
2691 BranchInst *BBBranch = cast<BranchInst>(
BB->getTerminator());
2697 updateSSA(
BB, PredBB, ValueMapping);
2701 BB->removePredecessor(PredBB,
true);
2704 OldPredBranch->eraseFromParent();
2706 BPI->copyEdgeProbabilities(
BB, PredBB);
2707 DTU->applyUpdatesPermissive(Updates);
2732 BB->getParent(),
BB);
2738 BI->applyMergedLocation(PredTerm->
getDebugLoc(),
SI->getDebugLoc());
2743 SI->eraseFromParent();
2749 PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
2751 Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
2755 PHINode *CondPHI = dyn_cast<PHINode>(
SI->getCondition());
2774 unfoldSelectInstr(Pred,
BB, PredSI, CondPHI,
I);
2793 BranchInst *CondBr = dyn_cast<BranchInst>(
BB->getTerminator());
2807 if (!
SI ||
SI->getParent() != Pred || !
SI->hasOneUse())
2818 LVI->getPredicateOnEdge(CondCmp->
getPredicate(),
SI->getOperand(1),
2819 CondRHS, Pred,
BB, CondCmp);
2821 LVI->getPredicateOnEdge(CondCmp->
getPredicate(),
SI->getOperand(2),
2822 CondRHS, Pred,
BB, CondCmp);
2825 LHSFolds != RHSFolds) {
2826 unfoldSelectInstr(Pred,
BB,
SI, CondLHS,
I);
2856 if (
BB->getParent()->hasFnAttribute(Attribute::SanitizeMemory))
2861 if (LoopHeaders.count(
BB))
2865 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
2868 [](
Value *V) { return !isa<ConstantInt>(V); }))
2872 using namespace PatternMatch;
2875 if (
SI->getParent() !=
BB)
2879 return Cond &&
Cond == V &&
Cond->getType()->isIntegerTy(1) && !IsAndOr;
2884 if (
ICmpInst *Cmp = dyn_cast<ICmpInst>(U.getUser())) {
2887 if (Cmp->getParent() ==
BB && Cmp->hasOneUse() &&
2888 isa<ConstantInt>(Cmp->getOperand(1 - U.getOperandNo())))
2889 if (
SelectInst *SelectI = dyn_cast<SelectInst>(Cmp->user_back()))
2890 if (isUnfoldCandidate(SelectI, Cmp->use_begin()->get())) {
2894 }
else if (
SelectInst *SelectI = dyn_cast<SelectInst>(U.getUser())) {
2896 if (isUnfoldCandidate(SelectI, U.get())) {
2915 SI->replaceAllUsesWith(NewPN);
2916 SI->eraseFromParent();
2918 std::vector<DominatorTree::UpdateType> Updates;
2928 DTU->applyUpdatesPermissive(Updates);
2954 using namespace PatternMatch;
2976 if (
auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
2978 if (
isGuard(&
I) && threadGuard(
BB, cast<IntrinsicInst>(&
I), BI))
2996 auto &
DL =
BB->getModule()->getDataLayout();
2997 bool TrueDestIsSafe =
false;
2998 bool FalseDestIsSafe =
false;
3003 TrueDestIsSafe =
true;
3008 FalseDestIsSafe =
true;
3011 if (!TrueDestIsSafe && !FalseDestIsSafe)
3014 BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
3015 BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
3021 if (Cost > BBDupThreshold)
3026 BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU);
3027 assert(GuardedBlock &&
"Could not create the guarded block?");
3032 BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU);
3033 assert(UnguardedBlock &&
"Could not create the unguarded block?");
3035 << GuardedBlock->
getName() <<
"\n");
3040 for (
auto BI =
BB->begin(); &*BI != AfterGuard; ++BI)
3041 if (!isa<PHINode>(&*BI))
3045 assert(InsertionPoint &&
"Empty block?");
3048 if (!Inst->use_empty()) {
3050 NewPN->
addIncoming(UnguardedMapping[Inst], UnguardedBlock);
3051 NewPN->
addIncoming(GuardedMapping[Inst], GuardedBlock);
3053 Inst->replaceAllUsesWith(NewPN);
3055 Inst->eraseFromParent();
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
A set of analyses that are preserved following a run of a transformation pass.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
A manager for alias analyses.
Analysis pass providing the TargetTransformInfo.
This is an optimization pass for GlobalISel generic memory operations.
static unsigned getBestDestForJumpOnUndef(BasicBlock *BB)
GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump,...
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...
static IntegerType * getInt1Ty(LLVMContext &C)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
static Constant * getNot(Constant *C)
A parsed version of the target data layout string in and methods for querying it.
bool hasOneUse() const
Return true if there is exactly one use of this value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI, PHINode *SIUse, unsigned Idx)
InstListType::iterator iterator
Instruction iterators...
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=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 ...
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.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
void findLoopHeaders(Function &F)
findLoopHeaders - We do not want jump threading to turn proper loop structures into irreducible loops...
static bool replaceFoldableUses(Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
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...
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
uint32_t getNumerator() const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
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.
bool processBranchOnXOR(BinaryOperator *BO)
processBranchOnXOR - We have an otherwise unthreadable conditional branch on a xor instruction in the...
static bool hasAddressTakenAndUsed(BasicBlock *BB)
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)
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.
const APInt & getValue() const
Return the constant as an APInt value reference.
Analysis to compute lazy value information.
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned pred_size(MachineBasicBlock *BB)
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
ReachingDefAnalysis InstSet & ToRemove
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
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 bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
Return true if Op is an instruction defined in the given block.
bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond)
Attempt to thread through two successive basic blocks.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
The instances of the Type class are immutable: once they are created, they are never changed.
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
static constexpr UpdateKind Insert
Constant * evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB, Value *cond)
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
unsigned getNumSuccessors() const
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
This class implements a map that also provides access to all stored values in a deterministic order.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
bool processImpliedCondition(BasicBlock *BB)
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_NODISCARD T pop_back_val()
std::pair< iterator, bool > insert(const ValueT &V)
Align getAlign() const
Return the alignment of the access that is being performed.
void setIncomingValue(unsigned i, Value *V)
bool tryThreadEdge(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs, BasicBlock *SuccBB)
tryThreadEdge - Thread an edge if it's safe and profitable to do so.
bool isExceptionalTerminator() const
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
bool duplicateCondBranchOnPHIIntoPred(BasicBlock *BB, const SmallVectorImpl< BasicBlock * > &PredBBs)
duplicateCondBranchOnPHIIntoPred - PredBB contains an unconditional branch to BB which contains an i1...
LLVM Basic Block Representation.
static Constant * getKnownConstant(Value *Val, ConstantPreference Preference)
getKnownConstant - Helper method to determine if we can thread over a terminator with the given value...
unsigned getNumOperands() const
Return number of MDNode operands.
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
This is the shared class of boolean and integer constants.
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...
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
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...
static cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
void initializeJumpThreadingPass(PassRegistry &)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
(vector float) vec_cmpeq(*A, *B) C
iterator begin()
Instruction iterator methods.
Analysis providing branch probability information.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Represent the analysis usage information of a pass.
static bool runImpl(const TargetLibraryInfo &TLI, Function &F)
bool isVectorTy() const
True if this is an instance of VectorType.
iterator_range< use_iterator > uses()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Legacy analysis pass which computes a DominatorTree.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
static LocationSize precise(uint64_t Value)
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.
AAMDNodes getAAMetadata() const
Returns the AA metadata for this instruction.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
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 removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB)
tryToUnfoldSelect - Look for blocks of the form bb1: a = select br bb2
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
bool tryToUnfoldSelectInCurrBB(BasicBlock *BB)
tryToUnfoldSelectInCurrBB - Look for PHI/Select or PHI/CMP/Select in the same BB in the form bb: p = ...
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Value * getCondition() const
The object format emitted by the WebAssembly backed is documented see the home and packaging for producing WebAssembly applications that can run in browsers and other environments wasi sdk provides a more minimal C C SDK based on llvm and a libc based on for producing WebAssemmbly applictions that use the WASI ABI Rust provides WebAssembly support integrated into Cargo There are two main which provides a relatively minimal environment that has an emphasis on being native wasm32 unknown which uses Emscripten internally and provides standard C C filesystem GL and SDL bindings For more and br_table instructions can support having a value on the value stack across the jump(sometimes). We should(a) model this
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...
This class is the base class for the comparison instructions.
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
bool isIntegerTy() const
True if this is an instance of IntegerType.
const MDOperand & getOperand(unsigned I) const
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...
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This instruction compares its operands according to the predicate given to the constructor.
LogicalOp_match< LHS, RHS, Instruction::Or > m_LogicalOr(const LHS &L, const RHS &R)
Matches L || R either in the form of L | R or L ? true : R.
Wrapper around LazyValueInfo.
bool simplifyPartiallyRedundantLoad(LoadInst *LI)
simplifyPartiallyRedundantLoad - If LoadI is an obviously partially redundant load instruction,...
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static BasicBlock * findMostPopularDest(BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * >> &PredToDestList)
findMostPopularDest - The specified list contains multiple possible threadable destinations.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
This is an important class for using LLVM in a threaded context.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
'undef' values are things that do not have specified contents.
initializer< Ty > init(const Ty &Val)
void adaptNoAliasScopes(llvm::Instruction *I, const DenseMap< MDNode *, MDNode * > &ClonedScopes, LLVMContext &Context)
Adapt the metadata for the specified instruction according to the provided mapping.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
This pass performs 'jump threading', which looks at blocks that have multiple predecessors and multip...
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
This class represents the LLVM 'select' instruction.
void cloneNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, DenseMap< MDNode *, MDNode * > &ClonedScopes, StringRef Ext, LLVMContext &Context)
Duplicate the specified list of noalias decl scopes.
This pass computes, caches, and vends lazy value constraint information.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool isUnconditional() const
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
void setOperand(unsigned i, Value *Val)
bool processGuards(BasicBlock *BB)
Try to propagate a guard from the current BB into one of its predecessors in case if another branch o...
The address of a basic block.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB)
Merge basic block BB into its sole predecessor if possible.
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,...
SmallVector< MachineOperand, 4 > Cond
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
Type * getType() const
All values are typed, get the type of this value.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB, BasicBlock *BB, BasicBlock *SuccBB)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
static const Function * getParent(const Value *V)
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool pred_empty(const BasicBlock *BB)
This is the base class for all instructions that perform data casts.
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB)
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
StringRef getName() const
Return a constant reference to the value's name.
An instruction for reading from memory.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
static ConstantInt * getFalse(LLVMContext &Context)
const Instruction & front() const
LLVMContext & getContext() const
Get the context in which this basic block lives.
static bool runOnFunction(Function &F, bool PostInlining)
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.
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
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...
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...
static ConstantInt * getTrue(LLVMContext &Context)
static cl::opt< bool > PrintLVIAfterJumpThreading("print-lvi-after-jump-threading", cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false), cl::Hidden)
bool processThreadableEdges(Value *Cond, BasicBlock *BB, jumpthreading::ConstantPreference Preference, Instruction *CxtI=nullptr)
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
void assign(size_type NumElts, ValueParamT Elt)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
Interval::pred_iterator pred_end(Interval *I)
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
void setAAMetadata(const AAMDNodes &N)
Sets the AA metadata on this instruction from the AAMDNodes structure.
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 ...
Provides information about what library functions are available for the current target.
iterator find(const KeyT &Val)
bool runImpl(Function &F, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, LazyValueInfo *LVI, AAResults *AA, DomTreeUpdater *DTU, bool HasProfileData, std::unique_ptr< BlockFrequencyInfo > BFI, std::unique_ptr< BranchProbabilityInfo > BPI)
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading", "Jump Threading", false, false) INITIALIZE_PASS_END(JumpThreading
Indirect Branch Instruction.
BranchProbability getCompl() const
This class represents a range of values.
A wrapper class for inspecting calls to intrinsic functions.
void updateSSA(BasicBlock *BB, BasicBlock *NewBB, DenseMap< Instruction *, Value * > &ValueMapping)
Update the SSA form.
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...
Analysis pass which computes a DominatorTree.
const InstListType & getInstList() const
Return the underlying instruction list container.
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 ...
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
Tristate
This is used to return true/false/dunno results.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Value * getArgOperand(unsigned i) const
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass * createJumpThreadingPass(int Threshold=-1)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
void RewriteUse(Use &U)
Rewrite a use of the symbolic value.
const BasicBlock * getParent() const
Predicate getPredicate() const
Return the predicate for this instruction.
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Legacy wrapper pass to provide the GlobalsAAResult object.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
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.
static const uint32_t IV[8]
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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...
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
A container for analyses that lazily runs them and caches their results.
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)
FunctionPass class - This class is used to implement most global optimizations.
This class represents a function call, abstracting a target machine's calling convention.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
AnalysisUsage & addRequired()
void takeName(Value *V)
Transfer the name from V to this value.
Instruction * SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DominatorTree *DT, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Value * getOperand(unsigned i) const
StringRef getString() const
Conditional or Unconditional Branch instruction.
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Helper class for SSA formation on a set of values defined in multiple blocks.
DenseMap< Instruction *, Value * > cloneInstructions(BasicBlock::iterator BI, BasicBlock::iterator BE, BasicBlock *NewBB, BasicBlock *PredBB)
Clone instructions in range [BI, BE) to NewBB.
void reserve(size_type N)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool isEHPad() const
Return true if this basic block is an exception handling block.
bool processBlock(BasicBlock *BB)
processBlock - If there are any predecessors whose control can be threaded through to a successor,...
LLVM Value Representation.
Analysis pass providing the TargetLibraryInfo.
bool processBranchOnPHI(PHINode *PN)
processBranchOnPHI - We have an otherwise unthreadable conditional branch on a PHI node (or freeze PH...
bool isConditional() const
LogicalOp_match< LHS, RHS, Instruction::And > m_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R either in the form of L & R or L ? R : false.
BasicBlock * getSuccessor(unsigned i) const
Representation for a specific memory location.
JumpThreadingPass(int T=-1)
static constexpr UpdateKind Delete
InstListType::const_iterator const_iterator
cl::opt< unsigned > DefMaxInstsToScan
The default number of maximum instructions to scan in the block, used by FindAvailableLoadedValue().
A Use represents the edge between a Value definition and its users.
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.