59#include "llvm/IR/IntrinsicsWebAssembly.h"
92#define DEBUG_TYPE "local"
94STATISTIC(NumRemoved,
"Number of unreachable basic blocks removed");
95STATISTIC(NumPHICSEs,
"Number of PHI's that got CSE'd");
99#ifdef EXPENSIVE_CHECKS
105 cl::desc(
"Perform extra assertion checking to verify that PHINodes's hash "
106 "function is well-behaved w.r.t. its isEqual predicate"));
111 "When the basic block contains not more than this number of PHI nodes, "
112 "perform a (faster!) exhaustive search instead of set-driven one."));
136 if (
auto *BI = dyn_cast<BranchInst>(
T)) {
137 if (BI->isUnconditional())
return false;
142 if (Dest2 == Dest1) {
148 assert(BI->getParent() &&
"Terminator not inserted in block!");
155 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
156 LLVMContext::MD_annotation});
159 BI->eraseFromParent();
160 if (DeleteDeadConditions)
165 if (
auto *
Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
179 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
180 LLVMContext::MD_annotation});
182 BI->eraseFromParent();
184 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
191 if (
auto *SI = dyn_cast<SwitchInst>(
T)) {
194 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
195 BasicBlock *DefaultDest = SI->getDefaultDest();
200 SI->getNumCases() > 0) {
201 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
204 bool Changed =
false;
207 for (
auto It = SI->case_begin(),
End = SI->case_end(); It !=
End;) {
209 if (It->getCaseValue() == CI) {
210 TheOnlyDest = It->getCaseSuccessor();
216 if (It->getCaseSuccessor() == DefaultDest) {
218 unsigned NCases = SI->getNumCases();
221 if (NCases > 1 && MD) {
227 unsigned Idx = It->getCaseIndex();
229 Weights[0] += Weights[
Idx + 1];
238 It = SI->removeCase(It);
239 End = SI->case_end();
243 if (
auto *NewCI = dyn_cast<ConstantInt>(SI->getCondition())) {
245 It = SI->case_begin();
255 if (It->getCaseSuccessor() != TheOnlyDest)
256 TheOnlyDest =
nullptr;
262 if (CI && !TheOnlyDest) {
265 TheOnlyDest = SI->getDefaultDest();
280 if (DTU && Succ != TheOnlyDest)
281 RemovedSuccessors.
insert(Succ);
283 if (Succ == SuccToKeep) {
284 SuccToKeep =
nullptr;
292 SI->eraseFromParent();
293 if (DeleteDeadConditions)
296 std::vector<DominatorTree::UpdateType> Updates;
297 Updates.reserve(RemovedSuccessors.
size());
298 for (
auto *RemovedSuccessor : RemovedSuccessors)
299 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
305 if (SI->getNumCases() == 1) {
308 auto FirstCase = *SI->case_begin();
310 FirstCase.getCaseValue(),
"cond");
314 FirstCase.getCaseSuccessor(),
315 SI->getDefaultDest());
327 MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
329 NewBr->
setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
332 SI->eraseFromParent();
338 if (
auto *IBI = dyn_cast<IndirectBrInst>(
T)) {
341 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
342 BasicBlock *TheOnlyDest = BA->getBasicBlock();
349 for (
unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
351 if (DTU && DestBB != TheOnlyDest)
352 RemovedSuccessors.
insert(DestBB);
353 if (IBI->getDestination(i) == SuccToKeep) {
354 SuccToKeep =
nullptr;
359 Value *Address = IBI->getAddress();
360 IBI->eraseFromParent();
361 if (DeleteDeadConditions)
368 BA->destroyConstant();
379 std::vector<DominatorTree::UpdateType> Updates;
380 Updates.reserve(RemovedSuccessors.
size());
381 for (
auto *RemovedSuccessor : RemovedSuccessors)
382 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
411 if (II->getIntrinsicID() == Intrinsic::stacksave ||
412 II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
413 II->isLifetimeStartOrEnd())
420 if (
I->isTerminator())
429 if (isa<DbgVariableIntrinsic>(
I))
438 if (
auto *CB = dyn_cast<CallBase>(
I))
442 if (!
I->willReturn()) {
443 auto *II = dyn_cast<IntrinsicInst>(
I);
447 switch (II->getIntrinsicID()) {
448 case Intrinsic::experimental_guard: {
452 auto *
Cond = dyn_cast<ConstantInt>(II->getArgOperand(0));
457 case Intrinsic::wasm_trunc_signed:
458 case Intrinsic::wasm_trunc_unsigned:
459 case Intrinsic::ptrauth_auth:
460 case Intrinsic::ptrauth_resign:
467 if (!
I->mayHaveSideEffects())
474 if (II->getIntrinsicID() == Intrinsic::stacksave ||
475 II->getIntrinsicID() == Intrinsic::launder_invariant_group)
478 if (II->isLifetimeStartOrEnd()) {
479 auto *Arg = II->getArgOperand(1);
481 if (isa<UndefValue>(Arg))
485 if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
487 if (IntrinsicInst *IntrinsicUse =
488 dyn_cast<IntrinsicInst>(Use.getUser()))
489 return IntrinsicUse->isLifetimeStartOrEnd();
496 if (II->getIntrinsicID() == Intrinsic::assume &&
499 return !
Cond->isZero();
504 if (
auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(
I)) {
505 std::optional<fp::ExceptionBehavior> ExBehavior =
506 FPI->getExceptionBehavior();
511 if (
auto *Call = dyn_cast<CallBase>(
I)) {
513 if (
Constant *
C = dyn_cast<Constant>(FreedOp))
514 return C->isNullValue() || isa<UndefValue>(
C);
520 if (
auto *LI = dyn_cast<LoadInst>(
I))
521 if (
auto *GV = dyn_cast<GlobalVariable>(
522 LI->getPointerOperand()->stripPointerCasts()))
523 if (!LI->isVolatile() && GV->isConstant())
535 std::function<
void(
Value *)> AboutToDeleteCallback) {
543 AboutToDeleteCallback);
551 std::function<
void(
Value *)> AboutToDeleteCallback) {
552 unsigned S = 0,
E = DeadInsts.
size(), Alive = 0;
553 for (; S !=
E; ++S) {
554 auto *
I = dyn_cast_or_null<Instruction>(DeadInsts[S]);
556 DeadInsts[S] =
nullptr;
563 AboutToDeleteCallback);
570 std::function<
void(
Value *)> AboutToDeleteCallback) {
572 while (!DeadInsts.
empty()) {
578 "Live instruction found in dead worklist!");
579 assert(
I->use_empty() &&
"Instructions with uses are not dead.");
584 if (AboutToDeleteCallback)
585 AboutToDeleteCallback(
I);
589 for (
Use &OpU :
I->operands()) {
590 Value *OpV = OpU.get();
606 I->eraseFromParent();
614 for (
auto *DII : DbgUsers)
615 DII->setKillLocation();
616 for (
auto *DPV : DPUsers)
617 DPV->setKillLocation();
632 for (++UI; UI != UE; ++UI) {
649 I = cast<Instruction>(*
I->user_begin())) {
655 if (!Visited.
insert(
I).second) {
675 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
676 Value *OpV =
I->getOperand(i);
677 I->setOperand(i,
nullptr);
690 I->eraseFromParent();
698 for (
User *U :
I->users()) {
700 WorkList.
insert(cast<Instruction>(U));
705 bool Changed =
false;
706 if (!
I->use_empty()) {
707 I->replaceAllUsesWith(SimpleV);
711 I->eraseFromParent();
726 bool MadeChange =
false;
743 assert(!BI->isTerminator());
753 while (!WorkList.
empty()) {
768 while (
PHINode *PN = dyn_cast<PHINode>(DestBB->
begin())) {
769 Value *NewVal = PN->getIncomingValue(0);
772 PN->replaceAllUsesWith(NewVal);
773 PN->eraseFromParent();
777 assert(PredBB &&
"Block doesn't have a single predecessor!");
791 if (PredOfPredBB != PredBB)
792 if (SeenPreds.
insert(PredOfPredBB).second)
793 Updates.
push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
796 if (SeenPreds.
insert(PredOfPredBB).second)
797 Updates.
push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
798 Updates.
push_back({DominatorTree::Delete, PredBB, DestBB});
828 "The successor list of PredBB isn't empty before "
829 "applying corresponding DTU updates.");
850 return First == Second || isa<UndefValue>(
First) || isa<UndefValue>(Second);
881 if (BBPreds.
count(IBB) &&
885 <<
"Can't fold, phi node " << PN->
getName() <<
" in "
886 << Succ->
getName() <<
" is conflicting with "
887 << BBPN->
getName() <<
" with regard to common predecessor "
899 if (BBPreds.
count(IBB) &&
903 <<
" is conflicting with regard to common "
904 <<
"predecessor " << IBB->
getName() <<
"\n");
931 if (!isa<UndefValue>(OldVal)) {
933 IncomingValues.
find(BB)->second == OldVal) &&
934 "Expected OldVal to match incoming value from BB!");
936 IncomingValues.
insert(std::make_pair(BB, OldVal));
941 if (It != IncomingValues.
end())
return It->second;
960 if (!isa<UndefValue>(V))
961 IncomingValues.
insert(std::make_pair(BB, V));
976 if (!isa<UndefValue>(V))
continue;
985 if (It == IncomingValues.
end()) {
998 unsigned PoisonCount =
count_if(TrueUndefOps, [&](
unsigned i) {
1001 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.
size()) {
1002 for (
unsigned i : TrueUndefOps)
1017 if (BB->
phis().empty() || Succ->
phis().empty())
1026 if (BBPreds.
count(SuccPred)) {
1029 CommonPred = SuccPred;
1049 assert(OldVal &&
"No entry in PHI for Pred BB!");
1066 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->
getParent() == BB) {
1067 PHINode *OldValPN = cast<PHINode>(OldVal);
1076 if (PredBB == CommonPred)
1091 for (
unsigned i = 0, e = BBPreds.
size(); i != e; ++i) {
1096 if (PredBB == CommonPred)
1116 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1133 bool BBPhisMergeable =
1137 if (!BBKillable && !BBPhisMergeable)
1157 while (isa<PHINode>(*BBI)) {
1158 for (
Use &U : BBI->uses()) {
1159 if (
PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1160 if (PN->getIncomingBlock(U) != BB)
1170 if (BBPhisMergeable && CommonPred)
1172 <<
" and " << Succ->
getName() <<
" : "
1173 << CommonPred->
getName() <<
"\n");
1241 if (TI->hasMetadata(LLVMContext::MD_loop))
1244 if (PredTI->hasMetadata(LLVMContext::MD_loop))
1249 else if (BBPhisMergeable)
1264 if (SeenPreds.
insert(PredOfBB).second)
1265 Updates.
push_back({DominatorTree::Insert, PredOfBB, Succ});
1273 if (SeenPreds.
insert(PredOfBB).second && PredOfBB != CommonPred)
1274 Updates.
push_back({DominatorTree::Delete, PredOfBB, BB});
1277 Updates.
push_back({DominatorTree::Delete, BB, Succ});
1280 if (isa<PHINode>(Succ->
begin())) {
1300 while (
PHINode *PN = dyn_cast<PHINode>(&BB->
front())) {
1302 assert(PN->use_empty() &&
"There shouldn't be any uses here!");
1303 PN->eraseFromParent();
1310 if (
MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop))
1312 Pred->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
1327 "applying corresponding DTU updates.");
1328 }
else if (BBPhisMergeable) {
1331 if (
Instruction *UseInst = dyn_cast<Instruction>(U.getUser()))
1332 return UseInst->
getParent() != CommonPred &&
1333 BBPreds.
contains(UseInst->getParent());
1354 bool Changed =
false;
1359 for (
auto I = BB->
begin();
PHINode *PN = dyn_cast<PHINode>(
I);) {
1364 for (
auto J =
I;
PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1365 if (
ToRemove.contains(DuplicatePN))
1390 struct PHIDenseMapInfo {
1391 static PHINode *getEmptyKey() {
1395 static PHINode *getTombstoneKey() {
1400 return PN == getEmptyKey() || PN == getTombstoneKey();
1414 static unsigned getHashValue(
PHINode *PN) {
1429 return LHS->isIdenticalTo(
RHS);
1447 bool Changed =
false;
1448 for (
auto I = BB->
begin();
PHINode *PN = dyn_cast<PHINode>(
I++);) {
1451 auto Inserted = PHISet.
insert(PN);
1452 if (!Inserted.second) {
1455 PN->replaceAllUsesWith(*Inserted.first);
1484 PN->eraseFromParent();
1490 V = V->stripPointerCasts();
1492 if (
AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1498 Align CurrentAlign = AI->getAlign();
1499 if (PrefAlign <= CurrentAlign)
1500 return CurrentAlign;
1504 if (
DL.exceedsNaturalStackAlignment(PrefAlign))
1505 return CurrentAlign;
1506 AI->setAlignment(PrefAlign);
1510 if (
auto *GO = dyn_cast<GlobalObject>(V)) {
1512 Align CurrentAlign = GO->getPointerAlignment(
DL);
1513 if (PrefAlign <= CurrentAlign)
1514 return CurrentAlign;
1520 if (!GO->canIncreaseAlignment())
1521 return CurrentAlign;
1523 if (GO->isThreadLocal()) {
1524 unsigned MaxTLSAlign = GO->getParent()->getMaxTLSAlignment() / CHAR_BIT;
1525 if (MaxTLSAlign && PrefAlign >
Align(MaxTLSAlign))
1526 PrefAlign =
Align(MaxTLSAlign);
1529 GO->setAlignment(PrefAlign);
1541 assert(V->getType()->isPointerTy() &&
1542 "getOrEnforceKnownAlignment expects a pointer!");
1554 if (PrefAlign && *PrefAlign > Alignment)
1575 for (
auto *DVI : DbgValues) {
1577 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1580 for (
auto *DPV : DPValues) {
1582 if ((DPV->getVariable() == DIVar) && (DPV->getExpression() == DIExpr))
1598 TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1608 "address of variable must have exactly 1 location operand.");
1611 if (std::optional<TypeSize> FragmentSize =
1612 AI->getAllocationSizeInBits(
DL)) {
1613 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1624 TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1634 "address of variable must have exactly 1 location operand.");
1637 if (std::optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(
DL)) {
1638 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1652 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1660 Instr->getParent()->insertDbgRecordBefore(DV, Instr);
1670 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1678 Instr->getParent()->insertDbgRecordAfter(DV, &*Instr);
1688 assert(DIVar &&
"Missing variable");
1690 Value *DV = SI->getValueOperand();
1707 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1717 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DII
1733 assert(DIVar &&
"Missing variable");
1739 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1758 assert(DIVar &&
"Missing variable");
1760 Value *DV = SI->getValueOperand();
1777 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1787 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DPV
1797 SI->getParent()->insertDbgRecordBefore(NewDPV, SI->getIterator());
1806 assert(DIVar &&
"Missing variable");
1815 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1828 if (InsertionPt != BB->
end()) {
1837 assert(DIVar &&
"Missing variable");
1843 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DPValue: " << *DPV
1876 assert(DIVar &&
"Missing variable");
1885 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DPValue: " << *DPV
1898 if (InsertionPt != BB->
end()) {
1906 bool Changed =
false;
1910 for (
auto &FI :
F) {
1912 if (
auto *DDI = dyn_cast<DbgDeclareInst>(&BI))
1915 if (DPV.getType() == DPValue::LocationType::Declare)
1924 auto LowerOne = [&](
auto *DDI) {
1926 dyn_cast_or_null<AllocaInst>(DDI->getVariableLocationOp(0));
1938 if (LoadInst *LI = dyn_cast<LoadInst>(U))
1939 return LI->isVolatile();
1940 if (StoreInst *SI = dyn_cast<StoreInst>(U))
1941 return SI->isVolatile();
1948 while (!WorkList.
empty()) {
1950 for (
const auto &AIUse : V->uses()) {
1951 User *U = AIUse.getUser();
1952 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
1953 if (AIUse.getOperandNo() == 1)
1955 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
1957 }
else if (
CallInst *CI = dyn_cast<CallInst>(U)) {
1961 if (!CI->isLifetimeStartOrEnd()) {
1966 NewLoc, CI->getIterator());
1968 }
else if (
BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1969 if (BI->getType()->isPointerTy())
1974 DDI->eraseFromParent();
1992 assert(BB &&
"No BasicBlock to clone DPValue(s) from.");
1993 if (InsertedPHIs.
size() == 0)
1998 for (
auto &
I : *BB) {
2000 for (
Value *V : DPV.location_ops())
2001 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2002 DbgValueMap.
insert({Loc, &DPV});
2005 if (DbgValueMap.
size() == 0)
2018 for (
auto PHI : InsertedPHIs) {
2023 for (
auto VI :
PHI->operand_values()) {
2024 auto V = DbgValueMap.
find(VI);
2025 if (V != DbgValueMap.
end()) {
2026 DPValue *DbgII = cast<DPValue>(V->second);
2027 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2028 if (NewDI == NewDbgValueMap.
end()) {
2030 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2032 DPValue *NewDbgII = NewDI->second;
2041 for (
auto DI : NewDbgValueMap) {
2043 DPValue *NewDbgII = DI.second;
2045 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2054 assert(BB &&
"No BasicBlock to clone dbg.value(s) from.");
2055 if (InsertedPHIs.
size() == 0)
2062 for (
auto &
I : *BB) {
2063 if (
auto DbgII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
2064 for (
Value *V : DbgII->location_ops())
2065 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2066 DbgValueMap.
insert({Loc, DbgII});
2069 if (DbgValueMap.
size() == 0)
2084 for (
auto *
PHI : InsertedPHIs) {
2089 for (
auto *VI :
PHI->operand_values()) {
2090 auto V = DbgValueMap.
find(VI);
2091 if (V != DbgValueMap.
end()) {
2092 auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
2093 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2094 if (NewDI == NewDbgValueMap.
end()) {
2095 auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
2096 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2107 for (
auto DI : NewDbgValueMap) {
2109 auto *NewDbgII = DI.second;
2111 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2112 NewDbgII->insertBefore(&*InsertionPt);
2117 DIBuilder &Builder, uint8_t DIExprFlags,
2122 auto ReplaceOne = [&](
auto *DII) {
2123 assert(DII->getVariable() &&
"Missing variable");
2124 auto *DIExpr = DII->getExpression();
2126 DII->setExpression(DIExpr);
2127 DII->replaceVariableLocationOp(Address, NewAddress);
2133 return !DbgDeclares.
empty() || !DPVDeclares.
empty();
2141 assert(DIVar &&
"Missing variable");
2171 for (
auto *DVI : DbgUsers)
2173 DVI->getExpression(), NewAllocaAddress, DVI,
2174 nullptr, Builder,
Offset);
2179 DPV->getExpression(), NewAllocaAddress,
nullptr,
2193 Instruction *
I = dyn_cast<Instruction>(Assign->getAddress());
2198 assert(!Assign->getAddressExpression()->getFragmentInfo().has_value() &&
2199 "address-expression shouldn't have fragment info");
2212 Assign->getAddressExpression(), Ops, 0,
false);
2214 "address-expression shouldn't have fragment info");
2217 if (AdditionalValues.
empty()) {
2218 Assign->setAddress(NewV);
2219 Assign->setAddressExpression(SalvagedExpr);
2221 Assign->setKillAddress();
2231 const unsigned MaxDebugArgs = 16;
2232 const unsigned MaxExpressionSize = 128;
2233 bool Salvaged =
false;
2235 for (
auto *DII : DbgUsers) {
2236 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) {
2237 if (DAI->getAddress() == &
I) {
2241 if (DAI->getValue() != &
I)
2247 bool StackValue = isa<DbgValueInst>(DII);
2248 auto DIILocation = DII->location_ops();
2251 "DbgVariableIntrinsic must use salvaged instruction as its location");
2257 Value *Op0 =
nullptr;
2259 auto LocItr =
find(DIILocation, &
I);
2260 while (SalvagedExpr && LocItr != DIILocation.end()) {
2262 unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
2269 LocItr = std::find(++LocItr, DIILocation.end(), &
I);
2276 DII->replaceVariableLocationOp(&
I, Op0);
2277 bool IsValidSalvageExpr = SalvagedExpr->
getNumElements() <= MaxExpressionSize;
2278 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2279 DII->setExpression(SalvagedExpr);
2280 }
else if (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
2281 DII->getNumVariableLocationOps() + AdditionalValues.
size() <=
2283 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2288 DII->setKillLocation();
2294 for (
auto *DPV : DPUsers) {
2295 if (DPV->isDbgAssign()) {
2296 if (DPV->getAddress() == &
I) {
2300 if (DPV->getValue() != &
I)
2307 bool StackValue = DPV->getType() != DPValue::LocationType::Declare;
2308 auto DPVLocation = DPV->location_ops();
2311 "DbgVariableIntrinsic must use salvaged instruction as its location");
2317 Value *Op0 =
nullptr;
2319 auto LocItr =
find(DPVLocation, &
I);
2320 while (SalvagedExpr && LocItr != DPVLocation.end()) {
2322 unsigned LocNo = std::distance(DPVLocation.begin(), LocItr);
2329 LocItr = std::find(++LocItr, DPVLocation.end(), &
I);
2336 DPV->replaceVariableLocationOp(&
I, Op0);
2337 bool IsValidSalvageExpr =
2339 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2340 DPV->setExpression(SalvagedExpr);
2341 }
else if (DPV->getType() != DPValue::LocationType::Declare &&
2342 IsValidSalvageExpr &&
2343 DPV->getNumVariableLocationOps() + AdditionalValues.
size() <=
2345 DPV->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2351 DPV->setKillLocation();
2360 for (
auto *DII : DbgUsers)
2361 DII->setKillLocation();
2363 for (
auto *DPV : DPUsers)
2364 DPV->setKillLocation();
2371 unsigned BitWidth =
DL.getIndexSizeInBits(
GEP->getPointerAddressSpace());
2375 if (!
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
2377 if (!VariableOffsets.
empty() && !CurrentLocOps) {
2378 Opcodes.
insert(Opcodes.
begin(), {dwarf::DW_OP_LLVM_arg, 0});
2381 for (
const auto &
Offset : VariableOffsets) {
2384 "Expected strictly positive multiplier for offset.");
2386 Offset.second.getZExtValue(), dwarf::DW_OP_mul,
2387 dwarf::DW_OP_plus});
2390 return GEP->getOperand(0);
2395 case Instruction::Add:
2396 return dwarf::DW_OP_plus;
2397 case Instruction::Sub:
2398 return dwarf::DW_OP_minus;
2399 case Instruction::Mul:
2400 return dwarf::DW_OP_mul;
2401 case Instruction::SDiv:
2402 return dwarf::DW_OP_div;
2403 case Instruction::SRem:
2404 return dwarf::DW_OP_mod;
2405 case Instruction::Or:
2406 return dwarf::DW_OP_or;
2407 case Instruction::And:
2408 return dwarf::DW_OP_and;
2409 case Instruction::Xor:
2410 return dwarf::DW_OP_xor;
2411 case Instruction::Shl:
2412 return dwarf::DW_OP_shl;
2413 case Instruction::LShr:
2414 return dwarf::DW_OP_shr;
2415 case Instruction::AShr:
2416 return dwarf::DW_OP_shra;
2427 if (!CurrentLocOps) {
2432 AdditionalValues.
push_back(
I->getOperand(1));
2439 auto *ConstInt = dyn_cast<ConstantInt>(BI->
getOperand(1));
2441 if (ConstInt && ConstInt->getBitWidth() > 64)
2447 uint64_t Val = ConstInt->getSExtValue();
2450 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2451 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2455 Opcodes.
append({dwarf::DW_OP_constu, Val});
2474 return dwarf::DW_OP_eq;
2476 return dwarf::DW_OP_ne;
2479 return dwarf::DW_OP_gt;
2482 return dwarf::DW_OP_ge;
2485 return dwarf::DW_OP_lt;
2488 return dwarf::DW_OP_le;
2498 auto *ConstInt = dyn_cast<ConstantInt>(Icmp->
getOperand(1));
2500 if (ConstInt && ConstInt->getBitWidth() > 64)
2508 uint64_t Val = ConstInt->getSExtValue();
2526 auto &M = *
I.getModule();
2527 auto &
DL = M.getDataLayout();
2529 if (
auto *CI = dyn_cast<CastInst>(&
I)) {
2530 Value *FromValue = CI->getOperand(0);
2532 if (CI->isNoopCast(
DL)) {
2541 !(isa<TruncInst>(&
I) || isa<SExtInst>(&
I) || isa<ZExtInst>(&
I) ||
2542 isa<IntToPtrInst>(&
I) || isa<PtrToIntInst>(&
I)))
2546 if (FromType->isPointerTy())
2547 FromType =
DL.getIntPtrType(FromType);
2549 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2554 Ops.
append(ExtOps.begin(), ExtOps.end());
2558 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
2560 if (
auto *BI = dyn_cast<BinaryOperator>(&
I))
2562 if (
auto *IC = dyn_cast<ICmpInst>(&
I))
2589 bool Changed =
false;
2593 if (isa<Instruction>(&To)) {
2594 bool DomPointAfterFrom =
From.getNextNonDebugInstruction() == &DomPoint;
2596 for (
auto *DII :
Users) {
2606 }
else if (!DT.
dominates(&DomPoint, DII)) {
2607 UndefOrSalvage.
insert(DII);
2612 for (
auto *DPV : DPUsers) {
2616 if (isa<DbgVariableIntrinsic>(NextNonDebug))
2619 if (DomPointAfterFrom && NextNonDebug == &DomPoint) {
2625 }
else if (!DT.
dominates(&DomPoint, MarkedInstr)) {
2626 UndefOrSalvageDPV.
insert(DPV);
2632 for (
auto *DII :
Users) {
2633 if (UndefOrSalvage.
count(DII))
2645 for (
auto *DPV : DPUsers) {
2646 if (UndefOrSalvageDPV.
count(DPV))
2659 if (!UndefOrSalvage.
empty() || !UndefOrSalvageDPV.
empty()) {
2683 bool SameSize =
DL.getTypeSizeInBits(FromTy) ==
DL.getTypeSizeInBits(ToTy);
2684 bool LosslessConversion = !
DL.isNonIntegralPointerType(FromTy) &&
2685 !
DL.isNonIntegralPointerType(ToTy);
2686 return SameSize && LosslessConversion;
2696 if (!
From.isUsedByMetadata())
2699 assert(&
From != &To &&
"Can't replace something with itself");
2708 return DPV.getExpression();
2722 assert(FromBits != ToBits &&
"Unexpected no-op conversion");
2726 if (FromBits < ToBits)
2737 return std::nullopt;
2739 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2751 return std::nullopt;
2753 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2767 bool Changed =
false;
2769 I->dropDbgRecords();
2770 for (
Use &U :
I->operands()) {
2772 if (isa<Instruction>(
Op) && !
Op->getType()->isTokenTy()) {
2782std::pair<unsigned, unsigned>
2784 unsigned NumDeadInst = 0;
2785 unsigned NumDeadDbgInst = 0;
2792 while (EndInst != &BB->
front()) {
2804 if (isa<DbgInfoIntrinsic>(Inst))
2812 return {NumDeadInst, NumDeadDbgInst};
2828 Successor->removePredecessor(BB, PreserveLCSSA);
2833 UI->setDebugLoc(
I->getDebugLoc());
2836 unsigned NumInstrsRemoved = 0;
2838 while (BBI != BBE) {
2839 if (!BBI->use_empty())
2841 BBI++->eraseFromParent();
2847 for (
BasicBlock *UniqueSuccessor : UniqueSuccessors)
2848 Updates.
push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2852 return NumInstrsRemoved;
2871 auto NewWeights =
uint32_t(TotalWeight) != TotalWeight
2874 NewCall->
setMetadata(LLVMContext::MD_prof, NewWeights);
2897 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2926 UnwindEdge, InvokeArgs, OpBundles, CI->
getName(), BB);
2933 DTU->
applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2940 Split->front().eraseFromParent();
2951 bool Changed =
false;
2959 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
2960 Value *Callee = CI->getCalledOperand();
2962 if (
Function *
F = dyn_cast<Function>(Callee)) {
2963 auto IntrinsicID =
F->getIntrinsicID();
2968 if (IntrinsicID == Intrinsic::assume) {
2975 }
else if (IntrinsicID == Intrinsic::experimental_guard) {
2986 if (!isa<UnreachableInst>(CI->getNextNode())) {
2992 }
else if ((isa<ConstantPointerNull>(Callee) &&
2994 cast<PointerType>(Callee->getType())
2995 ->getAddressSpace())) ||
2996 isa<UndefValue>(Callee)) {
3001 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
3005 if (!isa<UnreachableInst>(CI->getNextNonDebugInstruction())) {
3012 }
else if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3018 if (SI->isVolatile())
continue;
3022 if (isa<UndefValue>(
Ptr) ||
3023 (isa<ConstantPointerNull>(
Ptr) &&
3025 SI->getPointerAddressSpace()))) {
3034 if (
auto *II = dyn_cast<InvokeInst>(Terminator)) {
3036 Value *Callee = II->getCalledOperand();
3037 if ((isa<ConstantPointerNull>(Callee) &&
3039 isa<UndefValue>(Callee)) {
3043 if (II->doesNotReturn() &&
3044 !isa<UnreachableInst>(II->getNormalDest()->front())) {
3050 BasicBlock *OrigNormalDest = II->getNormalDest();
3054 Ctx, OrigNormalDest->
getName() +
".unreachable",
3055 II->getFunction(), OrigNormalDest);
3057 II->setNormalDest(UnreachableNormalDest);
3060 {{DominatorTree::Delete, BB, OrigNormalDest},
3061 {DominatorTree::Insert, BB, UnreachableNormalDest}});
3065 if (II->use_empty() && !II->mayHaveSideEffects()) {
3067 BasicBlock *NormalDestBB = II->getNormalDest();
3068 BasicBlock *UnwindDestBB = II->getUnwindDest();
3071 II->eraseFromParent();
3073 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
3079 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
3081 struct CatchPadDenseMapInfo {
3096 if (
LHS == getEmptyKey() ||
LHS == getTombstoneKey() ||
3097 RHS == getEmptyKey() ||
RHS == getTombstoneKey())
3099 return LHS->isIdenticalTo(
RHS);
3110 E = CatchSwitch->handler_end();
3114 ++NumPerSuccessorCases[HandlerBB];
3115 auto *CatchPad = cast<CatchPadInst>(HandlerBB->
getFirstNonPHI());
3116 if (!HandlerSet.insert({CatchPad, Empty}).second) {
3118 --NumPerSuccessorCases[HandlerBB];
3119 CatchSwitch->removeHandler(
I);
3126 std::vector<DominatorTree::UpdateType> Updates;
3127 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
3129 Updates.push_back({DominatorTree::Delete, BB,
I.first});
3130 DTU->applyUpdates(Updates);
3138 }
while (!Worklist.
empty());
3145 if (
auto *II = dyn_cast<InvokeInst>(TI))
3151 if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
3153 UnwindDest = CRI->getUnwindDest();
3154 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
3156 CatchSwitch->getParentPad(),
nullptr, CatchSwitch->getNumHandlers(),
3157 CatchSwitch->getName(), CatchSwitch->getIterator());
3158 for (
BasicBlock *PadBB : CatchSwitch->handlers())
3159 NewCatchSwitch->addHandler(PadBB);
3161 NewTI = NewCatchSwitch;
3162 UnwindDest = CatchSwitch->getUnwindDest();
3173 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
3186 if (Reachable.
size() ==
F.size())
3195 if (Reachable.
count(&BB))
3200 BlocksToRemove.
insert(&BB);
3203 if (BlocksToRemove.
empty())
3207 NumRemoved += BlocksToRemove.
size();
3220 K->dropUnknownNonDebugMetadata(KnownIDs);
3221 K->getAllMetadataOtherThanDebugLoc(
Metadata);
3223 unsigned Kind = MD.first;
3229 K->setMetadata(Kind,
nullptr);
3231 case LLVMContext::MD_dbg:
3233 case LLVMContext::MD_DIAssignID:
3234 K->mergeDIAssignID(J);
3236 case LLVMContext::MD_tbaa:
3239 case LLVMContext::MD_alias_scope:
3242 case LLVMContext::MD_noalias:
3243 case LLVMContext::MD_mem_parallel_loop_access:
3246 case LLVMContext::MD_access_group:
3247 K->setMetadata(LLVMContext::MD_access_group,
3250 case LLVMContext::MD_range:
3251 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3254 case LLVMContext::MD_fpmath:
3257 case LLVMContext::MD_invariant_load:
3261 K->setMetadata(Kind, JMD);
3263 case LLVMContext::MD_nonnull:
3264 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3265 K->setMetadata(Kind, JMD);
3267 case LLVMContext::MD_invariant_group:
3270 case LLVMContext::MD_align:
3271 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3275 case LLVMContext::MD_dereferenceable:
3276 case LLVMContext::MD_dereferenceable_or_null:
3278 K->setMetadata(Kind,
3281 case LLVMContext::MD_preserve_access_index:
3284 case LLVMContext::MD_noundef:
3287 K->setMetadata(Kind, JMD);
3289 case LLVMContext::MD_nontemporal:
3291 K->setMetadata(Kind, JMD);
3293 case LLVMContext::MD_prof:
3305 if (
auto *JMD = J->
getMetadata(LLVMContext::MD_invariant_group))
3306 if (isa<LoadInst>(K) || isa<StoreInst>(K))
3307 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
3312 unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
3313 LLVMContext::MD_alias_scope,
3314 LLVMContext::MD_noalias,
3315 LLVMContext::MD_range,
3316 LLVMContext::MD_fpmath,
3317 LLVMContext::MD_invariant_load,
3318 LLVMContext::MD_nonnull,
3319 LLVMContext::MD_invariant_group,
3320 LLVMContext::MD_align,
3321 LLVMContext::MD_dereferenceable,
3322 LLVMContext::MD_dereferenceable_or_null,
3323 LLVMContext::MD_access_group,
3324 LLVMContext::MD_preserve_access_index,
3325 LLVMContext::MD_prof,
3326 LLVMContext::MD_nontemporal,
3327 LLVMContext::MD_noundef};
3333 Source.getAllMetadata(MD);
3336 const DataLayout &
DL = Source.getModule()->getDataLayout();
3337 for (
const auto &MDPair : MD) {
3338 unsigned ID = MDPair.first;
3348 case LLVMContext::MD_dbg:
3349 case LLVMContext::MD_tbaa:
3350 case LLVMContext::MD_prof:
3351 case LLVMContext::MD_fpmath:
3352 case LLVMContext::MD_tbaa_struct:
3353 case LLVMContext::MD_invariant_load:
3354 case LLVMContext::MD_alias_scope:
3355 case LLVMContext::MD_noalias:
3356 case LLVMContext::MD_nontemporal:
3357 case LLVMContext::MD_mem_parallel_loop_access:
3358 case LLVMContext::MD_access_group:
3359 case LLVMContext::MD_noundef:
3364 case LLVMContext::MD_nonnull:
3368 case LLVMContext::MD_align:
3369 case LLVMContext::MD_dereferenceable:
3370 case LLVMContext::MD_dereferenceable_or_null:
3376 case LLVMContext::MD_range:
3384 auto *ReplInst = dyn_cast<Instruction>(Repl);
3393 if (isa<OverflowingBinaryOperator>(ReplInst) &&
3400 else if (!isa<LoadInst>(
I))
3401 ReplInst->andIRFlags(
I);
3415template <
typename RootType,
typename DominatesFn>
3417 const RootType &Root,
3418 const DominatesFn &Dominates) {
3423 if (!Dominates(Root, U))
3427 dbgs() <<
"' with " << *To <<
" in " << *U.getUser() <<
"\n");
3436 auto *BB =
From->getParent();
3440 auto *
I = cast<Instruction>(U.getUser());
3441 if (
I->getParent() == BB)
3455 return ::replaceDominatedUsesWith(
From, To, Root, Dominates);
3461 auto Dominates = [&DT](
const BasicBlock *BB,
const Use &U) {
3464 return ::replaceDominatedUsesWith(
From, To, BB, Dominates);
3470 if (Call->hasFnAttr(
"gc-leaf-function"))
3472 if (
const Function *
F = Call->getCalledFunction()) {
3473 if (
F->hasFnAttribute(
"gc-leaf-function"))
3476 if (
auto IID =
F->getIntrinsicID()) {
3478 return IID != Intrinsic::experimental_gc_statepoint &&
3479 IID != Intrinsic::experimental_deoptimize &&
3480 IID != Intrinsic::memcpy_element_unordered_atomic &&
3481 IID != Intrinsic::memmove_element_unordered_atomic;
3498 auto *NewTy = NewLI.
getType();
3501 if (NewTy->isPointerTy()) {
3508 if (!NewTy->isIntegerTy())
3513 auto *ITy = cast<IntegerType>(NewTy);
3523 auto *NewTy = NewLI.
getType();
3525 if (NewTy == OldLI.
getType()) {
3534 if (!NewTy->isPointerTy())
3537 unsigned BitWidth =
DL.getPointerTypeSizeInBits(NewTy);
3549 for (
auto *DII : DbgUsers)
3551 for (
auto *DPV : DPUsers)
3552 DPV->eraseFromParent();
3581 I->dropUBImplyingAttrsAndMetadata();
3582 if (
I->isUsedByMetadata())
3585 I->dropDbgRecords();
3586 if (
I->isDebugOrPseudoInst()) {
3588 II =
I->eraseFromParent();
3602 const APInt &API = cast<ConstantInt>(&CV)->getValue();
3603 std::optional<int64_t> InitIntOpt = API.
trySExtValue();
3605 static_cast<uint64_t>(*InitIntOpt))
3609 if (isa<ConstantInt>(
C))
3610 return createIntegerExpression(
C);
3612 auto *
FP = dyn_cast<ConstantFP>(&
C);
3622 if (isa<ConstantPointerNull>(
C))
3626 if (CE->getOpcode() == Instruction::IntToPtr) {
3627 const Value *V = CE->getOperand(0);
3628 if (
auto CI = dyn_cast_or_null<ConstantInt>(V))
3629 return createIntegerExpression(*CI);
3639 BitPart(
Value *
P,
unsigned BW) : Provider(
P) {
3640 Provenance.resize(BW);
3650 enum { Unset = -1 };
3682static const std::optional<BitPart> &
3684 std::map<
Value *, std::optional<BitPart>> &BPS,
int Depth,
3686 auto I = BPS.find(V);
3690 auto &Result = BPS[V] = std::nullopt;
3691 auto BitWidth = V->getType()->getScalarSizeInBits();
3699 LLVM_DEBUG(
dbgs() <<
"collectBitParts max recursion depth reached.\n");
3703 if (
auto *
I = dyn_cast<Instruction>(V)) {
3711 Depth + 1, FoundRoot);
3712 if (!
A || !
A->Provider)
3716 Depth + 1, FoundRoot);
3717 if (!
B ||
A->Provider !=
B->Provider)
3721 Result = BitPart(
A->Provider,
BitWidth);
3722 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx) {
3723 if (
A->Provenance[BitIdx] != BitPart::Unset &&
3724 B->Provenance[BitIdx] != BitPart::Unset &&
3725 A->Provenance[BitIdx] !=
B->Provenance[BitIdx])
3726 return Result = std::nullopt;
3728 if (
A->Provenance[BitIdx] == BitPart::Unset)
3729 Result->Provenance[BitIdx] =
B->Provenance[BitIdx];
3731 Result->Provenance[BitIdx] =
A->Provenance[BitIdx];
3739 const APInt &BitShift = *
C;
3746 if (!MatchBitReversals && (BitShift.
getZExtValue() % 8) != 0)
3750 Depth + 1, FoundRoot);
3756 auto &
P = Result->Provenance;
3757 if (
I->getOpcode() == Instruction::Shl) {
3771 const APInt &AndMask = *
C;
3775 unsigned NumMaskedBits = AndMask.
popcount();
3776 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3780 Depth + 1, FoundRoot);
3785 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3787 if (AndMask[BitIdx] == 0)
3788 Result->Provenance[BitIdx] = BitPart::Unset;
3795 Depth + 1, FoundRoot);
3799 Result = BitPart(Res->Provider,
BitWidth);
3800 auto NarrowBitWidth =
X->getType()->getScalarSizeInBits();
3801 for (
unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3802 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3803 for (
unsigned BitIdx = NarrowBitWidth; BitIdx <
BitWidth; ++BitIdx)
3804 Result->Provenance[BitIdx] = BitPart::Unset;
3811 Depth + 1, FoundRoot);
3815 Result = BitPart(Res->Provider,
BitWidth);
3816 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3817 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3825 Depth + 1, FoundRoot);
3829 Result = BitPart(Res->Provider,
BitWidth);
3830 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3831 Result->Provenance[(
BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3838 Depth + 1, FoundRoot);
3843 Result = BitPart(Res->Provider,
BitWidth);
3844 for (
unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3845 unsigned ByteBitOfs = ByteIdx * 8;
3846 for (
unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3847 Result->Provenance[(
BitWidth - 8 - ByteBitOfs) + BitIdx] =
3848 Res->Provenance[ByteBitOfs + BitIdx];
3865 if (!MatchBitReversals && (ModAmt % 8) != 0)
3870 Depth + 1, FoundRoot);
3871 if (!
LHS || !
LHS->Provider)
3875 Depth + 1, FoundRoot);
3876 if (!
RHS ||
LHS->Provider !=
RHS->Provider)
3879 unsigned StartBitRHS =
BitWidth - ModAmt;
3881 for (
unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3882 Result->Provenance[BitIdx + ModAmt] =
LHS->Provenance[BitIdx];
3883 for (
unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3884 Result->Provenance[BitIdx] =
RHS->Provenance[BitIdx + StartBitRHS];
3898 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3899 Result->Provenance[BitIdx] = BitIdx;
3905 if (
From % 8 != To % 8)
3920 Instruction *
I,
bool MatchBSwaps,
bool MatchBitReversals,
3927 if (!MatchBSwaps && !MatchBitReversals)
3929 Type *ITy =
I->getType();
3934 bool FoundRoot =
false;
3935 std::map<Value *, std::optional<BitPart>> BPS;
3942 [](int8_t
I) {
return I == BitPart::Unset || 0 <=
I; }) &&
3943 "Illegal bit provenance index");
3946 Type *DemandedTy = ITy;
3947 if (BitProvenance.
back() == BitPart::Unset) {
3948 while (!BitProvenance.
empty() && BitProvenance.
back() == BitPart::Unset)
3949 BitProvenance = BitProvenance.
drop_back();
3950 if (BitProvenance.
empty())
3953 if (
auto *IVecTy = dyn_cast<VectorType>(ITy))
3954 DemandedTy = VectorType::get(DemandedTy, IVecTy);
3965 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3966 bool OKForBitReverse = MatchBitReversals;
3967 for (
unsigned BitIdx = 0;
3968 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3969 if (BitProvenance[BitIdx] == BitPart::Unset) {
3976 BitIdx, DemandedBW);
3981 Intrin = Intrinsic::bswap;
3982 else if (OKForBitReverse)
3983 Intrin = Intrinsic::bitreverse;
3988 Value *Provider = Res->Provider;
3991 if (DemandedTy != Provider->
getType()) {
4002 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
4008 if (ITy != Result->getType()) {
4025 if (
F && !
F->hasLocalLinkage() &&
F->hasName() &&
4027 !
F->doesNotAccessMemory())
4033 if (
I->getOperand(OpIdx)->getType()->isMetadataTy())
4037 if (!isa<Constant>(
I->getOperand(OpIdx)))
4040 switch (
I->getOpcode()) {
4043 case Instruction::Call:
4044 case Instruction::Invoke: {
4045 const auto &CB = cast<CallBase>(*
I);
4048 if (CB.isInlineAsm())
4053 if (CB.isBundleOperand(OpIdx))
4056 if (OpIdx < CB.arg_size()) {
4059 if (isa<IntrinsicInst>(CB) &&
4060 OpIdx >= CB.getFunctionType()->getNumParams()) {
4062 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
4067 if (CB.getIntrinsicID() == Intrinsic::gcroot)
4071 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
4076 return !isa<IntrinsicInst>(CB);
4078 case Instruction::ShuffleVector:
4081 case Instruction::Switch:
4082 case Instruction::ExtractValue:
4085 case Instruction::InsertValue:
4088 case Instruction::Alloca:
4092 return !cast<AllocaInst>(
I)->isStaticAlloca();
4093 case Instruction::GetElementPtr:
4097 for (
auto E = std::next(It, OpIdx); It !=
E; ++It)
4106 if (
Constant *
C = dyn_cast<Constant>(Condition))
4110 Value *NotCondition;
4112 return NotCondition;
4115 Instruction *Inst = dyn_cast<Instruction>(Condition);
4118 else if (
Argument *Arg = dyn_cast<Argument>(Condition))
4120 assert(Parent &&
"Unsupported condition to invert");
4131 if (Inst && !isa<PHINode>(Inst))
4132 Inverted->insertAfter(Inst);
4142 bool Changed =
false;
4144 if (!
F.hasFnAttribute(Attribute::NoSync) &&
4145 F.doesNotAccessMemory() && !
F.isConvergent()) {
4151 if (!
F.hasFnAttribute(Attribute::NoFree) &&
F.onlyReadsMemory()) {
4152 F.setDoesNotFreeMemory();
4157 if (!
F.hasFnAttribute(Attribute::MustProgress) &&
F.willReturn()) {
4158 F.setMustProgress();
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static unsigned getIntrinsicID(const SDNode *N)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
ReachingDefAnalysis InstSet & ToRemove
static bool isEqual(const Function &Caller, const Function &Callee)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
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 DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file contains constants used for implementing Dwarf debug support.
static unsigned getHashValueImpl(SimpleValue Val)
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Rewrite Partial Register Uses
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
Module.h This file contains the declarations for the Module class.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
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.
APInt bitcastToAPInt() const
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
uint64_t getZExtValue() const
Get zero extended value.
unsigned popcount() const
Count the number of bits set.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
std::optional< int64_t > trySExtValue() const
Get sign extended value if possible.
int64_t getSExtValue() const
Get sign extended value.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
an instruction to allocate memory on the stack
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
This class represents an incoming formal argument to a Function.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
const T & back() const
back - Get the last element.
size_t size() const
size - Get the array size.
ArrayRef< T > drop_back(size_t N=1) const
Drop the last N elements of the array.
bool empty() const
empty - Check if the array is empty.
Value handle that asserts if the Value is deleted.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
InstListType::const_iterator getFirstNonPHIIt() const
Iterator returning form of getFirstNonPHI.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
const Instruction & front() const
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
void insertDbgRecordAfter(DbgRecord *DPV, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
void flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
void insertDbgRecordBefore(DbgRecord *DPV, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
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...
bool hasNPredecessorsOrMore(unsigned N) const
Return true if this block has N predecessors or more.
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
const Instruction & back() const
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
static BinaryOperator * CreateNot(Value *Op, const Twine &Name, BasicBlock::iterator InsertBefore)
This class represents a no-op cast from one type to another.
The address of a basic block.
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setCallingConv(CallingConv::ID CC)
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
CallingConv::ID getCallingConv() const
Value * getCalledOperand() const
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
FunctionType * getFunctionType() const
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
AttributeList getAttributes() const
Return the parameter attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
static CastInst * CreateIntegerCast(Value *S, Type *Ty, bool isSigned, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a ZExt, BitCast, or Trunc for int -> int casts.
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr, BasicBlock::iterator InsertBefore)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB, BasicBlock::iterator InsertBefore)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getPredicate() const
Return the predicate for this instruction.
A constant value that is initialized with an expression using other constant values.
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getNot(Constant *C)
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
This is the shared class of boolean and integer constants.
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
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 destroyConstant()
Called if some element of this constant is no longer valid.
DIExpression * createConstantValueExpression(uint64_t Val)
Create an expression for a variable that does not have an address, but does have a constant value.
static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
unsigned getNumElements() const
static ExtOps getExtOps(unsigned FromSize, unsigned ToSize, bool Signed)
Returns the ops for a zero- or sign-extension in a DIExpression.
static void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)
Append Ops with operations to apply the Offset.
static DIExpression * appendOpsToArg(const DIExpression *Expr, ArrayRef< uint64_t > Ops, unsigned ArgNo, bool StackValue=false)
Create a copy of Expr by appending the given list of Ops to each instance of the operand DW_OP_LLVM_a...
static std::optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
uint64_t getElement(unsigned I) const
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
static DIExpression * appendExt(const DIExpression *Expr, unsigned FromSize, unsigned ToSize, bool Signed)
Append a zero- or sign-extension to Expr.
std::optional< DIBasicType::Signedness > getSignedness() const
Return the signedness of this variable's type, or std::nullopt if this type is neither signed nor uns...
Instruction * MarkedInstr
Link back to the Instruction that owns this marker.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
DIExpression * getExpression() const
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
unsigned getNumVariableLocationOps() const
void setExpression(DIExpression *NewExpr)
std::optional< uint64_t > getFragmentSizeInBits() const
Get the size (in bits) of the variable, or fragment of the variable that is described.
Value * getVariableLocationOp(unsigned OpIdx) const
DILocalVariable * getVariable() const
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
bool isAddressOfVariable() const
Does this describe the address of a local variable.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
This represents the llvm.dbg.label instruction.
This represents the llvm.dbg.value instruction.
This is the common base class for debug info intrinsics for variables.
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue)
Value * getVariableLocationOp(unsigned OpIdx) const
void setExpression(DIExpression *NewExpr)
DILocalVariable * getVariable() const
unsigned getNumVariableLocationOps() const
bool isAddressOfVariable() const
Does this describe the address of a local variable.
std::optional< uint64_t > getFragmentSizeInBits() const
Get the size (in bits) of the variable, or fragment of the variable that is described.
DIExpression * getExpression() const
DILocation * get() const
Get the underlying DILocation.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasDomTree() const
Returns true if it holds a DominatorTree.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
const BasicBlock & getEntryBlock() const
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
bool extractProfTotalWeight(uint64_t &TotalVal) const
Retrieve total raw weight values of a branch.
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool isIdenticalToWhenDefined(const Instruction *I) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
A wrapper class for inspecting calls to intrinsic functions.
BasicBlock * getUnwindDest() const
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, BasicBlock::iterator InsertBefore)
BasicBlock * getNormalDest() const
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
Value * getPointerOperand()
MDNode * createRange(const APInt &Lo, const APInt &Hi)
Return metadata describing the range [Lo, Hi).
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
static MDNode * getMergedProfMetadata(MDNode *A, MDNode *B, const Instruction *AInstr, const Instruction *BInstr)
Merge !prof metadata from two instructions.
static MDNode * getMostGenericFPMath(MDNode *A, MDNode *B)
static MDNode * getMostGenericRange(MDNode *A, MDNode *B)
static MDNode * intersect(MDNode *A, MDNode *B)
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
This class implements a map that also provides access to all stored values in a deterministic order.
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
A Module instance is used to store all the information related to an LLVM module.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
const_block_iterator block_begin() const
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
void setIncomingValue(unsigned i, Value *V)
const_block_iterator block_end() const
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.
T get() const
Returns the value of the specified pointer type.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
size_type size() const
Determine the number of elements in the SetVector.
Vector takeVector()
Clear the SetVector and return the underlying vector.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
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 reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
iterator insert(iterator I, T &&Elt)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Provides information about what library functions are available for the current target.
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
static constexpr TypeSize getFixed(ScalarTy ExactSize)
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.
bool isArrayTy() const
True if this is an instance of ArrayType.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
bool isPointerTy() const
True if this is an instance of PointerType.
bool isFloatTy() const
Return true if this is 'float', a 32-bit IEEE fp type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isStructTy() const
True if this is an instance of StructType.
bool isDoubleTy() const
Return true if this is 'double', a 64-bit IEEE fp type.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isTokenTy() const
Return true if this is 'token'.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
value_op_iterator value_op_end()
Value * getOperand(unsigned i) const
value_op_iterator value_op_begin()
iterator find(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
LLVMContext & getContext() const
All values hold a context through their type.
static constexpr unsigned MaxAlignmentExponent
The maximum alignment for instructions.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
std::pair< iterator, bool > insert(const ValueT &V)
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
CastOperator_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bind_ty< WithOverflowInst > m_WithOverflowInst(WithOverflowInst *&I)
Match a with overflow intrinsic, capturing it if we match.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
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)
@ DW_OP_LLVM_arg
Only used in LLVM metadata.
@ ebStrict
This corresponds to "fpexcept.strict".
This is an optimization pass for GlobalISel generic memory operations.
void salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns, ArrayRef< DPValue * > DPInsns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
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 RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool succ_empty(const Instruction *I)
BasicBlock * changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge, DomTreeUpdater *DTU=nullptr)
Convert the CallInst to InvokeInst with the specified unwind edge basic block.
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...
TinyPtrVector< DbgDeclareInst * > findDbgDeclares(Value *V)
Finds dbg.declare intrinsics declaring local variables as living in the memory that 'V' points to.
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
CallInst * changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoke into a normal call.
bool isMathLibCallNoop(const CallBase *Call, const TargetLibraryInfo *TLI)
Check whether the given call has no side-effects.
void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source)
Copy the metadata from the source instruction to the destination (the replacement for the source inst...
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
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...
bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)
Compute the access-group list of access groups that Inst1 and Inst2 are both in.
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
bool handleUnreachableTerminator(Instruction *I, SmallVectorImpl< Value * > &PoisonedValues)
If a terminator in an unreachable basic block has an operand of type Instruction, transform it into p...
bool canSimplifyInvokeNoUnwind(const Function *F)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
Interval::pred_iterator pred_end(Interval *I)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
bool wouldInstructionBeTriviallyDeadOnUnusedPaths(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction has no side effects on any paths other than whe...
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
DIExpression * getExpressionForConstant(DIBuilder &DIB, const Constant &C, Type &Ty)
Given a constant, create a debug information expression.
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information,...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
TinyPtrVector< DPValue * > findDPVDeclares(Value *V)
As above, for DPVDeclares.
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII)
Produce a DebugLoc to use for each dbg.declare that is promoted to a dbg.value.
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V, SmallVectorImpl< DPValue * > *DPValues=nullptr)
Finds the debug info intrinsics describing a value.
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a range metadata node to a new load instruction.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DPValue * > *DPValues=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset=0)
Replaces multiple llvm.dbg.value instructions when the alloca it describes is replaced with a new val...
Align tryEnforceAlignment(Value *V, Align PrefAlign, const DataLayout &DL)
If the specified pointer points to an object that we control, try to modify the object's alignment to...
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow instructions that are not...
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
gep_type_iterator gep_type_begin(const User *GEP)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, const TargetLibraryInfo *TLI)
Given a CallInst, check if it calls a string function known to CodeGen, and mark it with NoBuiltin if...
unsigned pred_size(const MachineBasicBlock *BB)
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DPValue types only and downcast.
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
bool replaceDbgDeclare(Value *Address, Value *NewAddress, DIBuilder &Builder, uint8_t DIExprFlags, int Offset)
Replaces llvm.dbg.declare instruction when the address it describes is replaced with a new value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This struct is a compact representation of a valid (non-zero power of two) alignment.
An information struct used to provide DenseMap with the various necessary components for a given valu...
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
unsigned getBitWidth() const
Get the bit width of this value.
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.