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);
1615 "address of variable must have exactly 1 location operand.");
1618 if (std::optional<TypeSize> FragmentSize =
1619 AI->getAllocationSizeInBits(
DL)) {
1620 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1631 TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1641 "address of variable must have exactly 1 location operand.");
1644 if (std::optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(
DL)) {
1645 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1659 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1668 Instr->getParent()->insertDbgRecordBefore(DV, Instr);
1676 auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1685 Instr->getParent()->insertDbgRecordAfter(DV, &*Instr);
1695 assert(DIVar &&
"Missing variable");
1697 Value *DV = SI->getValueOperand();
1714 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1724 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DII
1740 assert(DIVar &&
"Missing variable");
1746 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1765 assert(DIVar &&
"Missing variable");
1767 Value *DV = SI->getValueOperand();
1784 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1794 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DVR
1805 SI->getParent()->insertDbgRecordBefore(NewDVR, SI->getIterator());
1814 assert(DIVar &&
"Missing variable");
1823 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: "
1836 if (InsertionPt != BB->
end()) {
1846 assert(DIVar &&
"Missing variable");
1852 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: "
1886 assert(DIVar &&
"Missing variable");
1895 LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: "
1908 if (InsertionPt != BB->
end()) {
1917 bool Changed =
false;
1921 for (
auto &FI :
F) {
1923 if (
auto *DDI = dyn_cast<DbgDeclareInst>(&BI))
1926 if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
1935 auto LowerOne = [&](
auto *DDI) {
1937 dyn_cast_or_null<AllocaInst>(DDI->getVariableLocationOp(0));
1949 if (LoadInst *LI = dyn_cast<LoadInst>(U))
1950 return LI->isVolatile();
1951 if (StoreInst *SI = dyn_cast<StoreInst>(U))
1952 return SI->isVolatile();
1959 while (!WorkList.
empty()) {
1961 for (
const auto &AIUse : V->uses()) {
1962 User *U = AIUse.getUser();
1963 if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
1964 if (AIUse.getOperandNo() == 1)
1966 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
1968 }
else if (
CallInst *CI = dyn_cast<CallInst>(U)) {
1972 if (!CI->isLifetimeStartOrEnd()) {
1980 }
else if (
BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1981 if (BI->getType()->isPointerTy())
1986 DDI->eraseFromParent();
2006 assert(BB &&
"No BasicBlock to clone DbgVariableRecord(s) from.");
2007 if (InsertedPHIs.
size() == 0)
2012 for (
auto &
I : *BB) {
2014 for (
Value *V : DVR.location_ops())
2015 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2016 DbgValueMap.
insert({Loc, &DVR});
2019 if (DbgValueMap.
size() == 0)
2034 for (
auto PHI : InsertedPHIs) {
2039 for (
auto VI :
PHI->operand_values()) {
2040 auto V = DbgValueMap.
find(VI);
2041 if (V != DbgValueMap.
end()) {
2043 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2044 if (NewDI == NewDbgValueMap.
end()) {
2046 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2057 for (
auto DI : NewDbgValueMap) {
2061 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2070 assert(BB &&
"No BasicBlock to clone dbg.value(s) from.");
2071 if (InsertedPHIs.
size() == 0)
2078 for (
auto &
I : *BB) {
2079 if (
auto DbgII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
2080 for (
Value *V : DbgII->location_ops())
2081 if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2082 DbgValueMap.
insert({Loc, DbgII});
2085 if (DbgValueMap.
size() == 0)
2100 for (
auto *
PHI : InsertedPHIs) {
2105 for (
auto *VI :
PHI->operand_values()) {
2106 auto V = DbgValueMap.
find(VI);
2107 if (V != DbgValueMap.
end()) {
2108 auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
2109 auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2110 if (NewDI == NewDbgValueMap.
end()) {
2111 auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
2112 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2123 for (
auto DI : NewDbgValueMap) {
2125 auto *NewDbgII = DI.second;
2127 assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2128 NewDbgII->insertBefore(&*InsertionPt);
2133 DIBuilder &Builder, uint8_t DIExprFlags,
2138 auto ReplaceOne = [&](
auto *DII) {
2139 assert(DII->getVariable() &&
"Missing variable");
2140 auto *DIExpr = DII->getExpression();
2142 DII->setExpression(DIExpr);
2143 DII->replaceVariableLocationOp(Address, NewAddress);
2149 return !DbgDeclares.
empty() || !DVRDeclares.
empty();
2158 assert(DIVar &&
"Missing variable");
2188 for (
auto *DVI : DbgUsers)
2190 DVI->getExpression(), NewAllocaAddress, DVI,
2191 nullptr, Builder,
Offset);
2196 DVR->getExpression(), NewAllocaAddress,
nullptr,
2210 Instruction *
I = dyn_cast<Instruction>(Assign->getAddress());
2215 assert(!Assign->getAddressExpression()->getFragmentInfo().has_value() &&
2216 "address-expression shouldn't have fragment info");
2229 Assign->getAddressExpression(), Ops, 0,
false);
2231 "address-expression shouldn't have fragment info");
2234 if (AdditionalValues.
empty()) {
2235 Assign->setAddress(NewV);
2236 Assign->setAddressExpression(SalvagedExpr);
2238 Assign->setKillAddress();
2248 const unsigned MaxDebugArgs = 16;
2249 const unsigned MaxExpressionSize = 128;
2250 bool Salvaged =
false;
2252 for (
auto *DII : DbgUsers) {
2253 if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) {
2254 if (DAI->getAddress() == &
I) {
2258 if (DAI->getValue() != &
I)
2264 bool StackValue = isa<DbgValueInst>(DII);
2265 auto DIILocation = DII->location_ops();
2268 "DbgVariableIntrinsic must use salvaged instruction as its location");
2274 Value *Op0 =
nullptr;
2276 auto LocItr =
find(DIILocation, &
I);
2277 while (SalvagedExpr && LocItr != DIILocation.end()) {
2279 unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
2286 LocItr = std::find(++LocItr, DIILocation.end(), &
I);
2293 DII->replaceVariableLocationOp(&
I, Op0);
2294 bool IsValidSalvageExpr = SalvagedExpr->
getNumElements() <= MaxExpressionSize;
2295 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2296 DII->setExpression(SalvagedExpr);
2297 }
else if (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
2298 DII->getNumVariableLocationOps() + AdditionalValues.
size() <=
2300 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2305 DII->setKillLocation();
2311 for (
auto *DVR : DPUsers) {
2312 if (DVR->isDbgAssign()) {
2313 if (DVR->getAddress() == &
I) {
2317 if (DVR->getValue() != &
I)
2325 DVR->getType() != DbgVariableRecord::LocationType::Declare;
2326 auto DVRLocation = DVR->location_ops();
2329 "DbgVariableIntrinsic must use salvaged instruction as its location");
2335 Value *Op0 =
nullptr;
2337 auto LocItr =
find(DVRLocation, &
I);
2338 while (SalvagedExpr && LocItr != DVRLocation.end()) {
2340 unsigned LocNo = std::distance(DVRLocation.begin(), LocItr);
2347 LocItr = std::find(++LocItr, DVRLocation.end(), &
I);
2354 DVR->replaceVariableLocationOp(&
I, Op0);
2355 bool IsValidSalvageExpr =
2357 if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2358 DVR->setExpression(SalvagedExpr);
2359 }
else if (DVR->getType() != DbgVariableRecord::LocationType::Declare &&
2360 IsValidSalvageExpr &&
2361 DVR->getNumVariableLocationOps() + AdditionalValues.
size() <=
2363 DVR->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2369 DVR->setKillLocation();
2378 for (
auto *DII : DbgUsers)
2379 DII->setKillLocation();
2381 for (
auto *DVR : DPUsers)
2382 DVR->setKillLocation();
2389 unsigned BitWidth =
DL.getIndexSizeInBits(
GEP->getPointerAddressSpace());
2393 if (!
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
2395 if (!VariableOffsets.
empty() && !CurrentLocOps) {
2396 Opcodes.
insert(Opcodes.
begin(), {dwarf::DW_OP_LLVM_arg, 0});
2399 for (
const auto &
Offset : VariableOffsets) {
2402 "Expected strictly positive multiplier for offset.");
2404 Offset.second.getZExtValue(), dwarf::DW_OP_mul,
2405 dwarf::DW_OP_plus});
2408 return GEP->getOperand(0);
2413 case Instruction::Add:
2414 return dwarf::DW_OP_plus;
2415 case Instruction::Sub:
2416 return dwarf::DW_OP_minus;
2417 case Instruction::Mul:
2418 return dwarf::DW_OP_mul;
2419 case Instruction::SDiv:
2420 return dwarf::DW_OP_div;
2421 case Instruction::SRem:
2422 return dwarf::DW_OP_mod;
2423 case Instruction::Or:
2424 return dwarf::DW_OP_or;
2425 case Instruction::And:
2426 return dwarf::DW_OP_and;
2427 case Instruction::Xor:
2428 return dwarf::DW_OP_xor;
2429 case Instruction::Shl:
2430 return dwarf::DW_OP_shl;
2431 case Instruction::LShr:
2432 return dwarf::DW_OP_shr;
2433 case Instruction::AShr:
2434 return dwarf::DW_OP_shra;
2445 if (!CurrentLocOps) {
2450 AdditionalValues.
push_back(
I->getOperand(1));
2457 auto *ConstInt = dyn_cast<ConstantInt>(BI->
getOperand(1));
2459 if (ConstInt && ConstInt->getBitWidth() > 64)
2465 uint64_t Val = ConstInt->getSExtValue();
2468 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2469 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2473 Opcodes.
append({dwarf::DW_OP_constu, Val});
2492 return dwarf::DW_OP_eq;
2494 return dwarf::DW_OP_ne;
2497 return dwarf::DW_OP_gt;
2500 return dwarf::DW_OP_ge;
2503 return dwarf::DW_OP_lt;
2506 return dwarf::DW_OP_le;
2516 auto *ConstInt = dyn_cast<ConstantInt>(Icmp->
getOperand(1));
2518 if (ConstInt && ConstInt->getBitWidth() > 64)
2526 uint64_t Val = ConstInt->getSExtValue();
2544 auto &M = *
I.getModule();
2545 auto &
DL = M.getDataLayout();
2547 if (
auto *CI = dyn_cast<CastInst>(&
I)) {
2548 Value *FromValue = CI->getOperand(0);
2550 if (CI->isNoopCast(
DL)) {
2559 !(isa<TruncInst>(&
I) || isa<SExtInst>(&
I) || isa<ZExtInst>(&
I) ||
2560 isa<IntToPtrInst>(&
I) || isa<PtrToIntInst>(&
I)))
2564 if (FromType->isPointerTy())
2565 FromType =
DL.getIntPtrType(FromType);
2567 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2572 Ops.
append(ExtOps.begin(), ExtOps.end());
2576 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
2578 if (
auto *BI = dyn_cast<BinaryOperator>(&
I))
2580 if (
auto *IC = dyn_cast<ICmpInst>(&
I))
2607 bool Changed =
false;
2611 if (isa<Instruction>(&To)) {
2612 bool DomPointAfterFrom =
From.getNextNonDebugInstruction() == &DomPoint;
2614 for (
auto *DII :
Users) {
2624 }
else if (!DT.
dominates(&DomPoint, DII)) {
2625 UndefOrSalvage.
insert(DII);
2630 for (
auto *DVR : DPUsers) {
2634 if (isa<DbgVariableIntrinsic>(NextNonDebug))
2637 if (DomPointAfterFrom && NextNonDebug == &DomPoint) {
2643 }
else if (!DT.
dominates(&DomPoint, MarkedInstr)) {
2644 UndefOrSalvageDVR.
insert(DVR);
2650 for (
auto *DII :
Users) {
2651 if (UndefOrSalvage.
count(DII))
2663 for (
auto *DVR : DPUsers) {
2664 if (UndefOrSalvageDVR.
count(DVR))
2677 if (!UndefOrSalvage.
empty() || !UndefOrSalvageDVR.
empty()) {
2701 bool SameSize =
DL.getTypeSizeInBits(FromTy) ==
DL.getTypeSizeInBits(ToTy);
2702 bool LosslessConversion = !
DL.isNonIntegralPointerType(FromTy) &&
2703 !
DL.isNonIntegralPointerType(ToTy);
2704 return SameSize && LosslessConversion;
2714 if (!
From.isUsedByMetadata())
2717 assert(&
From != &To &&
"Can't replace something with itself");
2726 return DVR.getExpression();
2740 assert(FromBits != ToBits &&
"Unexpected no-op conversion");
2744 if (FromBits < ToBits)
2755 return std::nullopt;
2757 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2769 return std::nullopt;
2771 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2785 bool Changed =
false;
2787 I->dropDbgRecords();
2788 for (
Use &U :
I->operands()) {
2790 if (isa<Instruction>(
Op) && !
Op->getType()->isTokenTy()) {
2800std::pair<unsigned, unsigned>
2802 unsigned NumDeadInst = 0;
2803 unsigned NumDeadDbgInst = 0;
2810 while (EndInst != &BB->
front()) {
2822 if (isa<DbgInfoIntrinsic>(Inst))
2830 return {NumDeadInst, NumDeadDbgInst};
2846 Successor->removePredecessor(BB, PreserveLCSSA);
2851 UI->setDebugLoc(
I->getDebugLoc());
2854 unsigned NumInstrsRemoved = 0;
2856 while (BBI != BBE) {
2857 if (!BBI->use_empty())
2859 BBI++->eraseFromParent();
2865 for (
BasicBlock *UniqueSuccessor : UniqueSuccessors)
2866 Updates.
push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2870 return NumInstrsRemoved;
2889 auto NewWeights =
uint32_t(TotalWeight) != TotalWeight
2892 NewCall->
setMetadata(LLVMContext::MD_prof, NewWeights);
2915 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2944 UnwindEdge, InvokeArgs, OpBundles, CI->
getName(), BB);
2951 DTU->
applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2958 Split->front().eraseFromParent();
2969 bool Changed =
false;
2977 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
2978 Value *Callee = CI->getCalledOperand();
2980 if (
Function *
F = dyn_cast<Function>(Callee)) {
2981 auto IntrinsicID =
F->getIntrinsicID();
2986 if (IntrinsicID == Intrinsic::assume) {
2993 }
else if (IntrinsicID == Intrinsic::experimental_guard) {
3004 if (!isa<UnreachableInst>(CI->getNextNode())) {
3010 }
else if ((isa<ConstantPointerNull>(Callee) &&
3012 cast<PointerType>(Callee->getType())
3013 ->getAddressSpace())) ||
3014 isa<UndefValue>(Callee)) {
3019 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
3023 if (!isa<UnreachableInst>(CI->getNextNonDebugInstruction())) {
3030 }
else if (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3036 if (SI->isVolatile())
continue;
3040 if (isa<UndefValue>(
Ptr) ||
3041 (isa<ConstantPointerNull>(
Ptr) &&
3043 SI->getPointerAddressSpace()))) {
3052 if (
auto *II = dyn_cast<InvokeInst>(Terminator)) {
3054 Value *Callee = II->getCalledOperand();
3055 if ((isa<ConstantPointerNull>(Callee) &&
3057 isa<UndefValue>(Callee)) {
3061 if (II->doesNotReturn() &&
3062 !isa<UnreachableInst>(II->getNormalDest()->front())) {
3068 BasicBlock *OrigNormalDest = II->getNormalDest();
3072 Ctx, OrigNormalDest->
getName() +
".unreachable",
3073 II->getFunction(), OrigNormalDest);
3075 II->setNormalDest(UnreachableNormalDest);
3078 {{DominatorTree::Delete, BB, OrigNormalDest},
3079 {DominatorTree::Insert, BB, UnreachableNormalDest}});
3083 if (II->use_empty() && !II->mayHaveSideEffects()) {
3085 BasicBlock *NormalDestBB = II->getNormalDest();
3086 BasicBlock *UnwindDestBB = II->getUnwindDest();
3089 II->eraseFromParent();
3091 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
3097 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
3099 struct CatchPadDenseMapInfo {
3114 if (
LHS == getEmptyKey() ||
LHS == getTombstoneKey() ||
3115 RHS == getEmptyKey() ||
RHS == getTombstoneKey())
3117 return LHS->isIdenticalTo(
RHS);
3128 E = CatchSwitch->handler_end();
3132 ++NumPerSuccessorCases[HandlerBB];
3133 auto *CatchPad = cast<CatchPadInst>(HandlerBB->
getFirstNonPHI());
3134 if (!HandlerSet.insert({CatchPad, Empty}).second) {
3136 --NumPerSuccessorCases[HandlerBB];
3137 CatchSwitch->removeHandler(
I);
3144 std::vector<DominatorTree::UpdateType> Updates;
3145 for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
3147 Updates.push_back({DominatorTree::Delete, BB,
I.first});
3148 DTU->applyUpdates(Updates);
3156 }
while (!Worklist.
empty());
3163 if (
auto *II = dyn_cast<InvokeInst>(TI))
3169 if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
3171 UnwindDest = CRI->getUnwindDest();
3172 }
else if (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
3174 CatchSwitch->getParentPad(),
nullptr, CatchSwitch->getNumHandlers(),
3175 CatchSwitch->getName(), CatchSwitch->getIterator());
3176 for (
BasicBlock *PadBB : CatchSwitch->handlers())
3177 NewCatchSwitch->addHandler(PadBB);
3179 NewTI = NewCatchSwitch;
3180 UnwindDest = CatchSwitch->getUnwindDest();
3191 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
3204 if (Reachable.
size() ==
F.size())
3213 if (Reachable.
count(&BB))
3218 BlocksToRemove.
insert(&BB);
3221 if (BlocksToRemove.
empty())
3225 NumRemoved += BlocksToRemove.
size();
3238 K->dropUnknownNonDebugMetadata(KnownIDs);
3239 K->getAllMetadataOtherThanDebugLoc(
Metadata);
3241 unsigned Kind = MD.first;
3247 K->setMetadata(Kind,
nullptr);
3249 case LLVMContext::MD_dbg:
3251 case LLVMContext::MD_DIAssignID:
3252 K->mergeDIAssignID(J);
3254 case LLVMContext::MD_tbaa:
3257 case LLVMContext::MD_alias_scope:
3260 case LLVMContext::MD_noalias:
3261 case LLVMContext::MD_mem_parallel_loop_access:
3264 case LLVMContext::MD_access_group:
3265 K->setMetadata(LLVMContext::MD_access_group,
3268 case LLVMContext::MD_range:
3269 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3272 case LLVMContext::MD_fpmath:
3275 case LLVMContext::MD_invariant_load:
3279 K->setMetadata(Kind, JMD);
3281 case LLVMContext::MD_nonnull:
3282 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3283 K->setMetadata(Kind, JMD);
3285 case LLVMContext::MD_invariant_group:
3288 case LLVMContext::MD_mmra:
3291 case LLVMContext::MD_align:
3292 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
3296 case LLVMContext::MD_dereferenceable:
3297 case LLVMContext::MD_dereferenceable_or_null:
3299 K->setMetadata(Kind,
3302 case LLVMContext::MD_preserve_access_index:
3305 case LLVMContext::MD_noundef:
3308 K->setMetadata(Kind, JMD);
3310 case LLVMContext::MD_nontemporal:
3312 K->setMetadata(Kind, JMD);
3314 case LLVMContext::MD_prof:
3326 if (
auto *JMD = J->
getMetadata(LLVMContext::MD_invariant_group))
3327 if (isa<LoadInst>(K) || isa<StoreInst>(K))
3328 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
3333 auto JMMRA = J->
getMetadata(LLVMContext::MD_mmra);
3334 auto KMMRA = K->getMetadata(LLVMContext::MD_mmra);
3335 if (JMMRA || KMMRA) {
3336 K->setMetadata(LLVMContext::MD_mmra,
3343 unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
3344 LLVMContext::MD_alias_scope,
3345 LLVMContext::MD_noalias,
3346 LLVMContext::MD_range,
3347 LLVMContext::MD_fpmath,
3348 LLVMContext::MD_invariant_load,
3349 LLVMContext::MD_nonnull,
3350 LLVMContext::MD_invariant_group,
3351 LLVMContext::MD_align,
3352 LLVMContext::MD_dereferenceable,
3353 LLVMContext::MD_dereferenceable_or_null,
3354 LLVMContext::MD_access_group,
3355 LLVMContext::MD_preserve_access_index,
3356 LLVMContext::MD_prof,
3357 LLVMContext::MD_nontemporal,
3358 LLVMContext::MD_noundef,
3359 LLVMContext::MD_mmra};
3365 Source.getAllMetadata(MD);
3368 const DataLayout &
DL = Source.getModule()->getDataLayout();
3369 for (
const auto &MDPair : MD) {
3370 unsigned ID = MDPair.first;
3380 case LLVMContext::MD_dbg:
3381 case LLVMContext::MD_tbaa:
3382 case LLVMContext::MD_prof:
3383 case LLVMContext::MD_fpmath:
3384 case LLVMContext::MD_tbaa_struct:
3385 case LLVMContext::MD_invariant_load:
3386 case LLVMContext::MD_alias_scope:
3387 case LLVMContext::MD_noalias:
3388 case LLVMContext::MD_nontemporal:
3389 case LLVMContext::MD_mem_parallel_loop_access:
3390 case LLVMContext::MD_access_group:
3391 case LLVMContext::MD_noundef:
3396 case LLVMContext::MD_nonnull:
3400 case LLVMContext::MD_align:
3401 case LLVMContext::MD_dereferenceable:
3402 case LLVMContext::MD_dereferenceable_or_null:
3408 case LLVMContext::MD_range:
3416 auto *ReplInst = dyn_cast<Instruction>(Repl);
3425 if (isa<OverflowingBinaryOperator>(ReplInst) &&
3432 else if (!isa<LoadInst>(
I))
3433 ReplInst->andIRFlags(
I);
3447template <
typename RootType,
typename ShouldReplaceFn>
3449 const RootType &Root,
3450 const ShouldReplaceFn &ShouldReplace) {
3455 if (!ShouldReplace(Root, U))
3459 dbgs() <<
"' with " << *To <<
" in " << *U.getUser() <<
"\n");
3468 auto *BB =
From->getParent();
3472 auto *
I = cast<Instruction>(U.getUser());
3473 if (
I->getParent() == BB)
3487 return ::replaceDominatedUsesWith(
From, To, Root, Dominates);
3493 auto Dominates = [&DT](
const BasicBlock *BB,
const Use &U) {
3496 return ::replaceDominatedUsesWith(
From, To, BB, Dominates);
3502 auto DominatesAndShouldReplace =
3504 return DT.
dominates(Root, U) && ShouldReplace(U, To);
3506 return ::replaceDominatedUsesWith(
From, To, Root, DominatesAndShouldReplace);
3512 auto DominatesAndShouldReplace = [&DT, &ShouldReplace,
3514 return DT.
dominates(BB, U) && ShouldReplace(U, To);
3516 return ::replaceDominatedUsesWith(
From, To, BB, DominatesAndShouldReplace);
3522 if (Call->hasFnAttr(
"gc-leaf-function"))
3524 if (
const Function *
F = Call->getCalledFunction()) {
3525 if (
F->hasFnAttribute(
"gc-leaf-function"))
3528 if (
auto IID =
F->getIntrinsicID()) {
3530 return IID != Intrinsic::experimental_gc_statepoint &&
3531 IID != Intrinsic::experimental_deoptimize &&
3532 IID != Intrinsic::memcpy_element_unordered_atomic &&
3533 IID != Intrinsic::memmove_element_unordered_atomic;
3550 auto *NewTy = NewLI.
getType();
3553 if (NewTy->isPointerTy()) {
3560 if (!NewTy->isIntegerTy())
3565 auto *ITy = cast<IntegerType>(NewTy);
3575 auto *NewTy = NewLI.
getType();
3577 if (NewTy == OldLI.
getType()) {
3586 if (!NewTy->isPointerTy())
3589 unsigned BitWidth =
DL.getPointerTypeSizeInBits(NewTy);
3601 for (
auto *DII : DbgUsers)
3603 for (
auto *DVR : DPUsers)
3604 DVR->eraseFromParent();
3633 I->dropUBImplyingAttrsAndMetadata();
3634 if (
I->isUsedByMetadata())
3637 I->dropDbgRecords();
3638 if (
I->isDebugOrPseudoInst()) {
3640 II =
I->eraseFromParent();
3654 const APInt &API = cast<ConstantInt>(&CV)->getValue();
3655 std::optional<int64_t> InitIntOpt = API.
trySExtValue();
3657 static_cast<uint64_t>(*InitIntOpt))
3661 if (isa<ConstantInt>(
C))
3662 return createIntegerExpression(
C);
3664 auto *
FP = dyn_cast<ConstantFP>(&
C);
3676 if (isa<ConstantPointerNull>(
C))
3680 if (CE->getOpcode() == Instruction::IntToPtr) {
3681 const Value *V = CE->getOperand(0);
3682 if (
auto CI = dyn_cast_or_null<ConstantInt>(V))
3683 return createIntegerExpression(*CI);
3689 auto RemapDebugOperands = [&Mapping](
auto *DV,
auto Set) {
3690 for (
auto *
Op : Set) {
3692 if (
I != Mapping.
end())
3693 DV->replaceVariableLocationOp(
Op,
I->second,
true);
3696 auto RemapAssignAddress = [&Mapping](
auto *DA) {
3697 auto I = Mapping.
find(DA->getAddress());
3698 if (
I != Mapping.
end())
3699 DA->setAddress(
I->second);
3701 if (
auto DVI = dyn_cast<DbgVariableIntrinsic>(Inst))
3702 RemapDebugOperands(DVI, DVI->location_ops());
3703 if (
auto DAI = dyn_cast<DbgAssignIntrinsic>(Inst))
3704 RemapAssignAddress(DAI);
3706 RemapDebugOperands(&DVR, DVR.location_ops());
3707 if (DVR.isDbgAssign())
3708 RemapAssignAddress(&DVR);
3717 BitPart(
Value *
P,
unsigned BW) : Provider(
P) {
3718 Provenance.resize(BW);
3728 enum { Unset = -1 };
3760static const std::optional<BitPart> &
3762 std::map<
Value *, std::optional<BitPart>> &BPS,
int Depth,
3764 auto I = BPS.find(V);
3768 auto &Result = BPS[V] = std::nullopt;
3769 auto BitWidth = V->getType()->getScalarSizeInBits();
3777 LLVM_DEBUG(
dbgs() <<
"collectBitParts max recursion depth reached.\n");
3781 if (
auto *
I = dyn_cast<Instruction>(V)) {
3789 Depth + 1, FoundRoot);
3790 if (!
A || !
A->Provider)
3794 Depth + 1, FoundRoot);
3795 if (!
B ||
A->Provider !=
B->Provider)
3799 Result = BitPart(
A->Provider,
BitWidth);
3800 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx) {
3801 if (
A->Provenance[BitIdx] != BitPart::Unset &&
3802 B->Provenance[BitIdx] != BitPart::Unset &&
3803 A->Provenance[BitIdx] !=
B->Provenance[BitIdx])
3804 return Result = std::nullopt;
3806 if (
A->Provenance[BitIdx] == BitPart::Unset)
3807 Result->Provenance[BitIdx] =
B->Provenance[BitIdx];
3809 Result->Provenance[BitIdx] =
A->Provenance[BitIdx];
3817 const APInt &BitShift = *
C;
3824 if (!MatchBitReversals && (BitShift.
getZExtValue() % 8) != 0)
3828 Depth + 1, FoundRoot);
3834 auto &
P = Result->Provenance;
3835 if (
I->getOpcode() == Instruction::Shl) {
3849 const APInt &AndMask = *
C;
3853 unsigned NumMaskedBits = AndMask.
popcount();
3854 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3858 Depth + 1, FoundRoot);
3863 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3865 if (AndMask[BitIdx] == 0)
3866 Result->Provenance[BitIdx] = BitPart::Unset;
3873 Depth + 1, FoundRoot);
3877 Result = BitPart(Res->Provider,
BitWidth);
3878 auto NarrowBitWidth =
X->getType()->getScalarSizeInBits();
3879 for (
unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3880 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3881 for (
unsigned BitIdx = NarrowBitWidth; BitIdx <
BitWidth; ++BitIdx)
3882 Result->Provenance[BitIdx] = BitPart::Unset;
3889 Depth + 1, FoundRoot);
3893 Result = BitPart(Res->Provider,
BitWidth);
3894 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3895 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3903 Depth + 1, FoundRoot);
3907 Result = BitPart(Res->Provider,
BitWidth);
3908 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3909 Result->Provenance[(
BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3916 Depth + 1, FoundRoot);
3921 Result = BitPart(Res->Provider,
BitWidth);
3922 for (
unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3923 unsigned ByteBitOfs = ByteIdx * 8;
3924 for (
unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3925 Result->Provenance[(
BitWidth - 8 - ByteBitOfs) + BitIdx] =
3926 Res->Provenance[ByteBitOfs + BitIdx];
3943 if (!MatchBitReversals && (ModAmt % 8) != 0)
3948 Depth + 1, FoundRoot);
3949 if (!
LHS || !
LHS->Provider)
3953 Depth + 1, FoundRoot);
3954 if (!
RHS ||
LHS->Provider !=
RHS->Provider)
3957 unsigned StartBitRHS =
BitWidth - ModAmt;
3959 for (
unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3960 Result->Provenance[BitIdx + ModAmt] =
LHS->Provenance[BitIdx];
3961 for (
unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3962 Result->Provenance[BitIdx] =
RHS->Provenance[BitIdx + StartBitRHS];
3976 for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3977 Result->Provenance[BitIdx] = BitIdx;
3983 if (
From % 8 != To % 8)
3998 Instruction *
I,
bool MatchBSwaps,
bool MatchBitReversals,
4005 if (!MatchBSwaps && !MatchBitReversals)
4007 Type *ITy =
I->getType();
4012 bool FoundRoot =
false;
4013 std::map<Value *, std::optional<BitPart>> BPS;
4020 [](int8_t
I) {
return I == BitPart::Unset || 0 <=
I; }) &&
4021 "Illegal bit provenance index");
4024 Type *DemandedTy = ITy;
4025 if (BitProvenance.
back() == BitPart::Unset) {
4026 while (!BitProvenance.
empty() && BitProvenance.
back() == BitPart::Unset)
4027 BitProvenance = BitProvenance.
drop_back();
4028 if (BitProvenance.
empty())
4031 if (
auto *IVecTy = dyn_cast<VectorType>(ITy))
4032 DemandedTy = VectorType::get(DemandedTy, IVecTy);
4043 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
4044 bool OKForBitReverse = MatchBitReversals;
4045 for (
unsigned BitIdx = 0;
4046 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
4047 if (BitProvenance[BitIdx] == BitPart::Unset) {
4054 BitIdx, DemandedBW);
4059 Intrin = Intrinsic::bswap;
4060 else if (OKForBitReverse)
4061 Intrin = Intrinsic::bitreverse;
4066 Value *Provider = Res->Provider;
4069 if (DemandedTy != Provider->
getType()) {
4080 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
4086 if (ITy != Result->getType()) {
4103 if (
F && !
F->hasLocalLinkage() &&
F->hasName() &&
4105 !
F->doesNotAccessMemory())
4111 if (
I->getOperand(OpIdx)->getType()->isMetadataTy())
4115 if (!isa<Constant>(
I->getOperand(OpIdx)))
4118 switch (
I->getOpcode()) {
4121 case Instruction::Call:
4122 case Instruction::Invoke: {
4123 const auto &CB = cast<CallBase>(*
I);
4126 if (CB.isInlineAsm())
4131 if (CB.isBundleOperand(OpIdx))
4134 if (OpIdx < CB.arg_size()) {
4137 if (isa<IntrinsicInst>(CB) &&
4138 OpIdx >= CB.getFunctionType()->getNumParams()) {
4140 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
4145 if (CB.getIntrinsicID() == Intrinsic::gcroot)
4149 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
4154 return !isa<IntrinsicInst>(CB);
4156 case Instruction::ShuffleVector:
4159 case Instruction::Switch:
4160 case Instruction::ExtractValue:
4163 case Instruction::InsertValue:
4166 case Instruction::Alloca:
4170 return !cast<AllocaInst>(
I)->isStaticAlloca();
4171 case Instruction::GetElementPtr:
4175 for (
auto E = std::next(It, OpIdx); It != E; ++It)
4184 if (
Constant *
C = dyn_cast<Constant>(Condition))
4188 Value *NotCondition;
4190 return NotCondition;
4193 Instruction *Inst = dyn_cast<Instruction>(Condition);
4196 else if (
Argument *Arg = dyn_cast<Argument>(Condition))
4198 assert(Parent &&
"Unsupported condition to invert");
4209 if (Inst && !isa<PHINode>(Inst))
4210 Inverted->insertAfter(Inst);
4220 bool Changed =
false;
4222 if (!
F.hasFnAttribute(Attribute::NoSync) &&
4223 F.doesNotAccessMemory() && !
F.isConvergent()) {
4229 if (!
F.hasFnAttribute(Attribute::NoFree) &&
F.onlyReadsMemory()) {
4230 F.setDoesNotFreeMemory();
4235 if (!
F.hasFnAttribute(Attribute::MustProgress) &&
F.willReturn()) {
4236 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.
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.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
void insertDbgRecordAfter(DbgRecord *DR, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
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
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...
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.
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
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.
std::optional< uint64_t > getFragmentSizeInBits() const
Get the size (in bits) of the variable, or fragment of the variable that is described.
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 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...
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.
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.
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.
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.
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.
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.
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.
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.
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.