59#include "llvm/IR/IntrinsicsWebAssembly.h"
93#define DEBUG_TYPE "local"
95STATISTIC(NumRemoved,
"Number of unreachable basic blocks removed");
96STATISTIC(NumPHICSEs,
"Number of PHI's that got CSE'd");
100#ifdef EXPENSIVE_CHECKS
106 cl::desc(
"Perform extra assertion checking to verify that PHINodes's hash "
107 "function is well-behaved w.r.t. its isEqual predicate"));
112 "When the basic block contains not more than this number of PHI nodes, "
113 "perform a (faster!) exhaustive search instead of set-driven one."));
137 if (
auto *BI = dyn_cast<BranchInst>(
T)) {
138 if (BI->isUnconditional())
return false;
143 if (Dest2 == Dest1) {
149 assert(BI->getParent() &&
"Terminator not inserted in block!");
156 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
157 LLVMContext::MD_annotation});
160 BI->eraseFromParent();
161 if (DeleteDeadConditions)
166 if (
auto *
Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
180 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
181 LLVMContext::MD_annotation});
183 BI->eraseFromParent();
185 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
192 if (
auto *SI = dyn_cast<SwitchInst>(
T)) {
195 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
196 BasicBlock *DefaultDest = SI->getDefaultDest();
201 SI->getNumCases() > 0) {
202 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
205 bool Changed =
false;
208 for (
auto It = SI->case_begin(),
End = SI->case_end(); It !=
End;) {
210 if (It->getCaseValue() == CI) {
211 TheOnlyDest = It->getCaseSuccessor();
217 if (It->getCaseSuccessor() == DefaultDest) {
219 unsigned NCases = SI->getNumCases();
222 if (NCases > 1 && MD) {
228 unsigned Idx = It->getCaseIndex();
230 Weights[0] += Weights[
Idx + 1];
239 It = SI->removeCase(It);
240 End = SI->case_end();
244 if (
auto *NewCI = dyn_cast<ConstantInt>(SI->getCondition())) {
246 It = SI->case_begin();
256 if (It->getCaseSuccessor() != TheOnlyDest)
257 TheOnlyDest =
nullptr;
263 if (CI && !TheOnlyDest) {
266 TheOnlyDest = SI->getDefaultDest();
281 if (DTU && Succ != TheOnlyDest)
282 RemovedSuccessors.
insert(Succ);
284 if (Succ == SuccToKeep) {
285 SuccToKeep =
nullptr;
293 SI->eraseFromParent();
294 if (DeleteDeadConditions)
297 std::vector<DominatorTree::UpdateType> Updates;
298 Updates.reserve(RemovedSuccessors.
size());
299 for (
auto *RemovedSuccessor : RemovedSuccessors)
300 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
306 if (SI->getNumCases() == 1) {
309 auto FirstCase = *SI->case_begin();
311 FirstCase.getCaseValue(),
"cond");
315 FirstCase.getCaseSuccessor(),
316 SI->getDefaultDest());
328 MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
330 NewBr->
setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
333 SI->eraseFromParent();
339 if (
auto *IBI = dyn_cast<IndirectBrInst>(
T)) {
342 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
343 BasicBlock *TheOnlyDest = BA->getBasicBlock();
350 for (
unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
352 if (DTU && DestBB != TheOnlyDest)
353 RemovedSuccessors.
insert(DestBB);
354 if (IBI->getDestination(i) == SuccToKeep) {
355 SuccToKeep =
nullptr;
360 Value *Address = IBI->getAddress();
361 IBI->eraseFromParent();
362 if (DeleteDeadConditions)
369 BA->destroyConstant();
380 std::vector<DominatorTree::UpdateType> Updates;
381 Updates.reserve(RemovedSuccessors.
size());
382 for (
auto *RemovedSuccessor : RemovedSuccessors)
383 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
412 if (
II->getIntrinsicID() == Intrinsic::stacksave ||
413 II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
414 II->isLifetimeStartOrEnd())
421 if (
I->isTerminator())
430 if (isa<DbgVariableIntrinsic>(
I))
439 if (
auto *CB = dyn_cast<CallBase>(
I))
443 if (!
I->willReturn()) {
444 auto *
II = dyn_cast<IntrinsicInst>(
I);
448 switch (
II->getIntrinsicID()) {
449 case Intrinsic::experimental_guard: {
453 auto *
Cond = dyn_cast<ConstantInt>(
II->getArgOperand(0));
458 case Intrinsic::wasm_trunc_signed:
459 case Intrinsic::wasm_trunc_unsigned:
460 case Intrinsic::ptrauth_auth:
461 case Intrinsic::ptrauth_resign:
468 if (!
I->mayHaveSideEffects())
475 if (
II->getIntrinsicID() == Intrinsic::stacksave ||
476 II->getIntrinsicID() == Intrinsic::launder_invariant_group)
481 if (
II->getIntrinsicID() == Intrinsic::allow_runtime_check ||
482 II->getIntrinsicID() == Intrinsic::allow_ubsan_check)
485 if (
II->isLifetimeStartOrEnd()) {
486 auto *Arg =
II->getArgOperand(1);
488 if (isa<UndefValue>(Arg))
492 if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
494 if (IntrinsicInst *IntrinsicUse =
495 dyn_cast<IntrinsicInst>(Use.getUser()))
496 return IntrinsicUse->isLifetimeStartOrEnd();
503 if (
II->getIntrinsicID() == Intrinsic::assume &&
506 return !
Cond->isZero();
511 if (
auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(
I)) {
512 std::optional<fp::ExceptionBehavior> ExBehavior =
513 FPI->getExceptionBehavior();
518 if (
auto *Call = dyn_cast<CallBase>(
I)) {
520 if (
Constant *
C = dyn_cast<Constant>(FreedOp))
521 return C->isNullValue() || isa<UndefValue>(
C);
527 if (
auto *LI = dyn_cast<LoadInst>(
I))
528 if (
auto *GV = dyn_cast<GlobalVariable>(
529 LI->getPointerOperand()->stripPointerCasts()))
530 if (!LI->isVolatile() && GV->isConstant())
542 std::function<
void(
Value *)> AboutToDeleteCallback) {
550 AboutToDeleteCallback);
558 std::function<
void(
Value *)> AboutToDeleteCallback) {
559 unsigned S = 0, E = DeadInsts.
size(), Alive = 0;
560 for (; S != E; ++S) {
561 auto *
I = dyn_cast_or_null<Instruction>(DeadInsts[S]);
563 DeadInsts[S] =
nullptr;
570 AboutToDeleteCallback);
577 std::function<
void(
Value *)> AboutToDeleteCallback) {
579 while (!DeadInsts.
empty()) {
585 "Live instruction found in dead worklist!");
586 assert(
I->use_empty() &&
"Instructions with uses are not dead.");
591 if (AboutToDeleteCallback)
592 AboutToDeleteCallback(
I);
596 for (
Use &OpU :
I->operands()) {
597 Value *OpV = OpU.get();
613 I->eraseFromParent();
621 for (
auto *DII : DbgUsers)
622 DII->setKillLocation();
623 for (
auto *DVR : DPUsers)
624 DVR->setKillLocation();
639 for (++UI; UI != UE; ++UI) {
656 I = cast<Instruction>(*
I->user_begin())) {
662 if (!Visited.
insert(
I).second) {
682 for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
683 Value *OpV =
I->getOperand(i);
684 I->setOperand(i,
nullptr);
697 I->eraseFromParent();
705 for (
User *U :
I->users()) {
707 WorkList.
insert(cast<Instruction>(U));
712 bool Changed =
false;
713 if (!
I->use_empty()) {
714 I->replaceAllUsesWith(SimpleV);
718 I->eraseFromParent();
733 bool MadeChange =
false;
750 assert(!BI->isTerminator());
760 while (!WorkList.
empty()) {
775 while (
PHINode *PN = dyn_cast<PHINode>(DestBB->
begin())) {
776 Value *NewVal = PN->getIncomingValue(0);
779 PN->replaceAllUsesWith(NewVal);
780 PN->eraseFromParent();
784 assert(PredBB &&
"Block doesn't have a single predecessor!");
798 if (PredOfPredBB != PredBB)
799 if (SeenPreds.
insert(PredOfPredBB).second)
800 Updates.
push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
803 if (SeenPreds.
insert(PredOfPredBB).second)
804 Updates.
push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
805 Updates.
push_back({DominatorTree::Delete, PredBB, DestBB});
835 "The successor list of PredBB isn't empty before "
836 "applying corresponding DTU updates.");
857 return First == Second || isa<UndefValue>(
First) || isa<UndefValue>(Second);
888 if (BBPreds.
count(IBB) &&
892 <<
"Can't fold, phi node " << PN->
getName() <<
" in "
893 << Succ->
getName() <<
" is conflicting with "
894 << BBPN->
getName() <<
" with regard to common predecessor "
906 if (BBPreds.
count(IBB) &&
910 <<
" is conflicting with regard to common "
911 <<
"predecessor " << IBB->
getName() <<
"\n");
938 if (!isa<UndefValue>(OldVal)) {
940 IncomingValues.
find(BB)->second == OldVal) &&
941 "Expected OldVal to match incoming value from BB!");
943 IncomingValues.
insert(std::make_pair(BB, OldVal));
948 if (It != IncomingValues.
end())
return It->second;
967 if (!isa<UndefValue>(V))
968 IncomingValues.
insert(std::make_pair(BB, V));
983 if (!isa<UndefValue>(V))
continue;
992 if (It == IncomingValues.
end()) {
1005 unsigned PoisonCount =
count_if(TrueUndefOps, [&](
unsigned i) {
1008 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.
size()) {
1009 for (
unsigned i : TrueUndefOps)
1024 if (BB->
phis().empty() || Succ->
phis().empty())
1033 if (BBPreds.
count(SuccPred)) {
1036 CommonPred = SuccPred;
1056 assert(OldVal &&
"No entry in PHI for Pred BB!");
1073 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->
getParent() == BB) {
1074 PHINode *OldValPN = cast<PHINode>(OldVal);
1083 if (PredBB == CommonPred)
1098 for (
unsigned i = 0, e = BBPreds.
size(); i != e; ++i) {
1103 if (PredBB == CommonPred)
1123 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1140 bool BBPhisMergeable =
1144 if (!BBKillable && !BBPhisMergeable)
1164 while (isa<PHINode>(*BBI)) {
1165 for (
Use &U : BBI->uses()) {
1166 if (
PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1167 if (PN->getIncomingBlock(U) != BB)
1177 if (BBPhisMergeable && CommonPred)
1179 <<
" and " << Succ->
getName() <<
" : "
1180 << CommonPred->
getName() <<
"\n");
1248 if (TI->hasMetadata(LLVMContext::MD_loop))
1251 if (PredTI->hasMetadata(LLVMContext::MD_loop))
1256 else if (BBPhisMergeable)
1271 if (SeenPreds.
insert(PredOfBB).second)
1272 Updates.
push_back({DominatorTree::Insert, PredOfBB, Succ});
1280 if (SeenPreds.
insert(PredOfBB).second && PredOfBB != CommonPred)
1281 Updates.
push_back({DominatorTree::Delete, PredOfBB, BB});
1284 Updates.
push_back({DominatorTree::Delete, BB, Succ});
1287 if (isa<PHINode>(Succ->
begin())) {
1307 while (
PHINode *PN = dyn_cast<PHINode>(&BB->
front())) {
1309 assert(PN->use_empty() &&
"There shouldn't be any uses here!");
1310 PN->eraseFromParent();
1317 if (
MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop))
1319 Pred->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
1334 "applying corresponding DTU updates.");
1335 }
else if (BBPhisMergeable) {
1338 if (
Instruction *UseInst = dyn_cast<Instruction>(U.getUser()))
1339 return UseInst->
getParent() != CommonPred &&
1340 BBPreds.
contains(UseInst->getParent());
1361 bool Changed =
false;
1366 for (
auto I = BB->
begin();
PHINode *PN = dyn_cast<PHINode>(
I);) {
1371 for (
auto J =
I;
PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1372 if (
ToRemove.contains(DuplicatePN))
1397 struct PHIDenseMapInfo {
1398 static PHINode *getEmptyKey() {
1402 static PHINode *getTombstoneKey() {
1407 return PN == getEmptyKey() || PN == getTombstoneKey();
1421 static unsigned getHashValue(
PHINode *PN) {
1436 return LHS->isIdenticalTo(
RHS);
1454 bool Changed =
false;
1455 for (
auto I = BB->
begin();
PHINode *PN = dyn_cast<PHINode>(
I++);) {
1458 auto Inserted = PHISet.
insert(PN);
1459 if (!Inserted.second) {
1462 PN->replaceAllUsesWith(*Inserted.first);
1491 PN->eraseFromParent();
1497 V = V->stripPointerCasts();
1499 if (
AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1505 Align CurrentAlign = AI->getAlign();
1506 if (PrefAlign <= CurrentAlign)
1507 return CurrentAlign;
1511 if (
DL.exceedsNaturalStackAlignment(PrefAlign))
1512 return CurrentAlign;
1513 AI->setAlignment(PrefAlign);
1517 if (
auto *GO = dyn_cast<GlobalObject>(V)) {
1519 Align CurrentAlign = GO->getPointerAlignment(
DL);
1520 if (PrefAlign <= CurrentAlign)
1521 return CurrentAlign;
1527 if (!GO->canIncreaseAlignment())
1528 return CurrentAlign;
1530 if (GO->isThreadLocal()) {
1531 unsigned MaxTLSAlign = GO->getParent()->getMaxTLSAlignment() / CHAR_BIT;
1532 if (MaxTLSAlign && PrefAlign >
Align(MaxTLSAlign))
1533 PrefAlign =
Align(MaxTLSAlign);
1536 GO->setAlignment(PrefAlign);
1548 assert(V->getType()->isPointerTy() &&
1549 "getOrEnforceKnownAlignment expects a pointer!");
1561 if (PrefAlign && *PrefAlign > Alignment)
1582 for (
auto *DVI : DbgValues) {
1584 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1587 for (
auto *DVR : DbgVariableRecords) {
1589 if ((DVR->getVariable() == DIVar) && (DVR->getExpression() == DIExpr))
1605 TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1606 if (std::optional<uint64_t> FragmentSize =
1616 "address of variable must have exactly 1 location operand.");
1619 if (std::optional<TypeSize> FragmentSize =
1620 AI->getAllocationSizeInBits(
DL)) {
1621 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1632 TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1633 if (std::optional<uint64_t> FragmentSize =
1643 "address of variable must have exactly 1 location operand.");
1646 if (std::optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(
DL)) {
1647 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1661 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1670 Instr->getParent()->insertDbgRecordBefore(DV, Instr);
1678 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1687 Instr->getParent()->insertDbgRecordAfter(DV, &*Instr);
1697 assert(DIVar &&
"Missing variable");
1699 Value *DV = SI->getValueOperand();
1716 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1726 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DII
1742 assert(DIVar &&
"Missing variable");
1748 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1767 assert(DIVar &&
"Missing variable");
1769 Value *DV = SI->getValueOperand();
1786 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1796 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DVR
1807 SI->getParent()->insertDbgRecordBefore(NewDVR, SI->getIterator());
1816 assert(DIVar &&
"Missing variable");
1825 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1838 if (InsertionPt != BB->
end()) {
1848 assert(DIVar &&
"Missing variable");
1854 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: "
1871 LI->
getParent()->insertDbgRecordAfter(DV, LI);
1888 assert(DIVar &&
"Missing variable");
1897 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: "
1910 if (InsertionPt != BB->
end()) {
1919 bool Changed =
false;
1923 for (
auto &FI :
F) {
1925 if (
auto *DDI = dyn_cast<DbgDeclareInst>(&BI))
1928 if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
1937 auto LowerOne = [&](
auto *DDI) {
1939 dyn_cast_or_null<AllocaInst>(DDI->getVariableLocationOp(0));
1951 if (LoadInst *LI = dyn_cast<LoadInst>(U))
1952 return LI->isVolatile();
1953 if (StoreInst *SI = dyn_cast<StoreInst>(U))
1954 return SI->isVolatile();
1961 while (!WorkList.
empty()) {
1963 for (
const auto &AIUse : V->uses()) {
1964 User *U = AIUse.getUser();
1965 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
1966 if (AIUse.getOperandNo() == 1)
1968 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
1970 }
else if (
CallInst *CI = dyn_cast<CallInst>(U)) {
1974 if (!CI->isLifetimeStartOrEnd()) {
1982 }
else if (
BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1983 if (BI->getType()->isPointerTy())
1988 DDI->eraseFromParent();
2008 assert(BB &&
"No BasicBlock to clone DbgVariableRecord(s) from.");
2009 if (InsertedPHIs.
size() == 0)
2014 for (
auto &
I : *BB) {
2016 for (
Value *V : DVR.location_ops())
2017 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2018 DbgValueMap.
insert({Loc, &DVR});
2021 if (DbgValueMap.
size() == 0)
2036 for (
auto PHI : InsertedPHIs) {
2041 for (
auto VI :
PHI->operand_values()) {
2042 auto V = DbgValueMap.
find(VI);
2043 if (V != DbgValueMap.
end()) {
2045 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2046 if (NewDI == NewDbgValueMap.
end()) {
2048 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2059 for (
auto DI : NewDbgValueMap) {
2063 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2072 assert(BB &&
"No BasicBlock to clone dbg.value(s) from.");
2073 if (InsertedPHIs.
size() == 0)
2080 for (
auto &
I : *BB) {
2081 if (
auto DbgII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
2082 for (
Value *V : DbgII->location_ops())
2083 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2084 DbgValueMap.
insert({Loc, DbgII});
2087 if (DbgValueMap.
size() == 0)
2102 for (
auto *
PHI : InsertedPHIs) {
2107 for (
auto *VI :
PHI->operand_values()) {
2108 auto V = DbgValueMap.
find(VI);
2109 if (V != DbgValueMap.
end()) {
2110 auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
2111 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2112 if (NewDI == NewDbgValueMap.
end()) {
2113 auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
2114 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2125 for (
auto DI : NewDbgValueMap) {
2127 auto *NewDbgII = DI.second;
2129 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2130 NewDbgII->insertBefore(&*InsertionPt);
2135 DIBuilder &Builder, uint8_t DIExprFlags,
2140 auto ReplaceOne = [&](
auto *DII) {
2141 assert(DII->getVariable() &&
"Missing variable");
2142 auto *DIExpr = DII->getExpression();
2144 DII->setExpression(DIExpr);
2145 DII->replaceVariableLocationOp(Address, NewAddress);
2151 return !DbgDeclares.
empty() || !DVRDeclares.
empty();
2160 assert(DIVar &&
"Missing variable");
2190 for (
auto *DVI : DbgUsers)
2192 DVI->getExpression(), NewAllocaAddress, DVI,
2193 nullptr, Builder,
Offset);
2198 DVR->getExpression(), NewAllocaAddress,
nullptr,
2212 Instruction *
I = dyn_cast<Instruction>(Assign->getAddress());
2217 assert(!Assign->getAddressExpression()->getFragmentInfo().has_value() &&
2218 "address-expression shouldn't have fragment info");
2231 Assign->getAddressExpression(), Ops, 0,
false);
2233 "address-expression shouldn't have fragment info");
2238 if (AdditionalValues.
empty()) {
2239 Assign->setAddress(NewV);
2240 Assign->setAddressExpression(SalvagedExpr);
2242 Assign->setKillAddress();
2252 const unsigned MaxDebugArgs = 16;
2253 const unsigned MaxExpressionSize = 128;
2254 bool Salvaged =
false;
2256 for (
auto *DII : DbgUsers) {
2257 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) {
2258 if (DAI->getAddress() == &
I) {
2262 if (DAI->getValue() != &
I)
2268 bool StackValue = isa<DbgValueInst>(DII);
2269 auto DIILocation = DII->location_ops();
2272 "DbgVariableIntrinsic must use salvaged instruction as its location");
2278 Value *Op0 =
nullptr;
2280 auto LocItr =
find(DIILocation, &
I);
2281 while (SalvagedExpr && LocItr != DIILocation.end()) {
2283 unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
2290 LocItr = std::find(++LocItr, DIILocation.end(), &
I);
2298 DII->replaceVariableLocationOp(&
I, Op0);
2299 bool IsValidSalvageExpr = SalvagedExpr->
getNumElements() <= MaxExpressionSize;
2300 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2301 DII->setExpression(SalvagedExpr);
2302 }
else if (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
2303 DII->getNumVariableLocationOps() + AdditionalValues.
size() <=
2305 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2310 DII->setKillLocation();
2316 for (
auto *DVR : DPUsers) {
2317 if (DVR->isDbgAssign()) {
2318 if (DVR->getAddress() == &
I) {
2322 if (DVR->getValue() != &
I)
2330 DVR->getType() != DbgVariableRecord::LocationType::Declare;
2331 auto DVRLocation = DVR->location_ops();
2334 "DbgVariableIntrinsic must use salvaged instruction as its location");
2340 Value *Op0 =
nullptr;
2342 auto LocItr =
find(DVRLocation, &
I);
2343 while (SalvagedExpr && LocItr != DVRLocation.end()) {
2345 unsigned LocNo = std::distance(DVRLocation.begin(), LocItr);
2352 LocItr = std::find(++LocItr, DVRLocation.end(), &
I);
2360 DVR->replaceVariableLocationOp(&
I, Op0);
2361 bool IsValidSalvageExpr =
2363 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2364 DVR->setExpression(SalvagedExpr);
2365 }
else if (DVR->getType() != DbgVariableRecord::LocationType::Declare &&
2366 IsValidSalvageExpr &&
2367 DVR->getNumVariableLocationOps() + AdditionalValues.
size() <=
2369 DVR->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2375 DVR->setKillLocation();
2384 for (
auto *DII : DbgUsers)
2385 DII->setKillLocation();
2387 for (
auto *DVR : DPUsers)
2388 DVR->setKillLocation();
2395 unsigned BitWidth =
DL.getIndexSizeInBits(
GEP->getPointerAddressSpace());
2399 if (!
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
2401 if (!VariableOffsets.
empty() && !CurrentLocOps) {
2402 Opcodes.
insert(Opcodes.
begin(), {dwarf::DW_OP_LLVM_arg, 0});
2405 for (
const auto &
Offset : VariableOffsets) {
2408 "Expected strictly positive multiplier for offset.");
2410 Offset.second.getZExtValue(), dwarf::DW_OP_mul,
2411 dwarf::DW_OP_plus});
2414 return GEP->getOperand(0);
2419 case Instruction::Add:
2420 return dwarf::DW_OP_plus;
2421 case Instruction::Sub:
2422 return dwarf::DW_OP_minus;
2423 case Instruction::Mul:
2424 return dwarf::DW_OP_mul;
2425 case Instruction::SDiv:
2426 return dwarf::DW_OP_div;
2427 case Instruction::SRem:
2428 return dwarf::DW_OP_mod;
2429 case Instruction::Or:
2430 return dwarf::DW_OP_or;
2431 case Instruction::And:
2432 return dwarf::DW_OP_and;
2433 case Instruction::Xor:
2434 return dwarf::DW_OP_xor;
2435 case Instruction::Shl:
2436 return dwarf::DW_OP_shl;
2437 case Instruction::LShr:
2438 return dwarf::DW_OP_shr;
2439 case Instruction::AShr:
2440 return dwarf::DW_OP_shra;
2451 if (!CurrentLocOps) {
2456 AdditionalValues.
push_back(
I->getOperand(1));
2463 auto *ConstInt = dyn_cast<ConstantInt>(BI->
getOperand(1));
2465 if (ConstInt && ConstInt->getBitWidth() > 64)
2471 uint64_t Val = ConstInt->getSExtValue();
2474 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2475 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2479 Opcodes.
append({dwarf::DW_OP_constu, Val});
2498 return dwarf::DW_OP_eq;
2500 return dwarf::DW_OP_ne;
2503 return dwarf::DW_OP_gt;
2506 return dwarf::DW_OP_ge;
2509 return dwarf::DW_OP_lt;
2512 return dwarf::DW_OP_le;
2522 auto *ConstInt = dyn_cast<ConstantInt>(Icmp->
getOperand(1));
2524 if (ConstInt && ConstInt->getBitWidth() > 64)
2532 uint64_t Val = ConstInt->getSExtValue();
2550 auto &M = *
I.getModule();
2551 auto &
DL = M.getDataLayout();
2553 if (
auto *CI = dyn_cast<CastInst>(&
I)) {
2554 Value *FromValue = CI->getOperand(0);
2556 if (CI->isNoopCast(
DL)) {
2565 !(isa<TruncInst>(&
I) || isa<SExtInst>(&
I) || isa<ZExtInst>(&
I) ||
2566 isa<IntToPtrInst>(&
I) || isa<PtrToIntInst>(&
I)))
2570 if (FromType->isPointerTy())
2571 FromType =
DL.getIntPtrType(FromType);
2573 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2578 Ops.
append(ExtOps.begin(), ExtOps.end());
2582 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
2584 if (
auto *BI = dyn_cast<BinaryOperator>(&
I))
2586 if (
auto *IC = dyn_cast<ICmpInst>(&
I))
2613 bool Changed =
false;
2617 if (isa<Instruction>(&To)) {
2618 bool DomPointAfterFrom =
From.getNextNonDebugInstruction() == &DomPoint;
2620 for (
auto *DII :
Users) {
2630 }
else if (!DT.
dominates(&DomPoint, DII)) {
2631 UndefOrSalvage.
insert(DII);
2636 for (
auto *DVR : DPUsers) {
2640 if (isa<DbgVariableIntrinsic>(NextNonDebug))
2643 if (DomPointAfterFrom && NextNonDebug == &DomPoint) {
2647 DomPoint.
getParent()->insertDbgRecordAfter(DVR, &DomPoint);
2649 }
else if (!DT.
dominates(&DomPoint, MarkedInstr)) {
2650 UndefOrSalvageDVR.
insert(DVR);
2656 for (
auto *DII :
Users) {
2657 if (UndefOrSalvage.
count(DII))
2669 for (
auto *DVR : DPUsers) {
2670 if (UndefOrSalvageDVR.
count(DVR))
2683 if (!UndefOrSalvage.
empty() || !UndefOrSalvageDVR.
empty()) {
2707 bool SameSize =
DL.getTypeSizeInBits(FromTy) ==
DL.getTypeSizeInBits(ToTy);
2708 bool LosslessConversion = !
DL.isNonIntegralPointerType(FromTy) &&
2709 !
DL.isNonIntegralPointerType(ToTy);
2710 return SameSize && LosslessConversion;
2720 if (!
From.isUsedByMetadata())
2723 assert(&
From != &To &&
"Can't replace something with itself");
2732 return DVR.getExpression();
2746 assert(FromBits != ToBits &&
"Unexpected no-op conversion");
2750 if (FromBits < ToBits)
2761 return std::nullopt;
2763 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2775 return std::nullopt;
2777 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2791 bool Changed =
false;
2793 I->dropDbgRecords();
2794 for (
Use &U :
I->operands()) {
2796 if (isa<Instruction>(
Op) && !
Op->getType()->isTokenTy()) {
2806std::pair<unsigned, unsigned>
2808 unsigned NumDeadInst = 0;
2809 unsigned NumDeadDbgInst = 0;
2816 while (EndInst != &BB->
front()) {
2828 if (isa<DbgInfoIntrinsic>(Inst))
2836 return {NumDeadInst, NumDeadDbgInst};
2852 Successor->removePredecessor(BB, PreserveLCSSA);
2857 UI->setDebugLoc(
I->getDebugLoc());
2860 unsigned NumInstrsRemoved = 0;
2862 while (BBI != BBE) {
2863 if (!BBI->use_empty())
2865 BBI++->eraseFromParent();
2871 for (
BasicBlock *UniqueSuccessor : UniqueSuccessors)
2872 Updates.
push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2876 return NumInstrsRemoved;
2882 II->getOperandBundlesAsDefs(OpBundles);
2884 II->getCalledOperand(), Args, OpBundles);
2895 auto NewWeights =
uint32_t(TotalWeight) != TotalWeight
2898 NewCall->
setMetadata(LLVMContext::MD_prof, NewWeights);
2909 II->replaceAllUsesWith(NewCall);
2919 II->eraseFromParent();
2921 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2950 UnwindEdge, InvokeArgs, OpBundles, CI->
getName(), BB);
2954 II->setMetadata(LLVMContext::MD_prof, CI->
getMetadata(LLVMContext::MD_prof));
2957 DTU->
applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2964 Split->front().eraseFromParent();
2975 bool Changed =
false;
2983 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
2984 Value *Callee = CI->getCalledOperand();
2986 if (
Function *
F = dyn_cast<Function>(Callee)) {
2987 auto IntrinsicID =
F->getIntrinsicID();
2992 if (IntrinsicID == Intrinsic::assume) {
2999 }
else if (IntrinsicID == Intrinsic::experimental_guard) {
3010 if (!isa<UnreachableInst>(CI->getNextNode())) {
3016 }
else if ((isa<ConstantPointerNull>(Callee) &&
3018 cast<PointerType>(Callee->getType())
3019 ->getAddressSpace())) ||
3020 isa<UndefValue>(Callee)) {
3025 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
3029 if (!isa<UnreachableInst>(CI->getNextNonDebugInstruction())) {
3036 }
else if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3042 if (SI->isVolatile())
continue;
3046 if (isa<UndefValue>(
Ptr) ||
3047 (isa<ConstantPointerNull>(
Ptr) &&
3049 SI->getPointerAddressSpace()))) {
3058 if (
auto *
II = dyn_cast<InvokeInst>(Terminator)) {
3060 Value *Callee =
II->getCalledOperand();
3061 if ((isa<ConstantPointerNull>(Callee) &&
3063 isa<UndefValue>(Callee)) {
3067 if (
II->doesNotReturn() &&
3068 !isa<UnreachableInst>(
II->getNormalDest()->front())) {
3078 Ctx, OrigNormalDest->
getName() +
".unreachable",
3079 II->getFunction(), OrigNormalDest);
3081 II->setNormalDest(UnreachableNormalDest);
3084 {{DominatorTree::Delete, BB, OrigNormalDest},
3085 {DominatorTree::Insert, BB, UnreachableNormalDest}});
3089 if (
II->use_empty() && !
II->mayHaveSideEffects()) {
3095 II->eraseFromParent();
3097 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
3103 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
3105 struct CatchPadDenseMapInfo {
3120 if (
LHS == getEmptyKey() ||
LHS == getTombstoneKey() ||
3121 RHS == getEmptyKey() ||
RHS == getTombstoneKey())
3123 return LHS->isIdenticalTo(
RHS);
3134 E = CatchSwitch->handler_end();
3138 ++NumPerSuccessorCases[HandlerBB];
3139 auto *CatchPad = cast<CatchPadInst>(HandlerBB->
getFirstNonPHI());
3140 if (!HandlerSet.insert({CatchPad, Empty}).second) {
3142 --NumPerSuccessorCases[HandlerBB];
3143 CatchSwitch->removeHandler(
I);
3150 std::vector<DominatorTree::UpdateType> Updates;
3151 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
3153 Updates.push_back({DominatorTree::Delete, BB,
I.first});
3154 DTU->applyUpdates(Updates);
3162 }
while (!Worklist.
empty());
3169 if (
auto *
II = dyn_cast<InvokeInst>(TI))
3175 if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
3177 UnwindDest = CRI->getUnwindDest();
3178 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
3180 CatchSwitch->getParentPad(),
nullptr, CatchSwitch->getNumHandlers(),
3181 CatchSwitch->getName(), CatchSwitch->getIterator());
3182 for (
BasicBlock *PadBB : CatchSwitch->handlers())
3183 NewCatchSwitch->addHandler(PadBB);
3185 NewTI = NewCatchSwitch;
3186 UnwindDest = CatchSwitch->getUnwindDest();
3197 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
3210 if (Reachable.
size() ==
F.size())
3219 if (Reachable.
count(&BB))
3224 BlocksToRemove.
insert(&BB);
3227 if (BlocksToRemove.
empty())
3231 NumRemoved += BlocksToRemove.
size();
3244 K->dropUnknownNonDebugMetadata(KnownIDs);
3245 K->getAllMetadataOtherThanDebugLoc(
Metadata);
3247 unsigned Kind = MD.first;
3253 K->setMetadata(Kind,
nullptr);
3255 case LLVMContext::MD_dbg:
3257 case LLVMContext::MD_DIAssignID:
3258 K->mergeDIAssignID(J);
3260 case LLVMContext::MD_tbaa:
3263 case LLVMContext::MD_alias_scope:
3266 case LLVMContext::MD_noalias:
3267 case LLVMContext::MD_mem_parallel_loop_access:
3270 case LLVMContext::MD_access_group:
3271 K->setMetadata(LLVMContext::MD_access_group,
3274 case LLVMContext::MD_range:
3275 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3278 case LLVMContext::MD_fpmath:
3281 case LLVMContext::MD_invariant_load:
3285 K->setMetadata(Kind, JMD);
3287 case LLVMContext::MD_nonnull:
3288 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3289 K->setMetadata(Kind, JMD);
3291 case LLVMContext::MD_invariant_group:
3294 case LLVMContext::MD_mmra:
3297 case LLVMContext::MD_align:
3298 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3302 case LLVMContext::MD_dereferenceable:
3303 case LLVMContext::MD_dereferenceable_or_null:
3305 K->setMetadata(Kind,
3308 case LLVMContext::MD_preserve_access_index:
3311 case LLVMContext::MD_noundef:
3314 K->setMetadata(Kind, JMD);
3316 case LLVMContext::MD_nontemporal:
3318 K->setMetadata(Kind, JMD);
3320 case LLVMContext::MD_prof:
3332 if (
auto *JMD = J->
getMetadata(LLVMContext::MD_invariant_group))
3333 if (isa<LoadInst>(K) || isa<StoreInst>(K))
3334 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
3339 auto JMMRA = J->
getMetadata(LLVMContext::MD_mmra);
3340 auto KMMRA = K->getMetadata(LLVMContext::MD_mmra);
3341 if (JMMRA || KMMRA) {
3342 K->setMetadata(LLVMContext::MD_mmra,
3349 unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
3350 LLVMContext::MD_alias_scope,
3351 LLVMContext::MD_noalias,
3352 LLVMContext::MD_range,
3353 LLVMContext::MD_fpmath,
3354 LLVMContext::MD_invariant_load,
3355 LLVMContext::MD_nonnull,
3356 LLVMContext::MD_invariant_group,
3357 LLVMContext::MD_align,
3358 LLVMContext::MD_dereferenceable,
3359 LLVMContext::MD_dereferenceable_or_null,
3360 LLVMContext::MD_access_group,
3361 LLVMContext::MD_preserve_access_index,
3362 LLVMContext::MD_prof,
3363 LLVMContext::MD_nontemporal,
3364 LLVMContext::MD_noundef,
3365 LLVMContext::MD_mmra};
3371 Source.getAllMetadata(MD);
3375 for (
const auto &MDPair : MD) {
3376 unsigned ID = MDPair.first;
3386 case LLVMContext::MD_dbg:
3387 case LLVMContext::MD_tbaa:
3388 case LLVMContext::MD_prof:
3389 case LLVMContext::MD_fpmath:
3390 case LLVMContext::MD_tbaa_struct:
3391 case LLVMContext::MD_invariant_load:
3392 case LLVMContext::MD_alias_scope:
3393 case LLVMContext::MD_noalias:
3394 case LLVMContext::MD_nontemporal:
3395 case LLVMContext::MD_mem_parallel_loop_access:
3396 case LLVMContext::MD_access_group:
3397 case LLVMContext::MD_noundef:
3402 case LLVMContext::MD_nonnull:
3406 case LLVMContext::MD_align:
3407 case LLVMContext::MD_dereferenceable:
3408 case LLVMContext::MD_dereferenceable_or_null:
3414 case LLVMContext::MD_range:
3422 auto *ReplInst = dyn_cast<Instruction>(Repl);
3431 if (isa<OverflowingBinaryOperator>(ReplInst) &&
3438 else if (!isa<LoadInst>(
I))
3439 ReplInst->andIRFlags(
I);
3453template <
typename RootType,
typename ShouldReplaceFn>
3455 const RootType &Root,
3456 const ShouldReplaceFn &ShouldReplace) {
3461 if (!ShouldReplace(Root, U))
3465 dbgs() <<
"' with " << *To <<
" in " << *U.getUser() <<
"\n");
3474 auto *BB =
From->getParent();
3478 auto *
I = cast<Instruction>(U.getUser());
3479 if (
I->getParent() == BB)
3493 return ::replaceDominatedUsesWith(
From, To, Root, Dominates);
3499 auto Dominates = [&DT](
const BasicBlock *BB,
const Use &U) {
3502 return ::replaceDominatedUsesWith(
From, To, BB, Dominates);
3508 auto DominatesAndShouldReplace =
3510 return DT.
dominates(Root, U) && ShouldReplace(U, To);
3512 return ::replaceDominatedUsesWith(
From, To, Root, DominatesAndShouldReplace);
3518 auto DominatesAndShouldReplace = [&DT, &ShouldReplace,
3520 return DT.
dominates(BB, U) && ShouldReplace(U, To);
3522 return ::replaceDominatedUsesWith(
From, To, BB, DominatesAndShouldReplace);
3528 if (Call->hasFnAttr(
"gc-leaf-function"))
3530 if (
const Function *
F = Call->getCalledFunction()) {
3531 if (
F->hasFnAttribute(
"gc-leaf-function"))
3534 if (
auto IID =
F->getIntrinsicID()) {
3536 return IID != Intrinsic::experimental_gc_statepoint &&
3537 IID != Intrinsic::experimental_deoptimize &&
3538 IID != Intrinsic::memcpy_element_unordered_atomic &&
3539 IID != Intrinsic::memmove_element_unordered_atomic;
3556 auto *NewTy = NewLI.
getType();
3559 if (NewTy->isPointerTy()) {
3566 if (!NewTy->isIntegerTy())
3571 auto *ITy = cast<IntegerType>(NewTy);
3581 auto *NewTy = NewLI.
getType();
3583 if (NewTy == OldLI.
getType()) {
3592 if (!NewTy->isPointerTy())
3595 unsigned BitWidth =
DL.getPointerTypeSizeInBits(NewTy);
3607 for (
auto *DII : DbgUsers)
3609 for (
auto *DVR : DPUsers)
3610 DVR->eraseFromParent();
3639 I->dropUBImplyingAttrsAndMetadata();
3640 if (
I->isUsedByMetadata())
3643 I->dropDbgRecords();
3644 if (
I->isDebugOrPseudoInst()) {
3646 II =
I->eraseFromParent();
3660 const APInt &API = cast<ConstantInt>(&CV)->getValue();
3661 std::optional<int64_t> InitIntOpt = API.
trySExtValue();
3663 static_cast<uint64_t>(*InitIntOpt))
3667 if (isa<ConstantInt>(
C))
3668 return createIntegerExpression(
C);
3670 auto *
FP = dyn_cast<ConstantFP>(&
C);
3682 if (isa<ConstantPointerNull>(
C))
3686 if (CE->getOpcode() == Instruction::IntToPtr) {
3687 const Value *V = CE->getOperand(0);
3688 if (
auto CI = dyn_cast_or_null<ConstantInt>(V))
3689 return createIntegerExpression(*CI);
3695 auto RemapDebugOperands = [&Mapping](
auto *DV,
auto Set) {
3696 for (
auto *
Op : Set) {
3698 if (
I != Mapping.
end())
3699 DV->replaceVariableLocationOp(
Op,
I->second,
true);
3702 auto RemapAssignAddress = [&Mapping](
auto *DA) {
3703 auto I = Mapping.
find(DA->getAddress());
3704 if (
I != Mapping.
end())
3705 DA->setAddress(
I->second);
3707 if (
auto DVI = dyn_cast<DbgVariableIntrinsic>(Inst))
3708 RemapDebugOperands(DVI, DVI->location_ops());
3709 if (
auto DAI = dyn_cast<DbgAssignIntrinsic>(Inst))
3710 RemapAssignAddress(DAI);
3712 RemapDebugOperands(&DVR, DVR.location_ops());
3713 if (DVR.isDbgAssign())
3714 RemapAssignAddress(&DVR);
3723 BitPart(
Value *
P,
unsigned BW) : Provider(
P) {
3724 Provenance.resize(BW);
3734 enum { Unset = -1 };
3766static const std::optional<BitPart> &
3768 std::map<
Value *, std::optional<BitPart>> &BPS,
int Depth,
3770 auto I = BPS.find(V);
3774 auto &Result = BPS[V] = std::nullopt;
3775 auto BitWidth = V->getType()->getScalarSizeInBits();
3783 LLVM_DEBUG(
dbgs() <<
"collectBitParts max recursion depth reached.\n");
3787 if (
auto *
I = dyn_cast<Instruction>(V)) {
3795 Depth + 1, FoundRoot);
3796 if (!
A || !
A->Provider)
3800 Depth + 1, FoundRoot);
3801 if (!
B ||
A->Provider !=
B->Provider)
3805 Result = BitPart(
A->Provider,
BitWidth);
3806 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx) {
3807 if (
A->Provenance[BitIdx] != BitPart::Unset &&
3808 B->Provenance[BitIdx] != BitPart::Unset &&
3809 A->Provenance[BitIdx] !=
B->Provenance[BitIdx])
3810 return Result = std::nullopt;
3812 if (
A->Provenance[BitIdx] == BitPart::Unset)
3813 Result->Provenance[BitIdx] =
B->Provenance[BitIdx];
3815 Result->Provenance[BitIdx] =
A->Provenance[BitIdx];
3823 const APInt &BitShift = *
C;
3830 if (!MatchBitReversals && (BitShift.
getZExtValue() % 8) != 0)
3834 Depth + 1, FoundRoot);
3840 auto &
P = Result->Provenance;
3841 if (
I->getOpcode() == Instruction::Shl) {
3855 const APInt &AndMask = *
C;
3859 unsigned NumMaskedBits = AndMask.
popcount();
3860 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3864 Depth + 1, FoundRoot);
3869 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3871 if (AndMask[BitIdx] == 0)
3872 Result->Provenance[BitIdx] = BitPart::Unset;
3879 Depth + 1, FoundRoot);
3883 Result = BitPart(Res->Provider,
BitWidth);
3884 auto NarrowBitWidth =
X->getType()->getScalarSizeInBits();
3885 for (
unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3886 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3887 for (
unsigned BitIdx = NarrowBitWidth; BitIdx <
BitWidth; ++BitIdx)
3888 Result->Provenance[BitIdx] = BitPart::Unset;
3895 Depth + 1, FoundRoot);
3899 Result = BitPart(Res->Provider,
BitWidth);
3900 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3901 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3909 Depth + 1, FoundRoot);
3913 Result = BitPart(Res->Provider,
BitWidth);
3914 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3915 Result->Provenance[(
BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3922 Depth + 1, FoundRoot);
3927 Result = BitPart(Res->Provider,
BitWidth);
3928 for (
unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3929 unsigned ByteBitOfs = ByteIdx * 8;
3930 for (
unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3931 Result->Provenance[(
BitWidth - 8 - ByteBitOfs) + BitIdx] =
3932 Res->Provenance[ByteBitOfs + BitIdx];
3949 if (!MatchBitReversals && (ModAmt % 8) != 0)
3954 Depth + 1, FoundRoot);
3955 if (!
LHS || !
LHS->Provider)
3959 Depth + 1, FoundRoot);
3960 if (!
RHS ||
LHS->Provider !=
RHS->Provider)
3963 unsigned StartBitRHS =
BitWidth - ModAmt;
3965 for (
unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3966 Result->Provenance[BitIdx + ModAmt] =
LHS->Provenance[BitIdx];
3967 for (
unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3968 Result->Provenance[BitIdx] =
RHS->Provenance[BitIdx + StartBitRHS];
3982 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3983 Result->Provenance[BitIdx] = BitIdx;
3989 if (
From % 8 != To % 8)
4004 Instruction *
I,
bool MatchBSwaps,
bool MatchBitReversals,
4011 if (!MatchBSwaps && !MatchBitReversals)
4013 Type *ITy =
I->getType();
4018 bool FoundRoot =
false;
4019 std::map<Value *, std::optional<BitPart>> BPS;
4026 [](int8_t
I) {
return I == BitPart::Unset || 0 <=
I; }) &&
4027 "Illegal bit provenance index");
4030 Type *DemandedTy = ITy;
4031 if (BitProvenance.
back() == BitPart::Unset) {
4032 while (!BitProvenance.
empty() && BitProvenance.
back() == BitPart::Unset)
4033 BitProvenance = BitProvenance.
drop_back();
4034 if (BitProvenance.
empty())
4037 if (
auto *IVecTy = dyn_cast<VectorType>(ITy))
4038 DemandedTy = VectorType::get(DemandedTy, IVecTy);
4049 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
4050 bool OKForBitReverse = MatchBitReversals;
4051 for (
unsigned BitIdx = 0;
4052 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
4053 if (BitProvenance[BitIdx] == BitPart::Unset) {
4060 BitIdx, DemandedBW);
4065 Intrin = Intrinsic::bswap;
4066 else if (OKForBitReverse)
4067 Intrin = Intrinsic::bitreverse;
4072 Value *Provider = Res->Provider;
4075 if (DemandedTy != Provider->
getType()) {
4086 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
4092 if (ITy != Result->getType()) {
4109 if (
F && !
F->hasLocalLinkage() &&
F->hasName() &&
4111 !
F->doesNotAccessMemory())
4117 if (
I->getOperand(OpIdx)->getType()->isMetadataTy())
4121 if (!isa<Constant>(
I->getOperand(OpIdx)))
4124 switch (
I->getOpcode()) {
4127 case Instruction::Call:
4128 case Instruction::Invoke: {
4129 const auto &CB = cast<CallBase>(*
I);
4132 if (CB.isInlineAsm())
4137 if (CB.isBundleOperand(OpIdx))
4140 if (OpIdx < CB.arg_size()) {
4143 if (isa<IntrinsicInst>(CB) &&
4144 OpIdx >= CB.getFunctionType()->getNumParams()) {
4146 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
4151 if (CB.getIntrinsicID() == Intrinsic::gcroot)
4155 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
4160 return !isa<IntrinsicInst>(CB);
4162 case Instruction::ShuffleVector:
4165 case Instruction::Switch:
4166 case Instruction::ExtractValue:
4169 case Instruction::InsertValue:
4172 case Instruction::Alloca:
4176 return !cast<AllocaInst>(
I)->isStaticAlloca();
4177 case Instruction::GetElementPtr:
4181 for (
auto E = std::next(It, OpIdx); It != E; ++It)
4190 if (
Constant *
C = dyn_cast<Constant>(Condition))
4194 Value *NotCondition;
4196 return NotCondition;
4199 Instruction *Inst = dyn_cast<Instruction>(Condition);
4202 else if (
Argument *Arg = dyn_cast<Argument>(Condition))
4204 assert(Parent &&
"Unsupported condition to invert");
4215 if (Inst && !isa<PHINode>(Inst))
4216 Inverted->insertAfter(Inst);
4226 bool Changed =
false;
4228 if (!
F.hasFnAttribute(Attribute::NoSync) &&
4229 F.doesNotAccessMemory() && !
F.isConvergent()) {
4235 if (!
F.hasFnAttribute(Attribute::NoFree) &&
F.onlyReadsMemory()) {
4236 F.setDoesNotFreeMemory();
4241 if (!
F.hasFnAttribute(Attribute::MustProgress) &&
F.willReturn()) {
4242 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")
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
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
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.
const uint64_t * getRawData() const
This function returns a pointer to the internal storage of the APInt.
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.
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
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 flushTerminatorDbgRecords()
Eject any debug-info trailing at the end of a block.
const Function * getParent() const
Return the enclosing method, or null if none.
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
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.
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
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
BinaryOps getOpcode() const
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
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, InsertPosition InsertBefore=nullptr)
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="", InsertPosition InsertBefore=nullptr)
static CastInst * CreateIntegerCast(Value *S, Type *Ty, bool isSigned, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a ZExt, BitCast, or Trunc for int -> int casts.
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, InsertPosition InsertBefore=nullptr)
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.
DIExpression * foldConstantMath()
Try to shorten an expression with constant math operations that can be evaluated at compile time.
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
std::optional< uint64_t > getActiveBits(DIVariable *Var)
Return the number of bits that have an active value, i.e.
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...
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.
Instruction * MarkedInstr
Link back to the Instruction that owns this marker.
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, bool AllowEmpty=false)
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.
DIExpression * getExpression() const
Record of a variable value-assignment, aka a non instruction representation of the dbg....
bool isAddressOfVariable() const
Does this describe the address of a local variable.
DbgVariableRecord * clone() const
void setExpression(DIExpression *NewExpr)
DIExpression * getExpression() const
Value * getVariableLocationOp(unsigned OpIdx) const
DILocalVariable * getVariable() const
unsigned getNumVariableLocationOps() const
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
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 deleteBB(BasicBlock *DelBB)
Delete DelBB.
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
void applyUpdatesPermissive(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
bool hasDomTree() const
Returns true if it holds a DomTreeT.
bool isBBPendingDeletion(BasicBlockT *DelBB) const
Returns true if DelBB is awaiting deletion.
void recalculate(FuncT &F)
Notify DTU that the entry block was replaced.
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...
iterator_range< simple_ilist< DbgRecord >::iterator > getDbgRecordRange() const
Return a range over the DbgRecords attached to this instruction.
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.
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.
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.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
A wrapper class for inspecting calls to intrinsic functions.
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, InsertPosition InsertBefore=nullptr)
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
Value * getPointerOperand()
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
MDNode * createRange(const APInt &Lo, const APInt &Hi)
Return metadata describing the range [Lo, Hi).
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.
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 isFloatingPointTy() const
Return true if this is one of the floating-point types.
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.
const ParentTy * getParent() const
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)
CastInst_match< OpTy, TruncInst > m_Trunc(const OpTy &Op)
Matches Trunc.
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.
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.
pred_iterator pred_end(BasicBlock *BB)
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...
unsigned replaceDominatedUsesWithIf(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge, function_ref< bool(const Use &U, const Value *To)> ShouldReplace)
Replace each use of 'From' with 'To' if that use is dominated by the given edge and the callback Shou...
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 salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns, ArrayRef< DbgVariableRecord * > DPInsns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the debug info intrinsics describing a value.
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...
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.
void remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst)
Remap the operands of the debug records attached to Inst, and the operands of Inst itself if it's a d...
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.
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
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.
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.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
pred_iterator pred_begin(BasicBlock *BB)
bool 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.
void setBranchWeights(Instruction &I, ArrayRef< uint32_t > Weights, bool IsExpected)
Create a new branch_weights metadata node and add or overwrite a prof metadata reference to instructi...
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.
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)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
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 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)
TinyPtrVector< DbgVariableRecord * > findDVRDeclares(Value *V)
As above, for DVRDeclares.
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 DbgVariableRecord 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.